Research map / Large language models / Agents, code and math
ReGAL: Refactoring Programs to Discover Generalizable Abstractions
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes ReGAL, a gradient-free method that refactors primitive programs with a frozen LLM (GPT-3.5) to learn a verified library of reusable helper functions, improving program prediction across five domains.
Problem
LLMs generate programs one query at a time from primitives, leading to redundant code, repeated errors, and no shared abstractions across examples.
Approach
Learn a code bank of reusable helper functions by batch-refactoring clustered, curriculum-ordered primitive programs with a frozen LLM, verifying helpers by execution, retrying with feedback, and periodically editing and pruning the library; at test time an agent retrieves helpers and demos as in-context examples.
Key results
- CodeLlama-13B with ReGAL abstractions improves by 11.5% on LOGO (45.6 to 57.1), 26.1% on Date, and 8.1% on TextCraft, outperforming GPT-3.5 primitive programs on LOGO and TextCraft.
- GPT-3.5-turbo gains 11.8% on MATH (43.2 to 55.4) with ReGAL.
- Under distribution shift on TextCraft, full ReGAL adaptation reaches 17.2 vs 7.8 for primitive programs.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use ReGAL helper functions instead of primitive-only programs | CodeLlama-13B · LOGO test | accuracy: 45.6 -> 57.1 | Helped |
| Use ReGAL helper functions instead of primitive-only programs | GPT-3.5-turbo · Date test | accuracy: 88.9 -> 90.2 | Helped |
| Use ReGAL helper functions instead of primitive-only programs | GPT-3.5-turbo · MATH Algebra test | accuracy: 43.2 -> 55.4 | Helped |
| Add retry (ablation) | ReGAL · LOGO dev | accuracy: 48.3 -> 55.0 | Helped |
| Add retry (ablation) | ReGAL · Date dev | accuracy: 51.9 -> 77.0 | Helped |
| Add retry (ablation) | ReGAL · TextCraft dev | accuracy: 30.43 -> 34.12 | Helped |
| Use a curriculum ordered from shorter to longer queries rather than shuffled clusters (ablation) | ReGAL · LOGO dev | accuracy: 36.3 -> 55.0 | Helped |
| Use a curriculum ordered from shorter to longer queries rather than shuffled clusters (ablation) | ReGAL · Date dev | accuracy: 56.6 -> 77.0 | Helped |
| Use a curriculum ordered from shorter to longer queries rather than shuffled clusters (ablation) | ReGAL · TextCraft dev | accuracy: 28.78 -> 34.12 | Helped |
| Add pruneCodeBank (ablation) | ReGAL · LOGO dev | accuracy: 52.0 -> 55.0 | Helped |
| Add pruneCodeBank (ablation) | ReGAL · Date dev | accuracy: 65.5 -> 77.0 | Helped |
| Add pruneCodeBank (ablation) | ReGAL · TextCraft dev | accuracy: 25.26 -> 34.12 | Helped |
Surprising findings
- Retrials and curriculum ordering are the largest contributors in ablations; random ordering drops LOGO by 18.7%.
- Lemur-70B produced many empty outputs on math tasks, so ReGAL gains there were not significant.
Limitations
- Learned functions are code-based and may be less flexible than neural skills, especially in dynamic environments like navigation.
- Not all domains have reusable abstractions; gains depend on domain structure.
- Gains on math domains (MATH, TabMWP) are smaller and lack a clear domain language.
Experimental setup
Datasets: LOGO BigBench-Hard date understanding TextCraft MATH TabMWP
Benchmarks: LOGO Date understanding TextCraft MATH (Algebra) TabMWP
Metrics: accuracy
Baselines: Primitive programs baseline agent Lilo Faithful-CoT ReAct GPT-3.5-turbo primitive programs
Builds on: DreamCoder Lilo Faithful-CoT ReAct Program-of-Thoughts
Closest papers by meaning
- Chain of Execution Supervision Promotes General Reasoning in Large Language Models (NeurIPS 2025 · similarity 0.86)
- CodeChain: Towards Modular Code Generation Through Chain of Self-revisions with Representative Sub-modules (ICLR 2024 · similarity 0.86)
- Divide-and-Conquer Meets Consensus: Unleashing the Power of Functions in Code Generation (NeurIPS 2024 · similarity 0.86)
- Code Repair with LLMs gives an Exploration-Exploitation Tradeoff (NeurIPS 2024 · similarity 0.86)
- LILO: Learning Interpretable Libraries by Compressing and Documenting Code (ICLR 2024 · similarity 0.86)
- SemCoder: Training Code Language Models with Comprehensive Semantics Reasoning (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.