PaperlayerView exact revision on arXiv

Source-linked AI summary

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

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

arXiv:2308.10379v3cs.CLcs.AI

TL;DR

LLM methods for deeper thought exploration often rely on external, repeated generation and assessment, increasing query and computational demands. AoT uses algorithmic examples in context to guide exploration within generation. The authors report that it surpasses prior single-query and external tree-search approaches while using fewer queries and tokens, and can search fewer nodes than the DFS algorithm it imitates.

  • Problem

    Methods for deeper planning and thought exploration can require repeated LLM queries and computational resources, while linear reasoning paths restrict coverage when subproblems have multiple viable options.

    Source: §1 · p. 1

  • Method

    AoT uses algorithmic in-context examples to guide iterative exploration of candidate paths within one or a few unified generations.

    Source: §1 · pp. 2–3

  • Results

    The authors report that AoT surpasses prior single-query techniques and external tree-search implementations, and systematically navigates fewer nodes than its DFS counterpart.

    Source: §5 · p. 8, §6 · p. 9

  • Takeaways & Limitations

    The authors present AoT as a way to streamline idea discovery while balancing cost and computational demands.

    Source: §6 · p. 9

    AoT was tested only with GPT-4, and the authors say its advanced capabilities appear pivotal; its resource demands also exceed standard prompting and CoT.

    Source: §7 · p. 9

Abstract

from arXiv · show

Current literature, aiming to surpass the "Chain-of-Thought" approach, often resorts to external modi operandi involving halting, modifying, and then resuming the generation process to boost Large Language Models' (LLMs) reasoning capacities. Due to their myopic perspective, they escalate the number of query requests, leading to increased costs, memory, and computational overheads. Addressing this, we propose the Algorithm of Thoughts -- a novel strategy that propels LLMs through algorithmic reasoning pathways. By employing algorithmic examples fully in-context, this overarching view of the whole process exploits the innate recurrence dynamics of LLMs, expanding their idea exploration with merely one or a few queries. Our technique outperforms earlier single-query methods and even more recent multi-query strategies that employ an extensive tree search algorithms while using significantly fewer tokens. Intriguingly, our results suggest that instructing an LLM using an algorithm can lead to performance surpassing that of the algorithm itself, hinting at LLM's inherent ability to weave its intuition into optimized searches. We probe into the underpinnings of our method's efficacy and its nuances in application. The code and related content can be found in: https://algorithm-of-thoughts.github.io.

1. Introduction

LLM reasoning has moved from direct answers toward linear reasoning and external search, but deeper exploration can require repeated queries and substantial resources. AoT instead uses algorithmic in-context examples to guide recursive exploration, with the authors reporting fewer tokens and queries alongside stronger performance than prior approaches.

1. Introduction

  • The introduction situates LLM reasoning between direct-answer strategies and linear reasoning paths, while noting external mechanisms that alter generation by changing context.It also describes intermediary reasoning steps as improving arithmetic reasoning tasks.Source: §1 · p. 1
  • External tree-search approaches can explore alternatives through repeated generation, assessment, and resumption, but this increases query and computational demands.The paper also notes potential latency, bandwidth, availability, and energy costs from repeated queries.Source: §1 · pp. 1–2
  • The authors report that AoT surpasses multi-query techniques while requiring significantly fewer tokens for prompting and generation.Their stated goal was to reduce query counts while maintaining performance on tasks requiring world knowledge.Source: §1 · p. 2
  • AoT uses algorithmic examples to guide layered exploration of candidate ideas, reference earlier intermediate steps, and pursue or abandon paths within iterative generation.The authors frame this as a hybrid of human intuitive insight and systematic algorithmic exploration.Source: §1 · pp. 2–3
  • AoT reframes in-context learning as [PROBLEM, SEARCH PROCESS, SOLUTION], rather than examples pairing problems with answers or successive solution steps.The authors report that LLMs can add intuition to the algorithmic search and surpass the algorithm itself in search efficiency.Source: §1 · p. 3
  • The paper presents AoT as a new in-context learning paradigm and previews later discussion of its idea, experiments, hypotheses, and conclusion.Source: §1 · p. 3

2. Related Work

Related work spans direct input-output prompting, linear chains of reasoning, and methods for decomposition or tree search. AoT is distinguished as an exploratory approach that allows reasoning paths to change rather than requiring a fixed sequence.

Standard Prompting

  • Standard prompting gives a language model a few input-output examples before it answers a test sample.The paper describes it as general and requiring no special prompting strategy, but reports worse performance than more advanced methods (Shao et al., 2023; Wei et al., 2022a; Lyu et al., 2023).Source: §2 · p. 3

