Elamur Research⌕
☰
home / papers / 2023 / Parsel: Algorithmic Reasoning with Language Models by Composing Decompositions

Parsel: Algorithmic Reasoning with Language Models by Composing Decompositions

Paper · 2023 · Eric Zelikman, Qian Huang, Gabriel Poesia et al.

Summary

Large language models that write code tend to break down on long, multi-step tasks, because a single wrong token can ruin an entire program. Human programmers avoid this by sketching a high-level design and building it piece by piece. Parsel brings this practice to code LLMs. A model first breaks a task into a hierarchy of functions written in natural language, using a small intermediate language also named Parsel. It then samples several candidate implementations for each function. Finally, the Parsel synthesizer searches over combinations of these candidates and checks them against tests or other constraints. Splitting the call graph into strongly-connected components means search cost grows only with the largest component, not with the whole program. On competition-level APPS problems, on HumanEval, and on VirtualHome robotic planning, this approach clearly beats sampling whole solutions directly. The work suggests that LLMs reason better about algorithms when they decompose problems first and then compose the parts into a solution.

Key points

  • On competition-level APPS problems, Parsel with Codex achieves pass rates more than 75% higher than earlier results from directly sampling AlphaCode and Codex, often with a smaller sample budget.
  • With GPT-4, which generated Parsel zero-shot, and automatically generated tests, pass@1 on HumanEval rose from 67% to 85%.
  • In VirtualHome, robotic plans produced through Parsel were judged accurate more than twice as often as plans generated directly.
  • Success probability followed a roughly quadratic curve in log-scaled counts of sampled Parsel programs and of sampled implementations (R² ≥ 0.99). A 2.7B CodeGen model solved no APPS problems.
  • The method depends on closed models (Codex, GPT-4). As a demonstration of scale, the authors synthesized a working Lisp interpreter from a 21-function Parsel program. Code is available at github.com/ezelikman/parsel.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 18,614 worksArtificial Intelligence · 17,965 worksArts and Humanities · 17,450 worksLanguage and Linguistics · 17,296 works

🧭 Topics 2Research subjects and languages the work is about.Language models & pretraining · 3,894 worksReasoning · 1,685 works

Cite

Cite as Eric Zelikman, Qian Huang, Gabriel Poesia, Noah D. Goodman and Nick Haber. 2023. Parsel: Algorithmic Reasoning with Language Models by Composing Decompositions. arXiv:2212.10561.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.2212.10561 · arXiv 2212.10561

@misc{zelikman2023parsel,
  title = {{Parsel: Algorithmic Reasoning with Language Models by Composing Decompositions}},
  author = {Eric Zelikman, Qian Huang, Gabriel Poesia, Noah D. Goodman and Nick Haber},
  year = {2023},
  doi = {10.48550/arxiv.2212.10561},
  eprint = {2212.10561},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.2212.10561}
}

References

