CoChat
Sign Up
Cited by 15Logic, Reasoning, and KnowledgeLogic, programming, and type systemsNatural Language Processing Techniques

Parsel🐍: Algorithmic Reasoning with Language Models by Composing Decompositions

Open access
Zelikman, Eric, Huang, Qian, Poesia, Gabriel, Goodman, Noah, Haber, Nick·2023·Advances in Neural Information Processing Systems 36
DOI 10.52202/075280-1367
Open this paper in CoChat — free accountOpen PDF

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. 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

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.52202/075280-1367

Cites

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • The probability that one of n solutions solves all of a problem's independent, modular parts drops precipitously with the number of parts, but the probability that an attempt solves a given part does not depend on the number of parts.

    “the probability that one of n solutions solves all of a problem's independent, modular parts drops precipitously with the number of parts, but the probability that an attempt solves a given part does not depend on the number of parts.”

    From Self-Taught Optimizer (STOP): Recursively Self-Improving Code Generation (2023) · cites this paper as Zelikman et al. (2023)

    Section 3.1 (p. 6) reports that as the number of required components grows, mixing parts from two programs solves more problems than sampling 16 complete programs. It also argues that, assuming independence, combining implementations is more likely to yield a correct program than taking the same number of whole-program samples. The paper does not state that an attempt’s probability of solving a given part is unaffected by the number of parts. (LLM, conf=0.83)

    Experimental — accuracy not yet measured

  • Agent systems often show dramatic improvements in benchmark performance over plain LLMs through combinations of prompting strategies and methods for combining different LLM outputs.

    “These agent systems often show dramatic improvements in benchmark performance over”

    From A Self-Improving Coding Agent (2025) · cites this paper as Zelikman et al., 2023

    The Abstract (p. 1) describes Parsel combining LLM-generated function implementations using tests and reports substantially higher benchmark pass rates than direct LLM sampling. The Introduction (p. 1) also describes few-shot prompting and improvement over GPT-4 alone. These passages support Parsel as an example, but this paper does not establish that agent systems *often* achieve such improvements as a class. (LLM, conf=0.84)

    Experimental — accuracy not yet measured

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

No references could be resolved yet.

