On the Empirical Complexity of Reasoning and Planning in LLMs
Liwei Kang Zirui Zhao David Hsu Wee Sun Lee
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.