Parsel 🐍
Parsel🐍: Algorithmic Reasoning with Language Models by Composing Decompositions
Eric Zelikman Qian Huang Gabriel Poesia Noah D. Goodman Nick Haber
Parsel🐍: Algorithmic Reasoning with Language Models by Composing Decompositions
Eric Zelikman Qian Huang Gabriel Poesia Noah D. Goodman Nick Haber
|
|
 |
||
| Abstract: 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, taking hierarchical function descriptions in natural language as input. We show that Parsel can be used across domains requiring hierarchical reasoning, including program synthesis, robotic planning, and theorem proving. We show that LLMs generating Parsel solve more competition-level problems in the APPS dataset, resulting in pass rates that are over 75% higher than prior results from directly sampling AlphaCode and Codex, while often using a smaller sample budget. We also find that LLM-generated robotic plans using Parsel as an intermediate language 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. |
||
Parsel Overview
 |
||
|
Parsel overview. A human or LM writes a task decomposition in the Parsel language, which is split into its strongly-connected components (SCC), and then the Parsel compiler uses a code LM and a constraint solver to implement and compose each SCC.
|
Parsel Examples
 |
||
|
Parsel compilation examples. Examples using Parsel to compile programs for VirtualHome, Lean, and Python. Note the columns on the generated examples are only there to allow them to fit compactly -- each program implementation is one contiguous solution. Colors for Parsel code on the left are used to indicate
constraints
and
references
. All other Parsel lines shown are definitions.
|
Paper
 |
Zelikman, Huang, Poesia, Goodman, Haber (2022) Parsel 🐍: A (De-)compositional Framework for Algorithmic Reasoning with Language Models [Paper] [Code] |
Bibtex
@misc{zelikman2022parsel,
url = {https://arxiv.org/abs/2212.10561},
author = {Zelikman, Eric and Huang, Qian and Poesia, Gabriel and Goodman, Noah D and Haber, Nick},
keywords = {Computation and Language (cs.CL); Artificial Intelligence (cs.AI); Machine Learning (cs.LG)},
title = {Parsel 🐍: Algorithmic Reasoning with Language Models by Composing Decompositions},
publisher = {NeurIPS 2023},
year = {2022},
copyright = {arXiv.org perpetual, non-exclusive license}
}
Acknowledgements |