論文の概要: How Sparse Attention Approximates Exact Attention? Your Attention is Naturally $n^C$-Sparse

• arxiv url: http://arxiv.org/abs/2404.02690v2
• Date: Wed, 12 Feb 2025 14:32:46 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-13 18:10:00.551
• Title: How Sparse Attention Approximates Exact Attention? Your Attention is Naturally $n^C$-Sparse
• Title（参考訳）: あなたの注意は自然に$n^C$-sparseである。
• Authors: Yichuan Deng, Zhao Song, Jing Xiong, Chiwun Yang,
• Abstract要約: スパース注意(英: Sparse Attention)とは、標準的な注意計算と準四分法的な複雑性を近似する手法である。 KVキャッシュのプルーニング、スパースベースの高速注意、スパーストランスフォーマーといったテクニックのバリエーションは、効率的なLLM(Large Language Models)デプロイメントに広く利用されている。
• 参考スコア（独自算出の注目度）: 9.552839922307587
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Sparse Attention is a technique that approximates standard attention computation with sub-quadratic complexity. This is achieved by selectively ignoring smaller entries in the attention matrix during the softmax function computation. Variations of this technique, such as pruning KV cache, sparsity-based fast attention, and Sparse Transformer, have been extensively utilized for efficient Large Language Models (LLMs) deployment. Despite its widespread use, a theoretical understanding of the conditions under which sparse attention performs on par with traditional attention remains elusive. This work aims to $\textbf{bridge this gap by examining the inherent sparsity of standard attention processes}$. Our theoretical framework reveals several brand-new key insights: $\bullet$ Attention is $n^{C}$-sparse, implying that considering only the largest $\Omega(n^{C})$ entries out of all $n$ entries is sufficient for sparse attention to approximate the exact attention matrix with decreasing loss. Here, $n$ represents the input length and $C \in (0, 1)$ is a constant. $\bullet$ Stable $o(\log(n))$-sparse attention, which approximates attention computation with $\log(n)$ or fewer entries, may not be feasible since the error will persist at a minimum of $O(1)$. $\bullet$ An adaptive strategy ($\alpha \cdot n^C, \alpha \in \mathbb{R}$) for the window size of efficient attention methods rather than a fixed one is guaranteed to perform more accurately and efficiently in a task for inference on flexible context lengths.
• Abstract（参考訳）: スパース注意(英: Sparse Attention)とは、標準的な注意計算と準四分法的な複雑性を近似する手法である。 これは、ソフトマックス関数計算中に注意行列の小さいエントリを選択的に無視することで達成される。 KVキャッシュのプルーニング、スパースベースの高速注意、スパーストランスフォーマーといったテクニックのバリエーションは、効率的なLLM(Large Language Models)デプロイメントに広く利用されている。 広く使われているにもかかわらず、希少な注意が従来の注意と同等に作用する条件に関する理論的理解はいまだに解明されていない。 この作業は、標準の注意プロセスの本質的な間隔を調べて、このギャップを$\textbf{bridge することを目的としています。 我々の理論フレームワークは、いくつかの新しい重要な洞察を明らかにしている: $\bullet$ Attention is $n^{C}$-sparse は、すべての$n$エントリのうち、最大$\Omega(n^{C})$エントリだけを考えると、損失を減少させて正確な注意行列を近似するのに十分であることを意味する。 ここで、$n$は入力長を表し、$C \in (0, 1)$は定数である。 $\bullet$ Stable $o(\log(n))$-sparse attentionは、注意計算を$\log(n)$以下で近似する。 $\bullet$ 適応戦略(\alpha \cdot n^C, \alpha \in \mathbb{R}$)は、柔軟なコンテキスト長の推論タスクにおいて、より正確に効率的に実行することを保証している。

関連論文リスト

• Reinforcement Learning under Latent Dynamics: Toward Statistical and Algorithmic Modularity [51.40558987254471]
  強化学習の現実的な応用は、エージェントが複雑な高次元の観察を行う環境を含むことが多い。 本稿では,統計的・アルゴリズム的な観点から,textit General$ latent dynamicsの下での強化学習の課題に対処する。
  論文  参考訳（メタデータ） (2024-10-23T14:22:49Z)
• Beyond Linear Approximations: A Novel Pruning Approach for Attention Matrix [17.086679273053853]
  大きな言語モデル(LLM)は、私たちの日常生活の様々な側面を強化する大きな可能性を示しています。 彼らの成長する能力は、非常に大きなモデルサイズを犠牲にし、エッジデバイスへのデプロイメントを困難にしている。 本稿では,注目行列の近似を直接最適化する LLM 重み付け手法を提案する。
  論文  参考訳（メタデータ） (2024-10-15T04:35:56Z)
• LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions [54.54897832889028]
  任意の$K$に対して、$n$とは独立に「普遍集合」$Uサブセット[n]$が存在し、任意の$Q$と任意の行$i$に対して、大きな注目スコアが$A_i,j$ in row $i$ of $A$は全て$jin U$を持つことを示す。 我々は、視覚変換器のスキームの利点を実証的に示し、トレーニング中に我々の普遍的なセットを使用する新しいモデルのトレーニング方法を示した。
  論文  参考訳（メタデータ） (2024-10-07T19:47:13Z)
• Interpreting and Improving Large Language Models in Arithmetic Calculation [72.19753146621429]
  大規模言語モデル(LLM)は、多くのアプリケーションにまたがる顕著な可能性を示している。 本研究では,LLMが計算を行う特定のメカニズムを明らかにする。 LLMの計算性能を高めるために、これらの必須ヘッド/MLPを選択的に微調整する潜在的な利点について検討する。
  論文  参考訳（メタデータ） (2024-09-03T07:01:46Z)
• Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
  線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。 これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。 また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
  論文  参考訳（メタデータ） (2024-08-16T02:33:07Z)
• Beyond KV Caching: Shared Attention for Efficient LLMs [5.801044612920816]
  本稿では,大規模言語モデル(LLM)の効率を高めるための新しい共有注意機構を提案する。 提案手法は,先進LLMにおいて観測される注意分布の等方性傾向を利用して,予測に必要な計算フロップとKVキャッシュのサイズを減少させる。 以上の結果から,SAは計算資源の保存だけでなく,頑健なモデル性能も維持し,資源制約環境におけるより効率的なLCMの展開を容易にすることが示唆された。
  論文  参考訳（メタデータ） (2024-07-13T07:23:07Z)
• Conv-Basis: A New Paradigm for Efficient Attention Inference and Gradient Computation in Transformers [16.046186753149]
  最近のLarge Language Models(LLM)におけるトランスフォーマーの成功の鍵は自己認識メカニズムである 我々は、注目行列の畳み込み様構造を利用して、畳み込み行列を用いた注目の効率的な近似法を開発する。 トランスフォーマーモデルにおけるアテンション計算を加速するための新しいパラダイムが、より長いコンテキストへのアプリケーションを支援することを願っています。
  論文  参考訳（メタデータ） (2024-05-08T17:11:38Z)
• Extending Token Computation for LLM Reasoning [5.801044612920816]
  大規模言語モデル(LLM)は、自然言語処理の進歩において重要な要素である。 LLMは、非効率な注意分布のため、複雑な推論タスクに苦しむことが多い。 本稿では,アテンション機構の最適化を利用して,計算トークンをChain-of-Thoughtプロセスで拡張する新しい手法を提案する。
  論文  参考訳（メタデータ） (2024-03-22T03:23:58Z)
• 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)
• How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computation [12.853829771559916]
  本稿では,三重相関を捉える注意の一般化について検討する。 この一般化は、変圧器では不可能であった三重結合の検出に関する問題を解くことができる。 構築, アルゴリズム, 下位境界が自然に高次テンソルや相関に一般化されることが示される。
  論文  参考訳（メタデータ） (2023-10-06T07:42:39Z)
