acceptodds
Under review as a conference paper at ICLR 2027

One Retrieved Token per Step Is Enough: Tight Linear Chain-of-Thought Complexity for Directed Reachability

Abstract

A recent ICML paper asks whether directed reachability in the self-consistent bounded-attention prefix-oracle model can be solved with chain-of-thought tokens, rather than the known construction. We give a sparse-sensitive resolution: for every -vertex, -edge input, including arbitrary edge order, self-loops, and repeated tokens, a -cBAPO-CoT decides reachability using at most nonhalt tokens and an alphabet of size . Together with the existing linear lower bound under fixed-bandwidth, worst-case quantifiers, this gives tight token complexity. The construction combines split-invariant predecessor attention over present edges with threaded depth-first search: each discovery token records visitedness, a parent, and the continuation needed after backtracking. We also give a -token simple-path certificate and a bound for regular reachability with a fixed deterministic finite automaton. A separate result shows that arbitrary-oracle cBAPOs can decide nonrecursive length languages even over a binary alphabet, whereas fixed finite-alphabet machines with total-recursive suffix oracles are Turing-simulable. Existing exhaustive and randomized verification covers 14,236 instances. An illustrative single-seed neural study is retained as diagnostic evidence, not as a realization or proof of the oracle model.

Primary area:
learning theory
Keywords:
chain-of-thought reasoning, token complexity, directed reachability, self-consistent bounded-attention prefix oracles (cBAPO), predecessor attention, threaded depth-first search, regular-path reachability

Reviews

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

The authors study the optimal chain of thought length for solving directed reachability under the BAPO model. Previous work showed that directed reachability in n-node, m-edge graphs can be solved by a BAPO-CoT with O(n2)O(n^2) CoT steps, but requires at least Ω(m)\Omega(m). The authors close this gap, producing a BAPO-CoT that solves reachability in Θ(m)\Theta(m) steps, showing the previously known lower bound is tight. Additionally, the authors provide additional observations about the (non)-Turing simulability of BAPOs.

Critical strengths
  1. The paper directly answers an open question from a recent ICML paper related to chain of thought efficiency. The result is a nice improvement over the previously-known BAPO-CoT algorithm for reachability and uses some structures that could be helpful in other BAPO-CoT analyses.
Critical weaknesses
  1. The clarity and writing of the paper need substantial improvement. Terminology and notation are used throughout with no definition, and results are introduced without motivation. See comments below for examples and suggestions for improvement.
  2. The contribution of the paper is minimal. It closes one BAPO token complexity gap for reachability (previously known to be between Ω(m)\Omega(m) and O(n2)O(n^2)), showing Θ(m)\Theta(m) is tight. The other results of the paper (Prop 15, Thm 16, Thm 17, Thm 18, Thm 21) are small observations and corollaries. A full conference paper should make more substantive contributions. This result as it stands is better suited for a short arXiv report or perhaps a workshop, or could be one component in a more ambitious paper that more significantly advances our understanding of token complexity.
Questions for authors

I don't have questions that would affect my assessment. See comments below.

Comments

Most of the comments are around clarity. These are intended to be constructive and highlight points of confusion as a reader -- apologies if they come across as blunt

  • Why write Θ(m+1)\Theta(m+1) rather than Θ(m)\Theta(m)?
  • The last two sentences of the abstract are out of place and should be rewritten or removed
  • Line 42-44 could say something more helpful (or be cut)
  • Line 51 uses undefined notation (TC? c?)
  • In the introduction contributions, (i) and (ii) are lemmas rather than contributions, and (vii) is validation. When summarizing contributions, it would be more helpful to the reader to highlight only what provides new and sufficiently general takeaways; e.g., "c-BAPOs with finite alphabets and total-recursive suffix oracles can be simulated by Turing machines" is one example
  • BAPO-consistency is not defined (line 150); it should at least be said that any BAPO with a = 0 is a cBAPO (with reference)
  • In def 1, what is a "query state readable from yNy_N? what is VV? In Lemma 2, what is a "canonical score query"?
  • Section 4 should explain that the point of this lemma and the resulting primitives is that any (0, 1)-score-BAPO can compute one of those primitives in a single step (but not multiple simultaneously, right?)
  • Section 5 should start by motivating and explaining (20)
  • It's very hard to understand what is happening in Lemma 4 and what its purpose is. And what is N+(u)N^+(u)?
  • what does "resume below jj" mean in (22)? The purpose of these tokens isn't clear. Starting this section with an explanation of the strategy would be more useful. The explanation of decoding is also confusing
  • All of these issues make the lemmas in Section 7 very hard to follow.
  • An arXiv identifier should not be used as a citation (line 349).
  • Translating BAPO-CoT token complexity into transformer CoT score evaluations (Section 8.2) is very dubious as there isn't a formal BAPO-transformer equivalence.
  • Every section needs more motivation and explanation.
