acceptodds
Withdrawn from ICLR 2027

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

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

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 -bit blocks, these imply and for any fixed worst-case error . Thus additional recurrent computation cannot compensate for sublogarithmic source precision. A matching construction achieves and . Complementing the lower bounds, we construct a fixed rational-weight recurrent-attention program that simulates a -step, -space Turing machine in rounds and mutable bits using 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.

Primary area:
learning theory
Keywords:
Recurrent Attention, Finite-Precision Computation, Communication Complexity, Time–Memory Tradeoffs, Transformer Expressivity, Turing Machine Simulation, Floating-Point Arithmetic

Reviews

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

This paper studies the computational limitations of recurrent attention when inputs are static and mutable states access them through finite-precision interfaces. Using communication complexity, the authors derive lower bounds on time, memory, and precision. They also develop a recurrent-attention construction for Turing-machine simulation and evaluate it experimentally.

Critical strengths

Understanding the computational limitations of recurrent attention is a timely and relevant research direction, although the proposed analysis considers a restrictive setting.

Critical weaknesses
  1. Clarity and organization. The paper is difficult to follow, as the studied problem, its motivation, and the connections between the results are not clearly established.
  • Introduction: The paper starts with general statements about Transformer limitations without motivating or properly introducing the specific architecture studied. It neither establishes a research gap nor clearly summarizes the contributions.
  • Section 1.1: Perceiver and other architectures are introduced without explaining their relevance, while several terms remain undefined. The purpose of Figure 1 is also unclear.
  • Sections 3–5: The connections between the theoretical results are insufficiently explained, with little interpretation of what the theorems establish and why they matter.
  • The paper also lacks a conclusion.
  1. Contextualization and related work The related-work section reads as a juxtaposition of research directions rather than a structured discussion that identifies the research gap and positions the contributions. In particular, the motivation for studying set disjointness and its relevance to practical recurrent-attention applications remain unclear. The novelty of some results, especially those concerning finite-precision softmax, is also insufficiently established relative to recent work such as Brösamle and Eckstein (ICML 2026). Overall, the paper does not clearly communicate what new understanding its theoretical results provide beyond existing work.

  2. Experimental evaluation The evaluation is very brief and primarily consists of sanity checks of the theoretical construction using two synthetic Turing machines. The experiments mainly verify that the simulation works and that removing the numerical repair mechanism leads to errors. While these checks are useful, they provide limited insight into the practical significance of the results. Evaluating the derived lower bounds on concrete recurrent-attention architectures would help establish their relevance and strengthen the connection between theory and practice.

Questions for authors
  1. Motivation and applicability: Could the authors clarify why they focus on this particular computational model and identify practical recurrent-attention architectures that satisfy its assumptions?

  2. Novelty and validation: Could the authors clarify how their finite-precision results differ from Brösamle and Eckstein (ICML 2026), and whether the derived lower bounds could be evaluated quantitatively on practical architectures?

Reviewer_SbTSOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The Authors 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. The Authors claim that they proved two communication bounds: a cumulative query bound and a finite response-table bound whose size is independent of recurrent time and mutable memory.

Critical strengths

The theoretical analysis conducted in the paper (see: Section 3) sounds solid, yet the Reviewer is not certain that the presented proofs are completely correct. The compiler execution experiment is very interesting (all 11,751 transitions agreeing exactly is a great result, yet more elaborate discussion on what the Authors summarize as: " satisfying the theorem’s sufficient parameters" would be very welcome).

Critical weaknesses

The paper seems to be written by the AI agent. The narrative is not clear and this starts as early on as in the Abstract (what is P and TM ?). What are the main claims made in the paper ? It is hard to find them in the introduction. Even though the compiler experiment is very interesting (see: my comment above), the empirical section is too compact (it does not contain other results). The presentation of the paper can be significantly improved. Some intuition or sketch of the proofs of the theorems from the main body of the paper would improve the overall presentation. Certain sections are completely missing (what about Conclusion summarizing the results and findings ?).

Questions for authors

The Reviewer would like to ask the Authors to address the questions raised in the Critical Weaknesses section.

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

The paper studies recurrent attention in which mutable slots repeatedly query a fixed input. Each input element is encoded independently and never updated, and the slots read it through a fixed set of attention kernels at limited numerical precision.

The paper proves two communication bounds. The first charges each query for the numerical summaries it exchanges. The second collects everything one input block can tell the slots into a finite response table over all possible queries and accumulator values, and it holds for any number of rounds and any amount of slot memory, provided the program halts on every input. For disjointness with constant dimensions and kernel count, the first bound gives a time-memory lower bound and the second gives a logarithmic precision requirement. Both have bounded-error versions, and the table bound also has an average-case version.

On the constructive side, a two-step rounding trick recovers the exact intended lattice value from an approximate softmax read, under the paper's precision and score-gap conditions. This gives a fixed-weight compiler that simulates a Turing machine exactly at logarithmic precision, and a disjointness construction that matches the precision bound. A one-work-tape version of the compiler is implemented for two machines and checked after every transition against a reference interpreter.

Critical strengths
  • I like the response-table bound. It shows that extra rounds and extra memory cannot obtain more from a fixed finite interface, so input access and computation become separate resources. The bound is stated for rounded softmax with explicit numerical semantics, and for disjointness the precision lower and upper bounds match up to constant factors.
  • I also appreciate that the compiler stays exact with a precision that does not grow with run length, and that its implementation is checked after every transition against an independent interpreter.
Critical weaknesses
  • My main reservation is that the results speak directly to a narrow class of architectures.
    • The bounds assume records that are never updated, a fixed kernel library, and an encoding of each input block that does not depend on the other block. The disjointness corollaries also fix the query width.
    • The paper notes that Slot Attention and BLIP-2's Q-Former expose different interfaces and need extra accounting, and standard Transformers, which rewrite token states at every layer, are not of the static-source form. As far as I can see, the architectures shown to fit directly are the original Perceiver's local-input setting with shared source projections, and Set2Set.
    • Once query width is allowed to grow, the table bound only requires query width times precision to exceed roughly the log of the input length. For realistic query widths and input lengths this holds even at very low precision, so I think the precision requirement matters only for very narrow queries.
  • I also found the main text quite terse. Definitions and results are stated compactly, all proofs are in the appendix, and the paper ends without a conclusion. A short closing section on what the results imply for practical models would help readers a lot.
Questions for authors
  • Section 6 reports a first semantic divergence when repair is removed or fused. Does that mean the decoded machine configuration differs from the interpreter, or that a stored word first leaves the exact lattice? If the run without repair were continued, would it ever return a wrong answer?
  • Could you compare the compiler's resources with those of Chung & Siegelmann and Giannou et al., covering precision and its dependence on run length, persistent memory, rounds, and whether the weights are fixed?
  • Is the gap between the time-memory lower bound and your construction inherent to the model?

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

Related papers

Discussion (0)

Sign in to comment.