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

A recent ICML paper asks whether directed reachability in the self-consistent bounded-attention prefix-oracle model can be solved with $O(m+n)$ chain-of-thought tokens, rather than the known $O(n^2)$ construction. We give a sparse-sensitive resolution: for every $n$-vertex, $m$-edge input, including arbitrary edge order, self-loops, and repeated tokens, a $(0,1)$-cBAPO-CoT decides reachability using at most $3m+2$ nonhalt tokens and an alphabet of size $\Theta (|\Sigma |)$. Together with the existing linear lower bound under fixed-bandwidth, worst-case quantifiers, this gives tight $\Theta (m+1)$ 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 $3m+2$-token simple-path certificate and a $3|Q|m+2$ 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.