論文の概要: Calibrated Early Termination with Bounded Optimality Gaps for Constrained Vector Search
- arxiv url: http://arxiv.org/abs/2611.16148v1
- Date: Thu, 12 Nov 2026 01:15:23 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-14 01:36:33.295919
- Title: Calibrated Early Termination with Bounded Optimality Gaps for Constrained Vector Search
- Title(参考訳): 制限ベクトル探索のための境界最適ギャップによる校正早期終了
- Abstract要約: 制約付き$k$-nearest-neighbor(k$-NN)クエリの早期終了について検討する。
我々は、少なくとも1-varepsilon$の確率で答えが正確である最も安い停止規則を求める。
私たちのキーとなる考え方は、ルールが使用する可能性のある観察を宣言し、その中のすべてのルールをモノトーンとして考えることです。
- 参考スコア(独自算出の注目度): 12.457670937221073
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Vector search over learned embeddings is the retrieval layer of recommendation and retrieval-augmented generation, and many applications cap how many answer items one category may contribute. Graph indexes answer a query by best-first traversal, and where it stops determines its cost and whether its answer is exact. We study early termination for such constrained $k$-nearest-neighbor ($k$-NN) queries, with plain $k$-NN as a special case, and seek the cheapest stopping rule whose answer is exact with probability at least $1-\varepsilon$. Learned early-termination methods instead target average recall, which does not guarantee exact answers. Multiple testing can calibrate any parameterized stopping rule to our target, but it cannot tell how much a better rule with the same risk and observations would save. Answering this needs a lower bound on the optimum of a rule family too large to enumerate, valid for the query population. Our key idea is to declare the observations a rule may use and to consider every rule monotone in them. Risk-constrained stopping then becomes a linear program over an order polytope, whose Lagrangian minimizers form a nested chain of staircase rules computed exactly by dynamic programming. Fixed-sequence binomial tests along this chain calibrate our rule, CaST, whose failure probability is at most $\varepsilon$ with confidence $1-δ$. Lagrangian weak duality bounds the optimum of the declared class from below at all risk levels at once, without a union bound over the rules. On two datasets of one million items each, CaST replayed on logged searches costs at most 1.132 times the class optimum for risk levels from 0.03 to 0.10, at 95% joint confidence per setting. Larger savings thus need a rule outside the class. At a common risk target on held-out queries, CaST is faster than every other calibrated rule we time, which take 4.8% to 45.5% more mean time.
- Abstract(参考訳): 学習した埋め込みに対するベクトル探索は、推薦と検索強化生成の検索層であり、多くのアプリケーションは、あるカテゴリが貢献する回答項目の数に上限を置いている。
グラフインデックスは、最優先のトラバースによってクエリに応答し、どこで停止し、そのコストと、その答えが正確かどうかを判断する。
このような制約付き$k$-nearest-neighbor(k$-NN)クエリの早期終了について検討し、通常$k$-NNを特別なケースとして、少なくとも1-\varepsilon$の確率で答えが正確である最も安い停止ルールを求める。
学習した早期終了法は、正確な答えを保証しない平均的リコールをターゲットにしている。
複数のテストは、パラメータ化された停止ルールをターゲットに調整できますが、同じリスクと観察でどれだけ良いルールが救われるかはわかりません。
これを答えるには、列挙するには大きすぎるルールファミリの最適値に対する低いバウンダリが必要であり、クエリ人口に有効である。
私たちのキーとなる考え方は、ルールが使用する可能性のある観察を宣言し、その中のすべてのルールをモノトーンとして考えることです。
リスク制約付き停止は順序ポリトープ上の線形プログラムとなり、ラグランジアン最小化器は動的プログラミングによって正確に計算された階段ルールのネスト連鎖を形成する。
この連鎖に沿った固定シーケンス二項検定は我々の規則であるCaSTを校正するが、その失敗確率は最大で1-δ$の信頼度を持つ\varepsilon$である。
ラグランジアン弱双対性(英語版)は、宣言されたクラスの最適度を、すべてのリスクレベルを一度に下から、ルールに束縛されたユニオンなしで境界付ける。
それぞれ100万項目の2つのデータセットで、ログされた検索で再生されたCaSTは、クラスが0.03から0.10までのリスクレベルに最適化されるのに対して、少なくとも1.132倍のコストがかかる。
より大きな貯蓄はクラス外でのルールを必要とする。
ホールドアウトクエリの一般的なリスクターゲットでは、CaSTは時間ごとの他のキャリブレーションされたルールよりも高速で、平均時間は4.8%から45.5%である。
関連論文リスト
- Safe Multi-Objective Reinforcement Learning: Zero Constraint Violation and Primal-Averaging Convergence [23.52682293579858]
安全多目的強化学習 (MORL) について, 学習全体を通して拘束力の欠如を伴わない検討を行った。
重要な課題は、制約に違反することなく、未知のダイナミクスと制約コストの下で十分に調査することである。
我々は、実行されたポリシーの安全性を保証する最初のサンプル効率のMORLアルゴリズムを提供する。
論文 参考訳(メタデータ) (2026-10-29T05:47:57Z) - Bayesian Fixed-Confidence Best-Arm Identification with Abstention [51.253617466579335]
本研究では,学習者が端末の推薦を控えることができるベイジアン固定自信ベストアーム識別問題について検討する。
目標誤差確率$$および棄権予算$に対して、S&C(Screen-and-Confirm)を提案し、その予測停止時間を分析する。
論文 参考訳(メタデータ) (2026-10-21T19:45:09Z) - Slow Beats Fast at the Kesten-Stigum Threshold: Minimax, Fisher-Information and Belief-Propagation Characterizations of the Information-Computation Gap in Sparse Stochastic Block Models [0.0]
本研究は,$q$コミュニティを用いた疎対称計算ブロックモデルにおけるコミュニティリカバリについて検討する。
我々はKesten-Stigumしきい値$d2=1$と、その下の情報計算ギャップの3つの特徴を得る。
論文 参考訳(メタデータ) (2026-10-06T05:43:49Z) - Parameter-Free Heavy-Tailed Bandits [36.983245230853434]
固定テール指数のモーメント境界$u$に対する適応について研究する。
我々は、全てのアルゴリズムが$u$を知らないこと、あるいはその上限を知らないことは、その分布依存と分布に依存しない後悔の保証の間に急激なトレードオフを従わなければならないことを証明している。
論文 参考訳(メタデータ) (2026-07-31T14:27:28Z) - When Does Learning to Stop Help? A Cost-Aware Study of Early Exits in Reasoning Models [4.8190992438931035]
LearnStopは、プレフィックスオブザーバブルな機能の上に隠された状態のないロジスティックストッパーである。
学習は、答えが振動し、正しさの証拠が広がる場所を給与する。
コスト計算は、KVキャッシュでトークンを32%節約するのと同じ方針で、ブラックボックスの繰り返しプリフィルで121%余分なコストがかかる。
論文 参考訳(メタデータ) (2026-06-29T19:33:42Z) - Decision from Suboptimal Classifiers: Excess Risk Pre- and Post-Calibration [52.70324949884702]
バッチ二分決定における近似的後続確率を用いた余剰リスクの定量化を行う。
我々は、再校正のみが後悔のほとんどに対処する体制と、後悔が集団的損失に支配される体制を識別する。
NLP実験では、これらの量によって、より高度なポストトレーニングの期待値が運用コストに値するかどうかが分かる。
論文 参考訳(メタデータ) (2025-03-23T10:52:36Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳(メタデータ) (2024-02-14T07:52:00Z) - Estimating Optimal Policy Value in General Linear Contextual Bandits [50.008542459050155]
多くのバンドイット問題において、政策によって達成可能な最大報酬は、前もって不明であることが多い。
我々は,最適政策が学習される前に,サブ線形データ構造における最適政策値を推定する問題を考察する。
V*$で問題依存上界を推定する,より実用的で効率的なアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-02-19T01:09:24Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳(メタデータ) (2022-08-11T04:12:50Z) - Screening for a Reweighted Penalized Conditional Gradient Method [20.62129327196916]
条件勾配法(CGM)は大規模なスパース凸最適化に広く用いられている。
一般化一般化器の疎性獲得特性の調整方法を示す。
本実験では,正則化器の凹凸を調整し,スクリーニング規則のアグレッシブ性を検証する。
論文 参考訳(メタデータ) (2021-07-02T14:37:37Z) - Sharp Statistical Guarantees for Adversarially Robust Gaussian
Classification [54.22421582955454]
逆向きに頑健な分類の過剰リスクに対する最適ミニマックス保証の最初の結果を提供する。
結果はAdvSNR(Adversarial Signal-to-Noise Ratio)の項で述べられており、これは標準的な線形分類と逆数設定との類似の考え方を一般化している。
論文 参考訳(メタデータ) (2020-06-29T21:06:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。