Research works printed but not linked: 65

  1. [2][2] S. Acquaviva, Y. Pu, M. Kryven, T. Sechopoulos, C. Wong, G. E. Ecanow, M. Nye, M. H. Tessler, and J. B. Tenenbaum. Communicating natural programs to humans and machines. NeurIPS , 2022. -
  2. [3][3] C. Anil, Y. Wu, A. J. Andreassen, A. Lewkowycz, V. Misra, V. V. Ramasesh, A. Slone, G. GurAri, E. Dyer, and B. Neyshabur. Exploring length generalization in large language models. In Advances in Neural Information Processing Systems . -
  3. [4][4] T. Anthony, Z. Tian, and D. Barber. Thinking fast and slow with deep learning and tree search. Advances in Neural Information Processing Systems , 30, 2017. -
  4. [5][5] B. Athiwaratkun, S. K. Gouda, Z. Wang, X. Li, Y. Tian, M. Tan, W. U. Ahmad, S. Wang, Q. Sun, M. Shang, et al. Multi-lingual evaluation of code generation models. arXiv preprint arXiv:2210.14868 , 2022. - · arXiv
  5. [6][6] J. Austin, A. Odena, M. Nye, M. Bosma, H. Michalewski, D. Dohan, E. Jiang, C. Cai, M. Terry, Q. Le, et al. Program synthesis with large language models. arXiv preprint arXiv:2108.07732 , 2021. - · arXiv
  6. [7][7] M. A. Bauer. Programming by examples. Artificial Intelligence , 12(1):1-21, 1979. -
  7. [8][8] L. Beurer-Kellner, M. Fischer, and M. Vechev. Prompting is programming: A query language for large language models. arXiv preprint arXiv:2212.06094 , 2022. - · arXiv
  8. [9][9] M. Bowers, T. X. Olausson, C. Wong, G. Grand, J. B. Tenenbaum, K. Ellis, and A. Solar-Lezama. Top-down synthesis for library learning. POPL , 2023. -
  9. [10][10] A. Brohan, Y. Chebotar, C. Finn, K. Hausman, A. Herzog, D. Ho, J. Ibarz, A. Irpan, E. Jang, R. Julian, et al. Do as i can, not as i say: Grounding language in robotic affordances. In 6th Annual Conference on Robot Learning , 2022. -
  10. [11][11] B. Chen, F. Zhang, A. Nguyen, D. Zan, Z. Lin, J.-G. Lou, and W. Chen. Codet: Code generation with generated tests. arXiv preprint arXiv:2207.10397 , 2022. - · arXiv
  11. [12][12] M. Chen, J. Tworek, H. Jun, Q. Yuan, H. P. d. O. Pinto, J. Kaplan, H. Edwards, Y. Burda, N. Joseph, G. Brockman, et al. Evaluating large language models trained on code. arXiv preprint arXiv:2107.03374 , 2021. - · arXiv
  12. [13][13] Z. Cheng, T. Xie, P. Shi, C. Li, R. Nadkarni, Y . Hu, C. Xiong, D. Radev, M. Ostendorf, L. Zettlemoyer, et al. Binding language models in symbolic languages. arXiv preprint arXiv:2210.02875 , 2022. - · arXiv
  13. [14][14] F. Chollet. On the measure of intelligence. arXiv preprint arXiv:1911.01547 , 2019. - · arXiv
  14. [15][15] K. Cobbe, V. Kosaraju, M. Bavarian, J. Hilton, R. Nakano, C. Hesse, and J. Schulman. Training verifiers to solve math word problems. arXiv preprint arXiv:2110.14168 , 2021. - · arXiv
  15. [16][16] J. Cocke and K. Kennedy. An algorithm for reduction of operator strength. Communications of the ACM , 20(11):850-856, 1977. -
  16. [17][17] E. Daka and G. Fraser. A survey on unit testing practices and problems. In 2014 IEEE 25th International Symposium on Software Reliability Engineering , pages 201-211. IEEE, 2014. -
  17. [19][19] A. Desai, S. Gulwani, V. Hingorani, N. Jain, A. Karkare, M. Marron, and S. Roy. Program synthesis using natural language. In Proceedings of the 38th International Conference on Software Engineering , pages 345-356, 2016. -
  18. [20][20] D. Dohan, W. Xu, A. Lewkowycz, J. Austin, D. Bieber, R. G. Lopes, Y. Wu, H. Michalewski, R. A. Saurous, J. Sohl-Dickstein, et al. Language model cascades. arXiv preprint arXiv:2207.10342 , 2022. - · arXiv
  19. [21][21] N. Du, Y. Huang, A. M. Dai, S. Tong, D. Lepikhin, Y. Xu, M. Krikun, Y. Zhou, A. W. Yu, O. Firat, et al. Glam: Efficient scaling of language models with mixture-of-experts. In International Conference on Machine Learning , pages 5547-5569. PMLR, 2022. -
  20. [22][22] D. Dua, S. Gupta, S. Singh, and M. Gardner. Successive prompting for decomposing complex questions. arXiv preprint arXiv:2212.04092 , 2022. - · arXiv
  21. [23][23] K. Ellis, C. Wong, M. Nye, M. Sablé-Meyer, L. Morales, L. Hewitt, L. Cary, A. Solar-Lezama, and J. B. Tenenbaum. Dreamcoder: Bootstrapping inductive program synthesis with wakesleep library learning. In Proceedings of the 42nd acm sigplan international conference on programming language design and implementation , pages 835-850, 2021. -
  22. [25][25] S. Gulwani. Programming by examples. Dependable Software Systems Engineering , 45(137): 3-15, 2016. -
  23. [26][26] S. Gulwani, O. Polozov, R. Singh, et al. Program synthesis. Foundations and Trends® in Programming Languages , 4(1-2):1-119, 2017. -
  24. [27][27] D. Hendrycks, S. Basart, S. Kadavath, M. Mazeika, A. Arora, E. Guo, C. Burns, S. Puranik, H. He, D. Song, et al. Measuring coding challenge competence with apps. Advances in Neural Information Processing Systems , 2021. -
  25. [28][28] W. Huang, P. Abbeel, D. Pathak, and I. Mordatch. Language models as zero-shot planners: Extracting actionable knowledge for embodied agents. arXiv preprint arXiv:2201.07207 , 2022. - · arXiv
  26. [30][30] A. Q. Jiang, S. Welleck, J. P. Zhou, W. Li, J. Liu, M. Jamnik, T. Lacroix, Y . Wu, and G. Lample. Draft, sketch, and prove: Guiding formal theorem provers with informal proofs. arXiv preprint arXiv:2210.12283 , 2022. - · arXiv
  27. [31][31] O. Khattab, K. Santhanam, X. L. Li, D. Hall, P. Liang, C. Potts, and M. Zaharia. Demonstratesearch-predict: Composing retrieval and language models for knowledge-intensive nlp. arXiv preprint arXiv:2212.14024 , 2022. - · arXiv
  28. [32][32] T. Kojima, S. S. Gu, M. Reid, Y. Matsuo, and Y. Iwasawa. Large language models are zero-shot reasoners. arXiv preprint arXiv:2205.11916 , 2022. - · arXiv
  29. [33][33] S. Kulal, P. Pasupat, K. Chandra, M. Lee, O. Padon, A. Aiken, and P. S. Liang. Spoc: Searchbased pseudocode to code. Advances in Neural Information Processing Systems , 32, 2019. -
  30. [34][34] A. K. Lampinen, I. Dasgupta, S. C. Chan, K. Matthewson, M. H. Tessler, A. Creswell, J. L. McClelland, J. X. Wang, and F. Hill. Can language models learn from explanations in context? arXiv preprint arXiv:2204.02329 , 2022. - · arXiv
  31. [35][35] Y. Li, D. Choi, J. Chung, N. Kushman, J. Schrittwieser, R. Leblond, T. Eccles, J. Keeling, F. Gimeno, A. Dal Lago, et al. Competition-level code generation with alphacode. Science , 378 (6624):1092-1097, 2022. -
  32. [36][36] P. Liang, R. Bommasani, T. Lee, D. Tsipras, D. Soylu, M. Yasunaga, Y. Zhang, D. Narayanan, Y. Wu, A. Kumar, et al. Holistic evaluation of language models. arXiv preprint arXiv:2211.09110 , 2022. - · arXiv
  33. [37][37] A. Marasovi´ c, I. Beltagy, D. Downey, and M. E. Peters. Few-shot self-rationalization with natural language prompts. arXiv preprint arXiv:2111.08284 , 2021. - · arXiv
  34. [38][38] W. Merrill, Y. Goldberg, R. Schwartz, and N. A. Smith. Provable limitations of acquiring meaning from ungrounded form: What will future language models understand? Transactions of the Association for Computational Linguistics , 9:1047-1060, 2021. -
  35. [39][39] E. Nijkamp, B. Pang, H. Hayashi, L. Tu, H. Wang, Y. Zhou, S. Savarese, and C. Xiong. Codegen: An open large language model for code with multi-turn program synthesis. arXiv preprint arXiv:2203.13474 , 2022. - · arXiv
  36. [40][40] E. Nijkamp, B. Pang, H. Hayashi, L. Tu, H. Wang, Y. Zhou, S. Savarese, and C. Xiong. A conversational paradigm for program synthesis. arXiv preprint arXiv:2203.13474 , 2022. - · arXiv
  37. [42][42] M. Nye, A. J. Andreassen, G. Gur-Ari, H. Michalewski, J. Austin, D. Bieber, D. Dohan, A. Lewkowycz, M. Bosma, D. Luan, et al. Show your work: Scratchpads for intermediate computation with language models. arXiv preprint arXiv:2112.00114 , 2021. - · arXiv
  38. [43][43] A. Odena, K. Shi, D. Bieber, R. Singh, C. Sutton, and H. Dai. Bustle: Bottom-up program synthesis through learning-guided exploration. ICLR , 2021. -
  39. [44][44] OpenAI. Gpt-4 technical report. arXiv , 2023. -
  40. [45][45] S. Palan and C. Schitter. Prolific. ac-a subject pool for online experiments. Journal of Behavioral and Experimental Finance , 17:22-27, 2018. -
  41. [46][46] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems , 32, 2019. -
  42. [47][47] N. Perry, M. Srivastava, D. Kumar, and D. Boneh. Do users write more insecure code with ai assistants? arXiv preprint arXiv:2211.03622 , 2022. - · arXiv
  43. [48][48] G. Poesia, A. Polozov, V. Le, A. Tiwari, G. Soares, C. Meek, and S. Gulwani. Synchromesh: Reliable code generation from pre-trained language models. In International Conference on Learning Representations , 2022. -
  44. [49][49] S. Polu and I. Sutskever. Generative language modeling for automated theorem proving. arXiv preprint arXiv:2009.03393 , 2020. - · arXiv
  45. [50][50] X. Puig, K. Ra, M. Boben, J. Li, T. Wang, S. Fidler, and A. Torralba. Virtualhome: Simulating household activities via programs. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition , pages 8494-8502, 2018. -
  46. [51][51] N. F. Rajani, B. McCann, C. Xiong, and R. Socher. Explain yourself! leveraging language models for commonsense reasoning. ACL , 2019. -
  47. [52][52] M. Raza, S. Gulwani, and N. Milic-Frayling. Compositional program synthesis from natural language and examples. In Twenty-Fourth International Joint Conference on Artificial Intelligence , 2015. -
  48. [53][53] G. Sandoval, H. Pearce, T. Nys, R. Karri, B. Dolan-Gavitt, and S. Garg. Security implications of large language model code assistants: A user study. arXiv preprint arXiv:2208.09727 , 2022. - · arXiv
  49. [54][54] V. Shwartz, P. West, R. L. Bras, C. Bhagavatula, and Y. Choi. Unsupervised commonsense question answering with self-talk. EMNLP 2020 , 2020. -
  50. [55][55] H. A. Simon and A. Newell. Human problem solving: The state of the theory in 1970. American psychologist , 26(2):145, 1971. -
  51. [56][56] I. Singh, V. Blukis, A. Mousavian, A. Goyal, D. Xu, J. Tremblay, D. Fox, J. Thomason, and A. Garg. Progprompt: Generating situated robot task plans using large language models. arXiv preprint arXiv:2209.11302 , 2022. - · arXiv
  52. [59][59] J. Uesato, N. Kushman, R. Kumar, F. Song, N. Siegel, L. Wang, A. Creswell, G. Irving, and I. Higgins. Solving math word problems with process-and outcome-based feedback. arXiv preprint arXiv:2211.14275 , 2022. - · arXiv
  53. [60][60] J. Wei, X. Wang, D. Schuurmans, M. Bosma, E. Chi, Q. Le, and D. Zhou. Chain of thought prompting elicits reasoning in large language models. arXiv preprint arXiv:2201.11903 , 2022. - · arXiv
  54. [61][61] N. Wies, Y. Levine, and A. Shashua. Sub-task decomposition enables learning in sequence to sequence tasks. arXiv preprint arXiv:2204.02892 , 2022. - · arXiv
  55. [62][62] F. F. Xu, U. Alon, G. Neubig, and V. J. Hellendoorn. A systematic evaluation of large language models of code. In Proceedings of the 6th ACM SIGPLAN International Symposium on Machine Programming , pages 1-10, 2022. -
  56. [63][63] S. Yao, J. Zhao, D. Yu, N. Du, I. Shafran, K. Narasimhan, and Y. Cao. React: Synergizing reasoning and acting in language models. arXiv preprint arXiv:2210.03629 , 2022. - · arXiv
  57. [64][64] A. Ye, C. Cui, T. Shi, and M. O. Riedl. Neural story planning, 2022. URL https://arxiv. org/abs/2212.08718 . -
  58. [65][65] P. Yin and G. Neubig. A syntactic neural model for general-purpose code generation. ACL , 2017. -
  59. [66][66] P. Yin, B. Deng, E. Chen, B. Vasilescu, and G. Neubig. Learning to mine aligned code and natural language pairs from stack overflow. In 2018 IEEE/ACM 15th international conference on mining software repositories (MSR) , pages 476-486. IEEE, 2018. -
  60. [67][67] P. Yin, W.-D. Li, K. Xiao, A. Rao, Y. Wen, K. Shi, J. Howland, P. Bailey, M. Catasta, H. Michalewski, A. Polozov, and C. Sutton. Natural language to code generation in interactive data science notebooks, 2022. URL https://arxiv.org/abs/2212.09248 . - · arXiv
  61. [68][68] E. Zelikman, Y. Wu, J. Mu, and N. Goodman. STar: Bootstrapping reasoning with reasoning. In A. H. Oh, A. Agarwal, D. Belgrave, and K. Cho, editors, Advances in Neural Information Processing Systems , 2022. URL https://openreview.net/forum?id=\_3ELRdg2sgI . -
  62. [69][69] T. Zhang, T. Yu, T. B. Hashimoto, M. Lewis, W.-t. Yih, D. Fried, and S. I. Wang. Coder reviewer reranking for code generation. arXiv preprint arXiv:2211.16490 , 2022. - · arXiv
  63. [70][70] K. Zheng, J. M. Han, and S. Polu. Minif2f: a cross-system benchmark for formal olympiad-level mathematics. ICLR , 2022. -
  64. [71][71] D. Zhou, N. Schärli, L. Hou, J. Wei, N. Scales, X. Wang, D. Schuurmans, O. Bousquet, Q. Le, and E. Chi. Least-to-most prompting enables complex reasoning in large language models. arXiv preprint arXiv:2205.10625 , 2022. - · arXiv
  65. [72][72] H. Zhou, A. Nova, H. Larochelle, A. Courville, B. Neyshabur, and H. Sedghi. Teaching algorithmic reasoning via in-context learning. arXiv preprint arXiv:2211.09066 , 2022. ``` 1 select_airport_cities(city_road_cost, city_airport_cost): given a matrix representing the ↪ → cost of building a road between any two cities, and a list representing the cost of ↪ → building an airport in a city (where any two cities with airports are connected), return ↪ → a list of the cities that should have airports built in them to minimize the total cost ↪ → of building roads and airports such that all cities are connected. The list should be ↪ → sorted in ascending order. 2 [[0,3,3],[3,0,3],[3,3,0]],[0,0,0] -> [0,1,2] 3 [[0,3,3],[3,0,3],[3,3,0]],[10,10,10] -> [] 4 [[0,10,3],[10,0,11],[3,11,0]],[1,4,5] -> [0,1] 5 sky_city_cost(city_road_cost, city_airport_cost): given a list of lists representing the ↪ → cost of building a road between any two cities, and a list representing the cost of ↪ → building an airport in a city, return a new cost matrix with a new node corresponding ↪ → to the sky. 6 [[1,2,3],[1,2,3],[1,2,3]],[4,5,6] -> [[1,2,3,4],[1,2,3,5],[1,2,3,6],[4,5,6,0]] 7 minimum_spanning_tree(cost_matrix): given a list of lists representing the cost of each ↪ → edge, return an adjacency matrix corresponding to the minimum spanning true. 8 [[0,1,3,4],[1,0,2,100],[3,2,0,5],[4,100,5,0]] -> ↪ → [[0,1,0,1],[1,0,1,0],[0,1,0,0],[1,0,0,0]] 9 final_node_connectors(adjacency_matrix): given a list of lists representing an adjacency ↪ → matrix, return a list of the nodes connected to the final node. However, if only one ↪ → node is connected to the final node, return an empty list. 10 [[0,1,0,1],[1,0,1,0],[0,1,0,0],[1,0,0,0]] -> [] 11 [[0,1,0,1],[1,0,1,0],[0,1,0,1],[1,0,1,0]] -> [0,2] ``` Figure A.9: A potential programming assignment focused on problem-solving rather than implementation. The top-level function and asserts would be the assigned problem (which Codex [12] does not seem to be able to solve directly), while the other functions would be the student solution. · arXiv

Cited by

Sorted by citations

Authors
Zelikman, E., Huang, Q., Poesia, G., Goodman, N., & Haber, N.
ORCID
Venue
Advances in Neural Information Processing Systems 36
Publisher
Neural Information Processing Systems Foundation, Inc. (NeurIPS)
Published
2023
Pages
31466-31523
ISSN
1049-5258 (ISSN-L)
DOI
10.52202/075280-1367
OpenAlex
W7133208738
Cited by
15
References
0
Citations by year
2026: 1 · 2025: 6 · 2024: 5 · 2023: 2 · 2014: 1
FWCI
2.49
Type
conference paper
Language
en
Open access
Locations
  • neural information processing systems (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Logic, Reasoning, and Knowledge
  • Physical Sciences › Computer Science › Artificial Intelligence › Logic, programming, and type systems
  • Physical Sciences › Computer Science › Artificial Intelligence › Natural Language Processing Techniques
Keywords
algorithmic reasoning, language models, decomposition, composition, program synthesis

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review