# Input-Conditioned Search for Efficient Test-Time Scaling of Recursive Reasoners

> Input-Conditioned Search scales frozen recursive reasoners by injecting hypotheses and restatements, achieving state-of-the-art accuracy across six reasoning tasks with up to 195x fewer FLOPs and no retraining.

- **Source:** [arXiv](https://arxiv.org/abs/2610.18547)
- **Published:** 2026-10-17
- **Permalink:** https://picx.dev/p/Ddv21i
- **Whiteboard:** https://picx.dev/p/Ddv21i/image

## Summary

## 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)

| Protocol | Sudoku | Maze | Light-Up | Nurikabe | Tapa | Heyawake |
|---|---|---|---|---|---|---|
| **Certificate available** | | | | | | |
| Standard TRM | 86.0 | 91.6 | 99.7 | 83.8 | 72.8 | 86.4 |
| + depth scaling | 98.2 | 91.6 | 100.0 | 84.9 | 75.4 | 87.8 |
| PTRM | 98.3 | 92.4 | 100.0 | 86.1 | 76.4 | 88.7 |
| GRAM | 97.5 | 90.8 | 99.7 | 91.9 | 52.3 | 97.1 |
| EqR | 98.8 | 95.0 | 91.4 | 77.1 | 26.7 | 31.6 |
| Attractor | 94.8† | 80.7 | 100.0 | 89.0 | 82.2 | 94.2 |
| **ICS** | **99.94** | **100.0** | **100.0** | **95.9** | **95.9** | **99.1** |
| **No certificate** | | | | | | |
| Standard TRM | 86.0 | 91.6 | 99.7 | 83.8 | 72.8 | 86.4 |
| + depth scaling | 98.1 | 85.1 | 99.7 | 80.9 | 67.7 | 84.3 |
| PTRM | 98.3 | 91.8 | 100.0 | 84.9 | 74.9 | 88.7 |
| GRAM, LPRM | 97.2 | 84.7 | 99.1 | 86.1 | 43.1 | 93.6 |
| EqR | 98.8 | 87.4 | 80.2 | 57.7 | 17.4 | 18.8 |
| Attractor | 94.8† | 53.6 | 100.0 | 87.6 | 78.1 | 92.2 |
| **ICS** | **99.70** | **99.1** | **100.0** | **88.4** | **86.7** | **94.5** |

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

### Component Ablation (Table 2)

| Components | Certificate Selection | | Model Selection | |
|---|---|---|---|---|
| | Accuracy (%) | TFLOPs | Accuracy (%) | TFLOPs |
| A: TRM + depth scaling | 87.85 | 0.38 | 87.85 | 0.38 |
| AB: + hypotheses | 99.92 | 1.39 | 99.75 | 1.10 |
| AC: + restatements | 98.83 | 1.19 | 98.82 | 1.19 |
| **ABC: full ICS** | **99.94** | **1.39** | **99.81** | **1.12** |

### 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.

---

_Markdown view of https://picx.dev/p/Ddv21i, served by PicX — AI-generated visual whiteboard summaries of research papers._