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.

大型语言模型在高级提示技术方面具有出色的推理能力，但在需要探索、战略前瞻和序贯决策的任务上存在不足。最近的研究通过利用外部程序定义搜索逻辑，使 LLMs 能够执行被动树搜索以解决更具挑战性的推理任务。我们提出了一种名为 LLM 的自主树搜索能力的新概念，它可以自动生成包含正确答案的搜索轨迹的响应。在 4 个益智游戏上的实验表明，我们的方法可以取得巨大的改进。与先前的方法相比，ATS-BFS 方法在准确性上提高了 33％，而 GPT API 成本降低了 65.6% 或 47.7%。此外，我们使用 ATS 提示方法收集数据并对 LLaMA 进行微调，在 LLaMA2-7B 和 LLaMA2-13B 上相对于 CoT-tuned LLaMAs 提高了 40.6% 和 38.5%。