PaperlayerView exact revision on arXiv

Source-linked AI summary

$\phi$-Decoding: Adaptive Foresight Sampling for Balanced Inference-Time Exploration and Exploitation

Fangzhi Xu, Hang Yan, Chang Ma, Haiteng Zhao, Jun Liu, Qika Lin, Zhiyong Wu

arXiv:2503.13288v1cs.LGcs.AIcs.CL

TL;DR

Auto-regressive generation is short-sighted, while search-based decoding can incur vast search and excessive exploration. ϕ-Decoding estimates step value from simulated futures and prunes computation adaptively; across seven benchmarks, it reports state-of-the-art performance and efficiency.

  • Problem

    Auto-regressive generation's short-sightedness limits global-optimum reasoning, while search-based methods face vast search spaces and excessive exploration with insufficient exploitation.

    Source: §1 · p. 1

  • Method

    ϕ-Decoding estimates step values from simulated future paths using advantage-based and clustered-path distributions, then samples their joint distribution and applies pruning strategies.

    Source: §1 · p. 2

  • Results

    Across seven diverse LLM benchmarks, ϕ-Decoding demonstrates state-of-the-art performance and efficiency; versus the MCTS-style method, its average improvement is 3.25-5.70% at one-third of the cost.

    Source: §3.3 · p. 5, §6 · p. 9

  • Takeaways & Limitations

    ϕ-Decoding generalizes across 3B, 7B, 8B, and 70B LLMs and scales across various computational budgets.

    Source: §6 · p. 9

    Uncertainty-based step estimation can trap LLMs at an incorrect step with exceptionally high confidence.

    Source: §2.2 · p. 3

Abstract

from arXiv · show

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 $\phi$-Decoding. To provide a precise and expressive estimation of step value, $\phi$-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 $\phi$-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.

1 Introduction

Auto-regressive reasoning is short-sighted, while search-based methods incur extensive search and can over-explore. ϕ-Decoding uses foresight-based step values and adaptive pruning; experiments report improved benchmark performance and efficiency.

  • Auto-regressive generation predicts each next step from preceding steps, limiting global-optimum search; search-based methods face vast spaces, excessive exploration, and insufficient exploitation.Source: §1 · pp. 1–2
  • ϕ-Decoding frames decoding as foresight sampling: simulated futures estimate current-step value through advantage-based and clustered-path distributions, whose joint sampling selects steps.Source: §1 · p. 2
  • In-width and in-depth pruning are proposed to allocate computation adaptively and address whether every step needs deliberation.Source: §1 · p. 2
  • Across diverse reasoning benchmarks, ϕ-Decoding improves LLaMA3.1-Instruct-8B average performance by >14% over auto-regressive CoT.Source: §1 · p. 2
  • Inference-time scaling lets ϕ-Decoding match the suboptimal baseline's performance with 6× efficiency.Source: §1 · p. 2

2 Methodology

ϕ-Decoding frames step selection as foresight sampling, combining future-path advantage and cluster alignment to estimate step value, then pruning candidates across width and depth to allocate computation.

2.1 Preliminary

  • Foresight sampling conditions current-step selection on preceding steps and estimated future outcomes, addressing autoregressive generation’s short-sightedness through future simulation.The paper frames its objective as estimating step value from preceding steps and simulated future steps.Source: §2.1 · pp. 2–3

2.2 Step Value Estimation

  • Advantage scores absolute value from adjacent-step changes, while cluster-size alignment captures relative consistency; their rewards form a joint sampling distribution.Foresight-path probability differences estimate advantage; cluster alignment reflects how consistently paths reach similar outcomes.Source: §2.2 · pp. 3–4

2.3 Dynamic Pruning Strategy

  • In-width pruning removes exceptionally low-confidence candidates before look-ahead, while in-depth pruning uses largest-cluster size to trigger early stopping.The in-width threshold can be adjusted from the mean confidence minus a multiple of its standard deviation.Source: §2.3 · p. 4

