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

We characterize the memory required for streaming attention on a prescribed finite input grid, charging state and arithmetic in bits under the error scale $ϵ\Vert \mathrm{softmax}(Kq){\Vert }_2\Vert V{\Vert }_F$. 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 $R=\ln T$ and let $M_{d,b}$ count unit-ball keys on $2^{-b}{\mathbb{Z}}^d$. For scalar values and $ϵ=T^{-\beta }$ with fixed $\beta >0$, optimal space is $\Theta (R\min \{M_{d,b},(R/\ln R{)}^d\})$ at fixed $d$ and $b=O(\log T)$, and $\Theta (M_{d,b}R)$ at fixed $b$ and polylogarithmic $d$. The arbitrary-state lower bounds match deterministic histograms or rounded moments, including under output feedback. For fixed $d,b,B_0$ and failure probability, uniformly over $T^{-B_0}\le ϵ\le .1$, randomized space is instead $\Theta (\ln (1/ϵ)+\ln \ln T)$ with or without feedback, while deterministic space is $\Theta (\ln T)$ 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.