Elamur Research⌕
☰
home / papers / 2026 / Budget-Aware Anytime Reasoning with LLM-Synthesized Preference Data

Budget-Aware Anytime Reasoning with LLM-Synthesized Preference Data

Paper · 2026 · Xuanming Zhang, Shwan Ashrafi, Aziza Mirsaidova et al.

Summary

The paper looks at how LLMs behave when reasoning is cut short by a fixed token or latency budget. In such cases, a usable partial answer delivered early can be worth more than a complete answer that arrives too late. The authors build an evaluation pipeline that works in three steps. First, it samples Chain-of-Thought traces. Second, it truncates each trace at a series of token checkpoints. Third, it asks the model to produce an answer using only the truncated prefix. They summarize the resulting quality-versus-budget curves with a new metric, the Anytime Index. To improve these curves, they propose Preference Data Prompting (PDP). PDP needs no training. The model's own traces are scored at equal budgets, and pairs of better and worse traces are inserted into the prompt as contrastive examples. The authors test PDP on NaturalPlan (Trip), AIME 2024 and GPQA-Diamond with seven LLMs. It generally improves both intermediate and final quality over standard CoT. The gains are largest for reasoning-oriented models. The work offers a practical way to measure and boost reasoning efficiency under compute limits.

Key points

  • The Anytime Index. It is a normalized, trapezoid-based area under the best-so-far quality curve, with values between 0 and 1. It rewards models that reach good answers at small budgets.
  • Budget checkpoints. NaturalPlan uses budgets of 100–800 tokens, with traces capped at 4,096 tokens. AIME and GPQA use budgets of 200–1600 tokens, with traces capped at 16,384 tokens. Quality is measured by Constraint Satisfaction Rate for planning and by accuracy for QA and math.
  • Building preference pairs. For each input, PDP draws a pool of 64 traces. Pairs are always formed at the same truncation length, so the contrast reflects reasoning quality rather than reasoning length.
  • Models and baselines. The study covers Grok-3, Grok-3-mini, GPT-oss-120B/20B, GPT-4.1, GPT-4o and Llama-3.3-70B. Each is compared against base CoT, LEAP, and PDP(+), an ablation that shows only the preferred traces.
  • Main results.
    • In 6 of the 7 models, PDP outscores LEAP on the overall Anytime Index.
    • For strong reasoning models, PDP's gains over LEAP are about 17.6% in final score, 11.4% in average score, and 7.9 Anytime Index points.
    • For GPT-oss-120B, the overall Anytime Index rises from 54.7 to 65.8.
    • Gains for GPT-4.1 and GPT-4o are weaker.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓Columbia UniversityNew York · United States254 works · 56,747 citations

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 18,614 worksArtificial Intelligence · 17,965 worksArts and Humanities · 17,450 worksLanguage and Linguistics · 17,296 works

🧭 Topics 2Research subjects and languages the work is about.Language models & pretraining · 3,894 worksReasoning · 1,685 works

Cite

Cite as Xuanming Zhang, Shwan Ashrafi, Aziza Mirsaidova, Amir H. Rezaeian, Miguel Ballesteros, Lydia Chilton, Zhou Yu and Dan Roth. 2026. Budget-Aware Anytime Reasoning with LLM-Synthesized Preference Data. Findings of the Association for Computational Linguistics: ACL 2026.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/2026.findings-acl.417

