betaFeedback

WorksComputer Science

Best-of-Depth: Learning Exploratory Dynamics in Looped Transformers

Abstract

Looped Transformers extend inference-time computation through repeated latent-state updates, but final-depth training does not directly encourage useful intermediate alternatives. We introduce Best-of-Depth (BoD), which trains a recurrent trajectory as a candidate set by minimizing prediction loss across depths. Different valid targets can be matched at different depths without architectural changes or depth-specific labels. An exact-match analysis connects this objective to solution coverage. On N-Queens completion and graph coloring, BoD improves coverage over final-depth and intermediate-supervision objectives. N-Queens coverage reaches 91.03%, versus 45.75% for final-depth training. Further experiments show discovery beyond the training depth and recovery of solutions withheld from teacher pools on familiar inputs. Fine-tuning a pretrained looped language model with BoD yields higher pooled code-generation success than final-depth training when programs are generated separately at evaluated fixed depths. These results support training recurrent computation for solution discovery along its trajectory.

Introduction

Additional inference-time computation can improve a model’s ability to solve problems [25, 5]. Looped Transformers accumulate computation by repeatedly applying a shared transformation to a latent state [9, 13, 28]. This extends computational depth without adding parameters, and greater recurrent depth can improve reasoning performance [24, 12]. Making these models effective therefore involves learning how successive updates should contribute to solving a problem.

The learning objective can reflect how predictions are used at inference. Best-of-N sampling generates and verifies multiple candidate solutions, increasing the opportunity to find a correct answer beyond a single attempt [5, 8]. Inference-aware Best-of-N training incorporates this procedure into learning [7], while Explorative Modeling (XM) trains on the candidate that best matches a target [14]. These approaches illustrate how learning objectives shape candidate generation. Recurrent models also offer multiple predictions, read out at successive depths along one trajectory. We therefore ask: Can a single recurrent trajectory be trained to visit distinct useful solution candidates?

Simply increasing recurrent computation does not guarantee distinct useful candidates. Recent work promotes fixed-point convergence for stability [29] or uses convergence for halting [21], but convergence alone does not determine which alternatives a trajectory discovers. Supervising only the final prediction [9, 24] does not directly reward useful intermediate alternatives; supervising every depth against the same target asks all readouts to reproduce that target. Candidate-set evaluation suggests another criterion: the target should be reached somewhere within the depth budget. Because later predictions depend on preceding latent states, the learning problem is to train these coupled predictions collectively.

We introduce Best-of-Depth (BoD), which trains a recurrent trajectory as a candidate set using the minimum prediction loss across supervised depths (Figure 1). A shared decoder reads out predictions, and the loss at the selected depth trains the recurrent computation. Each target need only be matched at one depth, allowing different valid targets for the same input to be matched at different depths without a prescribed assignment or visitation order. The set-loss formulation is related to multiple-hypothesis learning [15, 18, 4]; here, candidates are generated successively and coupled through shared latent dynamics. BoD requires no architectural changes, additional parameters, or depth-specific labels.

Figure 1. Learning alternative solutions along one recurrent trajectory. Top: One input admits multiple valid solutions. Middle: Schematic latent trajectories illustrate (a) repeated predictions under Last-Depth, (b) independent candidates from Best-of-NN, and (c) distinct solutions along one BoD trajectory; shaded regions decode to A–C. Bottom: Both models reuse FθF_\theta across depths. Last-Depth trains on LDL_D; BoD trains on the lowest loss across depths (highlighted L2L_2 for target A).

We study solution discovery theoretically and empirically. Under exact-match loss and uniformly sampled valid targets, minimizing expected BoD loss maximizes solution coverage. On N-Queens completion and graph coloring, where all valid solutions can be enumerated, Success@Depth measures whether any valid solution is found, while Coverage@Depth measures the fraction of the valid solution set recovered. Coverage therefore tests whether additional computation discovers alternatives after an initial solution is found. We also test discovery beyond teacher pools and training depth, and compare trajectory counts and depths under a fixed recurrent-step budget on these controlled tasks. For autoregressive code generation, we fine-tune Huginn [12] and evaluate programs generated separately at different fixed depths.

We find that BoD recovers more distinct valid solutions on both controlled tasks. The N-Queens coverage reaches 91.03%; coverage continues increasing after success nearly saturates, showing further discovery of valid alternatives. BoD also recovers solutions withheld from teacher pools on familiar inputs and finds new solutions beyond the training depth. BoD achieves higher pooled code-generation success than final-depth training on HumanEval and MBPP [6, 1]. On MBPP, it also gains more solved problems from pooling beyond depth 32 alone. Fixed-budget comparisons favor combining depth with multiple trajectories. Together with analyses of outputs and latent states, these results characterize how candidate-set training changes solution discovery along recurrent trajectories.

Related Work

Recurrent Computation and Looped Transformers. Looped Transformers reuse layers across depth; the Universal Transformer also supports adaptive halting [9]. Subsequent work studies algorithmic capabilities [13, 28, 11] and latent reasoning [24]. At language-model scale, Geiping et al. [12] study reasoning gains from increased recurrent depth. Flexible depth allocation uses learned exits [32], token-level routing [3], or shortcut consistency [16]. Stable depth extrapolation motivates constraints on recurrent dynamics and depth sampling [22], or depth-dependent residual scaling [19].

Existing methods supervise final outputs at fixed depths [9, 24] or sampled depths [12], apply supervision over recurrent windows [28], or supervise intermediate outputs for early exit [2]. Other objectives weight losses by exit probabilities [32]. Unlike intermediate reasoning-token supervision [10], BoD needs only output targets and prescribes no solution order.

Test-Time Candidate Generation and Compute Scaling. Additional inference compute supports candidate generation and evaluation. Repeated sampling raises the chance of at least one correct candidate, while identifying it remains a separate problem [5]. Best-of-NN selects candidates with a verifier [8]; self-consistency aggregates answers across reasoning paths [27]. Process supervision assesses intermediate steps [20], while tree-structured methods evaluate partial solutions to guide further expansion [30, 25].

Snell et al. [25] compare parallel sampling with sequential revisions, finding that the preferred allocation depends on difficulty and budget. Their revision process is conditioned on previous textual answers. Our fixed recurrent-step comparison instead allocates compute between recurrent latent updates and multiple trajectories (§ 5.1), with external candidate evaluation.

Learning to Generate Multiple Hypotheses. Multiple Choice Learning scores a prediction set through its best member’s loss against the target [15]. Stochastic MCL trains only the lowest-loss predictor per example, enabling deep ensembles to specialize without a predefined data partition [18]. Best-of-Many uses the best reconstruction among latent samples in a variational objective for sequence prediction [4]. The forward formulation of Explorative Modeling learns from the candidate closest to a target, studying exploration as a scaling axis across generative tasks [14].

Chow et al. [7] align imitation and reinforcement learning with verifier-based Best-of-NN selection. BoD instead minimizes supervised prediction loss over recurrent readouts: later hypotheses depend on earlier states, and the selected loss trains the shared update and decoder.

Best-of-Depth

Looped Transformers

A looped Transformer encodes an input xx and repeatedly applies a shared transformation:

h0=Enc⁡θ(x),hd=Fθ(hd−1;x),pd=Dec⁡θ(hd),d=1,…,D.(1)h_0 = \operatorname{Enc}_{\theta}(x), \qquad h_d = F_{\theta}(h_{d-1};x), \qquad p_d = \operatorname{Dec}_{\theta}(h_d), \qquad d = 1,\ldots,D. \tag*{(1)}

One application of FθF_{\theta} is a loop, and dd denotes recurrent depth. A shared decoder reads the prediction distribution pdp_d from each state. Let y∈Y∗(x)y \in\mathcal{Y}^{*}(x) be a valid target, y^d(x)\hat{y}_d(x) the greedy prediction, and Ld(x,y)=ℓ(pd,y)L_d(x,y)=\ell(p_d,y) the per-example loss. We omit input and parameter dependence when unambiguous.

Supervising the final recurrent output is an established approach in fixed-depth looped models [9, 24]. We call this Last-Depth training: only the prediction at the maximum training depth contributes to the loss,

LLast-Depth=LD.(2)\mathcal{L}_{\mathrm{Last\text{-}Depth}} = L_D. \tag*{(2)}

Best-of-Depth Objective

At training depth D=DtrainD = D_{\mathrm{train}}, let D⊆{1,…,D}\mathcal{D} \subseteq\{1,\ldots,D\} denote the supervised depths, including DD. BoD minimizes

LBoD(x,y)=min⁡d∈DLd(x,y).(3)\mathcal{L}_{\mathrm{BoD}}(x,y)=\min_{d\in\mathcal{D}} L_d(x,y). \tag*{(3)}

Each LdL_d averages losses over predicted positions. BoD selects one depth for the entire target and trains on its loss, breaking exact ties at random.

For an autoregressive target, the teacher-forced loss is

Ld(x,y)=−1T∑t∈Tlog⁡pd(yt∣x,y<t),T=∣T∣.(4)L_d(x,y)=-\frac{1}{T}\sum_{t\in\mathcal{T}}\log p_d(y_t\mid x,y_{<t}),\qquad T=|\mathcal{T}|. \tag*{(4)}

where T\mathcal{T} contains target-token positions and pdp_d is the depth-dd next-token distribution.

For the same readouts, Mean-Depth supervises all depths and Random-Depth samples one per example:

LMean-Depth=1∣D∣∑d∈DLd,LRandom-Depth=Ld~,d~∼Uniform⁡(D).(5)\mathcal{L}_{\mathrm{Mean\text{-}Depth}}=\frac{1}{|\mathcal{D}|}\sum_{d\in\mathcal{D}}L_d,\qquad\mathcal{L}_{\mathrm{Random\text{-}Depth}}=L_{\tilde{d}},\qquad\tilde{d}\sim\operatorname{Uniform}(\mathcal{D}). \tag*{(5)}

Soft-Depth smoothly relaxes the minimum:

LSoft-Depth(x,y)=−τlog⁡(1∣D∣∑d∈Dexp⁡[−Ld(x,y)/τ]),τ>0.(6)\mathcal{L}_{\mathrm{Soft\text{-}Depth}}(x,y)=-\tau\log\left(\frac{1}{|\mathcal{D}|}\sum_{d\in\mathcal{D}}\exp[-L_d(x,y)/\tau]\right),\qquad\tau>0. \tag*{(6)}

