Abstract
Standard sequence mixing layers used in language models struggle to balance efficiency and performance. Self-attention performs well on long context tasks but has expensive quadratic compute and linear memory costs, while linear attention and SSMs use only linear compute and constant memory but struggle with long context processing. In this paper, we develop a sequence mixing layer that aims to find a better compromise between memory-compute costs and long-context processing, which we call online vector-quantized (OVQ) attention. OVQ-attention requires linear compute costs and constant memory, but, unlike linear attention and SSMs, it uses a sparse memory update that allows it to greatly increase the size of its memory state and, consequently, memory capacity. We develop a theoretical basis for OVQ-attention based on Gaussian mixture regression, and we test it on a variety of synthetic long context tasks and on long context language modeling. OVQ-attention shows significant improvements over linear attention baselines and the original VQ-attention, on which OVQ-attention was inspired. It demonstrates competitive, and sometimes identical, performance to strong self-attention baselines up 64k sequence length, despite using a small fraction of the memory of full self-attention.
Introduction
Modern Large Language Models (LLMs) face a fundamental trade-off between performance and efficiency. Standard Transformers utilize self-attention, which excels at long-context tasks but suffers from quadratic computational complexity and linear memory growth ($O(T^2)$ compute, $O(T)$ memory per layer). As sequences lengthen, the Key-Value (KV) cache becomes a significant bottleneck. Conversely, linear attention and State Space Models (SSMs) offer linear compute and constant memory ($O(T)$ compute, $O(1)$ memory state), but often fail at complex retrieval tasks like "needle-in-a-haystack" because their fixed-size compressed state loses fine-grained information.
Previous attempts to mitigate this using Vector Quantization (VQ) relied on static, pre-trained dictionaries that could not adapt to the specific distribution of keys in a novel document. This paper introduces Online Vector Quantized (OVQ) Attention, which overcomes these limitations by dynamically updating its memory dictionary during the forward pass.
The OVQ-Attention Mechanism
OVQ-Attention treats memory as a dynamic Gaussian Mixture Model (GMM). Instead of a static dictionary, it learns both a key dictionary ($D_k$) and a value dictionary ($D_v$) on-the-fly.
The core innovations include:
- Online Dictionary Learning: As new tokens arrive, the model updates its internal "centroids" using a sparse, k-means-style update. This allows the model to "re-center" its memory on the specific keys it is currently processing.
- Gaussian Mixture Regression (GMR) Framework: The attention mechanism is reformulated as a GMR problem, providing a principled theoretical foundation for handling memory as a set of weighted averages.
- Sparse Memory Updates: By only updating the "nearest neighbor" centroid, OVQ-Attention can scale to a very large number of centroids (high capacity) without increasing the per-token computational cost.
- Dynamic State Growth: The memory state grows quickly at the start of a sequence and plateaus at a maximum size ($N$), optimizing for both early-sequence learning and late-sequence stability.
Experimental Results
The researchers evaluated OVQ-Attention on several benchmarks, including In-Context Recall (ICR), In-Context Learning (ICL), and long-context language modeling (PG19).
Key findings include:
- Near-Lossless Retrieval: On 64k-length ICR tasks, OVQ-Attention matched the performance of full self-attention, whereas linear attention baselines failed beyond 2k tokens.
- Memory Efficiency: The model achieved Transformer-level performance while using only 10-25% of the memory required for a full KV cache at long context lengths.
- Language Modeling Performance: On the PG19 dataset, OVQ-Attention significantly outperformed gated delta nets and original VQ-attention, matching standard attention models.
- Robust Generalization: Models trained on 4k tokens successfully extrapolated to 64k tokens, demonstrating the robustness of the online quantization approach.
Conclusion and Future Work
OVQ-Attention demonstrates that the failure of previous VQ-based attention was not due to quantization itself, but the lack of adaptability. By making the dictionary online and sparse, OVQ-Attention decouples memory capacity from computational cost. Future work will focus on hardware-level optimizations, such as custom CUDA kernels for sparse operations, and scaling the architecture to models with billions of parameters. The online clustering nature of OVQ-Attention also suggests potential applications in continual learning and "infinite context" modeling.
Summary updated