CoChat
Sign Up
PreprintCited by 1Software Engineering ResearchTeaching and Learning ProgrammingEvolutionary Algorithms and Applications

ReGAL: Refactoring Programs to Discover Generalizable Abstractions

Open access
Stengel-Eskin, Elias, Prasad, Archiki, Bansal, Mohit·2024·arXiv
DOI 10.48550/arxiv.2401.16467arXiv 2401.16467
Open this paper in CoChat — free accountOpen PDF

Abstract

While large language models (LLMs) are increasingly being used for program synthesis, they lack the global view needed to develop useful abstractions; they generally predict programs one at a time, often repeating the same functionality. Generating redundant code from scratch is both inefficient and error-prone. To address this, we propose Refactoring for Generalizable Abstraction Learning (ReGAL), a gradient-free method for learning a library of reusable functions via code refactorization, i.e., restructuring code without changing its execution output. ReGAL learns from a small set of existing programs, iteratively verifying and refining its abstractions via execution. We find that the shared function libraries discovered by ReGAL make programs easier to predict across diverse domains. On five datasets -- LOGO graphics generation, Date reasoning, TextCraft (a Minecraft-based text-game) MATH, and TabMWP -- both open-source and proprietary LLMs improve in accuracy when predicting programs with ReGAL functions. For CodeLlama-13B, ReGAL results in absolute accuracy increases of 11.5% on LOGO, 26.1% on date understanding, and 8.1% on TextCraft, outperforming GPT-3.5 in two of three domains. Our analysis reveals ReGAL's abstractions encapsulate frequently-used subroutines as well as environment dynamics.

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

DataCite · 10.48550/arxiv.2401.16467

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?

  • Methods that augment LLMs with tools or learned libraries typically rely on iterative reasoning and tool invocation at inference time, and thus remain sensitive to compute budgets.

    “While these methods demonstrate that LLMs can acquire useful structure, they typically rely on iterative reasoning and tool invocation at inference time, and thus remain sensitive to compute budgets.”

    From ReaComp: Compiling LLM Reasoning into Symbolic Solvers for Efficient Program Synthesis (2026) · cites this paper as Stengel-Eskin et al., 2024

    The Introduction describes generating and executing a program for each query, and the Discussion describes test-time LLM use as a variable cost that scales with the test-set size. Related Work also says some prior approaches repeatedly execute skills from scratch. But the paper does not establish that tool- or library-augmented methods typically use iterative reasoning and tool invocation at inference time; REGAL’s iterative verification and refinement concern learning its abstractions, not test-time reasoning. (LLM, conf=0.83)

    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.

No citation lists for this paper

No citation lists for this paper yet — checked again daily.

Cited by 1

