# φ-Decoding: Adaptive Foresight Sampling for Balanced Inference-Time Exploration and Exploitation

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

## Key facts

- Cited by 13 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 29 of its 36 references that are in the map.
- First posted on arXiv 17 Mar 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, 29 of 29)

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [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)
- [Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks](https://mlsanity.com/paper/1908.10084/) (2019)
- [Scaling Laws for Neural Language Models](https://mlsanity.com/paper/2001.08361/) (2020)
- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021)
- [Think you have Solved Question Answering? Try ARC, the AI2 Reasoning Challenge](https://mlsanity.com/paper/1803.05457/) (2018)
- [GPQA: A Graduate-Level Google-Proof Q&A Benchmark](https://mlsanity.com/paper/2311.12022/) (2023)
- [Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters](https://mlsanity.com/paper/2408.03314/) (2024)
- [Math-Shepherd: Verify and Reinforce LLMs Step-by-step without Human Annotations](https://mlsanity.com/paper/2312.08935/) (2023)
- [Reasoning with Language Model is Planning with World Model](https://mlsanity.com/paper/2305.14992/) (2023)
- [Do NOT Think That Much for 2+3=? On the Overthinking of o1-Like LLMs](https://mlsanity.com/paper/2412.21187/) (2024)
- [rStar-Math: Small LLMs Can Master Math Reasoning with Self-Evolved Deep Thinking](https://mlsanity.com/paper/2501.04519/) (2025)
- [Quiet-STaR: Language Models Can Teach Themselves to Think Before Speaking](https://mlsanity.com/paper/2403.09629/) (2024)
- [Inference Scaling Laws: An Empirical Analysis of Compute-Optimal Inference for Problem-Solving with Language Models](https://mlsanity.com/paper/2408.00724/) (2024)
- [ReClor: A Reading Comprehension Dataset Requiring Logical Reasoning](https://mlsanity.com/paper/2002.04326/) (2020)
- [Retrieve, Program, Repeat: Complex Knowledge Base Question Answering via Alternate Meta-learning](https://mlsanity.com/paper/2010.15875/) (2020)
- [Chain-of-Thought Reasoning Without Prompting](https://mlsanity.com/paper/2402.10200/) (2024)
- [Universal Self-Consistency for Large Language Model Generation](https://mlsanity.com/paper/2311.17311/) (2023)
- [Self-Evaluation Guided Beam Search for Reasoning](https://mlsanity.com/paper/2305.00633/) (2023)
- [Fast Best-of-N Decoding via Speculative Rejection](https://mlsanity.com/paper/2410.20290/) (2024)
- [Self-Alignment for Factuality: Mitigating Hallucinations in LLMs via Self-Evaluation](https://mlsanity.com/paper/2402.09267/) (2024)
- [AceMath: Advancing Frontier Math Reasoning with Post-Training and Reward Modeling](https://mlsanity.com/paper/2412.15084/) (2024)
- [Corex: Pushing the Boundaries of Complex Reasoning through Multi-Model Collaboration](https://mlsanity.com/paper/2310.00280/) (2023)
- [Vision-Language Models Can Self-Improve Reasoning via Reflection](https://mlsanity.com/paper/2411.00855/) (2024)
- [Adaptive Inference-Time Compute: LLMs Can Predict if They Can Do Better, Even Mid-Generation](https://mlsanity.com/paper/2410.02725/) (2024)
- [Non-myopic Generation of Language Models for Reasoning and Planning](https://mlsanity.com/paper/2410.17195/) (2024)
- [Empowering Large Language Model Agents through Action Learning](https://mlsanity.com/paper/2402.15809/) (2024)

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

- [Efficient Reasoning Models: A Survey](https://mlsanity.com/paper/2504.10903/) (2025)
- [A Survey of Token Compression for Efficient Multimodal Large Language Models](https://mlsanity.com/paper/2507.20198/) (2025)
- [Genius: A Generalizable and Purely Unsupervised Self-Training Framework For Advanced Reasoning](https://mlsanity.com/paper/2504.08672/) (2025)
- [MUR: Momentum Uncertainty guided Reasoning for Large Language Models](https://mlsanity.com/paper/2507.14958/) (2025)
- [CoFFT: Chain of Foresight-Focus Thought for Visual Language Models](https://mlsanity.com/paper/2509.22010/) (2025)
- [OdysseyArena: Benchmarking Large Language Models For Long-Horizon, Active and Inductive Interactions](https://mlsanity.com/paper/2602.05843/) (2026)
- [The Art of Efficient Reasoning: Data, Reward, and Optimization](https://mlsanity.com/paper/2602.20945/) (2026)
- [Token-Guard: Towards Token-Level Hallucination Control via Self-Checking Decoding](https://mlsanity.com/paper/2601.21969/) (2026)
- [Decoding in Geometry: Alleviating Embedding-Space Crowding for Complex Reasoning](https://mlsanity.com/paper/2601.22536/) (2026)
- [Efficient Test-Time Inference via Deterministic Exploration of Truncated Decoding Trees](https://mlsanity.com/paper/2604.20500/) (2026)
- [Dual-Dimensional Consistency: Balancing Budget and Quality in Adaptive Inference-Time Scaling](https://mlsanity.com/paper/2605.15100/) (2026)
- [DeepLook: Deeper Thinking with Lookahead](https://mlsanity.com/paper/2607.22602/) (2026)
- [OmniConfess: Eliciting Token Confessions to Mitigate Omni-Modal Hallucination](https://mlsanity.com/paper/2610.02999/) (2026)

## Abstract (arXiv)

Inference-time optimization scales computation to derive deliberate reasoning steps for effective performance. While previous search-based strategies address the short-sightedness of auto-regressive generation, the vast search space leads to excessive exploration and insufficient exploitation. To strike an efficient balance to derive the optimal step, we frame the decoding strategy as foresight sampling, leveraging simulated future steps to obtain globally optimal step estimation. Built on it, we propose a novel decoding strategy, named φ-Decoding. To provide a precise and expressive estimation of step value, φ-Decoding approximates two distributions via foresight and clustering. Sampling from the joint distribution, the optimal steps can be selected for exploitation. To support adaptive computation allocation, we propose in-width and in-depth pruning strategies, featuring a light-weight solution to achieve inference efficiency. Extensive experiments across seven benchmarks show φ-Decoding outperforms strong baselines in both performance and efficiency. Additional analysis demonstrates its generalization across various LLMs and scalability across a wide range of computing budgets. The code will be released at https://github.com/xufangzhi/phi-Decoding, and the open-source PyPI package is coming soon.