ACORN-1 알고리즘으로 KNN prefiltering 시 거리 계산 비용 95% 절감함

Context

KNN 벡터 검색에서 필터를 적용할 때 postfiltering 방식은 전체 데이터에서 최근접 이웃을 찾은 후 필터를 적용하므로, 필터 선택도가 높은 경우 요청한 k개의 결과를 보장하지 못함. 10개를 요청해도 2개만 반환되는 문제가 발생함.

Technical Solution

• Prefiltering: HNSW 그래프 탐색 자체에 필터를 통합하여 탐색 중 필터에 매칭되는 노드만 결과 힙에 추가함
• ACORN-1: 필터에 매칭되지 않는 노드의 거리 계산을 건너뛰며, 대신 해당 노드의 이웃을 통해 필터 매칭 노드를 간접 탐색함
• Adaptive threshold: 필터 매칭 비율이 60% 이하면 ACORN-1을, 이상이면 naive prefiltering을 자동 선택함
• Automatic brute-force fallback: 필터 매칭 문서가 매우 적은 경우(예: 1000만 개 중 50개) HNSW 탐색 대신 선형 스캔으로 전환함

Impact

필터 매칭률 5%에서 95%의 거리 계산 비용을 절감함. Manticore Search 19.0.1 이상에서 기본 활성화됨.

Key Takeaway

필터링된 KNN 검색의 핵심은 필터 선택도에 따라 동적으로 알고리즘을 전환하는 것이다. ACORN-1은 필터에 매칭되지 않는 영역을 비용 없이 통과하여 매칭 노드를 효율적으로 탐색한다.