論文の概要: Support Basis: Fast Attention Beyond Bounded Entries

• arxiv url: http://arxiv.org/abs/2510.01643v1
• Date: Thu, 02 Oct 2025 03:51:28 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-03 16:59:20.977046
• Title: Support Basis: Fast Attention Beyond Bounded Entries
• Title（参考訳）: Support Basis: 境界要素を越えた高速な注意
• Authors: Maryam Aliakbarpour, Vladimir Braverman, Junze Yin, Haochen Zhang,
• Abstract要約: 本稿では,有界エントリを超越した効率的なアテンション近似のための新しいフレームワークであるSupport-Basis decompositionを紹介する。 提案手法では,この特性を利用して大小の成分を分割し,スパース成分の正確な計算と高密度成分の近似を可能にする。
• 参考スコア（独自算出の注目度）: 21.21399891887812
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: The quadratic complexity of softmax attention remains a central bottleneck in scaling large language models (LLMs). [Alman and Song, NeurIPS 2023] proposed a sub-quadratic attention approximation algorithm, but it works only under the restrictive bounded-entry assumption. Since this assumption rarely holds in practice, its applicability to modern LLMs is limited. In this paper, we introduce support-basis decomposition, a new framework for efficient attention approximation beyond bounded entries. We empirically demonstrate that the entries of the query and key matrices exhibit sub-Gaussian behavior. Our approach uses this property to split large and small entries, enabling exact computation on sparse components and polynomial approximation on dense components. We establish rigorous theoretical guarantees, proving a sub-quadratic runtime, and extend the method to a multi-threshold setting that eliminates all distributional assumptions. Furthermore, we provide the first theoretical justification for the empirical success of polynomial attention [Kacham, Mirrokni, and Zhong, ICML 2024], showing that softmax attention can be closely approximated by a combination of multiple polynomial attentions with sketching.
• Abstract（参考訳）: ソフトマックスの注意の二次的複雑さは、大規模言語モデル(LLM)のスケーリングにおいて依然として中心的なボトルネックとなっている。 [Alman and Song, NeurIPS 2023] は準四進的注意近似アルゴリズムを提案したが、制限付き入射仮定の下でのみ機能する。 この仮定は実際にはほとんど成り立たないため、現代のLLMへの適用性は限られている。 本稿では,有界エントリを超越した効率的なアテンション近似のための新しいフレームワークである,サポートベイズ分解を導入する。 クエリとキー行列のエントリがガウス以下の振る舞いを示すことを実証的に示す。 提案手法では,この特性を利用して大小の成分を分割し,スパース成分の正確な計算と高密度成分の多項式近似を可能にする。 我々は厳密な理論的保証を確立し、準四分法ランタイムを証明し、全ての分布仮定を排除したマルチスレッド設定に拡張する。 さらに,多項式注意の実証的成功(Kacham, Mirrokni, Zhong, ICML 2024]に対する最初の理論的正当性を示す。

関連論文リスト

• Maximum a Posteriori Inference for Factor Graphs via Benders' Decomposition [0.38233569758620056]
  一般ベイズ因子モデルにおける最大a-ポストペリオーリ推定法を提案する。 ベイジアン・ガウス混合モデルと潜在ディリクレ割り当てに対するMAP推定アルゴリズムを導出する。
  論文  参考訳（メタデータ） (2024-10-24T19:57:56Z)
• Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
  統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。 予測と高い確率で、新しい過剰なリスク境界を提供する。 我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
  論文  参考訳（メタデータ） (2022-11-03T12:40:24Z)
• Global Optimization for Cardinality-constrained Minimum Sum-of-Squares Clustering via Semidefinite Programming [1.3053649021965603]
  最小二乗クラスタリング(MSSC)は、最近、各クラスタの濃度に関する事前知識を活用するために拡張されている。 本稿では,分枝切断法に基づく大域的最適化手法を提案する。 上界に対して、各ノードで解いたSDP緩和の解を生かした局所探索手順を提案する。
  論文  参考訳（メタデータ） (2022-09-19T10:19:06Z)
• Reinforcement Learning from Partial Observation: Linear Function Approximation with Provable Sample Efficiency [111.83670279016599]
  部分観察決定過程(POMDP)の無限観測および状態空間を用いた強化学習について検討した。 線形構造をもつPOMDPのクラスに対する部分可観測性と関数近似の最初の試みを行う。
  論文  参考訳（メタデータ） (2022-04-20T21:15:38Z)
• Near-Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time [46.31710224483631]
  既存の定数係数近似のスケッチ次元における対数的要素について、Nelson and Nguyen (FOCS, 2013) の主な開問題を回避する方法を示す。 私たちが使用している重要なテクニックは、不確実性原理と抽出子に基づくIndykの明示的なマッピングです。 ランク計算と列の線形独立部分集合の探索という基本的な問題に対して、我々のアルゴリズムはCheung, Kwok, Lau (JACM, 2013)を改良し、それぞれ定数係数と$log(n)$-factorの範囲内で最適である。
  論文  参考訳（メタデータ） (2021-07-16T19:34:10Z)
• Optimal Gradient-based Algorithms for Non-concave Bandit Optimization [76.57464214864756]
  この研究は、未知の報酬関数が非可逆であるようなバンドイット問題の大群を考察する。 我々のアルゴリズムは、非常に一般化されたゼロ階最適化のパラダイムに基づいている。 標準的な楽観的アルゴリズムは次元因子によって準最適であることを示す。
  論文  参考訳（メタデータ） (2021-07-09T16:04:24Z)
• Semi-Sparsity for Smoothing Filters [1.1404527665142667]
  本稿では,新しい疎度誘導フレームワークに基づく半疎度平滑化アルゴリズムを提案する。 我々は、一連の信号/画像処理とコンピュータビジョンアプリケーションに多くの利点を示す。
  論文  参考訳（メタデータ） (2021-07-01T17:31:42Z)
• Approximation Algorithms for Sparse Principal Component Analysis [57.5357874512594]
  主成分分析(PCA)は、機械学習と統計学において広く使われている次元削減手法である。 スパース主成分分析(Sparse principal Component Analysis)と呼ばれる,スパース主成分負荷を求める様々な手法が提案されている。 本研究では,SPCA問題に対するしきい値の精度,時間,近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-23T04:25:36Z)
• Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Condition [52.08417569774822]
  本稿では,深層学習(深層AUC)により注目度が高まっている,円滑な非凹部min-max問題の解法に焦点をあてる。
  論文  参考訳（メタデータ） (2020-06-12T00:32:21Z)

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

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