[AI] HNSW - ANN부터 파라미터 튜닝까지, RAG 검색 성능의 진짜 핵심

 

 

[AI] LLM 학습 노트 공개 - Transformer부터 RAG까지, 그리고 운영 가능한 AI 시스템을 향해

 

ㅁ 들어가며

ANN과 HNSW는 VectorDB를 활용한 RAG 구현의 “심장”이다.

  Embedding은 의미를 벡터로 바꿔주고,
  Vector Similarity는 거리를 계산해 주지만,

 

수백만 개 벡터 중에서 실제로 무엇을 얼마나 빨리 찾을 수 있느냐는
결국 ANN 인덱스가 결정한다.

 

그 중심에 있는 알고리즘이 바로 HNSW다.

이번 글에서는 다음 흐름으로 정리해 보려 한다.

• ANN이 무엇인지
• 왜 Brute-force 검색이 불가능한지
• HNSW가 어떻게 문제를 해결하는지
• 그리고 실무에서 중요한 파라미터(M, ef)를 어떻게 바라봐야 하는지

 

ㅁ ANN이란 무엇인가

ANN은 Approximate Nearest Neighbor의 약자다.
직역하면 “근사 최근접 이웃 탐색”.

완벽한 정답 대신, 충분히 가까운 결과를 매우 빠르게 찾는 방식

 

벡터 검색에서 정확한 최근접 이웃(Exact NN)을 찾으려면 모든 벡터와 거리를 계산해야 한다.

 

벡터가 N개라면:

• 시간 복잡도: O(N)
• 100만 개 → 가능
• 1억 개 → 거의 불가능

RAG에서는 이런 규모가 기본이다. 그래서 우리는 선택을 해야 한다.

  100% 정확한 검색을 포기하고,
  95~98% 정도의 Recall을 얻는 대신
  수천 배 빠른 검색을 택한다.

 

 이게 ANN의 철학이다.

 

ㅁ 왜 HNSW가 필요할까

VectorDB는 단순 저장소가 아니다.

의미 공간 탐색기다.

 

질문 벡터가 들어오면:

• 가장 가까운 의미 좌표들을 찾고
• 그 결과를 LLM에 넘긴다

문제는 “어떻게 빠르게 찾느냐”다.

 

대표적인 방식은 세 가지다.

• Flat (Brute-force)
• IVF
• HNSW

Flat은 정확하지만 느리고,
IVF는 빠르지만 품질 손실이 있고,
HNSW는 속도와 Recall의 균형이 가장 좋다.

그래서 대부분의 VectorDB가 기본 인덱스로 HNSW를 채택한다.

 

ㅁ HNSW 한 줄 요약

HNSW(Hierarchical Navigable Small World)는 
   계층적 그래프 구조를 이용해
   고차원 벡터 공간을 빠르게 탐색하는 ANN 알고리즘이다.

 

핵심 아이디어는 이것이다.

• 위에서는 대충 찾고
• 아래에서 정밀하게 찾는다

지도 앱과 매우 비슷하다.

고속도로 → 일반도로 → 골목길

 

ㅁ HNSW의 구조 — 왜 “계층적 그래프”인가

HNSW는 여러 레벨의 그래프로 구성된다.

• 상위 레벨: 노드 수 적음, 연결 길음 (대략 탐색)
• 하위 레벨: 모든 노드 존재, 촘촘한 연결 (정밀 탐색)

검색 흐름은 다음과 같다.

1. 최상위 레벨에서 시작
2. greedy하게 더 가까운 노드로 이동
3. 더 이상 개선이 없으면 한 레벨 내려감
4. 최하위 레벨에서 후보를 충분히 탐색
5. 상위 K개 반환

이 구조 덕분에 탐색 깊이는 O(log N) 수준으로 줄어든다.

 

ㅁ HNSW의 핵심 파라미터 3가지

HNSW 튜닝의 본질은 딱 세 개다.

M
ef_construction
ef_search

이 세 값이 Recall / Latency / Memory를 모두 결정한다.

 

ㅁ M — 그래프의 밀도

M은 각 노드가 가질 수 있는 최대 이웃 수다.

• 작으면: 메모리 적음, Recall 낮음
• 크면: 메모리 큼, Recall 높음

직관적으로:

   M은 “길의 개수”다.

   길이 많을수록 목적지에 도달할 확률은 높아지지만,
   지도는 무거워진다.

 

실무 기준:

• RAG 기본: 16~32
• 프로덕션 권장: 24

 

ㅁ ef_construction — 인덱스 품질

인덱스를 만들 때
   각 벡터가 연결될 후보를 얼마나 넓게 볼지 정하는 값이다.

• 낮으면: 빌드 빠름, 그래프 품질 낮음
• 높으면: 빌드 느림, 그래프 품질 높음

중요한 포인트:

   ef_construction은 인덱스 생성 시에만 사용된다.
   즉, 한 번 제대로 만들어 두는 게 중요하다.

 

권장 범위:

• 128 ~ 200

 

ㅁ ef_search — 검색 품질 (런타임 조절 가능)

검색 시 탐색할 후보 개수다.

이 값이 클수록:

• Recall 상승
• Latency 증가

작을수록:

• 빠르지만 부정확

핵심 장점:

   ef_search는 쿼리마다 바꿀 수 있다.

 

즉,

• 일반 질문: ef_search=100
• 고품질 질문: ef_search=200

같은 식의 동적 튜닝이 가능하다.

 

RAG 권장 시작점:

• ef_search = 100

 

ㅁ 실무에서 추천하는 기본 세트

RAG 기준 최소 출발점:

• M = 24
• ef_construction = 200
• ef_search = 100

여기서 시작해서:

1. Recall 측정
2. 느리면 ef_search 감소
3. 품질 부족하면 ef_search 증가
4. 그래도 부족하면 M 증가 (재인덱싱 필요)

이 순서가 가장 현실적이다.

 

ㅁ 중요한 정리

HNSW는 “알고리즘”이 아니라
   “트레이드오프 컨트롤러”에 가깝다.

 

항상 세 가지를 교환한다.

• Recall
• Latency
• Memory

완벽한 값은 없다.

서비스 요구사항에 맞는 균형점을 찾는 게 전부다.

 

ㅁ RAG 관점에서 다시 보기

RAG 파이프라인은 이렇게 이어진다.

Transformer
→ Embedding
→ Chunking
→ Vector Similarity
→ ANN(HNSW)
→ Retriever
→ Reranker
→ LLM

여기서 HNSW는 Retriever의 실제 성능을 결정한다.

 

아무리 좋은 임베딩을 써도, HNSW가 엉성하면 결과는 바로 무너진다.

 

ㅁ 마무리

처음에는 ANN이 그냥 “빠른 검색 기술”이라고 생각했다.

지금은 이렇게 느낀다.

HNSW는 RAG의 검색 품질을 설계하는 도구다.

  모델보다,
  프롬프트보다,
  심지어 임베딩보다 먼저 봐야 할 것이
  ANN과 HNSW 파라미터다.

 

RAG는 모델 문제가 아니라 시스템 문제다.

그리고 HNSW는 그 시스템의 중심에 있다.