論文の概要: Approaching I/O-optimality for Approximate Attention

• arxiv url: http://arxiv.org/abs/2605.23751v1
• Date: Fri, 22 May 2026 15:23:26 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-25 17:29:20.410798
• Title: Approaching I/O-optimality for Approximate Attention
• Title（参考訳）: 近似注意のためのI/O最適化へのアプローチ
• Authors: Pál András Papp, Aleksandros Sobczyk, Anastasios Zouzias,
• Abstract要約: 大規模言語モデルにおけるI/Oの複雑さを再考する。 I/Oコストは、ほとんどのパラメーターレギュレーションにおいて、ほぼ直線的に$n$にのみ依存する。
• 参考スコア（独自算出の注目度）: 45.67330863443465
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We revisit the I/O complexity of attention in large language models. Given query-key-value matrices $Q,K,V\in\mathbb{R}^{n\times d}$, and a machine with fast memory size $M$, the goal is to compute the "attention matrix" $A=\text{softmax}(Q K ^{\top}/\sqrt{d}) V$ with the minimal number of data transfers between fast and slow memory. Existing methods in the literature, most notably FlashAttention and its variants, incur an I/O cost that depends quadratically on $n$, while a trivial lower bound only requires $Ω(nd)$ I/O's to read the inputs and write the output. In this work, we present a technique for computing attention where the I/O cost only depends almost-linearly on $n$ in most parameter regimes. This is achieved by developing I/O-efficient algorithms inspired by the recent approximate attention framework of Alman and Song. We also prove corresponding lower bounds in each parameter regime to show that our algorithms are indeed close to I/O-optimal.
• Abstract（参考訳）: 大規模言語モデルにおけるI/Oの複雑さを再考する。 クエリキー値行列$Q,K,V\in\mathbb{R}^{n\times d}$と高速メモリサイズ$M$のマシンが与えられた場合、目標は、高速メモリと低速メモリの間のデータ転送の最小限の値で、"アテンション行列"$A=\text{softmax}(Q K ^{\top}/\sqrt{d}) V$を計算することである。 文献の既存の方法、特にFlashAttentionとその変種は、$n$に二次的に依存するI/Oコストを発生させ、一方、自明な下限は入力を読み書きするために$Ω(nd)$ I/O'sしか必要としない。 本研究は,I/Oコストがほとんどのパラメータ規則において$n$にほぼ直線的にのみ依存する,計算注意のための手法を提案する。 これは、AlmanとSongの最近の近似アテンションフレームワークにインスパイアされた、I/O効率のアルゴリズムを開発することで実現されている。 また,アルゴリズムがI/O最適値に近いことを示すために,各パラメータの下位境界を証明した。

関連論文リスト

• HSR-Enhanced Sparse Attention Acceleration [19.776342074253435]
  大規模言語モデル(LLM)における注意計算を高速化する新しい手法を提案する。 我々は,従来のSoftmaxアテンションとReLUアテンションの両方において,アテンションメカニズム内の固有空間を利用する。 提案手法は,Softmaxの注意を確実に無視できる誤差を導入するのみである。
  論文  参考訳（メタデータ） (2024-10-14T05:18:02Z)
• How Sparse Attention Approximates Exact Attention? Your Attention is Naturally $n^C$-Sparse [9.552839922307587]
  スパース注意(英: Sparse Attention)とは、標準的な注意計算と準四分法的な複雑性を近似する手法である。 KVキャッシュのプルーニング、スパースベースの高速注意、スパーストランスフォーマーといったテクニックのバリエーションは、効率的なLLM(Large Language Models)デプロイメントに広く利用されている。
  論文  参考訳（メタデータ） (2024-04-03T12:37:34Z)
• One Pass Streaming Algorithm for Super Long Token Attention Approximation in Sublinear Space [11.735802740426294]
  注意計算は、$O(n2)$の時間複雑性と$O(n2)$の空間複雑性を同時に行う。 ストリーミング方式で1パスのデータのみを読み取る新しいアルゴリズムを導入する。 特に,本アルゴリズムは,超長期トークンを用いたメモリ効率の優れた性能を示す。
  論文  参考訳（メタデータ） (2023-11-24T18:35:00Z)
• Oblivious Stochastic Composite Optimization [47.48197617884748]
  我々のアルゴリズムは問題のパラメータに関する事前の知識なしで収束することを示す。 3つのアルゴリズムは全て、実現可能な集合の直径、リプシッツ定数、あるいは目的関数の滑らかさについて事前の知識なしに機能する。 我々は,フレームワークを比較的大規模に拡張し,大規模半確定プログラム上での手法の効率性と堅牢性を実証する。
  論文  参考訳（メタデータ） (2023-06-30T08:34:29Z)
• Provably Efficient Reinforcement Learning via Surprise Bound [66.15308700413814]
  本稿では,一般値関数近似を用いた効率の良い強化学習アルゴリズムを提案する。 本アルゴリズムは, 線形設定と疎高次元線形設定の両方に適用した場合に, 合理的な後悔境界を達成できる。
  論文  参考訳（メタデータ） (2023-02-22T20:21:25Z)
• Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time [8.808780937701522]
  我々は、より効率的でエラーの少ない最小化フレームワークに向けて、大きな一歩を踏み出します。 我々のアルゴリズムは時間$widetilde O(|Omega| k)$で実行され、解の検証にはほぼ線形である。
  論文  参考訳（メタデータ） (2023-02-21T23:49:36Z)
• Gaussian Process Bandit Optimization with Few Batches [49.896920704012395]
  有限腕バンディットアルゴリズムにインスパイアされたバッチアルゴリズムを導入する。 O(log T)$ batches in time horizon $T$.sqrtTgamma_T)$ using $O(log T)$ batches in time horizon。 さらに,アルゴリズムの修正版を提案し,バッチ数によって後悔がどう影響するかを特徴付ける。
  論文  参考訳（メタデータ） (2021-10-15T00:54:04Z)
• List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
  高次元におけるリストデコタブル平均推定の基本的な課題について検討する。 我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。 我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
  論文  参考訳（メタデータ） (2020-11-19T17:21:37Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)

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

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