Chain-of-Thought

  • CoT presents intermediate reasoning pieces in examples, prompting the model to decompose a problem into simpler linear steps toward an answer.Self-consistency samples multiple reasoning paths and selects by majority vote, requiring additional generations (Wang et al., 2022).Source: §2 · p. 3

Least-to-Most prompting (L2M)

  • Least-to-Most prompting decomposes a problem into smaller subproblems and solves them sequentially, relying on a nearly perfect decomposition in one attempt.The paper contrasts this assumption with tasks such as the game of 24, where decomposition is complex; AoT considers multiple options for each subproblem.Source: §2 · p. 4

Tree of Thoughts (ToT)

  • Tree of Thoughts explores multiple options with external tree-search mechanisms and can use LLM evaluations to prune unpromising nodes.The paper says ToT requires multiple LLM queries and external response-processing functions, whereas AoT uses a single prompt without coding skills.Source: §2 · p. 4

3. Algorithm of Thoughts

Algorithm of Thoughts (AoT) uses in-context search-algorithm examples and uninterrupted generation to explore candidate paths with few interactions. The section also describes how AoT handles search choices and states a theoretical expressivity result.

  • Adding correct in-context equations with identical outputs sharply reduces text-davinci-003’s accuracy on basic arithmetic tasks.The passage links the decline to the possibility that correct reasoning examples can bias the model toward echoing outputs.Source: §3 · p. 4, Figure 3 · p. 4
  • AoT patterns in-context examples after DFS or BFS and addresses tree-search tasks in one unified generation sweep, using one or two LLM interactions.It aims to reduce the need for separate queries over subsets while exploring candidate paths.Source: §3 · p. 4
  • AoT frames intermediate search layers as choosing among candidate chains, focusing its examples on the search process rather than solving each selected subproblem.Source: §3 · p. 5
  • AoT continuously generates solutions for the current subproblem without pauses, keeping them in shared context for evaluation.The authors argue that uninterrupted sequences can yield correct choices that isolated token probabilities miss.Source: §3 · p. 5
  • The approach uses in-context examples to prioritize promising candidates and predominantly adopts DFS with pruning, while also reporting BFS metrics.The authors say this avoids separate evaluation prompts and external search mechanisms.Source: §3 · p. 5
  • AoT is stated to tackle NP problems, extending the expressivity result for CoT from P problems.The corollary relates transformer decoding steps under AoT to time-complexity classes.Source: §3 · p. 5

4. Experiments

Across the tested benchmarks, AoT outperforms single-prompt methods and external tree-search strategies. The experiments examine Game of 24, mini crosswords, and fine-tuning, alongside task-specific setup and error analyses.

4. Experiments

  • Across the tested benchmarks, AoT outperforms single-prompt methods and external tree-search strategies, including ToT.The authors also report that AoT retains an advantage over standard prompting or CoT after fine-tuning.Source: §4 · pp. 5–6

4.1. Game of 24

  • The Game of 24 setup uses 5-shot prompts and DFS-style AoT examples; its test set comprises games 901–1000 from a difficulty-ranked collection of 1,362 games.The reported AoT search uses temperature 0; success requires reaching 24 with the exact numbers and allowed operations.Source: §4.1 · p. 6
  • With one query, AoT outperforms ToT on Game of 24 while using more than 100 times fewer requests and fewer prompt and completion tokens.ToT permits up to 100 node visits, amounting to several hundred LLM queries per example.Source: Table 1 · p. 6, §4.1 · p. 6
  • Manual resolution raises AoT's Game of 24 success rate to 78%, surpassing ToT; 7% of mistakes stem from non-algorithmic factors such as expression missteps and non-finalization.The authors identify prompt refinement for recognizing and expressing successful resolutions as a potential improvement.Source: §4.1 · p. 7, Table 2 · p. 7

4.2. Mini Crosswords

  • On mini crosswords, AoT surpasses earlier prompting methods and ToT in word success rate, with 25 times fewer total tokens than ToT.The setup uses two queries, with a warm-start phase followed by recursive candidate selection and compatibility checks in a single generation window.Source: Table 3 · p. 7, §4.2 · p. 7
  • In mini crosswords, the common errors are misguided word placements followed by pattern misinterpretations; the analysis also identifies failures in preselection and letter alignment.The evaluation covers 20 games, and the authors note that ToT uses an external mechanism to address letter alignment.Source: §4.2 · pp. 7–8