3 Experiments

Across reasoning benchmarks, ϕ-Decoding improves average performance over standard CoT and balances accuracy with computational cost. Experiments also assess the method across baselines, backbones, and inference-time budgets.

3.1 Evaluation Benchmarks and Metrics

  • Evaluation covered six reasoning benchmarks plus competition-level AIME, reporting Pass@1 accuracy and FLOPS to characterize the performance–efficiency trade-off.The six benchmarks are GSM8K, MATH-500, GPQA, ReClor, LogiQA, and ARC-Challenge.Source: §3.1 · pp. 4–5

3.2 Baselines and Backbone LLMs

  • Five baselines were compared on six tasks using LLaMA3.1-8B-Instruct and Mistral-v0.3-7B-Instruct, with additional backbones used to assess generalization and scalability.The additional models include Qwen2.5-3B, LLaMA3.1-70B, and R1-Distill-LLaMA-8B for competition-level tasks.Source: §3.2 · p. 5

3.3 Main Results

  • Against MCTS-style methods, ϕ-Decoding improved average performance by 3.25–5.70% with one-third of the computational cost.The paper also reports lower computational cost than the four strong baselines in general.Source: §3.3 · p. 5
  • 14.62% and 6.92% average improvements over standard CoT were observed on LLaMA3.1-Instruct and Mistral-v0.3-Instruct, respectively, without extra training.Table 1 presents the main results across six reasoning benchmarks; its caption identifies the average and FLOPS columns.Source: §3.3 · p. 5, Table 1 · p. 6

3.4 On the Inference-Time Scaling

  • Across every plotted computational budget, ϕ-Decoding leads; near 57% average performance, it is over 6× more efficient than even suboptimal methods.Figure 3 plots inference-time computational cost against average performance on six benchmarks.Source: §3.4 · pp. 5–6, Figure 3 · p. 5

4 Analysis

Ablations associate foresight sampling and clustering with performance gains, while dynamic pruning reduces compute. Further analyses examine generalization across model sizes, step-value estimation, and where inference-time computation matters.

4.1 Ablation Studies

  • Ablations report 2.98%-6.09% gains from foresight at extra inference cost, 0.95%-1.97% average gains from clustering, and efficiency plus performance gains from dynamic pruning.Foresight simulates future steps; clustering calibrates the sampling distribution, and dynamic pruning reduces computational costs.Source: §4.1 · p. 6

4.2 Generalization and Scalability

  • ϕ-Decoding improves LLaMA3.1-70B-Instruct across four benchmarks and raises Qwen2.5-3B performance by 3.80% on average across six reasoning benchmarks.The AIME 2024 analysis also reports gains with LLaMA3.1-8B-Instruct and R1-Distill-LLaMA-8B, including a well-trained reasoning model.Source: §4.2 · pp. 6–7, Table 3 · p. 7, Table 4 · p. 7

4.3 Accuracy of Step Value Estimation

  • More accurate step-value estimation aligns with better task performance, and ϕ-Decoding achieves the best step-value estimate and final accuracy among four approaches.Figure 4 shows step-value accuracy in light blue and averaged task performance in dark blue.Source: Figure 4 · p. 7, §4.3 · p. 7

4.4 Analysis on Step-wise Overthinking

  • Early steps are costlier and more critical; breadth pruning reduces about 20% of costs there, while depth pruning later uses early stopping to alleviate overthinking.Figure 5 shows independent benchmarks, with LLaMA results in the first row and Mistral results in the second.Source: §4.4 · p. 8, Figure 5 · p. 8

5 Related Works

Prior inference-time optimization methods include search-based and sampling-based approaches, as well as reward-model and self-reflection strategies. The paper positions ϕ-Decoding as a training-free, external-model-independent approach to adaptive scaling.

6 Conclusion

