While language models (LMs) offer significant capability in zero-shot
reasoning tasks across a wide range of domains, they do not perform
satisfactorily in problems which requires multi-step reasoning. Previous
approaches to mitigate this involves breaking a larger, multi-step task into
sub-tasks and asking the language model to generate proposals ("thoughts") for
each sub-task and using exhaustive planning approaches such as DFS to compose a
solution. In this work, we leverage this idea to introduce two new
contributions: first, we formalize a planning-based approach to perform
multi-step problem solving with LMs via Partially Observable Markov Decision
Processes (POMDPs), with the LM's own reflections about the value of a state
used as a search heuristic; second, leveraging the online POMDP solver POMCP,
we demonstrate a superior success rate of 89.4% on the Game of 24 task as
compared to existing approaches while also offering better anytime performance
characteristics than fixed tree-search which is used previously. Taken
together, these contributions allow modern LMs to decompose and solve
larger-scale reasoning tasks more effectively.

在本研究中，我们使用基于规划的方法结合部分可观察马尔可夫决策过程（POMDPs）来解决多步骤的问题，并通过 POMCP 在线求解器在 24 点游戏任务上展现出了 89.4% 的优越成功率，同时也提供了比之前使用的固定树搜索更好的任意时间性能。