이 기술 보고서는 계층적 탐색 가능 소세계(HNSW) 그래프의 속도와 이론적 정확성 보장을 결합하는 "Certify-then-Rectify" 프레임워크를 소개합니다. 이 방법은 검색 품질을 동적으로 평가하고 필요시 정확한 복원 알고리즘으로 격상하여 최악의 경우 정확성을 보장합니다.
- 최소한의 오버헤드로 HNSW 검색 품질을 평가하는 분포フリー 통계적 검증기를 사용합니다.
- HNSW 그래프를 기하학적 스패너로 재해석하여 실제 최근접 이웃의 최대 거리를 제한합니다.
- 극값 이론을 적용하여 최대 경험 신축 계수를 확률적으로 추정합니다.
- 정확한 검색의 최악의 경우 정확성을 유지하면서 HNSW의 평균 케이스 속도를 제공합니다.
이 접근 방식은 휴리스틱 검색과 엄격한 검색 사이의 격차를 해소하며, 벤치마크 데이터셋에서 다른 적용 가능한 방법보다 우수합니다.