4.3. Finetuning

  • After fine-tuning on 900 examples, AoT fine-tuning improves GPT-3.5-Turbo by 60%, compared with 8% for CoT.The reported Game of 24 solution rates for CoT and AoT were similar, while the authors conclude that fine-tuning alone does not produce implicit nonlinear thinking.Source: Table 5 · p. 8, §4.3 · p. 8

5. Discussion

The discussion examines how AoT searches the Game of 24, how example length affects its search, and how it performs on other tasks and models. AoT visits fewer nodes than DFS, while results on question answering and dynamic programming are described more cautiously.

Can AoT surpass the DFS it is patterned after?

  • AoT systematically visits fewer nodes than its DFS counterpart, with the authors attributing the difference to the LLM’s heuristic rather than DFS’s uniform subtree selection.The authors describe this as an advantage of the LLM’s recursive reasoning.Source: §5 · p. 8, Figure 5 · p. 8

How does the search step count within the algorithmic example modulate AoT’s behavior?

  • Longer in-context examples produce longer generations, while shorter examples produce shorter ones than standard AoT, suggesting example length biases search velocity.AoT (Short) uses one or two steps per example; AoT (Long) adds three to five subtree explorations.Source: §5 · p. 8, Figure 6 · p. 9

Can AoT be used for question-answering tasks?

  • On GSM8K and StrategyQA, AoT shows a slight boost, while GPT-4 with CoT is already competent on these tasks.The evaluation used the first 100 questions from each benchmark.Source: §5 · p. 9, Table 6 · p. 9

Can AoT work as other dynamic programming methods?

  • For Coin Change and Edit Distance, the authors omit ToT’s DFS/BFS results as unfairly poor comparisons, noting tabulation is easier and single-leaf CoT can solve these problems.They treat ToT’s performance as equivalent to CoT when using a single leaf node.Source: §5 · p. 9, Table 7 · p. 9

Can AoT help other SOTA LLMs?

  • Claude 3 and Gemini 1.5 Pro both benefit significantly from AoT; Gemini 1.5 Pro was not evaluated with CoT-SC because API access was unavailable.Table 8 provides the additional model results.Source: §5 · p. 9, Table 8 · p. 9

6. Conclusion

The paper presents AoT as a minimal-query prompting strategy and reports that it outperforms prior single-query and external tree-search approaches. It frames the approach as a way to streamline idea discovery while identifying token efficiency and theoretical understanding as future work.

Conclusion

  • AoT navigates LLM reasoning pathways using minimal queries and outperforms prior single-query techniques and external tree-search implementations.The authors describe its aim as streamlining idea discovery while balancing cost and computational demands.Source: §6 · p. 9
  • Future work includes designing more token-efficient algorithmic examples and developing adaptive mechanisms for “tunnel-vision” activation to expedite search.The authors also call for deeper theoretical understanding of this mode of in-context learning.Source: §6 · p. 9
  • The authors identify theoretical investigation of this in-context learning approach as an open direction.They describe it as a fresh mode of in-context learning.Source: §6 · p. 9

7. Limitations

AoT reduces queries relative to ToT but uses more resources than standard prompting and CoT. The reported evaluation is limited to GPT-4, and the authors caution that less capable models may not see comparable gains.

Limitations

  • AoT’s resource demands exceed those of standard prompting and CoT because it explores ideas through token generation.The authors identify token-efficient algorithmic examples as a future research direction.Source: §7 · p. 9
  • The evaluation tested GPT-4 exclusively, so performance on other models is not established by these tests.The authors suggest GPT-4’s advanced capabilities may be important for AoT’s optimal functioning.Source: §7 · p. 9
  • The authors caution that less capable models might not achieve comparable performance boosts from AoT.This caveat concerns model capability, not a reported test of all lower-capability models.Source: §7 · p. 9

A. Game of 24 - Additional Details

The appendix defines Game of 24 search terms and maps the first operations, solution node, and other nodes in an illustration. These terms describe the states explored and the extent of search.

Game of 24 terminology

  • In Figure 7, yellow nodes mark first operations and their resulting states, green marks the solution node, and pink marks all other nodes.Source: Figure 7 · p. 13
  • First operations are the addition, subtraction, multiplication, or division choices made after selecting the first two numbers.Figure 7 marks the first operations and the states they lead to in yellow.Source: A. Game of 24 - Additional Details · p. 13, Figure 7 · p. 13
  • Subtree exploration means searching all or most nodes branching from the same state, typically when fewer than four numbers remain.Source: A. Game of 24 - Additional Details · p. 13
  • A visited node is a state consisting of the numbers remaining after operations; for example, 8 3 1 can be one state.The passage also gives 8 3 as a state after another operation.Source: A. Game of 24 - Additional Details · p. 13