• Efficient Model-Free Exploration in Low-Rank MDPs [76.87340323826945]
  低ランクマルコフ決定プロセスは、関数近似を持つRLに対して単純だが表現力のあるフレームワークを提供する。 既存のアルゴリズムは、(1)計算的に抽出可能であるか、または(2)制限的な統計的仮定に依存している。 提案手法は,低ランクMPPの探索のための最初の実証可能なサンプル効率アルゴリズムである。
  論文  参考訳（メタデータ） (2023-07-08T15:41:48Z)
• Computing large deviation prefactors of stochastic dynamical systems based on machine learning [4.474127100870242]
  弱い雑音の極限における力学系の希少事象の指数推定を特徴付ける大きな偏差理論を提案する。 我々は、ベクトル場の分解に基づいて、準ポテンシャル、最も確率の高い経路とプレファクタを計算するためのニューラルネットワークフレームワークを設計する。 数値実験は、弱いランダム変動によって引き起こされる稀な事象の内部メカニズムを探索する上で、その強力な機能を示す。
  論文  参考訳（メタデータ） (2023-06-20T09:59:45Z)
• Representation Learning with Multi-Step Inverse Kinematics: An Efficient and Optimal Approach to Rich-Observation RL [106.82295532402335]
  既存の強化学習アルゴリズムは、計算的難易度、強い統計的仮定、最適なサンプルの複雑さに悩まされている。 所望の精度レベルに対して、レート最適サンプル複雑性を実現するための、最初の計算効率の良いアルゴリズムを提供する。 我々のアルゴリズムMusIKは、多段階の逆運動学に基づく表現学習と体系的な探索を組み合わせる。
  論文  参考訳（メタデータ） (2023-04-12T14:51:47Z)
