Delving into Tree of Thoughts Prompting  

Written By Sebastian Tafoya

Recent breakthroughs in machine learning have propelled language models to new heights, enabling them to tackle a diverse array of tasks. Despite these advancements, language models still face hurdles in problem-solving scenarios that demand exploration, strategic planning, and the ability to make conscious decisions. To overcome these obstacles, a team of researchers from Princeton University and Google DeepMind have developed a novel framework, titled "Tree of Thoughts" (ToT), which empowers language models to engage in deliberate decision-making by evaluating multiple reasoning paths and self-assessing choices to determine the most effective course of action.  

What is ToT Prompting?  

Tree of Thought Prompting is a prompt engineering technique that allows large language models (LLMs) to explore multiple reasoning paths to solve complex problems. Instead of generating a single chain of thoughts, as in the Chain of Thought method, Tree of Thought Prompting creates a tree structure where each node is a coherent unit of text (a thought) that serves as a step. intermediate towards the solution. LLMs can evaluate and choose different options, as well as go back or anticipate, when necessary, to make global decisions. This technique is inspired by the way humans brainstorm, creating and considering various ideas.  

 

Figure 1 visually contrasts the architectural design of the ToT framework with the "Chain-of-Thought" and "Self-Consistency with Chain-of-Thought" reasoning methodologies.   

Figure 1  
Official implementation for paper Tree of Thoughts  
Deliberate Problem Solving with Large Language Models  

How does it work?  

ToT employs a tree-based search approach to tackle problems, where each node represents a partial solution encompassing the initial input and the sequence of thoughts generated thus far. The framework comprises four fundamental components for writing the prompts:  

1. Thought Decomposition: This component is responsible for breaking down the problem into smaller and manageable subproblems, each of which can be solved by generating a thought. A thought is a piece of information that can be expressed in natural language, such as a word, a phrase, a sentence, or a paragraph. The size of a thought depends on the complexity and the domain of the problem.   

For example, if the problem is to write a summary of a news article, a thought could be a sentence that captures the main idea of a paragraph in the article. If the problem is to solve a math equation, a thought could be a step in the calculation process.  

Figure 2  
Thought Decomposition step representation.  

2. Thought Generator: This component is responsible for generating potential thoughts that can be added to the current state to form a partial solution. A state is a sequence of thoughts that represents the progress made so far in solving the problem.  

  

There are two strategies for generating thoughts: CoT and propose prompt. CoT uses a language model to sample multiple thoughts from a single prompt that contains the initial input and the current state. Propose prompt uses a language model to generate one thought at a time from a prompt that contains the initial input, the current state, and a proposal keyword.   

  

For example, if the problem is to write a summary of a news article, CoT could use a prompt like:  

Summary: [current state]  

Sampling multiple sentences that could be added to the summary.  

Propose prompt could use a prompt like:   

Summary: [current state]  

Propose: [proposal keyword]  

This would generate one sentence that matches the proposal keyword, such as “contrast”, “example”, or “conclusion”.  

Figure 3  
Thought Generator step representation.  

3. State Evaluator: This component is responsible for evaluating the quality and the potential of different states in solving the problem. The evaluation serves as a heuristic for the search algorithm, guiding it towards promising states and determining the exploration order.  
  
There are two strategies for evaluating states: independent state evaluation and voting across states. Independent state evaluation uses a language model to score each state based on a prompt that contains the initial input and the state. Voting across states uses a language model to compare pairs of states based on a prompt that contains the initial input and the two states.   

  
For example, if the problem is to write a summary of a news article, independent state evaluation could use a prompt like:  

Summary: [state]  

Score:   

This would generate a numerical score that reflects the coherence, relevance, and conciseness of the summary.  

Voting across states could use a prompt like:   

Summary 1: [state 1]  

Summary 2: [state 2]   

Vote:  

This would generate a vote that indicates which summary is better.  

Figure 4  
State Evaluator step representation.  

4. Search Algorithm: This component is responsible for exploring the search space of possible states and finding the best solution to the problem. The search space is a tree structure, where each node is a state and each edge is a thought. The root node is the initial input and the leaf nodes are the final solutions. The search algorithm traverses the tree and expands the nodes by applying the thought generator and the state evaluator.  