Lower-loss depths receive greater gradient weight; the limits τ→0\tau\to0 and τ→∞\tau\to\infty recover BoD and Mean-Depth, respectively. All methods allow the same readouts at inference time.

Interpreting the Best-of-Depth Objective

For exact-match loss, write LBoD0-1=min⁡d∈D1[y^d≠y]\mathcal{L}_{\mathrm{BoD}}^{0\text{-}1}=\min_{d\in\mathcal{D}}\mathbf{1}[\hat{y}_d\ne y]. The first two results connect this objective to target discovery and solution coverage.

Proposition 1 (First-hit interpretation). Let τy=min⁡{d∈D:y^d=y}\tau_y=\min\{d\in\mathcal{D}:\hat{y}_d=y\}, with τy=∞\tau_y=\infty if no readout matches yy. Then

E[LBoD0-1]=Pr⁡(τy>D).(7)\mathbb{E}[\mathcal{L}_{\mathrm{BoD}}^{0\text{-}1}]=\Pr(\tau_y>D). \tag*{(7)}

BoD thus evaluates whether the target is reached anywhere within the depth budget.

Proposition 2 (Connection to solution coverage). Fix xx and SD(x)={y^d(x):d∈D}S_D(x)=\{\hat{y}_d(x):d\in\mathcal{D}\} independently of the target Y∼Uniform⁡(Y⋆(x))Y\sim\operatorname{Uniform}(\mathcal{Y}^{\star}(x)). Then

EY[LBoD0-1∣x]=1−∣SD(x)∩Y⋆(x)∣∣Y⋆(x)∣=1−Coverage@Depth⁡(D;x).(8)\mathbb{E}_Y[\mathcal{L}_{\mathrm{BoD}}^{0\text{-}1}\mid x]=1-\frac{|S_D(x)\cap\mathcal{Y}^{\star}(x)|}{|\mathcal{Y}^{\star}(x)|}=1-\operatorname{Coverage@Depth}(D;x). \tag*{(8)}

Minimizing this risk maximizes coverage; repeated candidates do not increase coverage.

For cross-entropy, the following construction separates the objectives under shared recurrent computation.

Proposition 3 (Separation in solution discovery). There exists a multi-solution task, a shared recurrent model with depth budget DD and factorized readouts, and a common symmetric initialization and SGD schedule such that, under cross-entropy training with uniformly resampled valid targets, greedy coverage satisfies

