論文の概要: Efficient Long-Decoding Inference with Reasoning-Aware Attention Sparsity
- arxiv url: http://arxiv.org/abs/2502.11147v1
- Date: Sun, 16 Feb 2025 14:28:52 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-18 14:14:42.950932
- Title: Efficient Long-Decoding Inference with Reasoning-Aware Attention Sparsity
- Title(参考訳): Reasoning-Aware Attention Sparsity を用いた高速長符号化推論
- Authors: Junhao Hu, Wenrui Huang, Weidong Wang, Zhenwen Li, Tiancheng Hu, Zhixia Liu, Xusheng Chen, Tao Xie, Yizhou Shan,
- Abstract要約: 推論タスクを解くには、時間とメモリ消費の$O(N)を発生させる(思考の)長いデコードチェーンを必要とすることが多い。
我々はRaaSという新しいアルゴリズムを提案し、マイルストーントークンを識別し、保持するが、それはもはや必要なくなるまでである。
このパターンに基づいて,$O(L)$時間と$O(L)$メモリの複雑さで精度の高いRaaSというアルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 14.409253716114213
- License:
- Abstract: Large Language Models (LLMs) have demonstrated strong capabilities across various domains, with recent advancements in challenging reasoning tasks such as mathematics and programming. However, solving reasoning tasks often requires long decoding chains (of thoughts), which incur $O(N)$ time and memory consumption, where $N$ is the chain length. To mitigate $O(N)$ time and memory consumption, existing sparsity-based algorithms propose retaining only the most critical token's intermediate data (i.e., key-value cache) and discarding the rest. However, these existing algorithms struggle with the ``impossible trinity'' of accuracy, time, and memory. For example, the state-of-the-art algorithm, Quest, achieves high accuracy with $O(L)$ time but $O(N)$ memory ($L$ is the cache budget, $L \ll N$). To address this issue, in this paper, we identify a new attention pattern during the decode stage of reasoning tasks, where milestone tokens (analogous to lemmas in mathematical proofs) emerge, are utilized, and then become unimportant afterward. Based on this pattern, we propose a new algorithm named RaaS that identifies and retains milestone tokens only until they are no longer needed, achieving high accuracy with $O(L)$ time and $O(L)$ memory complexity.
- Abstract(参考訳): 大規模言語モデル(LLM)は、数学やプログラミングといった難解な推論タスクの進歩とともに、様々な領域で強力な能力を示している。
しかし、推論タスクを解くには、(思考の)長いデコードチェーンを必要とすることが多く、その場合、時間とメモリ消費は$O(N)で、そこでは$N$はチェーン長である。
O(N)$の時間とメモリ消費を軽減するために、既存のスパシティベースのアルゴリズムは、最も重要なトークンの中間データ(キーバリューキャッシュ)のみを保持し、残りを破棄することを提案している。
しかし、これらの既存のアルゴリズムは精度、時間、メモリの「不可能トリニティ」に苦慮している。
例えば、最先端のアルゴリズムであるQuestは、$O(L)$ timeで高い精度を達成するが、$O(N)$ memory$L$はキャッシュ予算、$L \ll N$である。
この問題に対処するために,本論文では,マイルストーントークン(数学的証明における補題に類似する)が出現し,その後重要視されるような,推論タスクの復号段階における新たな注意パターンを同定する。
このパターンに基づき、我々はRaaSという新しいアルゴリズムを提案し、もはや必要なくなるまでマイルストーントークンを特定し、保持し、その精度を$O(L)$ timeと$O(L)$ memory complexityで達成する。
関連論文リスト
- Algorithm Design for Continual Learning in IoT Networks [16.35495567193046]
連続学習(CL)は、異なるタスクから連続的に生成されたストリーミングデータに対する新しいオンライン学習技術である。
実用的なIoTネットワークでは、データをサンプリングしてさまざまなタスクを学習する自動運転車は、タスクパターンの順序をルーティングし変更することができる。
論文 参考訳(メタデータ) (2024-12-22T02:36:09Z) - HashAttention: Semantic Sparsity for Faster Inference [91.54218318798603]
HashAttentionは、推奨問題としてピボットトークンの識別をキャストする原則的なアプローチである。
ビットワイズ演算を用いて、このハミング空間における所定のクエリに対する重要なトークンを効率的に識別する。
これはLongBenchとLlama-3.1-8Bモデルの1/32times$で使用されるトークンの数を減らすことができる。
論文 参考訳(メタデータ) (2024-12-19T02:34:15Z) - A Training-free Sub-quadratic Cost Transformer Model Serving Framework With Hierarchically Pruned Attention [43.211427581302715]
大規模言語モデルにおける文脈長を増大させるため,HiP(Hierarchically Pruned Attention)を提案する。
HiPは注意機構の時間的複雑さを$O(T log T)$に減らし、空間的複雑さを$O(T)$に減らし、$T$はシーケンス長である。
HiPは, 劣化を最小限に抑えつつ, プリフィルとデコードの両方のレイテンシとメモリ使用率を著しく低減することを示す。
論文 参考訳(メタデータ) (2024-06-14T08:32:45Z) - 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) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳(メタデータ) (2023-07-24T14:37:22Z) - Improved Algorithms for Allen's Interval Algebra by Dynamic Programming
with Sublinear Partitioning [9.594432031144716]
アレンの区間代数は質的時間的推論において最もよく知られた計算の1つである。
NPハードな定性推論問題を解くための新しい枠組みを提案する。
我々はアレンの区間代数に対して$O*((fraccnlogn)n)$の大きな改善を得る。
論文 参考訳(メタデータ) (2023-05-25T11:45:12Z) - Simplifying and Understanding State Space Models with Diagonal Linear
RNNs [56.33053691749856]
本研究は、離散化ステップを解消し、バニラ対角線形RNNに基づくモデルを提案する。
概念的にはるかに単純であるにもかかわらず、$mathrmDLR$は以前提案したSSMと同じくらいのパフォーマンスを示す。
また、合成シーケンス・ツー・シーケンス・タスクのスイートによって、SSMとアテンションベースモデルの表現性も特徴付ける。
論文 参考訳(メタデータ) (2022-12-01T18:53:06Z) - Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
本研究では,有限水平マルコフ決定過程(MDP)によってモデル化されたエピソディック強化学習(RL)問題をバッチ数に制約を加えて検討する。
我々は,$tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot)をほぼ最適に後悔するアルゴリズムを設計し,$(S,A,H,K)$の対数項を$K$で隠蔽する。
技術的貢献は2つある: 1) 探索のためのほぼ最適設計スキーム
論文 参考訳(メタデータ) (2022-10-15T09:22:22Z) - 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) - RNNs can generate bounded hierarchical languages with optimal memory [113.73133308478612]
RNNは、自然言語構文の足場を反映した境界階層言語を効率的に生成できることを示す。
Dyck-($k$,$m$)は、よくネストされた括弧($k$型)と$m$バウンドされたネスト深さの言語である。
明示的な構成により,$O(m log k)$ hidden units の RNN がメモリの指数的削減に十分であることを示す。
論文 参考訳(メタデータ) (2020-10-15T04:42:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。