Self-Evaluation Guided Beam Search for Reasoning
Open accessAbstract
Breaking down a problem into intermediate steps has demonstrated impressive performance in Large Language Model (LLM) reasoning. However, the growth of the reasoning chain introduces uncertainty and error accumulation, making it challenging to elicit accurate final results. To tackle this challenge of uncertainty in multi-step reasoning, we introduce a stepwise self-evaluation mechanism to guide and calibrate the reasoning process of LLMs. We propose a decoding algorithm integrating the self-evaluation guidance via stochastic beam search. The self-evaluation guidance serves as a better-calibrated automatic criterion, facilitating an efficient search in the reasoning space and resulting in superior prediction quality. Stochastic beam search balances exploitation and exploration of the search space with temperature-controlled randomness. Our approach surpasses the corresponding Codex-backboned baselines in few-shot accuracy by $6.34\%$, $9.56\%$, and $5.46\%$ on the GSM8K, AQuA, and StrategyQA benchmarks, respectively. Experiment results with Llama-2 on arithmetic reasoning demonstrate the efficiency of our method in outperforming the baseline methods with comparable computational budgets. Further analysis in multi-step reasoning finds our self-evaluation guidance pinpoints logic failures and leads to higher consistency and robustness. Our code is publicly available at https://guideddecoding.github.io/.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
The publisher hasn’t deposited this paper’s reference list.
Research works printed but not linked: 27
- Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. 2020. Language models are few-shot learners. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual.
- Massimo Caccia, Lucas Caccia, William Fedus, Hugo Larochelle, Joelle Pineau, and Laurent Charlin. 2020. Language gans falling short. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net.
- Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, Alex Ray, Raul Puri, Gretchen Krueger, Michael Petrov, Heidy Khlaaf, Girish Sastry, Pamela Mishkin, Brooke Chan, Scott Gray, Nick Ryder, Mikhail Pavlov, Alethea Power, Lukasz Kaiser, Mohammad Bavarian, Clemens Winter, Philippe Tillet, Felipe Petroski Such, Dave Cummings, Matthias Plappert, Fotios Chantzis, Elizabeth Barnes, Ariel Herbert-Voss, William Hebgen Guss, Alex Nichol, Alex Paino, Nikolas Tezak, Jie Tang, Igor Babuschkin, Suchir Balaji, Shantanu Jain, William Saunders, Christopher Hesse, Andrew N. Carr, Jan Leike, Josh Achiam, Vedant Misra, Evan Morikawa, Alec Radford, Matthew Knight, Miles Brundage, Mira Murati, Katie Mayer, Peter Welinder, Bob McGrew, Dario Amodei, Sam McCandlish, Ilya Sutskever, and Wojciech Zaremba. 2021. Evaluating large language models trained on code.
- 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. 2021. Training verifiers to solve math word problems. CoRR, abs/2110.14168. · arXiv
- Luyu Gao, Aman Madaan, Shuyan Zhou, Uri Alon, Pengfei Liu, Yiming Yang, Jamie Callan, and Graham Neubig. 2023. PAL: program-aided language models. In International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 10764-10799.
- PMLR.
- Alex Graves. 2012. Sequence transduction with recurrent neural networks. CoRR, abs/1211.3711. · arXiv
- Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q. Weinberger. 2017. On calibration of modern neural networks. In Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pages 1321-1330.
- PMLR.
- Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi. 2020. The curious case of neural text degeneration. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net.
- Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. 2022. Large language models are zero-shot reasoners. In NeurIPS.
- Wouter Kool, Herke van Hoof, and Max Welling. 2019. Stochastic beams and where to find them: The gumbel- top-k trick for sampling sequences without replacement. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 3499-3508. PMLR.
- Lorenz Kuhn, Yarin Gal, and Sebastian Farquhar. 2023. Semantic uncertainty: Linguistic invariances for uncertainty estimation in natural language generation. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net.
- Aitor Lewkowycz, Anders Andreassen, David Dohan, Ethan Dyer, Henryk Michalewski, Vinay V. Ramasesh, Ambrose Slone, Cem Anil, Imanol Schlag, Theo Gutman-Solo, Yuhuai Wu, Behnam Neyshabur, Guy Gur-Ari, and Vedant Misra. 2022. Solving quantitative reasoning problems with language models. In NeurIPS.
- Pan Lu, Liang Qiu, Kai-Wei Chang, Ying Nian Wu, Song-Chun Zhu, Tanmay Rajpurohit, Peter Clark, and Ashwin Kalyan. 2023. Dynamic prompt learning via policy gradient for semi-structured mathematical reasoning. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net.
- Clara Meister, Afra Amini, Tim Vieira, and Ryan Cotterell. 2021. Conditional poisson stochastic beam search. CoRR, abs/2109.11034. · arXiv
- Maxwell I. Nye, Anders Johan Andreassen, Guy Gur-Ari, Henryk Michalewski, Jacob Austin, David Bieber, David Dohan, Aitor Lewkowycz, Maarten Bosma, David Luan, Charles Sutton, and Augustus Odena. 2021. Show your work: Scratchpads for intermediate computation with language models. CoRR, abs/2112.00114. · arXiv
- Jack W. Rae, Sebastian Borgeaud, Trevor Cai, Katie Millican, Jordan Hoffmann, H. Francis Song, John Aslanides, Sarah Henderson, Roman Ring, Susannah Young, Eliza Rutherford, Tom Hennigan, Jacob Menick, Albin Cassirer, Richard Powell, George van den Driessche, Lisa Anne Hendricks, Maribeth Rauh, Po- Sen Huang, Amelia Glaese, Johannes Welbl, Sumanth Dathathri, Saffron Huang, Jonathan Uesato, John Mellor, Irina Higgins, Antonia Creswell, Nat McAleese, Amy Wu, Erich Elsen, Siddhant M. Jayakumar, Elena Buchatskaya, David Budden, Esme Sutherland, Karen Simonyan, Michela Paganini, Laurent Sifre, Lena Martens, Xiang Lorraine Li, Adhiguna Kuncoro, Aida Nematzadeh, Elena Gribovskaya, Domenic Donato, Angeliki Lazaridou, Arthur Mensch, Jean-Baptiste Lespiau, Maria Tsimpoukelli, Nikolai Grigorev, Doug Fritz, Thibault Sottiaux, Mantas Pajarskas, Toby Pohlen, Zhitao Gong, Daniel Toyama, Cyprien de Masson d'Autume, Yujia Li, Tayfun Terzi, Vladimir Mikulik, Igor Babuschkin, Aidan Clark, Diego de Las Casas, Aurelia Guy, Chris Jones, James Bradbury, Matthew J. Johnson, Blake A. Hechtman, Laura Weidinger, Iason Gabriel, William Isaac, Edward Lockhart, Simon Osindero, Laura Rimell, Chris Dyer, Oriol Vinyals, Kareem Ayoub, Jeff Stanway, Lorrayne Bennett, Demis Hassabis, Koray Kavukcuoglu, and Geoffrey Irving. 2021. Scaling language models: Methods, analysis & insights from training gopher. CoRR, abs/2112.11446. · arXiv
- Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc V. Le, Ed H. Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. 2023. Self-consistency improves chain of thought reasoning in language models. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net.
- Jason Wei, Yi Tay, Rishi Bommasani, Colin Raffel, Barret Zoph, Sebastian Borgeaud, Dani Yogatama, Maarten Bosma, Denny Zhou, Donald Metzler, Ed H. Chi, Tatsunori Hashimoto, Oriol Vinyals, Percy Liang, Jeff Dean, and William Fedus. 2022a. Emergent abilities of large language models. Trans. Mach. Learn. Res., 2022.
- Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed H. Chi, Quoc V. Le, and Denny Zhou. 2022b. Chain-of-thought prompting elicits reasoning in large language models. In NeurIPS.
- Sarah Wiegreffe and Ana Marasovic. 2021. Teach me to explain: A review of datasets for explainable natural language processing. In Proceedings of the Neural Information Processing Systems Track on Datasets and Benchmarks 1, NeurIPS Datasets and Benchmarks 2021, December 2021, virtual.
- Yonghui Wu, Mike Schuster, Zhifeng Chen, Quoc V. Le, Mohammad Norouzi, Wolfgang Macherey, Maxim Krikun, Yuan Cao, Qin Gao, Klaus Macherey, Jeff Klingner, Apurva Shah, Melvin Johnson, Xiaobing Liu, Lukasz Kaiser, Stephan Gouws, Yoshikiyo Kato, Taku Kudo, Hideto Kazawa, Keith Stevens, George Kurian, Nishant Patil, Wei Wang, Cliff Young, Jason Smith, Jason Riesa, Alex Rudnick, Oriol Vinyals, Greg Corrado, Macduff Hughes, and Jeffrey Dean. 2016. Google's neural machine translation system: Bridging the gap between human and machine translation. CoRR, abs/1609.08144. · arXiv
- Tianyi Zhang, Tao Yu, Tatsunori Hashimoto, Mike Lewis, Wen-Tau Yih, Daniel Fried, and Sida Wang. 2023. Coder reviewer reranking for code generation. In International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 41832-41846.
- PMLR.
- Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schuurmans, Claire Cui, Olivier Bousquet, Quoc V. Le, and Ed H. Chi. 2023. Least-to-most prompting enables complex reasoning in large language models. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net.
- Wangchunshu Zhou, Jinyi Hu, Hanlin Zhang, Xiaodan Liang, Maosong Sun, Chenyan Xiong, and Jian Tang. 2020. Towards interpretable natural language understanding with explanations as latent variables. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual.
Cited by
Sorted by citations
Graph of Thoughts: Solving Elaborate Problems with Large Language Models
Besta, M., Blach, N., Kubicek, A., Gerstenberger, R., Podstawski, M., Gianinazzi, L., Gajda, J., Lehmann, T., Niewiadomski, H., Nyczyk, P., et al. (2024) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v38i16.29720 · Cited by 556 · see citing works
Kamoi, R., Zhang, Y., Zhang, N., Han, J., & Zhang, R. (2024) · Transactions of the Association for Computational Linguistics · doi:10.1162/tacl_a_00713 · Cited by 82 · see citing works
LLMs cannot find reasoning errors, but can correct them given the error location
Tyen, G., Mansoor, H., Carbune, V., Chen, P., & Mak, T. (2024) · Findings of the Association for Computational Linguistics ACL 2024 · doi:10.18653/v1/2024.findings-acl.826 · Cited by 24 · see citing works
Adaptive-solver framework for dynamic strategy selection in large language model reasoning
Zhou, J., Zhong, W., Wang, Y., & Wang, J. (2025) · Information Processing & Management · doi:10.1016/j.ipm.2024.104052 · Cited by 19 · see citing works
Training Large Language Models to Reason in a Continuous Latent Space
Hao, S., Sukhbaatar, S., Su, D., Li, X., Hu, Z., Weston, J., & Tian, Y. (2024) · arXiv · doi:10.48550/arxiv.2412.06769 · Cited by 18 · see citing works
“There are works that equip LLMs with explicit tree search algorithms (Xie et al., 2023; Yao et al., 2023; Hao et al., 2024), or train the LLM on search dynamics and trajectories (Lehnert et al., 2024; Gandhi et al., 2024; Su et al., 2024).”
Automatic Model Selection with Large Language Models for Reasoning
Zhao, J., Xie, Y., Kawaguchi, K., He, J., & Xie, M. (2023) · Findings of the Association for Computational Linguistics: EMNLP (Findings of EMNLP) · doi:10.18653/v1/2023.findings-emnlp.55 · Cited by 13 · see citing works
Self-citationMuennighoff, N., Yang, Z., Shi, W., Li, X. L., Fei-Fei, L., Hajishirzi, H., Zettlemoyer, L., Liang, P., Candès, E., & Hashimoto, T. (2025) · arXiv · doi:10.48550/arxiv.2501.19393 · Cited by 12 · see citing works
“…potential is given in polar coordinates ( 𝑟,𝜃 ) : We can rewrite the potential as: The Hamiltonian for a particle in 2D is given by: In polar coordinates ( 𝑟,𝜃 ) , the Laplacian operator is: So the Hamiltonian in polar coordinates is: The time-independent Schrödinger equation is 𝐻𝜓 = 𝐸𝜓 .”
Understanding Agentic AI: Algorithms and Infrastructure
Ma, W.-L., Guo, Y.-J., Han, Q.-L., Zhou, W., Zhu, X.-G., Xiong, J., Wen, S., & Xiang, Y. (2026) · IEEE/CAA Journal of Automatica Sinica · doi:10.1109/jas.2026.125993 · Cited by 11 · see citing works
Priority Sampling of Large Language Models for Compilers
Grubisic, D., Seeker, V., Synnaeve, G., Leather, H., Mellor-Crummey, J., & Cummins, C. (2024) · EuroMLSys@EuroSys · doi:10.1145/3642970.3655831 · Cited by 17 · see citing works
Enhancing LLM Performance on Legal Textual Entailment with Few-Shot CoT-based RAG
Reji, S. A., Sheik, R., Sharon, A., Avisha Rai, M., & Nirmala, S. J. (2024) · IEEE International Conference on Signal Processing, Informatics, Communication and Energy Systems (SPICES) · doi:10.1109/spices62143.2024.10779705 · Cited by 7 · see citing works
Generating Phishing Attacks and Novel Detection Algorithms in the Era of Large Language Models
Fairbanks, J., & Serra, E. (2024) · IEEE International Conference on Big Data (BigData) · doi:10.1109/bigdata62323.2024.10825007 · Cited by 6 · see citing works
Li, S., Kallidromitis, K., Gokul, A., Koneru, A., Kato, Y., Kozuka, K., & Grover, A. (2025) · IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv51701.2025.01453 · Cited by 4 · see citing works
Sakarvadia, M., Ajith, A., Khan, A., Grzenda, D., Hudson, N., Bauer, A., Chard, K., & Foster, I. T. (2023) · BlackboxNLP Workshop on Analyzing and Interpreting Neural Networks for NLP (BlackboxNLP) · doi:10.18653/v1/2023.blackboxnlp-1.26 · Cited by 4 · see citing works
Gradually Excavating External Knowledge for Implicit Complex Question Answering
Liu, C., Li, X., Shang, L., Jiang, X., Liu, Q., Lam, E. Y. M., & Wong, N. (2023) · Findings of the Association for Computational Linguistics: EMNLP (Findings of EMNLP) · doi:10.18653/v1/2023.findings-emnlp.961 · Cited by 2 · see citing works
SPRInT: Scaling Programmatic Reasoning for INstruction Tuning in mathematics
Yan, Y., Li, L., & Zhang, B.-W. (2025) · Neurocomputing · doi:10.1016/j.neucom.2025.129868 · Cited by 1 · see citing works
ToFC: Tree-of-Fact with Continued Best-First Search for Commonsense Reasoning
Dai, L., & Qin, K. (2024) · International Joint Conference on Neural Networks (IJCNN) · doi:10.1109/ijcnn60899.2024.10649921 · Cited by 1 · see citing works
ECHo: A Visio-Linguistic Dataset for Event Causality Inference via Human-Centric Reasoning
Xie, Y., Li, G., & Kan, M. (2023) · Findings of the Association for Computational Linguistics: EMNLP (Findings of EMNLP) · doi:10.18653/v1/2023.findings-emnlp.268 · Cited by 1 · see citing works
Self-citationLLM-AS: A Self-Improve LLM Reasoning Framework Integrated with A* Heuristics Algorithm
Meng, X., Niu, K., & Chen, X. (2024) · Frontiers in artificial intelligence and applications · doi:10.3233/faia241464
A Meta-Analysis of Cloud-Based Llms in Implicit Multi-Step Reasoning
You, J., Gao, Y., Xu, Z., & Zhao, L. (2025) · International Seminar on Artificial Intelligence, Networking and Information Technology (AINIT) · doi:10.1109/ainit65432.2025.11035021
EEGTCT: Electroencephalogram-Based Chinese Text Decoding
Zhang, S., Yu, B., Zhou, L., Wang, G., Wei, J., Sun, L., & Bu, L. (2025) · Lecture notes in computer science · doi:10.1007/978-981-95-0006-2_15
Self-Chill: A Divergence-Convergence Framework for Multi-Path Generation in LLMs
Li, Y., Chen, Y., Li, D., Wang, W. B., & Zhang, Y. (2026) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp55912.2026.11464445
TARA-LLM: A Knowledge-Driven Model for Task Assignment of Multiplayer Reach-Avoid Games
Liang, R., Yan, R., Liu, B., Li, X., Chen, J., & Dong, X. (2026) · IEEE Transactions on Industrial Informatics · doi:10.1109/tii.2026.3683214
Adaptive Beam Search with Shannon Entropy for Data-Centric Reasoning in LLMs
Kim, Y., Jeong, Y., Kim, J., & Cho, S. (2026) · Lecture notes in computer science · doi:10.1007/978-981-92-1468-6_43
Empirical Study of Process Reward-Guided Model Ensemble for Edge Reasoning
Liu, Y., Wu, Y., Zhao, S., Ye, T., & Chen, J. (2026) · IEEE International Symposium on Circuits and Systems proceedings · doi:10.1109/iscas66217.2026.11562617
Is CUI a Dated Way of Saying LLM?
Simpson, J. (2026) · ACM Conference on Conversational User Interfaces (CUI) · doi:10.1145/3816046.3816302
Reasoning over Semantic IDs Enhances Generative Recommendation
He, Y., Sun, Y., Tan, J., Chen, Y., Kong, X., Shen, C., Wang, X., Zhang, A., & Chua, T. (2026) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/3770855.3818122 · Cited by 1 · see citing works
CYANSQL: Unlock the Power of NL2SQL Via Clustering-Based Test-Time Scaling
Qin, H., Ren, T., He, Z., Wang, X. S., Xing, J., Ye, Y., Huang, S., & Li, J. (2026) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde65706.2026.00084
Ren, J., & Zhao, K. (2026) · International Conference on Machine Learning and Intelligent Computing · doi:10.1145/3829441.3829479
Leak Less by Thinking More: Test-Time Scaling for Contextual Privacy in LLM Reasoning
Wu, Z., Zhang, Q., Lou, J., & Chen, C. (2026) · International Joint Conference on Neural Networks (IJCNN) · doi:10.1109/ijcnn69854.2026.11729472
DynRCA: Dynamic Sampling for Efficient Multi-Agent Reasoning in Microservice RCA
Liu, Y., Xiao, Y., Yang, G., Guo, S., & Qi, F. (2026) · International Joint Conference on Neural Networks (IJCNN) · doi:10.1109/ijcnn69854.2026.11728860
- Authors
- Xie, Y., Kawaguchi, K., Zhao, Y., Zhao, J. X., Kan, M.-Y., He, J., & Xie, M.
- Venue
- Advances in Neural Information Processing Systems 36
- Published
- 2023
- Pages
- 41618-41650
- ISSN
- 1049-5258 (ISSN-L)
- OpenAlex
- W7133217386
- Cited by
- 27
- References
- 0
- Citations by year
- 2026: 11 · 2025: 5 · 2024: 7 · 2023: 4
- FWCI
- 4.79
- Type
- conference paper
- Language
- en
- Open access
- green
- arxiv.org
- Licence
- cc-by-sa
- Locations
- neural information processing systems (publishedVersion)
- arXiv (Cornell University) (submittedVersion, cc-by-sa)
- Rare & Special e-Zone (The Hong Kong University of Science and Technology) (submittedVersion)
- arXiv (Cornell University)
- Funders
- National Supercomputing Centre Singapore
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › AI-based Problem Solving and Planning
- Physical Sciences › Computer Science › Artificial Intelligence › Logic, Reasoning, and Knowledge
- Physical Sciences › Computer Science › Computer Networks and Communications › Constraint Satisfaction and Optimization
- Keywords
- self-assessment, reasoning, search heuristics
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
