Elamur Research⌕
☰
home / papers / 2024 / Adaptive Inference-Time Compute: LLMs Can Predict if They Can Do Better, Even Mid-Generation

Adaptive Inference-Time Compute: LLMs Can Predict if They Can Do Better, Even Mid-Generation

Paper · 2024 · Rohin Manvi, Anikait Singh and Stefano Ermon

Summary

Best-of-N sampling makes LLM outputs better, but it is expensive. It needs a separate reward model and always generates a fixed, large number of candidates. Manvi, Singh and Ermon propose "capability-aware self-evaluation" to cut this cost. After a partial or complete answer, the model sees a short self-evaluation prompt. It then estimates how likely a fresh restart is to beat the current response. The estimate comes from the probability of a single predefined token, so it is very cheap and reuses the existing KV cache.

The authors fine-tune Llama 3.1 8B Instruct on about 30,000 on-policy preference pairs that include ties. The pairs come from real LMSYS user prompts and are labeled with the ArmoRM reward model. The self-evaluation then drives two strategies. Adaptive sampling keeps generating only while improvement still seems likely. Early pruning stops weak candidates partway through. Both give clear quality gains on AlpacaEval and GSM8K at a fraction of the usual sample budget. This makes inference-time scaling more practical when queries vary widely in difficulty.

Key points

  • Training data: roughly 30k preferences from unfiltered LMSYS prompts, labeled by ArmoRM, which was itself trained on about 1M preferences or ratings. No external reward model is needed at inference.
  • Best-of-16 gains for Llama 3.1 8B:
    • AlpacaEval win rate against GPT-4 rises from 21% to 34%.
    • GSM8K accuracy, on held-out problems, rises from 84% to 91%.
  • Adaptive sampling with temperature annealing:
    • An average of 1.2 samples recovers 74% of the 16-sample improvement.
    • An average of 1.9 samples recovers 84%.
  • Early pruning: 50–75% of samples can be cut mid-generation with little quality loss. At 75% pruning, about 56% of generated tokens are saved.
  • Limitation: sequential adaptive sampling adds latency. The authors reduce it with exponentially growing batch sizes and suggest search methods, such as beam search, as future work.

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

🎓Stanford UniversityStanford · United States434 works · 314,419 citations

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksArts and Humanities · 16,039 worksLanguage and Linguistics · 15,891 works

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

Cite

Cite as Rohin Manvi, Anikait Singh and Stefano Ermon. 2024. Adaptive Inference-Time Compute: LLMs Can Predict if They Can Do Better, Even Mid-Generation. arXiv:2410.02725.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.2410.02725 · arXiv 2410.02725

@misc{manvi2024adaptive,
  title = {{Adaptive Inference-Time Compute: LLMs Can Predict if They Can Do Better, Even Mid-Generation}},
  author = {Rohin Manvi, Anikait Singh and Stefano Ermon},
  year = {2024},
  doi = {10.48550/arxiv.2410.02725},
  eprint = {2410.02725},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.2410.02725}
}

