論文の概要: HNSW with Accuracy Guarantees Using Graph Spanners

• arxiv url: http://arxiv.org/abs/2607.02338v2
• Date: Sun, 05 Jul 2026 02:09:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-07 17:33:48.976998
• Title: HNSW with Accuracy Guarantees Using Graph Spanners
• Title（参考訳）: グラフスパナを用いた高精度保証付きHNSW
• Abstract要約: Certify-then-Rectify"フレームワークは、検索速度と正確な検索の厳密さのギャップを埋める。 提案手法では,まず分布のない統計証明を用いて標準HNSW検索の品質を動的に評価する。
• 参考スコア（独自算出の注目度）: 7.703662859297531
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Hierarchical Navigable Small World (HNSW) graphs serve as the industry standard due to their logarithmic complexity and strong empirical performance. However, HNSW relies on greedy graph traversal, a heuristic that provides no theoretical guarantees of correctness. In this paper, we propose a novel "Certify-then-Rectify" framework that bridges the gap between the speed of heuristic search and the rigor of exact retrieval. Rather than discarding HNSW, our approach first employs a distribution-free statistical certifier to dynamically evaluate the quality of a standard HNSW search with minimal overhead. If certification indicates that the retrieved neighbors are of low quality, the framework safely escalates to a rigorous exact recovery algorithm. To make this exact recovery computationally feasible, we reinterpret the HNSW graph as a geometric spanner and utilize Extreme Value Theory to stochastically estimate its maximum empirical stretch factor. This allows us to mathematically bound the maximum distance of true nearest neighbors. Extensive evaluations on benchmark datasets demonstrate that our tiered framework delivers the average-case speed of HNSW while ensuring the worst-case correctness of exact search and outperforming other applicable approaches.
• Abstract（参考訳）: Hierarchical Navigable Small World (HNSW)グラフは、対数的複雑性と強力な経験的パフォーマンスのため、業界標準として機能する。 しかし、HNSWは、理論的な正確性を保証するようなヒューリスティックなグラフトラバーサルに依存している。 本稿では,ヒューリスティック検索の速度と厳密な検索の厳密さのギャップを埋める,新しいCertify-then-Rectifyフレームワークを提案する。 提案手法では,HNSWを破棄する代わりに,まず分布のない統計証明を用いて標準HNSW検索の品質を最小限のオーバーヘッドで動的に評価する。 取得した隣人が品質が低いことを示す場合、フレームワークは厳密な正確な回復アルゴリズムに安全にエスカレートする。 そこで我々は,HNSWグラフを幾何スパンナーとして再解釈し,エクストリーム値理論を用いて,その最大経験的ストレッチ係数を確率論的に推定する。 これにより、真の最も近い隣人の最大距離を数学的に制限することができる。 ベンチマークデータセットの大規模な評価は、我々の階層化フレームワークがHNSWの平均ケース速度を実現し、正確な検索の最悪のケースの正確性を保証し、他の適用可能なアプローチよりも優れていることを示している。

関連論文リスト

• kNN-Graph: An adaptive graph model for $k$-nearest neighbors [17.882218619659756]
  計算複雑性から推論遅延を分離する適応グラフモデルを提案する。 このアーキテクチャは、分類精度を損なうことなく、推論速度を大幅に加速し、リアルタイムのパフォーマンスを達成することを実証する。
  論文  参考訳（メタデータ） (2026-01-23T07:15:53Z)
• From HNSW to Information-Theoretic Binarization: Rethinking the Architecture of Scalable Vector Search [0.7804710977378487]
  本稿では,支配的な"HNSW + float32 + cosine similarity"スタックのアーキテクチャ的制約を分析する。 最大情報二項化(MIB)に基づく代替情報理論アーキテクチャの導入と実証評価を行った。 その結果,完全精度のシステムに匹敵する検索品質を示すとともに,レイテンシを大幅に低減し,高い要求レートで一定のスループットを維持することができた。
  論文  参考訳（メタデータ） (2025-12-16T23:24:37Z)
