Lune

ACL Findings2026

Budget-Aware Anytime Reasoning with LLM-Synthesized Preference Data

Xuanming Zhang, Shwan Ashrafi, Aziza Mirsaidova, Amir Rezaeian, Miguel Ballesteros, Lydia B. Chilton, Zhou Yu, Dan Roth

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 selfimprovement method using LLM-synthesized preference data, where models learn from their own reasoning comparisons to produce better intermediate solutions. Experiments on Natu-ralPlan (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.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Tree of Thoughts: Deliberate Problem Solving with Large Language Models cites Self-Refine: Iterative Refinement with Self-Feedback
  • Tree of Thoughts: Deliberate Problem Solving with Large Language Models cites Chain-of-Thought Prompting Elicits Reasoning in Large Language Models
  • Self-Refine: Iterative Refinement with Self-Feedback cites Chain-of-Thought Prompting Elicits Reasoning in Large Language Models
  • Dynamic Early Exit in Reasoning Models cites Chain-of-Thought Prompting Elicits Reasoning in Large Language Models
Builds onCited byLeft to right by year; the more cited, the higher.

Builds on10

  1. Chain-of-Thought Prompting Elicits Reasoning in Large Language ModelsJason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma et al.NeurIPS 2022 · 22,562 citations
  2. Tree of Thoughts: Deliberate Problem Solving with Large Language ModelsShunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran et al.NeurIPS 2023 · 5,068 citations
  3. Self-Refine: Iterative Refinement with Self-FeedbackAman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan et al.NeurIPS 2023 · 4,972 citations
  4. Iterative Reasoning Preference OptimizationRichard Yuanzhe Pang, Weizhe Yuan, He He, Kyunghyun Cho et al.NeurIPS 2024 · 287 citations
  5. Dynamic Early Exit in Reasoning ModelsChenxu Yang, Qingyi Si, Yongjie Duan, Zheliang Zhu et al.ICLR 2026 · 250 citations

Related papers

  1. Plan and Budget: Effective and Efficient Test-Time Scaling on Reasoning Large Language ModelsJunhong Lin, Xinyue Zeng, Jie Zhu, Song Wang et al.ICLR 2026 · 30 citations
  2. An Empirical Study of LLM Reasoning Ability Under Strict Output Length ConstraintYi Sun, Han Wang, Jiaqiang Li, Jiacheng Liu et al.EMNLP 2025 · 1 citation
  3. Optimizing Anytime Reasoning via Budget Relative Policy OptimizationPenghui Qi, Zichen Liu, Tianyu Pang, Chao Du et al.NeurIPS 2025 · 29 citations
  4. Graph-enhanced Large Language Models in Asynchronous Plan ReasoningFangru Lin, Emanuele La Malfa, Valentin Hofmann, Elle Michelle Yang et al.ICML 2024 · 33 citations
  5. Accelerating LLM Reasoning via Early Rejection with Partial Reward ModelingSeyyed Saeid Cheshmi, Azal Ahmad Khan, Xinran Wang, Zirui Liu et al.EMNLP Findings 2025
Dusk over the sea between two cliffs drawn in fine vertical lines