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

Attention computation takes both the time complexity of $O(n^2)$ and the space complexity of $O(n^2)$ simultaneously, which makes deploying Large Language Models (LLMs) in streaming applications that involve long contexts requiring substantial computational resources. 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 …

algorithm applications approximation attention complexity computation computational cs.cl cs.lg devday language language models large language large language models llms openai openai devday resources space stat.ml streaming token