acceptodds
Under review as a conference paper at ICLR 2027

Finite-Precision Streaming Attention: Space Bounds and the Role of Randomness

Abstract

We characterize the memory required for streaming attention on a prescribed finite input grid, charging state and arithmetic in bits under the error scale . The lower bounds encode multi-bit symbols in binary occurrence frequencies: one terminal query recovers a selected symbol while respecting the input grid, stream length, and original token energy. Let and let count unit-ball keys on . For scalar values and with fixed , optimal space is at fixed and , and at fixed and polylogarithmic . The arbitrary-state lower bounds match deterministic histograms or rounded moments, including under output feedback. For fixed and failure probability, uniformly over , randomized space is instead with or without feedback, while deterministic space is in the charged-clock model. An all-prefix approximate-counting certificate establishes this separation with finite numerical workspace. The results concern bounded logits, with fixed-temperature and input-perturbation extensions. Finite checks certify decoding and active randomized updates; the measured configuration still favors exact histograms in total encoded state.

Primary area:
learning theory
Keywords:
streaming attention, space complexity, finite precision, randomized algorithms, approximate counting

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_i6aVOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

I found several passages difficult to follow, including in the introduction. Important constructions are named before they are explained, and some central arguments are compressed into phrases that leave the reader to reconstruct the reasoning. The examples below concern the writing, not the validity of the mathematics. I think these parts need a substantial rewrite before any technical judgment.

Critical strengths

See questions

Critical weaknesses

See questions

Questions for authors

Some examples of passages I could not understand:

  • Lines 39-41: "Our main technical contribution is a finite frequency channel. An inverse response construction first specifies real-valued encoder intermediates, which need not lie on the input grid." What is the "frequency channel"? What is being inverted?

  • Lines 48-49: "Write R=ln⁡TR=\ln T and let Md,bM_{d,b} be the number of legal unit-ball keys on the grid 2−bZd2^{-b}\mathbb{Z}^d."

    Define "legal keys" explicitly at first use, before discussing their cardinality. What is T?

  • Lines 51-53: "Explicitly conditioned key sets make the frequency channel match deterministic histograms or rounded moments."

    "Conditioned" in what sense? What are "rounded moments"?

  • Lines 56-58: "Classical approximate counting supplies the randomized saving; we prove its matching transfer to the original attention error, including finite workspace and an all-prefix guarantee valid under causal feedback."

    What is being transferred? What does "matching" mean here?

  • Lines 185-186: "Alice transmits only the streaming state. Fano’s inequality for each selected symbol and entropy subadditivity prove (9)."

    What is the role of Alice? It was not introduced before. What information does the decoder have?

  • Lines 244-245: "Assigning private coins to each counter makes a causal input policy only an interleaving of their already-uniform trajectories."

    Uniform in what sense? Why does adaptive interleaving preserve accuracy?

  • Lines 255-256: "Capping ee at H+2H+2 charges worst-case memory without adding failure on the good event."

    What is the "good event"?

  • Lines 295-296: "Neither a floored Γ\Gamma nor energy computed after averaging values is used."

    What is a "floored Γ\Gamma"? Which averaging operation is being excluded?

  • Lines 323-324: "Appendix I separates persistent encoding, object sizes, allocation peaks, sampled register liveness, and a reviewed numerical-workspace envelope."

    What is this "workspace envelope"? Is it measured or proved?

Reviewer_PtzdOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies how much memory streaming attention is needed when the inputs have finite precision, with keys and queries in the unit ball and all coordinates on a grid of spacing 2^{−b}. It asks whether algorithms can use much less memory than in the real-valued setting of earlier work (Kochetkova et al. 2025; Chen et al. 2026), under the same error measure.

