# SubGen: Token Generation in Sublinear Time and Memory

arXiv: https://arxiv.org/abs/2402.06082 · HTML: https://mlsanity.com/paper/2402.06082/

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- Placed in KV cache optimization, one of 12 directions in Efficient LLM inference and serving.
- Builds on 19 of its 28 references that are in the map.
- First posted on arXiv 8 Feb 2024.

## Placed in

- Efficient LLM inference and serving / [KV cache optimization](https://mlsanity.com/inference/kv-cache-optimization/)

## Builds on (most cited first, 19 of 19)

- [Learning Transferable Visual Models From Natural Language Supervision](https://mlsanity.com/paper/2103.00020/) (2021)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Judging LLM-as-a-Judge with MT-Bench and Chatbot Arena](https://mlsanity.com/paper/2306.05685/) (2023)
- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [RoFormer: Enhanced Transformer with Rotary Position Embedding](https://mlsanity.com/paper/2104.09864/) (2021)
- [Efficient Streaming Language Models with Attention Sinks](https://mlsanity.com/paper/2309.17453/) (2023)
- [Code Llama: Open Foundation Models for Code](https://mlsanity.com/paper/2308.12950/) (2023)
- [Imagen Video: High Definition Video Generation with Diffusion Models](https://mlsanity.com/paper/2210.02303/) (2022)
- [H2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models](https://mlsanity.com/paper/2306.14048/) (2023)
- [FlexGen: High-Throughput Generative Inference of Large Language Models with a Single GPU](https://mlsanity.com/paper/2303.06865/) (2023)
- [Model Tells You What to Discard: Adaptive KV Cache Compression for LLMs](https://mlsanity.com/paper/2310.01801/) (2023)
- [Scissorhands: Exploiting the Persistence of Importance Hypothesis for LLM KV Cache Compression at Test Time](https://mlsanity.com/paper/2305.17118/) (2023)
- [Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Time](https://mlsanity.com/paper/2310.17157/) (2023)
- [Fast Attention Requires Bounded Entries](https://mlsanity.com/paper/2302.13214/) (2023)
- [HyperAttention: Long-context Attention in Near-Linear Time](https://mlsanity.com/paper/2310.05869/) (2023)
- [FlashDecoding++: Faster Large Language Model Inference on GPUs](https://mlsanity.com/paper/2311.01282/) (2023)
- [Optimal approximate matrix product in terms of stable rank](https://mlsanity.com/paper/1507.02268/) (2015)
- [Hardness of Low Rank Approximation of Entrywise Transformed Matrix Products](https://mlsanity.com/paper/2311.01960/) (2023)

## Built on by (most cited first, 21 of 21)

- [TurboQuant: Online Vector Quantization with Near-optimal Distortion Rate](https://mlsanity.com/paper/2504.19874/) (2025)
- [QJL: 1-Bit Quantized JL Transform for KV Cache Quantization with Zero Overhead](https://mlsanity.com/paper/2406.03482/) (2024)
- [KVSharer: Efficient Inference via Layer-Wise Dissimilar KV Cache Sharing](https://mlsanity.com/paper/2410.18517/) (2024)
- [LongLLaDA: Unlocking Long Context Capabilities in Diffusion LLMs](https://mlsanity.com/paper/2506.14429/) (2025)
- [A Tighter Complexity Analysis of SparseGPT](https://mlsanity.com/paper/2408.12151/) (2024)
- [HSR-Enhanced Sparse Attention Acceleration](https://mlsanity.com/paper/2410.10165/) (2024)
- [ReAttention: Training-Free Infinite Context with Finite Attention Scope](https://mlsanity.com/paper/2407.15176/) (2024)
- [Streaming Attention Approximation via Discrepancy Theory](https://mlsanity.com/paper/2502.07861/) (2025)
- [BUZZ: Beehive-structured Sparse KV Cache with Segmented Heavy Hitters for Efficient LLM Inference](https://mlsanity.com/paper/2410.23079/) (2024)
- [HashEvict: A Pre-Attention KV Cache Eviction Strategy using Locality-Sensitive Hashing](https://mlsanity.com/paper/2412.16187/) (2024)
- [Compression Barriers for Autoregressive Transformers](https://mlsanity.com/paper/2502.15955/) (2025)
- [Nearly Optimal Attention Coresets](https://mlsanity.com/paper/2605.05602/) (2026)
- [The risk of KV cache compression](https://mlsanity.com/paper/2607.01520/) (2026)
- [DensityKV: Density-Guided KV Cache Compression for Long Video Generation](https://mlsanity.com/paper/2608.27922/) (2026)
- [CalibQuant: 1-Bit KV Cache Quantization for Multimodal LLMs](https://mlsanity.com/paper/2502.14882/) (2025)
- [SALE : Low-bit Estimation for Efficient Sparse Attention in Long-context LLM Prefilling](https://mlsanity.com/paper/2505.24179/) (2025)
- [Radar: Fast Long-Context Decoding for Any Transformer](https://mlsanity.com/paper/2503.10571/) (2025)
- [Time and Memory Trade-off of KV-Cache Compression in Tensor Transformer Decoding](https://mlsanity.com/paper/2503.11108/) (2025)
- [Sublinear Time Quantum Algorithm for Attention Approximation](https://mlsanity.com/paper/2602.00874/) (2026)
- [RoPE-Aware Bit Allocation for KV-Cache Quantization](https://mlsanity.com/paper/2606.24033/) (2026)
- [Query-Oblivious Coresets for Softmax Attention: Improved Bounds and Efficient Constructions](https://mlsanity.com/paper/2609.06327/) (2026)

## Abstract (arXiv)

Despite the significant success of large language models (LLMs), their extensive memory requirements pose challenges for deploying them in long-context token generation. The substantial memory footprint of LLM decoders arises from the necessity to store all previous tokens in the attention module, a requirement imposed by key-value (KV) caching. In this work, our focus is on developing an efficient compression technique for the KV cache. Empirical evidence indicates a significant clustering tendency within key embeddings in the attention module. Building on this key insight, we have devised a novel caching method with sublinear complexity, employing online clustering on key tokens and online ℓ2 sampling on values. The result is a provably accurate and efficient attention decoding algorithm, termed SubGen. Not only does this algorithm ensure a sublinear memory footprint and sublinear time complexity, but we also establish a tight error bound for our approach. Empirical evaluations on long-context question-answering tasks demonstrate that SubGen significantly outperforms existing and state-of-the-art KV cache compression methods in terms of performance and efficiency.