Based on the repo and paper “Tree of Thoughts: Deliberate Problem Solving with Large Language Models”: https://arxiv.org/abs/2305.10601
Language models have proven effective problem solvers across a wide range of problems in many domains but are limited by a token-level decision-making process during inference. Because of this, initial decisions play a pivotal role and early mistakes can prevent success in later decision making. Tree of Thoughts (ToT) is a decision making framework introduced in (1) that generalizes Chain of Thought prompting (2), enabling language models to explore branching possibilities with coherent units of text (thoughts) as an intermediate step. ToT allows LMs to perform deliberate decision making by considering multiple different reasoning paths and self-evaluating choices to decide the next course of action, as well as looking ahead or backtracking when necessary to make global choices. In this project, we implement the Tree of Thoughts framework in Wolfram language for the first time, reproduce a solution for the game of 24, and begin to explore the use of this framework for more general problem solving in the context of coding challenges.

Initialization


Alternate Implementation with ServiceConnect


Game of 24

Game of 24 is a mathematical reasoning challenge, where the goal is to use 4 numbers and basic arithmetic operations (+-*/) to obtain 24.
For example, given input “4 9 10 13”, a solution output could be “(10-4)*(13-9)=24”.
​
In order to approach Game of 24 within the Tree of Thoughts framework we must first break it down into steps. A natural way to do this is to take two numbers at a time and apply an arithmetic operation
13 - 10 = 3
After this operation we have used two of our numbers and have two left (4 and 9) in addition to our result (3) so we have:
Step 1: 13 - 10 = 3 (left: 4 9 3)
After two more steps we can reach the solution:
Step 2: 9 - 3 = 6 (left: 4 6)
Step 3: 4 * 6 = 24 (left: 24)
Now that we have reached 24 we can construct our solution:
Answer: 4 * (9 - (13 - 10)) = 24
​
Before we proceed toward our solution with Tree of Thoughts, we provide some motivation as to why ToT or similar frameworks are very helpful for problem solving with LLMs.
​
First let’s look at how ChatGPT, in this case GPT-4 approaches solving this problem. Using the steps we provided above we will provide a 1-shot chain of thought (CoT) reasoning prompt using a handy function built into Wolfram Language as of version 13.3, LLMFunction (3).
​
​Note: in order to run this notebook you must have an OpenAI API key (which you can set up here https://openai.com/blog/openai-api ). After getting your API key you can set it in your Wolfram environment using:
SystemCredentials[OPENAI_API_KEY] = "your_key"

Attempting to Solve Game of 24 with Chain of Thought Prompting

In[]:=
cot1Shot=LLMFunction["Use numbers and basic arithmetic operations (+ - * /) to obtain 24.Each step, you are only allowed to choose two of the remaining numbers to obtain a new number. You must use the four numbers in the input and only those numbers in your answer.Input: 4 4 6 8Steps:4 + 8 = 12 (left: 4 6 12)6 - 4 = 2 (left: 2 12)2 * 12 = 24 (left: 24)Answer: (6 - 4) * (4 + 8) = 24Input: `input`",LLMEvaluator->llmParams];
In[]:=
cot1ShotResponse=cot1Shot[<|"input"->"4 9 10 13"|>]
Out[]=
Steps:13 - 9 = 4 (left: 4 4 10)4 * 4 = 16 (left: 16 10)16 + 10 = 26 (left: 26)Answer: (13 - 9) * 4 + 10 = 26Note: It seems there's no way to obtain 24 with these numbers using basic arithmetic operations.
With a 1-shot prompt GPT-4 gets close to a solution obtaining a result of 26 and recognizing its mistake, states (falsely) that there is no way to obtain 24 with these numbers.
​
We can improve the performance with this approach by using more examples. Below we provide a 5-shot chain of thought prompt:
In[]:=
cot5Shot=LLMFunction["Use numbers and basic arithmetic operations (+ - * /) to obtain 24. Each step, you are only allowed to choose two of the remaining numbers to obtain a new number. You must use the four numbers in the input and only those numbers in your answer.Input: 4 4 6 8Steps:4 + 8 = 12 (left: 4 6 12)6 - 4 = 2 (left: 2 12)2 * 12 = 24 (left: 24)Answer: (6 - 4) * (4 + 8) = 24Input: 2 9 10 12Steps:12 * 2 = 24 (left: 9 10 24)10 - 9 = 1 (left: 1 24)24 * 1 = 24 (left: 24)Answer: (12 * 2) * (10 - 9) = 24Input: 4 9 10 13Steps:13 - 10 = 3 (left: 3 4 9)9 - 3 = 6 (left: 4 6)4 * 6 = 24 (left: 24)Answer: 4 * (9 - (13 - 10)) = 24Input: 1 4 8 8Steps:8 / 4 = 2 (left: 1 2 8)1 + 2 = 3 (left: 3 8)3 * 8 = 24 (left: 24)Answer: (1 + 8 / 4) * 8 = 24Input: 5 5 5 9Steps:5 + 5 = 10 (left: 5 9 10)10 + 5 = 15 (left: 9 15)15 + 9 = 24 (left: 24)Answer: ((5 + 5) + 5) + 9 = 24Input: `input`",LLMEvaluator->llmParams];
In[]:=
cot5ShotResponse=cot5Shot[<|"input"->"4 9 10 13"|>]
Out[]=
Steps:13 - 10 = 3 (left: 3 4 9)9 - 3 = 6 (left: 4 6)4 * 6 = 24 (left: 24)Answer: 4 * (9 - (13 - 10)) = 24
In the 5-shot chain of thought case, GPT-4 provides a valid solution to the problem for the given input.
With more difficult inputs, GPT-4 is unable to find a solution with the 5-shot prompt.
In[]:=
cot5ShotResponse=cot5Shot[<|"input"->"3 4 5 13"|>]
Out[]=
Steps:13 - 4 = 9 (left: 3 5 9)9 - 5 = 4 (left: 3 4)3 * 4 = 12 (left: 12)12 * 2 = 24 (left: 24)Answer: 2 * (3 * (13 - 4 - 5)) = 24

Generate Thoughts with the Propose Prompt (1-shot learning example)

Tree of Thoughts improves language models’ problem solving ability by enabling them to explore a branching web of possible decisions. At any given step in our problem solving process we consider several options, evaluate them, and keep the best options in our set of options. The first step for any given input (either the task input or numbers left after an operation) is to generate a list of proposed options we can consider.
In[]:=
generateProposals=LLMFunction["Input: 2 8 8 14Possible next steps:2 + 8 = 10 (left: 8 10 14)8 / 2 = 4 (left: 4 8 14)14 + 2 = 16 (left: 8 8 16)2 * 8 = 16 (left: 8 14 16)8 - 2 = 6 (left: 6 8 14)14 - 8 = 6 (left: 2 6 8)14 / 2 = 7 (left: 7 8 8)14 - 2 = 12 (left: 8 8 12)Input: `input`Possible next steps:",StringSplit[#,"\n"]&,LLMEvaluator->llmParams];
Now we can use this function to generate a list of options for our task input and visualize the results as a tree.
In[]:=
taskInput="4 5 6 10";​​proposals=generateProposals[<|"input"->taskInput|>]
Out[]=
{4 + 5 = 9 (left: 6 9 10),5 + 6 = 11 (left: 4 10 11),10 - 4 = 6 (left: 5 6 6),6 + 4 = 10 (left: 5 10 10),10 / 5 = 2 (left: 2 4 6),6 - 5 = 1 (left: 1 4 10),10 - 6 = 4 (left: 4 4 5),5 * 4 = 20 (left: 6 10 20) ,10 / 4 = 2.5 (left: 2.5 5 6)}
In[]:=
Tree[StringTemplate["input: `input`"][<|"input"->taskInput|>],StringReplace[#,"("->"\n("]&/@proposals,TreeLayout->Left]
Out[]=

Evaluate Proposed Thoughts with Value Prompt

After we have generated a list of proposals we need to evaluate them so we can decide whether or not we should continue down a particular path of reasoning. In order to do this we use three categories which we will assign numerical values to form a rough heuristic for evaluating a particular proposal. Below we give an 8-shot prompt with varying inputs. If the numbers reach 24 we return “sure”. If they cannot reach 24 we return “impossible” and if we can get close we return “likely”. It is important to keep in mind that this is a rough heuristic and that the model may make mistakes in the evaluation that will persist later.
In[]:=
evaluateProposal=LLMFunction["Evaluate if given numbers can reach 24 (sure/likely/impossible)10 1410 + 14 = 24sure11 1211 + 12 = 2312 - 11 = 111 * 12 = 13211 / 12 = 0.91impossible4 4 104 + 4 + 10 = 8 + 10 = 184 * 10 - 4 = 40 - 4 = 36(10 - 4) * 4 = 6 * 4 = 24sure4 9 119 + 11 + 4 = 20 + 4 = 24sure5 7 85 + 7 + 8 = 12 + 8 = 20(8 - 5) * 7 = 3 * 7 = 21I cannot obtain 24 now, but numbers are within a reasonable rangelikely5 6 65 + 6 + 6 = 17(6 - 5) * 6 = 1 * 6 = 6I cannot obtain 24 now, but numbers are within a reasonable rangelikely10 10 1110 + 10 + 11 = 31(11 - 10) * 10 = 1010 10 10 are all too bigimpossible1 3 31 * 3 * 3 = 9(1 + 3) * 3 = 121 3 3 are all too smallimpossible`input`",LLMEvaluator->llmParams];
In order to evaluate a thought, we look at the numbers that remain after performing an operation.

Helper function to get left numbers from thoughts

Evaluate proposal

Helper function to get value from evaluated thoughts

We assign to each category a numerical value. We heavily weight cases where the model is “sure” to avoid missing paths that can reach a solution.
For each of our proposed steps we get a value. We perform n=3 evaluations for each proposal and sum the results
Here we visualize the results after generating proposals for the first step and evaluating.

Select Top Proposals and Repeat The Process

The next step is to select the top proposals based on value and generate new proposals for each of these with the remaining numbers as input. Here we select the top 5 proposals from the previous step.
Here is the pruned tree with the top 5 proposals.
Here we visualize a sub-tree for a select path in our tree.

Generate and Evaluate Answers

In order to produce a solution to the task, we must write the final equation resulting from the steps we have followed so far. We know we have reached the final step when our previous operation results in only “24” remaining i.e. our output ends in “(left: 24)”.
Finally, once we arrive at an answer to our problem, we want to make sure to evaluate it to ensure that it is indeed a valid answer.
Now we’re ready to solve Game of 24!

Solving Game of 24 with Tree of Thoughts

Our solveTask function runs iteratively for four steps generating proposals, evaluating them, taking the best

Extending to Other Problems

How can we extend the tree of thoughts methodology to other types of problems with less well defined solutions and thought spaces? We can look at using language models to solve coding challenges such as those presented in An Elementary Introduction to the Wolfram Language (4).
Below are a few selected exercises from the book.
Unlike the case of Game of 24, there is no obvious way to break down any given coding problem into a series of steps that we can use for Tree of Thoughts. One approach is to ask GPT-4 to help us break down a problem.
In this case, GPT-4 is not only able to reproduce some reasonable steps but also generates a valid answer for the problem. These steps can be used to generate a prompt that can help us solve more challenging problems.
​
In order to make our chain of thought prompt for proposals we use the above prompt to generate steps for a number of problems. We sample a subset of the steps produced and suggest the model to provide a possible next step.
Similar to the case for Game of 24 we can ask the model to evaluate a proposal, in this case asking it whether a set of steps will accomplish (sure), is reasonable (likely) or cannot produce the desired result (impossible).
In order to produce a solution to the coding challenge we ask the model to produce an answer for the problem given a series of steps.
Once we have produced an answer, we can evaluate the answer and judge whether it produced the desired result.

Conclusion

We investigated the use of the Tree of Thoughts framework to extend language models’ problem solving ability for difficult problems that require exploring a diversity of intermediate thoughts. We used the newly introduced LLMFunction capability in Wolfram Language to reproduce the ToT algorithm for the Game of 24. We visualized the results of exploring and evaluating proposals for intermediate steps in this game. We produce and visualize a solution to the game by exploring the Tree of Thoughts. Finally we begin to explore extending this framework to solving coding challenges, providing prompts that could be used toward this end.

Acknowledgment

I’d like to thank Jofre Espigule, my project mentor, for his extensive support and mentorship and helpful ideas throughout the course of my project. Thanks also to Steven Wolfram, Mads, Xerxes, Yi, Danielle, Stephanie and all the other mentors and TAs that made Wolfram Summer School 2023 possible.

References

1
.
Tree of Thoughts: Deliberate Problem Solving with Large Language Models - https://arxiv.org/abs/2305.10601
2
.
Chain-of-Thought Prompting Elicits Reasoning in Large Language Models - https://arxiv.org/abs/2201.11903
3
.
The New World of LLM Functions: Integrating LLM Technology into the Wolfram Language - https://writings.stephenwolfram.com/2023/05/the-new-world-of-llm-functions-integrating-llm-technology-into-the-wolfram-language/
4
.
An Elementary Introduction to the Wolfram Language - https://www.wolfram.com/language/elementary-introduction/3rd-ed/
5
.
Progressive-Hint Prompting Improves Reasoning in Large Language Models - https://arxiv.org/abs/2304.09797
6
.
Language Models as Zero-Shot Planners: Extracting Actionable Knowledge for Embodied Agents - https://arxiv.org/abs/2201.07207
7
.
Inner Monologue: Embodied Reasoning through Planning with Language Models - https://arxiv.org/abs/2207.05608
8
.
OpenAI GPT-4 Technical Report - https://arxiv.org/abs/2303.08774
9
.
Reflexion: Language Agents with Verbal Reinforcement Learning - https://arxiv.org/abs/2303.11366
10
.
S.A. Sloman. The empirical case for two systems of reasoning. Psychological bulletin, 119(1): 3,1996.

CITE THIS NOTEBOOK

Tree of thoughts: exploratory problem solving with LLMs​
by Rob Giometti​
Wolfram Community, STAFF PICKS, July 12, 2023
​https://community.wolfram.com/groups/-/m/t/2959295