Budget-Aware Anytime Reasoning with LLM-Synthesized Preference Data

AI summary

Overview

Research area: Natural Language Processing / LLM reasoning efficiency, specifically budget-aware "anytime" reasoning and inference-time self-improvement.

Technical level: Intermediate. The core ideas are intuitive (trade solution quality against token budget) but the paper introduces a formal metric with a trapezoidal area-under-curve formula and reports detailed multi-model benchmark tables.

Scope: The paper proposes a framework for measuring how LLM solution quality improves as reasoning tokens are spent, introduces the Anytime Index metric, and proposes Preference Data Prompting — an inference-time method that uses the model's own contrastive preference pairs to produce better partial solutions — evaluated on NaturalPlan (Trip), AIME 2024, and GPQA across seven models.

What This Paper Is About

Most LLM reasoning work assumes unlimited computation and only scores the final answer, so it cannot say whether a model reaches a good answer early or only at the very end. The authors argue that many real tasks (such as trip planning) require the best possible output within a fixed reasoning budget, where a useful partial solution beats an expensive exhaustive one. The paper's goal is to define and measure this "anytime" behavior, and then to improve it without any human supervision or fine-tuning.

Key Contributions

1. An evaluation framework for anytime reasoning in LLMs, built on sampling multiple Chain-of-Thought traces, truncating each at a series of token-budget checkpoints, re-prompting the model for a final answer from the truncated prefix, and scoring the result with task-specific metrics (Constraint Satisfaction Rate for planning, accuracy for math and scientific QA).

2. The Anytime Index, a metric that quantifies a model's quality-per-token tradeoff across multiple reasoning budgets, normalized to the range [0, 1], capturing reasoning efficiency over time rather than only final accuracy.

3. Preference Data Prompting (PDP), a scalable inference-time self-improvement method that uses LLM-generated preference data — pairs of preferred and rejected reasoning traces truncated to the same token budget — as in-context examples, requiring no human supervision and no fine-tuning.

4. Empirical evidence of improved intermediate and final solution quality across structured planning (NaturalPlan), math (AIME 2024), and scientific QA (GPQA-Diamond), spanning Grok-3, Grok-3-mini, GPT-oss-120B, GPT-oss-20B, GPT-4.1, GPT-4o, and Llama-3.3-70B.

Main Findings

• PDP is the best overall method for the strongest reasoners: When results are averaged across the three datasets ("Overall" columns), PDP achieves the highest Anytime Index for all reasoning-specialized models as well as Llama-3.3-70B. Gains are driven by higher-quality intermediate traces at early and mid-range budgets, and in most cases carry through to better final scores at the maximum budget.

• Contrastive supervision matters more than positive examples alone: PDP(+) — the ablation that uses only high-quality traces and omits rejected ones — consistently improves over CoT, but the full PDP, which includes both preferred and rejected traces, yields stronger anytime behavior. Across the 21 model–dataset settings, PDP achieves a higher Anytime Index than PDP(+) in the majority of cases, with the gap most pronounced for reasoning-specialized models.

• PDP beats a learning-from-mistakes baseline: Compared with LEAP, PDP achieves a higher overall Anytime Index across six out of seven models and superior average CSR/accuracy in all cases. For models with strong reasoning capabilities, PDP improves overall final CSR/accuracy by 17.6%, average CSR/accuracy by 11.4%, and the Anytime Index by 7.9.

• General-purpose models benefit less consistently: For GPT-4.1 and GPT-4o, PDP consistently improves over CoT but does not always achieve the best Anytime Index among prompting strategies. The authors attribute this to PDP working best when a model can reliably distinguish higher- from lower-quality reasoning traces — a capacity stronger in reasoning-specialized models.

• Illustrative per-model results from Table 1: Grok-3 on NaturalPlan (Trip) rises from a Base final CSR of 74.7 to 90.2 with PDP (Anytime Index 68.4 to 78.1). Grok-3-mini on AIME reaches 100.0 final accuracy with PDP versus 80.6 for Base, with Anytime Index 87.1 versus 80.9. GPT-oss-120B on GPQA goes from 44.3 Base final accuracy to 69.4 with PDP. GPT-oss-20B on GPQA goes from 28.4 to 60.7. GPT-4o on GPQA goes from 52.8 to 65.3. Llama-3.3-70B on NaturalPlan goes from 71.5 to 82.0.

• Anytime Index can distinguish equally accurate but differently paced methods: The appendix gives a concrete scenario in which baseline CoT and PDP both reach a final CSR of approximately 0.95 at 800 tokens on Grok-3-mini, but PDP reaches 0.9 CSR already at 350 tokens while baseline CoT stays near 0.83–0.85 CSR until a jump at 500–600 tokens. The Anytime Index favors PDP, marking it as the better anytime reasoner under variable budgets.

Methodology in Plain English

