- 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 CoT steps, but requires at least . The authors close this gap, producing a BAPO-CoT that solves reachability in steps, showing the previously known lower bound is tight. Additionally, the authors provide additional observations about the (non)-Turing simulability of BAPOs.
Critical strengths
- 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
- 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.
- The contribution of the paper is minimal. It closes one BAPO token complexity gap for reachability (previously known to be between and ), showing 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 rather than ?
- 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 ? what is ? 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 ?
- what does "resume below " 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.
Summary of the revision
We thank the reviewers for their detailed feedback. The revision preserves the central 3m+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 n for every m: initialization retrieves position N−1, and edge tags identify input edges. Parent-code priorities replace position-dependent record scores, giving O(logn)-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 R and the number MR of distinct edges with source in R,
T≤1+2MR+∣R∣≤3MR+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.
At n=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) 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 b, preserving the alphabet and trace. All-cut correctness uses an explicit conversion that merges prefix top-b candidates with visible candidates.
The implicit-graph transfer theorem gives 3∣Eimp∣+2 tokens under explicit local-query, initialization, goal-test, and alphabet conditions, and 3cm+2 when each input relation token represents at most c 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 n. We characterize (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% to 97.38±0.44% (mean ± sample SD), improving all three seeds. Soft inference on the same guided checkpoints gives 97.44±0.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.