مقاله الگوریتم یک جریان عبور برای تقریب توکن فوق العاده طولانی در فضای زیر خطی

چکیده

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.

چکیده به فارسی (ترجمه ماشینی)

استفاده از مدل های بزرگ زبان (LLM) در برنامه های جریان که شامل زمینه های طولانی ، به ویژه برای دیالوگ های گسترده و تجزیه و تحلیل متن ، از اهمیت ویژه ای برخوردار است اما دو چالش مهم را ارائه می دهد.در مرحله اول ، مصرف حافظه در مرحله رمزگشایی به دلیل ذخیره حالت های کلیدی و ارزش (kV) نشانه های قبلی قابل توجه است.ثانیا ، محاسبات توجه با پیچیدگی زمانی $ O (n^2) $ برای تولید هر نشانه وقت گیر است.در Openai Devday اخیر (6 نوامبر 2023) ، OpenAI مدل جدیدی را منتشر کرد که قادر به پشتیبانی از یک سند به طول 128k است ، در مقاله ما ، ما روی مسئله کارآمد حافظه تمرکز می کنیم وقتی که طول زمینه $ n $ بسیار بیشتر از 128K است.($ n gg 2^d $).با در نظر گرفتن یک توجه خود یک لایه با ماتریس پرس و جو ، کلید و ارزش $ q ، k ، v in mathbb {r}^{n times d} $ ، روش چند جمله ای خروجی توجه $ t در را تقریب می دهد.Mathbb {r}^{n times d} $.این کار را با ساخت $ u_1 ، u_2 in mathbb {r}^{n times t} $ انجام می دهد تا توجه $ { sf attn} (q ، k ، v) محاسبه $ در $ n^{1+o(1) اعدام زمان $.با وجود این ، ذخیره ماتریس کلید و ارزش $ k ، v in mathbb {r}^{n times d} $ هنوز هم به فضای $ (n d) $ نیاز دارد و منجر به استفاده قابل توجه حافظه می شود.در پاسخ به این چالش ها ، ما یک الگوریتم جدید را معرفی می کنیم که فقط یک پاس از داده ها را در مد جریان می خواند.این روش از فضای زیرنویس $ o (n) $ برای ذخیره سه ماتریس طرح استفاده می کند و نیاز به ذخیره دقیق $ k ، v $ را کاهش می دهد.نکته قابل توجه ، الگوریتم ما عملکرد استثنایی حافظه با نشانه های فوق العاده طولانی را نشان می دهد.با افزایش طول توکن $ n $ ، خطای ما تضمین می شود در حالی که استفاده از حافظه تقریباً ثابت است.این ویژگی منحصر به فرد ، پتانسیل تکنیک ما را در کارآمد با LLM ها در برنامه های جریان تأکید می کند.