Algorithm of Thoughts: Enhancing Exploration of Ideas in Large Language Models
Bilgehan Sel, Ahmad Al-Tawaha, Vanshaj Khattar, Lu Wang, Ruoxi Jia and Ming Jin Virginia Tech, Microsoft
“Current literature, aiming to surpass the “Chain-of-Thought” approach, often resorts to an external modus operandi involving halting, modifying, and then resuming the generation process to boost Large Language Models’ (LLMs) reasoning capacities. This mode escalates 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, pioneering a new mode of in-context learning. By employing algorithmic examples, we exploit 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 stands on par with a recent multi-query strategy that employs an extensive tree search algorithm. 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.”
Evaluation capabilities of LLMs can also be used to direct the search by pruning nodes that are hopeless to increase efficiency. However, ToT’s Achilles’ heel is its excessive reliance on LLM queries, at times necessitating hundreds for just one problem.
To offset this bias, diversifying the outputs of examples might seem like a viable solution, but this could subtly skew the distribution of outputs. Merely adding unsuccessful trials, much like a random search, might inadvertently encourage the model to retry rather than truly solve. Capturing the true essence of algorithmic behavior, where both failed searches and subsequent recovering and learning from such attempts play a role, we incorporate in-context examples patterned after search algorithms, notably depth-first search (DFS) and breadth-first search (BFS). See Fig. 1 for an example.
Rather than posing separate queries for every subset, we leverage the iterative capabilities of the LLM to address them in one unified generation sweep. By confining ourselves to one or two LLM interactions, this approach naturally incorporates insights from antecedent context candidates and tackles intricate issues requiring an in-depth exploration of the solution domain. In alignment with our goal, we also give insights into how small or big those thoughts should be and what type of in-context examples should be given to the LLM to promote token efficiency.
Decomposition into Subproblems. Given a problem, constructing a search tree that delineates feasible reasoning pathways is already a demanding task, excluding the actual problem-solving aspect. Any decomposition must consider not just the interrelations between subtasks, but also the ease of addressing each individually.
As above, existing techniques lean on additional prompting to discern the potential of tree nodes, aiding decisions regarding exploration direction. Our observations suggest that if the most promising routes are encapsulated within the in-context examples, LLMs inherently gravitate towards prioritizing those promising candidates. This diminishes the need for intricate prompt engineering and allows the incorporation of intricate heuristics, whether intuitive or knowledge-driven. Again, the absence of disjoint prompts in our approach allows for an immediate assessment of candidate viability in the same generation.