Demystifying Chains, Trees, and Graphs of Thoughts

Original Paper: https://arxiv.org/abs/2401.14295

By: Maciej Besta, Florim Memedi, Zhenyu Zhang, Robert Gerstenberger, Guangyuan Piao, Nils Blach, Piotr Nyczyk, Marcin Copik, Grzegorz Kwaśniewski, Jürgen Müller, Lukas Gianinazzi, Ales Kubicek, Hubert Niewiadomski, Aidan O'Mahony, Onur Mutlu, Torsten Hoefler

Abstract:

The field of natural language processing (NLP) has witnessed significant progress in recent years, with a notable focus on improving large language models' (LLM) performance through innovative prompting techniques. Among these, prompt engineering coupled with structures has emerged as a promising paradigm, with designs such as Chain-of-Thought, Tree of Thoughts, or Graph of Thoughts, in which the overall LLM reasoning is guided by a structure such as a graph. As illustrated with numerous examples, this paradigm significantly enhances the LLM's capability to solve numerous tasks, ranging from logical or mathematical reasoning to planning or creative writing. To facilitate the understanding of this growing field and pave the way for future developments, we devise a general blueprint for effective and efficient LLM reasoning schemes. For this, we conduct an in-depth analysis of the prompt execution pipeline, clarifying and clearly defining different concepts. We then build the first taxonomy of structure-enhanced LLM reasoning schemes. We focus on identifying fundamental classes of harnessed structures, and we analyze the representations of these structures, algorithms executed with these structures, and many others. We refer to these structures as reasoning topologies, because their representation becomes to a degree spatial, as they are contained within the LLM context. Our study compares existing prompting schemes using the proposed taxonomy, discussing how certain design choices lead to different patterns in performance and cost. We also outline theoretical underpinnings, relationships between prompting and other parts of the LLM ecosystem such as knowledge bases, and the associated research challenges. Our work will help to advance future prompt engineering techniques.

Summary Notes

A Simplified Guide to Advanced Prompting Schemes for AI Engineers

AI Engineers are pushing the boundaries of natural language processing (NLP) by enabling AI systems to reason and make decisions in a human-like manner.

This guide explores advanced prompting schemes, crucial for arithmetic, commonsense, and symbolic reasoning tasks in AI, and discusses their implications for professionals in the field.

Understanding Reasoning in AI

Reasoning is a core function of NLP, allowing AI to process and respond to information in a way that mirrors human thought. The effectiveness of an AI system's reasoning abilities hinges on the choice of prompting scheme.

Arithmetic Reasoning

Arithmetic reasoning enables AI to tackle mathematical challenges. Here's how different prompting schemes stack up:

• Input-Output (IO) Prompting: Struggles with math tasks.
• Chain of Thought (CoT): Offers substantial improvements in accuracy across various math datasets.
• Zero-shot-CoT: Shows promise in certain areas, though not surpassing CoT.
• Path of Thought (PoT): Excels in financial datasets, outperforming CoT.

Different schemes like decomposition and refinement show varying levels of success in math reasoning, highlighting the importance of context and task complexity.

Commonsense Reasoning

For AI to apply broad knowledge to new scenarios, the choice of prompting scheme is key:

• CoT: Performs better than IO prompting in datasets requiring strategic answers.
• SelfAsk: Further enhances performance, especially in complex, multi-hop questions.

Refinement strategies improve AI's contextual understanding, enabling more sophisticated reasoning.

Symbolic Reasoning

This involves abstract problem-solving, where:

• CoT: Excels in familiar tasks but struggles with unfamiliar ones.
• CoS: Offers a noticeable boost in spatial reasoning tasks over CoT.

Tree and Graph Schemes

The effectiveness of tree and graph-based schemes varies greatly with the task and dataset:

• Tree schemes are useful for decomposable problems and creative tasks.
• Graph schemes enhance performance in arithmetic and commonsense reasoning but at a computational cost.

Refinement Schemes for Specialized Domains

In coding tasks, refinement schemes like SELF-REFINE improve readability and efficiency, showing their value in niche areas.

Understanding Topology & Scheduling

The structuring of reasoning steps and the organization of prompts play a critical role in the effectiveness of prompting strategies.

Looking Ahead: Future Research

Promising avenues for future research include exploring new topology classes, enhancing single-prompt strategies, integrating with advanced neural networks, and leveraging hardware acceleration for better performance.

Conclusion

For AI Engineers in enterprise environments, choosing the appropriate prompting scheme is vital for developing advanced AI systems.

This guide lays the groundwork for further exploration and innovation in AI reasoning, pointing towards the development of more advanced, efficient, and human-like AI solutions.