# Parsel: Algorithmic Reasoning with Language Models by Composing Decompositions

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

## Key facts

- Cited by 64 papers in the map (data through 14 Oct 2026).
- Placed in Reasoning benchmarks and evaluation, one of 17 directions in LLM reasoning.
- Builds on 49 of its 76 references that are in the map.
- First posted on arXiv 20 Dec 2022.

## Placed in

- LLM reasoning / [Reasoning benchmarks and evaluation](https://mlsanity.com/lr/reasoning-benchmarks-and-evaluation/)

## Builds on (most cited first, 30 of 49)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [Large Language Models are Zero-Shot Reasoners](https://mlsanity.com/paper/2205.11916/) (2022)
- [Program Synthesis with Large Language Models](https://mlsanity.com/paper/2108.07732/) (2021)
- [Do As I Can, Not As I Say: Grounding Language in Robotic Affordances](https://mlsanity.com/paper/2204.01691/) (2022)
- [Competition-Level Code Generation with AlphaCode](https://mlsanity.com/paper/2203.07814/) (2022)
- [Least-to-Most Prompting Enables Complex Reasoning in Large Language Models](https://mlsanity.com/paper/2205.10625/) (2022)
- [Language Models as Zero-Shot Planners: Extracting Actionable Knowledge for Embodied Agents](https://mlsanity.com/paper/2201.07207/) (2022)
- [STaR: Bootstrapping Reasoning With Reasoning](https://mlsanity.com/paper/2203.14465/) (2022)
- [Measuring Coding Challenge Competence With APPS](https://mlsanity.com/paper/2105.09938/) (2021)
- [Solving math word problems with process- and outcome-based feedback](https://mlsanity.com/paper/2211.14275/) (2022)
- [GLaM: Efficient Scaling of Language Models with Mixture-of-Experts](https://mlsanity.com/paper/2112.06905/) (2021)
- [Show Your Work: Scratchpads for Intermediate Computation with Language Models](https://mlsanity.com/paper/2112.00114/) (2021)
- [CodeGen: An Open Large Language Model for Code with Multi-Turn Program Synthesis](https://mlsanity.com/paper/2203.13474/) (2022)
- [ProgPrompt: Generating Situated Robot Task Plans using Large Language Models](https://mlsanity.com/paper/2209.11302/) (2022)
- [VirtualHome: Simulating Household Activities via Programs](https://mlsanity.com/paper/1806.07011/) (2018)
- [MiniF2F: a cross-system benchmark for formal Olympiad-level mathematics](https://mlsanity.com/paper/2109.00110/) (2021)
- [Generative Language Modeling for Automated Theorem Proving](https://mlsanity.com/paper/2009.03393/) (2020)
- [CodeT: Code Generation with Generated Tests](https://mlsanity.com/paper/2207.10397/) (2022)
- [Explain Yourself! Leveraging Language Models for Commonsense Reasoning](https://mlsanity.com/paper/1906.02361/) (2019)
- [A Systematic Evaluation of Large Language Models of Code](https://mlsanity.com/paper/2202.13169/) (2022)
- [Draft, Sketch, and Prove: Guiding Formal Theorem Provers with Informal Proofs](https://mlsanity.com/paper/2210.12283/) (2022)
- [Thinking Fast and Slow with Deep Learning and Tree Search](https://mlsanity.com/paper/1705.08439/) (2017)
- [Can language models learn from explanations in context?](https://mlsanity.com/paper/2204.02329/) (2022)
- [Binding Language Models in Symbolic Languages](https://mlsanity.com/paper/2210.02875/) (2022)
- [Exploring Length Generalization in Large Language Models](https://mlsanity.com/paper/2207.04901/) (2022)
- [Do Users Write More Insecure Code with AI Assistants?](https://mlsanity.com/paper/2211.03622/) (2022)

## Built on by (most cited first, 30 of 64)

- [SWE-agent: Agent-Computer Interfaces Enable Automated Software Engineering](https://mlsanity.com/paper/2405.15793/) (2024)
- [Quiet-STaR: Language Models Can Teach Themselves to Think Before Speaking](https://mlsanity.com/paper/2403.09629/) (2024)
- [Large Language Model-Based Agents for Software Engineering: A Survey](https://mlsanity.com/paper/2409.02977/) (2024)
- [Self-Taught Optimizer (STOP): Recursively Self-Improving Code Generation](https://mlsanity.com/paper/2310.02304/) (2023)
- [Cut the Crap: An Economical Communication Pipeline for LLM-based Multi-Agent Systems](https://mlsanity.com/paper/2410.02506/) (2024)
- [Hypothesis Search: Inductive Reasoning with Language Models](https://mlsanity.com/paper/2309.05660/) (2023)
- [CodeR: Issue Resolving with Multi-Agent and Task Graphs](https://mlsanity.com/paper/2406.01304/) (2024)
- [Symbolic Regression with a Learned Concept Library](https://mlsanity.com/paper/2409.09359/) (2024)
- [A Self-Improving Coding Agent](https://mlsanity.com/paper/2504.15228/) (2025)
- [HyperAgent: Generalist Software Engineering Agents to Solve Coding Tasks at Scale](https://mlsanity.com/paper/2409.16299/) (2024)
- [Code Repair with LLMs gives an Exploration-Exploitation Tradeoff](https://mlsanity.com/paper/2405.17503/) (2024)
- [Can LLM Graph Reasoning Generalize beyond Pattern Memorization?](https://mlsanity.com/paper/2406.15992/) (2024)
- [From Code to Correctness: Closing the Last Mile of Code Generation with Hierarchical Debugging](https://mlsanity.com/paper/2410.01215/) (2024)
- [On the Prospects of Incorporating Large Language Models (LLMs) in Automated Planning and Scheduling (APS)](https://mlsanity.com/paper/2401.02500/) (2024)
- [Generating Code World Models with Large Language Models Guided by Monte Carlo Tree Search](https://mlsanity.com/paper/2405.15383/) (2024)
- [Repo2Run: Automated Building Executable Environment for Code Repository at Scale](https://mlsanity.com/paper/2502.13681/) (2025)
- [What Makes Large Language Models Reason in (Multi-Turn) Code Generation?](https://mlsanity.com/paper/2410.08105/) (2024)
- [AI capabilities can be significantly improved without expensive retraining](https://mlsanity.com/paper/2312.07413/) (2023)
- [CodeS: Natural Language to Code Repository via Multi-Layer Sketch](https://mlsanity.com/paper/2403.16443/) (2024)
- [Is Programming by Example solved by LLMs?](https://mlsanity.com/paper/2406.08316/) (2024)
- [Exposing Limitations of Language Model Agents in Sequential-Task Compositions on the Web](https://mlsanity.com/paper/2311.18751/) (2023)
- [Brains vs. Bytes: Evaluating LLM Proficiency in Olympiad Mathematics](https://mlsanity.com/paper/2504.01995/) (2025)
- [Large Language Model-based Data Science Agent: A Survey](https://mlsanity.com/paper/2508.02744/) (2025)
- [Think Outside the Code: Brainstorming Boosts Large Language Models in Code Generation](https://mlsanity.com/paper/2305.10679/) (2023)
- [Divide-and-Conquer Meets Consensus: Unleashing the Power of Functions in Code Generation](https://mlsanity.com/paper/2405.20092/) (2024)
- [Towards Rationality in Language and Multimodal Agents: A Survey](https://mlsanity.com/paper/2406.00252/) (2024)
- [Syzygy: Dual Code-Test C to (safe) Rust Translation using LLMs and Dynamic Analysis](https://mlsanity.com/paper/2412.14234/) (2024)
- [Evaluating statistical language models as pragmatic reasoners](https://mlsanity.com/paper/2305.01020/) (2023)
- [Learning Task Decomposition to Assist Humans in Competitive Programming](https://mlsanity.com/paper/2406.04604/) (2024)
- [NeSyCoCo: A Neuro-Symbolic Concept Composer for Compositional Generalization](https://mlsanity.com/paper/2412.15588/) (2024)

## Abstract (arXiv)

Despite recent success in large language model (LLM) reasoning, LLMs struggle with hierarchical multi-step reasoning tasks like generating complex programs. For these tasks, humans often start with a high-level algorithmic design and implement each part gradually. We introduce Parsel, a framework enabling automatic implementation and validation of complex algorithms with code LLMs. With Parsel, we automatically decompose algorithmic tasks into hierarchical natural language function descriptions and then search over combinations of possible function implementations using tests. We show that Parsel can be used across domains requiring hierarchical reasoning, including program synthesis and robotic planning. We find that, using Parsel, LLMs solve more competition-level problems in the APPS dataset, resulting in pass rates over 75% higher than prior results from directly sampling AlphaCode and Codex, while often using a smaller sample budget. Moreover, with automatically generated tests, we find that Parsel can improve the state-of-the-art pass@1 performance on HumanEval from 67% to 85%. We also find that LLM-generated robotic plans using Parsel are more than twice as likely to be considered accurate than directly generated plans. Lastly, we explore how Parsel addresses LLM limitations and discuss how Parsel may be useful for human programmers. We release our code at https://github.com/ezelikman/parsel