pith. sign in

arxiv: 2606.07205 · v1 · pith:BXPVIQS4new · submitted 2026-06-05 · 💻 cs.DS · cs.LG

Towards Tight Bounds for Streaming Attention

Justin Y. Chen , Ying Feng , Piotr Indyk , Michael Kapralov , Ekaterina Kochetkova , Boris Prokhorov This is my paper

Pith reviewed 2026-06-27 20:35 UTC · model grok-4.3

classification 💻 cs.DS cs.LG
keywords streaming algorithmsattention mechanismkernel density estimationspace complexitydiscrepancy theorypolynomial methodINDEX problemKV cache compression
0
0 comments X

The pith

Streaming attention approximation requires space nearly independent of the precision parameter.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes nearly tight space bounds for the streaming attention approximation problem, which formalizes the task of maintaining a compressed KV cache while approximating transformer attention outputs. Prior work left a gap where algorithmic space grew with the desired precision but lower bounds did not. The authors close this gap by combining three kernel density estimation techniques for the upper bound and introducing a new reduction from the INDEX problem with side information for the lower bound. A sympathetic reader would care because this determines the fundamental memory cost of running large language models under streaming constraints.

Core claim

The space complexity of streaming attention approximation is governed by a nearly tight interplay of discrepancy-based coreset constructions, the polynomial method, and space partitioning on the algorithmic side, together with a new INDEX-based lower bound technique that removes the previous dependence on the precision parameter.

What carries the argument

Interplay of discrepancy-based coreset constructions, the polynomial method, and space partitioning applied to kernel density estimation tasks, plus a reduction from INDEX with side information.

If this is right

  • Space usage for streaming attention no longer increases with the precision parameter.
  • The upper and lower bounds are nearly tight, closing the gap from earlier discrepancy-based and information-theoretic results.
  • The new INDEX-with-side-information technique applies to other high-dimensional geometric estimation problems.
  • KV cache compression algorithms can be designed around the combined discrepancy-polynomial-partitioning framework.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The techniques could be instantiated in practical transformer implementations to achieve memory savings without precision-dependent overhead.
  • Similar reductions may tighten space bounds for streaming versions of other attention variants or related sequence models.
  • The work suggests that high-dimensional streaming problems in general may benefit from mixing discrepancy, polynomial, and partitioning methods.

Load-bearing premise

The streaming attention approximation problem reduces to kernel density estimation tasks whose space is controlled by the cited discrepancy, polynomial, and partitioning methods.

What would settle it

An explicit streaming algorithm whose space grows with precision while matching the new lower bound construction, or a lower bound proof showing space must grow with precision.

Figures

Figures reproduced from arXiv: 2606.07205 by Boris Prokhorov, Ekaterina Kochetkova, Justin Y. Chen, Michael Kapralov, Piotr Indyk, Ying Feng.