References

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

  1. Gaon An, Junhyeok Lee, Xingdong Zuo, Norio Kosaka, Kyung-Min Kim, and Hyun Oh Song. Direct preference-based policy optimization without reward modeling, 2023. URL https://arxiv.org/ abs/2301.12842. — [arXiv:2301.12842](https://arxiv.org/abs/2301.12842) ↗
  2. Zachary Ankner, Mansheej Paul, Brandon Cui, Jonathan D. Chang, and Prithviraj Ammanabrolu. Critique-out-loud reward models, 2024. URL https://arxiv.org/abs/2408.11791. ↗
  3. Ralph Allan Bradley and Milton E. Terry. Rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika, 39(3/4):324–345, 1952. ISSN 00063444. URL http://www.jstor.org/stable/2334029. ↗
  4. Eugene Charniak and Mark Johnson. Coarse-to-fine n-best parsing and maxent discriminative reranking. In Proceedings of the 43rd Annual Meeting on Association for Computational Linguistics, ACL ’05, page 173–180, USA, 2005. Association for Computational Linguistics. doi: 10.3115/ 1219840.1219862. URL…
  5. Wei-Lin Chiang, Lianmin Zheng, Ying Sheng, Anastasios Nikolas Angelopoulos, Tianle Li, Dacheng Li, Hao Zhang, Banghua Zhu, Michael Jordan, Joseph E. Gonzalez, and Ion Stoica. Chatbot arena: An open platform for evaluating llms by human preference, 2024. URL https://arxiv.org/abs/2403. 04132. ↗
  6. Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman. Training verifiers to solve math word problems, 2021. URL https://arxiv.org/abs/2110.14168. ↗
  7. Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, and et al. The llama 3 herd of models, 2024.
  8. Yann Dubois, Xuechen Li, Rohan Taori, Tianyi Zhang, Ishaan Gulrajani, Jimmy Ba, Carlos Guestrin, Percy Liang, and Tatsunori B. Hashimoto. Alpacafarm: A simulation framework for methods that learn from human feedback, 2024.
  9. Mohammad Gheshlaghi Azar, Mark Rowland, Bilal Piot, Daniel Guo, Daniele Calandriello, Michal Valko, and Rémi Munos. A General Theoretical Paradigm to Understand Learning from Human Preferences. arXiv e-prints, art. arXiv:2310.12036, October 2023. doi: 10.48550/arXiv.2310.12036.
  10. Nathan Lambert, Valentina Pyatkin, Jacob Morrison, LJ Miranda, Bill Yuchen Lin, Khyathi Chandu, Nouha Dziri, Sachin Kumar, Tom Zick, Yejin Choi, Noah A. Smith, and Hannaneh Hajishirzi. Rewardbench: Evaluating reward models for language modeling, 2024. URL https://arxiv.org/ abs/2403.13787. ↗
  11. Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, Shashank Gupta, Bodhisattwa Prasad Majumder, Katherine Hermann, Sean Welleck, Amir Yazdanbakhsh, and Peter Clark. Self-refine: Iterative refinement with self-… find
  12. Long Ouyang, Jeff Wu, Xu Jiang, Diogo Almeida, Carroll L. Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, John Schulman, Jacob Hilton, Fraser Kelton, Luke Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul Christiano, Jan Leike, and Ryan Lowe. Training la… — Training language models to follow instructions with human feedback
  13. Rafael Rafailov, Archit Sharma, Eric Mitchell, Stefano Ermon, Christopher D Manning, and Chelsea Finn. Direct preference optimization: Your language model is secretly a reward model. arXiv preprint arXiv:2305.18290, 2023.
  14. Charlie Snell, Jaehoon Lee, Kelvin Xu, and Aviral Kumar. Scaling llm test-time compute optimally can be more effective than scaling model parameters, 2024. URL https://arxiv.org/abs/2408.03314. ↗
  15. Nisan Stiennon, Long Ouyang, Jeff Wu, Daniel M. Ziegler, Ryan Lowe, Chelsea Voss, Alec Radford, Dario Amodei, and Paul F. Christiano. Learning to summarize from human feedback. CoRR, abs/2009.01325, 2020. URL https://arxiv.org/abs/2009.01325. ↗
  16. Haoxiang Wang, Wei Xiong, Tengyang Xie, Han Zhao, and Tong Zhang. Interpretable preferences via multi-objective reward modeling and mixture-of-experts, 2024. URL https://arxiv.org/abs/ 2406.12845. ↗
  17. Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc Le, Ed Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models, 2023. URL https://arxiv.org/abs/2203.11171. ↗
  18. Lunjun Zhang, Arian Hosseini, Hritik Bansal, Mehran Kazemi, Aviral Kumar, and Rishabh Agarwal. Generative verifiers: Reward modeling as next-token prediction, 2024. URL https://arxiv.org/ abs/2408.15240. ↗
  19. Lianmin Zheng, Wei-Lin Chiang, Ying Sheng, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zi Lin, Zhuohan Li, Dacheng Li, Eric P. Xing, Hao Zhang, Joseph E. Gonzalez, and Ion Stoica. Judging llm-as-a-judge with mt-bench and chatbot arena, 2023. URL https://arxiv.org/abs/2306.05685. ↗

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/manvi-2024-adaptive-inference-time-compute-llms/