Summary (Overview)

• Novel scaling axis: The paper introduces Input-Conditioned Search (ICS), a method for test-time scaling of frozen recursive reasoners by searching over alternative input conditions to induce different update maps, rather than simply increasing depth or width.
• Two key operations: ICS is instantiated via (1) hypothesis injection — inserting tentative partial predictions into the input, and (2) validity-preserving restatements — expressing the task in equivalent representations via invertible transformations.
• State-of-the-art results: Across six reasoning tasks (Sudoku-Extreme, Maze-Hard, Light-Up, Nurikabe, Tapa, Heyawake), ICS achieves the highest mean accuracy with and without a task certificate, using up to 10–195× fewer model FLOPs than baselines.
• Theoretical contribution: The paper provides theoretical analysis and computer-assisted proofs showing ICS can locally eliminate incorrect attracting fixed points through fold (saddle-node) bifurcations induced by input conditioning.
• Efficiency without training: ICS requires no additional model training, achieving 99.7% accuracy on Sudoku-Extreme (model-based selection) with ~92% error reduction relative to the strongest baseline at comparable compute.

---

Introduction and Theoretical Foundation

Background and Motivation

Recursive reasoners solve problems by repeatedly applying a learned update rule to a latent state. While they can scale test-time computation via:

• Depth scaling: iterating the same update map for more steps
• Width scaling: generating multiple trajectories via latent perturbations

Both retain the same input-conditioned update map — meaning trajectories may converge to incorrect attractors that persist under both continued iteration and random perturbations.

The central research question: How can a frozen recursive reasoner use additional test-time computation to overcome persistent failures and discover correct solutions efficiently?

Formal Framework

A recursive reasoner $M_\theta$ receives input $x \in \mathcal{V}^{L_x}$ and iterates a learned update:

$$z_t = F_\theta(z_{t-1}; x), \qquad \hat{y}_t = g_\theta(z_t; x), \qquad q_t = Q_\theta(z_t), \qquad t = 1, 2, \ldots \tag{1}$$

where:

• $z \in \mathcal{Z} = \mathbb{R}^d$ is the latent state
• $g_\theta$ decodes the answer $\hat{y}$
• $Q_\theta$ produces a halting score
• $F_x := F_\theta(\cdot; x)$ is the fixed latent update map for a given input $x$

Key insight: Since each recursive update depends on both learned parameters and the input, varying the input condition provides a way to induce alternative update maps while keeping parameters frozen.

Answer Selection Regimes

The paper distinguishes two evaluation protocols:

• Certificate-based selection: $\hat{y}_{\text{cert}} = c_{\text{cert}}(\mathcal{C}(x); x, V)$ — uses a task validity checker $V$ during selection
• Model-based selection: $\hat{y}_{\text{model}} = c_{\text{model}}(\mathcal{P}(x); x)$ — relies only on model-derived signals (halting scores, prediction agreement)

---

Methodology

Input-Conditioned Search (ICS)

ICS runs the frozen reasoner from a fresh initialization under conditioned inputs:

$$z_0^{(\tilde{x})} = z_0, \qquad z_t^{\tilde{x}} = F_{\tilde{x}}\left(z_{t-1}^{(\tilde{x})}\right), \quad t = 1, \ldots, T_{\tilde{x}} \tag{2}$$

Operation 1: Hypothesis Injection

A hypothesis specifies tentative assignments $H = \{(i, \nu_i): i \in I_H\}$ at mutable positions. The conditioned input is:

$$(x_H)_i = \begin{cases} v_j, & i \in I_H, \\ x_i, & i \notin I_H. \end{cases} \tag{3}$$

This preserves original givens while expressing tentative assignments (digits in Sudoku, path membership in Maze, etc.).

Operation 2: Validity-Preserving Restatements

An invertible transformation $\Phi$ maps the task to an equivalent representation:

$$V(\Phi(x), \Phi(y)) = V(x, y) \tag{4}$$