Reviewer_doaxOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

The paper studies the directed reachability problem in a recently proposed computational model cBAPO, which is an idealized model of information flow in attention based models. The authors claim to answer an open question raised in previous work about the computational complexity of directed reachability in cBAPO. They show that the problem can be solved by a model using at most 3m+23m+2 many reasoning tokens, where mm is the number of edges. Combined with existing lower bounds this gives a tight worst-case linear token complexity. This construction combines known techniques in DFS search with predecessor queries and storage techniques in the cBAPO architecture. The paper also presents applications of their result to regular-path reachability and obeservations about computability in cBAPO.

Critical strengths
  • The main contribution answers an explicitly stated question in previous work.
  • cBAPO as an abstraction of general attention based models and their investigation is in general an interesting line of research.
Critical weaknesses
  1. The paper provides hardly any motivation and intuition of the theoretical results. While the introduction states the main problems and describes the general ideas, the subsequent sections are simple chaining of definitions, lemmas and theorems. There is no main story line explaining the central ideas and how each component fits into the bigger picture of the overall proof goal.
  2. Due to the lack of explanation and motivation behind several lemmas and theorems, the distinction between techniques coming from previous work and new contributions was not made explicit. For examples the construction for Max and Rightmost seems to be already present in the previous work of Schnabel et al. (2025).
  3. The theoretical contribution of the paper is rather limited. While I acknowledge that the paper answers a previously raised question, the new contributions appear to be concentrated on a representation of standard DFS build from relatively elementary operations. The regular-path extension uses a standard product-graph construction. The computability observations are separate consequences of the model definition.
  4. Moreover, the roles and significance of Sections 10 and 11 are poorly explained. It is unclear how these results contribute to the general research of cBAPO.

To conclude, on the theoretical side alone, I would lean towards weak rejection. The construction is useful, but I find the contribution overall too weak. The contribution is largely based on the specific DFS representation, while several other results are direct extensions or elementary observations. The substantial exposition problems strengthen my recommendation to a clear rejection. The paper does not guide the reader through the construction or clearly separate existing techniques from new ideas.

Questions for authors

Please comment on the weaknesses.

