In this paper, we introduce the Tree-of-Thought (ToT) framework, a novel approach aimed at improving the problem-solving capabilities of auto-regressive
large language models (LLMs). The ToT technique is inspired by the human
mind’s approach for solving complex reasoning tasks through trial and error. In
this process, the human mind explores the solution space through a tree-like
thought process, allowing for backtracking when necessary. To implement ToT
as a software system, we augment an LLM with additional modules including a
prompter agent, a checker module, a memory module, and a ToT controller. In
order to solve a given problem, these modules engage in a multi-round conversation with the LLM. The memory module records the conversation and state
history of the problem solving process, which allows the system to backtrack
to the previous steps of the thought-process and explore other directions from
there. To verify the effectiveness of the proposed technique, we implemented
a ToT-based solver for the Sudoku Puzzle. Experimental results show that the
ToT framework can significantly increase the success rate of Sudoku puzzle solving.