Predictions are mapped back via $\hat{y} = \Phi^{-1}(\hat{y}_{\Phi(x)})$.

Search Procedure

1. Initial rollout on original input $x$
2. Hypothesis-conditioned search: Expand nodes by adding assignments, prioritizing positions with smallest prediction margin:

$$m_i^{(H)} = \ell_{i,(1)}^{(H)} - \ell_{i,(2)}^{(H)} \tag{6}$$

where $\ell_{i,(1)}^{(H)}$ and $\ell_{i,(2)}^{(H)}$ are the largest and second-largest decoder logits.

3. Candidate ranking prioritizes children by:

$$\left(\sum_{(i,\upsilon) \in H'} \mathbf{1}[\hat{y}_{H',i} \neq \upsilon], \quad \mathbf{1}[\hat{y}_{H'} \neq \Pi_x(\hat{y}_{H'})], \quad -q_{H'}\right) \tag{7}$$

4. Restatement exploration if hypothesis search fails
5. Beam search with width $W$ for expansion

---

Empirical Validation / Results

Main Results (Table 1)

†Attractor evaluated on a fixed 3,072-instance subset.

Component Ablation (Table 2)

Key Efficiency Findings

• Sudoku-Extreme: ICS achieves 99.70% at 1.14 TFLOPs/puzzle, reducing errors by ~92% vs. TRM + greedy depth at 1.20 TFLOPs
• Across tasks: 10–525× less test-time computation than scaling baselines
• LLM comparison: ICS achieves 91.7% mean accuracy vs. 78.3% for strongest LLM on PPBench golden set

Recovery Dynamics (Section 5)

• Cold-start perturbations recover substantially more instances than warm-start perturbations (which recover none)
• Recovery drops sharply after only two recursion steps for failed trajectories (Figure 5)
• Hypothesis injection increases the relative one-step update residual at incorrect fixed points from ~$2.4 \times 10^{-7}$ to 0.225, eliminating near-stationarity

---

Theoretical and Practical Implications

Theoretical Mechanism

The paper establishes that input conditioning can locally eliminate incorrect attracting fixed points through fold (saddle-node) bifurcations:

Continuous variation of the input embedding causes an incorrect attracting fixed point to collide with an unstable fixed point, and the pair disappears through a local fold (saddle-node) bifurcation.

Sufficient conditions are derived and verified with rigorous numerical certificates in separately trained 4×4 Sudoku reasoners. Numerical continuation in Maze-Hard and Sudoku-Extreme provides complementary evidence of folds in incorrect fixed-point branches.

Practical Implications

1. No retraining required: ICS works with frozen models, making it directly applicable to deployed recursive reasoners
2. Efficiency: Substantial accuracy gains at 1–2 orders of magnitude less compute than scaling baselines
3. Complementary to existing methods: ICS can be combined with depth/width scaling for further gains
4. Model-based selection works: Even without task certificates, ICS outperforms baselines with access to certificates

---

Conclusion

Main Takeaways

• Input conditioning is an effective scaling axis for recursive reasoners, enabling escape from incorrect attractors without retraining
• ICS combines hypothesis injection and validity-preserving restatements to explore alternative update maps efficiently
• Theoretical grounding: Input conditioning can provably eliminate incorrect attracting fixed points via bifurcations
• Practical efficiency: State-of-the-art accuracy across six reasoning tasks at substantially lower compute

Future Directions

1. Training-time shaping: Designing training objectives that make recursive dynamics more amenable to input-conditioned search
2. Broader search strategies: More sophisticated proposal mechanisms and search scheduling
3. Scaling to larger models: Applying ICS principles to larger recursive reasoners and language models
4. Learning input conditions: Learning to generate effective hypotheses/restatements rather than relying on decoder logits

The paper motivates further research on shaping recursive dynamics during training and at test time as a fundamental dimension of efficient test-time scaling.