The paper introduces ϕ-Decoding to balance exploration and exploitation during inference. Across seven benchmarks, it reports strong performance and efficiency, with generalization across model sizes and computational budgets.

  • ϕ-Decoding balances exploration and exploitation during inference and demonstrates performance and efficiency across seven benchmarks, with generalization across 3B, 7B, 8B, and 70B models and varied computational budgets.Source: §6 · pp. 8–9

A Implementation Details

The implementation details define inference-time FLOPS as a measure of computational efficiency and report its average across benchmarks.

  • Inference-time FLOPS measures computational efficiency, and the reported FLOPS values are averaged across benchmarks.Source: §A.1 · p. 11

A.2 Inference Setup

The inference setup specifies ϕ-Decoding’s configuration and overall pipeline. Because of the high cost, the authors searched hyperparameters only within a small range.

A.2 Inference Setup

  • The setup defines M as step beam size, N as rollouts per beam, Tmin and Tmax as foresight-step bounds, K as cluster count, and δ as the early-stopping threshold.The authors searched these hyperparameters within a very small range because of the cost, leaving optimal configuration search for future work.Source: Table 5 · p. 11, §A.2 · p. 11
  • The paper provides a pseudocode algorithm and Figure 6 as a high-level overview of ϕ-Decoding.Source: B Algorithm of ϕ-Decoding · p. 11, Figure 6 · p. 11

C Generalization to Smaller LLMs

On Qwen2.5-3B-Instruct, ϕ-Decoding improves average performance over the auto-regressive chain-of-thought baseline across six reasoning benchmarks.

C Generalization to Smaller LLMs

D Accuracy of Step Value Estimation

The analysis assesses whether estimated step values track candidate-step outcomes. It compares value estimates with foresight-derived outcome accuracy and averages the match across timestamps.

D Accuracy of Step Value Estimation

  • The algorithm takes a query, LLM, beam and rollout counts, foresight-step bounds, cluster count, and early-stopping threshold, and returns a step sequence.Source: D Accuracy of Step Value Estimation · p. 12
  • In-width pruning filters candidates using their step-confidence mean and variance before foresight paths and scores are derived for the remaining candidates.Source: D Accuracy of Step Value Estimation · p. 12
  • The procedure derives advantage from adjacent-step foresight-score differences, combines advantage and alignment in R, and uses early stopping before completing candidates at the last foresight step.It then samples one candidate based on R.Source: D Accuracy of Step Value Estimation · p. 12
  • Step-value estimation accuracy is measured by matching the estimated-value distribution P1 to the foresight-derived outcome-accuracy distribution P2 at each timestamp.The two distributions have equal size.Source: D Accuracy of Step Value Estimation · p. 13
  • For ϕ-Decoding and Predictive Decoding, P1 uses model-estimated step values; for auto-regressive and ToT methods, selected steps receive binary reward 1 and other candidates 0.Source: D Accuracy of Step Value Estimation · p. 13
  • The final accuracy score averages the distribution-matching results across timestamps.Source: D Accuracy of Step Value Estimation · p. 13

E In-depth Analysis of Cluster Strategies

The cluster analysis compares TF-IDF with sentence-embedding alternatives and examines cluster-count choices. Embedding-based clustering remains competitive, while the authors identify K=2 or 3 as good choices under the stated setup.

E.1 Variants of Cluster

  • The main experiments use TF-IDF clustering from the syntax perspective, while sentence-BERT can instead provide sentence embeddings for clustering.Source: §E.1 · p. 13
  • Sentence-embedding clustering achieves competitive but slightly lower average performance than TF-IDF, and larger embedding models can improve average performance.The compared SBERT models use multi-qa-mpnet-base-dot-v1 (109M) and all-MiniLM-L6-v2 (22.7M).Source: §E.1 · p. 13

E.2 Hyperparameters of Cluster

  • K=2 or 3 are identified as good cluster-count choices when M=4 and N=4, giving at most 16 foresight paths for clustering.The authors note that increasing K may bring much uncertainty.Source: §E.2 · p. 13
Loading 2503.13288v1…