For high accuracy, the authors characterize when restricting the inputs to a finite grid reduces the memory requirement: for ε = T^{−β}, where T is the stream length, the paper shows that Θ(log T · min{M, (log T/log log T)^d}) bits are necessary and sufficient in fixed dimension d, where M is the number of grid points. The upper bound follows from keeping either exact counts and value sums for all grid points or a truncated Taylor expansion, as in Chen et al. The main technical contribution is the matching lower bound, proved by an encoding argument, and its rate matches known covering-number bounds for Gaussian kernels (Kühn 2011).

The paper also studies randomized algorithms. For constant ε and fixed d and b, they need only Θ(log log T) bits, while deterministic algorithms need Θ(log T). The randomized algorithm keeps approximate counts, and the paper shows that approximate counts suffice for attention.

Critical strengths
  1. Tight bounds for high accuracy. The paper settles the memory of high-accuracy streaming attention in this model, with matching upper and lower bounds Θ(log T · min{M, (log T/log log T)^d}) deterministic or randomized. The lower bound (the paper’s main contribution) is built from standard ingredients, but fitting them to low-precision inputs and streams of length T takes careful work.

  2. When randomization helps. The paper also gives sharp answers on randomization, with matching lower bounds: randomized algorithms need Θ(log log T) bits for constant accuracy against Θ(log T) for deterministic ones, and gain nothing for high accuracy. I like that the randomized guarantee holds even when the stream depends on previous outputs, as in autoregressive generation.

Critical weaknesses
  1. The bounded-norm assumption excludes attention concentrated on a few tokens in a long stream. The grid assumption also differs from what is used in practical KV compression. In addition the reported experiment does not demonstrate the memory saving.

  2. The algorithms that turn out to be optimal are the “standard’’ ones, and the gain from randomization is the familiar one from approximate counting. The main contribution is therefore the lower bound, which is solid but conceptually modest.

Questions for authors
  1. Range of Theorem 2. Theorem 2 is stated for d polylogarithmic in T, but the proof in Appendix D.2 does not seem to use more than the number of keys being a small power of T. Does the theorem hold for d up to a small power of T, and if not, where does the proof need the polylogarithmic bound?

  2. Implications for continuous inputs. Your hard instances seem to be valid inputs for Kochetkova et al. and Chen et al. as well. Does Theorem 1 give a lower bound in their real-valued setting that was not known for fixed dimension, and does a matching upper bound hold there with memory counted in bits as here? In either case, the paper should address this in my opinion.

Reviewer_NVoVOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper targets a KV cache compression problem as follows. There is a stream of tokens and each comes with two vectors, key (k) and value (v). At any point a query q can arrive, and the algorithm has to output the attention result that is the softmax-weighted average of the values with weights e^(k·q). The usual way to do this is to keep the whole KV cache, which grows linearly with the size of all keys and values. The question is how few bits of memory one can keep and still answer every query approximately.

A previous work (Haris and Onak, 2025) showed that any algorithm that can output a (1+\eta)-approximate attention result with probability 9/10 must use linear memory size for any constant \eta. This paper studies lower bounds in a variant version with 1) additive error, 2) keys and queries are points of 2^(−b)·Z^d inside the unit ball, and 3) values are multiples of 2^(−b) in [−1, 1].

However, the paper is not rigorous enough to deliver any concrete result. Several things are not strictly defined throughout the entire paper. The paper certainly feels like "AI slop" and is well-below the bar of proper scientific communication. The current writeup is full of poorly written "intuition"; just as few clear examples:

  • In Theorem 1 and 2 statements, “all three spaces” are never properly defined. The only relevant content is a sentence “Let S_obl,S_ad,Sd_{et,ad} denote optimal oblivious randomized, feedback randomized,and feedback deterministic space.”
  • “Charged-clock convention” in Theorem 3 is never formally defined.

Those undefined terms and lack of polish make the results in the paper extremely difficult to understand, and push the work of polishing (which should have been done by the authors) onto reviewers. This is a clear reject from my perspective.

Critical strengths

The topic is of high interest to many researchers working scalable attention approaches.

Critical weaknesses

The critical weakness is the presentation.

Questions for authors

None.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.