Evaluation pipeline. For each task input, the authors sample N full Chain-of-Thought traces per model, up to a global maximum of 4,096 tokens for NaturalPlan and 16,384 tokens for AIME and GPQA. They define token-budget checkpoints: for NaturalPlan, budgets of 100, 200, ..., 800 tokens; for AIME and GPQA, budgets of 200, 300, ..., 1600 tokens. At each checkpoint, a trace is truncated to keep only the first b_i reasoning tokens, and the model is re-prompted to produce a final answer from that partial prefix. This simulates real interruptions from latency limits or token budgets. Quality at each checkpoint (Q_i) is the Constraint Satisfaction Rate for planning tasks (the fraction of satisfied constraints, checked automatically by a rule-based checker) and accuracy for math and scientific QA, averaged over the sampled traces.

The Anytime Index. The metric takes the best score achieved up to each budget, builds a quality-versus-budget curve, computes the area under it using the trapezoidal rule, and divides by the budget range times the global best achievable score, yielding a value in [0, 1]. The interpretation is: if you do not know in advance how many tokens you will be allowed, how good is this model on average over the whole budget range? The paper notes the metric is inspired by area-under-curve metrics used in optimization, analogous to how AUC-ROC summarizes a classifier across thresholds.

Preference Data Prompting. The method builds on the evaluation setup. For NaturalPlan, the authors sample N = 64 CoT traces per input; for AIME and GPQA, they sample 5 and 30 validation examples respectively and generate N = 32 CoT traces per example. Each trace is truncated at each budget and scored. At each budget, traces are ranked by quality, and preference pairs are formed with a preferred (higher-scoring) and rejected (lower-scoring) trace truncated to the same length — fixing the budget forces the contrast to reflect differences in reasoning quality, not reasoning length. For each dataset, the pair with the largest quality gap at each budget is selected as one contrastive in-context example (eight for NaturalPlan, and similarly for AIME and GPQA). The intermediate solutions themselves (the trip plan or math answer) are omitted from the prompt, so the model learns from contrastive reasoning patterns rather than imitating surface outputs. Preference pairs are generated once offline and reused across all inference runs, so additional inference cost is minimal.

Baselines compared: Base (standard Chain-of-Thought prompting), LEAP (in-context principle learning from mistakes), PDP(+) (positive traces only), and PDP (full contrastive preference pairs).

Why This Matters

Impact on research. The paper shifts evaluation away from a single end-of-reasoning score toward the whole quality-versus-token trajectory, offering a principled way to compare "fast-thinking" and "slow-thinking" models. It also shows a self-improvement signal can be synthesized by the model itself at inference time, without human preference labels or weight updates, and connects modern LLM reasoning to the classical anytime-algorithm literature.

Real-world applications (as framed by the paper):

• Trip planning and structured itinerary generation, where constraints (number of cities, trip length, duration per city) must be respected and a feasible partial plan has immediate value.
• Mathematical problem solving under time or token limits, where partial progress toward a solution is still assessable.
• Expert-level scientific question answering, which demands sustained, knowledge-intensive multi-step reasoning.
• Any deployment with strict latency, compute, or budget limits where reasoning may be interrupted early or stopped dynamically.

Industry relevance. The evaluated models come from xAI, OpenAI, Meta, and the work was done in collaboration with Oracle AI, with the first author's contribution completed during an internship at Oracle. Because PDP is inference-time only, uses offline-generated prompt data, and requires no fine-tuning or human annotation, it is directly applicable to production systems that must serve answers within fixed cost or latency envelopes.

Future Directions

• Internalize anytime behavior during training: The authors explicitly plan to investigate preference-driven fine-tuning, suggesting Direct Preference Optimization (DPO) to move beyond inference-time prompting and "close the self-improvement cycle."
• Broaden the task set: Experiments focus primarily on trip planning with NaturalPlan; the authors call for validation on a wider set of tasks, including open-ended domains such as code generation.
• Benchmark against more reasoning strategies: The paper compares mainly Chain-of-Thought against its own method rather than exhaustively against Tree-of-Thoughts, Self-Consistency, and similar approaches.
• Exploit the Anytime Index's sensitivity: The metric is designed to separate methods with similar final quality but very different early- and mid-budget behavior, and the authors note that future work should identify specific method pairs where this gap is largest.

Target Audience

Researchers and practitioners in LLM reasoning, test-time compute scaling, and inference efficiency; engineers deploying LLMs under latency, token, or cost budgets; and anyone working on self-improvement, preference-based prompting, or benchmark design for budget-aware evaluation. Readers interested in planning and constraint-satisfaction applications will find the NaturalPlan analysis especially relevant, while those focused on mathematical and scientific reasoning will find the AIME 2024 and GPQA results useful.

Authors’ abstract

We study the reasoning behavior of large language models (LLMs) under limited computation budgets. In such settings, producing useful partial solutions quickly is often more practical than exhaustive reasoning, which incurs high inference costs. Many real-world tasks, such as trip planning, require models to deliver the best possible output within a fixed reasoning budget. We introduce an anytime reasoning framework and the Anytime Index, a metric that quantifies how effectively solution quality improves as reasoning tokens increase. To further enhance efficiency, we propose an inference-time self-improvement method using LLM-synthesized preference data, where models learn from their own reasoning comparisons to produce better intermediate solutions. Experiments on NaturalPlan (Trip), AIME, and GPQA datasets show consistent gains across Grok-3, GPT-oss, GPT-4.1/4o, and LLaMA models, improving both reasoning quality and efficiency under budget constraints.