Policy-Guided Search on Tree-of-Thoughts for Efficient Problem Solving with Bounded Language Model Queries (Extended Abstract)

Abstract

Recent studies explored integrating search algorithms with Language Models (LMs) to perform look-ahead on the "Tree-of-Thoughts" (ToT), improving performance on problem-solving tasks. However, these search algorithms overlook the computational costs of LM inference under constrained budgets. We adapt Levin Tree Search (LTS) (Orseau et al. 2018) to ToT (Yao et al. 2023), leveraging LM probabilities as a policy to guide tree exploration without additional evaluation queries. We extend theoretical results of LTS by showing that, for ToT (a pruned tree), LTS guarantees a bound on states expanded and thoughts generated. Empirical evaluation under fixed LM query budgets demonstrates that LTS consistently achieves comparable or higher accuracy than baseline search algorithms across three domains (Blocksworld, PrOntoQA, Array Sorting) and four distinct LMs.