There are two basic search algorithms: breadth-first search and depth-first search. Breadth-first search explores the tree level by level, expanding all the nodes at the same depth before moving to the next depth. Depth-first search explores the tree branch by branch, expanding the most promising node at each depth until reaching a leaf node or a dead end.   

For example, if the problem is to write a summary of a news article, breadth-first search could generate multiple sentences for each paragraph in the article and evaluate them independently, while depth-first search could generate one sentence for each paragraph in the article and evaluate them sequentially.  

Essentially, the ToT framework constructs a thought tree by generating diverse chains-of-thoughts paths. The algorithm then navigates this tree, evaluating the chains of thoughts at each node to identify reasoning paths with the highest likelihood of leading to the correct solution.  

Figure 5  
Search Algorithm step representation. 

Tree of Thoughts implementation  

 Tree of Thoughts Prompting has been successfully applied to three tasks that require non-trivial planning or searching: the 24 game, creative writing, and mini crossword puzzles. For example, in the game of 24, while GPT-4 with the “Chain of Thought” method only solved 4% of the tasks, the “Tree of Thoughts” method achieved a success rate of 74%, as demonstrated in this paper.  

In this example, we are going to use the LangChain platform to implement a ToT-based problem-solving system that can consider important factors, brainstorm, analyze and rank potential solutions to the problem.  

Utilizing LangChain's LLMChain class, we will outline a structured sequence of thought processes, akin to a decision tree, while employing the ChatOpenAI model to generate intermediary insights throughout this deliberative sequence. The Tree of Thoughts prompt is defined using PromptTemplate, and the chain is executed at each step of the process.   

 First, we’ll import the necessary libraries:  

Then we’ll start creating the ToT prompt.  

  • Step 1: Thought Decomposition (Breaking Down the Problem)  

Goal: Divide the problem into manageable subproblems, each solved by generating a "thought."  

  • Step 2: Thought Generator (Creating Potential Solutions)  

Goal: Generate potential "thoughts" to be added to the current state (sequence of thoughts).   

  • Step 3: State Evaluator (Assessing Potential)  

Goal: Evaluate the quality and potential of different states (sequences of thoughts) for solving the problem.   

  • Step 4: Search Algorithm (Finding the Best Solution)  

Goal: Explore the search space of possible states (thought tree) and find the optimal solution.  

Build the Overall ToT:  

Now, we build the overall chain to put the process together, which will follow these steps:  

  • Constructs a thought tree with diverse reasoning paths.  

  • Navigates the tree, evaluating chains of thoughts at each node.  

  • Identifies reasoning paths with the highest likelihood of leading to the solution.  

We employ the 'SequentialChain' component to seamlessly integrate the four chains, ensuring that the output of one chain serves as the input for the subsequent chain.   

The output is:  

Ranking of solutions:

1. Non-motorized transport options: This solution not only addresses transportation issues but also promotes healthier lifestyles and reduces carbon emissions. It is a sustainable and cost-effective option that can have a significant impact on the overall urban environment.

2. Smart traffic management systems: Implementing smart traffic management systems can greatly improve traffic flow, reduce travel times, and enhance road safety. This solution is practical and efficient in optimizing transportation systems.

3. Comprehensive public transportation system: While expanding public transportation networks is essential for reducing traffic congestion and emissions, it may require significant investment and time to implement. However, it remains a crucial aspect of sustainable urban transportation.

4. Carpooling and ridesharing initiatives: Encouraging carpooling and ridesharing can help reduce the number of single-occupancy vehicles on the road, but it may face challenges in terms of changing individual behavior and preferences.

5. Stricter regulations on emissions and electric vehicles: Transitioning to cleaner and greener transportation is vital for reducing air pollution and dependence on fossil fuels. However, the success of this solution may depend on the availability and affordability of electric vehicles and charging infrastructure.

6. Infrastructure improvements: Investing in infrastructure upgrades is necessary for enhancing connectivity and accessibility. While this solution may not directly address transportation issues, it can contribute to creating a more sustainable and resilient urban environment.