B. Creative Writing

The creative-writing task asks the LLM to turn four arbitrary sentences into a cohesive four-paragraph narrative, ending each paragraph with one of the given sentences. The exercise emphasizes creativity and strategic deliberation.

B. Creative Writing

B.1. Task Setup

The task uses 100 distinct input sets of randomly sourced sentences and evaluates responses primarily for coherence. Each response receives five GPT-4 zero-shot ratings, which are averaged.

B.1. Task Setup

  • 100 distinct input sets are formed from sentences randomly sourced from randomwordgenerator.com.Source: §B.1 · p. 13
  • Because the task has no predetermined correct answers, evaluation focuses on response coherence.GPT-4 is noted to consistently follow the input guidelines.Source: §B.1 · p. 13
  • Each response is rated for coherence by GPT-4 using a zero-shot prompt, with five ratings averaged on a 1-to-10 scale.Source: §B.1 · p. 13

B.2. Baselines

The baselines are standard and Chain-of-Thought prompts without preliminary training, while ToT results are reported without modification. The CoT prompt asks for a plan before narrative drafting, and each standard and CoT method generates ten samples per task iteration.

B.2. Baselines

  • Standard and CoT prompts are used without preliminary training, and ToT results are presented without modification.Source: §B.2 · pp. 13–14
  • The standard prompt directly instructs the LLM to write a cohesive narrative under the stipulated parameters.Source: §B.2 · p. 13
  • The CoT prompt requires a succinct plan before drafting the narrative, functioning as an intermediate cognitive bridge.Source: §B.2 · pp. 13–14
  • Ten samples are generated for each task iteration using both standard and CoT methods.Source: §B.2 · p. 14

B.3. AoT Setup

The AoT creative-writing approach is evaluated zero-shot. It generates five plans, selects the most promising, and then refines the resulting narrative for coherence.

B.3. AoT Setup

  • The AoT approach tackles the task in a zero-shot setting, mirroring ToT’s methodology.Source: §B.3 · p. 14
  • The prompt first asks the model to formulate five distinct plans and select the most promising one to shape a narrative.Source: §B.3 · p. 14
  • The selected plan’s narrative is then refined for optimal coherence.Source: §B.3 · p. 14

B.4. Results

On the creative-writing task, AoT outperforms standard prompting and CoT and improves over ToT, though its advantage over ToT is not statistically significant; it also requires fewer queries than ToT.

B.4. Results

  • AoT requires fewer queries than ToT.The passage provides no query-count values.Source: §B.4 · p. 14, Table 9 · p. 14
  • AoT outperforms the single-query prompting methods standard prompting and CoT on the creative-writing task.Source: §B.4 · p. 14, Figure 8 · p. 14
  • AoT outpaces standard prompting and CoT on creative-writing performance and improves over ToT, but the difference from ToT is not statistically significant.Figure 8 compares the four prompting methods; Table 9 consolidates performance scores.Source: Figure 8 · p. 14, §B.4 · p. 14, Table 9 · p. 14

C. CoT vs. Single Iteration AoT in the Game of 24

With only one initial operation in its in-context examples, AoT (Short) uses tree search on the remaining three numbers and achieves a 48% success rate, versus 4% for CoT.

C. CoT vs. Single Iteration AoT in the Game of 24

D. Detailed Analysis on the Effect of the Length of the Prompts

Across AoT (Short), AoT, and AoT (Long), the number of initial steps in the prompts correlates with solution length; balanced initial steps emphasizing promising operations are associated with earlier successes.

D. Detailed Analysis on the Effect of the Length of the Prompts

E. Proof of Corollary 3.1

The corollary considers transformers generating O(a^n) intermediate tokens with AoT; the proof invokes exponential intermediate-token scaling with problem depth and possible actions to infer capability to solve NP problems.

E. Proof of Corollary 3.1

  • The corollary’s setting is an AoT transformer generating O(a^n) intermediate tokens, with TIME(a^n) defined for a ≥ 1.Source: E. Proof of Corollary 3.1 · p. 15
  • The proof says backtracking and continuing from other nodes makes intermediate-token counts scale exponentially with problem depth and possible actions per leaf, then invokes Merrill and Sabharwal’s Theorem 2 to state NP-problem capability.AOT(n) denotes AoT decoding steps for an input of n tokens.Source: E. Proof of Corollary 3.1 · p. 15

F. Prompts

This section presents the appendix’s prompts and chat-role conventions across reasoning and writing tasks. It covers Game of 24 and arithmetic search formats, crossword solving, and workflows for coherent writing and coherence scoring.

