通过计算分离理解脚手架（scaffolds）的优势

# Understanding the Benefits of Scaffoldsthrough Computational Separations
Source: [https://arxiv.org/html/2610.27157](https://arxiv.org/html/2610.27157)
Jingchu GaiAdam BlockAndrej RisteskiMachine Learning DepartmentCarnegie Mellon UniversityDepartments of Computer Scienceand Electrical EngineeringColumbia UniversityMachine Learning DepartmentCarnegie Mellon Universityjgai@cs\.cmu\.eduadam\.block@columbia\.eduaristesk@cs\.cmu\.edu

###### Abstract

Inference\-time harnesses, i\.e\., external procedures that call a model many times and keep state across calls, can substantially improve model capabilities\. In this paper, we investigate the benefits of using such harnesses and the extent to which these benefits can be internalized through training\. More precisely, we conceptualize a harness𝒜\\mathcal\{A\}as an arbitrary wrapper around a base modelMMand attempt to distill a student model from the harness’s traces\. Empirically we find that, even with simple scaffolds and small models, the inference\-time harness significantly outperforms a distilled student\. We then prove that such a gap is due to a fundamental representational limitation: inference\-time harnesses can compute a closure of their per\-call primitive that is𝖭𝖫\\mathsf\{NL\}\-complete even when the primitive is a trivial𝖠𝖢0\\mathsf\{AC\}^\{0\}lookup, and that no fixed\-depth forward pass can represent under the widely believed conjecture that𝖭𝖫⊈𝖳𝖢0\\mathsf\{NL\}\\not\\subseteq\\mathsf\{TC\}^\{0\}\. Our theory suggests that expanding the representational capacity of the student relative to the task at hand, e\.g\., by enlarging the model, making the task easier, or lengthening its chain\-of\-thought, is necessary to close the gap, which we verify empirically\. Finally, we scale to an agentic harness on competition math, where the same gap reappears\. Overall, our results show that a harness confers on the base model a profound gain in representational power, one that training a same\-class student on its traces cannot transfer back into the weights\.

## 1Introduction

Much of the recent progress on challenging reasoning and agentic tasks depends on the workflow surrounding a language model\. An*inference\-time harness*\(or*scaffold*\) keeps the underlying model fixed, but calls it repeatedly, maintaining state and choosing later queries based on earlier answers\. Harnesses range from sampling and selecting complete solutions\([Wang et al\., 2022](https://arxiv.org/html/2610.27157#bib.bib42);[Cobbe et al\., 2021](https://arxiv.org/html/2610.27157#bib.bib6)\)to searching over partial solutions\([Yao et al\., 2023](https://arxiv.org/html/2610.27157#bib.bib45)\), backtracking with a verifier\([Rohatgi et al\., 2026](https://arxiv.org/html/2610.27157#bib.bib34)\), coordinating agents\([Du et al\., 2023](https://arxiv.org/html/2610.27157#bib.bib8)\), and incorporating tools and environment feedback\([Yao et al\., 2022](https://arxiv.org/html/2610.27157#bib.bib44)\)\.

There is something puzzling about how elementary some of these strategies are—and why they should improve the performance of already strong models\. For example, early systems achieving IMO gold\-level performance\([Huang & Yang, 2025](https://arxiv.org/html/2610.27157#bib.bib16)\)and autonomous mathematics research systems like Aletheia\([Feng et al\., 2026](https://arxiv.org/html/2610.27157#bib.bib10)\)use designed, but simple loops of maintaining a candidate set of solutions, expanding them, and pruning them by verification occasionally\. Why should a model capable of sophisticated mathematical reasoning benefit so much from having such a simple strategy imposed from outside?

Moreover, considering that simplicity of design is often desirable, the fact that carefully designed harnesses are needed to achieve strong performance raises the question of whether one can expect a model to learn such strategies on its own, thereby internalizing the benefits of a harness\. Indeed,[Cundy & Ermon \(2024\)](https://arxiv.org/html/2610.27157#bib.bib7)train models to perform backtracking themselves and[Gandhi et al\. \(2024\)](https://arxiv.org/html/2610.27157#bib.bib12)to search by learning from serialized search traces\. It is unclear, however, when one can expect this internalization to be successful and when a practitioner would be better off simply using a harness at inference\-time\.

There is likely more than one reason why a harness can improve performance: for example, it may increase the effective capacity of the underlying model, provide a form of error correction, or provide implicit decomposition of the target task into semantically meaningful subtasks\([Zhang et al\.,](https://arxiv.org/html/2610.27157#bib.bib47)\)\. While these intuitions are plausible, turning them into a predictive theory that can guide harness design requires precise hypotheses that can be tested quantitatively and, ideally, proved under suitable assumptions\. The prevalence and success of harnesses make this an increasingly important task\.

In this paper, we examine the success of inference\-time harnesses through a computational lens: we show a model capable of executing each individual step of a harness may nevertheless be unable to represent the computation performed by the composition represented by the harness\. We first investigate this hypothesis experimentally, then give a theoretical setting in which such internalization is*provably*impossible under standard computational modeling assumptions of the base model\.

We first perform controlled experiments on Dyck languages \(a formal language of valid nested parentheses\) and Sokoban \(a maze\-like puzzle game\), where we can train a model from scratch and vary the difficulty of generalization\. We train a base model on ground\-truth demonstrations, then augment it with a harness: either a principled backtracking algorithm \(VGB\) introduced by[Rohatgi et al\. \(2026\)](https://arxiv.org/html/2610.27157#bib.bib34), or A\* search with model\-pruned expansions\([Hart et al\., 1968](https://arxiv.org/html/2610.27157#bib.bib14);[Lehnert et al\., 2024](https://arxiv.org/html/2610.27157#bib.bib20)\)\. Together, the harness and base model specify a teacher whose behavior we attempt to reproduce with a student of the same size and model class as the base model\. The student is trained on the teacher’s traces, either from scratch or by fine\-tuning the base model\. In both cases, a substantial gap remains, particularly out of distribution\. Changing the amount and composition of training data, the trace format, or the number of training iterations does not close this gap in the settings we test\.

Why does this training fail to reproduce the teacher’s behavior? One possible explanation is that a harness fundamentally increases the representational capacity of the base model, so that reproducing the harness requires a larger model than executing its individual calls\. We investigate this by increasing the student’s size while keeping the teacher fixed: sufficiently large students match and eventually exceed their teacher’s performance\. We also test a complementary hypothesis that a simpler harness should be easier for the original student to internalize\. Specifically, we replace verifier\-controlled backtracking with a rule that deletes a fixed number of tokens and regenerates\. The same\-sized student can match this simpler teacher\.

Model size is not the only reasonable consideration: a student may also need more “reasoning steps” to carry out the harness’s computation\. Indeed, recent work has shown that increasing the length of a chain of thought can be understood to mimic the representational capacity of a much deeper model\([Merrill & Sabharwal, 2024](https://arxiv.org/html/2610.27157#bib.bib29);[Li et al\., 2024](https://arxiv.org/html/2610.27157#bib.bib22);[Merrill & Sabharwal, 2026a](https://arxiv.org/html/2610.27157#bib.bib26);[Amiri et al\., 2025](https://arxiv.org/html/2610.27157#bib.bib2)\)\. In particular, on modular arithmetic, we find that training a model to use a longer chain of thought lets it match and eventually exceed the accuracy obtained by augmenting a shorter\-chain model with verifier\-guided search\. These experiments suggest that successful internalization depends on the student’s size, the number of reasoning steps it can take, and the complexity of the strategy it must reproduce\.

These observations motivate a formal separation in*representational capacity*\. We consider directedss–ttreachability\([Jones, 1975](https://arxiv.org/html/2610.27157#bib.bib19)\), the task of path\-finding in a graph\. To model a search harness, we think of vertices as reasoning states and edges as valid transitions\. The base model only answers local edge queries, which are adjacency\-matrix lookups computable by constant\-depth Boolean circuits \(𝖠𝖢0\\mathsf\{AC\}^\{0\}\)\. The harness maintains a search frontier and visited set, using these queries to perform breadth\-first search and decide reachability in polynomial time\.

Internalizing the harness requires the student to decide reachability from the graph itself\. Under standard precision assumptions, fixed\-depth transformers of polynomial size can be simulated by constant\-depth threshold circuits \(𝖳𝖢0\\mathsf\{TC\}^\{0\}\), even with logarithmic\-length chain\-of\-thought\([Li et al\., 2024](https://arxiv.org/html/2610.27157#bib.bib22);[Merrill & Sabharwal, 2026a](https://arxiv.org/html/2610.27157#bib.bib26)\)\. Since directed reachability is𝖭𝖫\\mathsf\{NL\}\-complete, the widely believed computational complexity separation𝖭𝖫⊈𝖳𝖢0\\mathsf\{NL\}\\not\\subseteq\\mathsf\{TC\}^\{0\}implies that no such student can reproduce the harness on all inputs\. The separation thus captures a concrete obstacle to internalization: composing local decisions through an external search procedure can exceed the students’ representational capacity\.

Finally, we examine whether the same pattern persists with an agentic harness around a pretrained language model\. We use Branching\([Bateni et al\., 2025](https://arxiv.org/html/2610.27157#bib.bib4)\), which organizes model calls into a tree: leaves propose solutions independently, and internal nodes synthesize new solutions from their children\. Using Qwen3\-1\.7B on competition mathematics \(DAPO\-Math\-17k\), we flatten the teacher’s runs into transcripts and LoRA fine\-tune the same backbone to reproduce them in a single autoregressive rollout\. As the branching factorddand depthLLincrease, the teacher’s accuracy improves while the student’s eventually plateaus, widening the gap\. Increasing the LoRA rank yields only modest gains, whereas enlarging the backbone closes the gap\. These results support the same interpretation as our controlled experiments and theory: internalizing a harness may require a larger model than the one used in the harness\.

Figure 1:Same\-size students cannot recover the teacher\.*ID \(blue\) / OOD \(magenta\) accuracy of the base model and the two students; dashed lines denote the teacher\.*### 1\.1Our contributions

Students cannot internalize natural inference\-time harnesses if they are the same size as the teacher\.We generate training data from traces of a modelMMused inside a harness, and perform supervised finetuning \(SFT\) ofMMon them\. Across two natural harnesses: a principled backtracking algorithm \(VGB\)\([Rohatgi et al\., 2026](https://arxiv.org/html/2610.27157#bib.bib34)\)and A\* search\([Hart et al\., 1968](https://arxiv.org/html/2610.27157#bib.bib14)\); a set of natural, extensive ablations varying the amount of traces, training iterations, trace format, amount of out\-of\-distribution data—the resulting student never closes the gap to its teacher\.

The performance gap closes when increasing relative expressive power of the student\.We show empirically that the gap in performance between a model with a harness and a \(finetuned\) model without the harness closes as the student’s expressive power grows relative to the task—for example, using a larger student, an easier scaffold, or a longer chain\-of\-thought\.

There is a formal obstruction to internalizing a harness provided by representational capacity\.We consider directedss–ttreachability on a graph as a paradigmatic problem modeling path\-finding\. A base model that answers local edge queries—an𝖠𝖢0\\mathsf\{AC\}^\{0\}computation—can be used by a polynomial\-time harness to run breadth\-first search and decide reachability\. On the other hand, a student with anO⁡\(log⁡n\)O\(\\log n\)\-length chain\-of\-thought provably stays inside𝖳𝖢0\\mathsf\{TC\}^\{0\}\. By contrast, under standard precision assumptions, a fixed\-depth, polynomial\-size student remains in𝖳𝖢0\\mathsf\{TC\}^\{0\}even with anO⁡\(log⁡n\)O\(\\log n\)\-length chain\-of\-thought\. Thus, assuming𝖭𝖫⊈𝖳𝖢0\\mathsf\{NL\}\\not\\subseteq\\mathsf\{TC\}^\{0\}, no such student can internalize the harness\.

Our results extend to popular harnesses on mathematical reasoning tasks\.We distill the Branching harness\([Bateni et al\., 2025](https://arxiv.org/html/2610.27157#bib.bib4)\)on competition math using Qwen3\-1\.7B\. The harness reaches43\.6%43\.6\\%accuracy with8585model calls, while a single\-pass student saturates near36%36\\%\. Increasing the LoRA rank improves the student by only2\.22\.2percentage points; increasing its backbone from1\.71\.7B to44B closes the gap\.

### 1\.2Preliminaries and notation

Throughout the paper we fix a base autoregressive modelMM\(the*base model*\), trained on clean demonstrations of a task with standard next\-token prediction\. An*inference\-time harness*\(or*scaffold*\)𝒜\\mathcal\{A\}is any algorithm that can callMMas an oracle\. The resulting teacher is𝒜⁡\[M\]\\mathcal\{A\}\[M\]\. A run of𝒜\\mathcal\{A\}produces a*trace*—the full sequence of calls and answers\. The specific form of this trace will vary with the choice of scaffold\. A*student*SSis a model trained by next\-token prediction on these traces\. We ask whetherSScan*internalize*𝒜\\mathcal\{A\}—i\.e\. match the accuracy of𝒜⁡\[M\]\\mathcal\{A\}\[M\]from one forward pass\.

Computational complexity classes\.We recall several standard definitions of uniform circuit classes; see[Arora et al\. \(2009\)](https://arxiv.org/html/2610.27157#bib.bib3)and[Vollmer \(1999\)](https://arxiv.org/html/2610.27157#bib.bib41)for background\.𝖠𝖢0\\mathsf\{AC\}^\{0\}denotes constant\-depth, polynomial\-size circuits with unbounded fan\-in AND/OR/NOT gates\.𝖳𝖢0\\mathsf\{TC\}^\{0\}adds unbounded fan\-in threshold \(majority\) gates\. Throughout the formal analysis, these families are logspace\-uniform: a deterministic procedure generates the circuit from1n1^\{n\}usingO⁡\(log⁡n\)O\(\\log n\)workspace\. The classes𝖫\\mathsf\{L\}and𝖭𝖫\\mathsf\{NL\}consist of languages decided using deterministic and nondeterministic logarithmic space, respectively\. We recall the following standard inclusions:

𝖠𝖢0⊆𝖳𝖢0⊆𝖫⊆𝖭𝖫⊆𝖯\.\\textstyle\\mathsf\{AC\}^\{0\}\\subseteq\\mathsf\{TC\}^\{0\}\\subseteq\\mathsf\{L\}\\subseteq\\mathsf\{NL\}\\subseteq\\mathsf\{P\}\.

## 2Students with the Same Expressive Power as the Base Model Cannot Recover the Teacher’s Performance

We begin with empirical observations derived in simple, but clean settings in which we can train a student model from scratch, and perform thorough sweeps and ablations across various relevant aspects of the setup\. Concretely, we consider harnesses inspired by search algorithms \(principled backtracking based on\([Rohatgi et al\., 2026](https://arxiv.org/html/2610.27157#bib.bib34)\)and A\*\), for the tasks of generating valid strings of nested parentheses \(i\.e\. Dyck languages\) and Sokoban \(a maze\-like puzzle game\) respectively—and ask whether distillation can transfer the harness’s gains to a student of the same size and architecture as the base model, and hence the same expressive power\. We find that students trained from scratch perform far below even the base models; students fine\-tuned from the base models also cannot reach the teachers’ gains\.

Figure 2:Bigger students and a simpler scaffold narrow the gap\.*\(a\) The two scaffolds\. \(b\) Accuracy against the student’s parameter count\. \(c\) Accuracy against the distribution the traces were drawn from; dashed lines mark the teacher\.*### 2\.1Setup

We use two tasks with an easy\-to\-control in\-distribution \(ID\) / out\-of\-distribution \(OOD\) instances\.

1. 1\.Dyck: sequences of properly nested brackets, with every opening bracket matched by a closing bracket of the same type\. We use44bracket types and sequences of length6464\. The ID distribution draws bracket types with probabilities\[0\.1,0\.2,0\.3,0\.4\]\[0\.1,0\.2,0\.3,0\.4\], while the OOD distribution reverses these probabilities to\[0\.4,0\.3,0\.2,0\.1\]\[0\.4,0\.3,0\.2,0\.1\]\.
2. 2\.Sokoban: a puzzle in which a player moves through a grid and pushes a box onto a target, with walls blocking the movement\. We use a5×55\\times 5grid with one player, one box, one target, and up to three walls, with actions\{U,D,L,R\}\\\{U,D,L,R\\\}\. ID instances have short solutions, while OOD instances are biased toward longer ones \(reversed solution\-length buckets\)\.

We consider the following two scaffolds:

1. 1\.VGB\([Rohatgi et al\., 2026](https://arxiv.org/html/2610.27157#bib.bib34)\)\. The base model proposes an actiona∼M\(⋅∣s\)a\\sim M\(\\cdot\\mid s\), a verifier scores it, and the step is committed or retracted \(<BT\>\) according to the Metropolis\-style ratio pretract=max⁡\(ε,1−V~​\(s,a\)/V~​\(s\)\)\.\\textstyle p\_\{\\text\{retract\}\}\\;=\\;\\max\\big\(\\varepsilon,\\;1\-\\widetilde\{V\}\(s,a\)/\\widetilde\{V\}\(s\)\\big\)\. HereV~\\widetilde\{V\}is the*policy\-conditional*success probability—how likely the base model is to produce a valid solution from the current prefix—so the ratio measures the progress the proposed action makes: V~\(s\)=𝔼τ∼M\(⋅∣s\)\[𝟏\[valid\(s∘τ\)\]\],V~\(s,a\):=V~\(s∘a\)\.\\textstyle\\widetilde\{V\}\(s\)=\\mathbb\{E\}\_\{\\tau\\sim M\(\\cdot\\mid s\)\}\\big\[\\mathbf\{1\}\[\\text\{valid\}\(s\\circ\\tau\)\]\\big\],\\qquad\\widetilde\{V\}\(s,a\):=\\widetilde\{V\}\(s\\circ a\)\.
2. 2\.A\* search\([Hart et al\., 1968](https://arxiv.org/html/2610.27157#bib.bib14)\)maintains a frontier of candidate states and repeatedly expands the state with the smallestf=g\+hf=g\+h\. Hereggis the number of moves taken so far, andhhis the Manhattan distance from the box to the target\. At each expansion, we retain only the top\-k=2k\{=\}2successor actions according to base model’s logits\. The trace records when a node enters the frontier \(<CREATE\>\) and when it is expanded \(<CLOSE\>\), along with itsg,h,fg,h,fvalues; it ends with the resulting<PLAN\>\. This search\-log serialization follows[Lehnert et al\. \(2024\)](https://arxiv.org/html/2610.27157#bib.bib20)\. The trace prepends a quantized verifier bucket before each action or<BT\>event, so the student sees the signal that drove every backtrack\.

Figure 3:A long enough chain\-of\-thought matches the scaffold\.*\(a\) The task\. \(b\) Accuracy against the training chain\-of\-thought lengthLL; the dashed line marks the phase transition\.*We defer the exact Metropolis derivation, verifier instantiations, and trace formatting to Appendix[B\.1](https://arxiv.org/html/2610.27157#A2.SS1)\.

Both student and teacher models are22\-layer Transformers withdmodel=128d\_\{\\text\{model\}\}\{=\}128and44heads \(≈0\.68\\approx 0\.68M parameters\), so the student is the*same size*as the model the teacher\. The base model is trained on clean ID demonstrations\. Students are trained in two ways: \(i\)*from scratch*on a pool of traces and \(ii\)*fine\-tuned*from the base model on a mixture of traces and clean data\. We report accuracy on held\-out ID and OOD splits under greedy/top\-ppdecoding \(gen\); unless otherwise noted, the teacher figure is the full scaffold𝒜⁡\[M\]\\mathcal\{A\}\[M\]\.

### 2\.2Experimental Results

We first show that in both tasks, the student cannot recover the teacher’s accuracy\. We then perform ablations on the training data distribution, the number of training iterations, and the amount of training data that gives strong evidence that the gap between the student and the teacher is not caused by training dynamics\.

Student Cannot Recover Teacher Model\.Figure[1](https://arxiv.org/html/2610.27157#S1.F1)compares the base model, the teacher𝒜⁡\[M\]\\mathcal\{A\}\[M\], and the two students in the three \(algorithm, domain\) settings\. A student trained from scratch on the teacher’s traces falls below the base model both ID and OOD, likely because the traces are a much harder learning target than clean task data\. A student fine\-tuned from the base model stays close to the base model on both splits, but well below the teacher\.

Ablations\.We give strong evidence the gap is not due to a failure of training: we sweep various relevant aspects in the training setup, and the same\-size student always stays below the teacher\. Full grids, including four trace formats, are in Appendix[B\.3](https://arxiv.org/html/2610.27157#A2.SS3)\.

∙\\bullet*Fine\-tuning sweeps\.*Starting from the base model we vary, one axis at a time: the*clean\-data ratio*mixed with VGB traces \(00–100%100\\%\), the number of*fine\-tuning iterations*\(33K–88K\), the*number of traces*\(11K–2020K traces\), and the*training\-source mixture*Pα=\(1−α\)​PID\+α​POODP\_\{\\alpha\}=\(1\-\\alpha\)P\_\{\\text\{ID\}\}\+\\alpha P\_\{\\text\{OOD\}\}of the puzzles the traces are drawn from \(α∈\{0,0\.25,0\.5,0\.75\}\\alpha\\in\\\{0,0\.25,0\.5,0\.75\\\}\)\. Across all four axes the student tracks the base model and stays below the teacher dashed line \(Figure[6](https://arxiv.org/html/2610.27157#A1.F6), Appendix[B\.3\.1](https://arxiv.org/html/2610.27157#A2.SS3.SSS1)\)\. Adding more data, more iterations, and richer source mixtures change the student only marginally\.

∙\\bullet*From\-scratch sweeps\.*Holding the student at the fixed teacher scale \(0\.680\.68M\), we sweep the remaining data and optimization knobs of the from\-scratch training: random*seeds*, the training\-sourceα\\alpha\-mix, and an*OOD\-source*variant where the training traces themselves come from OOD instances\. Across all of these sweeps, the gap between the student and the teacher remains \(Figure[8](https://arxiv.org/html/2610.27157#A1.F8), Appendix[B\.3\.2](https://arxiv.org/html/2610.27157#A2.SS3.SSS2)\)\.

## 3The Student–Teacher Gap Closes as the Student’s Expressive Power Increases

In Section[2](https://arxiv.org/html/2610.27157#S2)we systematically performed various changes to the training setup, but the student was always taken to be in the*same*model class as the model its teacher wraps\. In this section, we remove that constraint and investigate the effect of allowing the student’s expressive power to grow—relative to the hardness of the task\. We find that the gap is not an intrinsic property of trace distillation: it shrinks, and eventually vanishes, along many axes that increase the student’s representational capacity\. We consider three ways of increasing the student’s expressive power relative to the scaffolded teacher: enlarging the student’s size \(Section[3\.1](https://arxiv.org/html/2610.27157#S3.SS1)\), replacing the scaffold with a simpler one \(Section[3\.2](https://arxiv.org/html/2610.27157#S3.SS2)\), and lengthening the student’s chain\-of\-thought \(Section[3\.3](https://arxiv.org/html/2610.27157#S3.SS3)\)\.

### 3\.1Bigger Students Learn Harnesses Better

We first consider increasing the student’s expressive power by directly increasing its number of parameters\.

Setup\.Section[2](https://arxiv.org/html/2610.27157#S2)fixed the student at the teacher scale \(≈0\.68\\approx 0\.68M\)\. Here we sweep1212scales over two orders of magnitude in parameter count \(0\.100\.10M–11\.511\.5M\) and ask whether a*bigger*student internalizes the scaffold better\. Each \(scale, clean\-ratio, iteration\) cell is a fresh student trained on the same pool of traces as Section[2](https://arxiv.org/html/2610.27157#S2), evaluated on the held\-out ID/OOD split\. We report the per\-scale best accuracy\.

Results\.As the student grows, its gap to the teacher shrinks on both ID and OOD: on VGB\-Dyck \(Figure[2](https://arxiv.org/html/2610.27157#S2.F2)b\) and on A\*\- and VGB\-Sokoban \(Figure[9](https://arxiv.org/html/2610.27157#A1.F9), Appendix[C\.1](https://arxiv.org/html/2610.27157#A3.SS1)\)\.

### 3\.2Simpler Harnesses Can be Learned without Increasing Student Size

Next, we consider making the target task easier: the teacher’s scaffold is replaced by a simpler one, which implicitly increases the student’s expressive power relative to the scaffolded teacher\. We again find that the gap between the student and the teacher shrinks\.

Setup\.VGB and A\*\-search both maintain unbounded search state—the number of steps the teacher takes and the amount of history grow with the problem\. If we instead consider a harness which is*bounded and local*, the student becomes larger in a relative sense\. We test the simplest such scaffold on Dyck: single\-step backtracking \(BT\), where a verifier flags the last token as erroneous and the model retracts a fixed stride and regenerates\. The distilled student learns to emit its*own*<BT\>tokens autoregressively—internalizing the policy with no external verifier—and we vary the source distribution of the distilled traces, anα\\alpha\-mixture between the ID and OOD bracket distributions\.

Results\.On ID, the student recovers the teacher’s accuracy \(Figure[2](https://arxiv.org/html/2610.27157#S2.F2)c\), whereas a same\-size student distilled from VGB on Dyck stays below its teacher \(Section[2](https://arxiv.org/html/2610.27157#S2), Figure[1](https://arxiv.org/html/2610.27157#S1.F1)\)\. On OOD, the student does not fully recover the teacher’s accuracy, and how close it gets depends on the distribution the traces are drawn from: traces from the ID distribution alone recover little, while mixing in a small fraction of OOD traces \(α=0\.25\\alpha\{=\}0\.25\) brings the student much closer to the teacher \(Figure[2](https://arxiv.org/html/2610.27157#S2.F2)c\)\. With this choice of training distribution, the gap between student and teacher is smaller than when the student learns VGB\. The full grid, including single\-pass accuracy and synthetic\-BT fine\-tunes, is in Table[2](https://arxiv.org/html/2610.27157#A1.T2)\(Appendix[C\.2](https://arxiv.org/html/2610.27157#A3.SS2)\)\.

### 3\.3Longer Student Chains\-of\-Thought Allow for Better Performance

Prior theoretical work has theoretically shown that increasing the length of the chain\-of\-thought also increases a student’s expressive power\([Merrill & Sabharwal, 2024](https://arxiv.org/html/2610.27157#bib.bib29);[Li et al\., 2024](https://arxiv.org/html/2610.27157#bib.bib22)\)\. In this section, we consider a modular arithmetic task and show that the longer the student’s chain\-of\-thought, the smaller the gap to the scaffolded teacher\.

Setup\.We consider modular arithmetic overℤ11\\mathbb\{Z\}\_\{11\}\([Feng et al\., 2023](https://arxiv.org/html/2610.27157#bib.bib9)\), built up from numbers, arithmetic operators, and parentheses\. A reduction step evaluates the leftmost subexpression that is ready to be computed and replaces it with its value modulo1111, until we are left with a single number\. This rule gives each expression a prescribed chain ofnopsn\_\{\\text\{ops\}\}steps\. We train a depth\-33transformer to produce only the firstLLsteps of that chain and varyLLto control how much of the computation it learns to perform\. At inference time, the scaffold samplesK=16K\{=\}16candidate next steps from the model\. An oracle checks which candidates match the next valid reduction; the scaffold commits a valid candidate, or backtracks if all1616fail\.

Results\.Figure[3](https://arxiv.org/html/2610.27157#S2.F3)b \(nops=20n\_\{\\text\{ops\}\}\{=\}20\) compares, at each training chain\-of\-thought lengthLL, the model decoded greedily with the same model used in the scaffold\. With the scaffold \(“\+ scaffold” bars\), accuracy stays high at everyLL\. Without it \(“greedy” bars\), a model trained on a short chain\-of\-thought falls far below the scaffold; its accuracy rises withLL, sharply across the phase transition marked by the dashed line betweenL=18L\{=\}18andL=19L\{=\}19, and atL=19L\{=\}19andL=20L\{=\}20it matches the scaffold\. The experiment therefore confirms that increasing the student’s expressive power through a longer chain\-of\-thought closes its gap to the scaffolded teacher\. The task definition, scaffold, and thenops=10n\_\{\\text\{ops\}\}\{=\}10curve are in Appendix[C\.3](https://arxiv.org/html/2610.27157#A3.SS3)\.

## 4An Expressivity Separation Between Scaffold and Student

The experiments in Sections[2](https://arxiv.org/html/2610.27157#S2)and[3](https://arxiv.org/html/2610.27157#S3)empirically show that a student trained on a scaffold’s traces cannot match its teacher’s accuracy when the student is only as expressive as the teacher model\. Once the student’s expressive power grows relative to the teacher’s, however—through a larger model, a longer chain\-of\-thought, or an easier task—the gap between the two narrows\. The natural hypothesis is therefore that the student cannot even*represent*what the computation of the scaffold\. This section shows this hypothesis is formally true under natural mathematical modeling abstractions from complexity theory used to understand the representational power of Transformers\([Merrill et al\., 2022](https://arxiv.org/html/2610.27157#bib.bib30);[Li et al\., 2024](https://arxiv.org/html/2610.27157#bib.bib22)\)\.

Figure 4:Illustration of the directedss–ttreachability task\.*\(a\) The path\-finding task\. \(b\) With an𝖠𝖢0\\mathsf\{AC\}^\{0\}edge oracle, a harness decides it in polynomial time\. \(c\) A model with a bounded chain\-of\-thought cannot\.*### 4\.1Setup: path\-finding in a graph

We use directedss–ttreachability \(STCON,\([Jones, 1975](https://arxiv.org/html/2610.27157#bib.bib19)\)\) as a paradigm mathematical abstraction for the task of path\-finding in a graph\. An instance consists of a directed graph with adjacency matrixA∈\{0,1\}N×NA\\in\\\{0,1\\\}^\{N\\times N\}, a sourcess, and a targettt\. The task is to decide whether there is a paths=v0→v1→⋯→vT=ts=v\_\{0\}\\to v\_\{1\}\\to\\cdots\\to v\_\{T\}=t\. Checking whether one proposed move is valid in the graph is easy: the local edge predicateEA​\(u,v\)=Au​vE\_\{A\}\(u,v\)=A\_\{uv\}is computable in𝖠𝖢0\\mathsf\{AC\}^\{0\}\. Indeed,EA\(u,v\)=⋁i,j∈\[N\]\(Ai​j∧\[u=i\]∧\[v=j\]\)E\_\{A\}\(u,v\)=\\bigvee\_\{i,j\\in\[N\]\}\(A\_\{ij\}\\land\[u=i\]\\land\[v=j\]\), which is a constant\-depth circuit of polynomial size because each equality test is an AND ofO⁡\(log⁡N\)O\(\\log N\)literals and the outer OR hasN2N^\{2\}terms\. Reachability asks whether some sequence of such moves leads tott, so it requires combining many local answers\.

Under standard complexity separation assumptions, there is a gap between the computational difficulties of checking for the validity of a single move and connectivity ofssandtt: while checking an edge is in𝖠𝖢0\\mathsf\{AC\}^\{0\}, deciding whether a path exists is𝖭𝖫\\mathsf\{NL\}\-complete even under𝖠𝖢0\\mathsf\{AC\}^\{0\}reductions\([Immerman, 1983a](https://arxiv.org/html/2610.27157#bib.bib17)\)\. Hence, assuming𝖭𝖫⊈𝖳𝖢0\\mathsf\{NL\}\\not\\subseteq\\mathsf\{TC\}^\{0\}, no𝖳𝖢0\\mathsf\{TC\}^\{0\}circuit can solve this task\. This is helpful because our lower bound uses an expressivity upper bound for the student: under standard precision and uniformity assumptions, a fixed\-depth transformer can be simulated by a𝖳𝖢0\\mathsf\{TC\}^\{0\}circuit\([Merrill et al\., 2022](https://arxiv.org/html/2610.27157#bib.bib30);[Merrill & Sabharwal, 2023](https://arxiv.org/html/2610.27157#bib.bib28)\)\. The scaffold uses the model only for the simpler queryE⁡\(A,u,v\)=Au​vE\(A,u,v\)=A\_\{uv\}, while the student must decide reachability from the full input\(A,s,t\)\(A,s,t\)\. Thus, even if we grant the student every computation in𝖳𝖢0\\mathsf\{TC\}^\{0\}, the assumed separation𝖭𝖫⊈𝖳𝖢0\\mathsf\{NL\}\\not\\subseteq\\mathsf\{TC\}^\{0\}rules out solving all reachability instances\.

In fact, the same machinery will be able to handle even chain\-of\-thought of logarithmic length\. To that end, we’ll define mathematically a model allowing chain\-of\-thought\. Fix a finite alphabetΣ\\Sigmacontaining a padding symbol⊥\\bot, and an integerc≥1c\\geq 1, and setTc​\(n\)=⌈c​log2⁡\(n\+1\)⌉\.T\_\{c\}\(n\)=\\bigl\\lceil c\\log\_\{2\}\(n\+1\)\\bigr\\rceil\.Shorter runs are padded to this length, and the final predicate ignores the padding\.

###### Definition 1\(CoT with𝖳𝖢0\\mathsf\{TC\}^\{0\}verification\)\.

A languageLLlies inCoTTc​\(n\)​\(Σ,𝖳𝖢0\)\\mathrm\{CoT\}\_\{T\_\{c\}\(n\)\}\(\\Sigma,\\mathsf\{TC\}^\{0\}\)if there are step predicatesVn,i​\(x,z<i,zi\)V\_\{n,i\}\(x,z\_\{<i\},z\_\{i\}\), for1≤i≤Tc​\(n\)1\\leq i\\leq T\_\{c\}\(n\), and a final predicateBn​\(x,z\)B\_\{n\}\(x,z\)such that

x∈L⟺there existsz∈ΣTc​\(n\)such thatBn\(x,z\)∧⋀i=1Tc​\(n\)Vn,i\(x,z<i,zi\)\.\\textstyle x\\in L\\quad\\Longleftrightarrow\\quad\\text\{there exists \}z\\in\\Sigma^\{T\_\{c\}\(n\)\}\\text\{ such that\}\\quad B\_\{n\}\(x,z\)\\land\\bigwedge\_\{i=1\}^\{T\_\{c\}\(n\)\}V\_\{n,i\}\(x,z\_\{<i\},z\_\{i\}\)\.The predicates have a common constant depth bound and a common polynomial size bound innn\. They are jointly logspace\-uniform: one logarithmic\-space procedure, given\(1n,i\)\(1^\{n\},i\), generates the circuit forVn,iV\_\{n,i\}, and another, given1n1^\{n\}, generates the circuit forBnB\_\{n\}\.

This abstraction includes deterministic autoregressive generation:Vn,iV\_\{n,i\}checks thatziz\_\{i\}is the token prescribed by the model on the preceding prefix, andBnB\_\{n\}checks whether the final answer is yes\. Allowing any transcript satisfying these checks can only enlarge the class of student computations\.

### 4\.2Harnesses Allow for Increased Expressivity

First, we show that adding logaritmically bounded CoT results in a model still in𝖳𝖢0\\mathsf\{TC\}^\{0\}, using the same transcript\-enumeration argument as[Merrill & Sabharwal \(2026b, Theorem 4 and Appendix E\)](https://arxiv.org/html/2610.27157#bib.bib27):

###### Lemma 1\(Short CoT remain in𝖳𝖢0\\mathsf\{TC\}^\{0\}\)\.

For every fixed finite alphabetΣ\\Sigmaand integerc≥1c\\geq 1,

CoTTc​\(n\)​\(Σ,𝖳𝖢0\)⊆𝖳𝖢0\.\\textstyle\\mathrm\{CoT\}\_\{T\_\{c\}\(n\)\}\(\\Sigma,\\mathsf\{TC\}^\{0\}\)\\subseteq\\mathsf\{TC\}^\{0\}\.

There are only\|Σ\|Tc​\(n\)=poly⁡\(n\)\|\\Sigma\|^\{T\_\{c\}\(n\)\}=\\mathrm\{poly\}\(n\)possible transcripts\. A circuit checks each transcript in parallel and accepts if one passes every check, increasing the depth only by two\. Appendix[D\.2](https://arxiv.org/html/2610.27157#A4.SS2)contains the complete proof\.

###### Theorem 1\(Scaffold–student separation\)\.

Assume𝖭𝖫⊈𝖳𝖢0\\mathsf\{NL\}\\not\\subseteq\\mathsf\{TC\}^\{0\}\. ForSTCONon anNN\-vertex graph given by its adjacency matrixAA, the following hold:

1. \(i\)The local predicateE⁡\(A,u,v\)=Au​vE\(A,u,v\)=A\_\{uv\}lies in𝖠𝖢0\\mathsf\{AC\}^\{0\}\. GivenN,s,tN,s,tand oracle access toEAE\_\{A\}, a deterministic polynomial\-time breadth\-first\-search scaffold decides reachability using at mostN2N^\{2\}oracle calls andO⁡\(N\)O\(N\)bits of external state\.
2. \(ii\)For every fixed finite alphabetΣ\\Sigmaand integerc≥1c\\geq 1, STCON∉CoTTc​\(n\)​\(Σ,𝖳𝖢0\),Tc​\(n\)=⌈c​log2⁡\(n\+1\)⌉,\\textstyle\\textsc\{STCON\}\\notin\\mathrm\{CoT\}\_\{T\_\{c\}\(n\)\}\(\\Sigma,\\mathsf\{TC\}^\{0\}\),\\qquad T\_\{c\}\(n\)=\\lceil c\\log\_\{2\}\(n\+1\)\\rceil,wherennis the encoded input length and the predicates satisfy Definition[1](https://arxiv.org/html/2610.27157#Thmdefinition1)\.

Part \(i\) is the standard breadth\-first\-search algorithm\. For part \(ii\), Lemma[1](https://arxiv.org/html/2610.27157#Thmlemma1)would put a successful student in𝖳𝖢0\\mathsf\{TC\}^\{0\}\. Composing it with the uniform𝖠𝖢0\\mathsf\{AC\}^\{0\}reductions toSTCONwould then put every language in𝖭𝖫\\mathsf\{NL\}in𝖳𝖢0\\mathsf\{TC\}^\{0\}, contradicting the assumption\. The full proof is in Appendix[D\.3](https://arxiv.org/html/2610.27157#A4.SS3)\.

The theorem can be seen as giving an example of a natural task on which a scaffold simulating a search procedure combines elementary model calls into a computation that no student in the stated class can reproduce on all inputs, even withO⁡\(log⁡n\)O\(\\log n\)chain\-of\-thought tokens\. This is a representational obstruction to internalization\. Commensurate with the experiments, longer chains of thought or increase in depth can change asymptotic expressive power\([Merrill & Sabharwal, 2024](https://arxiv.org/html/2610.27157#bib.bib29);[Merrill & Sabharwal, 2026b](https://arxiv.org/html/2610.27157#bib.bib27)\)\.

## 5Agentic Scaffolding

This section moves from simple, controlled tasks \(Dyck, Sokoban\) to more realistic ones: aBranchingscaffold\([Bateni et al\., 2025](https://arxiv.org/html/2610.27157#bib.bib4)\)applied to competition mathematics problems\. We show that the gap between student and teacher widens as the number of calls grows, thereby demonstrating the broader applicability of our earlier theory and experiments\.

Figure 5:Larger trees widen the gap\.*\(a\) Teacher and student accuracy on Qwen3\-1\.7B per tree shape\(d,L\)\(d,L\)\. \(b\) Trace length and gain over the base model on QED\-Nano\.*Setup\.The base modelMMis Qwen3\-1\.7B \(enable\_thinking=False\); the task is DAPO\-Math\-17k, with correctness judged bymath\-verifyon the last`\\boxed\{\.\.\.\}`\. We distill from a15001500\-problem pool of traces \(cached pass@1≈0\.30\\approx 0\.30\) and evaluate on a disjoint500500\-problem set \(pass@1≈0\.31\\approx 0\.31\)\.

Branching scaffold\.The Branching scaffold callsMMin a depth\-LLtree: the leaves callMMon the question at temperature1\.01\.0, and each internal node callsMMonce to synthesize a*fresh*solution from its children\. The canonical𝐤𝐬=\[3,3\]\\mathbf\{ks\}\{=\}\[3,3\]tree uses99leaves→3\\to 3aggregators→1\\to 1root \(1313calls, no verifier\)\. The distillation\-knob ablations use the smaller𝐤𝐬=\[3\]\\mathbf\{ks\}\{=\}\[3\]variant \(33leaves\+1\+1root,44calls\); the shape sweep varies the topology of the full tree\. We flatten the transcript \(\#\# Attempt/\#\# Final Solution\) and LoRA fine\-tuneMMto emit the whole trace, and hence the answer, in one autoregressive rollout, keeping only root\-correct runs\.

Experimental Result\.We distill Branching trees of increasing size into a same\-size student, varying the number of childrend∈\{2,3,4\}d\\in\\\{2,3,4\\\}and the depthL∈\{1,2,3\}L\\in\\\{1,2,3\\\}\(Figure[5](https://arxiv.org/html/2610.27157#S5.F5)a; full grid in Figure[12](https://arxiv.org/html/2610.27157#A1.F12)\)\. WhenddandLLare small \(left of Figure[5](https://arxiv.org/html/2610.27157#S5.F5)a\), the student recovers most of the teacher’s gain over the base model in one autoregressive rollout\. This agrees with Section[3\.2](https://arxiv.org/html/2610.27157#S3.SS2)\(Figure[2](https://arxiv.org/html/2610.27157#S2.F2)c\), where a simpler backtracking rule narrows the teacher–student gap\. AsddandLLgrow \(right of Figure[5](https://arxiv.org/html/2610.27157#S5.F5)a\), the teacher keeps improving as calls are added, while the unscaffolded student does not, and it collapses once the tree reaches depth three\. Thus, larger teacher trees are harder to reproduce with the tested same\-size students\.

Ablation\.We compare changes to the student backbone, the number of trainable parameters, and the data mixture \(full results in Appendix[E\.1](https://arxiv.org/html/2610.27157#A5.SS1)\)\.

∙\\bullet*Backbone size has the larger effect\.*We compare enlarging the backbone with increasing LoRA rank and with full fine\-tuning at fixed backbone size\. Moving from the1\.71\.7B to the44B backbone closes the gap and surpasses the teacher \(Figure[13](https://arxiv.org/html/2610.27157#A1.F13)a\), whereas raising the LoRA rank, or fine\-tuning every weight, makes little difference \(Figure[13](https://arxiv.org/html/2610.27157#A1.F13)b\)\.

∙\\bullet*The tested clean\-data mixtures do not close the gap\.*The student tolerates about half clean data, then starts to fall back toward the clean\-data baseline, and no mixture can reache the teacher’s performance \(Figure[12](https://arxiv.org/html/2610.27157#A1.F12)a\)\.

A harness on a strong prover relative to model size\.Unlike the off\-the\-shelf Qwen3\-1\.7B used above, QED\-Nano\([Qu et al\., 2026](https://arxiv.org/html/2610.27157#bib.bib32)\)is a44B prover built specifically for Olympiad proofs, trained on solutions from a685685B model and then refined by reinforcement learning, which makes it unusually strong relative to its size\. After RL, the released checkpoint is used in a multi\-call scaffold at evaluation time, and its strongest reported results use that scaffold\. We put Branching on that same RL checkpoint and sweep the tree shape, scoring both arms of the same trace on300300problems from the model’s own RL corpus\. Across the shapes that stay within seven calls in total, none achieves a gain whose confidence interval is above zero \(Figure[5](https://arxiv.org/html/2610.27157#S5.F5)b, Appendix[E\.2](https://arxiv.org/html/2610.27157#A5.SS2)\)\. A clear gain does appear once we go tod=3d\{=\}3,L=3L\{=\}3, but by then the estimated total trace length is more than five times the context window considered for distillation\. Within this sweep, the shape with a clear gain also has the longest estimated trace\. This creates an obstacle to distilling the complete trace within that context budget\. We do not train a QED\-Nano student in this experiment\.

## 6Conclusion

We studied when a model can internalize the benefits of an inference\-time harness\. Across controlled tasks and agentic scaffolds, we find that same\-size students remain below their teachers in our experiments, while larger students, longer chains of thought, and simpler scaffolds can narrow or close the gap\. We formalize a representational obstruction that explains these observations: under𝖭𝖫⊈𝖳𝖢0\\mathsf\{NL\}\\not\\subseteq\\mathsf\{TC\}^\{0\}, a scaffold simulating a search procedure exceeds the expressive power of a short\-CoT student class\. We thus clarify computational benefits of scaffolds\.

### AI use statement

We did not use AI to plan or design the experiments in this work\. However, we used AI tools for coding and for writing assistance\. We have reviewed all AI\-assisted work and take responsibility for the final content of this paper\.

### Acknowledgements

A\.R\. and J\.G\. are supported in part by NSF awards IIS\-2211907, CCF\-2238523, IIS\-2403275, an Amazon Research Award, ONR award N000142512124, a Google Research Scholar Award, and an OpenAI Superalignment Fast Grant\. A\.B\. was supported in part by a research grant from Schmidt Sciences\.

## References

- Agarwal et al\. \(2024\)Rishabh Agarwal, Nino Vieillard, Yongchao Zhou, Piotr Stanczyk, Sabela Ramos Garea, Matthieu Geist, and Olivier Bachem\.On\-policy distillation of language models: Learning from self\-generated mistakes\.In*International Conference on Learning Representations*, volume 2024, pp\. 21246–21263, 2024\.
- Amiri et al\. \(2025\)Alireza Amiri, Xinting Huang, Mark Rofin, and Michael Hahn\.Lower bounds for chain\-of\-thought reasoning in hard\-attention transformers\.2025\.
- Arora et al\. \(2009\)Sanjeev Arora, Boaz Barak, et al\.*Computational complexity: a modern approach*, volume 1\.Cambridge University Press Cambridge, 2009\.
- Bateni et al\. \(2025\)MohammadHossein Bateni, Vincent Cohen\-Addad, Yuzhou Gu, Silvio Lattanzi, Simon Meierhans, and Christopher Mohri\.Algorithmic thinking theory\.*arXiv preprint arXiv:2512\.04923*, 2025\.
- Brown et al\. \(2024\)Bradley Brown, Jordan Juravsky, Ryan Ehrlich, Ronald Clark, Quoc V Le, Christopher Ré, and Azalia Mirhoseini\.Large language monkeys: Scaling inference compute with repeated sampling\.*arXiv preprint arXiv:2407\.21787*, 2024\.
- Cobbe et al\. \(2021\)Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, et al\.Training verifiers to solve math word problems\.*arXiv preprint arXiv:2110\.14168*, 2021\.
- Cundy & Ermon \(2024\)Chris Cundy and Stefano Ermon\.Sequencematch: Imitation learning for autoregressive sequence modelling with backtracking\.In*International Conference on Learning Representations*, volume 2024, pp\. 3387–3407, 2024\.
- Du et al\. \(2023\)Yilun Du, Shuang Li, Antonio Torralba, Joshua B Tenenbaum, and Igor Mordatch\.Improving factuality and reasoning in language models through multiagent debate\.2023\.
- Feng et al\. \(2023\)Guhao Feng, Bohang Zhang, Yuntian Gu, Haotian Ye, Di He, and Liwei Wang\.Towards revealing the mystery behind chain of thought: a theoretical perspective\.volume 36, pp\. 70757–70798, 2023\.
- Feng et al\. \(2026\)Tony Feng, Trieu H Trinh, Garrett Bingham, Dawsen Hwang, Yuri Chervonyi, Junehyuk Jung, Joonkyung Lee, Carlo Pagano, Sang\-hyun Kim, Federico Pasqualotto, et al\.Towards autonomous mathematics research\.*arXiv preprint arXiv:2602\.10177*, 2026\.
- Foster et al\. \(2024\)Dylan J Foster, Adam Block, and Dipendra Misra\.Is behavior cloning all you need? understanding horizon in imitation learning\.*Advances in Neural Information Processing Systems*, 37:120602–120666, 2024\.
- Gandhi et al\. \(2024\)Kanishk Gandhi, Denise Lee, Gabriel Grand, Muxin Liu, Winson Cheng, Archit Sharma, and Noah D Goodman\.Stream of search \(sos\): Learning to search in language\.2024\.
- Hao et al\. \(2023\)Shibo Hao, Yi Gu, Haodi Ma, Joshua Hong, Zhen Wang, Daisy Wang, and Zhiting Hu\.Reasoning with language model is planning with world model\.In*Proceedings of the 2023 conference on empirical methods in natural language processing*, pp\. 8154–8173, 2023\.
- Hart et al\. \(1968\)Peter E Hart, Nils J Nilsson, and Bertram Raphael\.A formal basis for the heuristic determination of minimum cost paths\.*IEEE transactions on Systems Science and Cybernetics*, 4\(2\):100–107, 1968\.
- Hinton et al\. \(2015\)Geoffrey Hinton, Oriol Vinyals, and Jeff Dean\.Distilling the knowledge in a neural network\.*arXiv preprint arXiv:1503\.02531*, 2015\.
- Huang & Yang \(2025\)Yichen Huang and Lin F Yang\.Winning gold at imo 2025 with a model\-agnostic verification\-and\-refinement pipeline\.*arXiv preprint arXiv:2507\.15855*, 2025\.
- Immerman \(1983a\)Neil Immerman\.Languages which capture complexity classes\.pp\. 347–354, 1983a\.
- Immerman \(1983b\)Neil Immerman\.Languages which capture complexity classes\.pp\. 347–354, 1983b\.
- Jones \(1975\)Neil D Jones\.Space\-bounded reducibility among combinatorial problems\.*Journal of Computer and System Sciences*, 11\(1\):68–85, 1975\.
- Lehnert et al\. \(2024\)Lucas Lehnert, Sainbayar Sukhbaatar, DiJia Su, Qinqing Zheng, Paul Mcvay, Michael Rabbat, and Yuandong Tian\.Beyond a\*: Better planning with transformers via search dynamics bootstrapping\.2024\.
- Li et al\. \(2026\)Yanhong Li, Anej Svete, Ashish Sabharwal, and William Merrill\.Efficiently representing algorithms with chain\-of\-thought transformers\.*arXiv preprint arXiv:2606\.19697*, 2026\.
- Li et al\. \(2024\)Zhiyuan Li, Hong Liu, Denny Zhou, and Tengyu Ma\.Chain of thought empowers transformers to solve inherently serial problems\.In*International Conference on Learning Representations*, volume 2024, pp\. 11911–11943, 2024\.
- Lightman et al\. \(2024\)Hunter Lightman, Vineet Kosaraju, Yuri Burda, Harrison Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, Ilya Sutskever, and Karl Cobbe\.Let’s verify step by step\.In*International Conference on Learning Representations*, volume 2024, pp\. 39578–39601, 2024\.
- Lu & Lab \(2025\)Kevin Lu and Thinking Machines Lab\.On\-policy distillation\.*Thinking Machines Lab: Connectionism*, 2025\.doi:10\.64434/tml\.20251026\.https://thinkingmachines\.ai/blog/on\-policy\-distillation\.
- Madaan et al\. \(2023\)Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, et al\.Self\-refine: Iterative refinement with self\-feedback\.volume 36, pp\. 46534–46594, 2023\.
- Merrill & Sabharwal \(2026a\)Will Merrill and Ashish Sabharwal\.A little depth goes a long way: The expressive power of log\-depth transformers\.volume 38, pp\. 95315–95339, 2026a\.
- Merrill & Sabharwal \(2026b\)Will Merrill and Ashish Sabharwal\.A little depth goes a long way: The expressive power of log\-depth transformers\.volume 38, pp\. 95315–95339, 2026b\.
- Merrill & Sabharwal \(2023\)William Merrill and Ashish Sabharwal\.The parallelism tradeoff: Limitations of log\-precision transformers\.*Transactions of the Association for Computational Linguistics*, 11:531–545, 2023\.
- Merrill & Sabharwal \(2024\)William Merrill and Ashish Sabharwal\.The expressive power of transformers with chain of thought\.In*International Conference on Learning Representations*, volume 2024, pp\. 7690–7706, 2024\.
- Merrill et al\. \(2022\)William Merrill, Ashish Sabharwal, and Noah A Smith\.Saturated transformers are constant\-depth threshold circuits\.*Transactions of the Association for Computational Linguistics*, 10:843–856, 2022\.
- Mirtaheri et al\. \(2026\)Parsa Mirtaheri, Ezra Edelman, Samy Jelassi, Eran Malach, and Enric Boix\-Adsera\.Let me think\! a long chain of thought can be worth exponentially many short ones\.volume 38, pp\. 166795–166826, 2026\.
- Qu et al\. \(2026\)Yuxiao Qu, Amrith Setlur, Jasper Dekoninck, Edward Beeching, Jia Li, Ian Wu, Lewis Tunstall, Aviral Kumar, et al\.Qed\-nano: Teaching a tiny model to prove hard theorems\.*arXiv preprint arXiv:2604\.04898*, 2026\.
- Rohatgi et al\. \(2025\)Dhruv Rohatgi, Adam Block, Audrey Huang, Akshay Krishnamurthy, and Dylan J Foster\.Computational\-statistical tradeoffs at the next\-token prediction barrier: Autoregressive and imitation learning under misspecification\.2025\.
- Rohatgi et al\. \(2026\)Dhruv Rohatgi, Abhishek Shetty, Donya Saless, Yuchen Li, Ankur Moitra, Andrej Risteski, and Dylan Foster\.Taming imperfect process verifiers: A sampling perspective on backtracking\.In*International Conference on Learning Representations*, volume 2026, pp\. 128647–128722, 2026\.
- Ross et al\. \(2011\)Stéphane Ross, Geoffrey Gordon, and Drew Bagnell\.A reduction of imitation learning and structured prediction to no\-regret online learning\.In*Proceedings of the fourteenth international conference on artificial intelligence and statistics*, pp\. 627–635\. JMLR Workshop and Conference Proceedings, 2011\.
- Saha et al\. \(2024\)Swarnadeep Saha, Omer Levy, Asli Celikyilmaz, Mohit Bansal, Jason Weston, and Xian Li\.Branch\-solve\-merge improves large language model evaluation and generation\.In*Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies \(Volume 1: Long Papers\)*, pp\. 8352–8370, 2024\.
- Shinn et al\. \(2023\)Noah Shinn, Federico Cassano, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao\.Reflexion: Language agents with verbal reinforcement learning\.volume 36, pp\. 8634–8652, 2023\.
- Snell et al\. \(2025\)Charlie Snell, Jaehoon Lee, Kelvin Xu, and Aviral Kumar\.Scaling llm test\-time compute optimally can be more effective than scaling parameters for reasoning\.In*International Conference on Learning Representations*, volume 2025, pp\. 10131–10165, 2025\.
- Sriraman et al\. \(2026\)Ved Sriraman, Peihan Liu, Daniel Hsu, and Adam Block\.Behavior cloning is not all you need: The optimality of on\-policy distillation for noisy expert feedback\.*arXiv preprint arXiv:2606\.30923*, 2026\.
- Tsilivis et al\. \(2026\)Nikolaos Tsilivis, Nirmit Joshi, Marko Medvedev, Julia Kempe, and Nati Srebro\.Learning through internalization\.*arXiv preprint arXiv:2606\.20937*, 2026\.
- Vollmer \(1999\)Heribert Vollmer\.*Introduction to circuit complexity: a uniform approach*\.Springer Science & Business Media, 1999\.
- Wang et al\. \(2022\)Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc Le, Ed Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou\.Self\-consistency improves chain of thought reasoning in language models\.2022\.
- Yang et al\. \(2024\)John Yang, Carlos Jimenez, Alexander Wettig, Kilian Lieret, Shunyu Yao, Karthik Narasimhan, and Ofir Press\.Swe\-agent: Agent\-computer interfaces enable automated software engineering\.volume 37, pp\. 50528–50652, 2024\.
- Yao et al\. \(2022\)Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao\.React: Synergizing reasoning and acting in language models\.2022\.
- Yao et al\. \(2023\)Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan\.Tree of thoughts: Deliberate problem solving with large language models\.volume 36, pp\. 11809–11822, 2023\.
- Yu et al\. \(2024\)Ping Yu, Jing Xu, Jason Weston, and Ilia Kulikov\.Distilling system 2 into system 1\.*arXiv preprint arXiv:2407\.06023*, 2024\.
- \(47\)Alex L Zhang, Zhening Li, and Omar Khattab\.The mismanaged geniuses hypothesis, 2026\.
- Zhang et al\. \(2026\)Huaqing Zhang, Jingchu Gai, Juno Kim, Bingbin Liu, and Andrej Risteski\.When does online imitation learning help in llm post\-training? the role of \(non\-\) realizability beyond horizon\.*arXiv preprint arXiv:2606\.30445*, 2026\.

## Appendix: contents

## Appendix ARelated Work

Figure 6:No fine\-tuning setting reaches the teacher\.*A same\-size student fine\-tuned on VGB traces \(Sokoban, MC\-oracle score, score tokens kept\)\. Top row: clean\-data ratio \(a\), number of iterations \(b\) and number of traces \(c\)\. Bottom row: the clean\-data sweep repeated with training puzzles drawn fromPαP\_\{\\alpha\}, forα=0\.25\\alpha=0\.25\(d\),0\.500\.50\(e\) and0\.750\.75\(f\)\. Dashed lines mark the teacher\.*Figure 7:Fine\-tuned A\* students stay at the base model\.*Fine\-tuning the base model on A\* traces \(Sokoban\)\. For every clean\-data ratio, number of iterations and amount of data, the student stays close to the base model and well below the teacher \(dashed\)\.*Figure 8:From\-scratch students stay far below the teacher\.*Students trained from scratch, with VGB in the top row and A\* search in the bottom row\. No seed, trace source or rough change in size brings either student close to its teacher \(dashed; VGB0\.765/0\.6050\.765/0\.605, A\*0\.99/0\.980\.99/0\.98\)\.*Table 1:*The1212student scales of Section[3\.1](https://arxiv.org/html/2610.27157#S3.SS1), pluslarge\. VGB is run on the88scales fromtinytom\_plus; A\* search and Dyck use all of them\.*Figure 9:Larger students close the gap on Sokoban\.*Best accuracy at each scale in the two Sokoban settings\.*Figure 10:Accuracy increases with size at every clean ratio and checkpoint\.*The sweeps of Figure[9](https://arxiv.org/html/2610.27157#A1.F9)shown separately for each clean\-data ratio and each checkpoint\. Within each block, the rows are A\*, VGB\-Sokoban and VGB\-Dyck from top to bottom\.*Table 2:*Full results of simple\-BT distillation on Dyck, in one pass and with the student’s own<BT\>tokens\. Figure[2](https://arxiv.org/html/2610.27157#S2.F2)c in the main text uses the<BT\>rows of the distilled students\.*Figure 11:The same phase transition on an easier task\.*\(a\) The verifier\-backtracking harness withK=16K\{=\}16\. \(b\) Accuracy against the training chain\-of\-thought lengthLLfornops=10n\_\{\\mathrm\{ops\}\}\{=\}10\.*Figure 12:No distillation setting reaches the teacher, and only the teacher gains from more calls\.*Branching distillation on Qwen3\-1\.7B\. Top row: clean\-data ratio \(a\), number of traces \(b\) and number of epochs \(c\); the teacher is dashed and the base model dotted\. Bottom row: number of calls per problem for every tree shape\(d,L\)\(d,L\)\(d\), and accuracy with the shapes sorted by the teacher’s accuracy \(e\)\.*Table 3:*The five tree shapes we run and the median length of their full traces\.*Figure 13:A larger backbone closes the gap\.*\(a\) Student accuracy with the1\.71\.7B and44B backbones\. \(b\) Student accuracy with LoRA ranks1616and6464and with full fine\-tuning\. \(c\) Gain of the harness over the base model on QED\-Nano for each shape\. Only the4040\-call shape has a gain whose interval excludes zero, and its trace is much longer than the context window\.*Agents and harnesses\.A lot of recent work on agents keeps the language model fixed and improves the harness around it\. Some harnesses let the model use tools and see feedback from an environment\([Yao et al\., 2022](https://arxiv.org/html/2610.27157#bib.bib44)\), or give it an interface for working with software\([Yang et al\., 2024](https://arxiv.org/html/2610.27157#bib.bib43)\)\. Others ask the model to check and fix its own answers\([Madaan et al\., 2023](https://arxiv.org/html/2610.27157#bib.bib25);[Shinn et al\., 2023](https://arxiv.org/html/2610.27157#bib.bib37)\), or let several copies of the model debate\([Du et al\., 2023](https://arxiv.org/html/2610.27157#bib.bib8)\)\. A task can also be split into parts whose answers are then combined\([Saha et al\., 2024](https://arxiv.org/html/2610.27157#bib.bib36)\)\. Branching combines sampled solutions in a tree\([Bateni et al\., 2025](https://arxiv.org/html/2610.27157#bib.bib4)\)\. Strong results in math have also come from harnesses that let strong models generate and check solutions\([Huang & Yang, 2025](https://arxiv.org/html/2610.27157#bib.bib16);[Feng et al\., 2026](https://arxiv.org/html/2610.27157#bib.bib10);[Qu et al\., 2026](https://arxiv.org/html/2610.27157#bib.bib32)\)\. It is still not well understood why such simple harnesses help models that are already strong\. One idea is that a harness breaks the task into smaller, meaningful steps\([Zhang et al\.,](https://arxiv.org/html/2610.27157#bib.bib47)\)\. We try to give clearer answers, using both experiments and theory\. We also ask a different question\. Instead of building a better harness, we ask whether the gains from a harness can be moved into the weights of a student of the same size as the base model\. We find that the model’s expressive power can stand in the way\.

Expressive power of transformers and chain\-of\-thought\.Several papers use circuit complexity to describe what transformers can compute\. A transformer with a fixed number of layers and saturated or log\-precision attention can only compute functions in the class𝖳𝖢0\\mathsf\{TC\}^\{0\}\([Merrill et al\., 2022](https://arxiv.org/html/2610.27157#bib.bib30);[Merrill & Sabharwal, 2023](https://arxiv.org/html/2610.27157#bib.bib28)\)\. Writing out intermediate reasoning steps lets a transformer compute more\([Feng et al\., 2023](https://arxiv.org/html/2610.27157#bib.bib9);[Li et al\., 2024](https://arxiv.org/html/2610.27157#bib.bib22);[Merrill & Sabharwal, 2024](https://arxiv.org/html/2610.27157#bib.bib29)\), and some tasks need long chains\-of\-thought\([Amiri et al\., 2025](https://arxiv.org/html/2610.27157#bib.bib2)\)\. Most relevant to our theory,[Merrill & Sabharwal \(2026b, Theorem 4\)](https://arxiv.org/html/2610.27157#bib.bib27)show that a chain\-of\-thought withO⁡\(log⁡n\)O\(\\log n\)steps keeps a transformer inside logspace\-uniform𝖳𝖢0\\mathsf\{TC\}^\{0\}\. They also show that a transformer whose depth grows with the input can decide whether one node of a directed graph can reach another\. Our Lemma[1](https://arxiv.org/html/2610.27157#Thmlemma1)uses their argument, which goes through all possible chains\-of\-thought\.[Li et al\. \(2026\)](https://arxiv.org/html/2610.27157#bib.bib21)study how a long enough chain\-of\-thought can run standard algorithms, such as graph search\.[Mirtaheri et al\. \(2026\)](https://arxiv.org/html/2610.27157#bib.bib31)look at a setting close to our formal example\. They show that one polynomially long chain\-of\-thought can solve a connectivity task on undirected graphs that polynomially many short chains, combined by majority vote, cannot solve\. Their result assumes a standard conjecture from circuit complexity\. Our theorem puts together the known limit for short chains\-of\-thought and the fact that directed reachability is hard\. This gives a formal reason why a student may fail to learn what a harness does\. Our experiments study the same question in practice, by distilling search and aggregation traces\.

Verifiers and inference\-time search\.A simple way to use more compute at inference time is to sample several solutions and pick one, either with a verifier or by majority vote\([Cobbe et al\., 2021](https://arxiv.org/html/2610.27157#bib.bib6);[Wang et al\., 2022](https://arxiv.org/html/2610.27157#bib.bib42);[Brown et al\., 2024](https://arxiv.org/html/2610.27157#bib.bib5)\)\. Process reward models score every step of a solution, which gives more detailed feedback than a verifier that only checks the final answer\([Lightman et al\., 2024](https://arxiv.org/html/2610.27157#bib.bib23)\)\. When test\-time compute is used well, a small model can sometimes beat a larger one\([Snell et al\., 2025](https://arxiv.org/html/2610.27157#bib.bib38)\)\. Other methods search over partial solutions\. They use tree search guided by the model\([Yao et al\., 2023](https://arxiv.org/html/2610.27157#bib.bib45);[Hao et al\., 2023](https://arxiv.org/html/2610.27157#bib.bib13)\), classical planning such as A\* search\([Hart et al\., 1968](https://arxiv.org/html/2610.27157#bib.bib14)\), or backtracking guided by an imperfect verifier\([Rohatgi et al\., 2026](https://arxiv.org/html/2610.27157#bib.bib34)\)\. Another line of work teaches the model to do the search on its own\. These methods train on written\-out search traces\([Gandhi et al\., 2024](https://arxiv.org/html/2610.27157#bib.bib12);[Lehnert et al\., 2024](https://arxiv.org/html/2610.27157#bib.bib20)\), add a backtracking action\([Cundy & Ermon, 2024](https://arxiv.org/html/2610.27157#bib.bib7)\), or distill the output of a harness into a single pass\([Yu et al\., 2024](https://arxiv.org/html/2610.27157#bib.bib46)\)\. Our experiments also train on such traces\. We find that a student of the same size as the base model does not reach its teacher\. The gap gets smaller as the student becomes more expressive relative to the task\. The work most similar to ours is[Tsilivis et al\. \(2026\)](https://arxiv.org/html/2610.27157#bib.bib40), who study how a transformer can absorb an explicit procedure into its weights\. They have the model absorb its own chain\-of\-thought tokens, while we have it absorb a harness that calls the model many times and keeps state between calls\. They also prove that gradient descent, with a curriculum that slowly removes the chain\-of\-thought, learns to compute sparse parities in a single forward pass\. We instead show a limit on what a same\-size student can represent\.

Distillation\.We conclude that a harness cannot be fully moved into the weights\. This depends partly on one assumption: in our setting, what limits*distillation*\([Hinton et al\., 2015](https://arxiv.org/html/2610.27157#bib.bib15)\)is mainly the student’s capacity\. Many forms of distillation have been studied\([Agarwal et al\., 2024](https://arxiv.org/html/2610.27157#bib.bib1);[Lu & Lab, 2025](https://arxiv.org/html/2610.27157#bib.bib24)\)\. We use the simplest one, which is supervised fine\-tuning on the teacher’s outputs\. When capacity is not a constraint, this method is provably optimal\([Foster et al\., 2024](https://arxiv.org/html/2610.27157#bib.bib11)\)\. Other papers show where it breaks down when capacity is limited\([Ross et al\., 2011](https://arxiv.org/html/2610.27157#bib.bib35);[Rohatgi et al\., 2025](https://arxiv.org/html/2610.27157#bib.bib33);[Sriraman et al\., 2026](https://arxiv.org/html/2610.27157#bib.bib39);[Zhang et al\., 2026](https://arxiv.org/html/2610.27157#bib.bib48)\)\. Together, these results suggest that distilling a harness with SFT is a reasonable way to measure how much the student’s capacity holds it back\.

## Appendix BSupplementary Details for Section[2](https://arxiv.org/html/2610.27157#S2)

In this appendix we describe the two harnesses and their traces, how we train the base models and the students, and all the ablations for Section[2](https://arxiv.org/html/2610.27157#S2)\.

### B\.1Harness Details

We first describe the two harnesses from Section[2](https://arxiv.org/html/2610.27157#S2)and how we write their traces for the student\.

#### B\.1\.1VGB \(probabilistic backtracking\)

At a prefixss, the base model proposes an actiona∼M\(⋅∣s\)a\\sim M\(\\cdot\\mid s\), and the harness then either commitsaaor emits a backtrack token<BT\>:

pretract=max⁡\(ε,1−V~​\(s,a\)V~​\(s\)\),\{commit​aw\.p\.​1−pretract,<BT\>w\.p\.​pretract\.\\textstyle p\_\{\\text\{retract\}\}\\;=\\;\\max\\\!\\Big\(\\varepsilon,\\;1\-\\tfrac\{\\widetilde\{V\}\(s,a\)\}\{\\widetilde\{V\}\(s\)\}\\Big\),\\qquad\\begin\{cases\}\\text\{commit \}a&\\text\{w\.p\. \}1\-p\_\{\\text\{retract\}\},\\\\\[2\.0pt\] \\texttt\{<BT\>\}\{\}&\\text\{w\.p\. \}p\_\{\\text\{retract\}\}\.\\end\{cases\}
The scoreV~\\widetilde\{V\}\.Following Eq\. \(3\) of[Rohatgi et al\. \(2026\)](https://arxiv.org/html/2610.27157#bib.bib34),V~​\(s\)\\widetilde\{V\}\(s\)is the probability that the base model, starting fromss, finishes with a valid sequence:

V~\(s\):=𝔼τ∼M\(⋅∣s\)\[𝟏\[valid\(s∘τ\)\]\]∈\[0,1\],V~\(s,a\):=V~\(s∘a\)\.\\textstyle\\widetilde\{V\}\(s\)\\;:=\\;\\mathbb\{E\}\_\{\\tau\\sim M\(\\cdot\\mid s\)\}\\big\[\\mathbf\{1\}\[\\text\{valid\}\(s\\circ\\tau\)\]\\big\]\\in\[0,1\],\\qquad\\widetilde\{V\}\(s,a\)\\;:=\\;\\widetilde\{V\}\(s\\circ a\)\.We estimate this probability in two ways:

- •*MC oracle\.*We sampleKKcompletionsτ1,…,τK\\tau\_\{1\},\\dots,\\tau\_\{K\}ofssfrom the base model and take the fraction that are valid,V^K​\(s\)=1K​∑k=1K𝟏​\[valid​\(s∘τk\)\]\\widehat\{V\}\_\{K\}\(s\)=\\tfrac\{1\}\{K\}\\sum\_\{k=1\}^\{K\}\\mathbf\{1\}\[\\text\{valid\}\(s\\circ\\tau\_\{k\}\)\]\. We useK=1K\{=\}1when generating traces andK=1000K\{=\}1000for evaluation\.
- •*LearnedV^\\widehat\{V\}\.*We train a small classifier that reads a prefixssand predictsV~​\(s\)\\widetilde\{V\}\(s\)\. To get a training label forss, we let the base model completessonce and record whether the result is valid\. The classifier is trained on these labels with binary cross\-entropy, as in Eq\. \(4\) of[Rohatgi et al\. \(2026\)](https://arxiv.org/html/2610.27157#bib.bib34)\. At inference time, we call the classifier once instead of samplingKKcompletions\.

Trace format\.A trace starts with the board, then lists the steps of the search, and ends with<EOS\>\. Each step takes two tokens\. The first is the verifier score at that step, rounded to one of1010levels and written as a token<Vq\>\. The second is the harness’s decision: the action it commits, or<BT\>\. Because the score comes right before each decision, the student can see what made the harness backtrack\. In total the vocabulary has2727tokens:

<board\>⏟prompt​\|<Vq\><action\_or\_BT\>⋯<Vq\><action\_or\_BT\>⏟search log \(2 tokens / step\)\|​<EOS\>⏟end\.\\textstyle\\underbrace\{\\texttt\{<board\>\}\}\_\{\\text\{prompt\}\}\\;\\Big\|\\;\\underbrace\{\\texttt\{<V$\{\}\_\{q\}$\>\}\\;\\texttt\{<action\\\_or\\\_BT\>\}\\;\\cdots\\;\\texttt\{<V$\{\}\_\{q\}$\>\}\\;\\texttt\{<action\\\_or\\\_BT\>\}\}\_\{\\text\{search log \(2 tokens / step\)\}\}\\;\\Big\|\\;\\underbrace\{\\texttt\{<EOS\>\}\}\_\{\\text\{end\}\}\.In the ablations we compare four versions of these traces\. They differ in two ways: the harness scores prefixes with either the learnedV^\\widehat\{V\}or the MC oracle, and the score tokens are either kept in the trace or removed\. Without score tokens, the student sees only the actions and the backtracks, and has to work out by itself when to backtrack\.

#### B\.1\.2A\* search \(LM\-pruned\)

The A\* harness is ordinary A\* search, with the base model used to prune it\. Like any A\* search, it keeps a queue of board states ordered byf=g\+hf=g\+h, whereggcounts the moves made so far andhhis the Manhattan\-distance heuristic\. At each step it takes the state with the smallestffout of the queue\. Plain A\* search would then put every state that is one legal move away into the queue\. Our harness puts in only two of them: the states reached by the two moves that the base model is most likely to make there\. With this pruning the harness still finds optimal plans, and its traces are about36%36\\%shorter than those of plain A\* search\.

Trace format\.The trace lists every state that the search creates \(<CREATE\>, followed by the state’s coordinates and its values ofgg,hhandff\) or closes \(<CLOSE\>, followed by its coordinates\), and it ends with the plan after<PLAN\>\. With these markers and the number tokens, the vocabulary has4545tokens:

<board\>⏟prompt​\|\(<CREATE\>​p​r​p​c​b​r​b​c​g​h​f∣<CLOSE\>​p​r​p​c​b​r​b​c\)∗⏟search log\|​<PLAN\>a1a2⋯<EOS\>⏟final plan\.\\textstyle\\small\\underbrace\{\\texttt\{<board\>\}\}\_\{\\text\{prompt\}\}\\;\\Big\|\\;\\underbrace\{\\big\(\\texttt\{<CREATE\>\}\\,pr\\,pc\\,br\\,bc\\,g\\,h\\,f\\;\\mid\\;\\texttt\{<CLOSE\>\}\\,pr\\,pc\\,br\\,bc\\big\)^\{\*\}\}\_\{\\text\{search log\}\}\\;\\Big\|\\;\\underbrace\{\\texttt\{<PLAN\>\}\\,a\_\{1\}a\_\{2\}\\cdots\\texttt\{<EOS\>\}\}\_\{\\text\{final plan\}\}\.At test time the student writes the whole trace by itself with greedy decoding, without calling the base model, and we check whether the plan after<PLAN\>solves the puzzle\.

### B\.2Experimental Details

Architecture\.Unless we say otherwise, the base model, the model inside the teacher and the same\-size student are the same small Transformer, with22layers, width128128and44attention heads \(about0\.680\.68M parameters\)\. Table[1](https://arxiv.org/html/2610.27157#A1.T1)lists the other sizes we use when we vary the size of the student\.

Dyck\.Each sequence is a string of6464brackets of four kinds, and it is valid if every opening bracket is closed by the matching bracket in the right order\. The ID and OOD sequences follow the same rules but use the four kinds of bracket with different frequencies:0\.10\.1,0\.20\.2,0\.30\.3and0\.40\.4in distribution, and the reverse out of distribution\. We train the base model on300300K valid ID sequences, using AdamW with learning rate3×10−43\\times 10^\{\-4\}for30003000iterations\. When the harness backtracks on Dyck, it deletes the last44tokens and lets the base model write them again, and it backtracks at most5050times\. Two verifiers can tell it when to backtrack\. The learned one is a linear classifier that reads the hidden state of the base model and predicts whether the last token is a mistake; it is correct on87\.3%87\.3\\%of tokens\. The oracle checks the prefix directly, so it is always correct\.

Sokoban\.Each puzzle is a5×55\\times 5grid with one player, one box, one target and at most three walls, and the goal is to push the box onto the target\. The player moves up, down, left or right, and<BT\>undoes the last move\. The model reads a puzzle as its2525cells, row by row, and then writes the moves\. Solutions are between33and1515moves long, and the two splits \(ID and OOD\) differ in how long they tend to be: short solutions are the most common in distribution, and long ones are the most common out of distribution\. The base model is trained in the same way as on Dyck, and we test on300300held\-out puzzles from each split\. The oracle verifier runs a breadth\-first search to check whether the puzzle can still be solved from the current state\.

Students\.A student learns from the teacher’s traces in one of two ways\. Either we train it from scratch on the traces alone, or we start from the base model and fine\-tune it on a mix of traces and clean data\. Unless we say otherwise, the mix is70%70\\%clean data and fine\-tuning runs for55K iterations\. At test time the student is on its own, with no harness and no verifier\.

### B\.3Full Ablation Grids

This section collects the full sweeps behind the ablations in Section[2\.2](https://arxiv.org/html/2610.27157#S2.SS2)\. We ran every sweep on both tasks and with all four versions of the VGB traces, and the figures show a few representative cases\. In every panel, the dashed lines mark the teacher\.

#### B\.3\.1Fine\-tuning the Base Model

Here the student starts from the base model and is fine\-tuned on a mix of traces and clean data\. A default run uses all of the traces, adds clean data until it makes up70%70\\%of the mix, and trains for55K iterations\. In each sweep we change just one of these three choices and leave the other two as they are\. We try clean\-data shares from0%0\\%to100%100\\%, training runs of33K,55K or88K iterations, and11K,55K or2020K traces\. We also change which puzzles the traces come from: instead of ID puzzles only, we draw them from the mixPα=\(1−α\)​PID\+α​POODP\_\{\\alpha\}=\(1\-\\alpha\)P\_\{\\text\{ID\}\}\+\\alpha P\_\{\\text\{OOD\}\}forα∈\{0\.25,0\.5,0\.75\}\\alpha\\in\\\{0\.25,0\.5,0\.75\\\}, and repeat the clean\-data sweep for eachα\\alpha\. Figure[6](https://arxiv.org/html/2610.27157#A1.F6)shows all four sweeps for VGB, and Figure[7](https://arxiv.org/html/2610.27157#A1.F7)shows the first three for A\* search\.

The first question is whether the student simply needs the right amount of clean data\. Clean data does help, but only up to a point\. On VGB, accuracy climbs quickly as the first30%30\\%of clean data is added, and after that it hardly moves, staying at about the level of the base model \(Figure[6](https://arxiv.org/html/2610.27157#A1.F6)a\)\. In other words, clean data repairs the damage that training on traces alone does to the student, but it does not lift the student above the base model\. The A\* traces are harder to learn, and without any clean data the A\* student fails almost completely \(Figure[7](https://arxiv.org/html/2610.27157#A1.F7)a\)\.

Training longer or on more traces does not help much either\. Going from33K to88K iterations adds only a few points, and twenty times more traces barely changes the student \(Figure[6](https://arxiv.org/html/2610.27157#A1.F6)b,c\), so the gap is unlikely to come from too little training or too little data\.

Finally, the gap could come from which puzzles the traces are drawn from\. Mixing OOD puzzles into training raises OOD accuracy a little, as one would expect, but the student ends up about as far below the teacher as before \(Figure[6](https://arxiv.org/html/2610.27157#A1.F6)d–f\)\.

#### B\.3\.2Training from Scratch

We run a similar set of checks for students trained from scratch at the size of the base model\. We train with four different random seeds, to see how much the results vary\. We train on traces from OOD puzzles, which tells us whether the student learns the search itself or only the statistics of the ID puzzles\. And we draw the training puzzles from the same mixPαP\_\{\\alpha\}as above\. The results are shown in Figure[8](https://arxiv.org/html/2610.27157#A1.F8)\.

## Appendix CSupplementary Details for Section[3](https://arxiv.org/html/2610.27157#S3)

This appendix gives more details on the three experiments of Section[3](https://arxiv.org/html/2610.27157#S3)\.

### C\.1Model\-Size Sweep \(Section[3\.1](https://arxiv.org/html/2610.27157#S3.SS1)\)

Setup\.In this sweep we change the size of the student and keep everything else fixed\. Every point is a new student, trained from scratch on the same traces as in Section[2](https://arxiv.org/html/2610.27157#S2)and tested on200200ID and200200OOD puzzles\. Table[1](https://arxiv.org/html/2610.27157#A1.T1)lists the1212sizes, which range from0\.100\.10M to5\.655\.65M parameters\.

Results\.The main text shows VGB on Dyck \(Figure[2](https://arxiv.org/html/2610.27157#S2.F2)b\), and Figure[9](https://arxiv.org/html/2610.27157#A1.F9)shows the two Sokoban settings\. On Sokoban, too, larger students do better, but how far they get depends on the harness\. With A\* search, the gap to the teacher shrinks steadily as the student grows, from0\.650\.65to0\.130\.13, yet no student reaches the teacher\. With VGB, the largest students go past the teacher, both ID and OOD\.

Each setting on its own\.The curves above take the best run at each size over all clean\-data ratios and checkpoints\. Figure[10](https://arxiv.org/html/2610.27157#A1.F10)shows each clean\-data ratio and each checkpoint separately\. Accuracy still goes up with size in every panel, both ID and OOD\.

### C\.2Simple\-BT Distillation \(Section[3\.2](https://arxiv.org/html/2610.27157#S3.SS2)\)

Setup\.Here the teacher uses a much simpler harness than VGB or A\* search\. It runs the base model on Dyck, and whenever a verifier flags the last token as a mistake, it deletes the last44tokens and lets the base model write them again\. The verifier is either the learned linear classifier or the oracle from Appendix[B\.2](https://arxiv.org/html/2610.27157#A2.SS2)\. The student starts from the base model and is fine\-tuned on a mix of clean data and teacher traces, where we keep only the traces with exactly one backtrack\. We also vary where the traces come from, by drawing the sequences from a mixPαP\_\{\\alpha\}of the ID and OOD distributions\.

Results\.Table[2](https://arxiv.org/html/2610.27157#A1.T2)lists the accuracy of every student in two modes\. In the first \(one pass\), the student writes the whole sequence from left to right with top\-ppsampling \(p=0\.9p\{=\}0\.9\), without any backtracking\. In the second, it samples in the same way, but whenever it writes a<BT\>token, the last44tokens are deleted and it continues from there, up to5050times\. For comparison, the table also includes students fine\-tuned on synthetic backtracking data, in which we insert errors taken from OOD data, chosen at random, or taken from ID data\. In distribution there is little to gain, since the distilled students already match the base model in one pass\. The interesting case is OOD\. There, letting the student use its own<BT\>tokens and drawing the traces from a slightly OOD mix \(α=0\.25\\alpha\{=\}0\.25\) together lift it a little above the base model\. It still stays well below the teacher that uses the oracle verifier\.

### C\.3Long\-CoT on Modular Arithmetic \(Section[3\.3](https://arxiv.org/html/2610.27157#S3.SS3)\)

Task\.We follow the setup of[Feng et al\. \(2023, Alg\. 1\)](https://arxiv.org/html/2610.27157#bib.bib9)\. Each problem is an arithmetic expression modulo1111withnopsn\_\{\\text\{ops\}\}operators, and it is solved one step at a time\. Each step simplifies the leftmost part of the expression that can be simplified, so every problem has exactly one chain of steps\. To control how much chain\-of\-thought the model sees, we train a33\-layer Transformer \(about2\.52\.5M parameters\) on the problem, then only the firstLLsteps of its chain, then the answer, and we varyLLfrom00tonopsn\_\{\\text\{ops\}\}\. We test on10001000held\-out problems\.

Harness\.The harness writes the solution one step at a time, where a step is one simplification of the expression\. At each step, the model proposes1616candidates for the next step\. An oracle verifier gives each candidate a score of11if the chain so far, with this candidate added, agrees with the true chain, and00otherwise\. If some candidate passes, the harness adds it to the chain and moves on\. If none passes, the harness backtracks: it removes the last step it added and tries that position again, this time without allowing the removed step, so that it does not make the same mistake twice\. Figure[11](https://arxiv.org/html/2610.27157#A1.F11)a illustrates this harness\. Figure[11](https://arxiv.org/html/2610.27157#A1.F11)b shows the results on an easier version of the task, withnops=10n\_\{\\text\{ops\}\}\{=\}10; the main text \(Figure[3](https://arxiv.org/html/2610.27157#S2.F3)\) showsnops=20n\_\{\\text\{ops\}\}\{=\}20\.

## Appendix DSupplementary Details for Section[4](https://arxiv.org/html/2610.27157#S4)

This appendix proves Lemma[1](https://arxiv.org/html/2610.27157#Thmlemma1)and Theorem[1](https://arxiv.org/html/2610.27157#Thmtheorem1)\. Throughout, circuit uniformity means logspace uniformity\. The input length isn=Θ⁡\(N2\)n=\\Theta\(N^\{2\}\),Σ\\Sigmais fixed and finite, andTc​\(n\)=⌈c​log2⁡\(n\+1\)⌉T\_\{c\}\(n\)=\\lceil c\\log\_\{2\}\(n\+1\)\\rceilfor a fixed integerc≥1c\\geq 1\.

### D\.1The local query and the hardness of reachability

ForA∈\{0,1\}N×NA\\in\\\{0,1\\\}^\{N\\times N\}andu,v∈\[N\]u,v\\in\[N\], the local predicate is

E\(A,u,v\)=⋁i,j∈\[N\]\(Ai​j∧\[u=i\]∧\[v=j\]\)\.\\textstyle E\(A,u,v\)=\\bigvee\_\{i,j\\in\[N\]\}\\bigl\(A\_\{ij\}\\land\[u=i\]\\land\[v=j\]\\bigr\)\.Writing each equality as a conjunction of binary literals gives a constant\-depth Boolean circuit with polynomially many gates and wires\. A logarithmic\-space procedure can generate the gates and their wiring by enumerating\(i,j\)\(i,j\), soE∈𝖠𝖢0E\\in\\mathsf\{AC\}^\{0\}\. The notationEA​\(u,v\)E\_\{A\}\(u,v\)fixes the graph and makes the two queried vertices explicit\.

DirectedSTCONis𝖭𝖫\\mathsf\{NL\}\-complete under uniform projection translations, and hence under uniform𝖠𝖢0\\mathsf\{AC\}^\{0\}many\-one reductions\([Immerman, 1983b](https://arxiv.org/html/2610.27157#bib.bib18), Corollary 4\.7\)\. The standard configuration\-graph construction explains the strength of the reduction\. For a fixed nondeterministic logspace machine and inputxx, its polynomially many configurations become vertices; an edge records one legal machine transition\. After fixing the two configurations, the legality of that transition depends on at most one input bit\. In a standard normal form, each output adjacency bit is therefore a constant, an input bit, or its negation, and its wiring is computable in logspace\. The source and target encode the initial configuration and a designated accepting configuration\.

This reduction strength is what Theorem[1](https://arxiv.org/html/2610.27157#Thmtheorem1)uses\. An arbitrary logspace reduction could itself perform work outside𝖳𝖢0\\mathsf\{TC\}^\{0\}, whereas a uniform𝖠𝖢0\\mathsf\{AC\}^\{0\}reduction can be composed with a𝖳𝖢0\\mathsf\{TC\}^\{0\}decision circuit while preserving constant depth, polynomial size, and logspace uniformity\.

### D\.2Proof of Lemma[1](https://arxiv.org/html/2610.27157#Thmlemma1)

###### Proof\.

LetL∈CoTTc​\(n\)​\(Σ,𝖳𝖢0\)L\\in\\mathrm\{CoT\}\_\{T\_\{c\}\(n\)\}\(\\Sigma,\\mathsf\{TC\}^\{0\}\), with predicatesVn,iV\_\{n,i\}andBnB\_\{n\}as in Definition[1](https://arxiv.org/html/2610.27157#Thmdefinition1)\. Letddandp⁡\(n\)p\(n\)be their common depth and polynomial size bounds\. Since the alphabet andccare fixed,

M⁡\(n\):=\|Σ\|Tc​\(n\)≤\|Σ\|​\(n\+1\)c​log2​\|Σ\|=poly⁡\(n\)\.\\textstyle M\(n\):=\|\\Sigma\|^\{T\_\{c\}\(n\)\}\\leq\|\\Sigma\|\(n\+1\)^\{c\\log\_\{2\}\|\\Sigma\|\}=\\mathrm\{poly\}\(n\)\.Enumerate all transcripts asz\(1\),…,z\(M⁡\(n\)\)z^\{\(1\)\},\\ldots,z^\{\(M\(n\)\)\}\. For each transcript, form the circuit

Accj​\(x\)=Bn​\(x,z\(j\)\)∧⋀i=1Tc​\(n\)Vn,i​\(x,z<i\(j\),zi\(j\)\)\.\\textstyle\\mathrm\{Acc\}\_\{j\}\(x\)=B\_\{n\}\\bigl\(x,z^\{\(j\)\}\\bigr\)\\land\\bigwedge\_\{i=1\}^\{T\_\{c\}\(n\)\}V\_\{n,i\}\\bigl\(x,z^\{\(j\)\}\_\{<i\},z^\{\(j\)\}\_\{i\}\\bigr\)\.Each predicate is evaluated after hardwiring its transcript inputs\. This does not increase its depth or size\. Add one AND gate for each transcript and one final OR:

Cn​\(x\)=⋁j=1M⁡\(n\)Accj​\(x\)\.\\textstyle C\_\{n\}\(x\)=\\bigvee\_\{j=1\}^\{M\(n\)\}\\mathrm\{Acc\}\_\{j\}\(x\)\.The resulting circuit has depth at mostd\+2d\+2and size at mostM⁡\(n\)​\(Tc​\(n\)\+1\)​p​\(n\)\+O⁡\(M⁡\(n\)\)M\(n\)\(T\_\{c\}\(n\)\+1\)p\(n\)\+O\(M\(n\)\), which is polynomial innn\.

For uniformity, the integerccis fixed andTc​\(n\)T\_\{c\}\(n\)is logspace\-computable\. Both a transcript and its index useO⁡\(log⁡n\)O\(\\log n\)bits, so a logarithmic\-space generator can enumerate the transcripts, produce their hardwired bits, and invoke the jointly uniform generators forVn,iV\_\{n,i\}andBnB\_\{n\}\. It can then add the AND and OR wiring using counters ofO⁡\(log⁡n\)O\(\\log n\)bits\. Thus\(Cn\)\(C\_\{n\}\)is logspace\-uniform\. By Definition[1](https://arxiv.org/html/2610.27157#Thmdefinition1),Cn​\(x\)=1C\_\{n\}\(x\)=1exactly whenx∈Lx\\in L, establishingL∈𝖳𝖢0L\\in\\mathsf\{TC\}^\{0\}\. ∎

This is the transcript\-enumeration argument used for logarithmic\-length transformer CoT by[Merrill & Sabharwal \(2026b, Theorem 4 and Appendix E\)](https://arxiv.org/html/2610.27157#bib.bib27)\. Joint uniformity and the explicit computable ceiling ensure that the construction also satisfies the uniformity convention of this paper\. The argument uses the polynomial number of possible transcripts; it does not establish a sharp threshold for the power of longer chains of thought\.

### D\.3Proof of Theorem[1](https://arxiv.org/html/2610.27157#Thmtheorem1)

###### Proof\.

*Part \(i\)\.*The preceding construction showsE∈𝖠𝖢0E\\in\\mathsf\{AC\}^\{0\}\. Run breadth\-first search usingEAE\_\{A\}to test existence of edges\. Store a visited setRR, a current frontierFF, and a next frontierF′F^\{\\prime\}asNN\-bit characteristic vectors\. Initially,R=F=\{s\}R=F=\\\{s\\\}\. At each iteration, set

F′=\{v∈\[N\]∖R:EA​\(u,v\)=1​for some​u∈F\},\\textstyle F^\{\\prime\}=\\\{v\\in\[N\]\\setminus R:\\ E\_\{A\}\(u,v\)=1\\text\{ for some \}u\\in F\\\},by querying the pairs inF×\(\[N\]∖R\)F\\times\(\[N\]\\setminus R\), and updateR←R∪F′R\\leftarrow R\\cup F^\{\\prime\}andF←F′F\\leftarrow F^\{\\prime\}\. Stop whenFFis empty, and accept exactly whent∈Rt\\in R\.

Afterkkiterations,RRcontains exactly the vertices at directed distance at mostkkfromss, andFFcontains those first reached at that distance\. This invariant proves correctness, including the cases=ts=t\. A vertex enters the frontier at most once, so each ordered pair is queried at most once, giving at mostN2N^\{2\}oracle calls\. The three characteristic vectors and the loop counters use3​N\+O⁡\(log⁡N\)=O⁡\(N\)3N\+O\(\\log N\)=O\(N\)bits\. The loop has at mostNNiterations and all its bookkeeping takes polynomial time\.

*Part \(ii\)\.*Suppose, for some fixedΣ\\Sigmaand integerc≥1c\\geq 1, thatSTCON∈CoTTc​\(n\)​\(Σ,𝖳𝖢0\)\\textsc\{STCON\}\\in\\mathrm\{CoT\}\_\{T\_\{c\}\(n\)\}\(\\Sigma,\\mathsf\{TC\}^\{0\}\)\. Lemma[1](https://arxiv.org/html/2610.27157#Thmlemma1)then givesSTCON∈𝖳𝖢0\\textsc\{STCON\}\\in\\mathsf\{TC\}^\{0\}\. For anyL∈𝖭𝖫L\\in\\mathsf\{NL\}, letfLf\_\{L\}be the uniform𝖠𝖢0\\mathsf\{AC\}^\{0\}many\-one reduction fromLLtoSTCONsupplied by projection completeness\([Immerman, 1983b](https://arxiv.org/html/2610.27157#bib.bib18)\)\. Composing a𝖳𝖢0\\mathsf\{TC\}^\{0\}circuit forSTCONwith the circuits for the output bits offLf\_\{L\}gives a circuit forLL\. The composition preserves constant depth, polynomial size, and logspace uniformity\. Hence𝖭𝖫⊆𝖳𝖢0\\mathsf\{NL\}\\subseteq\\mathsf\{TC\}^\{0\}, contradicting the assumption\. ∎

## Appendix ESupplementary Details for Section[5](https://arxiv.org/html/2610.27157#S5)

This appendix gives more details on the experiments in Section[5](https://arxiv.org/html/2610.27157#S5)\. We first describe more distillation experiments on Qwen3\-1\.7B \(Appendix[E\.1](https://arxiv.org/html/2610.27157#A5.SS1)\), and then the experiment on the QED\-Nano RL checkpoint\.

### E\.1Branching distillation on Qwen3\-1\.7B

Distillation settings\.The top row of Figure[12](https://arxiv.org/html/2610.27157#A1.F12)checks whether a better distillation recipe would close the gap, using the𝐤𝐬=\[3\]\\mathbf\{ks\}\{=\}\[3\]tree\. We vary three things\. The first is how much clean data we mix into the Branching traces, where clean data means in\-distribution solutions that the base model writes itself\. The second is the number of traces\. The third is the length of training, and the student stops improving after two epochs\. None of these settings brings the student up to the teacher\.

All tree shapes\.A tree withddchildren per node and depthLLcalls the model∑i=0Ldi\\sum\_\{i=0\}^\{L\}d^\{i\}times, so the shapes we try range from33calls for\(2,1\)\(2,1\)to8585for\(4,3\)\(4,3\)\. The bottom row of Figure[12](https://arxiv.org/html/2610.27157#A1.F12)shows the number of calls for each shape \(d\) and the accuracy of the teacher and the student \(e; the main text shows the same panel\)\. As the teacher makes more calls it gets better almost every time, while the student shows no clear trend\.

More capacity\.If the student falls short because it is too small, giving it more capacity should help\. We try two ways of doing this \(Figure[13](https://arxiv.org/html/2610.27157#A1.F13)\)\. Training more parameters of the same model helps only a little: with a higher LoRA rank, or even with full fine\-tuning, the student stays well below the teacher \(panel b\)\. Switching from the1\.71\.7B to the44B model, on the other hand, takes the student past the teacher \(panel a\)\. This suggests that the student needs a larger model, and that training more parameters of the same model is not enough\.

### E\.2The QED\-Nano checkpoint and its harness

QED\-Nano\([Qu et al\., 2026](https://arxiv.org/html/2610.27157#bib.bib32)\)is a44B model for writing Olympiad\-level proofs\. It starts from Qwen3\-4B\-Thinking and is trained in two stages: first supervised fine\-tuning on proofs written by the much larger DeepSeek\-Math\-V2, then reinforcement learning on theFineProofs\-RLproblems, with rewards computed from grading rubrics\. The harness is only added at test time and is not trained\. We use the released checkpoint, which is the model after both stages\.

The QED\-Nano paper reports that its harness, Recursive Self\-Aggregation \(RSA\), helps a lot: on IMO\-ProofBench it raises accuracy from40\.0%40\.0\\%to56\.9%56\.9\\%, at the cost of about2222times more tokens\. RSA works with a pool ofnnproofs\. The model first writesnnproofs independently\. Then, forTTrounds, it replaces the pool with new proofs, each written by mergingkkproofs drawn at random from the current pool\. Finally, the proofs are paired up, the model reads each pair and keeps the better proof, and this repeats until only one proof is left\. That proof is the final answer\. The same model plays every role, with a different prompt for each\.

This harness is far too large to distill\. With3939calls, one RSA trace is about1\.51\.5M tokens long, several times longer than any context we could train on\. We therefore test the simpler Branching harness, which writes a few independent proofs and merges them in a few steps\. Its traces are short enough that distilling them is at least possible, and we ask whether the harness still helps at these smaller sizes\.

### E\.3Corpus

We test on300300problems fromFineProofs\-RL, the5,2275\{,\}227problems used in the model’s reinforcement\-learning stage\. Using this set has two advantages\. The QED\-Nano authors already removed the problems that overlap with IMO\-ProofBench, the benchmark the harness was tuned on, and every problem comes with a grading rubric, which we need to score a free\-form proof\.

We only keep problems of medium difficulty, namely those on which the base model’s average reward over128128attempts lies between0\.100\.10and0\.600\.60\. On harder problems the model almost never writes a correct proof, so the harness has mostly wrong proofs to merge and little chance to improve on them\. On easier problems a single call is usually already correct, so there is little left for the harness to add\. From this range we take300300problems evenly spaced by difficulty, so that every run uses the same problems\.

### E\.4Shapes

Table[3](https://arxiv.org/html/2610.27157#A1.T3)lists the five tree shapes we run\. We describe a shape by a pair\(r,b\)\(r,b\)\. The model first writesbrb^\{r\}proofs; then, in each ofrrrounds, it merges every group ofbbproofs into one, until a single proof is left\. We turn off the final pairwise comparison, so a trace contains only the tree\. The shapes\(1,6\)\(1,6\)and\(2,2\)\(2,2\)cost the same,77calls each, but merge the proofs in different ways\. With\(1,6\)\(1,6\), the model writes66proofs and merges all of them at once\. With\(2,2\)\(2,2\), it writes44proofs, merges them in pairs into22proofs, and then merges those22into one\. Comparing the two therefore shows whether the shape of the tree matters when the cost is held fixed\.

### E\.5Generation and grading

Generation\.We serve the model with vLLM, allow up to65,53665\{,\}536tokens per call, and sample once per problem at temperature1\.01\.0\. We use the prompts from the QED\-Nano repository without changes\.

Base and harness answers\.Both answers come from the same run\. The base answer is the output of the first call, which is just one ordinary attempt at the problem, so the baseline costs nothing extra\. The harness answer is the output at the root of the tree\. Because the two answers share the problem, the run and the sampling settings, we can compare them problem by problem\. In both cases we grade only the final answer and not the model’s thinking\.

Grading\.A localgpt\-oss\-20bjudge scores each answer out of77points following the problem’s rubric, and we count an answer as correct if it scores at least66\. All the percentages we report are these pass rates\. Before grading we cut answers off at100,000100\{,\}000characters, because a few broken answers are extremely long and would otherwise make the grading call fail\. For the gain of the harness over the base answer, we give a95%95\\%confidence interval from a paired bootstrap\.

### E\.6Results and caveats

The results are in Figure[5](https://arxiv.org/html/2610.27157#S5.F5)b and Figure[13](https://arxiv.org/html/2610.27157#A1.F13)c\. For the four small trees, which make55to77calls, the harness is not clearly better than a single call: the confidence interval of the gain contains zero\. Only the largest tree,\(3,3\)\(3,3\)with4040calls, does clearly better than a single call\. But its trace is about1\.41\.4M tokens long, far more than the262262K\-token context window, so a student could not be trained on it\. Two caveats apply\.

*\(i\) We do not filter by trace length\.*How long a trace gets depends on the harness itself: when a merge runs into the token limit, the trace becomes too long and the answer also scores zero\. If we dropped the problems with long traces, we would mostly be removing problems on which the harness failed, and the harness would look better than it really is\. We therefore keep every problem\.

*\(ii\) We use a single run\.*Each problem is run once at temperature1\.01\.0and graded once\.