---
title: "Budget-Aware Anytime Reasoning with LLM-Synthesized"
description: "The authors build an evaluation pipeline that works in three steps. 21 references. Among them: 0."
authors: ["Xuanming Zhang", "Shwan Ashrafi", "Aziza Mirsaidova", "Amir H. Rezaeian", "Miguel Ballesteros", "Lydia Chilton", "Zhou Yu", "Dan Roth"]
year: 2026
venue: "Findings of the Association for Computational Linguistics: ACL 2026"
source: "https://aclanthology.org/2026.findings-acl.417/"
doi: "10.18653/v1/2026.findings-acl.417"
licence: "CC BY 4.0 (ACL Anthology)"
licence_url: "https://creativecommons.org/licenses/by/4.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/zhang-2026-budget-aware-anytime-reasoning-llm/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/zhang-2026-budget-aware-anytime-reasoning-llm/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2026](https://md.research.elamur.ai/free/en/papers/2026/page/25/) / Budget-Aware Anytime Reasoning with LLM-Synthesized Preference Data

# Budget-Aware Anytime Reasoning with LLM-Synthesized Preference Data

**Authors:** [Xuanming Zhang](https://md.research.elamur.ai/free/en/authors/xuanming-zhang/), Shwan Ashrafi, Aziza Mirsaidova, [Amir H. Rezaeian](https://md.research.elamur.ai/free/en/authors/amir-h-rezaeian/), [Miguel Ballesteros](https://md.research.elamur.ai/free/en/authors/miguel-ballesteros/), [Lydia Chilton](https://md.research.elamur.ai/free/en/authors/lydia-chilton/), [Zhou Yu](https://md.research.elamur.ai/free/en/authors/zhou-yu/) and [Dan Roth](https://md.research.elamur.ai/free/en/authors/dan-roth/) · **Year:** 2026 · **Venue:** [Findings of the Association for Computational Linguistics: ACL 2026](https://md.research.elamur.ai/free/en/venues/findings/) ([Findings of the Association for Computational Linguistics 2026](https://md.research.elamur.ai/free/en/venues/findings/2026/)) · **Publisher:** [Association for Computational Linguistics](https://md.research.elamur.ai/free/en/publishers/association-for-computational-linguistics/) · **Licence:** [CC BY 4.0 (ACL Anthology)](https://creativecommons.org/licenses/by/4.0/)

**Links:** [Publisher's page](https://aclanthology.org/2026.findings-acl.417/) · [PDF](https://aclanthology.org/2026.findings-acl.417.pdf) · [DOI 10.18653/v1/2026.findings-acl.417](https://doi.org/10.18653/v1/2026.findings-acl.417) · [OpenAlex](https://openalex.org/W7166873855)

**Citations:** 0 citations (OpenAlex, 2026-10-14)

## 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 University](https://md.research.elamur.ai/free/en/universities/columbia-university/) — University, New York, United States · 254 works · 56,747 citations

📚 Shelves (4): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 18,614 works · [🤖 Artificial Intelligence](https://md.research.elamur.ai/free/en/shelves/computer-science/artificial-intelligence/) · 17,965 works · [🎭 Arts and Humanities](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/) · 17,450 works · [🗣️ Language and Linguistics](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/language-and-linguistics/) · 17,296 works

🧭 Topics (2): [🧠 Language models & pretraining](https://md.research.elamur.ai/free/en/topics/language-models/) · 3,894 works · [🧮 Reasoning](https://md.research.elamur.ai/free/en/topics/reasoning/) · 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.

```bibtex
@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}
}
```

- [← previous BubbleRAG: Interactive Cognitive Offloading with Thought Bubble in Retrieval-Augmented Generation](https://md.research.elamur.ai/free/en/papers/ye-2026-bubblerag-interactive-cognitive-offloading-thought/)
- [next → Budget-Aware Routing for Long Clinical Text](https://md.research.elamur.ai/free/en/papers/qureshi-2026-budget-aware-routing-long-clinical/)
- [↑ back to papers of 2026](https://md.research.elamur.ai/free/en/papers/2026/page/25/)

## 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](https://scholar.google.com/scholar?q=Kaiyuan+Chen%2C+Jin+Wang%2C+and+Xuejie+Zhang%2E+2024%2E+Learning+to+reason+via+self%2Diterative+process+feedback+for+small+language+models%2E+arXiv+preprint+arXiv%3A2412%2E08393%2E)
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](https://md.research.elamur.ai/free/en/papers/chowdhery-2022-palm-scaling-language-modeling-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](https://scholar.google.com/scholar?q=Thomas+L+Dean+and+Mark+S+Boddy%2E+1988%2E+An+analysis+of+time%2Ddependent+planning%2E+In+AAAI%2C+volume+88%2C+pages+49%E2%80%9354%2E)
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](https://scholar.google.com/scholar?q=Gongfan+Fang%2C+Xinyin+Ma%2C+and+Xinchao+Wang%2E+2025%2E+Thinkless%3A+Llm+learns+when+to+think%2E+arXiv+preprint+arXiv%3A2505%2E13379%2E+%E2%80%94+%5BarXiv%3A2505%2E13379%5D%28https%3A%2F%2Farxiv%2Eorg%2Fabs%2F2505%2E13379%29)
5. Tingxu Han, Zhenting Wang, Chunrong Fang, Shiyu Zhao, Shiqing Ma, and Zhenyu Chen. 2024. [Token-budget-aware llm reasoning](https://md.research.elamur.ai/free/en/papers/han-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](https://scholar.google.com/scholar?q=Eric+A+Hansen+and+Shlomo+Zilberstein%2E+2001%2E+Monitoring+and+control+of+anytime+algorithms%3A+A+dynamic+programming+approach%2E+Artificial+Intelligence%2C+126%281%2D2%29%3A139%E2%80%93157%2E)
7. Jiaxin Huang, Shixiang Shane Gu, Le Hou, Yuexin Wu, Xuezhi Wang, Hongkun Yu, and Jiawei Han. 2022. [Large language models can self-improve](https://md.research.elamur.ai/free/en/papers/huang-2023-large-language-models-can-self/). 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](https://scholar.google.com/scholar?q=Aman+Madaan%2C+Niket+Tandon%2C+Prakhar+Gupta%2C+Skyler+Hallinan%2C+Luyu+Gao%2C+Sarah+Wiegreffe%2C+Uri+Alon%2C+Nouha+Dziri%2C+Shrimai+Prabhumoye%2C+Yiming+Yang%2C+et+al%2E+2023%2E+Self%2Drefine%3A+Iterative+refinement+with+self%2Df)
9. Meta. 2024. Llama 3.3 70b instruct: Text-only instruction-tuned model. [https://huggingface.co/meta-llama/Llama-3.3-70B-Instruct](https://huggingface.co/meta-llama/Llama-3.3-70B-Instruct). Released December 6, 2024; supports 128 k context, improved reasoning and multilingual capabilities. [↗](https://huggingface.co/meta-llama/Llama-3.3-70B-Instruct)
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](https://md.research.elamur.ai/free/en/papers/muennighoff-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/](https://openai.com/index/) gpt-oss-model-card/. Released under Apache 2.0; open-weight model capable of running on 16 GB hardware. [↗](https://openai.com/index/)
12. Richard Yuanzhe Pang, Weizhe Yuan, He He, Kyunghyun Cho, Sainbayar Sukhbaatar, and Jason Weston. 2024. [Iterative reasoning preference optimization](https://md.research.elamur.ai/free/en/papers/pang-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](https://scholar.google.com/scholar?q=Penghui+Qi%2C+Zichen+Liu%2C+Tianyu+Pang%2C+Chao+Du%2C+Wee+Sun+Lee%2C+and+Min+Lin%2E+2025%2E+Optimizing+anytime+reasoning+via+budget+relative+policy+optimization%2E+arXiv+preprint+arXiv%3A2505%2E13438%2E+%E2%80%94+%5BarXiv%3A2505%2E13438)
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](https://md.research.elamur.ai/free/en/papers/rein-2023-gpqa-graduate-level-google-proof/). 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](https://md.research.elamur.ai/free/en/papers/wei-2022-chain-thought-prompting-elicits-reasoning/). 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](https://md.research.elamur.ai/free/en/papers/yang-2025-dynamic-early-exit-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](https://scholar.google.com/scholar?q=Liang+Yao%2E+2024%2E+Large+language+models+are+contrastive+reasoners%2E+arXiv+preprint+arXiv%3A2403%2E08211%2E+%E2%80%94+%5BarXiv%3A2403%2E08211%5D%28https%3A%2F%2Farxiv%2Eorg%2Fabs%2F2403%2E08211%29)
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](https://scholar.google.com/scholar?q=Shunyu+Yao%2C+Dian+Yu%2C+Jeffrey+Zhao%2C+Izhak+Shafran%2C+Tom+Griffiths%2C+Yuan+Cao%2C+and+Karthik+Narasimhan%2E+2023%2E+Tree+of+thoughts%3A+Deliberate+problem+solving+with+large+language+models%2E+Advances+in+neural+inf)
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](https://md.research.elamur.ai/free/en/papers/zhang-2024-context-principle-learning-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](https://scholar.google.com/scholar?q=Huaixiu+Steven+Zheng%2C+Swaroop+Mishra%2C+Hugh+Zhang%2C+Xinyun+Chen%2C+Minmin+Chen%2C+Azade+Nova%2C+Le+Hou%2C+Heng%2DTze+Cheng%2C+Quoc+V+Le%2C+Ed+H+Chi%2C+et+al%2E+2024%2E+Natural+plan%3A+Benchmarking+llms+on+natural+language+pl)
21. Shlomo Zilberstein. 1996. Using anytime algorithms in intelligent systems. AI magazine, 17(3):73–73. [find](https://scholar.google.com/scholar?q=Shlomo+Zilberstein%2E+1996%2E+Using+anytime+algorithms+in+intelligent+systems%2E+AI+magazine%2C+17%283%29%3A73%E2%80%9373%2E)

*Updated 2 November 2026*