7. Community engagement: Involving residents in decision-making processes is crucial for ensuring inclusive and sustainable transportation solutions. However, community engagement may require time and effort to build trust and collaboration among stakeholders.

8. Policy implementation: Enacting and enforcing policies that support sustainable transportation practices is essential for achieving long-term goals. However, policy implementation may face challenges in terms of coordination and enforcement across different government agencies and stakeholders.

Overall, non-motorized transport options, smart traffic management systems, and a comprehensive public transportation system are the top-ranking solutions based on their potential impact, feasibility, and sustainability. However, a combination of multiple solutions may be necessary to address the complex challenges of urban transportation effectively.

We can see that the chain came up with several different well-thought solutions to the problem, making sure that each solution is ranked, taking into consideration the key aspects provided. Additionally, it has identified the links between the different plans. 

Real ToT Usage Example: Tree of Attacks  

In the context of the "Tree of Thoughts" (ToT) prompting technique, the "Tree of Attacks: Jailbreaking Black-Box LLMs Automatically" paper, by Mehrotra Et Al., exemplifies a successful application of ToT principles to enhance security against adversarial attacks on large language models (LLMs). By leveraging ToT's methodology of exploring multiple reasoning paths, the paper demonstrates a novel framework for systematically generating and assessing potential jailbreak scenarios. This approach mirrors ToT's decision-making process by iteratively refining prompts to navigate through the complex landscape of possible attacks efficiently. The success of this application not only showcases ToT's versatility beyond conventional problem-solving tasks but also highlights its potential to significantly contribute to the development of more robust and secure AI systems.  

Figure 6  
Illustration of the four steps of Tree of Attacks with Pruning (TAP) and the use of the three LLMs (attacker, evaluator, and target) in each of the steps. Obtained from arXiv:2312.02119  

Final considerations  

When utilizing an API, charges are incurred based on the number of tokens or characters processed and generated by the model. Consequently, employing numerous few-shot exemplars in the prompt can significantly increase the input token count, leading to higher API usage costs. Given that the defined chain prompts the model multiple times, it’s worth testing simple calls first, and then applying a chained ToT technique if necessary.   

  Additionally, it’s possible to create a ToT prompt in a single call using a prompt like the following, where the 4 sections of the ToT technique are combined:  

 Imagine three different experts are answering this question.  

They will brainstorm the answer step by step reasoning carefully and taking all facts into consideration.  

All experts will write down 1 step of their thinking, then share it with the group.  

They will each critique their response, and the all the responses of others.  

They will check their answer based on science and the laws of physics. Then all experts will go on to the next step and write down this step of their thinking.  

They will keep going through steps until they reach their conclusion taking into account the thoughts of the other experts If at any time they realize that there is a flaw in their logic they will backtrack to where that flaw occurred.  

If any expert realizes they're wrong at any point then they acknowledges this and start another train of thought.  

Each expert will assign a likelihood of their current assertion being correct Continue until the experts agree on the single most likely location.  

The question is...  

  

This method might be less powerful than the chained approach, since the model must process a single longer context call, instead of multiple short context calls.

Conclusion  

Advances in prompting techniques have dramatically broadened the range of problems that can be tackled using large language models (LLMs). However, most prompting techniques are limited by the inherent nature of autoregressive language generation, often adhering to a left-to-right approach that lacks strategic planning and opportunities for exploring alternative solutions. ToT prompting addresses this limitation by conceptualizing the problem-solving process as a tree of intermediate steps, each of which can be independently explored and evaluated using established algorithms and heuristics. The fundamental concept of ToT prompting is inherently versatile and can be adapted to various problem domains.   

In exploring the Tree of Thoughts prompting technique, we've just scratched the surface of what's possible when we harness the power of generative AI. Whether it's enhancing decision-making processes, automating operations, or unlocking new levels of creativity in your marketing strategies, Kmeleon's team of experts is here to guide you through every step of the journey. Visit us at www.kmeleon.tech to learn more and start your path towards a complete Gen AI evolution.  

References

Sebastian Tafoya

AI Scientist at Kmeleon - Deep Learning Expert - Data Architect

Previous

LLM Tool Review: LangSmith - Streamline Gen AI Development at Scale
Next

Nvidia’s Chat With RTX Tool