論文の概要: Fine-grained Attention I/O Complexity: Comprehensive Analysis for Backward Passes
- arxiv url: http://arxiv.org/abs/2410.09397v1
- Date: Sat, 12 Oct 2024 07:01:30 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-10-15 15:14:07.970775
- Title: Fine-grained Attention I/O Complexity: Comprehensive Analysis for Backward Passes
- Title(参考訳): 微細な注意I/O複雑度:後方進路の包括的解析
- Authors: Xiaoyu Li, Yingyu Liang, Zhenmei Shi, Zhao Song, Yufa Zhou,
- Abstract要約: LLM(Large Language Models)は、長いコンテキスト情報を処理する際、顕著な能力を示す。
列長に関する注意の二次的な複雑さは、重大な計算上の問題を引き起こす。
本稿では,後進パスに着目した注意機構のI/O複雑性の包括的解析を行う。
- 参考スコア(独自算出の注目度): 24.075230599299772
- License:
- Abstract: Large Language Models (LLMs) have demonstrated remarkable capabilities in processing long-context information. However, the quadratic complexity of attention computation with respect to sequence length poses significant computational challenges, and I/O aware algorithms have been proposed. This paper presents a comprehensive analysis of the I/O complexity for attention mechanisms, focusing on backward passes by categorizing into small and large cache scenarios. Using the red-blue pebble game framework, we establish tight bounds on I/O complexity across all cache sizes. We confirm that the de facto standard I/O aware algorithm FlashAttention is optimal for both forward and backward passes for the large cache size scenario. For small cache sizes, we provide an algorithm that improves over existing methods and achieves the tight bounds. Additionally, we extend our analysis to sparse attention, a mainstream speeding-up approach, deriving fine-grained lower bounds for both forward and backward passes and both small and large caches. Our findings complete the theoretical foundation for I/O complexity in attention mechanisms, offering insights for designing efficient algorithms of LLM training and inference.
- Abstract(参考訳): LLM(Large Language Models)は、長いコンテキスト情報を処理する際、顕著な能力を示す。
しかし、列長に対する注意計算の二次的な複雑さは、重要な計算課題を引き起こし、I/O認識アルゴリズムが提案されている。
本稿では,小規模・大規模キャッシュシナリオに分類することで,下位パスに着目した注意機構のI/O複雑性を包括的に解析する。
赤青のゲームフレームワークを使用して、すべてのキャッシュサイズにまたがるI/O複雑性を厳格に制限する。
我々は,デファクト標準I/O認識アルゴリズムであるFlashAttentionが,キャッシュサイズの大きなシナリオに対して,前方および後方の両方に最適であることを確認した。
キャッシュサイズを小さくするために、既存のメソッドを改良し、タイトなバウンドを実現するアルゴリズムを提供する。
さらに、我々は分析をスパース・アテンション、主流のスピードアップ・アプローチに拡張し、前と後の両方の細粒度の低い境界と、小と大の両方のキャッシュを導出する。
注意機構におけるI/O複雑性の理論的基礎を完成し,LLM学習と推論の効率的なアルゴリズムを設計するための洞察を提供する。
関連論文リスト
- Sketch and shift: a robust decoder for compressive clustering [17.627195350266796]
圧縮学習は、大規模学習のメモリフットプリントを大幅に削減する、新たなアプローチである。
CL-OMPRよりも大幅に改善された代替デコーダを提案する。
提案アルゴリズムは,従来より10倍小さいMNISTデータセットのスケッチからクラスタリング情報を抽出することができる。
論文 参考訳(メタデータ) (2023-12-15T16:53:55Z) - A Theory of I/O-Efficient Sparse Neural Network Inference [17.862408781750126]
機械学習モデルは、その精度を速い速度で向上させるため、エネルギーと計算資源の需要は増大する。
低レベルでは、これらのリソースの大部分は異なるメモリユニット間でのデータ移動によって消費されます。
我々は、スパースフィードフォワードニューラルネットワーク(FFNN)推論に必要なI/Oを厳密に理論的に分析する。
論文 参考訳(メタデータ) (2023-01-03T11:23:46Z) - Finite-Time Analysis of Fully Decentralized Single-Timescale
Actor-Critic [4.94128206910124]
本稿では,アクタ,批評家,グローバル報酬推定器を交互に更新する,完全に分散化されたアクタ・クリティカル(AC)アルゴリズムを提案する。
このアルゴリズムは,Markovian サンプリングにおいて $tildemathcalO(epsilon-2)$ のサンプル複雑性を持つことを示す。
また、我々のアルゴリズムのローカルアクションプライバシ保護バージョンとその分析も提供する。
論文 参考訳(メタデータ) (2022-06-12T13:14:14Z) - Accelerating Deep Learning Classification with Error-controlled
Approximate-key Caching [72.50506500576746]
我々は、近似キーキャッシングと名付けた新しいキャッシングパラダイムを提案する。
近似キャッシュはDL推論の負荷を軽減し、システムのスループットを向上するが、近似誤差を導入する。
我々は古典的なLRUと理想的なキャッシュのキャッシュシステム性能を解析的にモデル化し、期待される性能のトレース駆動評価を行い、提案手法の利点を最先端の類似キャッシュと比較した。
論文 参考訳(メタデータ) (2021-12-13T13:49:11Z) - Revisiting the Complexity Analysis of Conflict-Based Search: New
Computational Techniques and Improved Bounds [5.158632635415881]
最適解に対する最先端のアプローチは Conflict-Based Search (CBS) である
CBSの複雑性分析を再検討し、最悪の場合のアルゴリズムの実行時間に厳密な制限を与える。
論文 参考訳(メタデータ) (2021-04-18T07:46:28Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-01-07T08:00:02Z) - Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。
我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
論文 参考訳(メタデータ) (2020-08-29T14:58:26Z) - Faster Secure Data Mining via Distributed Homomorphic Encryption [108.77460689459247]
ホモモルフィック暗号化(HE)は、最近、暗号化されたフィールド上で計算を行う能力により、ますます注目を集めている。
本稿では,スケーリング問題の解決に向けて,新しい分散HEベースのデータマイニングフレームワークを提案する。
各種データマイニングアルゴリズムとベンチマークデータセットを用いて,新しいフレームワークの有効性と有効性を検証する。
論文 参考訳(メタデータ) (2020-06-17T18:14:30Z) - Optimal Continual Learning has Perfect Memory and is NP-hard [19.629732320437856]
連続学習(CL)アルゴリズムは、連続的に観察された複数のタスクにまたがる予測や表現を漸進的に学習する。
本論文は、その理由を説明する理論的アプローチを開発する。
悲惨な忘れ物を避けるために,CLアルゴリズムが持つ計算特性を導出する。
論文 参考訳(メタデータ) (2020-06-09T11:20:38Z) - Learning to Accelerate Heuristic Searching for Large-Scale Maximum
Weighted b-Matching Problems in Online Advertising [51.97494906131859]
バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。
既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。
我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
論文 参考訳(メタデータ) (2020-05-09T02:48:23Z) - Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。
ラグランジアン分解に基づく新しい手法を提案する。
ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
論文 参考訳(メタデータ) (2020-02-24T17:55:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。