この技術レポートは、階層型ナビゲ可能小世界（HNSW）グラフの速度と理論的な正しさの保証を組み合わせる「Certify-then-Rectify」フレームワークを紹介します。この手法は検索品質を動的に評価し、必要に応じて正確な復元アルゴリズムにエスカレーションすることで、最悪ケースの精度を保証します。

  • 最小限のオーバーヘッドでHNSW検索品質を評価する分布フリーの統計的検定器を使用します。
  • HNSWグラフを幾何学的スパンナーとして再解釈し、真の最近傍の最大距離を制限します。
  • 極値理論を適用して、最大経験ストレッチ係数を確率的に推定します。
  • 正確な検索の最悪ケースの正しさを維持しながら、HNSWの平均ケースの速度を提供します。

このアプローチはヒューリスティック検索と厳密な検索のギャップを埋め、ベンチマークデータセットで他の適用可能な手法を上回ります。