On the Empirical Complexity of Reasoning and Planning in LLM s (2024)

Abstract: Chain-of-thought (CoT), tree-of-thought (ToT), and related techniques work surprisingly well in practice for some complex reasoning tasks with Large Language Models (LLMs), but why? This work seeks the underlying reasons by conducting experimental case studies and linking the performance benefits to well-established sample and computational complexity principles in machine learning. We experimented with six reasoning tasks, ranging from grade school math, air travel planning, ..., to Blocksworld. The results suggest that (i) both CoT and ToT benefit significantly from task decomposition, which breaks a complex reasoning task into a sequence of steps with low sample complexity and explicitly outlines the reasoning structure; (ii) for computationally hard reasoning tasks, the more sophisticated tree structure of ToT outperforms the linear structure of CoT; (iii) explicitly annotating important variables is important for good performance. These findings provide useful guidelines for using LLM in solving reasoning tasks in practice.

## introduction reasoning and planning tasks are often challenging due to their inherently multi-step processes. compared with the direct approach that prompts the model to provide immediate answers, large language models (llms) showed surprising results on reasoning problems when they were asked to explain their reasoning step-by-step through a chainof-thought (cot) @xcite before providing their answers. this was followed by improvements of the tree-of-thought (tot) @xcite , combining llms with a search algorithm to structure reasoning steps into a tree and selecting promising next steps by self-evaluation. other variants include cot with self-consistency (cot-sc) @xcite ## related work llms have shown significant progress in tackling reasoning and planning problems. initial studies @xcite @xcite @xcite unveiled various prompting techniques that enable llms to demonstrate reasoning processes step by step, thereby substantially boosting their reasoning abilities. this approach has been swiftly adapted to address everyday planning issues @xcite @xcite @xcite . subsequent research has integrated llms with diverse search algorithms, further enhancing their capability to solve complex reasoning and planning challenges @xcite @xcite @xcite @xcite . several works explore why cot improves performance. @xcite investigates how cot enhances model capacity; @xcite and @xcite examine the training data distribution that enables cot to excel; dziri et al. (2023) discusses cot's limitations in compositional reasoning. our work takes a different approach, we explore principles that guide llm behavior across various reasoning frameworks, and provide insights into selecting appropriate strategies for different tasks. while @xcite discusses the sample complexity of llm planning, they overlook the computational implications. ## analysis of llm reasoning methods we aim to analyze llm reasoning methods from the sample and computational complexity perspective in machine learning. our goal is to understand the complexity of problems using simple representations. however, analyzing llm learning with transformer architecture is challenging, and the effects of pre-training, which we do not control, are present throughout. instead, we empirically observe whether our analysis reflects the practical behaviour of llms and whether the insights from our analysis are practically useful. specifically, when our analysis suggests that a particular method is preferred, we examine whether it is indeed preferred empirically. ## conclusion this paper provides a detailed empirical study to understand the effectiveness of cot and tot reasoning in planning and reasoning tasks using notions of sample and computational complexity in machine learning. we view cot and tot as decomposition methods for the underlying problem and study the complexity of the component predictors in the decomposed problems. our study finds that when the solution can be decomposed as a chain of reasoning steps where predicting the next step is not difficult, explicitly demonstrating the reasoning chain during learning can be helpful. leaving out important variables for deciding the next reasoning step instead of making all relevant variables explicit in the demonstrations will make learning more difficult. finally, when algorithmic analysis indicates that predicting the next reasoning step in a cot is computationally hard, a tot structure can be helpful.