Fugu-MT 論文翻訳(概要): One Pass Streaming Algorithm for Super Long Token Attention Approximation in Sublinear Space

論文の概要: 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の効率的な処理における我々の技術の可能性を示している。

論文の概要: One Pass Streaming Algorithm for Super Long Token Attention Approximation in Sublinear Space

関連論文リスト