F.1. Game of 24

  • The prompts use role labels for chat-completion interactions, with line breaks marking transitions between user and assistant turns.The appendix says “System,” “User,” and “Assistant” denote OpenAI API roles.Source: §F.1 · pp. 15–16

F.1.1. AOT (LONG)

  • The long prompt restricts operations to basic arithmetic, excludes negative or fractional intermediate values, and sorts remaining numbers in descending order.It also tells the model not to give up because each supplied number set has a solution.Source: §F.1.1 · pp. 23–24
  • When two numbers remain, the long prompt checks whether a basic arithmetic operation can produce 24, then demonstrates a solution by backtracking its steps.For 14, 8, 8, and 2, it returns (14 −8) * (8 / 2) = 24.Source: §F.1.1 · pp. 24–26

F.1.2. AOT (RANDOM)

  • The prompt asks users to use basic arithmetic operations to obtain 24, choosing two remaining numbers at each step to form a new number; it shows candidate expressions before giving an answer.For 4, 4, 6, and 8, it gives (6 −4) * (4 + 8) = 24.Source: §F.1.2 · p. 30

F.1.3. AOT (BFS)

  • The BFS prompt applies the long prompt’s nonnegative, nonfractional constraint and checks whether the final two numbers can yield 24.With three numbers left, it selects promising operations intended to leave a solvable pair; on reaching 24, it backtracks to state the answer.Source: §F.1.3 · pp. 31–32
  • The example lists candidate first, second, and third steps, then backtracks to the solution 14 − 8 = 6, 8 / 2 = 4, and 6 * 4 = 24.It gives the answer as (14 − 8) * (8 / 2) = 24.Source: §F.1.3 · pp. 32–33

F.2. AoT (Short)

  • The short AoT prompt asks for 24 using the given numbers and basic arithmetic, excluding operations that yield negative or fractional numbers.It says the remaining numbers are shown in descending order in parentheses and that every given set has a solution.Source: §F.2 · p. 42
  • With two numbers left, the short prompt checks whether a single basic arithmetic operation can produce 24, illustrating both solvable and unsolvable pairs.Examples include (30, 6) and (8, 3) as solvable, and (21, 2) and (12, 8) as unsolvable.Source: §F.2 · p. 42
  • Short AoT examples show selecting a promising operation, finding a path to 24, and backtracking to present the arithmetic solution.For 14, 8, 8, 2, the example uses 8 / 2 = 4, 14 − 8 = 6, then 6 * 4 = 24.Source: §F.2 · p. 42

F.3. 5 × 5 Mini Crosswords Prompts

  • The appendix says its prompts use System, User, and Assistant as OpenAI chat-completion roles, with line breaks marking API turns.It introduces exact experimental prompts and selected LLM generations.Source: §F.3 · p. 46

F.3.1. AOT

  • The crossword AoT example uses found words’ intersecting letters to constrain candidates for the next unfound entry against its clue.It selects olein for h2 using letters from v2 and v5, then tests candidates for subsequent vertical entries using horizontal-word letters.Source: §F.3.1 · pp. 46–47
  • The crossword-solving example fills entries by matching clue answers to crossing letters, then chooses abase from two fitting candidates to complete the grid.The prompt proceeds between horizontal and vertical entries, using already filled words to constrain each next answer.Source: §F.3.1 · pp. 48–50
  • A second crossword example rejects uvetta because it fails the crossing pattern, then fills entries including redia, irade, and frett.The prompt derives required letters from existing words and repeats the process until all listed entries are filled.Source: §F.3.1 · pp. 51–52

F.3.2. PROPOSE WORDS

  • The proposed-words prompt supplies five candidate words for each horizontal and vertical clue, including options such as RILLE, TEMPT, and ROSTER.The prompt requests ten options per clue; the supplied examples list five options for each of the five horizontal and five vertical clues.Source: §F.3.2 · p. 53

F.4.1. AOT

  • The writing task requires a coherent passage of four short paragraphs, each ending with the provided sentence.The required ending sentence is specified with the placeholder {0}.Source: §F.4.1 · p. 53
  • The writing prompt first asks for five plans, then detailed comparison of their promise and a final line identifying the best choice by integer ID.After selecting a plan, the model writes and refines a coherent passage while retaining the required ending sentence for each paragraph.Source: §F.4.1 · pp. 53–54

F.4.2. SCORE PROMPT

  • The score prompt asks the model to analyze a passage and conclude with an integer coherence score from 1 to 10.Source: §F.4.2 · p. 54

Related papers

Loading 2308.10379v3…