• A theoretical guarantee for SyncRank [0.0]
  雑音のペア比較からグローバルランキングを復元する SyncRank アルゴリズムの理論的,実証的な解析を行う。 我々の主定理は臨界雑音閾値(sigma = O(sqrt(n / log n))を特徴付け、SyncRankは高い確率で正確なランク回復を達成する。
  論文  参考訳（メタデータ） (2025-09-26T16:45:06Z)
• Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budget [55.938644481736446]
  本稿では,誤差確率の指数的減衰を保証し,最適な腕識別のための新しいアルゴリズムを提案する。 我々は,複雑性のレベルが異なる様々な問題インスタンスに対する包括的経験的評価を通じて,アルゴリズムの有効性を検証する。
  論文  参考訳（メタデータ） (2025-06-03T02:56:26Z)
• Optimal Multi-Fidelity Best-Arm Identification [65.23078799972188]
  バンディットのベストアーム識別において、アルゴリズムは、できるだけ早く特定の精度で、最高平均報酬の腕を見つけることを任務とする。 マルチフィデリティのベストアーム識別について検討し、低コストで低いフィデリティ(正確な平均推定値を持たない)で腕をサンプリングすることを選択できる。 この問題に対処するためのいくつかの方法が提案されているが、その最適性は、特に最適な腕を特定するのに必要な総コストのゆるやかな下限のため、未解決のままである。
  論文  参考訳（メタデータ） (2024-06-05T08:02:40Z)
• Open-Set Recognition: A Good Closed-Set Classifier is All You Need [146.6814176602689]
  分類器が「ゼロ・オブ・ア・ア・ア・ベ」決定を行う能力は、閉集合クラスにおける精度と高い相関関係があることが示される。 この相関を利用して、閉セット精度を向上させることにより、クロスエントロピーOSR'ベースライン'の性能を向上させる。 また、セマンティックノベルティを検出するタスクをより尊重する新しいベンチマークを構築した。
  論文  参考訳（メタデータ） (2021-10-12T17:58:59Z)
• Learning to Hash Robustly, with Guarantees [79.68057056103014]
  本稿では,理論的アルゴリズムと本質的に一致する最悪ケース保証を持つハミング空間のためのNSアルゴリズムを設計する。 理論的にも実用的にも、与えられたデータセットに対してアルゴリズムが最適化できる能力を評価する。 我々のアルゴリズムは、MNISTおよびImageNetデータセットに対する最悪のパフォーマンスのクエリを、1.8倍と2.1倍の精度でリコールする。
  論文  参考訳（メタデータ） (2021-08-11T20:21:30Z)
• Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discrimination [82.52105963476703]
  統計的学習、オンライン学習、その他における繰り返しのテーマは、低騒音の問題に対してより速い収束率が可能であることである。 1次保証は統計的およびオンライン学習において比較的よく理解されている。 三角識別と呼ばれる対数損失と情報理論量が一階保証を得る上で基本的な役割を担っていることを示す。
  論文  参考訳（メタデータ） (2021-07-05T19:20:34Z)
• Risk Minimization from Adaptively Collected Data: Guarantees for Supervised and Policy Learning [57.88785630755165]
  経験的リスク最小化(Empirical Risk Minimization, ERM)は、機械学習のワークホースであるが、適応的に収集されたデータを使用すると、そのモデルに依存しない保証が失敗する可能性がある。 本研究では,仮説クラス上での損失関数の平均値を最小限に抑えるため,適応的に収集したデータを用いた一般的な重み付きERMアルゴリズムについて検討する。 政策学習では、探索がゼロになるたびに既存の文献のオープンギャップを埋める率-最適後悔保証を提供する。
  論文  参考訳（メタデータ） (2021-06-03T09:50:13Z)
• Provably Efficient Reward-Agnostic Navigation with Linear Value Iteration [143.43658264904863]
  我々は、最小二乗値スタイルのアルゴリズムで一般的に使用される、より標準的なベルマン誤差の概念の下での反復が、ほぼ最適値関数の学習において強力なPAC保証を提供することを示す。 そこで本稿では,任意の(線形な)報酬関数に対して,最適に近いポリシーを学習するためにどのように使用できるかを示す。
  論文  参考訳（メタデータ） (2020-08-18T04:34:21Z)
• Consistency of Anchor-based Spectral Clustering [0.0]
  アンカーベースの手法は、スペクトルクラスタリングアルゴリズムの計算複雑性を低減する。 厳密な分析が可能であり,実践に有効であることを示す。 我々はChenとCaiの最先端のLCC法と競合することが判明した。
  論文  参考訳（メタデータ） (2020-06-24T18:34:41Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。