My Notebook

Recently, I came across an interesting paper from Google DeepMind introducing the concept of Tree of Thoughts (ToT). You can read the full paper here. Unlike the traditional Chain of Thought approach, which follows a single linear reasoning path, the Tree of Thoughts framework treats problem-solving as a search through multiple possible reasoning paths. This opens up the ability to explore alternatives, evaluate them, and backtrack when necessary—bringing the strengths of classical search algorithms like A*, Beam Search, and even combinations of BFS/DFS into the world of large language models.

ToT frames any problem as a search over a tree and consists of four components:

1. Thought decomposition:
ToT leverages problem properties to design and decompose intermediate thought steps. It sets the boundaries for the thoughts that the generator produces.

2. Thought Generation:
Explore multiple candidates at each step. When generating a new thought for the current state, you generally provide the model with all previous thoughts along the path leading to the current state.

3. State evaluator:
Each path is scored by the LLM based on how promising they are. We can use the LLM as a judge here!

4. Search algorithm:
We have the top-k most promising candidates based on their evaluation scores. We can use a heap-like data structure to select these top-k candidates.

For some problems, the search space can grow exponentially which could contribute to high latency and cost due to multiple 3rd-party LLM requests. Implementing ToT reliably is a challenge in itself as there are many moving parts.

Reference: https://lnkd.in/d8WFQ8TJ