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.

部署大型语言模型在涉及长文本的流式应用中面临着内存消耗和时间复杂度的挑战。本文介绍了一种新的算法，通过节约存储空间并保持较低的错误率，在流式应用中高效地处理大型语言模型。