Large Language Models (LLMs) work surprisingly well for some complex
reasoning problems via chain-of-thought (CoT) or tree-of-thought (ToT), but the
underlying reasons remain unclear. We seek to understand the performance of
these methods by conducting experimental case studies and linking the outcomes
to sample and computational complexity in machine learning. We found that if
problems can be decomposed into a sequence of reasoning steps and learning to
predict the next step has a low sample and computational complexity, explicitly
outlining the reasoning chain with all necessary information for predicting the
next step may improve performance. Conversely, for problems where predicting
the next step is computationally hard, adopting ToT may yield better reasoning
outcomes than attempting to formulate a short reasoning chain.

通过进行实验案例研究并将结果与机器学习中的样本和计算复杂性联系起来，我们发现如果问题可以分解成一系列推理步骤，并且学习预测下一步具有较低的样本和计算复杂性，明确列出推理链与预测下一步所需的所有必要信息可能会改善性能，相反，对于计算复杂的问题，采用树状推理可能比尝试形成简短的推理链更好地产生推理结果。