論文の概要: Efficiently Approximating Attention Is Hard

• arxiv url: http://arxiv.org/abs/2609.37261v1
• Date: Tue, 29 Sep 2026 11:11:35 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-30 21:28:47.435487
• Title: Efficiently Approximating Attention Is Hard
• Title（参考訳）: 効率よく注意を近似するのは難しい
• Abstract要約: 我々は,非自明な一様近似を保証するアルゴリズムが存在しないことを示した。 全体として,一様注意近似の計算限界について検討した。
• 参考スコア（独自算出の注目度）: 27.1081027038941
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Softmax attention is ubiquitous in modern machine learning, but its quadratic scaling with sequence length makes it costly. To reduce this cost, attention is often approximated with fast algorithms, which incur error but can still perform well in practice and on some inputs. At the same time, the growing diversity of attention applications makes approximation guarantees that do not depend on particular input structure a compelling target. For such uniform guarantees over all inputs, known runtime lower bounds rule out fast algorithms for near-exact attention, but leave open the practically important regime: is there an efficient algorithm with even a modest uniform approximation guarantee? We answer this question negatively. Under standard complexity-theoretic assumptions, no truly subquadratic algorithm can approximate attention with any nontrivial additive or relative guarantee uniformly over all inputs. This impossibility holds in the mildest parameter regime for which known algorithms do not already achieve strong approximation guarantees in near-linear time, and extends to practically relevant relaxations: even after polynomial preprocessing of the KV cache, no efficient algorithm can obtain a nontrivial uniform approximation guarantee, or identify a small set of keys receiving substantial attention under sparsity. Overall, our results settle the computational limits of uniform attention approximation.
• Abstract（参考訳）: ソフトマックスは現代の機械学習ではユビキタスだが、シーケンシャルなスケーリングによってコストがかかる。 このコストを削減するために、しばしば注意は高速アルゴリズムで近似されるが、これはエラーを発生させるが、実際やいくつかの入力でうまく機能する。 同時に、注目アプリケーションの多様性の増大により、特定の入力構造に依存しない近似保証が魅力的なターゲットとなる。 このような均一な保証のために、既知のランタイムローバウンドは、ほぼ完全に注意を払って高速なアルゴリズムを除外するが、実際重要なレギュレーションを開放する: 控えめな均一な近似を保証する効率的なアルゴリズムはあるだろうか? 私たちはこの質問に否定的に答える。 標準的な複雑性理論の仮定の下では、真に四進法的なアルゴリズムはすべての入力に対して非自明な加法的あるいは相対的な保証で注意を近似することはできない。 この不合理性は、既知のアルゴリズムがほぼ直線時間で強い近似保証を達成しておらず、KVキャッシュの多項式前処理の後でも、非自明な均一な近似保証を得ることができず、また、空間的にかなりの注意を払っているキーの小さなセットを特定できないような、実用的な緩和にまで拡張される。 全体として,一様注意近似の計算限界について検討した。

関連論文リスト

• Learning Augmented Exact Exponential Algorithms [3.0614165499580768]
  探索空間を確実に減らすのに、ランダムな推測に勝る雑音の多い予測器が十分であることを示す。 我々のアルゴリズムは、予測のペア独立性のみを必要とするか、あるいは、予測者の正確性に関する知識を必要としない。
  論文  参考訳（メタデータ） (2026-06-17T08:23:42Z)
• Efficient and Near-Optimal Noise Generation for Streaming Differential Privacy [24.138484222651346]
  個人的連続数え上げに対する2つのアプローチを提案する。 最初のアプローチは、Toeplitz行列のクラスに対する空間効率のよいストリーミング行列乗算アルゴリズムに基づいている。 任意に多くのステップに対して目的関数の効率的な閉形式を導出し、直接数値最適化がこの問題に対して極めて実用的な解をもたらすことを示す。
  論文  参考訳（メタデータ） (2024-04-25T16:11:46Z)
• When can you trust feature selection? -- I: A condition-based analysis of LASSO and generalised hardness of approximation [49.1574468325115]
  近似入力を読み取る際に、LASSOのミニミサの正しいサポートセットを(確率$>1/2$で)決定できないことを示す。 不適切な入力の場合、アルゴリズムは永遠に動作するので、間違った答えを出すことはない。 無限条件数を持つ点を含む開集合上で定義される任意のアルゴリズムに対して、アルゴリズムが永久に実行されるか、間違った解を生成するような入力が存在する。
  論文  参考訳（メタデータ） (2023-12-18T18:29:01Z)
• Learning distributed representations with efficient SoftMax normalization [3.8673630752805437]
  有界ノルムを持つ埋め込みベクトルに対して$rm SoftMax(XYT)$の正規化定数を計算する線形時間近似を提案する。 本稿では,提案手法が競合手法よりも高い精度あるいは同等の精度を達成できるような事前学習した埋め込みデータセットについて述べる。 提案アルゴリズムは解釈可能で,任意の埋め込み問題に容易に適応できる。
  論文  参考訳（メタデータ） (2023-03-30T15:48:26Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [61.98523595657983]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Uniform-PAC Bounds for Reinforcement Learning with Linear Function Approximation [92.3161051419884]
  線形関数近似を用いた強化学習について検討する。 既存のアルゴリズムは、高い確率的後悔と/またはおよそ正当性(PAC)サンプルの複雑さの保証しか持たない。 我々はFLUTEと呼ばれる新しいアルゴリズムを提案し、高い確率で最適ポリシーへの均一PAC収束を享受する。
  論文  参考訳（メタデータ） (2021-06-22T08:48:56Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。 この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。 古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
  論文  参考訳（メタデータ） (2020-07-01T18:43:32Z)

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

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