  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