• Randomized and Deterministic Attention Sparsification Algorithms for Over-parameterized Feature Dimension [18.57735939471469]
  我々は注意問題のスパシフィケーションを考慮する。 超大規模特徴量の場合、文の長さをほぼ線形に縮めることができる。
  論文  参考訳（メタデータ） (2023-04-10T05:52:38Z)
• Fast Attention Requires Bounded Entries [19.17278873525312]
  内部製品注意計算はTransformer, GPT-1, BERT, GPT-2, GPT-3, ChatGPTなどの大規模言語モデルを訓練するための基本的なタスクである。 行列を暗黙的に$A$とすることで、より高速なアルゴリズムが可能かどうかを検討する。 このことは、入力行列がより小さいエントリを持つ場合、注意計算の方がはるかに効率的である、実際に観察された現象の理論的な説明を与える。
  論文  参考訳（メタデータ） (2023-02-26T02:42:39Z)
• Provably Efficient Reinforcement Learning via Surprise Bound [66.15308700413814]
  本稿では,一般値関数近似を用いた効率の良い強化学習アルゴリズムを提案する。 本アルゴリズムは, 線形設定と疎高次元線形設定の両方に適用した場合に, 合理的な後悔境界を達成できる。
  論文  参考訳（メタデータ） (2023-02-22T20:21:25Z)
• Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
  我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。 実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
  論文  参考訳（メタデータ） (2021-05-17T16:40:48Z)
• Taming Discrete Integration via the Boon of Dimensionality [36.55732373661026]
  本稿では,離散積分をモデルカウントに効率よく還元する手法を提案する。 ニューラルネットワーク検証ドメインから生じるベンチマークに対して、詳細な実験分析を行う。 DeWeightは、このクラスのベンチマークに対して証明可能な保証で見積もりを計算する最初のテクニックである。
  論文  参考訳（メタデータ） (2020-10-21T02:32:51Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Untangling tradeoffs between recurrence and self-attention in neural networks [81.30894993852813]
  本稿では,再帰的ネットワークにおける自己注意が勾配伝播に与える影響を公式に分析する。 長期的な依存関係を捉えようとするとき、勾配をなくすことの問題を緩和することを証明する。 本稿では,スパース自己アテンションを反復的にスケーラブルに利用するための関連性スクリーニング機構を提案する。
  論文  参考訳（メタデータ） (2020-06-16T19:24:25Z)
• Multiplicative noise and heavy tails in stochastic optimization [62.993432503309485]
  経験的最適化は現代の機械学習の中心であるが、その成功における役割はまだ不明である。 分散による離散乗法雑音のパラメータによく現れることを示す。 最新のステップサイズやデータを含む重要な要素について、詳細な分析を行い、いずれも最先端のニューラルネットワークモデルで同様の結果を示す。
  論文  参考訳（メタデータ） (2020-06-11T09:58:01Z)
• Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
  我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。 最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
  論文  参考訳（メタデータ） (2020-03-04T07:36:38Z)

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

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