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.

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

超长词注意力近似的一遍流式算法在亚线性空间中

One Pass Streaming Algorithm for Super Long Token Attention  Approximation in Sublinear Space

A collection of $k$ sets is said to form a $k$-sunflower, or $\Delta$-system,
if the intersection of any two sets from the collection is the same, and we
call a family of sets $\mathcal{F}$ sunflower-free if it contains no
sunflowers. Following the recent breakthrough of Ellenberg and Gijswijt and
Croot, Lev and Pach we apply the polynomial method directly to
Erd\H{o}s-Szemer\'{e}di sunflower problem and prove that any sunflower-free
family $\mathcal{F}$ of subsets of $\{1,2,\dots,n\}$ has size at most \[
|\mathcal{F}|\leq3n\sum_{k\leq
n/3}\binom{n}{k}\leq\left(\frac{3}{2^{2/3}}\right)^{n(1+o(1))}. \] We say that
a set $A\subset(\mathbb Z/D \mathbb Z)^{n}=\{1,2,\dots,D\}^{n}$ for $D>2$ is
sunflower-free if every distinct triple $x,y,z\in A$ there exists a coordinate
$i$ where exactly two of $x_{i},y_{i},z_{i}$ are equal. Using a version of the
polynomial method with characters
$\chi:\mathbb{Z}/D\mathbb{Z}\rightarrow\mathbb{C}$ instead of polynomials, we
show that any sunflower-free set $A\subset(\mathbb Z/D \mathbb Z)^{n}$ has size
\[ |A|\leq c_{D}^{n} \] where $c_{D}=\frac{3}{2^{2/3}}(D-1)^{2/3}$. This can be
seen as making further progress on a possible approach to proving the
Erd\H{o}s-Rado sunflower conjecture, which by the work of Alon, Sphilka and
Umans is equivalent to proving that $c_{D}\leq C$ for some constant $C$
independent of $D$.

本文利用多项式方法等工具对 Erdős-Szemerédi sunflower 问题进行研究，证明任意 sunflower-free 族群的子集都有一个上限，并尝试解决此问题的其他方面。