Chain-of-Thought: Recovering P at Decode Time

📍 Where we are: Part V · Neural Depth: Chain-of-Thought and RL — Chapter 13. The Transformer Depth Ceiling priced the single forward pass at uniform TC⁰ and reserved one exit in the theorem's quietest clause, "no intermediate tokens generated and fed back"; this chapter opens that door and measures what walks through it.

Chain-of-thought (CoT) is usually filed under prompt engineering: add a step-by-step nudge to the prompt and the benchmark number goes up. This chapter files it where the theory says it belongs, under architecture. A transformer that decodes intermediate tokens and attends to them is a different machine from the same transformer answering in one pass, because every generated token is one more sequential step that the fixed layer stack could not perform on its own. The exchange rate between steps and power is now a theorem family: the decode budget climbs a ladder of complexity classes, and at a polynomial budget the machine characterizes exactly P, the class the previous chapter placed beyond any single pass unless the conjectured hierarchy collapses (TC⁰ = P). The companion module cot_steps.py demonstrates the mechanism with this volume's discipline, on the same task and the same training band as the previous chapter's cliffs: a depth-1 step network, trained only on single composition moves, is unrolled at evaluation and walks off the fixed-depth model's cliff without stumbling. Then the chapter pays the two bills that the recovered depth runs up, serial time and fragility, both printed as committed output, because the second bill is the opening argument of the next chapter's verifiers.

The simple version

Imagine multiplying two six-digit numbers entirely in your head, versus with a pencil and paper. Your head is the same head in both cases; the paper does not make any single mental step smarter. What the paper changes is the number of steps you can chain: you write down each intermediate result, read it back, and take the next small step, for as long as the problem needs. That is chain-of-thought. The model is the head, the decoded tokens are the paper, and the loop of writing and reading back is what turns a shallow thinker into a long computation. The paper charges twice, though. Every written line costs time that no amount of extra hands can parallelize away, and one mis-copied digit silently poisons every line after it.

What this chapter covers

• The loop, decoded mechanically: autoregressive decoding feeds outputs back as inputs, so the unrolled computation graph has depth proportional to the layer count times the number of generated tokens; the ceiling theorems of the previous chapter bound only the no-decoding regime.
• The ladder, stated with house discipline: each decode-step budget mapped to a complexity class, every symbol decoded, attributions given, and the load-bearing caveats quoted, including the one this chapter's experiment exists to probe: expressiveness is not learnability.
• The isolation experiment: a step model trained only on single moves (state, token → next state), never on a long instance, then unrolled n times at evaluation, so that depth can come from exactly one place, the loop.
• The committed head-to-head: accuracy versus length for n = 2 through 32, the unrolled step model beside the previous chapter's best fixed-depth model, with the asserts that guard the reading.
• The serial bill: the ledger column that reads exactly n, why the loop admits no parallel discount, and what that means for deployments that already own the earlier chapters' parallel lanes.
• The fragility exhibit: one corrupted intermediate state injected at position k, the committed table showing end-task accuracy 0.000 at every k, and the two-line group-theory proof of why a wrong thought never heals on this task.
• From scratchpads to the frontier: the empirical line that found the loop before the theory priced it, and the honest note that eliciting a chain does not certify its steps.

The door: decoding is a loop, and a loop is depth

Before any theorem, the mechanism, because it is purely mechanical. A transformer generates text autoregressively: it runs a full forward pass over everything written so far, emits one token, appends that token to the input, and runs again. Write $L$ for the number of layers (an architectural constant, as in the previous chapter) and $T$ for the number of tokens the model generates before its final answer. A single forward pass is a computation of depth proportional to $L$: each layer performs a bounded number of dependent stages, so the longest chain of operations in which each needs its predecessor's output has length $cL$ for some constant $c$ that counts stages per layer. Now unroll the generation. Pass number $t$ reads the token emitted by pass number $t-1$; that token does not exist until pass $t-1$ has run all the way to its output layer and sampled. So the $T$ passes are totally ordered, no two can overlap, and the longest dependent chain in the unrolled computation graph is the chain through all of them in sequence: $T$ passes times $cL$ stages per pass, depth $\Theta(L \cdot T)$, where $\Theta$ means bounded above and below by constant multiples (its one-sided cousin $O$, used below, means bounded above by a constant multiple only). With $L$ fixed, the depth of the whole computation grows linearly in $T$. The number of generated tokens is a depth budget, spent at decode time, that the architecture's frozen layer count never granted.