Research works printed but not linked: 63

  1. Abelson, H. and DiSessa, A. Turtle geometry: The computer as a medium for exploring mathematics. MIT press, 1986.
  2. Ahn, M., Brohan, A., Brown, N., Chebotar, Y., Cortes, O., David, B., Finn, C., Fu, C., Gopalakrishnan, K., Hausman, K., Herzog, A., Ho, D., Hsu, J., Ibarz, J., Ichter, B., Irpan, A., Jang, E., Ruano, R. J., Jeffrey, K., Jesmonth, S., Joshi, N., Julian, R., Kalashnikov, D., Kuang, Y., Lee, K.-H., Levine, S., Lu, Y., Luu, L., Parada, C., Pastor, P., Quiambao, J., Rao, K., Rettinghouse, J., Reyes, D., Sermanet, P., Sievers, N., Tan, C., Toshev, A., Vanhoucke, V., Xia, F., Xiao, T., Xu, P., Xu, S., Yan, M., and Zeng, A. Do as i can and not as i say: Grounding language in robotic affordances. In arXiv preprint arXiv:2204.01691, 2022. · arXiv
  3. Andreas, J., Rohrbach, M., Darrell, T., and Klein, D. Neural module networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 39-48, 2016.
  4. Barto, A. G. and Mahadevan, S. Recent advances in hier- archical reinforcement learning. Discrete event dynamic systems, 13(1-2):41-77, 2003.
  5. Bengio, Y., Louradour, J., Collobert, R., and Weston, J. Curriculum learning. In Proceedings of the 26th annual international conference on machine learning, pp. 41-48, 2009.
  6. Bogin, B., Gupta, S., Clark, P., and Sabharwal, A. Lever- aging code to improve in-context learning for semantic parsing. arXiv preprint arXiv:2311.09519, 2023. · arXiv
  7. Bowers, M., Olausson, T. X., Wong, L., Grand, G., Tenen- baum, J. B., Ellis, K., and Solar-Lezama, A. Top-down synthesis for library learning. Proceedings of the ACM on Programming Languages, 7(POPL):1182-1213, 2023.
  8. Cai, T., Wang, X., Ma, T., Chen, X., and Zhou, D. Large language models as tool makers. arXiv preprint arXiv:2305.17126, 2023. · arXiv
  9. Chen, W., Ma, X., Wang, X., and Cohen, W. W. Program of thoughts prompting: Disentangling computation from reasoning for numerical reasoning tasks. arXiv preprint arXiv:2211.12588, 2022. · arXiv
  10. Cho, J., Zala, A., and Bansal, M. Visual programming for text-to-image generation and evaluation. Thirty-seventh Conference on Neural Information Processing Systems (NeurIPS), 2023.
  11. Côté, M.-A., Kádár, A., Yuan, X., Kybartas, B., Barnes, T., Fine, E., Moore, J., Hausknecht, M., El Asri, L., Adada, M., et al. Textworld: A learning environment for text- based games. In Computer Games: 7th Workshop, CGW 2018, Held in Conjunction with the 27th International Conference on Artificial Intelligence, IJCAI 2018, Stock- holm, Sweden, July 13, 2018, Revised Selected Papers 7, pp. 41-75. Springer, 2019.
  12. Downey, A. Think python. " O'Reilly Media, Inc.", 2012.
  13. Dziri, N., Lu, X., Sclar, M., Li, X. L., Jian, L., Lin, B. Y., West, P., Bhagavatula, C., Bras, R. L., Hwang, J. D., et al. Faith and fate: Limits of transformers on compositionality. arXiv preprint arXiv:2305.18654, 2023. · arXiv
  14. Ellis, K., Wong, L., Nye, M., Sablé-Meyer, M., Morales, L., Hewitt, L., Cary, L., Solar-Lezama, A., and Tenenbaum, J. B. Dreamcoder: Bootstrapping inductive program syn- thesis with wake-sleep library learning. In Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation, pp. 835-850, 2021.
  15. Flynn, B. B. and Jacobs, F. R. Applications and implemen- tation: an experimental comparison of cellular (group technology) layout with process layout. Decision Sci- ences, 18(4):562-581, 1987.
  16. Fürnkranz, J., Gamberger, D., and Lavrač, N. Foundations of rule learning. Springer Science & Business Media, 2012.
  17. Futuyma, D. J. and Moreno, G. The evolution of ecological specialization. Annual review of Ecology and Systematics, 19(1):207-233, 1988.
  18. Grand, G., Wong, L., Bowers, M., Olausson, T. X., Liu, M., Tenenbaum, J. B., and Andreas, J. Learning in- terpretable libraries by compressing and documenting code. In Intrinsically-Motivated and Open-Ended Learn- ing Workshop@ NeurIPS2023, 2023.
  19. Gupta, S., Shah, R., Mohit, M., Kumar, A., and Lewis, M. Semantic parsing for task oriented dialog using hi- erarchical representations. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pp. 2787-2792, 2018.
  20. Gupta, T. and Kembhavi, A. Visual programming: Compo- sitional visual reasoning without training. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 14953-14962, 2023.
  21. Hendrycks, D., Burns, C., Kadavath, S., Arora, A., Basart, S., Tang, E., Song, D., and Steinhardt, J. Measuring mathematical problem solving with the math dataset. In Thirty-fifth Conference on Neural Information Process- ing Systems Datasets and Benchmarks Track (Round 2), 2021.
  22. Huang, W., Abbeel, P., Pathak, D., and Mordatch, I. Lan- guage models as zero-shot planners: Extracting action- able knowledge for embodied agents. arXiv preprint arXiv:2201.07207, 2022. · arXiv
  23. Huang, W., Wang, C., Zhang, R., Li, Y., Wu, J., and Fei-Fei, L. Voxposer: Composable 3D value maps for robotic manipulation with language models. In Conference on Robot Learning, pp. 540-562. PMLR, 2023.
  24. Khot, T., Trivedi, H., Finlayson, M., Fu, Y., Richardson, K., Clark, P., and Sabharwal, A. Decomposed prompting: A modular approach for solving complex tasks. In The Eleventh International Conference on Learning Repre- sentations, 2023.
  25. Lake, B. M., Salakhutdinov, R., and Tenenbaum, J. B. Human-level concept learning through probabilistic pro- gram induction. Science, 350(6266):1332-1338, 2015.
  26. Liu, J., Shen, D., Zhang, Y., Dolan, B., Carin, L., and Chen, W. What makes good in-context examples for GPT-3? In Agirre, E., Apidianaki, M., and Vulić, I. (eds.), Proceedings of Deep Learning Inside Out (DeeLIO 2022): The 3rd Workshop on Knowledge Extraction and Integration for Deep Learning Architectures, pp. 100- 114, Dublin, Ireland and Online, May 2022. Association for Computational Linguistics.
  27. Liu, X., Yu, H., Zhang, H., Xu, Y., Lei, X., Lai, H., Gu, Y., Ding, H., Men, K., Yang, K., et al. AgentBench: Evaluat- ing LLMs as agents. arXiv preprint arXiv:2308.03688, 2023. · arXiv
  28. Lu, P., Qiu, L., Chang, K.-W., Wu, Y. N., Zhu, S.-C., Ra- jpurohit, T., Clark, P., and Kalyan, A. Dynamic prompt learning via policy gradient for semi-structured mathemat- ical reasoning. In The Eleventh International Conference on Learning Representations, 2022.
  29. Lu, P., Peng, B., Cheng, H., Galley, M., Chang, K.-W., Wu, Y. N., Zhu, S.-C., and Gao, J. Chameleon: Plug-and- play compositional reasoning with large language models. arXiv preprint arXiv:2304.09842, 2023. · arXiv
  30. Lyu, Q., Havaldar, S., Stein, A., Zhang, L., Rao, D., Wong, E., Apidianaki, M., and Callison-Burch, C. Faithful Chain-of-Thought Reasoning. arXiv preprint arXiv:2301.13379, 2023. · arXiv
  31. Majumder, B. P., Mishra, B. D., Jansen, P., Tafjord, O., Tandon, N., Zhang, L., Callison-Burch, C., and Clark, P. Clin: A continually learning language agent for rapid task adaptation and generalization. arXiv preprint arXiv:2310.10134, 2023. · arXiv
  32. Marcus, G. F., Vijayan, S., Bandi Rao, S., and Vishton, P. M. Rule learning by seven-month-old infants. Science, 283 (5398):77-80, 1999.
  33. McConnell, S. Code complete. Pearson Education, 2004.
  34. Mialon, G., Dessì, R., Lomeli, M., Nalmpantis, C., Pa- sunuru, R., Raileanu, R., Rozière, B., Schick, T., Dwivedi- Yu, J., Celikyilmaz, A., et al. Augmented Language Mod- els: a Survey. arXiv preprint arXiv:2302.07842, 2023. · arXiv
  35. O'Donnell, T. J. Productivity and reuse in language: A theory of linguistic computation and storage. MIT Press, 2015.
  36. Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., Vanderplas, J., Passos, A., Cour- napeau, D., Brucher, M., Perrot, M., and Duchesnay, E. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830, 2011.
  37. Prasad, A., Koller, A., Hartmann, M., Clark, P., Sabharwal, A., Bansal, M., and Khot, T. Adapt: As-needed decompo- sition and planning with language models. arXiv preprint arXiv:2311.05772, 2023. · arXiv
  38. Qian, C., Han, C., Fung, Y., Qin, Y., Liu, Z., and Ji, H. Creator: Tool creation for disentangling abstract and con- crete reasoning of large language models. In Findings of the Association for Computational Linguistics: EMNLP 2023, pp. 6922-6939, 2023.
  39. Qin, Y., Liang, S., Ye, Y., Zhu, K., Yan, L., Lu, Y., Lin, Y., Cong, X., Tang, X., Qian, B., et al. ToolLLM: Facilitating large language models to master 16000+ real-world APIs. arXiv preprint arXiv:2307.16789, 2023. · arXiv
  40. Roy, S., Thomson, S., Chen, T., Shin, R., Pauls, A., Eisner, J., and Van Durme, B. Benchclamp: A benchmark for evaluating language models on semantic parsing. arXiv preprint arXiv:2206.10668, 2022. · arXiv
  41. Roziere, B., Gehring, J., Gloeckle, F., Sootla, S., Gat, I., Tan, X. E., Adi, Y., Liu, J., Remez, T., Rapin, J., et al. Code llama: Open foundation models for code. arXiv preprint arXiv:2308.12950, 2023. · arXiv
  42. Ruan, Y., Dong, H., Wang, A., Pitis, S., Zhou, Y., Ba, J., Dubois, Y., Maddison, C., and Hashimoto, T. Identifying the risks of LM agents with an LM-emulated sandbox. In NeurIPS 2023 Foundation Models for Decision Making Workshop, 2023.
  43. Saha, S., Zhang, S., Hase, P., and Bansal, M. Summariza- tion programs: Interpretable abstractive summarization with neural modular trees. In The Eleventh International Conference on Learning Representations, 2022.
  44. Schick, T., Dwivedi-Yu, J., Dessì, R., Raileanu, R., Lomeli, M., Zettlemoyer, L., Cancedda, N., and Scialom, T. Tool- former: Language models can teach themselves to use tools. arXiv preprint arXiv:2302.04761, 2023. · arXiv
  45. Shin, R. and Van Durme, B. Few-shot semantic parsing with language models trained on code. In Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 5417-5425, 2022.
  46. Singh, I., Blukis, V., Mousavian, A., Goyal, A., Xu, D., Tremblay, J., Fox, D., Thomason, J., and Garg, A. Prog- Prompt: Generating situated robot task plans using Large Language Models. In 2023 IEEE International Confer- ence on Robotics and Automation (ICRA), pp. 11523- 11530. IEEE, 2023.
  47. Srivastava, A., Rastogi, A., Rao, A., Shoeb, A. A. M., Abid, A., Fisch, A., Brown, A. R., Santoro, A., Gupta, A., Garriga-Alonso, A., et al. Beyond the imitation game: Quantifying and extrapolating the capabilities of language models. arXiv preprint arXiv:2206.04615, 2022. · arXiv
  48. Surís, D., Menon, S., and Vondrick, C. ViperGPT: Vi- sual inference via Python execution for reasoning. arXiv preprint arXiv:2303.08128, 2023. · arXiv
  49. Sutton, R. S., Precup, D., and Singh, S. Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning. Artificial intelligence, 112(1-2): 181-211, 1999.
  50. Suzgun, M., Scales, N., Schärli, N., Gehrmann, S., Tay, Y., Chung, H. W., Chowdhery, A., Le, Q. V., Chi, E. H., Zhou, D., et al. Challenging Big-Bench tasks and whether chain-of-thought can solve them. arXiv preprint arXiv:2210.09261, 2022. · arXiv
  51. Wang, G., Xie, Y., Jiang, Y., Mandlekar, A., Xiao, C., Zhu, Y., Fan, L., and Anandkumar, A. Voyager: An open- ended embodied agent with large language models. arXiv preprint arXiv:2305.16291, 2023. · arXiv
  52. Wang, Z., Fried, D., and Neubig, G. Trove: Inducing veri- fiable and efficient toolboxes for solving programmatic tasks. arXiv preprint arXiv:2401.12869, 2024. · arXiv
  53. Ward Jr, J. H. Hierarchical grouping to optimize an objective function. Journal of the American statistical association, 58(301):236-244, 1963.
  54. Weidinger, L., Mellor, J., Rauh, M., Griffin, C., Uesato, J., Huang, P.-S., Cheng, M., Glaese, M., Balle, B., Kasirzadeh, A., et al. Ethical and social risks of harm from language models. arXiv preprint arXiv:2112.04359, 2021. · arXiv
  55. Winograd, T. Understanding natural language. Cognitive psychology, 3(1):1-191, 1972.
  56. Wolf, T., Debut, L., Sanh, V., Chaumond, J., Delangue, C., Moi, A., Cistac, P., Rault, T., Louf, R., Funtowicz, M., Davison, J., Shleifer, S., von Platen, P., Ma, C., Jernite, Y., Plu, J., Xu, C., Scao, T. L., Gugger, S., Drame, M., Lhoest, Q., and Rush, A. M. Transformers: State-of- the-art natural language processing. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations, pp. 38- 45, Online, October 2020. Association for Computational Linguistics.
  57. Wong, L., Ellis, K. M., Tenenbaum, J., and Andreas, J. Leveraging language to learn program abstractions and search heuristics. In International Conference on Ma- chine Learning, pp. 11193-11204. PMLR, 2021.
  58. Wong, L., Mao, J., Sharma, P., Siegel, Z. S., Feng, J., Ko- rneev, N., Tenenbaum, J. B., and Andreas, J. Learning adaptive planning representations with natural language guidance. arXiv preprint arXiv:2312.08566, 2023. · arXiv
  59. Yang, C. The price of linguistic productivity: How children learn to break the rules of language. MIT press, 2016.
  60. Yao, S., Zhao, J., Yu, D., Du, N., Shafran, I., Narasimhan, K. R., and Cao, Y. React: Synergizing reasoning and acting in language models. In The Eleventh International Conference on Learning Representations, 2023.
  61. Yasunaga, M., Chen, X., Li, Y., Pasupat, P., Leskovec, J., Liang, P., Chi, E. H., and Zhou, D. Large language models as analogical reasoners. arXiv preprint arXiv:2310.01714, 2023. · arXiv
  62. Yuan, L., Chen, Y., Wang, X., Fung, Y. R., Peng, H., and Ji, H. Craft: Customizing LLMs by creating and retrieving from specialized toolsets. arXiv preprint arXiv:2309.17428, 2023. · arXiv
  63. Zelle, J. M. and Mooney, R. J. Learning to parse database queries using inductive logic programming. In Proceed- ings of the national conference on artificial intelligence, pp. 1050-1055, 1996.

Authors
Stengel-Eskin, E., Prasad, A., & Bansal, M.
ORCID
Venue
arXiv
Publisher
arXiv
Published
2024
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.2401.16467
arXiv
2401.16467
OpenAlex
W4391420755
Cited by
1
References
0
Citations by year
2024: 1
Type
posted content
Language
en
Open access
Licence
Locations
  • arXiv (Cornell University) (submittedVersion, cc-by)
  • arXiv (Cornell University) (cc-by)
Funders
  • National Science Foundation (2112635)
  • Defense Advanced Research Projects Agency (N66001-19-2-4031, N66001-19)
Topics
  • Physical Sciences › Computer Science › Information Systems › Software Engineering Research
  • Physical Sciences › Computer Science › Computer Science Applications › Teaching and Learning Programming
  • Physical Sciences › Computer Science › Artificial Intelligence › Evolutionary Algorithms and Applications
Keywords
refactoring, large language models, program synthesis, gradient-free learning, CodeLlama

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