論文の概要: Attention via Black-Box Vector Search

• arxiv url: http://arxiv.org/abs/2610.10135v1
• Date: Wed, 07 Oct 2026 14:14:58 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-08 21:58:22.955828
• Title: Attention via Black-Box Vector Search
• Title（参考訳）: ブラックボックスベクトルサーチによる注意
• Abstract要約: $(sqrtn/varepsilon)$検索されたキーは十分かつ必要であることを示す。 次に、キーとクエリの増大を許せば、上述の下位境界をバイパスできることを示す。 我々のアルゴリズムは、先行作業で使用されるトップ$とサンプリングアプローチより優れています。
• 参考スコア（独自算出の注目度）: 41.60720798340143
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Sparse attention mechanisms estimate attention over $n$ tokens using a small subset of keys. Many existing approaches use maximum inner product search (MIPS) to retrieve the heaviest keys, which motivates the following question: given black-box access to a MIPS oracle, how many keys must be retrieved to output an $\varepsilon$-accurate attention estimate? We answer this question by unifying prior approaches through the framework of priority sampling. With a single MIPS index, we show that $Θ(\sqrt{n}/\varepsilon)$ retrieved keys are both sufficient and necessary. With $Θ(\log n)$ indices, we give an algorithm that retrieves only $O(\log n+1/\varepsilon^2)$ keys and prove that this is near-optimal. More generally, we design algorithms that establish a smooth tradeoff between the number of MIPS indices and number of retrieved keys. We then show that if we allow augmentation of keys and queries, we can bypass the above lower bounds: there exists a simple priority-sampling estimator using a single MIPS index and $O(1/\varepsilon^2)$ retrieved keys. When integrated into LLM inference, our algorithms outperform top-$k$ and sampling approaches used in prior work and yield attention approximation that scales favorably to long contexts.
• Abstract（参考訳）: わずかな注意機構は、キーの小さなサブセットを使用して$n$トークンよりも注意を見積もる。 既存の多くのアプローチでは、最大内部積探索(MIPS)を使用して、最も重いキーを検索する。 優先サンプリングの枠組みを通じて事前のアプローチを統合することで、この問題に答える。 1つのMIPSインデックスで、$\sqrt{n}/\varepsilon)$取得キーが十分かつ必要であることを示す。 これは、$O(\log n+1/\varepsilon^2)$キーのみを検索し、ほぼ最適であることを示すアルゴリズムである。 より一般的に、MIPSインデックス数と検索キー数とのスムーズなトレードオフを確立するアルゴリズムを設計する。 次に、キーとクエリの増大を許せば、上記の下限をバイパスできることを示す:単一のMIPSインデックスと$O(1/\varepsilon^2)$検索キーを使った単純な優先度サンプリング推定器が存在する。 LLM推論に組み込むと、我々のアルゴリズムは、先行作業で使用されるトップ$k$とサンプリングアプローチを上回り、長いコンテキストに好適にスケールするアテンション近似を導出する。

関連論文リスト

• Solving Sparse SDPs in Sublinear Time: A Classical Algorithm Inspired by the Quantum OR Lemma [70.99943094379263]
  有界ラディウス系におけるスパース半定値プログラムに対する最初の準時間古典的解法を与える。 我々の主な技術的貢献は、ハミルトンのギブス状態を同時に表す古典的な手続きである。
  論文  参考訳（メタデータ） (2026-09-30T17:51:21Z)
• One Key Good, L Keys Better: List Decoding Meets Quantum Privacy Amplification [0.0]
  リストプライバシー増幅(LPA) LPA の形式化と emphQuantum Listleftover Hash Lemma (QLLHL) の証明
  論文  参考訳（メタデータ） (2026-03-18T10:37:05Z)
• Robust Approximation Algorithms for Non-monotone $k$-Submodular Maximization under a Knapsack Constraint [0.0]
  2つの決定論的近似アルゴリズムは、knapsack制約の下での非単調な$k$-部分モジュラー複雑性の問題に対して提案される。 提案アルゴリズムは,非単調な目的に対して,O(nk)$クエリの計算量内で一定の近似比を提供する。
  論文  参考訳（メタデータ） (2023-09-21T12:42:52Z)
• Weak Schur sampling with logarithmic quantum memory [0.0]
  弱いシュアサンプリングのための新しいアルゴリズムを提案する。 我々のアルゴリズムは、既約表現をインデックスするヤングラベルと対称群の多重度ラベルの両方を効率的に決定する。
  論文  参考訳（メタデータ） (2023-09-21T10:02:46Z)
• Do you know what q-means? [42.96240569413475]
  古典的な$varepsilon$-$k$-meansアルゴリズムは、ロイドのアルゴリズムの1つの反復の近似バージョンを時間的複雑さで実行する。 また,時間的複雑さを考慮した$q$-means量子アルゴリズムも提案する。
  論文  参考訳（メタデータ） (2023-08-18T17:52:12Z)
• Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
  本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。 我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2021-06-16T03:34:14Z)
• Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to Minimax Optimization [133.53164856723782]
  そこで我々は,関数値のみが得られるブラックボックス最小最適化のための新しいアクセラレーションゼロ階運動量 (AccZOM) 法を提案する。 一方,ブラックボックス最小値最適化のためのアクセラレーションゼロ階運動量降下法(Acc-MDA)を提案する。 特に、Acc-MDAは、$tildeO(kappa_y2.5epsilon-3)$の低い勾配の複雑さを、バッチサイズ$O(kappa_y4)$で得ることができる。
  論文  参考訳（メタデータ） (2020-08-18T22:19:29Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)

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

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