Reviewer_g2cAOpenReview ↗
Rating
1(−1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2(−1)
Read review
Paper summary

The paper shows that graph reachability is solvable with O(m+1)O(m+1) tokens under the restrictive cBAPO-CoT model. The BAPO model serves as a theoretical framework for studying the reasoning ability of transformer models by isolating limitations on communicating relevant information between token positions even when local computational capacity is unrestricted.

The main insight is that the model can implement a deterministic state tracking system (using discovery D, check C, and resume S tokens along with a root and target record R) that uses the final generated token to define its query and combines at most one retrieved prefix token with the visible suffix so it works under every arbitrary split required by the BAPO model. The algorithm takes advantage of attention's ability to assign higher scores to edges with larger destination labels + use the query to restrict candidates to outgoing edges below the current threshold so the highest-scoring eligible token gives the correct next vertex to explore. Together with the existing Ω(m)\Omega(m) lower bound this gives a tight linear worst-case token complexity under the fixed bandwidth assumption.

Critical strengths
  • The main contribution resolves an open question in the BAPO framework improving the O(n2)O(n^2) construction of the cited paper to O(m)O(m) which is especially significant for sparse graphs.
  • The paper is technically rigorous, and the authors carefully distinguish its formal guarantees in the oracle setting from claims about learnability in practical transformer models.
Critical weaknesses
  • Scope:

    • My main concern is with the generality of the result. I am not sure the extent to which the result informs reasoning beyond the cBAPO setting.
      • For instance, the construction uses a huge vocabulary of about ∣Γn∣=5n2+2n+3|\Gamma_n|=5n^2+2n+3 (see Section 6.2) which gives about 20k+ unique tokens for a 64-node graph (much more than even one-hot encoding by the number of vertices of the graph).
  • Experiments:

    • I wish the paper did more exhaustive experiments (even with tiny graphs) to justify how a guided trained model can perform better than vanilla model to justify the significance of the findings.

Minor Comments

  • The contributions section is too technical to make the main contributions clear at a glance. I suggest combining it with the main results discussion and presenting the key techniques in a separate section.
Questions for authors
  • In the zero-prefix-bandwidth setting studied here, is requiring correctness across all prefix–suffix splits not equivalent to requiring correctness only at the split immediately before the last token?

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of the revision

We thank the reviewers for their detailed feedback. The revision preserves the central 3m+23m+2 reachability result and incorporates the following changes.

1. A clearer construction and attribution (Sections 2–6). We reorganized the proof around the information available at the last-token cut, a worked trace, and the DFS invariant. The algorithm now explicitly uses one priority query per step: edge versus parent record, or target versus visitedness evidence. We define the query decoder, semantic ties, continuation thresholds, and resource quantifiers before use. Max, Rightmost, and the prefix/suffix maximum merge are explicitly credited to Schnabel et al. (2025), Appendix C.1, Proposition 2. The contribution is the immutable continuation-record representation under the joint bandwidth, alphabet, and token constraints.

2. Weaker assumptions and sharper accounting (Sections 5–6; Appendices A–C). The tagged construction now uses one machine per fixed nn for every mm: initialization retrieves position N−1N-1, and edge tags identify input edges. Parent-code priorities replace position-dependent record scores, giving O(log⁡n)O(\log n)-bit priorities independent of trace length. We prove a positive perturbation tolerance for hard selection with clipping, grid decoding, and zero filtering, assuming exact token fields, positions, and transitions. For source-reachable vertices RR and the number MRM_R of distinct edges with source in RR,

T≤1+2MR+∣R∣≤3MR+2,T\le 1+2M_R+|R|\le 3M_R+2,

with equality in the first bound on NO instances. We also completed the total transition rules and boundary cases, including current-token records, empty paths, and product-state encodings.

3. Only three additional vocabulary symbols (Section 7; Appendix D). A second construction uses the input alphabet plus YES, NO, and HALT:

∣Γn∣=n2+n+3,T≤4m+2.|\Gamma_n|=n^2+n+3,\qquad T\le4m+2.

At n=64n=64, this reduces the inventory from 20,611 to 4,163 symbols. Generated-position parity supplies token types, and the earliest incoming check stores each nonroot parent. This variant fixes (n,m)(n,m) and trades a constant-factor increase in trace length for fewer symbols. The residual quadratic alphabet comes from the edge-as-one-symbol input encoding.

4. Split equivalence and broader consequences (Sections 4, 8–9; Appendices B, G). We prove that, at zero prefix bandwidth, last-token-cut and all-cut realizability are equivalent for every fixed attention bandwidth bb, preserving the alphabet and trace. All-cut correctness uses an explicit conversion that merges prefix top-bb candidates with visible candidates.

The implicit-graph transfer theorem gives 3∣Eimp∣+23|E_{\mathrm{imp}}|+2 tokens under explicit local-query, initialization, goal-test, and alphabet conditions, and 3cm+23cm+2 when each input relation token represents at most cc edges. For regular-path queries, we strengthen the lower bound to every fixed DFA accepting an infinite language, with fixed bandwidth and the worst case taken over nn. We characterize (0,0)(0,0) maps on nonempty contexts by length and final token. We also give a Turing simulation for each fixed, finite-alphabet, split-consistent machine with a total-recursive suffix oracle.

5. Three-seed neural controls (Section 10; Appendix I). Width-48 controls compare answer-only, tagged-DFS, and retrieval-guided training with shared endpoint representations. Evaluation covers all 792 queries from 88 held-out three-vertex graphs and 2,048 queries from 128 four-vertex graphs. Graphs are split by isomorphism class. Each seed receives 2,400 updates and 76,800 matched graph exposures; target-token counts and compute are not matched.

On four vertices, retrieval supervision improves hard-inference answer accuracy from 93.85±0.40%93.85\pm0.40\% to 97.38±0.44%97.38\pm0.44\% (mean ±\pm sample SD), improving all three seeds. Soft inference on the same guided checkpoints gives 97.44±0.28%97.44\pm0.28\%. Full-attention trace and answer-only controls reach 96.42% and 95.93%, respectively. Guided hard retrieval achieves 100% answer and exact-trace accuracy under paired three-vertex order reversal, duplicate injection, and relabeling. Retrieval/transition diagnostics and first-YES certificate checks are reported separately. The original single-seed study is retained in the appendices.

6. Verification and implementation scope. Independent exact-arithmetic verifiers check 14,236 tagged-construction inputs and 10,236 compact-construction inputs across all splits and maximizing ties. A separate run checks all 1,048,576 four-vertex graph/query pairs at the last cut against transitive closure. All checks passed; the source package includes the verifiers and results. Section 11 now states the score-evaluation count for a specified symbolic implementation; transformer realization and latency require additional implementation assumptions.

The revised main text is ten pages, with complete proofs and experimental details in the appendices.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.