- 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
- 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.
-
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.
-
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
-
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?
-
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?