Research map / Large language models / Reasoning and chain of thought
Wider or Deeper? Scaling LLM Inference-Time Compute with Adaptive Branching Tree Search
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes AB-MCTS, an inference-time tree search that uses Thompson sampling over Bayesian posterior predictives to adaptively choose between generating new candidates (go wider) and refining existing ones (go deeper), outperforming repeated sampling and standard MCTS on coding and ML engineering tasks.
Problem
Repeated sampling lacks exploitation of external feedback, while existing multi-turn tree search methods like standard MCTS use a fixed branching factor that limits inference-time scaling with LLMs that can generate unboundedly many diverse outputs.
Approach
Introduces GEN and CONT nodes so that the branching factor is unbounded and the choice to widen or deepen at each node is made by Thompson sampling over Bayesian posterior predictive score distributions, with two variants: a node-specific mixed model (AB-MCTS-M) and a node-aggregation conjugate model (AB-MCTS-A).
Key results
- On LiveCodeBench with GPT-4o, AB-MCTS-A (Gaussian) reaches 39.1 Pass@1 vs 37.8 for repeated sampling and 36.7 for standard MCTS, achieving the top rank.
- AB-MCTS-M achieves the best average rank (2.3) across LiveCodeBench, CodeContest, and ARC-AGI, versus 3.5 for repeated sampling and 4.2 for standard MCTS.
- On MLE-Bench, AB-MCTS-M obtains the best average rank (1.3) across three Kaggle competitions, winning Spooky Author and Random Acts of Pizza.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use adaptive branching search (AB-MCTS variants) instead of repeated sampling | GPT-4o · LiveCodeBench | Pass@1: 37.8 { $\pm$ 0.5} -> 38.9 { $\pm$ 1.9}; 37.8 { $\pm$ 0.5} -> 39.1 { $\pm$ 1.9}; 37.8 { $\pm$ 0.5} -> 38.7 { $\pm$ 1.2} | Helped |
| Use adaptive branching search (AB-MCTS variants) instead of standard MCTS | DeepSeek-V3 · CodeContest | Pass@1: 43.8 { $\pm$ 0.9} -> 44.6 { $\pm$ 0.9}; 43.8 { $\pm$ 0.9} -> 44.8 { $\pm$ 0.6} | Helped |
| Use adaptive branching search instead of repeated sampling | GPT-4o · ARC-AGI | Pass@2: 15.0 { $\pm$ 1.0} -> 12.3 { $\pm$ 1.2}; 15.0 { $\pm$ 1.0} -> 13.0 { $\pm$ 3.6}; 15.0 { $\pm$ 1.0} -> 14.0 { $\pm$ 2.1} | Hurt |
| Use adaptive branching search instead of repeated sampling | DeepSeek-V3 · ARC-AGI | Pass@2: 18.6 { $\pm$ 1.0} -> 16.0 { $\pm$ 1.0}; 18.6 { $\pm$ 1.0} -> 18.3 { $\pm$ 0.6}; 18.6 { $\pm$ 1.0} -> 16.6 { $\pm$ 0.6} | Mixed |
| Use adaptive branching search instead of sequential refinement | GPT-4o · Nomad2018 | score: 0.059 -> 0.060 | Mixed |
| Use adaptive branching search instead of sequential refinement | GPT-4o · Spooky Author Identification | score: 0.46 -> 0.38 | Hurt |
| Use adaptive branching search instead of repeated sampling | GPT-4o · Random Acts of Pizza | score: 0.72 -> 0.72 | No clear effect |
| Vary the prior hyperparameters (ablation) | AB-MCTS-M · LiveCodeBench | Pass@1: 38.4 ± 1.6; 37.3 ± 0.4; 36.8 ± 1.5; 37.5 ± 1.5; 37.7 ± 1.3 | No clear effect |
| Vary the prior hyperparameters (ablation) | AB-MCTS-A (Gaussian) · LiveCodeBench | Pass@1: 38.0 ± 1.6; 37.0 ± 1.4; 37.3 ± 1.5; 37.7 ± 0.7 | No clear effect |
| Vary the prior hyperparameters (ablation) | AB-MCTS-A (Beta) · LiveCodeBench | Pass@1: 37.3 ± 1.5; 37.0 ± 1.5; 37.5 ± 1.3; 37.5 ± 1.3; 37.7 ± 1.2 | No clear effect |
Surprising findings
- Repeated sampling is the strongest baseline on ARC-AGI, and sequential refinement performs worst there, indicating broad exploration matters most for that task.
Limitations
- Assumes a reliable score evaluator is available during search, which can be hard to build for some tasks.
- Cost is measured only in API calls, not in real-world cost factors.
Experimental setup
Datasets: LiveCodeBench CodeContest ARC-AGI MLE-Bench
Benchmarks: LiveCodeBench CodeContest ARC-AGI MLE-Bench
Metrics: Pass@1 Pass@2 success rate average rank
Baselines: Repeated Sampling (best-of-n) Sequential Refinement Standard MCTS (LATS configuration)
Builds on: Monte Carlo Tree Search LATS progressive widening repeated sampling
Closest papers by meaning
- Inference Scaling Laws: An Empirical Analysis of Compute-Optimal Inference for LLM Problem-Solving (ICLR 2025 · similarity 0.91)
- Aligning Tree-Search Policies with Fixed Token Budgets in Test-Time Scaling of LLMs (ICML 2026 · similarity 0.90)
- Entropy-informed Decoding: Adaptive Information-Driven Branching (ICML 2026 · similarity 0.89)
- Rollout Roulette: A Probabilistic Inference Approach to Inference-Time Scaling of LLMs using Particle-Based Monte Carlo Methods (NeurIPS 2025 · similarity 0.89)
- Efficient Test-Time Scaling via Hierarchical Search and Self-Verification for Discrete Diffusion Language Models (ICML 2026 · similarity 0.89)
- DISC: Dynamic Decomposition Improves LLM Inference Scaling (NeurIPS 2025 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.