Chain-of-thought (CoT) constructions that make transformers Turing complete, typically simulate a counter machine, one transition per generated token, making autoregressive length proportional to the simulated runtime. Since serial generation is a key computational cost, we ask whether this length can be reduced while preserving the recognized language and the generalization properties of the simulation. We introduce two machine rewrites with exact recognition guarantees. First, order k macro transitions combine k reachable base transitions into one token. We prove that the resulting guards retain the per-counter threshold structure, determinism is preserved, and a run of length T is compressed to about T divided by k steps for fixed k, a constant factor reduction that leaves the asymptotic serial complexity unchanged, with a vocabulary bounded by the base vocabulary raised to k. Second, base b counting compresses monotone decrement bursts by processing b counter units per token. Both rewrites remain within the same CoT counter programming class, allowing the base construction's length generalization result to transfer under its assumptions. Experiments on synthetic counter machine tasks, including multi-counter multiplication with nested loops, show that transformers trained on compressed traces retain length generalization under moderate compression while achieving the predicted reductions in trace length, and that this retention degrades once compression becomes large relative to the counting range. We observe corresponding reductions in generation latency, attention operations, and key value cache size. Accuracy degrades as compression becomes aggressive relative to the counting range, consistent with our analysis. We further characterize reachable vocabulary growth and quantify the associated data scaling cost.
Transformers that produce a chain-of-thought before answering can carry out computations that a single forward pass cannot. A line of theory has made this precise by showing that, with sufficiently many generated intermediate tokens, decoder only transformers can simulate general models of computation
The counter machines underlying these constructions can be inefficient. A counter machine may require exponentially many steps in the space of the Turing machine it simulates
We study whether the step count of these counter machine based CoT constructions can be reduced without changing the computation being simulated. Our approach is to modify the simulated machine rather than the transformer architecture: several fine grained transitions can be represented by a single macro transition, while counting loops can process multiple counter units per generated token. We characterize when these rewrites preserve the structure required by the underlying transformer construction and quantify the resulting reduction in generated positions.
Our contributions are:
The base construction spends one generated position per base transition. Our first operator groups every reachable sequence of \(k\) consecutive base transitions into a single macro token, so a run of \(T\) base steps becomes a trace of about \(T/k\) tokens, rounded up. The composed guard remains a per counter threshold test, so the compressed machine stays within the same guarded update counter machine framework, with counters recoverable from prefix counts. It therefore recognizes the same language. The interactive example below illustrates this compression: the base trace collapses into its macro trace, reducing the number of generated positions while preserving the information represented by the computation.
Overall, our results show that, for the counter machine based CoT constructions studied here, the number of generated reasoning steps can be reduced by changing the granularity of the simulated computation. The analysis also makes explicit the resulting tradeoffs: greater compression reduces sequence length but can increase vocabulary size and affect learnability. We characterize these tradeoffs rather than claiming a general speedup for arbitrary chain-of-thought. In our setup, \(k\) and \(b\) are fixed, so all reductions reported here are constant factors in the input length; they reduce the serial length of the simulation by a bounded multiple rather than changing its asymptotic dependence on the simulated runtime.
Expressive power of transformers. A substantial body of work characterizes the computational limits of transformers. Fixed depth encoders without intermediate decoding fall within restricted circuit and logical classes
Chain-of-thought as computation. Intermediate generation can substantially expand the computational capabilities of transformers. Scratchpads and chain-of-thought were first demonstrated empirically
Counter machines. Counter machines are classical models of computation with well established connections to Turing machines and formal language recognition
Length generalization and positional encoding. Length generalization in transformers depends on both the underlying computation and the positional representation used to encode it
Complementary approaches to efficient generation. Several lines of work address the cost of long autoregressive computation from other directions. Positional encoding methods aim to make longer sequences easier to learn or extrapolate
Counter machines. A deterministic guarded update counter machine is a tuple \(S = (Q, k_c, \Delta, q_0, F_{\mathrm{acc}}, F_{\mathrm{rej}}, \iota)\) with control states \(Q\), \(k_c\) counters, transitions \(\Delta\), a start state, disjoint accepting and rejecting halting states, and an initializer \(\iota\) that sets the counters from the input word. A configuration is a pair \((q, x)\) with \(q \in Q\) and \(x \in \mathbb{N}^{k_c}\). A transition is \(\tau = (\mathrm{src}(\tau), g(\tau), u(\tau), \mathrm{dst}(\tau))\), where the guard \(g(\tau)\) is a conjunction of atoms \((x_i \bowtie c)\) for a single counter \(i\), a constant \(c \in \mathbb{N}\), and a comparison \(\bowtie \in {=, \ge, \le, >, <}\), and the effect \(u(\tau) \in \mathbb{Z}^{k_c}\) is added to the counters. The machine is deterministic when at most one transition is enabled at every configuration. On input \(w\), it starts at \((q_0, \iota(w))\) and repeatedly applies the unique enabled transition, emitting its token, until it reaches a halting state. The emitted sequence is the trace, and \(w\) is accepted when the final state is accepting.
Chain-of-thought counter programming. The base construction compiles such a machine into a decoder only transformer that emits the trace one token per step
a weighted prefix count over the emitted trace tokens \(a_1, \dots, a_{t-1}\). A causal attention head computes such prefix counts, and each guard atom \((x_i \bowtie c)\) is therefore a threshold test on that value. We call a simulation that uses integer effects and single counter threshold guards over prefix counts a CoT counter program. Our rewrites remain within this class, allowing the corresponding properties of the base construction, including its length generalization guarantee, to transfer under the stated assumptions.
Cost model. The transformer pays for a trace through its number of generated positions \(N\). Generation is serial in \(N\), the cumulative attention computation over the growing context costs \(\Theta(N^2 d)\) arithmetic operations for model width \(d\), and the key value cache grows linearly with \(N\). We therefore treat \(N\), the number of generated positions, as the primary quantity to reduce while keeping the recognized language fixed.
The base construction spends one generated position on each machine transition. Our first compression mechanism changes this granularity: several consecutive transitions that are jointly determined by the current configuration are represented by a single macro transition. The key question is whether this composition preserves the restricted guard structure required by the CoT counter program. We first establish this property, then derive determinism, exact recognition, and vocabulary bounds.
Fix a deterministic machine \(S\) with transition set \(\vocab\). A block of length \(r\) is a sequence \(\pi = \tau_1 \tau_2 \cdots \tau_r\) of base transitions that is chainable, meaning \(\dst(\tau_j) = \src(\tau_{j+1})\) for all \(j < r\). For a block, define the accumulated shift before its \(j\)th step as \(s_j = \sum_{l < j} \eff(\tau_l) \in \Int^{k_c}\), with \(s_1 = 0\). We then define the macro effect and guard as
\[u(M_\pi) = \sum_{j=1}^{r} u(\tau_j), \qquad \varphi_\pi(x) = \bigwedge_{j=1}^{r} g(\tau_j)\big(x + s_j\big),\]with \(\mathrm{src}(M_\pi) = \mathrm{src}(\tau_1)\) and \(\mathrm{dst}(M_\pi) = \mathrm{dst}(\tau_r)\). The token \(M_\pi\) fires only when \(x + s_j \in \Nat^{k_c}\) for every \(j\), which we fold into \(\varphi_\pi\) through the nonnegativity condition at each step.
The main technical question is whether composing guards in this way takes us outside the guard language supported by the base CoT construction.
Lemma 1 (Canonical guard). For any block \(\pi\), the macro guard \(\varphi_\pi\) is equivalent to a conjunction of single counter threshold atoms, or equivalently, a per counter interval constraint \(\bigwedge_{i=1}^{k_c} \big( \ell_i \le x_i \le h_i \big)\) with \(\ell_i \in \Nat\) and \(h_i \in \Nat \cup {\infty}\).
Proof. Each atom of \(\guard(\tau_j)\) has the form \((x_i \bowtie c)\) for a single counter \(i\). Substituting the shifted argument \(x + s_j\) replaces it by \((x_i \bowtie c - s_{j,i})\), which is again a single counter threshold atom on the same counter with the constant translated by the integer \(s_{j,i}\). When the translated constant is negative, the atom is either trivially true for \(\ge\) and \(>\) or trivially false for \(\le\), \(<\), and \(=\), which we simplify away. The nonnegativity requirement \(x_i + s_{j,i} \ge 0\) is the atom \((x_i \ge -s_{j,i})\). Thus \(\varphi_\pi\) is a finite conjunction of single counter threshold atoms. For a fixed counter \(i\), a conjunction of atoms \((x_i \ge a)\), \((x_i > a)\), \((x_i \le b)\), \((x_i < b)\), and \((x_i = c)\) is the intersection of half lines and points on \(\Nat\), which is an interval \([\ell_i, h_i]\), possibly empty, a single point, or unbounded above. Taking the conjunction over counters gives the stated per counter interval form. \(\square\)
Lemma 1 is the key closure property: composing transitions does not leave the guard language. The macro guard remains a threshold test on the prefix count defined in the preliminaries, so a macro token is still a valid primitive of the CoT counter program.
Order \(k\) machine. For a target order \(k\), the macro machine \(S_k\) keeps the states of \(S\) and uses the resulting macro tokens. From every non halting state \(q\), we include each chainable block \(\pi\) of length exactly \(k\) that starts at \(q\), whose guard \(\varphi_\pi\) is satisfiable, and whose first \(k-1\) destinations are non halting. To handle runs whose remaining length is not a multiple of \(k\), we also include variable order blocks of length \(r \in {1, \dots, k-1}\) whose final destination is a halting state. The macro vocabulary \(\vocab^{(k)}\) is the set of these tokens. Counters update by \(\eff(M_\pi)\), so the prefix count identity holds verbatim with macro effects, and \(S_k\) remains a CoT counter program.
The guard composition above preserves the local structure of the base machine. We next show that it also preserves deterministic execution and yields an exact reduction in trace length.
Lemma 2 (Determinism preserved). If \(S\) is deterministic, then \(S_k\) is deterministic.
Proof. Fix a reachable configuration \((q, x)\) of \(S_k\) with \(q\) non halting. Because \(S\) is deterministic, there is a unique maximal base run from \((q,x)\). Let \(\pi^\star\) be its first \(\min(k,m)\) transitions, where \(m\) is the number of base steps until the run first halts. We claim that \(M_{\pi^\star}\) is the unique macro token enabled at \((q,x)\).
It is enabled because every prefix of the base run satisfies its guard at the corresponding shifted counters, so \(\varphi_{\pi^\star}(x)\) holds. The destinations before the last are non halting exactly when \(\min(k,m)=k\), matching the two token families. For uniqueness, suppose a block \(\pi \ne \pi^\star\) with \(\src(\pi)=q\) had \(\varphi_\pi(x)\) true. Let \(j\) be the first index where \(\pi\) and \(\pi^\star\) differ. The prefix \(\tau_1 \cdots \tau_{j-1}\) is shared, so both reach the same configuration \((q',x')\) before step \(j\). Enabling \(\varphi_\pi\) requires \(\guard(\tau_j)\) to hold at \(x'\) and \(\tau_j\) to be applicable there, and likewise for \(\tau^\star_j\). Since \(S\) is deterministic, only one transition is enabled at \((q',x')\), so \(\tau_j = \tau^\star_j\), a contradiction. Halting states have no outgoing macro token, so determinism holds everywhere. \(\square\)
Theorem 1 (Macro speedup). Let \(S\) be a deterministic guarded update counter machine and let \(w\) be an input on which \(S\) halts after \(T\) base transitions. Then \(S_k\) on \(w\) halts after exactly \(\ceil{T/k}\) macro transitions, reaches the same halting state, and its counter values after \(m\) macro tokens equal the base counter values after \(\min(mk,T)\) base steps. Consequently, \(L(S_k) = L(S)\).
Proof. Write \(T = qk + r\) with \(0 \le r < k\). By Lemma 2, \(S_k\) follows the unique base run, grouped into blocks. The first \(q\) macro tokens are the length \(k\) blocks \(\pi^{(1)}, \dots, \pi^{(q)}\) covering base steps \(1\) through \(qk\). By the macro effect definition, the counter update of the \(m\)th macro token equals the sum of the effects of its \(k\) base steps. Thus, after \(m \le q\) macro tokens, the counters equal the base counters after \(mk\) steps by a telescoping sum matching the prefix count identity.
If \(r=0\), the \(q\)th block ends in the halting state and the trace length is \(q = \ceil{T/k}\). If \(r>0\), one variable order block of length \(r\) covers the remaining base steps \(qk+1,\dots,T\) and ends in the same halting state that \(S\) reaches. The trace length is therefore \(q+1 = \ceil{T/k}\), and the final counters match the base counters after \(T\) steps. The final states are identical, so \(w\) is accepted by \(S_k\) if and only if it is accepted by \(S\). \(\square\)
The theorem gives an exact reduction in the number of generated positions for every halting run. The remaining question is the price paid in the token vocabulary.
Proposition 1 (Vocabulary bound). The macro vocabulary satisfies
\(\vert \vocab^{(k)}\vert \le \sum_{r=1}^{k} \vert \vocab\vert ^r = O!\left(\vert \vocab\vert ^k\right)\).
Only chainable, guard satisfiable, reachable blocks are included, so the realized vocabulary can be substantially smaller than this worst case.
Proof. A block of length \(r\) is a sequence of \(r\) base transitions, of which there are at most \(\vert \vocab\vert ^r\). Summing over \(r \in {1,\dots,k}\) gives the bound. Chainability, satisfiability, and reachability only remove tokens. \(\square\)
The worst case can be loose for structured machines. We next give bounds that depend on the control flow rather than on the total number of base transitions. Let \(\delta\) denote the control flow out degree, namely, the largest number of outgoing base transitions at any state.
Proposition 2 (Structural bound). \(\vert \vocab^{(k)}\vert \le \vert Q\vert \sum_{r=1}^{k}\delta^r\). Moreover, macro tokens that induce the same transition, meaning that they share source, destination, effect vector, and canonical guard, can be merged without changing the machine. Because \(S\) is deterministic, distinct feasible blocks cannot have the same guard while inducing different effects or destinations.
Proof. Every block starts at one of \(\vert Q\vert\) states and extends by at most \(\delta\) choices at each of its \(r\) steps. Thus there are at most \(\vert Q\vert \delta^r\) chainable blocks of length \(r\). Summing over \(r \in {1,\dots,k}\) gives the stated bound before feasibility and reachability pruning.
For the merge claim, two blocks with equal source, destination, effect, and canonical guard denote the same guarded update transition, so representing them by one token leaves the machine’s runs unchanged. If two feasible blocks had the same guard but differed in effect or destination, then from a common configuration satisfying that guard they would induce two distinct feasible base runs, contradicting determinism. \(\square\)
For machines with a single non halting successor, the dependence on the macro order becomes linear.
Proposition 3 (Linear vocabulary for single successor loops). If every non halting state of \(S\) has exactly one outgoing transition to a non halting state, with any remaining transitions leading to halting states, then \(\vert \vocab^{(k)}\vert \le \vert Q\vert k\).
Proof. Fix a start state. Its unique non halting successor determines the non halting prefix of every block, so there is at most one full block of length \(k\) from that state. For each remainder length \(r \in {1,\dots,k-1}\), there is at most one block that halts after exactly \(r\) steps, since the first \(r-1\) steps are the forced non halting prefix and the \(r\)th is a transition to a halting state. Thus there are at most \(1+(k-1)=k\) tokens per start state and at most \(\vert Q\vert k\) in total. \(\square\)
Proposition 3 covers the counting loops used in our tasks, where each residue state has one decrement successor and one halting exit. This predicts linear rather than exponential vocabulary growth with the macro order, which we test empirically below.
The preceding results concern the simulated machine. We next connect them back to the transformer construction. We state this connection carefully: it is an expressibility result about the class of programs that the construction can represent, not a claim that gradient based training necessarily finds the corresponding transformer.
Assumption 1 (Compilability of CoT counter programs).
There is a fixed decoder only transformer construction that, for any deterministic guarded update counter machine expressed as a CoT counter program, exactly reproduces its trace, using no explicit positional encoding and reading each counter as a weighted prefix count of emitted tokens, with each guard atom a threshold test on that count. This is the compilation of the base construction
Proposition 4 (Preserved expressibility). Under Assumption 1, \(S_k\) is a CoT counter program, so the same construction compiles \(S_k\) into a transformer that exactly reproduces the macro trace. Any length generalization guarantee that the construction provides for \(S\) through the CoT counter program interface applies to \(S_k\) under the same assumptions.
Proof. After \(m\) macro tokens, the value of counter \(i\) is \(\iota_i(w) + \sum_{j \lt m} u_i\!\left(M_{\pi^{(j)}}\right)\), which is a weighted prefix count of the emitted macro tokens. Thus, it has exactly the form of base construction equation in preliminaries, now with the macro alphabet. By Lemma 1, each macro guard is an interval constraint on each counter, and hence can be expressed as a conjunction of threshold tests on these prefix counts. Therefore, the macro machine \(S_k\) satisfies the interface required by Assumption 1. Applying the construction of Assumption 1 to \(S_k\) consequently reproduces its trace exactly. \(\square\)
The transfer is therefore an existence statement: whenever the base construction provides the corresponding length generalization guarantee for \(S\), the same construction applies to \(S_k\). Whether training recovers this solution from finite data is a separate question, which we examine empirically in experiments. In particular, the larger macro alphabet can reduce the number of examples associated with each token, creating a potential sample complexity cost. Our data scaling experiments quantify this tradeoff.
Theorem 1 reduces a trace of length \(T\) to \(\ceil{T/k}\) positions. This raises a basic question: what exactly is being compressed? Macro composition does not remove information from the simulated computation. Rather, it changes how that information is distributed across generated positions.
Remark (Information is conserved). The macro trace has \(\ceil{T/k}\) tokens over an alphabet of size at most \(O(\vert \vocab\vert ^k)\). Thus, using the worst case vocabulary bound, its description length is approximately \(\frac{T}{k} \cdot k \log_2 \vert \Delta\vert = T \log_2 \vert \Delta\vert\) bits, matching the corresponding upper bound for the base trace. Macro composition therefore does not claim to compress the information content of the computation. It repackages the same computation into fewer, wider symbols.
The relevant resource for the transformer is instead the number of generated positions. Under our cost model, reducing the trace from \(T\) to \(\ceil{T/k}\) reduces serial generation length by a factor of \(k\) and the key value cache size by the same factor. For naive attention over the full generated trace, the arithmetic cost changes from \(\Theta(T^2d)\) to \(\Theta((T/k)^2d)\), giving a factor of \(k^2\) reduction. This is directly relevant to the serial cost studied by existing chain-of-thought lower bounds
Macro composition treats all transitions uniformly. Counting loops offer a more targeted form of compression. Consider a single counter \(i\) with a monotone decrement burst: a state \(s\) with a self loop transition \(\tau_{\mathrm{dec}}\) of guard \((x_i > 0)\) and effect \(-e_i\), together with an exit transition of guard \((x_i = 0)\). To remove a mass of \(V\) units, the base machine fires \(\tau_{\mathrm{dec}}\) exactly \(V\) times.
Construction. The base \(b\) rewrite replaces the unit loop with block transitions on the same state. A full block has guard \((x_i \ge b)\) and effect \(-b,e_i\). For each remainder \(\rho \in {1,\dots,b-1}\), a block has guard \((x_i = \rho)\) and effect \(-\rho,e_i\) leading to the exit. The exit guard \((x_i = 0)\) is unchanged.
Each block uses a canonical single counter guard, so the rewritten machine remains a CoT counter program. It is also deterministic: \((x_i \ge b)\) covers all values at least \(b\), while the remainder guards \((x_i = \rho)\) cover the remaining positive values.
Proposition 4 (Base \(b\) speedup). The base \(b\) rewrite emits \(\floor{V/b}\) full blocks and at most one remainder block, hence \(\ceil{V/b}\) tokens, to remove a mass of \(V\), compared with \(V\) tokens for the base machine. For runs whose length is dominated by such bursts, a base trace of length \(T\) becomes a trace of length \(\Theta(T/b)\).
Proof. Write \(V = b\floor{V/b} + \rho\) with \(0 \le \rho < b\). While \(x_i \ge b\), the only enabled block is the full block, which fires \(\floor{V/b}\) times and reduces the counter to \(\rho\). If \(\rho=0\), the exit fires next and the number of block tokens is \(\floor{V/b}=\ceil{V/b}\). If \(\rho>0\), the corresponding remainder block fires once before the exit, giving \(\floor{V/b}+1=\ceil{V/b}\) tokens. Summing over counting dominated bursts yields the stated \(\Theta(T/b)\) trace length, up to the constant number of control tokens per burst. \(\square\)
This rewrite gives a more specialized speedup than macro composition: rather than grouping arbitrary transition sequences, it changes the granularity of a known counting operation. Its effect on the overall simulation length depends on how much of the computation is spent in such bursts.
Corollary 1 (Effect on counter simulation length).
Suppose the base machine simulates a Turing machine using space \(s\) and has a counting dominated run of length \(T = 2^{\Theta(s)}\), as can arise in counter based simulations
and therefore
\[\log_2 T_b = \Theta(s) - \log_2 b.\]Proof. Immediate from Proposition 4 applied to a counting dominated run. \(\square\)
The corollary should be interpreted as a constant shift for fixed \(b\), rather than as a change in the asymptotic dependence on the simulated space. The improvement is therefore modest in this regime, but it becomes directly measurable when counting transitions dominate the generated trace.
The two mechanisms operate at different levels. Base \(b\) counting compresses specific counting bursts, while order \(k\) macro transitions compose the resulting transitions more generally.
Corollary 2 (Composability). Applying the base \(b\) rewrite followed by order \(k\) macro composition to a counting dominated run reduces the number of generated positions by approximately a factor of \(bk\). The resulting machine remains a deterministic CoT counter program and recognizes the same language.
Proof. The base \(b\) rewrite reduces a counting dominated trace from \(T\) to \(\Theta(T/b)\) by Proposition 4. Applying Theorem 1 to the resulting machine introduces a further factor of approximately \(k\) in the number of positions while preserving determinism, recognition, and the CoT counter program structure. \(\square\)
The two rewrites therefore expose a general design principle: compression can be obtained either by grouping arbitrary consecutive transitions or by increasing the granularity of structured counting operations. The former applies broadly but can incur a larger vocabulary, while the latter provides a more targeted reduction with a smaller structural overhead.
The base \(b\) construction is intentionally restricted to single counter monotone decrement bursts. A loop that decrements several counters by fixed amounts on every iteration can admit an analogous vector rewrite, with a full block representing \(b\) iterations and remainder blocks handling the final partial group. Mixed sign or data dependent updates are not covered by this fixed radix construction because the number of iterations need not be determined by a single counter. Such computations can still be handled by the more general macro transition construction.
We therefore focus the formal and empirical analysis on the single counter case. The broader point is not that every chain-of-thought computation admits a uniform \(b\) fold compression, but that structured portions of a counter computation can sometimes be represented at a coarser granularity while remaining within the same CoT counter programming framework.
The theoretical results establish exact trace compression at the machine level. We now test the corresponding learning and efficiency questions: whether transformers trained on compressed traces retain length generalization, how compression affects generation cost, and when the larger macro vocabulary becomes a practical bottleneck. All experiments use synthetic tasks generated by hand built deterministic counter machines, with the exact machine trace serving as supervision.
We consider four tasks with different computational structure. Parity and mod 3 read a two symbol string and accept when the count of the first symbol is divisible by \(2\) or \(3\), respectively. Both are single counter decrement loops and therefore admit the base \(b\) rewrite. Comparison reads \(a^m b^n\) and accepts when \(m > n\). Unary mult reads \(a^m b^n c^p\) and accepts when \(p = mn\); its nested loops and multiple counters make it a more demanding test of macro composition.
We train a two layer decoder only transformer with width \(64\) and approximately \(6.7 \times 10^4\) parameters, without positional encoding, using next token prediction on the machine traces. At evaluation, the model greedily generates the complete trace. A prediction is counted as correct only when the entire generated trace exactly matches the target trace. We report three length stratified splits: EM0 within the training length range, and EM1 and EM2 at lengths strictly beyond those observed during training. Results are averaged over the available random seeds. The reported runs use a single CPU core; the same implementation supports larger length, data, and optimization budgets.
The machine constructions themselves are verified separately by direct unit tests, so deviations in the experiments reflect learned behavior rather than errors in the rewritten machines.
We first vary macro order \(k\) and base \(b\) and measure both trace length and exact match. The central empirical question is whether reducing the number of positions changes the model’s ability to recover the underlying computation.
For macro transitions, trace length decreases monotonically with \(k\) across the tasks. The observed reduction is below the ideal factor \(k\) on shorter traces because constant control and halting tokens do not compress. On unary mult, where traces are substantially longer, the reduction is close to the theoretical factor: the mean length ratio is \(1.98\) at \(k=2\). Exact match remains \(1.00\) on all three splits at both \(k=1\) and \(k=2\), including the longer splits, indicating that the learned model can recover the compressed computation on a multi counter task with nested loops.
| Task | \(k\) | Mean trace | Length ratio | EM0 | EM1 | EM2 |
|---|---|---|---|---|---|---|
| comparison | 1 | 4.10 | 1.00 | 1.00 | 1.00 | 1.00 |
| comparison | 2 | 2.27 | 1.81 | 1.00 | 1.00 | 1.00 |
| comparison | 3 | 1.68 | 2.45 | 1.00 | 1.00 | 0.92 |
| parity | 1 | 6.23 | 1.00 | 1.00 | 1.00 | 1.00 |
| parity | 2 | 3.36 | 1.85 | 1.00 | 1.00 | 0.98 |
| parity | 4 | 1.92 | 3.24 | 1.00 | 1.00 | 1.00 |
| unary mult | 1 | 42.65 | 1.00 | 1.00 | 1.00 | 1.00 |
| unary mult | 2 | 21.50 | 1.98 | 1.00 | 1.00 | 1.00 |
The same pattern holds for base \(b\) counting. Moderate compression preserves generalization, whereas aggressive compression can cause a sharp drop in extrapolation accuracy. For example, mod 3 remains perfect through \(b=2\) but falls to \(0.81\) on EM1 and \(0.10\) on EM2 at \(b=4\). This is consistent with the positions versus vocabulary tradeoff: the rewritten machine remains exact, but the shorter traces provide fewer training contexts for the expanded token set.
| Task | \(b\) | Mean trace | Length ratio | EM0 | EM1 | EM2 |
|---|---|---|---|---|---|---|
| parity | 1 | 6.15 | 1.00 | 1.00 | 1.00 | 0.90 |
| parity | 2 | 3.83 | 1.61 | 1.00 | 1.00 | 0.97 |
| parity | 4 | 2.67 | 2.30 | 1.00 | 0.97 | 0.91 |
| mod 3 | 1 | 6.72 | 1.00 | 1.00 | 1.00 | 1.00 |
| mod 3 | 2 | 4.11 | 1.63 | 1.00 | 1.00 | 1.00 |
| mod 3 | 4 | 2.82 | 2.38 | 1.00 | 0.81 | 0.10 |
These results separate two effects. Trace compression is guaranteed by the machine transformation; learned length generalization is not. In the tested regime, the latter survives moderate compression but eventually degrades as the compressed representation becomes harder to learn.
We next measure the computational effect of reducing positions. We report serial decode steps, attention FLOPs under a key value cache, peak cache size, and measured greedy generation latency. To isolate the effect of trace length, generation is forced to the true number of decode steps rather than allowing an untrained model to terminate early.
Figure 5: Generation cost under compression. Measured latency decreases with the number of generated positions, while attention operations and key value cache size follow the predicted dependence on trace length. The attention reduction is approximately quadratic in the compression factor under the stated cost model.
For comparison, measured latency on the comparison task decreases from \(16.4\) ms at \(k=1\) to \(5.4\) ms at \(k=3\), a factor of \(3.0\) versus a trace length reduction of \(2.9\). Analytic attention operations decrease by a factor of \(7.5\). On mod 3, latency decreases from \(33.1\) ms at \(b=1\) to \(8.3\) ms at \(b=4\).
| Task | Setting | Mean trace | Latency (ms) | Attention FLOPs | KV bytes | Vocabulary |
|---|---|---|---|---|---|---|
| comparison | \(k=1\) | 17.21 | 16.40 | \(8.02\times10^4\) | 17621 | 9 |
| comparison | \(k=2\) | 8.79 | 7.95 | \(2.20\times10^4\) | 9002 | 12 |
| comparison | \(k=3\) | 6.00 | 5.38 | \(1.08\times10^4\) | 6144 | 15 |
| mod 3 | \(b=1\) | 32.83 | 33.09 | \(2.84\times10^5\) | 33621 | 11 |
| mod 3 | \(b=2\) | 17.17 | 15.74 | \(7.98\times10^4\) | 17578 | 14 |
| mod 3 | \(b=4\) | 9.42 | 8.33 | \(2.51\times10^4\) | 9642 | 20 |
The measurements therefore follow the qualitative scaling predicted by the position based cost model: fewer generated positions reduce serial work and cache usage, while the quadratic attention term falls more rapidly. These measurements concern the tested implementation and should not be interpreted as a hardware independent latency law.
Compression changes not only sequence length but also the effective token alphabet. We therefore examine how many macro tokens are actually reachable and how much additional training data is required.
Figure 6: Reachable macro vocabulary. The worst case vocabulary bound grows exponentially with macro order, while the number of reachable and guard satisfiable macros in the studied machines grows much more slowly. At \(k=4\), the bound is \(1554\) versus \(15\) reachable tokens for mod 3, and \(11110\) versus \(63\) for unary mult.
| Task | \(\vert \mathcal{V}\vert\) | \(k\) | Worst case bound | Reachable | Merged |
|---|---|---|---|---|---|
| parity | 4 | 2, 3, 4 | 20, 84, 340 | 6, 8, 10 | 6, 8, 10 |
| mod 3 | 6 | 2, 3, 4 | 42, 258, 1554 | 9, 12, 15 | 9, 12, 15 |
| comparison | 4 | 2, 3, 4 | 20, 84, 340 | 7, 10, 13 | 7, 10, 13 |
| unary mult | 10 | 2, 3, 4 | 110, 1110, 11110 | 21, 38, 63 | 21, 38, 63 |
The gap between the worst case and reachable vocabulary is substantial in all four tasks. For the studied counting loops, the reachable vocabulary grows approximately linearly with \(k\), consistent with the structural bound for single successor loops. Canonical merging does not reduce the counts further in these deterministic machines because feasible blocks already have disjoint guards.
We finally test whether this larger alphabet creates a measurable data requirement.
Figure 7: Data scaling with macro order. On parity, exact match on the longest split improves with training set size for all macro orders. At 60 examples, \(k=4\) reaches \(0.44\) exact match, while all tested orders reach \(1.00\) with sufficient data, illustrating the data cost associated with a larger compressed vocabulary.
Holding the counting range, model size, and optimizer budget fixed, exact match on the longest split increases with training set size for \(k\in{1,2,4}\). At the smallest budget of \(60\) examples, \(k=4\) is the most data limited and reaches \(0.44\), whereas all orders reach \(1.00\) once sufficient data is provided. This supports the predicted tradeoff: compression reduces the number of positions, but sufficiently aggressive compression can shift the bottleneck from sequence length to vocabulary coverage.
Across these experiments, three observations are consistent. First, the machine rewrites produce the predicted reductions in trace length, including on the multi counter unary mult task. Second, moderate compression can retain length generalization, while sufficiently aggressive compression can degrade learned accuracy even though the underlying rewritten machine remains exact. Third, the computational savings from fewer positions are accompanied by a larger vocabulary and an associated data requirement. Thus, the experiments support a compression tradeoff rather than an unconditional speedup: the useful regime is one in which the reduction in generated positions outweighs the learning cost of the expanded vocabulary.
Taken together, the theoretical and empirical results support a consistent picture: trace compression preserves the underlying computation while substantially reducing the serial burden placed on the learner. The formal results establish that macro transitions preserve guards, determinism, and the base computation at block boundaries, while reducing a length \(T\) trace to exactly \(\lceil T/k\rceil\) positions. The counting rewrite further compresses monotone decrement bursts, yielding the predicted additive \(\log_2 b\) improvement in the exponent, and the two constructions compose without leaving the underlying counter programming class. These results support our central claim that sequence length is a representation dependent cost rather than an intrinsic requirement of the computation, within the constant factor regime we analyze.
The empirical results complement these guarantees by testing whether the theoretical savings translate into learning behavior. Across the synthetic counter machine tasks, including nested multi counter multiplication, Transformers trained on compressed traces retain length generalization while exhibiting the predicted reductions in trace length. Our measurements of generation latency, attention operations, and key value cache size further connect the formal reduction in positions to practical computational savings. The vocabulary scaling experiments also identify the principal tradeoff: increasing the compression order can reduce sequence length, but may enlarge the macro vocabulary and eventually constrain learnability. Thus, the results collectively address both sides of the proposed construction: exact computational preservation and reduced serial cost, together with an explicit characterization of the representation capacity required to realize those savings.
Our analysis fixes the simulated machine and the one token per transition scheme; it does not change the class of recognizable languages, only the serial length of the trace. Base b as tested applies to single counter monotone decrement bursts, with a vector extension for synchronized multi counter loops and mixed sign loops left open. The exponent improvement of Corollary 1 is additive in \(\log_2 b\) rather than a change in rate. The macro vocabulary can grow as \(O(\vert \Delta\vert ^k)\) in the worst case; for the single successor loops studied here, it grows approximately linearly. More broadly, the data scaling study indicates that the learnable range of \(k\) and \(b\) is constrained by embedding capacity relative to the counting range. Finally, the empirical evaluation uses small synthetic tasks and a single CPU core, while the larger protocol is reproducible on a GPU. These limitations define the scope of the current study and motivate extensions to richer transition structures and larger scale settings.
We presented a principled compression theory for chain-of-thought counter simulation, treating the number of generated positions as a representation dependent computational cost. Order \(k\) macro transitions compose sequences of base transitions into wider tokens, while the base \(b\) counting rewrite compresses monotone decrement bursts. Together, these constructions reduce trace lengths from \(T\) to \(\lceil T/k\rceil\) and from \(V\) to \(\lceil V/b\rceil\), respectively, while preserving determinism, exact recognition, and membership in the underlying counter programming class. The theoretical results therefore establish that these savings arise from changing the representation of the computation, not from discarding computational information.
The empirical evaluation complements these guarantees by showing that the predicted compression is realized in practice. Under moderate compression, transformers trained on compressed traces retain length generalization across our synthetic counter machine tasks while achieving reductions in generation latency, attention operations, and key value cache usage; more aggressive compression trades this retention for shorter traces. At the same time, our vocabulary analysis and scaling experiments expose the fundamental tradeoff: more aggressive compression reduces serial length but can increase the macro vocabulary and eventually exceed the model’s effective representation capacity. This provides a concrete boundary for compression rather than treating shorter traces as universally beneficial.
More broadly, our results suggest that chain-of-thought length should not be viewed as a fixed property of a reasoning task. The computational content can remain unchanged while its serial representation is substantially compressed. By combining exact preservation theorems, complexity analysis, structural vocabulary bounds, and controlled empirical validation, we turn this observation into a concrete design principle: reasoning traces can be made shorter by changing their granularity, with the achievable compression determined by the structure of the computation and the capacity required to represent the resulting vocabulary.
PLACEHOLDER FOR ACADEMIC ATTRIBUTION
BibTeX citation
PLACEHOLDER FOR BIBTEX