5천 문서에서는 HNSW보다 완전탐색이 빨랐다

이 요약은 AI가 원문을 분석해 생성했습니다. 정확한 내용은 원문 기준으로 확인하세요.

TL;DR

글쓴이는 retrieval library 없이 BM25용 inverted index와 HNSW를 직접 구현해 NFCorpus 3,633개 문서와 SciFact 5,183개 문서에서 FAISS 및 완전탐색과 비교했습니다. 모든 검색 방식의 품질은 거의 같았지만, 이 규모에서는 dense matmul 기반 완전탐색이 직접 구현한 HNSW보다 10.9배와 18.3배 빨랐고 HNSW의 구축 비용도 훨씬 컸습니다. 실제 질의 시간은 검색보다 MiniLM-L6-v2 임베딩 생성이 87배 길었으며, 가장 큰 품질 향상은 BM25와 dense 결과를 RRF로 융합했을 때 발생했습니다. 다만 실험이 두 데이터셋과 한 장비에 국한돼 HNSW와 완전탐색의 crossover 지점은 아직 확정되지 않았습니다.

실용적 조언

문서 수가 수천 개 수준인 검색 시스템에서는 ANN index를 기본값으로 두기 전에 dense 벡터의 차원과 BLAS 기반 완전탐색 지연시간을 먼저 측정하는 편이 타당합니다. 이 실험에서는 3,633개 문서와 384차원 벡터의 exact 검색이 0.295ms였고 HNSW는 3.227ms였습니다. 실제 crossover를 찾으려면 고정된 데이터와 동일한 장비에서 corpus size를 연속적으로 늘리는 size sweep이 필요합니다.
검색 품질을 높이려면 BM25와 dense ranker를 각각 평가한 뒤 RRF 융합을 비교할 수 있습니다. 이 실험에서 RRF는 NFCorpus를 0.3162에서 0.3423으로, SciFact를 0.6644에서 0.6969로 높였고 융합 비용은 7.36μs였습니다. BM25의 NFCorpus 성능이 published figure보다 0.019 낮았으므로 stemming과 stopword 처리를 바꾼 변형도 별도로 검증해야 합니다.

섹션별 상세

글쓴이는 수천 개 문서와 384차원 벡터를 검색할 때 HNSW가 완전탐색보다 빠르지 않을 수 있다고 측정했습니다. NFCorpus 3,633개 문서에서 직접 구현한 `mini-hnsw`의 중앙 지연시간은 3.227ms로 `mini-brute`의 0.295ms보다 10.9배 높았고, SciFact 5,183개에서도 7.517ms 대 0.410ms로 18.3배 높았습니다. 이 규모에서는 완전탐색이 하나의 dense matmul로 처리되는 반면 HNSW는 포인터 추적과 우선순위 큐를 거치므로, ANN의 생략 이득이 탐색 오버헤드를 아직 상쇄하지 못했습니다.

FAISS 결과는 구현 언어만으로 현상을 설명하기 어려운 부분을 뒷받침했습니다. SciFact에서는 FAISS의 flat index가 자체 HNSW보다 1.36배 빨랐고, NFCorpus에서는 HNSW와 flat index의 평균 차이 0.019ms보다 실행 간 변동 0.023ms가 컸으며 p95도 0.207ms와 0.209ms로 가까웠습니다. 네 시스템의 nDCG@10은 NFCorpus에서 0.3159~0.3162, SciFact에서 모두 0.6451로 같아 속도 차이가 검색 품질 손실에서 비롯된 결과는 아니었습니다.

검색 단계보다 임베딩 생성 단계가 훨씬 큰 비용을 차지했습니다. NFCorpus에서 MiniLM-L6-v2 임베딩에는 25.8ms가 걸렸지만 그 임베딩을 이용한 exact 검색은 0.295ms에 그쳐 encoder가 retrieval보다 87배 느렸습니다. 따라서 이 실험의 문서 규모에서는 index 구조의 세부 최적화보다 임베딩 계산 비용이 전체 질의 지연시간을 더 크게 좌우했습니다.

가장 뚜렷한 품질 향상은 HNSW가 아니라 BM25와 dense 검색을 RRF로 결합한 데서 나왔습니다. NFCorpus nDCG@10은 단일 검색기의 최고 0.3162에서 0.3423으로, SciFact는 0.6644에서 0.6969로 상승했고 FAISS flat과 비교한 효과 크기의 p값은 각각 0.0045와 0.0009였습니다. 융합 비용은 7.36μs에 불과해, 비싼 HNSW 구축이나 검색 최적화보다 서로 다른 검색기가 내놓은 순위의 불일치를 활용하는 편이 이 조건에서 더 큰 이득을 냈습니다.

용어 해설

계층적 탐색 소세계 그래프(HNSW): — HNSW는 고차원 벡터를 여러 계층의 그래프로 연결하고, 상위 계층에서 대략적인 위치를 찾은 뒤 하위 계층으로 내려가며 최근접 이웃을 탐색하는 구조입니다. 전체 벡터를 순회하지 않는 대신 그래프 이동과 거리 계산 비용을 사용합니다.
BM25 검색 모델(BM25): — BM25는 문서 내 단어 빈도와 전체 문서에서의 희소성을 이용해 검색어와 문서의 관련도를 계산하는 전통적 검색 방식입니다. 이 글에서는 직접 만든 inverted index 위에서 동작하며 dense 검색 결과와 결합됩니다.
순위 상호성 융합(RRF): — RRF는 서로 다른 검색기가 반환한 문서 순위를 순위 역수 기반 점수로 합산하는 융합 방식입니다. 이 글에서는 BM25와 dense 검색의 순위를 결합해 단일 검색기보다 높은 nDCG@10을 얻는 데 사용됩니다.
역색인(Inverted Index): — Inverted index는 단어를 해당 단어가 포함된 문서 목록에 연결해 검색어가 등장한 문서를 빠르게 찾는 자료구조입니다. 글쓴이는 BM25 라이브러리 없이 이를 직접 구현하고 검색 성능을 측정했습니다.
근사 최근접 이웃 검색(ANN): — ANN은 모든 벡터와 정확히 비교하는 대신 일부 후보만 탐색해 최근접 이웃을 빠르게 찾는 방법입니다. HNSW의 efSearch 값을 조절하면 exact 검색에 대한 recall과 탐색 비용 사이의 균형을 바꿀 수 있습니다.
상위 10개 정규화 할인 누적 이득(nDCG@10): — nDCG@10은 검색 결과 상위 10개 문서의 관련도와 순서를 함께 평가하는 지표입니다. 이 글에서는 NFCorpus와 SciFact에서 exact 검색, HNSW, BM25와 RRF 융합의 검색 품질을 비교하는 기준으로 사용됩니다.

언급된 도구

FAISS중립

flat index와 HNSW index를 포함한 dense retrieval 기준 구현과 비교 대상

bm25s중립

BM25 검색 구현을 비교하는 기준 도구

rank_bm25중립

BM25 검색 구현을 비교하는 기준 도구

MiniLM-L6-v2중립

NFCorpus와 SciFact의 dense query embedding 생성

언급된 리소스

GitHubsankalp021/mini-search

문서HNSW vs Brute Force