Autonomous Tree-search Ability of Large Language Models
Zheyu Zhang Zhuorui Ye Yikang Shen Chuang Gan
Large Language Models have excelled in remarkable reasoning capabilities with
advanced prompting techniques, but they fall short on tasks that require
exploration, strategic foresight, and sequential decision-making. Recent works
propose to utilize external programs to define search logic, such that LLMs can
perform passive tree search to solve more challenging reasoning tasks. Though
impressive results have been achieved, there are several fundamental
limitations of these approaches. First, passive tree searches are not efficient
as they usually require multiple rounds of LLM API calls to solve one single
problem. Moreover, passive search methods are not flexible since they need
task-specific program designs. Then a natural question arises: can we maintain
the tree-search capability of LLMs without the aid of external programs, and
can still generate responses that clearly demonstrate the process of a
tree-structure search? To this end, we propose a new concept called autonomous
tree-search ability of LLM, which can automatically generate a response
containing search trajectories for the correct answer. Concretely, we perform
search trajectories using capable LLM API via a fixed system prompt, allowing
them to perform autonomous tree-search (ATS) right out of the box. Experiments
on 4 puzzle games demonstrate our method can achieve huge improvements. The
ATS-BFS method outperforms the Chain of Thought approach by achieving an
average accuracy improvement of 33%. Compared to Tree of Thoughts, it requires
65.6% or 47.7% less GPT-api cost to attain a comparable level of accuracy.
Moreover, we have collected data using the ATS prompt method and fine-tuned
LLaMA. This approach yield a greater improvement compared to the ones
fine-tuned on CoT data. Specifically, it outperforms CoT-tuned LLaMAs by an
average of 40.6% and 38.5% for LLaMA2-7B and LLaMA2-13B, respectively.