ICML 2024

Algorithm of Thoughts: Enhancing Exploration of Ideas in Large Language Models

Bilgehan Sel, Ahmad Al-Tawaha, Vanshaj Khattar, Ruoxi Jia, Ming Jin

Side-by-side prompt transcripts for the game of 24. Standard prompting shows only a question and a one-line answer, which is wrong. Chain-of-Thought shows three arithmetic steps leading to an answer, also wrong. Algorithm of Thoughts shows a numbered search: a first operation with a list of follow-up operations and their results, most of which fail, then a retry with a different first operation that ends in "24 = 120 / 5 -> found it!" and a correct answer. — **Figure.** The same puzzle under three prompts: standard prompting gives a bare answer and chain-of-thought a short derivation — both wrong here — while Algorithm of Thoughts shows the whole search, failed branches included, and reaches a correct expression.

Getting a language model to explore alternatives, rather than commit to the first line of reasoning it produces, has generally meant driving it from the outside. Tree of Thoughts and related methods halt generation at each step, spend a separate query asking the model to score partial ideas, prune the weak ones, and resume — with the tree itself maintained in external code that also has to parse the model's replies. The search works, but a single Game of 24 puzzle costs upwards of a hundred API calls (109 on average in this paper's measurements), and the accompanying expense, latency, and infrastructure load scale with it.

Algorithm of Thoughts moves the search inside one generation. The in-context examples are written not as [problem, solution] or [problem, steps, solution] but as [problem, search process, solution]: they show candidate operations being tried, unpromising branches being abandoned, a backtrack to a different subtree, and only then the answer. Because the entire trace stays in one context window, the model judges a new candidate against everything it has already written instead of being asked in a separate call, and it backtracks by writing the retreat out as text rather than through external code. Two probes on text-davinci-003 motivate the design. Adding in-context examples that are all correct but share an identical output steeply degrades accuracy on plain arithmetic, so example diversity has to come from somewhere — here, from failed searches and the recoveries that follow them. And sampling ideas in isolation misreads the model's own preferences: asked for the first five prime numbers, the second-most-likely first token is '1', which is not prime, while uninterrupted generation gets the sequence right.

On the game of 24 (games 901–1000 by difficulty from 4nums.com, run with GPT-4) the method reaches 71% with a single query, against 69% for Tree of Thoughts at an average of 109.1 queries, while using fewer tokens in both directions — 5,450 prompt and 998.4 completion tokens versus 13,900 and 5,500. On 5x5 mini crosswords it reaches 52% word success in two queries against 46.5% for ToT at over 200. The more surprising result is that the model does not merely imitate the depth-first search in its examples: it visits fewer nodes than that search does, apparently substituting its own sense of which subtree is worth opening for the algorithm's fixed ordering. The main benchmarks are GPT-4 only, and token use, while far below ToT, remains above chain-of-thought.

Key results

Game of 24: 71% success from one query, versus 69% for Tree of Thoughts at 109.1 queries per problem on average, with prompt tokens down from 13,900 to 5,450 and completion tokens from 5,500 to 998.4.
5x5 mini crosswords: 52% word success using two queries, versus 46.5% for Tree of Thoughts using more than 200 — a 25x reduction in total tokens.
The model outruns the algorithm it was shown: on the same games it visits fewer nodes than the depth-first search its in-context examples demonstrate, weaving its own heuristic into the traversal order.
Fine-tuning GPT-3.5-Turbo on 900 examples lifts chain-of-thought from 3% to 12% on the game of 24, but Algorithm of Thoughts from 3% to 63%, suggesting the gap is not missing domain knowledge.

BibTeX

@inproceedings{sel2024algorithm,
  title     = {Algorithm of Thoughts: Enhancing Exploration of Ideas in Large Language Models},
  author    = {Sel, Bilgehan and Al-Tawaha, Ahmad and Khattar, Vanshaj and Jia, Ruoxi and Jin, Ming},
  booktitle = {Proceedings of the 41st International Conference on Machine Learning},
  series    = {Proceedings of Machine Learning Research},
  volume    = {235},
  year      = {2024},
  publisher = {PMLR}
}