RAG나 시맨틱 검색을 제대로 이해하려면 Elasticsearch의 dense vector 검색이 내부에서 어떻게 동작하는지 알아야 하고, 그 핵심에 HNSW가 있기 때문에 이 개념을 한 번 정리해두려고 한다.
HNSW는 Elasticsearch에서 벡터 기반 검색을 빠르게 수행하기 위해 사용하는 근사 최근접 탐색 알고리즘이다.
dense vector 검색은 모든 문서 벡터와 거리를 계산하면 정확하지만 데이터가 조금만 많아져도 성능이 급격히 나빠진다.
그래서 Elasticsearch는 정확도 일부를 포기하고 속도를 얻는 방향을 선택했고, 그 결과가 HNSW다.
HNSW를 이해하려면 먼저 벡터 공간과 최근접 이웃 검색이라는 개념을 이해해야 한다.
문장 임베딩은 문장을 고정 차원의 실수 벡터로 변환한다.
의미가 비슷한 문장은 벡터 공간에서 서로 가까운 위치에 놓이게 된다.
최근접 이웃 검색은 이 공간에서 특정 벡터와 가장 가까운 다른 벡터들을 찾는 문제다.
이때 거리 계산 방식으로 cosine similarity나 dot product 같은 함수가 사용된다.
문제는 벡터 수가 많아질수록 모든 벡터와 거리를 계산하는 방식이 현실적으로 불가능해진다는 점이다.
HNSW는 이 문제를 그래프 기반 탐색으로 해결한다.
각 벡터를 하나의 노드로 보고, 의미적으로 가까운 벡터들끼리 미리 연결해 그래프를 만든다.
이 그래프는 하나가 아니라 여러 개의 계층으로 구성된다.
상위 계층은 노드 수가 적고 연결이 성글다.
하위 계층으로 내려갈수록 노드 수가 많아지고 연결이 촘촘해진다.
이 구조를 Small World Graph라고 부른다.
Small World Graph는 몇 번의 이동만으로도 전체 공간의 임의의 노드에 도달할 수 있는 성질을 가진다.
HNSW에서 검색은 가장 위 레벨의 임의의 노드에서 시작한다.
현재 노드보다 더 가까운 이웃 노드가 있으면 그쪽으로 이동한다.
더 이상 가까워질 수 없으면 한 단계 아래 레벨로 내려간다.
이 과정을 최하위 레벨까지 반복한다.
결과적으로 전체 벡터를 보지 않고도 충분히 가까운 벡터들을 빠르게 찾을 수 있다.
이 방식은 정확한 최근접 이웃 검색이 아니라 근사 최근접 이웃 검색이다.
항상 최적의 정답을 보장하지는 않는다.
하지만 검색 속도와 메모리 사용량 대비 정확도가 매우 높다.
Elasticsearch에서 dense_vector 필드를 index=true로 설정하면 내부적으로 HNSW 인덱스가 생성된다.
이 인덱스는 일반적인 inverted index와 완전히 다른 구조다.
텍스트 검색처럼 토큰을 기준으로 찾는 것이 아니라, 벡터 간 거리 기반 탐색만 수행한다.
벡터를 추가할 때마다 HNSW 그래프에 노드가 추가되고 주변 노드들과 연결된다.
이 과정에서 m, ef_construction 같은 파라미터가 그래프 품질과 메모리 사용량에 영향을 준다.
m은 각 노드가 가질 수 있는 최대 연결 수를 의미한다.
값이 클수록 검색 정확도는 좋아지지만 메모리 사용량이 증가한다.
ef_construction은 인덱스를 만들 때 탐색 범위를 얼마나 넓게 볼지를 결정한다.
검색 시에는 ef_search가 사용되며, 값이 클수록 정확도는 높아지고 속도는 느려진다.
Elasticsearch의 벡터 검색 성능 튜닝은 대부분 이 파라미터들을 어떻게 조정하느냐의 문제로 귀결된다.
HNSW는 삭제와 업데이트가 상대적으로 비용이 크다.
그래서 벡터 검색에서는 문서를 자주 갱신하기보다는 새로 쌓고 재색인하는 전략이 자주 사용된다.
결과적으로 Elasticsearch HNSW는 대규모 벡터 데이터를 실용적인 속도로 검색하기 위한 현실적인 선택이다.
RAG에서 질문 임베딩과 문서 임베딩을 연결해주는 핵심 엔진이 바로 이 구조 위에서 동작하고 있다.