# On the Empirical Complexity of Reasoning and Planning in LLMs

arXiv: https://arxiv.org/abs/2404.11041 · HTML: https://mlsanity.com/paper/2404.11041/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Placed in Prompting and chain-of-thought reasoning, one of 17 directions in LLM reasoning.
- Builds on 25 of its 93 references that are in the map.
- First posted on arXiv 17 Apr 2024.

## Placed in

- LLM reasoning / [Prompting and chain-of-thought reasoning](https://mlsanity.com/lr/prompting-and-chain-of-thought-reasoning/)

## Builds on (most cited first, 25 of 25)

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [LoRA: Low-Rank Adaptation of Large Language Models](https://mlsanity.com/paper/2106.09685/) (2021)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Large Language Models are Zero-Shot Reasoners](https://mlsanity.com/paper/2205.11916/) (2022)
- [Inner Monologue: Embodied Reasoning through Planning with Language Models](https://mlsanity.com/paper/2207.05608/) (2022)
- [Program of Thoughts Prompting: Disentangling Computation from Reasoning for Numerical Reasoning Tasks](https://mlsanity.com/paper/2211.12588/) (2022)
- [Language Models as Zero-Shot Planners: Extracting Actionable Knowledge for Embodied Agents](https://mlsanity.com/paper/2201.07207/) (2022)
- [Reasoning with Language Model is Planning with World Model](https://mlsanity.com/paper/2305.14992/) (2023)
- [Large Language Models](https://mlsanity.com/paper/2307.05782/) (2023)
- [Faith and Fate: Limits of Transformers on Compositionality](https://mlsanity.com/paper/2305.18654/) (2023)
- [Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers](https://mlsanity.com/paper/1811.04918/) (2018)
- [On the Planning Abilities of Large Language Models : A Critical Investigation](https://mlsanity.com/paper/2305.15771/) (2023)
- [Alphazero-like Tree-Search can Guide Large Language Model Decoding and Training](https://mlsanity.com/paper/2309.17179/) (2023)
- [Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspective](https://mlsanity.com/paper/2305.15408/) (2023)
- [Large Language Models as Commonsense Knowledge for Large-Scale Task Planning](https://mlsanity.com/paper/2305.14078/) (2023)
- [Self-Evaluation Guided Beam Search for Reasoning](https://mlsanity.com/paper/2305.00633/) (2023)
- [Thinking Like Transformers](https://mlsanity.com/paper/2106.06981/) (2021)
- [Planning with Large Language Models for Code Generation](https://mlsanity.com/paper/2303.05510/) (2023)
- [What Can Neural Networks Reason About?](https://mlsanity.com/paper/1905.13211/) (2019)
- [Why think step by step? Reasoning emerges from the locality of experience](https://mlsanity.com/paper/2304.03843/) (2023)
- [Everything of Thoughts: Defying the Law of Penrose Triangle for Thought Generation](https://mlsanity.com/paper/2311.04254/) (2023)
- [Understanding Reasoning Ability of Language Models From the Perspective of Reasoning Paths Aggregation](https://mlsanity.com/paper/2402.03268/) (2024)
- [What they do when in doubt: a study of inductive biases in seq2seq learners](https://mlsanity.com/paper/2006.14953/) (2020)

## Built on by (most cited first, 6 of 6)

- [To CoT or not to CoT? Chain-of-thought helps mainly on math and symbolic reasoning](https://mlsanity.com/paper/2409.12183/) (2024)
- [Evaluating Step-by-step Reasoning Traces: A Survey](https://mlsanity.com/paper/2502.12289/) (2025)
- [TextAtari: 100K Frames Game Playing with Language Agents](https://mlsanity.com/paper/2506.04098/) (2025)
- [Language Models, Graph Searching, and Supervision Adulteration: When More Supervision is Less and How to Make More More](https://mlsanity.com/paper/2503.10542/) (2025)
- [Complexity Agnostic Recursive Decomposition of Thoughts](https://mlsanity.com/paper/2601.04210/) (2025)
- [The Dog the Cat Chased Stumped the Model: Measuring When Language Models Abandon Structure for Shortcuts](https://mlsanity.com/paper/2510.20543/) (2025)

## Abstract (arXiv)

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 6 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, and (ii) for computationally hard reasoning tasks, the more sophisticated tree structure of ToT outperforms the linear structure of CoT. These findings provide useful guidelines for the use of LLM in solving reasoning tasks in practice.