# Shedding Light in Task Decomposition in Program Synthesis: The Driving Force of the Synthesizer Model

arXiv: https://arxiv.org/abs/2503.08738 · HTML: https://mlsanity.com/paper/2503.08738/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 36 references that are in the map.
- First posted on arXiv 11 Mar 2025.

## Builds on (most cited first, 24 of 24)

- [Planning with Large Language Models for Code Generation](https://mlsanity.com/paper/2303.05510/) (2023)
- [ADaPT: As-Needed Decomposition and Planning with Language Models](https://mlsanity.com/paper/2311.05772/) (2023)
- [DeepCoder: Learning to Write Programs](https://mlsanity.com/paper/1611.01989/) (2016)
- [RobustFill: Neural Program Learning under Noisy I/O](https://mlsanity.com/paper/1703.07469/) (2017)
- [WorldCoder, a Model-Based LLM Agent: Building World Models by Writing Code and Interacting with the Environment](https://mlsanity.com/paper/2402.12275/) (2024)
- [ARC Prize 2024: Technical Report](https://mlsanity.com/paper/2412.04604/) (2024)
- [Write, Execute, Assess: Program Synthesis with a REPL](https://mlsanity.com/paper/1906.04604/) (2019)
- [Compositional Generalization via Neural-Symbolic Stack Machines](https://mlsanity.com/paper/2008.06662/) (2020)
- [Compositional Generalization from First Principles](https://mlsanity.com/paper/2307.05596/) (2023)
- [Combining Induction and Transduction for Abstract Reasoning](https://mlsanity.com/paper/2411.02272/) (2024)
- [Learning to Infer Program Sketches](https://mlsanity.com/paper/1902.06349/) (2019)
- [Program Synthesis using Natural Language](https://mlsanity.com/paper/1509.00413/) (2015)
- [BUSTLE: Bottom-Up Program Synthesis Through Learning-Guided Exploration](https://mlsanity.com/paper/2007.14381/) (2020)
- [Is Programming by Example solved by LLMs?](https://mlsanity.com/paper/2406.08316/) (2024)
- [Hierarchical Programmatic Reinforcement Learning via Learning to Compose Programs](https://mlsanity.com/paper/2301.12950/) (2023)
- [Latent Programmer: Discrete Latent Codes for Program Synthesis](https://mlsanity.com/paper/2012.00377/) (2020)
- [CrossBeam: Learning to Search in Bottom-Up Program Synthesis](https://mlsanity.com/paper/2203.10452/) (2022)
- [ExeDec: Execution Decomposition for Compositional Generalization in Neural Program Synthesis](https://mlsanity.com/paper/2307.13883/) (2023)
- [Learning to Combine Per-Example Solutions for Neural Program Synthesis](https://mlsanity.com/paper/2106.07175/) (2021)
- [LambdaBeam: Neural Program Search with Higher-Order Functions and Lambdas](https://mlsanity.com/paper/2306.02049/) (2023)
- [Relational decomposition for program synthesis](https://mlsanity.com/paper/2408.12212/) (2024)
- [Learning big logical rules by joining small rules](https://mlsanity.com/paper/2401.16215/) (2024)
- [Relational program synthesis with numerical reasoning](https://mlsanity.com/paper/2210.00764/) (2022)
- [Learning a Hierarchical Planner from Humans in Multiple Generations](https://mlsanity.com/paper/2310.11614/) (2023)

## Built on by (most cited first, 2 of 2)

- [Agint: Agentic Graph Compilation for Software Engineering Agents](https://mlsanity.com/paper/2511.19635/) (2025)
- [Beyond Either-Or Reasoning: Transduction and Induction as Cooperative Problem-Solving Paradigms](https://mlsanity.com/paper/2505.14744/) (2025)

## Abstract (arXiv)

Task decomposition is a fundamental mechanism in program synthesis, enabling complex problems to be broken down into manageable subtasks. ExeDec, a state-of-the-art program synthesis framework, employs this approach by combining a Subgoal Model for decomposition and a Synthesizer Model for program generation to facilitate compositional generalization. In this work, we develop REGISM, an adaptation of ExeDec that removes decomposition guidance and relies solely on iterative execution-driven synthesis. By comparing these two exemplary approaches-ExeDec, which leverages task decomposition, and REGISM, which does not-we investigate the interplay between task decomposition and program generation. Our findings indicate that ExeDec exhibits significant advantages in length generalization and concept composition tasks, likely due to its explicit decomposition strategies. At the same time, REGISM frequently matches or surpasses ExeDec's performance across various scenarios, with its solutions often aligning more closely with ground truth decompositions. These observations highlight the importance of repeated execution-guided synthesis in driving task-solving performance, even within frameworks that incorporate explicit decomposition strategies. Our analysis suggests that task decomposition approaches like ExeDec hold significant potential for advancing program synthesis, though further work is needed to clarify when and why these strategies are most effective.