@inproceedings{zhang2026budget,
  title = {{Budget-Aware Anytime Reasoning with LLM-Synthesized Preference Data}},
  author = {Xuanming Zhang, Shwan Ashrafi, Aziza Mirsaidova, Amir H. Rezaeian, Miguel Ballesteros, Lydia Chilton, Zhou Yu and Dan Roth},
  booktitle = {Findings of the Association for Computational Linguistics: ACL 2026},
  year = {2026},
  doi = {10.18653/v1/2026.findings-acl.417},
  url = {https://doi.org/10.18653/v1/2026.findings-acl.417}
}

References

21 references, 9 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Kaiyuan Chen, Jin Wang, and Xuejie Zhang. 2024. Learning to reason via self-iterative process feedback for small language models. arXiv preprint arXiv:2412.08393. find
  2. Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, et al. 2023. Palm: Scaling language modeling with pathways. Journal of Machine Learning Research, 24(240):1–113.
  3. Thomas L Dean and Mark S Boddy. 1988. An analysis of time-dependent planning. In AAAI, volume 88, pages 49–54. find
  4. Gongfan Fang, Xinyin Ma, and Xinchao Wang. 2025. Thinkless: Llm learns when to think. arXiv preprint arXiv:2505.13379. — [arXiv:2505.13379](https://arxiv.org/abs/2505.13379) find
  5. Tingxu Han, Zhenting Wang, Chunrong Fang, Shiyu Zhao, Shiqing Ma, and Zhenyu Chen. 2024. Token-budget-aware llm reasoning. arXiv preprint arXiv:2412.18547.
  6. Eric A Hansen and Shlomo Zilberstein. 2001. Monitoring and control of anytime algorithms: A dynamic programming approach. Artificial Intelligence, 126(1-2):139–157. find
  7. Jiaxin Huang, Shixiang Shane Gu, Le Hou, Yuexin Wu, Xuezhi Wang, Hongkun Yu, and Jiawei Han. 2022. Large language models can self-improve. arXiv preprint arXiv:2210.11610.
  8. Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, et al. 2023. Self-refine: Iterative refinement with self-feedback. Advances in Neural Information Processing Systems, 36:46534–46594. find
  9. Meta. 2024. Llama 3.3 70b instruct: Text-only instruction-tuned model. https://huggingface.co/meta-llama/Llama-3.3-70B-Instruct. Released December 6, 2024; supports 128 k context, improved reasoning and multilingual capabilities. ↗
  10. Niklas Muennighoff, Zitong Yang, Weijia Shi, Xiang Lisa Li, Li Fei-Fei, Hannaneh Hajishirzi, Luke Zettlemoyer, Percy Liang, Emmanuel Candès, and Tatsunori Hashimoto. 2025. s1: Simple test-time scaling. arXiv preprint arXiv:2501.19393.
  11. OpenAI. 2025. Gpt-oss-20b: Open-weight reasoning model. https://openai.com/index/ gpt-oss-model-card/. Released under Apache 2.0; open-weight model capable of running on 16 GB hardware. ↗
  12. Richard Yuanzhe Pang, Weizhe Yuan, He He, Kyunghyun Cho, Sainbayar Sukhbaatar, and Jason Weston. 2024. Iterative reasoning preference optimization. Advances in Neural Information Processing Systems, 37:116617–116637.
  13. Penghui Qi, Zichen Liu, Tianyu Pang, Chao Du, Wee Sun Lee, and Min Lin. 2025. Optimizing anytime reasoning via budget relative policy optimization. arXiv preprint arXiv:2505.13438. — [arXiv:2505.13438](https://arxiv.org/abs/2505.13438) find
  14. David Rein, Betty Li Hou, Asa Cooper Stickland, Jackson Petty, Richard Yuanzhe Pang, Julien Dirani, Julian Michael, and Samuel R. Bowman. 2023. Gpqa: A graduate-level google-proof q&a benchmark. In arXiv preprint arXiv:2311.12022. GPQA-Diamond subset (198 expert-validated graduate-level science ques…
  15. Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al. 2022. Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824–24837. xAI. 2025. Grok 3: The age of reasoning agents. Model…
  16. Chenxu Yang, Qingyi Si, Yongjie Duan, Zheliang Zhu, Chenyu Zhu, Qiaowei Li, Zheng Lin, Li Cao, and Weiping Wang. 2025. Dynamic early exit in reasoning models. arXiv preprint arXiv:2504.15895.
  17. Liang Yao. 2024. Large language models are contrastive reasoners. arXiv preprint arXiv:2403.08211. — [arXiv:2403.08211](https://arxiv.org/abs/2403.08211) find
  18. Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan. 2023. Tree of thoughts: Deliberate problem solving with large language models. Advances in neural information processing systems, 36:11809–11822. find
  19. Tianjun Zhang, Aman Madaan, Luyu Gao, Steven Zheng, Swaroop Mishra, Yiming Yang, Niket Tandon, and Uri Alon. 2024. In-context principle learning from mistakes. arXiv preprint arXiv:2402.05403.
  20. Huaixiu Steven Zheng, Swaroop Mishra, Hugh Zhang, Xinyun Chen, Minmin Chen, Azade Nova, Le Hou, Heng-Tze Cheng, Quoc V Le, Ed H Chi, et al. 2024. Natural plan: Benchmarking llms on natural language planning. arXiv preprint arXiv:2406.04520. find
  21. Shlomo Zilberstein. 1996. Using anytime algorithms in intelligent systems. AI magazine, 17(3):73–73. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/zhang-2026-budget-aware-anytime-reasoning-llm/