Hierarchical Navigable Small World (HNSW) 그래프는 로그 복잡도(logarithmic complexity)와 강력한 경험적 성능 덕분에 업계 표준 역할을 하고 있습니다. 그러나 HNSW는 탐욕적 그래프 순회(greedy graph traversal)에 의존하며, 이는 정확성에 대한 이론적 보장을 제공하지 않는 휴리스틱(heuristic)입니다. 본 논문에서는 휴리스틱 탐색의 속도와 정확한 검색(exact retrieval)의 엄격함 사이의 간극을 메우는 새로운 "Certify-then-Rectify" 프레임워크를 제안합니다. HNSW를 폐기하는 대신, 우리의 접근 방식은 먼저 분포가 없는(distribution-free) 통계적 인증기(statistical certifier)를 사용하여 최소한의 오버헤드로 표준 HNSW 탐색의 품질을 동적으로 평가합니다. 만약 인증 결과 검색된 이웃의 품질이 낮다고 판단되면, 프레임워크는 안전하게 엄격한 정확한 복구(exact recovery) 알고리즘으로 격상됩니다. 이러한 정확한 복구를 계산적으로 실행 가능하게 만들기 위해, 우리는 HNSW 그래프를 기하학적 스패너(geometric spanner)로 재해석하고 극값 이론(Extreme Value Theory)을 활용하여 최대 경험적 신축 계수(maximum empirical stretch factor)를 확률적으로 추정합니다. 이를 통해 실제 최근접 이웃(true nearest neighbors)의 최대 거리를 수학적으로 제한할 수 있습니다. 벤치마크 데이터셋에 대한 광범위한 평가 결과, 우리의 계층적 프레임워크는 HNSW의 평균적인 속도를 제공하는 동시에 정확한 검색의 최악의 경우(worst-case)에 대한 정확성을 보장하며 다른 적용 가능한 방식들보다 뛰어난 성능을 보여줍니다.