mlsanityData to 14 Oct 2026

Streaming Attention Approximation via Discrepancy Theory

arXiv 2502.07861 ↗First posted 11 Feb 2025cs.LG cs.AI cs.DScited by 11

Not on the map. Why?

Abstract (arXiv)

Large language models (LLMs) have achieved impressive success, but their high memory requirements present challenges for long-context token generation. In this paper we study the streaming complexity of attention approximation, a key computational primitive underlying token generation. Our main contribution is BalanceKV, a streaming algorithm for ε-approximating attention computations based on geometric process for selecting a balanced collection of Key and Value tokens as per Banaszczyk's vector balancing theory. We complement our algorithm with space lower bounds for streaming attention computation. Besides strong theoretical guarantees, BalanceKV exhibits empirically validated performance improvements over existing methods, both for attention approximation and end-to-end performance on various long context benchmarks.

Key facts. Cited by 11 papers in the map (data through 14 Oct 2026). Builds on 58 of its 84 references that are in the map. First posted on arXiv 11 Feb 2025.

Builds on

58 of 84 references.

References · 58

  1. 2017Attention Is All You Needcited by 60,361
  2. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,305
  3. 2023GPT-4 Technical Reportcited by 18,396
  4. 2024The Llama 3 Herd of Modelscited by 14,715
  5. 2023Llama 2: Open Foundation and Fine-Tuned Chat Modelscited by 13,028
  6. 2020Scaling Laws for Neural Language Modelscited by 6,586
  7. 2022Hierarchical Text-Conditional Image Generation with CLIP Latentscited by 6,585
  8. 2023Efficient Memory Management for Large Language Model Serving with PagedAttentioncited by 5,944
  9. 2023QLoRA: Efficient Finetuning of Quantized LLMscited by 3,418
  10. 2020Longformer: The Long-Document Transformercited by 3,413
  11. 2022DreamBooth: Fine Tuning Text-to-Image Diffusion Models for Subject-Driven Generationcited by 3,300
  12. 2024Gemini 1.5: Unlocking multimodal understanding across millions of tokens of contextcited by 3,224
38 more
  1. 2023FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioningcited by 2,598
  2. 2019HuggingFace's Transformers: State-of-the-art Natural Language Processingcited by 2,218
  3. 2023Efficient Streaming Language Models with Attention Sinkscited by 2,186
  4. 2024Qwen2 Technical Reportcited by 2,120
  5. 2022GPTQ: Accurate Post-Training Quantization for Generative Pre-trained Transformerscited by 1,919
  6. 2023LongBench: A Bilingual, Multitask Benchmark for Long Context Understandingcited by 1,417
  7. 2023GQA: Training Generalized Multi-Query Transformer Models from Multi-Head Checkpointscited by 1,346
  8. 2024SnapKV: LLM Knows What You are Looking for Before Generationcited by 880
  9. 2024DeepSeekMoE: Towards Ultimate Expert Specialization in Mixture-of-Experts Language Modelscited by 867
  10. 2023H2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Modelscited by 832
  11. 2019Fast Transformer Decoding: One Write-Head is All You Needcited by 717
  12. 2024KIVI: A Tuning-Free Asymmetric 2bit Quantization for KV Cachecited by 637
  13. 2024QuaRot: Outlier-Free 4-Bit Inference in Rotated LLMscited by 634
  14. 2024KVQuant: Towards 10 Million Context Length LLM Inference with KV Cache Quantizationcited by 591
  15. 2023FlexGen: High-Throughput Generative Inference of Large Language Models with a Single GPUcited by 575
  16. 2022Efficiently Scaling Transformer Inferencecited by 539
  17. 2024FlashAttention-3: Fast and Accurate Attention with Asynchrony and Low-precisioncited by 519
  18. 2023Scissorhands: Exploiting the Persistence of Importance Hypothesis for LLM KV Cache Compression at Test Timecited by 439
  19. 2024PyramidKV: Dynamic KV Cache Compression based on Pyramidal Information Funnelingcited by 432
  20. 2024MInference 1.0: Accelerating Pre-filling for Long-Context LLMs via Dynamic Sparse Attentioncited by 383
  21. 2023SpQR: A Sparse-Quantized Representation for Near-Lossless LLM Weight Compressioncited by 367
  22. 2024Data Engineering for Scaling Language Models to 128K Contextcited by 186
  23. 2024GEAR: An Efficient KV Cache Compression Recipe for Near-Lossless Generative Inference of LLMcited by 158
  24. 2024ShadowKV: KV Cache in Shadows for High-Throughput Long-Context LLM Inferencecited by 134
  25. 2024No Token Left Behind: Reliable KV Cache Compression via Importance-Aware Mixed Precision Quantizationcited by 101
  26. 2024Not All Heads Matter: A Head-Level KV Cache Compression Method with Integrated Retrieval and Reasoningcited by 97
  27. 2016Orthogonal Random Featurescited by 91
  28. 2023HyperAttention: Long-context Attention in Near-Linear Timecited by 85
  29. 2024KV Cache is 1 Bit Per Channel: Efficient Large Language Model Inference with Coupled Quantizationcited by 76
  30. 2024WKVQuant: Quantizing Weight and Key/Value Cache for Large Language Models Gains Morecited by 69
  31. 2024QAQ: Quality Adaptive Quantization for LLM KV Cachecited by 66
  32. 2023KDEformer: Accelerating Transformers via Kernel Density Estimationcited by 58
  33. 2024QJL: 1-Bit Quantized JL Transform for KV Cache Quantization with Zero Overheadcited by 52
  34. 2024RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Searchcited by 48
  35. 2015Frequent Directions : Simple and Deterministic Matrix Sketchingcited by 39
  36. 2018Near-Optimal Coresets of Kernel Density Estimatescited by 30
  37. 2020Discrepancy Minimization via a Self-Balancing Walkcited by 22
  38. 2024SubGen: Token Generation in Sublinear Time and Memorycited by 21

50 most cited of 58 All 58 (JSON)

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 2; 2026: 9.

11 papers.

  1. 2025TurboQuant: Online Vector Quantization with Near-optimal Distortion Ratecited by 125
  2. 2026WildCat: Near-Linear Attention in Theory and Practicecited by 6
  3. 2026Nearly Optimal Attention Coresetscited by 4
  4. 2026The risk of KV cache compressioncited by 4
  5. 2025CalibQuant: 1-Bit KV Cache Quantization for Multimodal LLMscited by 3
  6. 2026WitCert: Sound Runtime Risk Observability and Gating for KV-Cache Quantizationcited by 3
  7. 2026Trust the Mass: Forced Weights in KV-Cache Evictioncited by 1
  8. 2026Express Language Modelingcited by 0
  9. 2026Query-Oblivious Coresets for Softmax Attention: Improved Bounds and Efficient Constructionscited by 0
  10. 2026Prediction Is Not a Sufficient Memory Statecited by 0
  11. 2026Fast Quantized Johnson-Lindenstrauss Transformscited by 0