STATIC-SOURCE RECURRENT ATTENTION: TIME, MEMORY, AND PRECISION

We study recurrent attention with immutable, position-locally encoded inputs and finite-precision queries. The model captures a class of iterative latent readers, including local-input configurations of Perceiver with a fixed source-kernel library. We prove two communication bounds: a cumulative query bound and a finite response-table bound whose size is independent of recurrent time and mutable memory. For set disjointness on two $N$-bit blocks, these imply $TM={\Omega }_{\epsilon }(N)$ and $P={\Omega }_{\epsilon }(\log N)$ for any fixed worst-case error $\epsilon <1/2$. Thus additional recurrent computation cannot compensate for sublogarithmic source precision. A matching construction achieves $P=\Theta (\log N)$ and $TM=O(N\log N)$. Complementing the lower bounds, we construct a fixed rational-weight recurrent-attention program that simulates a $\tau$-step, $S$-space Turing machine in $O(\tau +1)$ rounds and $O(S+p)$ mutable bits using $p=\Theta (\log (n+S+2))$ precision. A floating-point repair operation restores approximate softmax reads exactly before each state update, preventing error accumulation over time. An end-to-end finite-precision implementation matches independent Turing-machine traces for up to 10,010 transitions.