Tree of thoughts(ToT): A step change in AI Reasoning and Logic

Language models have become increasingly indispensable for solving a wide array of problems, yet they are bound by token-level, left-to-right decision-making processes during inference. This limitation becomes evident in tasks that demand exploration, strategic foresight, or situations where initial decisions hold immense significance. In response to this challenge, DeepMind researchers have introduced a groundbreaking framework for language model inference known as the "Tree of Thoughts" (ToT). This framework builds upon the well-known "Chain of Thought" approach to prompt language models, but it offers a substantial advancement by enabling exploration through coherent units of text, referred to as "thoughts," which serve as intermediary steps in the problem-solving process.

The Tree of Thoughts introduces a paradigm shift that allows for multi-step analysis akin to the Chain of Thought approach but with a remarkable difference. It permits multiple comparisons involving various multi-step analyses. This innovation increases the options available after each step, empowering the system to revert to earlier steps or even the initial one to seek fresh insights. Ultimately, it identifies the best option after multiple searches through different analytical possibilities.

Tree of Thoughts (ToT) empowers Language Models (LMs) to engage in deliberate decision-making. It achieves this by considering multiple distinct reasoning paths and evaluating choices to determine the next course of action. It also possesses the capability to look ahead or backtrack when necessary, making global decisions that significantly enhance problem-solving abilities. Experimental results showcase ToT's prowess in enhancing language models' capabilities across three novel tasks that demand non-trivial planning or search: Game of 24, Creative Writing, and Mini Crosswords.

For instance, in the Game of 24, while GPT-4 with chain-of-thought prompting managed to solve only 4% of tasks, our approach achieved an impressive success rate of 74%.

Tree of Thought represents a significant evolution beyond conventional input-output, chain of thought, and self-consistency with chain of thought approaches. It extends existing planning frameworks by concurrently considering multiple potentially viable plans at each step of problem-solving, proceeding with the most promising ones. The integration of thought sampling and value feedback seamlessly blends planning and decision-making mechanisms, facilitating efficient exploration within a solution tree. Traditional decision-making procedures typically entail training specialized reward and policy models, as seen in reinforcement learning. In contrast, we utilize the language model itself to provide value estimates for decision-making.

The Tree-of-Thought formulation exhibits remarkable versatility and excels in handling challenging tasks where GPT-4 struggles with standard prompts, achieving significantly higher accuracy.

It's worth noting that deliberate search, as exemplified by ToT, may not be essential for many existing tasks at which GPT-4 already excels. This work, in its initial stages, delves into three relatively simple tasks that challenge GPT-4 and call for enhanced search and planning abilities integrated with Language Models. As Language Models find application in more real-world decision-making scenarios (e.g., coding, data analysis, robotics), complex tasks may emerge, offering opportunities to explore these research questions further. Additionally, search methods like ToT may demand more resources (e.g., GPT-4 API cost) compared to sampling methods to improve task performance. However, the modular flexibility of ToT allows users to customize performance-cost trade-offs to suit their specific needs."