72 references, 38 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. M. Abadi, A. Agarwal, P. Barham, E. Brevdo, Z. Chen, C. Citro, G. S. Corrado, A. Davis, J. Dean, M. Devin, S. Ghemawat, I. Goodfellow, A. Harp, G. Irving, M. Isard, Y. Jia, R. Jozefowicz, L. Kaiser, M. Kudlur, J. Levenberg, D. Mané, R. Monga, S. Moore, D. Murray, C. Olah, M. Schuster, J. Shlens, B.… find
  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. find
  3. C. Anil, Y. Wu, A. J. Andreassen, A. Lewkowycz, V. Misra, V. V. Ramasesh, A. Slone, G. Gur-Ari, E. Dyer, and B. Neyshabur. Exploring length generalization in large language models. In Advances in Neural Information Processing Systems.
  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.
  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.
  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.
  7. M. A. Bauer. Programming by examples. Artificial Intelligence, 12(1):1–21, 1979. find
  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. find
  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. find
  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.
  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. find
  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.
  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.
  14. F. Chollet. On the measure of intelligence. arXiv preprint arXiv:1911.01547, 2019. find
  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.
  16. J. Cocke and K. Kennedy. An algorithm for reduction of operator strength. Communications of the ACM, 20(11):850–856, 1977. find
  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. find
  18. P. Denny, V. Kumar, and N. Giacaman. Conversing with copilot: Exploring prompt engineering for solving cs1 problems using natural language. SIGCSE, 2022. find
  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. find
  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.
  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.
  22. D. Dua, S. Gupta, S. Singh, and M. Gardner. Successive prompting for decomposing complex questions. arXiv preprint arXiv:2212.04092, 2022. find
  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 wake-sleep library learning. In Proceedings of the 42nd acm sigplan international conference on programming language design and… find
  24. M. Games. The fantastic combinations of john conway’s new solitaire game “life” by martin gardner. Scientific American, 223:120–123, 1970. find
  25. S. Gulwani. Programming by examples. Dependable Software Systems Engineering, 45(137): 3–15, 2016. find
  26. S. Gulwani, O. Polozov, R. Singh, et al. Program synthesis. Foundations and Trends® in Programming Languages, 4(1-2):1–119, 2017.
  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.
  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.
  29. B. Ibarz, V. Kurin, G. Papamakarios, K. Nikiforou, M. Bennani, R. Csordás, A. Dudzik, M. Bošnjak, A. Vitvitskyi, Y. Rubanova, et al. A generalist neural algorithmic learner. LoG, 2022. find
  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.
  31. O. Khattab, K. Santhanam, X. L. Li, D. Hall, P. Liang, C. Potts, and M. Zaharia. Demonstrate-search-predict: Composing retrieval and language models for knowledge-intensive nlp. arXiv preprint arXiv:2212.14024, 2022.
  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.
  33. S. Kulal, P. Pasupat, K. Chandra, M. Lee, O. Padon, A. Aiken, and P. S. Liang. Spoc: Search-based pseudocode to code. Advances in Neural Information Processing Systems, 32, 2019.
  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.
  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.
  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. find
  37. A. Marasović, I. Beltagy, D. Downey, and M. E. Peters. Few-shot self-rationalization with natural language prompts. arXiv preprint arXiv:2111.08284, 2021.
  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.
  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. find
  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. find
  41. P. Norvig. How to write a Lisp interpreter (in Python), 2010. URL http://norvig.com/lispy.html. ↗
  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.
  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. find
  44. OpenAI. Gpt-4 technical report. arXiv, 2023.
  45. S. Palan and C. Schitter. Prolific. ac—a subject pool for online experiments. Journal of Behavioral and Experimental Finance, 17:22–27, 2018. find
  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.
  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:2211.03622](https://arxiv.org/abs/2211.03622) find
  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. find
  49. S. Polu and I. Sutskever. Generative language modeling for automated theorem proving. arXiv preprint arXiv:2009.03393, 2020.
  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. find
  51. N. F. Rajani, B. McCann, C. Xiong, and R. Socher. Explain yourself! leveraging language models for commonsense reasoning. ACL, 2019.
  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. find
  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:2208.09727](https://arxiv.org/abs/2208.09727) find
  54. V. Shwartz, P. West, R. L. Bras, C. Bhagavatula, and Y. Choi. Unsupervised commonsense question answering with self-talk. EMNLP 2020, 2020. find
  55. H. A. Simon and A. Newell. Human problem solving: The state of the theory in 1970. American psychologist, 26(2):145, 1971. find
  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.
  57. A. Stuhlmüller, J. Reppert, and L. Stebbing. Factored cognition primer. https://primer.ought.org, 2022. ↗
  58. M. Tabachnyk and S. Nikolov. Ml-enhanced code completion improves developer productivity, 2022. find
  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.
  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.
  61. N. Wies, Y. Levine, and A. Shashua. Sub-task decomposition enables learning in sequence to sequence tasks. arXiv preprint arXiv:2204.02892, 2022. find
  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.
  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.
  64. A. Ye, C. Cui, T. Shi, and M. O. Riedl. Neural story planning, 2022. URL https://arxiv.org/abs/2212.08718. — [arXiv:2212.08718](https://arxiv.org/abs/2212.08718) ↗
  65. P. Yin and G. Neubig. A syntactic neural model for general-purpose code generation. ACL, 2017.
  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.
  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. ↗
  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. ↗
  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. find
  70. K. Zheng, J. M. Han, and S. Polu. Minif2f: a cross-system benchmark for formal olympiad-level mathematics. ICLR, 2022.
  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.
  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.

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/zelikman-2023-parsel-algorithmic-reasoning-language-models/