Algorithmic Thinking Theory

MohammadHossein Bateni, Vincent Cohen-Addad, Yuzhou Gu, Silvio Lattanzi, Simon Meierhans, Christopher Mohri
Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:613-639, 2026.

Abstract

Large language models (LLMs) have proven to be highly effective for solving complex reasoning tasks. Surprisingly, their capabilities can often be improved by iterating on previously generated solutions. In this context, a reasoning plan for generating and combining a set of solutions can be thought of as an algorithm for reasoning using a probabilistic oracle. We introduce a theoretical framework for analyzing such reasoning algorithms. This framework formalizes the principles underlying popular techniques for iterative improvement and answer aggregation, providing a foundation for designing a new generation of more powerful reasoning methods. Unlike approaches for understanding models that rely on architectural specifics, our model is grounded in experimental evidence. As a result, it offers a general perspective that may extend to a wide range of current and future reasoning oracles.

Cite this Paper

BibTeX
@InProceedings{pmlr-v336-bateni26a, title = {Algorithmic Thinking Theory}, author = {Bateni, MohammadHossein and Cohen-Addad, Vincent and Gu, Yuzhou and Lattanzi, Silvio and Meierhans, Simon and Mohri, Christopher}, booktitle = {Proceedings of Thirty Ninth Conference on Learning Theory}, pages = {613--639}, year = {2026}, editor = {Hanneke, Steve and Lattimore, Tor}, volume = {336}, series = {Proceedings of Machine Learning Research}, month = {29 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v336/main/assets/bateni26a/bateni26a.pdf}, url = {https://proceedings.mlr.press/v336/bateni26a.html}, abstract = {Large language models (LLMs) have proven to be highly effective for solving complex reasoning tasks. Surprisingly, their capabilities can often be improved by iterating on previously generated solutions. In this context, a reasoning plan for generating and combining a set of solutions can be thought of as an algorithm for reasoning using a probabilistic oracle. We introduce a theoretical framework for analyzing such reasoning algorithms. This framework formalizes the principles underlying popular techniques for iterative improvement and answer aggregation, providing a foundation for designing a new generation of more powerful reasoning methods. Unlike approaches for understanding models that rely on architectural specifics, our model is grounded in experimental evidence. As a result, it offers a general perspective that may extend to a wide range of current and future reasoning oracles. } }
Endnote
%0 Conference Paper %T Algorithmic Thinking Theory %A MohammadHossein Bateni %A Vincent Cohen-Addad %A Yuzhou Gu %A Silvio Lattanzi %A Simon Meierhans %A Christopher Mohri %B Proceedings of Thirty Ninth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2026 %E Steve Hanneke %E Tor Lattimore %F pmlr-v336-bateni26a %I PMLR %P 613--639 %U https://proceedings.mlr.press/v336/bateni26a.html %V 336 %X Large language models (LLMs) have proven to be highly effective for solving complex reasoning tasks. Surprisingly, their capabilities can often be improved by iterating on previously generated solutions. In this context, a reasoning plan for generating and combining a set of solutions can be thought of as an algorithm for reasoning using a probabilistic oracle. We introduce a theoretical framework for analyzing such reasoning algorithms. This framework formalizes the principles underlying popular techniques for iterative improvement and answer aggregation, providing a foundation for designing a new generation of more powerful reasoning methods. Unlike approaches for understanding models that rely on architectural specifics, our model is grounded in experimental evidence. As a result, it offers a general perspective that may extend to a wide range of current and future reasoning oracles.
APA
Bateni, M., Cohen-Addad, V., Gu, Y., Lattanzi, S., Meierhans, S. & Mohri, C.. (2026). Algorithmic Thinking Theory. Proceedings of Thirty Ninth Conference on Learning Theory, in Proceedings of Machine Learning Research 336:613-639 Available from https://proceedings.mlr.press/v336/bateni26a.html.

Related Material