論文の概要: One Pass Streaming Algorithm for Super Long Token Attention
Approximation in Sublinear Space
- arxiv url: http://arxiv.org/abs/2311.14652v1
- Date: Fri, 24 Nov 2023 18:35:00 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-27 14:10:16.871715
- Title: One Pass Streaming Algorithm for Super Long Token Attention
Approximation in Sublinear Space
- Title(参考訳): サブリニア空間における超長期トークン注意近似のためのワンパスストリーミングアルゴリズム
- Authors: Raghav Addanki, Chenyang Li, Zhao Song, Chiwun Yang
- Abstract要約: 長いコンテキストを含むストリーミングアプリケーションにおける大規模言語モデル(LLM)は、特に拡張された対話とテキスト分析において、2つの重要な課題を提示している。
第一に、以前のトークンのキーおよびバリュー状態(KV)のキャッシュのため、デコードフェーズにおいてメモリ消費は相当である。
第二に、トークンの生成にO(n2)$の時間で注意の複雑さが時間を要する。
ストリーミング方式でデータの1パスのみを読み込む新しいアルゴリズムを導入する。
- 参考スコア(独自算出の注目度): 11.735802740426294
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Deploying Large Language Models (LLMs) in streaming applications that involve
long contexts, particularly for extended dialogues and text analysis, is of
paramount importance but presents two significant challenges. Firstly, the
memory consumption is substantial during the decoding phase due to the caching
of Key and Value states (KV) of previous tokens. Secondly, attention
computation is time-consuming with a time complexity of $O(n^2)$ for the
generation of each token. In recent OpenAI DevDay (Nov 6, 2023), OpenAI
released a new model that is able to support a 128K-long document, in our
paper, we focus on the memory-efficient issue when context length $n$ is much
greater than 128K ($n \gg 2^d$). Considering a single-layer self-attention with
Query, Key, and Value matrices $Q, K, V \in \mathbb{R}^{n \times d}$, the
polynomial method approximates the attention output $T \in \mathbb{R}^{n \times
d}$. It accomplishes this by constructing $U_1, U_2 \in \mathbb{R}^{n \times
t}$ to expedite attention ${\sf Attn}(Q, K, V)$ computation within $n^{1+o(1)}$
time executions. Despite this, storing the Key and Value matrices $K, V \in
\mathbb{R}^{n \times d}$ still necessitates $O( n d)$ space, leading to
significant memory usage. In response to these challenges, we introduce a new
algorithm that only reads one pass of the data in streaming fashion. This
method employs sublinear space $o(n)$ to store three sketch matrices,
alleviating the need for exact $K, V$ storage. Notably, our algorithm exhibits
exceptional memory-efficient performance with super-long tokens. As the token
length $n$ increases, our error guarantee diminishes while the memory usage
remains nearly constant. This unique attribute underscores the potential of our
technique in efficiently handling LLMs in streaming applications.
- Abstract(参考訳): 長いコンテキストを含むストリーミングアプリケーション、特に拡張対話とテキスト分析にLLM(Large Language Models)をデプロイすることは、非常に重要であるが、2つの重要な課題がある。
第一に、以前のトークンのキーおよびバリュー状態(KV)のキャッシュのため、デコードフェーズにおいてメモリ消費は相当である。
第二に、注意計算は各トークンの生成にO(n^2)$の時間複雑さで時間を要する。
先日のOpenAI DevDay (2023年2月6日)で、OpenAIは、128Kのドキュメントをサポート可能な新しいモデルをリリースした。
Query, Key, and Value 行列 $Q, K, V \in \mathbb{R}^{n \times d}$ の単層自己アテンションを考えると、多項式法は注意出力 $T \in \mathbb{R}^{n \times d}$ を近似する。
u_1, u_2 \in \mathbb{r}^{n \times t}$ to expedite attention ${\sf attn}(q, k, v)$ computation within $n^{1+o(1)}$ time executions. でこれを実現している。
これにもかかわらず、キーとバリューの行列を$Kに格納するV \in \mathbb{R}^{n \times d}$はまだ$O(n d)$スペースを必要とするため、メモリ使用量は大幅に増加する。
これらの課題に対応して,ストリーミング方式でデータの1パスのみを読み取る新しいアルゴリズムを導入する。
この方法は3つのスケッチ行列を格納するためにサブ線形空間$o(n)$を使用し、正確な$K、V$ストレージの必要性を緩和する。
特に,超長トークンを用いたメモリ効率の優れた性能を示す。
トークン長の$n$が増加すると、メモリ使用量がほぼ一定である間、エラー保証は減少します。
このユニークな属性は、ストリーミングアプリケーションにおけるLLMの効率的な処理における我々の技術の可能性を示している。
関連論文リスト
- Conv-Basis: A New Paradigm for Efficient Attention Inference and Gradient Computation in Transformers [27.54512534985192]
我々は、注目行列の畳み込み様構造を利用して、畳み込み行列を用いた注目の効率的な近似法を開発する。
我々のアルゴリズムは、ほぼ線形時間、すなわち$n1+o(1)$を達成する。
この作業は、アプリケーションがより長いコンテキストに到達できるように、トランスフォーマーにおける注意計算を加速するための新しいパラダイムを提供する。
論文 参考訳(メタデータ) (2024-05-08T17:11:38Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳(メタデータ) (2023-06-02T18:55:27Z) - 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) - 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) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳(メタデータ) (2022-04-13T22:18:47Z) - 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) - Approximate Multiplication of Sparse Matrices with Limited Space [27.875251633343666]
我々はスパース共起方向を開発し、期待値の$widetildeOleft((nnz(X)+nnz(Y))ell+nell2right)$に時間複雑性を減少させる。
理論的解析により,我々のアルゴリズムの近似誤差はCODとほぼ同値であることが判明した。
論文 参考訳(メタデータ) (2020-09-08T05:39:19Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳(メタデータ) (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。