This single observation reorganizes the previous chapter. The ceiling theorem there bounded a transformer "run as a single forward pass that outputs its answer directly," and every word of that clause was load-bearing: the TC⁰ bound (TC⁰ is the previous chapter's class of constant-depth threshold circuits) is a bound on the $T = 0$ machine [1]. A model that writes intermediate tokens and reads them back is a shallow stack looped $T$ times, which is to say a deep computation assembled at inference time, and no fixed-depth circuit argument applies to it as a whole. The loop also explains where the intermediate state lives. A fixed-depth pass must carry all partial results in its activations, which the log-precision idealization deliberately starves; the decode loop externalizes the state into tokens, discrete symbols of unbounded count, exactly as Volume 1's forward chainer externalized its state into the growing fact set. What remains is to price the exchange, and that is the ladder.

A shallow stack looped n times is a deep computation: the decode budget climbs the complexity ladder, and the same task that broke the fixed-depth model at n = 5 holds at 1.000 out to n = 32 when the depth lives in the loop. Original diagram by the authors, created with AI assistance.

The ladder: what a step budget buys

The theorem family prices decode steps the way the previous chapter priced layers. Fix the same idealized machine as before, a transformer with a constant number of layers, polynomially bounded size, and log-precision arithmetic, but now allow it $t(n)$ decode steps on inputs of length $n$: it may generate $t(n)$ intermediate tokens, each fed back into the input, before committing to an answer. Here $n$ is the input length in tokens and $t(\cdot)$ is a budget function fixed in advance, the ladder's single dial. The results, stated with every rung attributed [1]:

decode-step budget $t(n)$	power of the machine	direction of the claim
$0$ (single pass)	uniform TC⁰ only	upper bound; the previous chapter's ceiling
$O(1)$ (constant)	still uniform TC⁰	upper bound: finitely many extra passes stack to constant depth
$O(\log n)$	contained in $\mathsf{L}$ (logspace)	upper bound: few steps buy little
$\Theta(n)$ (linear)	every regular language is reachable	lower bound: $n$ steps run any finite automaton
$\mathrm{poly}(n)$	exactly P	both bounds meet: the characterization

Decode each row. Uniform TC⁰ is the previous chapter's constant-depth threshold-circuit class; a constant number of extra passes multiplies the unrolled depth by a constant, and a constant times a constant is a constant, so the ceiling does not move. $\mathsf{L}$, logspace, is the class of problems decidable by an algorithm that reads its input read-only and uses only $O(\log n)$ bits of working memory; the upper bound says that a logarithmic token budget, each token drawn from a fixed vocabulary and hence worth $O(1)$ symbols of state (log-precision internals contribute $O(\log n)$ bits per step), can be replayed by a logspace simulator, so the machine stays inside a class still believed far below P. Regular languages are the languages recognized by deterministic finite automata (DFAs), machines with a fixed finite state set that read one symbol at a time; the lower bound is constructive, a transformer can emit its current automaton state as each decoded token and apply the transition function in one shallow pass, which is exactly the shape of this chapter's experiment. And the top rung is the title of this chapter: with a polynomial budget the idealized machine decides exactly the class P of polynomial-time problems, upper bound because each pass is polynomial work and there are polynomially many passes, lower bound because polynomially many decoded tokens can transcribe a polynomial-time Turing machine's tape, step by step, into the context [1]. The closure waves of Volume 1, the EL completion of Volume 2, the P-complete closures that the previous chapter placed above any fixed stack unless P collapses to NC, its parallel subclass: all of it returns to reach, provided the machine is allowed to think out loud for polynomially many tokens.

A second result sharpens the ladder at the rungs practice cares about. For arithmetic-expression evaluation and linear-equation solving, both posed over a finite field of prime modulus, and for context-free-grammar membership testing (a problem dynamic programming solves), bounded-depth log-precision transformers cannot produce the answer in a single pass unless TC⁰ equals NC¹, where NC¹ is the class of problems solvable by polynomial-size circuits of bounded fan-in gates whose depth may grow like $\log n$, the previous chapter's next rung, with the inclusion of TC⁰ in NC¹ conjectured strict and never proved; yet a fixed-size transformer that writes out a polynomial-length derivation, filling the dynamic-programming table cell by cell in its own decoded text, solves those same problems, and the same constructive theorem covers classic dynamic-programming recurrences such as longest increasing subsequence and edit distance [2]. The separation is conditional exactly where the previous chapter said such separations are, and the constructive half is unconditional: the weights exist, and the chain is the computation.

Three caveats travel with the ladder, and the house rule is to state them where the theorems are stated, not in a footnote. First, the poly-step qualifier: "exactly P" is a statement about polynomial budgets; nothing about the constants is claimed, and a budget theorem does not say which problems need how many steps (the unsolved part returns to this). Second, the idealizations: the results assume log-precision arithmetic and idealized attention, the same assumptions the ceiling theorem needed, so they bound an abstraction of the deployed object; the proofs are genuinely beyond this volume, and nothing the companion runs should be read as proving any rung. Third, and load-bearing for everything below: expressiveness is not learnability. Every rung asserts that weights exist; no rung says gradient descent finds them from any particular supervision. The previous chapter watched that gap from one side, a model failing inside a band its function class provably covers. This chapter's experiment is designed to stand on the gap's other side: choose a setting where the step function is demonstrably learnable, and then show that the loop, and only the loop, supplies the depth.

Learn one move, unroll n: the isolation experiment

The companion's design answers the third caveat at toy scale, and its logic deserves to be stated before its code. If a model were trained end-to-end on long chains, its successes would confound two resources, what the weights learned and what the loop contributes. So the module trains a step model on single moves only, never showing it an instance longer than one move, and manufactures all depth at evaluation time by unrolling. The task is the previous chapter's iterated $S_3$ composition, unchanged ($S_3$ is the group of all $3! = 3 \cdot 2 \cdot 1 = 6$ permutations of three letters, so a state is always one of six elements), with its generators and labels imported from depth_ceiling.py rather than retyped (cot_steps.py, lines 67–76): an instance is a sequence of $n$ non-identity permutations $g_1, \ldots, g_n$ of three letters, the answer is the product $p_n$ under the left fold $p_0 = e$, $p_j = p_{j-1} \circ g_j$, where $e$ is the identity permutation and $\circ$ is composition with the right factor acting first. The fold is the depth carrier: computing $p_n$ this way is $n$ dependent multiplications.

The supervision is scratchpad-style, in the precise sense that the training signal is the trace of the intermediate computation rather than the final answer [3]: every training trajectory from the previous chapter's short band ($n = 2$ through $6$) is unfolded into its individual steps, and the model sees only pairs of the form (current state, next token) → next state (cot_steps.py, lines 108–130):

def harvest_steps(rng: np.random.Generator) -> tuple[np.ndarray, np.ndarray]:
    """Single-step supervision from the SAME short band depth_ceiling trains
    on (n = 2..6), decomposed scratchpad-style (Nye et al. 2021): each
    trajectory p_0 = e, p_j = p_{j-1} ∘ g_j is unfolded into its steps

        x = [one-hot(p_{j-1}) ; one-hot(g_j)]  →  y = p_j ,

    so the net only ever sees ONE composition at a time.  Returns (X, y)
    with X of shape (Σ_n STEP_PER_LEN·n, 12) and y the new-state ids."""
    Xs, ys = [], []
    for n in TRAIN_LENGTHS:
        elems = sample_s3(n, STEP_PER_LEN, rng)
        # p_0 = e (the identity, element id 0) for every trajectory.
        state = np.zeros(len(elems), dtype=np.int64)
        for j in range(n):
            g = elems[:, j]
            # p_j = p_{j-1} ∘ g_j  via the Cayley table.
            nxt = MUL[state, g]
            Xs.append(np.concatenate([one_hot(state, 6), one_hot(g, 6)],
                                     axis=1))
            ys.append(nxt)
            state = nxt
    return np.vstack(Xs), np.concatenate(ys)

The step model itself is deliberately the weakest machine in this volume: a multilayer perceptron (MLP) with one hidden layer of width 24 using the tanh (hyperbolic-tangent) activation, input dimension 12 (two 6-way one-hot vectors for the state and the token, a one-hot vector being 1 at exactly the position of the encoded id and 0 everywhere else), output dimension 6, trained by the previous chapter's engine, the same hand-derived backpropagation that was certified against central finite differences there, with stochastic gradient descent (SGD), momentum, and fixed seeds (cot_steps.py, lines 133–141; the engine is depth_ceiling.py, lines 227–248). Depth 1 is the point. Whatever this network can compute in one pass is a bounded, constant-depth function; if unrolling it solves depth-$n$ problems, the depth demonstrably came from the loop.

There is also a clean symbolic reading of what the step model must learn, and it connects the experiment to the ladder's linear rung. The set of words over $S_3$ whose product equals a given element is a regular language: the 6-state DFA whose states are the group elements and whose transition function is $\delta(p, g) = p \circ g$ decides it, and that transition function is precisely the single move the step model is trained on. Unrolling the step model is running the automaton, one decoded token per input symbol, which is the constructive content of the ladder's $\Theta(n)$ rung at miniature scale [1]. Because the automaton is finite, learnability is not in question here by design: the step function has exactly 30 reachable input pairs (6 states times 5 non-identity tokens), and the module checks the learned function against the ground-truth Cayley table (the group's complete multiplication table, one entry $p \circ g$ for every state $p$ and token $g$) on every one of them (cot_steps.py, lines 144–153), with the committed result printed before any unrolling is allowed to mean anything:

[2] the step model — depth-bounded per step, trained on steps only
    architecture: 12 → 24 (tanh) → 6; ONE hidden layer (depth 1)
    supervision : 10000 single steps (p_(j-1), g_j) → p_j, harvested from
                  trajectories of the SAME short band n = 2..6 (scratchpad-style)
    learned transition table vs ground-truth Cayley table: 1.000 on all 30
    reachable (state, non-identity token) pairs — the automaton, learned

The harness promotes that line to a precondition: assert table_acc == 1.0 (cot_steps.py, lines 249–251). The unrolling itself is the chapter's whole mechanism (cot_steps.py, lines 158–184; the excerpt below omits the corruption arguments, deferred to the fragility section):

    count, n = elems.shape
    state = np.zeros(count, dtype=np.int64)
    steps_used = 0
    for j in range(1, n + 1):
        X = np.concatenate([one_hot(state, 6), one_hot(elems[:, j - 1], 6)],
                           axis=1)
        state = forward(params, X)[-1].argmax(axis=1)
        steps_used += 1

Read the argmax line as the decoding step. The network's continuous logits (its raw output scores, one real number per class) are collapsed to a discrete class, the new state, and that symbol, not the activations behind it, is re-encoded as one-hot input for the next pass. This is the chain-of-thought reading made literal: the intermediate result is written down as a token and read back, exactly a scratchpad entry, and nothing else crosses between passes. The state lives on the paper, not in the network.

The head-to-head: the loop carries the depth

The opponent is the previous chapter's strongest fixed-depth model on this task, the depth-3 MLP, retrained by the identical protocol (same generator seeds, same hyperparameters, same training band $n = 2$ through $6$; cot_steps.py, lines 189–198), so the model losing this comparison is the model behind the committed cliff tables, not a strawman. Both contestants are evaluated on shared fresh instances, 400 per length, drawn from one seeded stream (cot_steps.py, lines 253–265). The committed table is the chapter's spine:

[3] head-to-head on shared fresh instances, n = 2..32 (400 per length)
    fixed depth-3 = depth_ceiling's best S_3 model, retrained on its exact
    protocol; '—' marks lengths its 16-slot input window cannot ingest
        n   fixed depth-3   unrolled step   serial rounds (fixed/step)
        2       1.000           1.000            3 /  2
        3       1.000           1.000            3 /  3
        4       0.990           1.000            3 /  4
        5       0.777           1.000            3 /  5   ← fixed-depth cliff
        6       0.485           1.000            3 /  6   ← training horizon
        7       0.085           1.000            3 /  7
        8       0.133           1.000            3 /  8
        9       0.175           1.000            3 /  9
       10       0.177           1.000            3 / 10
       11       0.165           1.000            3 / 11
       12       0.165           1.000            3 / 12
       13       0.152           1.000            3 / 13
       14       0.177           1.000            3 / 14
       15       0.175           1.000            3 / 15
       16       0.185           1.000            3 / 16
       17         —             1.000            3 / 17   ← past the fixed net's input window
       18         —             1.000            3 / 18

The rows continue unchanged to $n = 32$: the unrolled step model reads 1.000 at every length while the fixed model has no column at all, because an instance longer than 16 elements does not fit its input encoding. The fixed model's rows reproduce the previous chapter's story on fresh instances, mastery through $n = 4$, the cliff at $n = 5$, and a tail (mean accuracy over $n = 7$ through $16$) of 0.159 against six-way chance $1/6 \approx 0.167$. The harness guards all of this as code rather than prose: the fixed model must be strong at $n = 2$, must cliff at or before the training horizon, and must collapse to chance beyond it, and then the two claims that are this chapter's thesis (cot_steps.py, lines 278–283):

    min_step = min(step_acc.values())
    assert min_step >= 0.95, \
        f"unrolled step model fell below 0.95 (min {min_step:.3f})"
    for n in range(TRAIN_MAX + 2, SLOTS + 1):  # n = 8..16: horizon+2 .. window end
        assert step_acc[n] - fixed_acc[n] >= 0.5, \
            f"step model does not dominate the fixed net at n={n}"

The contract is a floor of 0.95 at every length 2 through 32 and a dominance margin of at least 0.5 at every measurable length from two past the training horizon ($n = 8$ through $16$); the committed run clears both with room, step_min_acc=1.000 in the summary line. One paragraph of reading, because the table earns it. The fixed model had to represent the entire $n$-fold composition inside three rounds of combination, a function of the whole input whose required depth grows past any constant; gradient descent from short instances found a solution for the short band and nothing beyond it, exactly the mechanism the previous chapter diagnosed. The step model was never asked for any such function. Each of its passes solves a bounded-depth, fixed-size problem, one Cayley-table lookup, that its training distribution covered exhaustively (all 30 reachable pairs, learned to exactness), so no pass is ever out of distribution no matter how long the instance grows. The composition happens in the state, the decoded token passed from step to step, not in the weights. Length generalization is free because length was never a property the weights had to encode; the loop, an architectural act at evaluation time, carries all of it. That is the ladder's lesson in one table: the same parameters, spent per-step instead of per-instance, moved the machine to a different rung.

The serial bill

Now the first of the two prices, printed in the table's last column. The unrolled model's serial rounds entry reads exactly $n$ at length $n$: the module counts every forward pass and the harness asserts the count equals the instance length, with no discount (cot_steps.py, lines 285–287). The committed ledger states both sides of the trade:

[4] the cost ledger — what the recovered depth costs
    fixed net : 3 serial rounds at EVERY length (parallel across the input),
                but chance beyond its cliff (mean acc n=7..16: 0.159, chance 0.167)
    step net  : accuracy ≥ 1.000 at every n = 2..32, but the ledger column is
                exactly n — Θ(n) serial time, NO parallel speedup: the
                loop that buys the depth is the serial cost.  That is the
                CoT trade [Merrill & Sabharwal, ICLR 2024].

The reason there is no parallel discount is the same dependence argument that made the loop deep in the first place, and it is worth spelling out because it is the work-depth trilemma reappearing in its third costume. Step $j$ cannot begin until step $j-1$'s decoded state exists; the $n$ steps form a single dependent chain, so the span of the computation is $\Theta(n)$ regardless of how many processors are available. Wall-clock decode latency is proportional to $n$ (the module commits the step count rather than seconds, because seconds are machine facts and step counts are protocol facts, but each round is one forward pass, so the proportionality is exact by construction). Depth was the one resource the trilemma said cannot be bought with parallel hardware, and chain-of-thought does not refute that law; it obeys it, paying the depth floor in serial time, one token per unit. The deployment consequence follows immediately. A fixed-depth pass answers every length in constant rounds and is wrong past its cliff; the loop is right everywhere and is paid by the token. Where the reasoning fragment is shallow or parallelizable, the earlier chapters' lanes, materialization and rewriting, the squaring kernel, batched fixpoints, deliver the answer without serial decoding, and a throughput-critical system should buy them. The decode loop is the general-purpose lane, the only one that reaches P, and the meter runs on every step of it.

One wrong thought never heals

The second price is the chapter's honest centerpiece, and on this task it can be derived before it is measured. Suppose the chain is corrupted once: after step $k$ the state is not the true prefix product $p_k$ but some other element $q \ne p_k$, and decoding then continues correctly. Write $s = g_{k+1} \circ \cdots \circ g_n$ for the product of the remaining tokens, folded in the same order as everything else. By associativity of composition, the true answer factors through the prefix: $p_n = (p_k \circ g_{k+1}) \circ \cdots \circ g_n = p_k \circ s$. The corrupted run, executing the same correct steps from the wrong state, ends at $q \circ s$. Could the two coincide? Compose each with $s^{-1}$, the inverse permutation of $s$, on the right. If $q \circ s = p_k \circ s$ then $(q \circ s) \circ s^{-1} = (p_k \circ s) \circ s^{-1}$; regrouping by associativity, $q \circ (s \circ s^{-1}) = p_k \circ (s \circ s^{-1})$, so $q \circ e = p_k \circ e$, so $q = p_k$, contradicting $q \ne p_k$. The map "compose with $s$ on the right" is therefore injective: distinct inputs go to distinct outputs. And an injective map from the 6-element group to itself sends its 6 elements to 6 distinct outputs, which is all 6 of them, so the map is a bijection, a perfect pairing of the group with itself. A wrong state at step $k$ therefore maps to a wrong answer at step $n$ with probability exactly 1, whatever $k$ and whatever the corruption. The error does not decay along the chain; it rides it.

The module stages exactly this experiment. At a designated position it replaces the decoded state by a uniformly random wrong element (adding a uniform offset from 1 to 5 to the class id, modulo 6, which hits each of the other five ids equally; cot_steps.py, lines 167–183) and decodes onward. Because the learned step function matches the Cayley table on all 30 reachable pairs, the remaining steps really are exact right-multiplications and the derivation applies to the trained model, not just the ideal one. The committed exhibit, at length $n = 16$:

[5] wrong-step propagation — the fragility of serial reasoning
    inject ONE corrupted intermediate state (uniform wrong element) at n = 16:
    corruption position sweep (seed fixed): end-task accuracy after corrupting
      after step:      2      5      8     11     14
      accuracy  :  0.000  0.000  0.000  0.000  0.000
    over seeds (corrupt after step 8; clean = same instances, no corruption):
      seed   clean acc   error persists to the end
         0     1.000              1.000
         1     1.000              1.000
         2     1.000              1.000
         3     1.000              1.000
         4     1.000              1.000
      mean persistence 1.000: right-multiplying by the remaining
      suffix is a bijection of S_3, so one wrong thought NEVER heals —
      a serial chain is only as sound as its weakest verified step

Read the two tables against each other. The position sweep says corruption is equally fatal everywhere: early, middle, or late, end-task accuracy is 0.000, because the bijection argument is position-independent. The per-seed table separates the two quantities that a sloppier experiment would blur: the same instances decode to 1.000 clean, and the corrupted runs end wrong with persistence 1.000, the fraction of corrupted chains whose error survives to the final answer. The harness demands persistence at least 0.95 in every seed alongside clean accuracy at least 0.95 (cot_steps.py, lines 311–314), and the committed run saturates both.

Now the contrast that names the design consequence. The fixed-depth model past its cliff is also wrong, but diffusely: each instance independently lands near chance (the 0.159 tail), errors do not propagate because there is no chain for them to ride, and being wrong on one instance says nothing about the next. The serial machine inverts that risk profile. Its failure is not diffuse but concentrated: every single step is a single point of failure for the entire computation. The arithmetic is one line: if the steps of an $n$-step chain err independently with probability $\varepsilon$, each step is correct with probability $1 - \varepsilon$, so by independence the whole chain runs error-free with probability $(1 - \varepsilon) \times \cdots \times (1 - \varepsilon) = (1 - \varepsilon)^n$, a quantity that decays exponentially in exactly the $n$ the loop was purchased to reach. That clean-chain probability is a floor on end-task accuracy rather than a cap, because two errors can happen to cancel; what the bijection argument adds is that cancellation is the only rescue, since any single error that survives to the end is fatal with probability 1. Our miniature sits at the benign corner, $\varepsilon = 0$ on every reachable pair, which is why the injection had to be artificial; a deployed model reasoning in free-form text has no 30-entry table to saturate and no exactness certificate, so its $\varepsilon$ is unknown and its chains are long. Serial reasoning concentrates risk in every intermediate step, and nothing inside the loop checks the paper. That sentence is the opening argument of the next chapter's verifiers, and it is why this volume refuses to treat chain-of-thought as a free lunch: the loop buys depth, and it sells attack surface.

From scratchpads to the frontier

The empirical line found the loop before the theory priced it, and one paragraph of history keeps the credit straight. Scratchpad training showed that a fixed language model, taught to emit its intermediate computation as text before its answer, could execute multi-step arithmetic and program traces that the same model failed at directly; the supervision was the trace itself, which is exactly the shape of this chapter's step harvesting [3]. Chain-of-thought prompting then showed that at sufficient scale the traces need not be trained in at all: a handful of worked examples in the prompt elicits step-by-step decoding, and multi-step reasoning benchmarks jump, an emergent gain that made the loop famous [4]. The theory arrived afterward and explained both retrospectively: the single-pass machine is capped at uniform TC⁰ by the parallelism tradeoff [5], so tasks above that rung must fail without steps, and the decode budget is precisely the resource whose absence the cap prices, so adding steps is not a trick but a class change [1]. The honesty note this volume owes: prompting elicits the loop; it does not certify the steps. Our miniature's decoded state is the computation by construction, verified against the Cayley table at every reachable pair. A free-form rationale enjoys no such identity: the loop can decode plausible text that is not the computation producing the answer, and Part I's faithfulness chapter measured exactly that gap between stated and effective reasoning. The theorems bound what chains can compute; they say nothing about whether a particular chain did.

The unsolved part

The ladder's rungs are clean; the ground between them is mostly unmapped, in three directions this chapter's own numbers make concrete. First, step efficiency. The characterization at the top rung is polynomial, and polynomial is a loose word: for a given problem, the minimal decode budget that suffices is generally unknown, and the known rungs are far apart. Our task ran the automaton in $n$ steps, but the group is associative, so a balanced regrouping computes the product in $O(\log n)$ dependent multiplications; whether a decoder can be trained to emit such a schedule, and for which problems logarithmic or sublinear budgets suffice at all, sits between the $O(\log n)$ and $\Theta(n)$ rungs with few tight answers on either side. Second, adaptive budgets. Everything here fixed $t(n)$ in advance; a reasoning system should spend steps where the instance is hard and exit early where it is easy, which is the anytime question this volume keeps meeting, now at decode time, and principled learned early-exit for chains, with guarantees about what the saved steps could not have changed, does not yet exist. Third, the gap the experiment was designed around rather than through: which step functions are learnable from which supervision. Our step function had 30 reachable inputs and we supervised all of them; a deployed model's implicit step function has no such table, its trace format is discovered rather than fixed, and the theory that would predict when trace supervision of the scratchpad kind yields an exact, composable step, versus a step whose small errors compound, collapsing the clean-chain probability at the $(1-\varepsilon)^n$ rate the fragility section derived, is open ground between expressiveness and learning dynamics, the same two sciences whose missing bridge closed the previous chapter.

Why it matters

For the series, this chapter closes a loop that opened in Volume 1. The forward chainer computed its closure by iterating a shallow rule-application step over a growing fact set; the EL completion of Volume 2 and the fixpoint kernels of this volume have the same shape, a bounded step inside an unbounded loop, with the state living in an external, symbolic store. Chain-of-thought is the neural architecture rediscovering that shape at decode time: the token stream is the fact set, the forward pass is the rule application, and the ladder theorem is the license that says the shape recovers everything polynomial. That makes the design question for neuro-symbolic systems sharper than "should the model reason step by step." The questions this chapter equips the reader to ask of any CoT claim are quantitative: which rung does the task need, what serial bill does the budget imply at deployment, and what is the per-step error rate $\varepsilon$ that the $(1-\varepsilon)^n$ chain-survival probability will compound. And it hands the next chapter its problem statement in measured form: the loop's every step is an unverified single point of failure, our committed exhibit shows a single wrong thought is fatal with probability 1 on a task where steps are checkable, and the frontier's answer, reward signals and verifier gates wrapped around the decode loop, is where Part V goes next. For the reader's own research, the isolation design is the reusable artifact: when a mechanism and its learned approximation are entangled, find the setting where the learnable part is provably saturated, and let the mechanism carry the rest alone.

Key terms

• Autoregressive decoding: generation by repeated forward passes, each emitting one token that is appended to the input of the next pass; the loop that makes a fixed stack a deep computation.
• Chain of thought (CoT): intermediate tokens decoded before the answer; architecturally, a decode-time depth budget of one sequential step per generated token.
• Decode-step budget $t(n)$: the number of intermediate tokens allowed on inputs of length $n$; the ladder's dial, with $O(1)$ buying nothing beyond TC⁰, $O(\log n)$ staying inside logspace, $\Theta(n)$ reaching every regular language, and $\mathrm{poly}(n)$ characterizing exactly P.
• Step model: the companion's depth-1 network mapping (state, token) to the next state, trained on single moves only; the learned transition function of the task's 6-state automaton, exact on all 30 reachable pairs.
• Unrolling: applying the step model $n$ times at evaluation, re-encoding each argmax output as the next input; the loop that carries the depth, at exactly $n$ serial rounds.
• Serial rounds: the committed cost ledger's entry, asserted equal to the instance length; the work-depth trilemma's depth floor paid in decode time, with no parallel discount.
• Persistence: the fraction of corrupted chains whose error survives to the final answer; committed at 1.000, matching the bijection argument that right-composition with the remaining suffix never maps a wrong state to the right answer.
• Expressiveness versus learnability: the ladder asserts weights exist; it does not say training finds them, which is why the companion saturates the learnable part (the 30-pair step table) before crediting the loop with the depth.

Where this leads

The loop bought back P and paid in the two currencies this chapter printed: time, which is a budget, and fragility, which is a liability with no counterparty inside the model. Every step of a decoded chain is an unverified claim, and the committed exhibit showed what one false claim costs. The next chapter, Reinforcement Learning and Verifier-Gated Reasoning, builds the counterparty: reward signals that train the loop toward chains that survive checking, and verifier gates that refuse to let a wrong thought ride to the end, the symbolic engines of Volumes 1 and 2 returning as the checking machinery for exactly the serial computations this chapter made possible.

---

Companion code: examples/frontier/cot_steps.py trains the depth-1 step model on single-move supervision harvested from the short band, verifies the learned transition function against the Cayley table on all 30 reachable pairs, retrains the previous chapter's depth-3 opponent on its exact protocol, runs the shared head-to-head over n = 2..32, prints the serial-rounds ledger, and stages the corruption exhibit, with every claim quoted in this chapter guarded by an assert (step-model floor 0.95, dominance 0.5 at n = 8..16, steps-used = n, per-seed persistence 0.95). It imports the task generators and the certified MLP engine from examples/frontier/depth_ceiling.py; nothing is retyped. Run python3 examples/frontier/cot_steps.py to reproduce every number; two runs print byte-identical output.