Figure 1
Figure 1. Figure 1: Recentering and rescaling procedure for low radius datasets [PITH_FULL_IMAGE:figures/full_fig_p013_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Illustration of the standard Merge-and-Reduce algorithm ( [PITH_FULL_IMAGE:figures/full_fig_p016_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Recentering and rescale procedure for low radius datasets [PITH_FULL_IMAGE:figures/full_fig_p033_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Illustration of the standard Merge-and-Reduce algorithm ( [PITH_FULL_IMAGE:figures/full_fig_p037_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Illustration of the weighted Merge-and-Reduce algorithm ( [PITH_FULL_IMAGE:figures/full_fig_p038_5.png] view at source ↗
read the original abstract

The attention mechanism is a cornerstone of modern transformer architectures. However, its expressive power comes at the cost of quadratic runtime and linear space usage. In particular, the classical transformer architecture explicitly stores all previously seen input elements (tokens) in order to generate the next one. The problem of implementing a transformer in limited space, known as KV cache compression, has received much interest over the past few years, spurring the development of powerful heuristics. Recent works of Haris et al, COLT'25 and Kochetkova et al, NeurIPS'25, formalized KV cache compression as the streaming attention approximation problem, providing both upper bounds (based on discrepancy theory) and information theoretic lower bounds. However, those papers left open a significant gap between the upper and lower bounds. For example, the space usage of their algorithms increases with the precision parameter, but the lower bound does not get stronger. In this work, we revisit the streaming attention approximation problem and provide nearly tight bounds on its space complexity. On the algorithmic side, we achieve the result through a surprisingly tight interplay between three distinct methods for kernel density estimation: discrepancy-based coreset constructions (e.g., Charikar-Kapralov-Waingarten'24), the polynomial method (e.g., Greengard-Rokhlin'87, Alman-Song'23), and space partitioning (e.g., Andoni-Laarhoven-Razenshteyn-Waingarten'17, Charikar-Kapralov-Nouri-Siminelakis'20). On the lower bound side, our main technical contribution is a new technique for using the INDEX problem with a large amount of side information that we hope will prove useful in other high dimensional geometric estimation problems.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper claims to close the gap between upper and lower bounds on space complexity for the streaming attention approximation problem (KV cache compression). The upper bound is achieved by reducing the problem to kernel density estimation instances and combining three techniques: discrepancy-based coreset constructions (Charikar-Kapralov-Waingarten'24), the polynomial method (Alman-Song'23 and earlier), and space partitioning (Andoni et al.'17 and related). The lower bound introduces a new reduction technique based on the INDEX problem augmented with side information.

Significance. If the claimed near-tightness holds (i.e., the combined upper bound remains independent of the precision parameter ε while matching the lower bound up to lower-order factors), the result would resolve an explicit open gap from Haris et al. (COLT'25) and Kochetkova et al. (NeurIPS'25) and supply the first parameter-free space characterization for this streaming problem. The new INDEX-with-side-information technique is presented as potentially reusable for other high-dimensional geometric streaming tasks.

major comments (2)
  1. [algorithmic construction / reduction to KDE] The central claim of near-tightness rests on the reduction from streaming attention to KDE instances (abstract and algorithmic construction). The skeptic note correctly identifies the risk that error tolerances chosen for the three KDE primitives (discrepancy coresets, polynomial method, space partitioning) may reintroduce explicit 1/ε dependence in the final space bound. The manuscript must explicitly derive, in the section describing the interplay, the concrete error parameters passed to each primitive and show that the resulting space expression is independent of ε (or matches the lower bound's independence).
  2. [lower bound / INDEX reduction] The lower-bound section introduces a new INDEX-with-side-information reduction as the main technical contribution. It is load-bearing for the tightness claim, yet the abstract supplies no indication of how the side information is instantiated to match the attention kernel and streaming model without weakening the bound relative to prior information-theoretic lower bounds. A concrete parameter setting or lemma showing the reduction preserves the ε-independent lower bound is required.
minor comments (2)
  1. Notation for the attention kernel and the streaming model should be unified between the introduction and the technical sections to avoid ambiguity when referring to the precision parameter ε.
  2. The citations to the three KDE methods are appropriate but would benefit from a short table or paragraph contrasting their individual space expressions before the combined bound is stated.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful and constructive review. The two major comments identify places where additional explicit derivations would strengthen the presentation. We address both below and will revise the manuscript to incorporate the requested details.

read point-by-point responses

  1. Referee: [algorithmic construction / reduction to KDE] The central claim of near-tightness rests on the reduction from streaming attention to KDE instances (abstract and algorithmic construction). The skeptic note correctly identifies the risk that error tolerances chosen for the three KDE primitives (discrepancy coresets, polynomial method, space partitioning) may reintroduce explicit 1/ε dependence in the final space bound. The manuscript must explicitly derive, in the section describing the interplay, the concrete error parameters passed to each primitive and show that the resulting space expression is independent of ε (or matches the lower bound's independence).

    Authors: We agree that an explicit error-propagation calculation is needed for clarity. In the revised manuscript we will add a dedicated paragraph (new Subsection 4.4) that assigns error tolerances of ε/3 to each primitive and derives the composed space bound. Because the discrepancy coreset construction of Charikar-Kapralov-Waingarten'24 already yields space independent of ε once the kernel is approximated to constant accuracy, the polynomial method contributes only a logarithmic factor in 1/δ (with δ set to a constant), and the partitioning step of Andoni et al. is invoked only on a constant-accuracy instance, the overall space remains independent of ε and matches the lower bound up to lower-order terms. We will include the concrete parameter settings and the resulting expression. revision: yes

  2. Referee: [lower bound / INDEX reduction] The lower-bound section introduces a new INDEX-with-side-information reduction as the main technical contribution. It is load-bearing for the tightness claim, yet the abstract supplies no indication of how the side information is instantiated to match the attention kernel and streaming model without weakening the bound relative to prior information-theoretic lower bounds. A concrete parameter setting or lemma showing the reduction preserves the ε-independent lower bound is required.

    Authors: Section 5 already contains the reduction, but we acknowledge that the abstract is too high-level and that an explicit lemma would help. In the revision we will add Lemma 5.4, which instantiates the side information as the exact kernel values on a fixed set of O(1) reference points (independent of ε) and shows that any streaming algorithm solving the attention problem must still solve an INDEX instance of size Ω(1) whose communication lower bound is independent of ε. The parameter settings are d = Θ(log n), stream length n, and side-information size poly(log n); these choices preserve the ε-independent Ω(1) lower bound while matching the attention kernel exactly on the relevant queries. revision: yes

Circularity Check

0 steps flagged

Minor self-citations present but not load-bearing; bounds assembled from external KDE primitives plus new reduction

full rationale

The derivation relies on combining three externally published KDE techniques (discrepancy coresets, polynomial method, space partitioning) cited with examples from prior works, plus a new INDEX-based reduction for the lower bound. Overlapping authors appear in some citations (Kapralov in Charikar-Kapralov-Waingarten'24; Kochetkova in prior NeurIPS'25 work), but these are independent published results rather than self-defined inputs or fitted parameters renamed as predictions. No equations or claims in the provided text reduce the space bounds to a construction equivalent to the paper's own fitted values or ansatzes. The chain remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on the assumption that streaming attention approximation reduces to kernel density estimation whose space can be bounded by the three cited external methods plus a new communication-complexity reduction; no free parameters, invented entities, or ad-hoc axioms are named in the abstract.

axioms (2)
  • domain assumption Streaming attention can be approximated via kernel density estimation
    Abstract states the algorithmic side uses discrepancy-based coreset, polynomial method, and space partitioning for KDE.
  • domain assumption The INDEX problem with side information yields a strong lower bound for the geometric estimation task
    Abstract presents this as the main technical contribution on the lower bound side.

pith-pipeline@v0.9.1-grok · 5863 in / 1342 out tokens · 15099 ms · 2026-06-27T20:35:53.851050+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

47 extracted references · 7 canonical work pages · 1 internal anchor

  1. [1]

    Proceedings of the 38th International Conference on Machine Learning (ICML) , year =

    Arturs Backurs and Piotr Indyk and Cameron Musco and Tal Wagner , title =. Proceedings of the 38th International Conference on Machine Learning (ICML) , year =

  2. [2]

    Proceedings of the International Conference on Learning Representations (ICLR) , year =

    Ainesh Bakshi and Piotr Indyk and Praneeth Kacham and Sandeep Silwal and Samson Zhou , title =. Proceedings of the International Conference on Learning Representations (ICLR) , year =

  3. [3]

    2010 IEEE 51st Annual Symposium on Foundations of Computer Science (FOCS) , pages =

    Nikhil Bansal , title =. 2010 IEEE 51st Annual Symposium on Foundations of Computer Science (FOCS) , pages =

    2010

  4. [4]

    Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC) , pages =

    Nikhil Bansal and Daniel Dadush and Shashwat Garg and Shachar Lovett , title =. Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC) , pages =

  5. [5]

    SIAM Journal on Computing , volume =

    Shachar Lovett and Raghu Meka , title =. SIAM Journal on Computing , volume =

  6. [6]

    Factorization Norms and Hereditary Discrepancy , journal =

    Ji. Factorization Norms and Hereditary Discrepancy , journal =

  7. [7]

    Maddison and Andriy Mnih and Yee Whye Teh , title =

    Chris J. Maddison and Andriy Mnih and Yee Whye Teh , title =. 5th International Conference on Learning Representations,. 2017 , url =

    2017

  8. [8]

    5th International Conference on Learning Representations,

    Eric Jang and Shixiang Gu and Ben Poole , title =. 5th International Conference on Learning Representations,. 2017 , url =

    2017

  9. [9]

    Distilling the Knowledge in a Neural Network

    Geoffrey E. Hinton and Oriol Vinyals and Jeffrey Dean , title =. CoRR , volume =. 2015 , url =. 1503.02531 , timestamp =

    work page internal anchor Pith review Pith/arXiv arXiv 2015

  10. [10]

    2025 , url =

    NIST Digital Library of Mathematical Functions , howpublished =. 2025 , url =

    2025

  11. [11]

    2018 , month = sep, note =

    Tom Alberts and Davar Khoshnevisan , title =. 2018 , month = sep, note =

    2018

  12. [12]

    and Sawhney, Mehtaab S

    Alweiss, Ryan and Liu, Yang P. and Sawhney, Mehtaab S. , title =. SIAM Journal on Computing , pages =. 2021 , doi =. https://doi.org/10.1137/21M1442450 , abstract =

    work page doi:10.1137/21m1442450 2021

  13. [13]

    The Thirty-ninth Annual Conference on Neural Information Processing Systems , year=

    Streaming Attention Approximation via Discrepancy Theory , author=. The Thirty-ninth Annual Conference on Neural Information Processing Systems , year=

  14. [14]

    Razenshteyn , editor =

    Andoni, Alexandr and Razenshteyn, Ilya , title =. Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing , pages =. 2015 , isbn =. doi:10.1145/2746539.2746553 , abstract =

    work page doi:10.1145/2746539.2746553 2015

  15. [15]

    Proceedings of the 2017 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , chapter =

    Alexandr Andoni and Thijs Laarhoven and Ilya Razenshteyn and Erik Waingarten , title =. Proceedings of the 2017 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , chapter =. 2017 , pages =. doi:10.1137/1.9781611974782.4 , URL =. https://epubs.siam.org/doi/pdf/10.1137/1.9781611974782.4 , abstract =

    work page doi:10.1137/1.9781611974782.4 2017

  16. [16]

    Doctoral Theses , publisher=

    High-dimensional similarity search and sketching: algorithms and hardness , author=. Doctoral Theses , publisher=. 2017 , url=

    2017

  17. [17]

    2020 , eprint=

    Kernel Density Estimation through Density Constrained Near Neighbor Search , author=. 2020 , eprint=

    2020

  18. [18]

    2020 , eprint=

    Oblivious Sketching of High-Degree Polynomial Kernels , author=. 2020 , eprint=

    2020

  19. [19]

    2017 IEEE 58th Annual Symposium on Foundations of Computer Science , pages=

    Hashing-based-estimators for kernel density in high dimensions , author=. 2017 IEEE 58th Annual Symposium on Foundations of Computer Science , pages=. 2017 , organization=

    2017

  20. [20]

    Efficient Density Evaluation for Smooth Kernels , Year =

    Backurs, Arturs and Charikar, Moses and Indyk, Piotr and Siminelakis, Paris , Booktitle =. Efficient Density Evaluation for Smooth Kernels , Year =

  21. [21]

    Advances in neural information processing systems , volume=

    Space and time efficient kernel density estimation in high dimensions , author=. Advances in neural information processing systems , volume=

  22. [22]

    Rehashing kernel evaluation in high dimensions , Year =

    Siminelakis, Paris and Rong, Kexin and Bailis, Peter and Charikar, Moses and Levis, Philip , Booktitle =. Rehashing kernel evaluation in high dimensions , Year =

  23. [23]

    International Conference on Artificial Intelligence and Statistics , pages=

    Deann: Speeding up kernel-density estimation using approximate nearest neighbor search , author=. International Conference on Artificial Intelligence and Statistics , pages=. 2022 , organization=

    2022

  24. [24]

    1995 , isbn =

    Kremer, Ilan and Nisan, Noam and Ron, Dana , title =. 1995 , isbn =. doi:10.1145/225058.225277 , booktitle =

    work page doi:10.1145/225058.225277 1995

  25. [25]

    Vershynin, Roman , title =

  26. [26]

    and Tai, Wai Ming , title =

    Phillips, Jeff M. and Tai, Wai Ming , title =. Discrete Comput. Geom. , month = jun, pages =. 2020 , issue_date =. doi:10.1007/s00454-019-00134-6 , abstract =

    work page doi:10.1007/s00454-019-00134-6 2020

  27. [27]

    2024 , booktitle =

    Moses Charikar and Michael Kapralov and Erik Waingarten , title =. 2024 , booktitle =. doi:10.1137/1.9781611977912.184 , URL =. https://epubs.siam.org/doi/pdf/10.1137/1.9781611977912.184 , abstract =

    work page doi:10.1137/1.9781611977912.184 2024

  28. [28]

    Symposium on Theory of Computing , year=

    On the Computational Hardness of Transformers , author=. Symposium on Theory of Computing , year=

  29. [29]

    2025 , eprint=

    Subquadratic Algorithms and Hardness for Attention with Any Temperature , author=. 2025 , eprint=

    2025

  30. [30]

    International conference on algorithmic learning theory , pages=

    On the computational complexity of self-attention , author=. International conference on algorithmic learning theory , pages=. 2023 , organization=

    2023

  31. [31]

    Advances in Neural Information Processing Systems , volume=

    Fast attention requires bounded entries , author=. Advances in Neural Information Processing Systems , volume=

  32. [32]

    Advances in neural information processing systems , volume=

    Attention is all you need , author=. Advances in neural information processing systems , volume=

  33. [33]

    Proceedings of machine learning and systems , volume=

    Efficiently scaling transformer inference , author=. Proceedings of machine learning and systems , volume=

  34. [34]

    Journal of computational physics , volume=

    A fast algorithm for particle simulations , author=. Journal of computational physics , volume=. 1987 , publisher=

    1987

  35. [35]

    International Conference on Learning Representations , year=

    Reformer: The efficient transformer , author=. International Conference on Learning Representations , year=

  36. [36]

    International Conference on Learning Representations , year=

    Rethinking attention with performers , author=. International Conference on Learning Representations , year=

  37. [37]

    Advances in Neural Information Processing Systems , year=

    Scatterbrain: Unifying sparse and low-rank attention , author=. Advances in Neural Information Processing Systems , year=

  38. [38]

    International Conference on Machine Learning , pages=

    Kdeformer: Accelerating transformers via kernel density estimation , author=. International Conference on Machine Learning , pages=. 2023 , organization=

    2023

  39. [39]

    The Twelfth International Conference on Learning Representations , year=

    HyperAttention: Long-context Attention in Near-Linear Time , author=. The Twelfth International Conference on Learning Representations , year=

  40. [40]

    Advances in Neural Information Processing Systems , volume=

    H2o: Heavy-hitter oracle for efficient generative inference of large language models , author=. Advances in Neural Information Processing Systems , volume=

  41. [41]

    Proceedings of Machine Learning Research , volume=

    KIVI: A Tuning-Free Asymmetric 2bit Quantization for KV Cache , author=. Proceedings of Machine Learning Research , volume=. 2024 , publisher=

    2024

  42. [42]

    Advances in Neural Information Processing Systems , volume=

    Kv cache is 1 bit per channel: Efficient large language model inference with coupled quantization , author=. Advances in Neural Information Processing Systems , volume=

  43. [43]

    Advances in Neural Information Processing Systems , volume=

    Snapkv: Llm knows what you are looking for before generation , author=. Advances in Neural Information Processing Systems , volume=

  44. [44]

    2026 , month = mar, howpublished =

    Zandieh, Amir and Mirrokni, Vahab , title =. 2026 , month = mar, howpublished =

    2026

  45. [45]

    ACM Journal of the ACM (JACM) , volume=

    A framework for adversarially robust streaming algorithms , author=. ACM Journal of the ACM (JACM) , volume=. 2022 , publisher=

    2022

  46. [46]

    Theory OF Computing , volume=

    The One-Way Communication Complexity of Hamming Distance , author=. Theory OF Computing , volume=

  47. [47]

    The Thirty Eighth Annual Conference on Learning Theory , pages=

    Compression Barriers in Autoregressive Transformers , author=. The Thirty Eighth Annual Conference on Learning Theory , pages=. 2025 , organization=

    2025