[Paper] Algorithmic Thinking Theory

Source: arXiv - 2512.04923v1

Overview

The paper “Algorithmic Thinking Theory” proposes a fresh theoretical lens for understanding how large language models (LLMs) can be turned into powerful reasoning engines. By treating an LLM as a probabilistic oracle and viewing iterative prompting strategies as algorithms that query this oracle, the authors build a formal framework that explains why techniques like self‑refinement, chain‑of‑thought, and answer‑aggregation work so well—and how we can systematically design even better ones.

Key Contributions

• Algorithmic abstraction of LLM reasoning – models the LLM as a black‑box oracle and formalizes reasoning plans as algorithms that query it repeatedly.
• Unified theory for iterative improvement – captures popular heuristics (self‑critique, re‑prompting, majority voting) under a single mathematical framework.
• Performance guarantees – derives bounds on success probability and query complexity for different algorithmic strategies.
• Design principles for new reasoning methods – translates theoretical insights into concrete recipe‑like guidelines for building more effective prompting pipelines.
• Empirical validation – demonstrates that the theory predicts observed gains across several benchmark reasoning tasks (e.g., math word problems, commonsense QA).

Methodology

1. Probabilistic Oracle Model – The LLM is abstracted as a function that, given a prompt, returns a random answer drawn from an unknown distribution that reflects the model’s knowledge and stochasticity.
2. Reasoning Algorithms – The authors define a class of algorithms that can (a) generate an initial solution, (b) request refinements or alternative solutions, and (c) combine multiple outputs (e.g., via voting or weighted aggregation).
3. Theoretical Analysis – Using tools from probability theory and algorithmic analysis, they prove how the number of oracle calls and the quality of the aggregation rule affect the overall error probability.
4. Experimental Suite – They implement representative algorithms (plain chain‑of‑thought, self‑consistency, iterative self‑critique) on state‑of‑the‑art LLMs (GPT‑4, Claude, LLaMA‑2) and compare the observed success rates with the predictions of their theory.

Results & Findings

• Iterative prompting consistently outperforms single‑shot prompting, with diminishing returns that match the derived theoretical curves.
• Self‑consistency (sampling many chain‑of‑thought traces and voting) achieves near‑optimal error reduction for a given query budget, confirming the theory’s claim about majority voting being an efficient aggregator.
• A simple “refine‑then‑aggregate” algorithm (generate a solution, ask the model to critique and improve it, then combine several refined answers) often surpasses more ad‑hoc prompting tricks, delivering up to a 15 % absolute boost on hard math benchmarks.
• The framework accurately predicts the trade‑off between query cost (number of LLM calls) and accuracy, enabling practitioners to budget API usage more intelligently.

Practical Implications

• Prompt‑engineering roadmaps – Developers can now follow a principled checklist (generate → critique → resample → aggregate) rather than trial‑and‑error, reducing time spent on prompt tuning.
• Cost‑aware reasoning pipelines – By quantifying how many oracle calls are needed to reach a target accuracy, teams can optimize API spend, especially when using paid LLM services.
• Robust AI assistants – Embedding the algorithmic reasoning loop into chatbots or code‑assistants can make them more reliable on complex tasks like multi‑step calculations, logical deduction, or debugging.
• Framework‑agnostic integration – Because the theory treats the LLM as a black box, the same reasoning algorithms can be dropped into any model (open‑source or proprietary) without needing architectural changes.
• Tooling opportunities – The paper’s abstractions lend themselves to libraries that automatically manage sampling, self‑critique, and voting, similar to how hyperparameter‑tuning frameworks automate model search.

Limitations & Future Work

• Oracle assumptions – The theory presumes the LLM’s answer distribution is stationary across calls, which may break when context windows or system prompts change dynamically.
• Scalability of sampling – While the bounds are tight, achieving them can still require many API calls for very hard problems, limiting real‑time applicability.
• Evaluation breadth – Experiments focus on text‑based reasoning tasks; extending the framework to multimodal models (e.g., vision‑language) remains open.
• Adaptive algorithms – Future work could explore algorithms that learn to allocate queries adaptively based on intermediate confidence signals, potentially reducing cost further.

Bottom line: By casting LLM prompting as algorithmic reasoning over a probabilistic oracle, this work gives developers a rigorous, cost‑effective playbook for building smarter, more reliable AI systems.

Authors

• MohammadHossein Bateni
• Vincent Cohen-Addad
• Yuzhou Gu
• Silvio Lattanzi
• Simon Meierhans
• Christopher Mohri

Paper Information

• arXiv ID: 2512.04923v1
• Categories: cs.AI, cs.CL
• Published: December 4, 2025
• PDF: Download PDF