# Iterative Deepening Sampling as Efficient Test-Time Scaling

arXiv: https://arxiv.org/abs/2502.05449 · HTML: https://mlsanity.com/paper/2502.05449/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning.
- Builds on 33 of its 39 references that are in the map.
- First posted on arXiv 8 Feb 2025.

## Placed in

- LLM reasoning / [Test-time compute and efficient thinking](https://mlsanity.com/lr/test-time-compute-and-efficient-thinking/)

## Builds on (most cited first, 30 of 33)

- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Reflexion: Language Agents with Verbal Reinforcement Learning](https://mlsanity.com/paper/2303.11366/) (2023)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [Self-Refine: Iterative Refinement with Self-Feedback](https://mlsanity.com/paper/2303.17651/) (2023)
- [Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters](https://mlsanity.com/paper/2408.03314/) (2024)
- [MMLU-Pro: A More Robust and Challenging Multi-Task Language Understanding Benchmark](https://mlsanity.com/paper/2406.01574/) (2024)
- [Large Language Models Cannot Self-Correct Reasoning Yet](https://mlsanity.com/paper/2310.01798/) (2023)
- [Teaching Large Language Models to Self-Debug](https://mlsanity.com/paper/2304.05128/) (2023)
- [Reasoning with Language Model is Planning with World Model](https://mlsanity.com/paper/2305.14992/) (2023)
- [CRITIC: Large Language Models Can Self-Correct with Tool-Interactive Critiquing](https://mlsanity.com/paper/2305.11738/) (2023)
- [Phi-4 Technical Report](https://mlsanity.com/paper/2412.08905/) (2024)
- [Language Agent Tree Search Unifies Reasoning Acting and Planning in Language Models](https://mlsanity.com/paper/2310.04406/) (2023)
- [The Lessons of Developing Process Reward Models in Mathematical Reasoning](https://mlsanity.com/paper/2501.07301/) (2025)
- [rStar-Math: Small LLMs Can Master Math Reasoning with Self-Evolved Deep Thinking](https://mlsanity.com/paper/2501.04519/) (2025)
- [Chain-of-Thought Reasoning Without Prompting](https://mlsanity.com/paper/2402.10200/) (2024)
- [Planning with Large Language Models for Code Generation](https://mlsanity.com/paper/2303.05510/) (2023)
- [AlphaMath Almost Zero: Process Supervision without Process](https://mlsanity.com/paper/2405.03553/) (2024)
- [Accessing GPT-4 level Mathematical Olympiad Solutions via Monte Carlo Tree Self-refine with LLaMa-3 8B](https://mlsanity.com/paper/2406.07394/) (2024)
- [Fast Best-of-N Decoding via Speculative Rejection](https://mlsanity.com/paper/2410.20290/) (2024)
- [O1 Replication Journey -- Part 2: Surpassing O1-preview through Simple Distillation, Big Progress or Bitter Lesson?](https://mlsanity.com/paper/2411.16489/) (2024)
- [LLaMA-Berry: Pairwise Optimization for O1-like Olympiad-Level Mathematical Reasoning](https://mlsanity.com/paper/2410.02884/) (2024)
- [Step-level Value Preference Optimization for Mathematical Reasoning](https://mlsanity.com/paper/2406.10858/) (2024)
- [Scaling of Search and Learning: A Roadmap to Reproduce o1 from Reinforcement Learning Perspective](https://mlsanity.com/paper/2412.14135/) (2024)
- [When is Tree Search Useful for LLM Planning? It Depends on the Discriminator](https://mlsanity.com/paper/2402.10890/) (2024)
- [Why Solving Multi-agent Path Finding with Large Language Model has not Succeeded Yet](https://mlsanity.com/paper/2401.03630/) (2024)

## Built on by (most cited first, 8 of 8)

- [Towards Reasoning Era: A Survey of Long Chain-of-Thought for Reasoning Large Language Models](https://mlsanity.com/paper/2503.09567/) (2025)
- [SoftCoT++: Test-Time Scaling with Soft Chain-of-Thought Reasoning](https://mlsanity.com/paper/2505.11484/) (2025)
- [Parallel-Probe: Towards Efficient Parallel Thinking via 2D Probing](https://mlsanity.com/paper/2602.03845/) (2026)
- [LSPO: Length-aware Dynamic Sampling for Policy Optimization in LLM Reasoning](https://mlsanity.com/paper/2510.01459/) (2025)
- [CyclicReflex: Improving Reasoning Models via Cyclical Reflection Token Scheduling](https://mlsanity.com/paper/2506.11077/) (2025)
- [Self-Improvement of Large Language Models: A Technical Overview and Future Outlook](https://mlsanity.com/paper/2603.25681/) (2026)
- [Adaptive Rectification Sampling for Test-Time Compute Scaling](https://mlsanity.com/paper/2504.01317/) (2025)
- [Small RL Controller, Large Language Model: RL-Guided Adaptive Sampling for Test-Time Scaling](https://mlsanity.com/paper/2606.03102/) (2026)

## Abstract (arXiv)

Recent reasoning models, such as OpenAI's O1 series, have demonstrated exceptional performance on complex reasoning tasks and revealed new test-time scaling laws. Inspired by this, many people have been studying how to train models to achieve effective self-evaluation and self-correction to further enable the scaling paradigm. However, less studied is how to efficiently scale test-time compute from a fixed model, and this remains a challenge. In this paper, we address this challenge by focusing on enhancing the quality of self-reflection data generation for complex problem-solving at test time, which can also subsequently improve the training of next-generation large language models (LLMs). Specifically, we explore how systematically triggering a model's self-correction mechanisms can improve performance on challenging reasoning tasks. To this end, we propose a novel iterative deepening sampling algorithm framework designed to enhance self-correction and generate higher-quality samples. Through extensive experiments on Math500 and AIME benchmarks, we demonstrate that our method achieves a higher success rate on difficult tasks and provide detailed ablation studies to analyze its effectiveness across diverse settings.