mlsanityData to 7 Oct 2026

SubGen: Token Generation in Sublinear Time and Memory

arXiv 2402.06082 ↗First posted 8 Feb 2024cs.LG cs.AI cs.DScited by 21

On the map: Efficient LLM inference and serving → KV cache optimization

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.

Key facts. Cited by 21 papers in the map (data through 7 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.

Builds on

19 of 28 references.

Closest ancestors · 3

Same direction, newest first

  1. 2023Model Tells You What to Discard: Adaptive KV Cache Compression for LLMs3 Oct
  2. 2023H2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models24 Jun
  3. 2023Scissorhands: Exploiting the Persistence of Importance Hypothesis for LLM KV Cache Compression at Test Time26 May

Other references · 16

  1. 2021Learning Transferable Visual Models From Natural Language Supervisioncited by 33,456
  2. 2023GPT-4 Technical Reportcited by 18,132
  3. 2023Llama 2: Open Foundation and Fine-Tuned Chat Modelscited by 12,865
  4. 2023Judging LLM-as-a-Judge with MT-Bench and Chatbot Arenacited by 8,393
  5. 2021Evaluating Large Language Models Trained on Codecited by 8,053
  6. 2021RoFormer: Enhanced Transformer with Rotary Position Embeddingcited by 4,581
  7. 2023Efficient Streaming Language Models with Attention Sinkscited by 2,115
  8. 2023Code Llama: Open Foundation Models for Codecited by 2,105
  9. 2022Imagen Video: High Definition Video Generation with Diffusion Modelscited by 1,765
  10. 2023FlexGen: High-Throughput Generative Inference of Large Language Models with a Single GPUcited by 567
  11. 2023Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Timecited by 247
  12. 2023Fast Attention Requires Bounded Entriescited by 102
4 more
  1. 2023HyperAttention: Long-context Attention in Near-Linear Timecited by 85
  2. 2023FlashDecoding++: Faster Large Language Model Inference on GPUscited by 70
  3. 2015Optimal approximate matrix product in terms of stable rankcited by 37
  4. 2023Hardness of Low Rank Approximation of Entrywise Transformed Matrix Productscited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 7; 2025: 8; 2026: 6.

21 papers.

Sort:

By area:

  1. 2025TurboQuant: Online Vector Quantization with Near-optimal Distortion Ratecited by 116
  2. 2024QJL: 1-Bit Quantized JL Transform for KV Cache Quantization with Zero Overheadcited by 47
  3. 2024KVSharer: Efficient Inference via Layer-Wise Dissimilar KV Cache Sharingcited by 38
  4. 2025LongLLaDA: Unlocking Long Context Capabilities in Diffusion LLMscited by 38
  5. 2024A Tighter Complexity Analysis of SparseGPTcited by 19
  6. 2024HSR-Enhanced Sparse Attention Accelerationcited by 19
  7. 2024ReAttention: Training-Free Infinite Context with Finite Attention Scopecited by 13
  8. 2025Streaming Attention Approximation via Discrepancy Theorycited by 9
  9. 2024BUZZ: Beehive-structured Sparse KV Cache with Segmented Heavy Hitters for Efficient LLM Inferencecited by 8
  10. 2024HashEvict: A Pre-Attention KV Cache Eviction Strategy using Locality-Sensitive Hashingcited by 6
  11. 2025Compression Barriers for Autoregressive Transformerscited by 5
  12. 2026Nearly Optimal Attention Coresetscited by 4
9 more
  1. 2026The risk of KV cache compressioncited by 4
  2. 2025CalibQuant: 1-Bit KV Cache Quantization for Multimodal LLMscited by 3
  3. 2025SALE : Low-bit Estimation for Efficient Sparse Attention in Long-context LLM Prefillingcited by 3
  4. 2025Radar: Fast Long-Context Decoding for Any Transformercited by 2
  5. 2025Time and Memory Trade-off of KV-Cache Compression in Tensor Transformer Decodingcited by 2
  6. 2026Sublinear Time Quantum Algorithm for Attention Approximationcited by 1
  7. 2026RoPE-Aware Bit Allocation for KV-Cache Quantizationcited by 1
  8. 2026DensityKV: Density-Guided KV Cache Compression for Long Video Generationcited by 1
  9. 2026Query-Oblivious Coresets for Softmax Attention: Improved Bounds and Efficient Constructionscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025Key, Value, Compress: A Systematic Exploration of KV Cache Compression Techniques
  2. 2024Effectively Compress KV Heads for LLM
  3. 2024A Simple and Effective L2 Norm-Based Strategy for KV Cache Compression
  4. 2024Compressing KV Cache for Long-Context LLM Inference with Inter-Layer Attention Similarity
  5. 2026Moment-KV: Momentum-Based Decode-Time KV Cache Compression for Long Generation
  6. 2025CompressKV: Semantic Retrieval Heads Know What Tokens are Not Important Before Generation
  7. 2024RazorAttention: Efficient KV Cache Compression Through Retrieval Heads
  8. 2024Not All Heads Matter: A Head-Level KV Cache Compression Method with Integrated Retrieval and Reasoning