lim⁡n→∞Coverage@Depth⁡(D;θA(n))={0,A∈{Last,Mean,Random,Soft},1,A=BoD,(9)\lim_{n\to\infty}\operatorname{Coverage@Depth}(D;\theta_A^{(n)})= \begin{cases} 0, & A\in\{\mathrm{Last},\mathrm{Mean},\mathrm{Random},\mathrm{Soft}\},\\ 1, & A=\mathrm{BoD}, \end{cases} \tag*{(9)}

almost surely, where θA(n)\theta_A^{(n)} denotes the parameters after nn updates with objective AA. The Soft-Depth result holds for every fixed τ>0\tau>0; BoD selects one loss-minimizing depth when losses tie.

In this prescribed cyclic recurrence, the other objectives retain or recover a symmetric predictor with invalid greedy outputs. BoD breaks symmetry by selecting one depth, allowing different targets to reinforce the same latent solution through different recurrent phases.

Proofs are in Appendices § 14.§ 1 and § 14.§ 3, including a numerical illustration of Proposition 3. Cross-entropy coverage bounds are given in Appendices § 14.§ 2 and § 14.§ 4.

Experiments

Experimental Setup

Compared methods and candidate generation. We compare BoD, Last-Depth, Mean-Depth, Random-Depth, and Soft-Depth (τ=0.25\tau= 0.25; § 3). Within each task, all share the output head and a width-128 Transformer with two shared layers per loop and eight attention heads. Unless stated otherwise, we train with uniformly resampled valid targets at Dtrain=16D_{\mathrm{train}} = 16 and evaluate greedy readouts through Dtest=64D_{\mathrm{test}} = 64. For controlled-task experiments, we report means and sample standard deviations (SD) over three training seeds; randomized evaluations first average inference repeats within each seed. For multiple trajectories, we pool all intermediate predictions. § 4.4 describes autoregressive generation; Appendix § 11 gives implementation details.

Evaluation metrics. For the set of distinct candidates SD(x)S_D(x) (§ 3.3), with D=DtestD = D_{\mathrm{test}}, we report

Success@Depth⁡(D;x)=1[SD(x)∩Y⋆(x)≠∅],(10)\operatorname{Success@Depth}(D; x) = \mathbf{1}\left[S_D(x) \cap\mathcal{Y}^{\star}(x) \ne\varnothing\right], \tag*{(10)}
Coverage@Depth⁡(D;x)=∣SD(x)∩Y⋆(x)∣∣Y⋆(x)∣.(11)\operatorname{Coverage@Depth}(D; x) = \frac{\left|S_D(x) \cap\mathcal{Y}^{\star}(x)\right|}{\left|\mathcal{Y}^{\star}(x)\right|}. \tag*{(11)}

Both metrics are percentages averaged over problems. Coverage is our primary controlled-task metric; Success requires only a validity verifier. Single-depth accuracy measures the fraction of problems solved at depth DD. We abbreviate cumulative metrics as Success@DD and Coverage@DD, or Success and Coverage when candidate sets have no common depth budget.

N-Queens Completion

Settings. Each input specifies five fixed queens on a 10×1010 \times10 board. The model completes it so no two queens share a row, column, or diagonal. We use 100 cell tokens and train on 24,320 problems. Evaluation uses 1,000 multi-solution test problems with all valid completions enumerated. Distinct completed boards are distinct solutions; symmetry-equivalent inputs remain in the same split (Appendix § 11.§ 1).

Results. BoD outperforms all four objectives at depth 64, with 91.03% coverage and 99.03% success (Figure 2, left). Its largest gains occur near the training depth, with further discoveries beyond it and saturation by depth 64. Deeper evaluation benefits all objectives, but the others recover fewer valid completions per problem. BoD thus improves both success and the fraction of alternatives recovered along one trajectory.

Figure 2. Depth-wise solution discovery. Coverage@Depth (top) and Success@Depth (bottom) for greedy trajectories trained at depth 16. Bands indicate ±1\pm1 SD.

Graph Coloring

Settings. The model assigns one of three colors to each vertex so that adjacent vertices have different colors. We train on 4,096 connected 10-vertex graphs and test on 512, with adjacency rows encoded as vertex tokens. Each graph has 22–128128 enumerated solution families; colorings that differ only in color names count as one solution. Isomorphic graphs do not cross splits (Appendix § 11.§ 2).

Results. BoD achieves 72.16% coverage at depth 64 and solves nearly all test graphs (Figure 2, right). Success nearly saturates at the training depth, while coverage continues increasing: additional depth mainly recovers alternatives for already-solved graphs. Soft-Depth achieves high success but only 44.39% coverage, revealing differences in solution discovery despite similar success. Its coverage remains below BoD after development-set temperature selection (Appendix § 13.§ 4).

Code Generation

Settings. We fine-tune Huginn, a pretrained 3B-parameter looped language model [12], on 20,000 Python examples from CodeFeedback [31], with 1,000 validation examples. We train models under all five objectives at depth 32; we also evaluate the pretrained model. On all 164 HumanEval and 500 MBPP problems [6, 1], each model generates a complete program separately at each fixed depth in {4,8,12,16,24,32}\{4, 8, 12, 16, 24, 32\} using greedy decoding. Success@32 pools these six candidates. We score completed programs using tests that do not guide generation or repair; MBPP uses the public tests included in the prompt. Appendix § 11.§ 3 gives the full protocol.

Results. BoD achieves the highest Success@32 on both benchmarks (Table 1): 37.8% versus Last-Depth’s 34.8% on HumanEval, and 44.2% versus 39.2% on MBPP. BoD also has the highest depth-32 accuracy, although Mean-Depth, Random-Depth, and Soft-Depth perform better at shallow depths. Pooling BoD’s depth-specific programs solves problems missed at depth 32 alone, demonstrating useful shallow-depth candidates and extending BoD’s benefit to autoregressive generation.

MethodHumanEvalMBPP
DepthSuccess@DepthDepthSuccess@Depth
4816323248163232
Base0.012.824.425.630.51.217.029.029.839.8
Last-Depth0.013.427.426.834.81.821.230.231.439.2
Mean-Depth6.720.127.427.431.710.426.028.029.037.2
Random-Depth4.920.126.828.730.58.825.829.629.637.4
Soft-Depth6.120.726.226.832.99.425.229.230.839.4
Best-of-Depth0.614.629.329.937.80.621.030.633.244.2

Table 1. Code-generation results (%). Base is pretrained; other rows denote fine-tuning objectives. Depth columns show accuracy for one greedy program per problem. Success@32 pools the six evaluated depths {4,8,12,16,24,32}\{4, 8, 12, 16, 24, 32\}. Bold marks each column’s best result.

Ablation Studies

Width vs. Depth under a Fixed Recurrent-Step Budget

Figure 3(a, b) compares seven allocations of B=ND=64B = N D = 64 recurrent-block applications, with D∈{1,2,4,8,16,32,64}D \in\{1, 2, 4, 8, 16, 32, 64\} and N=64/DN = 64/D. Each method pools and deduplicates all intermediate predictions from NN trajectories. We perturb the initial states with Gaussian noise for N-Queens and permute vertices for graph coloring, including at N=1N = 1. Appendix § 13 gives the protocols.

Figure 3. Depth allocation and extrapolation. (a, b) Coverage pooling intermediate predictions from randomized trajectories under ND=64N D = 64. (c, d) BoD with unperturbed greedy readouts; open markers denote training depth. Bands indicate ±1\pm1 SD.

BoD achieves its highest mean coverage at (N,D)=(4,16)(N, D) = (4, 16) on both tasks; Last-Depth peaks at (2,32)(2, 32) on N-Queens and (4,16)(4, 16) on graph coloring. These results favor combining depth with multiple trajectories.

Training Depth and Test-Time Extrapolation

We vary training depth to examine whether solution discovery continues beyond the supervised trajectory. Figure 3(c, d) evaluates BoD trained at Dtrain∈{4,8,16}D_{\mathrm{train}} \in\{4, 8, 16\} using greedy readouts through Dtest∈{4,8,16,32,64}D_{\mathrm{test}} \in\{4, 8, 16, 32, 64\}. All settings show further discoveries beyond the training depth, with diminishing gains. Models trained deeper reach higher coverage by depth 64, but can lag at shallower depths. Training depth thus shapes both the breadth of the candidate set and the depth at which alternatives become available. Success curves and numerical results are in Appendix § 13.

Discovering Solutions Beyond the Training Targets

We test discovery beyond supplied targets by restricting each graph’s teacher pool to one, two, three, or four valid solutions, with an all-solutions control. The pools are nested, and targets are sampled uniformly from each pool; all conditions use the same training budget and 3,034 training graphs with at least five solutions (Appendix § 13.§ 6). Evaluation on these same graphs measures Seen Coverage, the fraction of teacher-pool solutions recovered, and Unseen Coverage, the fraction of withheld valid solutions recovered, averaged per graph. Table 2 compares Last-Depth, Last-Depth with multiple sampled trajectories (Last-Depth + BoN), and BoD under a recurrent-step budget of 64, collecting intermediate predictions for all three. BoD has the highest unseen coverage in every restricted-pool condition, increasing from 29.4% with one training solution to 46.2% with four. These are familiar training inputs, not unseen graphs.

Training solutionsLast-DepthLast-Depth + BoNBest-of-Depth
Seen CoverageUnseen CoverageSeen CoverageUnseen CoverageSeen CoverageUnseen Coverage
199.8±0.099.8\pm0.013.5±2.413.5\pm2.425.4±0.325.4\pm0.325.4±0.425.4\pm0.498.8±0.498.8\pm0.429.4±0.429.4\pm0.4
246.6±0.646.6\pm0.612.9±1.212.9\pm1.222.8±0.722.8\pm0.722.9±0.922.9\pm0.994.2±1.194.2\pm1.137.0±0.837.0\pm0.8
337.1±1.437.1\pm1.413.8±1.313.8\pm1.323.6±0.223.6\pm0.223.7±0.323.7\pm0.391.3±1.391.3\pm1.342.2±0.542.2\pm0.5
428.4±0.328.4\pm0.313.8±0.413.8\pm0.424.4±0.624.4\pm0.624.4±0.624.4\pm0.687.7±1.687.7\pm1.646.2±1.246.2\pm1.2
All11.8±0.211.8\pm0.2N/A25.0±0.425.0\pm0.4N/A67.4±4.467.4\pm4.4N/A

Table 2. Discovery beyond the training targets on graph coloring. Seen Coverage and Unseen Coverage (%) on 3,034 training graphs under ND=64N_D=64. All uses every valid solution as a training target candidate; Unseen Coverage is then undefined (N/A).

Comparison with Other Baselines

Table 14 in Appendix § 13.§ 7 compares BoD with unshared and autoregressive Transformers, masked diffusion (Sahoo et al., [23]), HRM (Wang et al., [26]), TRM (Jolicoeur-Martineau, [17]), and an instance-level adaptation of Ouro’s objective [32]. Task splits and update counts are shared, but architectures and candidate counts vary. BoD achieves the highest mean success and coverage on both tasks. HRM has similar N-Queens success but substantially lower coverage, illustrating the distinction between finding one solution and many. Ouro’s adapted objective also yields lower coverage on the same looped backbone.

MethodN-QueensGraph Coloring
SuccessCoverageSuccessCoverage
Transformer (8 layers)9.8±1.39.8 \pm1.34.8±0.64.8 \pm0.639.6±1.839.6 \pm1.85.2±0.55.2 \pm0.5
Transformer (32 layers)10.9±1.110.9 \pm1.15.4±0.65.4 \pm0.644.5±1.144.5 \pm1.16.3±0.36.3 \pm0.3
Autoregressive Transformer57.4±3.057.4 \pm3.027.4±1.427.4 \pm1.467.9±1.567.9 \pm1.58.2±0.48.2 \pm0.4
Masked Diffusion34.2±4.134.2 \pm4.116.3±2.016.3 \pm2.076.1±1.576.1 \pm1.510.3±0.310.3 \pm0.3
HRM98.6±0.598.6 \pm0.548.0±0.648.0 \pm0.667.4±0.967.4 \pm0.913.7±0.213.7 \pm0.2
TRM49.4±23.649.4 \pm23.623.8±11.423.8 \pm11.467.4±1.567.4 \pm1.514.3±0.314.3 \pm0.3
Ouro77.9±4.577.9 \pm4.546.8±3.746.8 \pm3.773.3±1.373.3 \pm1.318.6±0.118.6 \pm0.1
Best-of-Depth99.0±0.199.0 \pm0.191.0±1.091.0 \pm1.099.9±0.199.9 \pm0.172.2±3.672.2 \pm3.6

Table 14.

Understanding Exploratory Recurrent Dynamics

Figure 4 relates BoD’s broader discovery to its recurrent dynamics on graph coloring. The statistics cover all 512 test graphs and three training seeds (Appendix § 12).

Figure 4. Exploratory recurrent dynamics on graph coloring. (a) Example outputs; NEW marks first appearances. (b) Fraction of graphs with a new valid solution. (c) Separate PCA projections for the same example and seed as (a); markers identify solutions or invalid outputs. (d) Relative state displacement. (e) Loss-minimizing depths. Bands (b, d) and error bars (e) indicate ±1\pm1 SD. Dotted lines mark training depth 16.

BoD discovers new valid solutions near and just beyond the training depth, where Last-Depth makes few discoveries (Figure 4b). This metric counts first solutions and subsequent alternatives. Discovery declines at greater depths (Figure 2). In panel (a), Last-Depth produces invalid outputs through depth 14 and reaches two distinct solutions by depth 64, whereas BoD reaches all six.

Separate PCA projections for this example show BoD moving among states decoding to different valid solutions (Figure 4c). Across the test set, BoD maintains greater relative state displacement near and beyond the training depth, while Last-Depth’s declines (panel (d)). Displacement is measured before projection relative to the preceding state’s norm. Panels (a, b) measure discovery; panels (c, d) characterize the accompanying dynamics.

Loss-minimizing depths span all 16 supervised depths (Figure 4e), providing the best predictions for different input–target pairs. The histogram weights graphs equally and valid targets uniformly within each graph. Together, these analyses associate broader discovery with sustained latent movement and useful intermediate readouts. Additional computation beyond the training depth yields further alternatives.

Discussion and Limitations

Our results highlight training objectives as a design choice for inference-time candidate generation. On controlled tasks, BoD improves coverage using the same architecture and inference readouts as the comparison objectives. This motivates aligning recurrent training with candidate-set evaluation so intermediate predictions contribute useful alternatives.

Fixed-budget results favor combining depth with multiple trajectories. For autoregressive generation, extensions include cross-depth sampling, branching, restarts, verification, and adaptive stopping.

Our evidence covers small combinatorial tasks and one pretrained language model; discovery saturates with depth. Generality requires testing larger tasks and additional models.

Conclusion

Best-of-Depth trains on the lowest-loss prediction along a looped Transformer’s trajectory, allowing different depths to match different valid targets without architectural changes. On N-Queens completion and graph coloring, it improves success and solution coverage, with further discoveries beyond the training depth. On familiar graph-coloring inputs, it also recovers solutions withheld from the teacher pool. Trajectory analyses show broader discovery alongside sustained latent movement and use of multiple intermediate depths. Under a fixed recurrent-step budget, combining depth with multiple trajectories yields higher coverage. Code-generation experiments show higher cumulative success when pooling programs from different fixed depths. These findings support training and evaluating recurrent trajectories as candidate sets of complementary valid solutions across depth.

Reproducibility Statement

Appendix § 11 describes the datasets, models, training objectives, and evaluation protocols. Appendix § 12 specifies the trajectory analyses, Appendix § 13 reports detailed results and aggregation procedures, and Appendix § 14 provides the proofs. Table 4 lists the code-generation hyperparameters used for all five fine-tuning objectives.

SettingValue
ModelHuginn 3.565B, shared recurrent parameters
DataCodeFeedback Python examples; 20,000 train / 1,000 validation
Maximum sequence length1,024 tokens, including prompt and target
Training duration1 epoch, 625 updates
Effective batch size32
Maximum training depthDtrain=32D_{\mathrm{train}} = 32
OptimizerAdamW, β=(0.9,0.95)\beta= (0.9, 0.95), ϵ=10−8\epsilon= 10^{-8}, weight decay 0
Peak learning rate5×10−75 \times10^{-7}
ScheduleWarmup–Stable–Decay; first 63 updates warm up, final 63 decay

Table 4. Shared fine-tuning settings for the five code-generation objectives.

AI Use Statement

AI tools assisted with manuscript editing, mathematical derivations and proof review, LaTeX formatting, and compilation.

Implementation Details

For N-Queens and graph coloring, Last-Depth, Mean-Depth, Random-Depth, Soft-Depth, and BoD use the same architecture and output head within each task. The supervised depth set for Mean-Depth, Random-Depth, Soft-Depth, and BoD is D={1,…,Dtrain}D = \{1,\ldots,D_{\mathrm{train}}\}. Soft-Depth uses τ=0.25\tau= 0.25 except in the temperature sweep. At each presentation of an input, a target is sampled uniformly from its complete valid solution set, except in the withheld-solution ablation.

N-Queens Completion

Dataset. Each input specifies five fixed queens on a 10×1010 \times10 board. The training, development, and test splits contain 24,320, 400, and 2,000 inputs, respectively, with equal numbers of single- and multi-solution inputs in each split. All valid completions are enumerated, and D4D_4-equivalent inputs do not cross splits. Reported coverage and success use the 1,000 multi-solution test inputs. Distinct completed boards count as different solutions; outputs are not merged under D4D_4 symmetry.

Model and training. The model represents the board with 100 cell tokens and uses the shared recurrent architecture in Table 3. For the objective comparisons, we train each model for 20,000 updates and evaluate its EMA weights at that point. Evaluation collects the intermediate predictions of one trajectory through depth 64.

SettingValue
Recurrent transformationTwo shared Transformer layers per loop
Width / heads / FFN width128 / 8 / 384
Output normalizationStableMax
Training depth DtrainD_{\mathrm{train}}16
OptimizerAdamAtan2
Learning rate / batch size10−410^{-4} / 768
Schedule2,000 warmup updates, then constant learning rate
Weight decay / gradient clipping1 / norm 1
EMA decay0.999
Training updatesN-Queens: 20,000; graph coloring: 10,000

Table 3. Training settings for the N-Queens and graph-coloring objective comparisons.

Graph Coloring

Dataset. Inputs are connected graphs with 10 vertices, at least 10 edges, and 2–128 valid 3-coloring families. The training, development, and test splits contain 4,096, 512, and 512 graphs, respectively, with graph-isomorphic inputs separated across splits. All canonical solution families are enumerated; colorings related by a global permutation of color names belong to the same family. Every test graph has multiple valid solutions. Coverage is computed using each graph’s number of valid families and then averaged over graphs. The verifier checks edge constraints and color range independently of the sampled teacher.

Model and training. A projection of adjacency rows produces 10 vertex tokens. Only the 10 vertex colors contribute to the loss; trailing padding positions in the serialized representation are excluded. The model uses the shared configuration in Table 3, trains for 10,000 updates, and is evaluated using the EMA weights at that fixed update. The BoD objective minimizes graph-level mean cross-entropy over depths, after averaging over the valid output positions. Evaluation collects all greedy predictions from one trajectory through depth 64.

Temperature sweep. Figure 6 varies τ=0.1,0.2,…,1.0\tau= 0.1, 0.2, \ldots, 1.0 while retaining the graph-coloring configuration above. Each evaluation collects all outputs from one 64-step trajectory.

Figure 6. Sensitivity to the Soft-Depth temperature on graph coloring. Test success and coverage use all greedy readouts through depth 64. The curve varies τ=0.1,0.2,…,1.0\tau= 0.1, 0.2, \ldots, 1.0; horizontal lines show BoD and Mean-Depth under the same configuration. Bands indicate ±1\pm1 SD.

Code Generation

Fine-tuning. We use the 3.565B-parameter Huginn model and Python examples from CodeFeedback ([12, 31]). The training and validation sets contain 20,000 and 1,000 examples, respectively. Examples whose combined prompt and target exceed 1,024 tokens are excluded. Table 4 summarizes the training settings.

The loss at each depth is the mean teacher-forced cross-entropy over the entire response, excluding prompt and padding tokens, as in Eq. (4). Last-Depth uses the loss at depth 32. For BoD, all depths from 1 to 32 are scored along one recurrent trajectory, and a single depth with the lowest response-level loss is selected for each example. This depth is then recomputed for backpropagation through its last at most eight recurrent updates; exact loss ties are broken randomly. The selected depth is shared by all response tokens in the example, not chosen separately for each token.

Mean-Depth averages response-level losses over depths 1 through 32; Random-Depth samples one depth uniformly per example, shared by all response tokens. Soft-Depth uses Eq. (6) with τ=0.25\tau= 0.25 and D={1,…,32}\mathcal{D} = \{1, \ldots, 32\}, applied to the response-level losses. The loss is computed per example and then averaged over the batch. All five objectives use the dataset and optimization settings in Table 4, with the final checkpoint at update 625.

Generation and scoring. We evaluated all 164 HumanEval and 500 MBPP problems. Each model generates one program greedily at each fixed depth in {4,8,12,16,24,32}\{4, 8, 12, 16, 24, 32\}, giving six candidates per problem. There is no stochastic sampling, test-guided repair, or regeneration. Prompt and generated output together are limited to 1,024 tokens.

Graph-Coloring Trajectory Analysis

Figure 4 uses the Last-Depth and BoD checkpoints trained at depth 16 with uniformly sampled targets for 10,000 updates. We evaluate them greedily through depth 64 without input permutations or initial-state noise. Solution IDs denote canonical coloring families, with colorings related by global color-label permutations assigned the same ID. The new-solution indicator at depth dd is

1[y^d(x)∈Y∗(x) and y^d(x)∉Sd−1(x)],(12)\mathbf{1}\left[\hat{y}_d(x) \in\mathcal{Y}^{*}(x)\ \text{and}\ \hat{y}_d(x) \notin S_{d-1}(x)\right], \tag*{(12)}

where S0(x)=∅S_0(x) = \varnothing and membership is evaluated using canonical color families. Discovery indicators are checked against the preceding decoded outputs and enumerated valid families. Each population curve averages all 512 graphs within each seed.

Relative displacement is computed before PCA as

Δd=∥h~d−h~d−1∥2∥h~d−1∥2,d=2,…,64,(13)\Delta_d = \frac{\lVert\tilde{h}_d - \tilde{h}_{d-1} \rVert_2}{\lVert\tilde{h}_{d-1} \rVert_2}, \qquad d = 2, \ldots, 64, \tag*{(13)}

where h~d\tilde{h}_d concatenates the ten recurrent core states at depth dd. To construct the histograms of loss-minimizing depths, we find the depth with the lowest graph-level mean loss for each graph–target pair among the 16 training depths. We weight graphs equally and valid targets uniformly within each graph. When losses tie exactly, we select the earliest depth attaining the minimum.

Additional Results

Solution Discovery across Depth

Tables 5–8 give the numerical results for Figure 2. The evaluation sets and training budgets are specified in Appendices § 11.§ 1 and § 11.§ 2. All models are trained at depth 16 and read out greedily at every depth up to the stated budget.

Method@1@4@8@16@32@64
Last-Depth0.00 ± 0.000.00 ± 0.000.00 ± 0.0022.27 ± 1.2743.29 ± 3.1245.75 ± 3.93
Mean-Depth0.00 ± 0.002.51 ± 0.1820.42 ± 1.2036.52 ± 2.2144.52 ± 1.6649.94 ± 1.05
Random-Depth0.00 ± 0.002.46 ± 0.1119.93 ± 0.5335.42 ± 0.9144.15 ± 1.2449.63 ± 1.34
Soft-Depth0.00 ± 0.002.63 ± 0.3721.53 ± 0.8238.99 ± 0.7948.26 ± 0.8353.01 ± 1.47
Best-of-Depth0.00 ± 0.000.10 ± 0.0917.11 ± 1.2585.92 ± 0.9390.97 ± 0.9891.03 ± 1.05

Table 5. N-Queens Coverage@Depth (%) on 1,000 multi-solution test problems. Models are trained at Dtrain=16D_{\mathrm{train}} = 16.

Method@1@4@8@16@32@64
Last-Depth0.00 ± 0.000.00 ± 0.000.00 ± 0.0044.80 ± 2.5278.23 ± 4.4881.13 ± 4.94
Mean-Depth0.00 ± 0.005.10 ± 0.4040.37 ± 1.8365.97 ± 3.2575.37 ± 2.5081.97 ± 2.46
Random-Depth0.00 ± 0.005.00 ± 0.2039.43 ± 1.3464.50 ± 1.6175.27 ± 1.7282.30 ± 2.35
Soft-Depth0.00 ± 0.005.30 ± 0.7042.37 ± 1.1168.67 ± 1.6979.13 ± 2.1084.20 ± 2.49
Best-of-Depth0.00 ± 0.000.20 ± 0.1733.03 ± 2.2097.13 ± 0.5599.00 ± 0.1099.03 ± 0.12

Table 6. N-Queens Success@Depth (%) on 1,000 multi-solution test problems. Models are trained at Dtrain=16D_{\mathrm{train}} = 16.

Method@1@4@8@16@32@64
Last-Depth0.05 ± 0.012.01 ± 0.108.55 ± 0.7715.79 ± 0.8818.30 ± 0.8818.62 ± 0.76
Mean-Depth2.67 ± 0.0911.99 ± 0.2514.11 ± 0.0514.84 ± 0.0315.09 ± 0.0715.15 ± 0.07
Random-Depth2.38 ± 0.2011.51 ± 0.1513.87 ± 0.2914.42 ± 0.2514.68 ± 0.1514.75 ± 0.16
Soft-Depth0.88 ± 0.2515.17 ± 0.5924.36 ± 0.6636.64 ± 0.5342.18 ± 0.7744.39 ± 0.80
Best-of-Depth0.71 ± 0.4214.18 ± 0.5330.76 ± 0.7054.95 ± 0.8066.79 ± 1.8972.16 ± 3.62

Table 7. Graph-coloring Coverage@Depth (%) on 512 test graphs. Models are trained at Dtrain=16D_{\mathrm{train}} = 16.

Method@1@4@8@16@32@64
Last-Depth0.59 ± 0.3420.70 ± 1.4750.98 ± 2.9270.31 ± 1.8673.76 ± 1.3974.09 ± 1.30
Mean-Depth23.37 ± 0.9661.72 ± 1.2267.38 ± 0.2068.42 ± 0.1168.82 ± 0.1168.88 ± 0.11
Random-Depth21.88 ± 1.2860.16 ± 0.5266.28 ± 0.6367.12 ± 0.3067.32 ± 0.1167.38 ± 0.00
Soft-Depth10.74 ± 1.7979.88 ± 2.3494.60 ± 1.5897.98 ± 0.1198.44 ± 0.2098.63 ± 0.20
Best-of-Depth9.18 ± 4.0474.48 ± 1.4794.21 ± 0.7499.67 ± 0.3099.87 ± 0.2399.93 ± 0.11

Table 8. Graph-coloring Success@Depth (%) on 512 test graphs. Models are trained at Dtrain=16D_{\mathrm{train}} = 16.

At depth 64, graph-coloring BoD achieves 99.93 ± 0.11% success and 72.16 ± 3.62% coverage. On the multi-solution N-Queens test population, the corresponding values are 99.03 ± 0.12% and 91.03 ± 1.05%.

Width and Depth under a Fixed Recurrent-Step Budget

Tables 9 and 10 give the values plotted in Figure 3(a, Figure 3b). All seven allocations use ND=64ND = 64, pooling valid predictions from every intermediate depth of all trajectories before computing per-problem coverage. Each training seed averages 32 inference repeats.

For each N-Queens trajectory, we initialize the recurrent state with independent Gaussian noise scaled by the encoded input:

h0(j)=0.1 RMS⁡(Enc⁡θ(x)) ϵj,ϵj∼N(0,I),(14)h_0^{(j)} = 0.1\,\operatorname{RMS}(\operatorname{Enc}_{\theta}(x))\,\epsilon_j,\qquad\epsilon_j \sim\mathcal{N}(0,I), \tag*{(14)}

where RMS is the root mean square over entries of the encoded input, which remains unchanged during initialization. The scale is selected from {0,0.03,0.1,0.3}\{0, 0.03, 0.1, 0.3\} by mean development coverage at (N,D)=(4,16)(N,D)=(4,16) across both methods and all three seeds. The selected value, 0.1, is fixed before test evaluation. For graph coloring, we instead independently permute vertices for each trajectory, map predictions back to the original vertex order, and canonicalize color names before pooling solutions. Both procedures also apply at N=1N=1.

Depth DDTrajectories NNLast-DepthBest-of-Depth
1640.00±0.000.00 \pm0.000.00±0.000.00 \pm0.00
2320.00±0.000.00 \pm0.000.00±0.000.00 \pm0.00
4160.00±0.000.00 \pm0.000.50±0.300.50 \pm0.30
880.00±0.000.00 \pm0.0031.78±1.8131.78 \pm1.81
16448.49±2.0648.49 \pm2.0694.13±0.5694.13 \pm0.56
32256.25±2.4056.25 \pm2.4093.45±0.9293.45 \pm0.92
64144.55±3.8544.55 \pm3.8588.28±1.3288.28 \pm1.32

Table 9. N-Queens Coverage@Depth (%) at ND=64ND=64, pooling all NN trajectories through depth DD.

Depth DDTrajectories NNLast-DepthBest-of-Depth
1642.25±1.252.25 \pm1.2533.85±10.3433.85 \pm10.34
2322.26±1.352.26 \pm1.3562.86±2.6362.86 \pm2.63
41620.61±1.8220.61 \pm1.8277.28±0.6777.28 \pm0.67
8836.39±0.6536.39 \pm0.6582.80±0.2082.80 \pm0.20
16437.50±0.5137.50 \pm0.5185.86±0.4985.86 \pm0.49
32228.54±0.5228.54 \pm0.5282.67±1.4482.67 \pm1.44
64118.12±0.4118.12 \pm0.4172.14±3.4772.14 \pm3.47

Table 10. Graph-coloring Coverage@Depth (%) at ND=64ND=64, pooling all NN trajectories through depth DD.

Training Depth and Test-Time Extrapolation

The training-depth ablation uses BoD models trained at depths 4, 8, and 16, each with three seeds. The protocol holds the evaluation population and training-update budget fixed within each task, as specified in Appendix A. Depth-16 models are the same as in Figure 2. Evaluation uses unperturbed greedy trajectories. Tables 11 and 12 give coverage values for Figure 3(c, Figure 3d).

Training depth@4@8@16@32@64
46.48±3.886.48 \pm3.888.11±3.968.11 \pm3.968.21±4.018.21 \pm4.018.21±4.018.21 \pm4.018.21±4.018.21 \pm4.01
86.61±2.736.61 \pm2.7360.21±11.7260.21 \pm11.7275.15±11.9975.15 \pm11.9975.66±11.9075.66 \pm11.9075.70±11.9575.70 \pm11.95
160.10±0.090.10 \pm0.0917.11±1.2517.11 \pm1.2585.92±0.9385.92 \pm0.9390.97±0.9890.97 \pm0.9891.03±1.0591.03 \pm1.05

Table 11. N-Queens BoD Coverage@Depth (%) across training and test depths.

Training depth@4@8@16@32@64
421.09±0.5021.09 \pm0.5027.64±0.8327.64 \pm0.8331.53±0.5431.53 \pm0.5433.32±0.6433.32 \pm0.6434.13±0.6934.13 \pm0.69
817.02±0.5517.02 \pm0.5534.69±0.9234.69 \pm0.9244.86±0.9044.86 \pm0.9050.38±1.1050.38 \pm1.1053.11±1.5753.11 \pm1.57
1614.18±0.5314.18 \pm0.5330.76±0.7030.76 \pm0.7054.95±0.8054.95 \pm0.8066.79±1.8966.79 \pm1.8972.16±3.6272.16 \pm3.62

Table 12. Graph-coloring BoD Coverage@Depth (%) across training and test depths.

Figure 5 and Table 13 show the corresponding success results. Success increases beyond the training depth for the depth-4 and depth-8 models on both tasks. For graph coloring, success saturates earlier than coverage, separating initial solution finding from continued discovery of alternatives.

Figure 5. Success across training and evaluation depths. Success@Depth for BoD trained at depths 4, 8, and 16, using the same checkpoints and evaluation problems as Figure 3(c, Figure 3d). Open markers indicate evaluation at the training depth; bands indicate ±1\pm1 SD.

Training depth@4@8@16@32@64
N-Queens
412.67 ±\pm 7.3115.90 ±\pm 7.4116.07 ±\pm 7.5116.07 ±\pm 7.5116.07 ±\pm 7.51
813.73 ±\pm 5.7883.27 ±\pm 8.4294.40 ±\pm 4.5494.77 ±\pm 4.3794.80 ±\pm 4.39
160.20 ±\pm 0.1733.03 ±\pm 2.2097.13 ±\pm 0.5599.00 ±\pm 0.1099.03 ±\pm 0.12
Graph Coloring
488.09 ±\pm 0.8593.29 ±\pm 0.9294.86 ±\pm 1.7195.51 ±\pm 1.2895.57 ±\pm 1.30
882.36 ±\pm 0.5696.48 ±\pm 0.9098.70 ±\pm 0.4599.15 ±\pm 0.3099.22 ±\pm 0.39
1674.48 ±\pm 1.4794.21 ±\pm 0.7499.67 ±\pm 0.3099.87 ±\pm 0.2399.93 ±\pm 0.11

Table 13. BoD Success@Depth (%) for Figure 5.

Sensitivity to the Soft-Depth Temperature

The temperature in Soft-Depth controls how strongly learning concentrates on the lowest-loss readouts. We vary τ∈{0.1,0.2,…,1.0}\tau\in\{0.1, 0.2, \ldots, 1.0\} on graph coloring and evaluate cumulative success and coverage through depth 64, keeping all other settings fixed (Appendix § 11.§ 2). Coverage decreases as temperature increases, approaching Mean-Depth at larger temperatures (Figure 6). The development-selected τ=0.1\tau= 0.1 achieves 62.41% test coverage, compared with 72.16% for BoD, while both achieve success above 99%.

Withheld-Solution Discovery Protocol

The ablation in § 5.3 uses 3,034 graphs from the graph-coloring training split with at least five canonical valid solutions per graph. The cohort contains 79,713 solutions in total, with 5–128 per graph (mean 26.27). This restriction leaves withheld solutions in every one- through four-target condition; it changes the evaluation cohort relative to the full graph-coloring experiment. All coloring families are identified up to a global permutation of color names, as in Appendix § 11.§ 2.

For each graph and experimental seed, one random ordering of all valid solutions defines nested teacher pools of sizes one, two, three, and four. The all-solutions condition uses the complete pool. Pools remain fixed throughout each run; only the selected teacher is resampled at each presentation. Last-Depth and BoD share teacher pools, target draws, graph order, and initialization within each seed. The protocol uses the architecture and optimizer in Appendix § 11.§ 2, training depth 16, 10,000 updates, and three paired seeds.

Last-Depth and BoD each run one unperturbed trajectory through depth 64. Last-Depth + BoN reuses the Last-Depth checkpoint and pools predictions from independently vertex-permuted trajectories under ND=64N_D = 64. The allocation is selected from the seven pairs in § 5.1 using development-set coverage averaged across teacher conditions and seeds. This selects N=4N = 4 trajectories of depth D=16D = 16, fixed before evaluating withheld-solution discovery. Outputs are mapped back to the original vertex order before verification and canonicalization. Every method collects all intermediate readouts; Last-Depth + BoN therefore denotes sampling with all-depth readout, rather than terminal-only sampling. Randomized evaluation uses 32 repeats per training seed.

Seen and unseen coverage are macro-averaged over the same fixed graph cohort, using the teacher pool and its valid-solution complement as their respective denominators. Since increasing the teacher pool reduces the number of withheld solutions, supporting measurements include total coverage, the number of distinct unseen solutions recovered and the fraction of graphs with at least one such solution. The all-solutions condition has no withheld solutions, so its unseen coverage is undefined, while seen coverage equals total coverage.

Additional Baseline Protocols

The comparisons in Table 14 use the same datasets, teacher sampling, optimization settings, width 128, eight attention heads, and FFN width 384 as the main experiments. Each method uses three training seeds and a fixed final EMA checkpoint after 20,000 updates for N-Queens or 10,000 updates for graph coloring. These are independent implementations under a common training recipe. Parameter counts and training and inference FLOPs are not matched.

Table 14: Baseline comparison on N-Queens and graph coloring. Success and Coverage (%) summarize each method’s candidate set. Ouro uses an instance-level adaptation of its training objective. Compute and candidate counts differ across architectures; Appendix § 13.§ 7 gives the protocol.

The unshared Transformers have eight or 32 layers and produce one candidate per input. The autoregressive baseline uses a four-layer decoder and produces one complete candidate. Masked diffusion uses four layers with a SUBS parameterization and a completed 64-step denoising schedule. HRM uses four-layer low- and high-level modules with two cycles at each level; TRM uses two shared layers, four inner iterations, three cycles, and at most 16 outer training segments. HRM and TRM are evaluated with a fixed 64-step expansion rather than their native adaptive stopping rule. BoD and Ouro also collect all readouts through depth 64. Success and coverage are computed on the resulting candidate sets, using the definitions in § 4.1. For the autoregressive and diffusion baselines, metrics are averaged across three inference seeds within each training seed, without pooling candidates across repeats.

The Ouro baseline applies its Stage I expected-loss and entropy-regularization objective to whole instances, using the same looped backbone as BoD. A shared linear gate pools the recurrent states over unknown cells for N-Queens and over vertices for graph coloring, then predicts a sigmoid exit hazard at each depth. The first 15 hazards define an exit distribution by survival products, with the remaining mass assigned to depth 16. The gate adds 129 parameters; its weights start at zero and its bias at −log⁡15-\log15. Training minimizes the expected per-instance loss plus β\beta times the KL divergence of the exit distribution from the uniform distribution over the 16 training depths. Evaluation collects all greedy readouts through depth 64; the gate neither stops the trajectory nor filters candidates. This comparison adapts the learning objective, rather than evaluating a pretrained Ouro language model or reproducing its second training stage.

We select one positive coefficient per task by mean development Coverage@Depth at depth 64 over three training seeds, using the grid {0.001,0.003,0.01,0.03,0.05,0.1,0.25,1}\{0.001, 0.003, 0.01, 0.03, 0.05, 0.1, 0.25, 1\}. A separate β=0\beta= 0 control is excluded from selection; exact ties favor the smaller coefficient. The selected values are β=0.03\beta= 0.03 for N-Queens and β=0.001\beta= 0.001 for graph coloring, using 200 multi-solution development puzzles and 512 development graphs, respectively.

Theoretical Analysis

Throughout this appendix, fix a non-autoregressive input xx and a deterministic recurrent trajectory. Targets are drawn from the finite valid solution set Y∗(x)\mathcal{Y}^{*}(x), with cardinality M≥1M \ge1, uniformly unless otherwise specified. For the cross-entropy results, all depths 1,…,D1,\ldots,D are read out. The joint readout distribution on the complete output space Ω\Omega, with pd,jp_{d,j} the categorical distribution at predicted position jj, is

Pd(y∣x)=∏j=1T(x)pd,j(yj∣x).(15)P_d(y \mid x) = \prod_{j=1}^{T(x)} p_{d,j}(y_j \mid x). \tag*{(15)}

It is normalized over Ω\Omega, which includes invalid assignments. All logarithms are natural. For cross-entropy, define the expected whole-example loss

sD(x)=T(x)EY[LBoD(x,Y)]=EY[−log⁡max⁡d≤DPd(Y∣x)].(16)s_D(x) = T(x)\mathbb{E}_Y[\mathcal{L}_{\mathrm{BoD}}(x,Y)] = \mathbb{E}_Y\left[-\log\max_{d\le D} P_d(Y \mid x)\right]. \tag*{(16)}

Here T(x)T(x) is the number of predicted positions; the factor T(x)T(x) reverses the position averaging in the training loss. We suppress xx where the conditioning is unambiguous.

Proofs of Propositions 1 and 2

For Proposition 1, the minimum of the binary losses is zero exactly when at least one readout equals the target, which is equivalent to τy≤D\tau_y \le D. Hence the loss equals 1[τy>D]\mathbf{1}[\tau_y > D] pointwise. Taking an expectation over any distribution of target–trajectory pairs gives Eq. (7).

For Proposition 2, fix the candidate set independently of the sampled target. For any distribution qq supported on Y∗(x)\mathcal{Y}^{*}(x),

EY[LBoD0-1∣x]=∑y∈Y∗(x)q(y∣x) 1[y∉SD(x)](17)\mathbb{E}_Y[\mathcal{L}_{\mathrm{BoD}}^{0\text{-}1} \mid x] = \sum_{y\in\mathcal{Y}^{*}(x)} q(y \mid x)\,\mathbf{1}[y \notin S_D(x)] \tag*{(17)}
=1−∑y∈SD(x)∩Y∗(x)q(y∣x).(18)= 1 - \sum_{y\in S_D(x)\cap\mathcal{Y}^{*}(x)} q(y \mid x). \tag*{(18)}

When q(y∣x)=1/Mq(y \mid x) = 1/M, the second term is exactly the fraction of valid solutions in the candidate set, proving Eq. (8). For a random candidate set, the same identity holds conditional on that set, provided it is independent of the target given xx; averaging then yields expected coverage.

For graph-coloring family coverage, both the candidates in SD(x)S_D(x) and the predictions in the exact-match loss are canonicalized in the same way. The target set contains one canonical representative per valid family. Using raw color-label equality on the left and family coverage on the right would not give this identity. The cross-entropy results below instead use the raw joint distribution in Eq. (15): generating a canonical target is sufficient to discover its family, so their coverage lower bounds also hold after canonicalization.

Depth-Wise Sampling and Coverage

Lemma 1 (Distinct valid solutions from depth-wise sampling). Draw Y~d∼Pd(⋅∣x)\widetilde{Y}_d \sim P_d(\cdot\mid x) at each depth and set SD(x)={Y~d:d≤D}S_D(x) = \{\widetilde{Y}_d : d \le D\}. Let KDK_D count the distinct valid solutions in this random candidate set. Then

E[KD∣x]≥Me−sD(x),E[Coverage@Depth(D;x)∣x]≥e−sD(x).(19)\mathbb{E}[K_D \mid x] \ge M e^{-s_D(x)}, \qquad\mathbb{E}[\mathrm{Coverage@Depth}(D;x) \mid x] \ge e^{-s_D(x)}. \tag*{(19)}

The expectations are over candidate sampling; independence between candidates is not required.

Proof. For each valid solution yy, define Ay={Y~d=yA_y = \{\widetilde{Y}_d = y for some d≤D}d \le D\}. The union contains each individual event, hence

Pr⁡(Ay∣x)≥max⁡d≤DPr⁡(Y~d=y∣x)=max⁡d≤DPd(y∣x).(20)\Pr(A_y \mid x) \ge\max_{d \le D} \Pr(\widetilde{Y}_d = y \mid x) = \max_{d \le D} P_d(y \mid x). \tag*{(20)}

This uses only the marginal distribution of each candidate. Let

aD(y)=max⁡d≤DPd(y∣x),ZD⋆=∑y∈Y⋆(x)aD(y).(21)a_D(y) = \max_{d \le D} P_d(y \mid x), \qquad Z_D^\star= \sum_{y \in\mathcal{Y}^\star(x)} a_D(y). \tag*{(21)}

Linearity of expectation gives E[KD∣x]≥ZD⋆\mathbb{E}[K_D \mid x] \ge Z_D^\star. Since targets are uniform, Jensen’s inequality for the convex function −log⁡-\log yields

sD=1M∑y∈Y⋆(x)−log⁡aD(y)≥−log⁡(ZD⋆M).(22)s_D = \frac{1}{M}\sum_{y \in\mathcal{Y}^\star(x)} -\log a_D(y) \ge-\log\left(\frac{Z_D^\star}{M}\right). \tag*{(22)}

Thus ZD⋆≥Me−sDZ_D^\star\ge M e^{-s_D}, proving the count bound. Dividing by MM gives the coverage bound. If some valid target has aD(y)=0a_D(y)=0, then sD=∞s_D=\infty and the stated lower bound is zero.

The result also holds when additional candidates are drawn at any depth because adding candidates cannot remove the discovered solution. The sampling distributions must match those used in the loss function. For independent draws, the exact expected count for one sample per depth is

E[KD∣x]=∑y∈Y⋆(x)[1−∏d=1D(1−Pd(y∣x))].(23)\mathbb{E}[K_D \mid x] = \sum_{y \in\mathcal{Y}^\star(x)} \left[1-\prod_{d=1}^{D}\left(1-P_d(y \mid x)\right)\right]. \tag*{(23)}

Sharpness. Suppose MM is divisible by DD. Partition the valid solutions into DD disjoint subsets of size M/DM/D, and let PdP_d be uniform on the ddth subset. Then sD=log⁡(M/D)s_D=\log(M/D), and one draw from each depth produces exactly D=Me−sDD = M e^{-s_D} distinct valid solutions. This establishes sharpness as a bound on normalized readout distributions. It does not require that a particular factorized decoder can represent every such partition.

A Shared-Recurrent Construction for Proposition 3

Task and valid solutions. There is one input, the labeled complete bipartite graph K3,3K_{3,3}. Its valid outputs are the six perfect matchings, represented by the 3×33 \times3 permutation matrices in M\mathcal{M}. The output space is {0,1}3×3\{0,1\}^{3 \times3}; a selected edge has value one. A training target YY is drawn independently and uniformly from M\mathcal{M} at each update. Every edge occurs in two matchings, so E[Y]=J/3\mathbb{E}[Y] = J/3, where JJ is the all-ones matrix. The model does not receive the target as input, and decoding does not enforce the matching constraints.

One shared recurrence. Let r=(1 2 3)r=(1\ 2\ 3) permute the left vertices and c=(1 2)c=(1\ 2) permute the right vertices. Define the fixed linear map R\mathcal{R} by (RA)r(i),c(j)=Aij(\mathcal{R}A)_{r(i),c(j)}=A_{ij}. This is a symmetry of the graph and preserves matchings. It satisfies R6=I\mathcal{R}^{6}=I, and every matching has a full orbit:

{RdM:d=1,…,6}=M(M∈M).(24)\{\mathcal{R}^{d}M:d=1,\ldots,6\}=\mathcal{M}\qquad(M\in\mathcal{M}). \tag*{(24)}

Indeed, identify a matching with a permutation π\pi from left to right vertices. If RdMπ=Mπ\mathcal{R}^{d}M_{\pi}=M_{\pi}, then cd=πrdπ−1c^{d}=\pi r^{d}\pi^{-1}. When 3∤d3\nmid d, the right side has order three while the left has order one or two. Thus 3∣d3\mid d, and the identity then also requires 2∣d2\mid d. The orbit therefore has length six.

The only trainable parameter is a matrix θ∈R3×3\theta\in\mathbb{R}^{3\times3}. Let Π\Pi denote the permutation matrix representing R\mathcal{R} on vectorized matrices. A ten-dimensional hidden state with fixed initialization evolves according to

h0=(091),hd=S(θ)hd−1,S(θ)=(ΠΠvec⁡(θ)01×90).(25)h_{0}=\begin{pmatrix}0_{9}\\1\end{pmatrix},\qquad h_{d}=S(\theta)h_{d-1},\qquad S(\theta)=\begin{pmatrix}\Pi&\Pi\operatorname{vec}(\theta)\\0_{1\times9}&0\end{pmatrix}. \tag*{(25)}

The first nine entries of hdh_d give a logit matrix HdH_d; the last entry is zero after the first recurrent step. Consequently, Hd=RdθH_d=\mathcal{R}^{d}\theta. The same parameter-dependent matrix S(θ)S(\theta) is applied at every depth, but the trainable pattern is injected only at the first step. Subsequent steps apply the prescribed permutation. Thus, this construction studies how the objective uses an available recurrent orbit, rather than learning that orbit’s rule.

Readout and common training protocol. All methods use D=6D=6 and the shared factorized Bernoulli readout

Pθ,d(y)=∏i,jσ(Hd,ij)yij[1−σ(Hd,ij)]1−yij,Ld(θ;Y)=−19log⁡Pθ,d(Y),(26)P_{\theta,d}(y)=\prod_{i,j}\sigma(H_{d,ij})^{y_{ij}}[1-\sigma(H_{d,ij})]^{1-y_{ij}},\qquad L_d(\theta;Y)=-\frac{1}{9}\log P_{\theta,d}(Y), \tag*{(26)}

where σ\sigma is the sigmoid. Greedy decoding selects an edge exactly when its logit is positive. Each method starts at θ(0)=bJ\theta^{(0)}=bJ, with b=−log⁡2b=-\log2, and uses single-example SGD with ηn=9/(n+1)\eta_n=9/(n+1). This is equivalent to step size 1/(n+1)1/(n+1) on the summed loss; the factor nine accounts for the position averaging in Eq. (26). Random-Depth samples its depth independently of the target. BoD selects one minimizing depth uniformly when losses tie. Soft-Depth uses any fixed τ>0\tau>0 in Eq. (6). All methods may share the same target sequence. For the one input in this construction,

Coverage@Depth⁡(6;θ)=∣{1[Rdθ>0]:d=1,…,6}∩M∣6.(27)\operatorname{Coverage@Depth}(6;\theta)=\frac{\left|\left\{\mathbf{1}[\mathcal{R}^{d}\theta>0]:d=1,\ldots,6\right\}\cap\mathcal{M}\right|}{6}. \tag*{(27)}

The indicator acts entrywise. This makes explicit the parameter dependence used in Proposition 3.

Proof of Proposition 3. Write Φ(θ)=∑i,jlog⁡(1+eθij)\Phi(\theta)=\sum_{i,j}\log(1+e^{\theta_{ij}}) and use the Frobenius inner product. Because R\mathcal{R} permutes entries,

Ld(θ;Y)=19[Φ(θ)−⟨θ,R−dY⟩],∇θLd(θ;Y)=19[σ(θ)−R−dY].(28)L_d(\theta;Y)=\frac{1}{9}\left[\Phi(\theta)-\langle\theta,\mathcal{R}^{-d}Y\rangle\right],\qquad\nabla_{\theta}L_d(\theta;Y)=\frac{1}{9}\left[\sigma(\theta)-\mathcal{R}^{-d}Y\right]. \tag*{(28)}

Baseline minimizers and stationary objectives. Let RAR_A denote the expected loss for objective AA, including any random depth. Equation (24) implies 16∑d=16R−dY=J/3\frac{1}{6}\sum_{d=1}^{6}\mathcal{R}^{-d}Y=J/3 for every target. Hence

RLast(θ)=RMean(θ)=RRandom(θ)=19[Φ(θ)−⟨θ,J/3⟩].(29)R_{\mathrm{Last}}(\theta)=R_{\mathrm{Mean}}(\theta)=R_{\mathrm{Random}}(\theta)=\frac{1}{9}\left[\Phi(\theta)-\langle\theta,J/3\rangle\right]. \tag*{(29)}

This risk has positive diagonal Hessian entries (σ(θij)[1−σ(θij)])/9(\sigma(\theta_{ij})[1-\sigma(\theta_{ij})])/9 and the unique minimizer bJbJ. For Mean-Depth the loss already equals this risk for each individual target, so its gradient is zero at initialization and it remains there.

At bJbJ, all depthwise losses tie. Soft-Depth therefore assigns weight 1/61/6 to each gradient, independently of τ>0\tau>0. For every target,

∇θLSoft−Depth∣bJ=19[13J−16∑d=16R−dY]=0.(30)\nabla_{\theta}\mathcal{L}_{\mathrm{Soft-Depth}}\big|_{bJ}=\frac{1}{9}\left[\frac{1}{3}J-\frac{1}{6}\sum_{d=1}^{6}\mathcal{R}^{-d}Y\right]=0. \tag*{(30)}

It too remains exactly at initialization. Every logit is then b<0b < 0 at every depth, so Mean-Depth and Soft-Depth always have zero greedy coverage.

Almost-sure convergence for Last-Depth and Random-Depth. Their updates have the form θ(n+1)=θ(n)−an[σ(θ(n))−Zn]\theta^{(n+1)} = \theta^{(n)} - a_n[\sigma(\theta^{(n)}) - Z_n], where an=1/(n+1)a_n = 1/(n+1) and, conditional on the training history Fn\mathcal{F}_n, ZnZ_n is uniform over M\mathcal{M}. Set Vn=∥θ(n)−bJ∥22V_n = \lVert\theta^{(n)} - bJ\rVert_2^2 and A(θ)=⟨θ−bJ,σ(θ)−J/3⟩A(\theta) = \langle\theta- bJ, \sigma(\theta) - J/3\rangle. Strict monotonicity of the sigmoid gives A(θ)>0A(\theta) > 0 except at bJbJ; the bounded components of the stochastic gradient give

E[Vn+1∣Fn]≤Vn−2anA(θ(n))+9an2.(31)\mathbb{E}[V_{n+1}\mid\mathcal{F}_n] \le V_n - 2a_n A(\theta^{(n)}) + 9a_n^2. \tag*{(31)}

Thus Vn+9∑k=n∞ak2V_n + 9\sum_{k=n}^{\infty} a_k^2 is a nonnegative supermartingale. It converges almost surely, and summing its expected drift yields ∑nanA(θ(n))<∞\sum_n a_n A(\theta^{(n)}) < \infty almost surely. Consequently VnV_n has a finite limit. If this limit were positive, the iterates would eventually lie in a compact annulus about bJbJ on which AA has a positive minimum. This contradicts ∑nan=∞\sum_n a_n = \infty. Therefore both methods converge almost surely to bJbJ. Since b<0b < 0, all logits eventually remain negative, and greedy coverage is eventually zero.

BoD breaks symmetry and retains one latent matching. The orbit identity gives, for every target,

LBoD(θ;Y)=19[Φ(θ)−max⁡M∈M⟨θ,M⟩].(32)\mathcal{L}_{\mathrm{BoD}}(\theta;Y) = \frac{1}{9}\left[\Phi(\theta) - \max_{M\in\mathcal{M}}\langle\theta,M\rangle\right]. \tag*{(32)}

At initialization, let the selected tied depth for Y0Y_0 be d0⋆d_0^\star and set M⋆=R−d0⋆Y0M_\star= \mathcal{R}^{-d_0^\star}Y_0. The first update gives

θ(1)=bJ+M⋆−J/3.(33)\theta^{(1)} = bJ + M_\star- J/3. \tag*{(33)}

Its entries equal α1=b+2/3\alpha_1 = b + 2/3 on M⋆M_\star and β1=b−1/3\beta_1 = b - 1/3 elsewhere. For any other matching sharing t<3t < 3 edges with M⋆M_\star, the score gap is (3−t)(α1−β1)>0(3-t)(\alpha_1-\beta_1) > 0. Thus M⋆M_\star is now the unique maximum-score matching. For every subsequent target YY, BoD selects the phase satisfying Rd⋆M⋆=Y\mathcal{R}^{d^\star}M_\star= Y, so

∇θLBoD(θ;Y)=19[σ(θ)−M⋆].(34)\nabla_\theta\mathcal{L}_{\mathrm{BoD}}(\theta;Y) = \frac{1}{9}[\sigma(\theta)-M_\star]. \tag*{(34)}

All targets reinforce the same latent matching. The two logit values satisfy

αn+1=αn+an[1−σ(αn)],βn+1=βn−anσ(βn),n≥1.(35)\alpha_{n+1} = \alpha_n + a_n[1-\sigma(\alpha_n)], \qquad\beta_{n+1} = \beta_n - a_n\sigma(\beta_n), \qquad n \ge1. \tag*{(35)}

Their gap grows, preserving the unique maximizing matching. Both are negative after the first update, but α2>−log⁡2+2/3+1/4>0\alpha_2 > -\log2 + 2/3 + 1/4 > 0 while β2<0\beta_2 < 0. These signs persist. For every n≥2n \ge2, greedy decoding therefore yields y^d=RdM⋆\hat{y}_d = \mathcal{R}^dM_\star, whose six distinct values are all valid matchings. BoD has full coverage from the second update onward. This finite-update count uses the stated loss normalization and step sizes. Together with the baseline results, it proves the proposition.

The Soft-Depth result relies on exact symmetry at initialization. The prescribed recurrent orbit makes this an existence result for a shared recurrent model.

Numerical illustration. We run the specified SGD updates for 4,096 iterations in float64 on 64 independent teacher streams (seeds 0–63), shared across objectives within each run. Independent random streams select Random-Depth readouts and resolve the initial BoD tie. Soft-Depth is evaluated at τ∈{0.1,0.25,1}\tau\in\{0.1, 0.25, 1\}. Every reported checkpoint is decoded at all six depths and verified against the complete set of matchings. The Soft-Depth updates are computed from their actual weighted gradients; no special rule holds the parameters at initialization. Table 15 illustrates the proved distinction: BoD reaches full coverage after two updates in every run, whereas all four comparison objectives have zero coverage at the final checkpoint. Last-Depth and Random-Depth can temporarily produce valid solutions, consistent with the theorem, which describes eventual behavior rather than behavior at every iteration. The experiment is a numerical illustration of this construction, separate from the learned looped Transformer experiments. The implementation and per-run results accompany the paper.

Training objective02162564,096
Last-Depth0.015.61.60.00.0
Mean-Depth0.00.00.00.00.0
Random-Depth0.018.81.60.00.0
Soft-Depth (τ=0.1\tau= 0.1)0.00.00.00.00.0
Soft-Depth (τ=0.25\tau= 0.25)0.00.00.00.00.0
Soft-Depth (τ=1.0\tau= 1.0)0.00.00.00.00.0
Best-of-Depth0.0100.0100.0100.0100.0

Table 15. Numerical illustration of Proposition 3. Greedy Coverage@Depth at D=6D = 6 (%), averaged over 64 independent SGD runs on the same matching problem. Columns count training updates. All objectives use the same teacher stream within each run and the same initialization and step sizes.

A Certificate for Greedy Solution Coverage

Let SDS_D contain the distinct positionwise-greedy predictions from the same readouts. Then

∣SD∩Y⋆(x)∣M≥[1−sD(x)log⁡2]+.(36)\frac{\lvert S_D \cap Y^\star(x)\rvert}{M} \ge\left[1 - \frac{s_D(x)}{\log2}\right]_+. \tag*{(36)}

To prove this, consider a valid target y∉SDy \notin S_D. At every depth, at least one position is decoded to a token other than yjy_j. At that position, pd,j(yj∣x)≤1/2p_{d,j}(y_j \mid x) \le1/2, so −log⁡Pd(y∣x)≥log⁡2-\log P_d(y \mid x) \ge\log2. Consequently,

1[y∉SD]≤min⁡d≤D−log⁡Pd(y∣x)log⁡2.(37)\mathbf{1}[y \notin S_D] \le\frac{\min_{d \le D} -\log P_d(y \mid x)}{\log2}. \tag*{(37)}

Averaging over the uniform target distribution proves Eq. (36). The result is nontrivial when the whole-example risk is below log⁡2\log2; for the position-averaged loss, the corresponding threshold is log⁡2/T(x)\log2/T(x). In graph coloring, matching a canonical target exactly is sufficient to discover its canonical family, so subsequent canonicalization preserves this lower bound.

References

  1. [1]Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie Cai, Michael Terry, Quoc Le, and Charles Sutton. Program synthesis with large language models. arXiv preprint arXiv:2108.07732, 2021. URL https://arxiv.org/abs/2108.07732.
  2. [2]Sangmin Bae, Adam Fisch, Hrayr Harutyunyan, Ziwei Ji, Seungyeon Kim, and Tal Schuster. Relaxed recursive transformers: Effective parameter sharing with layer-wise LoRA. In International Conference on Learning Representations, 2025a. URL https://openreview.net/forum?id=WwpYSOkKtC.arxiv.org/abs/2410.20672
  3. [3]Sangmin Bae, Yujin Kim, Reza Bayat, Sungyun Kim, Jiyoun Ha, Tal Schuster, Adam Fisch, Hrayr Harutyunyan, Ziwei Ji, Aaron Courville, and Se-Young Yun. Mixture-of-recursions: Learning dynamic recursive depths for adaptive token-level computation. In Advances in Neural Information Processing Systems, 2025b. URL https://openreview.net/forum?id=QugsEIVWIG.
  4. [4]Apratim Bhattacharyya, Bernt Schiele, and Mario Fritz. Accurate and diverse sampling of sequences based on a “best of many” sample objective. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2018. URL https://arxiv.org/abs/1806.07772.
  5. [5]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. URL https://arxiv.org/abs/2407.21787.
  6. [6]Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, et al. Evaluating large language models trained on code. arXiv preprint arXiv:2107.03374, 2021. URL https://arxiv.org/abs/2107.03374.
  7. [7]Yinlam Chow, Guy Tennenholtz, Izzeddin Gur, Vincent Zhuang, Bo Dai, Sridhar Thiagarajan, Craig Boutilier, Rishabh Agarwal, Aviral Kumar, and Aleksandra Faust. Inference-aware fine-tuning for best-of-N sampling in large language models. In International Conference on Learning Representations, 2025. URL https://arxiv.org/abs/2412.15287.
  8. [8]Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman. Training verifiers to solve math word problems. arXiv preprint arXiv:2110.14168, 2021. URL https://arxiv.org/abs/2110.14168.
  9. [9]Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Lukasz Kaiser. Universal transformers. In International Conference on Learning Representations, 2019. URL https://arxiv.org/abs/1807.03819.
  10. [10]Ying Fan, Anej Svete, and Kangwook Lee. Bridging the gap between latent and explicit reasoning with looped transformers. arXiv preprint arXiv:2606.31779, 2026. URL https://arxiv.org/abs/2606.31779.
  11. [11]Khashayar Gatmiry, Nikunj Saunshi, Sashank J. Reddi, Stefanie Jegelka, and Sanjiv Kumar. Can looped transformers learn to implement multi-step gradient descent for in-context learning? In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pp. 15130–15152. PMLR, 2024. URL https://proceedings.mlr.press/v235/gatmiry24b.html.arxiv.org/abs/2410.08292
  12. [12]Jonas Geiping, Sean McLeish, Neel Jain, John Kirchenbauer, Siddharth Singh, Brian R. Bartoldson, Bhavya Kailkhura, Abhinav Bhatele, and Tom Goldstein. Scaling up test-time compute with latent reasoning: A recurrent depth approach. In Advances in Neural Information Processing Systems, 2025. URL https://openreview.net/forum?id=S3GnJooWIC.arxiv.org/abs/2502.05171
  13. [13]Angeliki Giannou, Shashank Rajput, Jy-yong Sohn, Kangwook Lee, Jason D. Lee, and Dimitris Papailiopoulos. Looped transformers as programmable computers. In International Conference on Machine Learning, 2023. URL https://proceedings.mlr.press/v202/giannou23a.html.arxiv.org/abs/2301.13196
  14. [14]Alexi Gladstone, Heng Ji, and Yilun Du. Explorative modeling: Unlocking a third pretraining axis and end-to-end generation. arXiv preprint arXiv:2607.27372, 2026. URL https://arxiv.org/abs/2607.27372.
  15. [15]Abner Guzmán-Rivera, Dhruv Batra, and Pushmeet Kohli. Multiple choice learning: Learning to produce multiple structured outputs. In Advances in Neural Information Processing Systems, 2012. URL https://proceedings.neurips.cc/paper_files/paper/2012/hash/cfbce4c1d7c425baf21d6b6f2babe6be-Abstract.html.
  16. [16]Ahmadreza Jeddi, Marco Ciccone, and Babak Taati. LoopFormer: Elastic-depth looped transformers for latent reasoning via shortcut modulation. In International Conference on Learning Representations, 2026. URL https://openreview.net/forum?id=RzYXb5YWBs.arxiv.org/abs/2602.11451
  17. [17]Alexia Jolicoeur-Martineau. Less is more: Recursive reasoning with tiny networks. arXiv preprint arXiv:2510.04871, 2025. URL https://arxiv.org/abs/2510.04871.
  18. [18]Stefan Lee, Senthil Purushwalkam, Michael Cogswell, Viresh Ranjan, David Crandall, and Dhruv Batra. Stochastic multiple choice learning for training diverse deep ensembles. In Advances in Neural Information Processing Systems, 2016. URL https://arxiv.org/abs/1606.07839.
  19. [19]Shuzhen Li, Yifan Zhang, Jiacheng Guo, Quanquan Gu, and Mengdi Wang. DeepLoop: Depth scaling for looped transformers. arXiv preprint arXiv:2607.13491, 2026. URL https://arxiv.org/abs/2607.13491.
  20. [20]Hunter Lightman, Vineet Kosaraju, Yura Burda, Harri 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, 2024. URL https://openreview.net/forum?id=V8L0pN6EOi.arxiv.org/abs/2305.20050
  21. [21]Sajad Movahedi, Vera Milovanović, Shlomo Libo Feigin, Alexander Theus, Thomas Hofmann, Valentina Boeva, T. Konstantin Rusch, and Antonio Orvieto. Fixed-point reasoners: Stable and adaptive deep looped transformers. arXiv preprint arXiv:2606.18206, 2026. URL https://arxiv.org/abs/2606.18206.
  22. [22]Hayden Prairie, Zachary Novack, Taylor Berg-Kirkpatrick, and Daniel Y. Fu. Parcae: Scaling laws for stable looped language models. arXiv preprint arXiv:2604.12946, 2026. URL https://arxiv.org/abs/2604.12946.
  23. [23]Subham Sekhar Sahoo, Marianne Arriola, Yair Schiff, Aaron Gokaslan, Edgar Marroquin, Justin T. Chiu, Alexander Rush, and Volodymyr Kuleshov. Simple and effective masked diffusion language models. In Advances in Neural Information Processing Systems, 2024. URL https://arxiv.org/abs/2406.07524.
  24. [24]Nikunj Saunshi, Nishanth Dikkala, Zhiyuan Li, Sanjiv Kumar, and Sashank J. Reddi. Reasoning with latent thoughts: On the power of looped transformers. In International Conference on Learning Representations, 2025. URL https://arxiv.org/abs/2502.17416.
  25. [25]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, 2025. URL https://openreview.net/forum?id=4FWAwZtd2n.arxiv.org/abs/2408.03314
  26. [26]Guan Wang, Jin Li, Yuhao Sun, Xing Chen, Changling Liu, Yue Wu, Meng Lu, Sen Song, and Yasin Abbasiyadkori. Hierarchical reasoning model. arXiv preprint arXiv:2506.21734, 2025. URL https://arxiv.org/abs/2506.21734.
  27. [27]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. In International Conference on Learning Representations, 2023. URL https://arxiv.org/abs/2203.11171.
  28. [28]Liu Yang, Kangwook Lee, Robert Nowak, and Dimitris Papailiopoulos. Looped transformers are better at learning learning algorithms. In International Conference on Learning Representations, 2024. URL https://arxiv.org/abs/2311.12424.
  29. [29]Xiao-Wen Yang, Ziyu Han, Xi-Hua Zhang, Wen-Da Wei, Jie-Jing Shao, Lan-Zhe Guo, and Yu-Feng Li. Stabilizing recurrent dynamics for test-time scalable latent reasoning in looped language models. In International Conference on Machine Learning, 2026. URL https://openreview.net/forum?id=tbdSfBM1bq.arxiv.org/abs/2605.26733
  30. [30]Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. In Advances in Neural Information Processing Systems, 2023. URL https://arxiv.org/abs/2305.10601.
  31. [31]Tianyu Zheng, Ge Zhang, Tianhao Shen, Xueling Liu, Bill Yuchen Lin, Jie Fu, Wenhu Chen, and Xiang Yue. OpenCodeInterpreter: Integrating code generation with execution and refinement. In Findings of the Association for Computational Linguistics: ACL 2024, pp. 12834–12859, 2024. doi: 10.18653/v1/2024.findings-acl.762. URL https://aclanthology.org/2024.findings-acl.762/.DOI
  32. [32]Rui-Jie Zhu, Zixuan Wang, Kai Hua, Tianyu Zhang, Ziniu Li, Haoran Que, Boyi Wei, Zixin Wen, Fan Yin, He Xing, Lu Li, Jiajun Shi, Kaijing Ma, Shanda Li, Taylor Kergan, Andrew Smith, Xingwei Qu, Mude Hui, Bohong Wu, Qiyang Min, Hongzhi Huang, Xun Zhou, Wei Ye, Jiaheng Liu, Jian Yang, Yunfeng Shi, Chenghua Lin, Enduo Zhao, Tianle Cai, Ge Zhang, Wenhao Huang, Yoshua Bengio, and Jason Eshraghian. Scaling latent reasoning via looped language models. arXiv preprint arXiv:2510.25741, 2026. URL https://arxiv.org/abs/2510.25741.

Paper details

vlnc:W_qhjtekyv
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 1

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

AI tools

View statement
Looking for related papers…
Contents