Shedding Light on Task Decomposition in Program Synthesis: The Driving Force of the Synthesizer Model
Janis Zenkner, Tobias Sesterhenn, Christian Bartelt · 2025
Read Shedding Light on Task Decomposition in Program Synthesis: The Driving Force of the Synthesizer Model by Janis Zenkner, Tobias Sesterhenn, Christian Bartelt (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-08738.txt.
Introduction
Janis Zenkner, Tobias Sesterhenn, and Christian Bartelt asked in 2025 whether breaking a programming task into subgoals is really what makes a leading synthesis system strong. ExeDec, a state-of-the-art program synthesizer, splits problems with a subgoal model and writes code piece by piece. The authors built REGISM, a stripped version that drops decomposition guidance entirely and instead iterates: write a program, run it, and revise from the execution results.
Comparing the two head-to-head, decomposition clearly won on length generalization and on composing learned concepts, the very abilities it was designed for. Yet REGISM matched or beat ExeDec in many other scenarios, and its solutions often lined up more closely with the true underlying decomposition of the task than the guided system's did. The authors conclude that repeated execution-guided synthesis is a driving force in its own right, not merely a fallback.
Catalog record
| CREATOR | Janis Zenkner, Tobias Sesterhenn, Christian Bartelt |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 40 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-08738
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Shedding Light on Task Decomposition in Program Synthesis: The Driving Force of the Synthesizer Model Janis Zenkner, Tobias Sesterhenn, Christian Bartelt Abstract 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. 1 Introduction In 2019, François Chollet introduced the arc ( arc ) as a benchmark to advance agi ( agi ) research by evaluating systems on their ability to perform broad reasoning tasks ( Chollet 2019 ) . Among the many approaches to achieving agi , program synthesis has emerged as a particularly promising avenue ( Chollet 2019 ) . Program synthesis automates the creation of programs that meet specified requirements, such as io ( io ) examples ( Devlin et al. 2017 ) , formal logical descriptions ( Hocquette & Cropper 2023 ) , natural language instructions ( Desai et al. 2016 ) , or partial program templates ( Alur et al. 2013 ) . This versatility enables systems to focus on the underlying logic of a problem rather than being tied to its specific details and realization. Despite recent progress, current systems still fall short of human-level performance ( Chollet et al. 2024 ) , making human cognition a key inspiration for generalizable reasoning methods. One such capability is the ability to decompose unfamiliar problems into smaller, manageable components ( Marcus 2003 ; Frankland & Greene 2020 ) . Task decomposition leverages this principle by dividing complex tasks into subtasks that require generalizable skills to solve ( Gulwani et al. 2017 ) . By solving these subtasks independently and integrating their solutions, systems can tackle complex problems with greater scalability and efficiency. Moreover, the emphasis on developing general-purpose capabilities, rather than narrowly tailored solutions, aligns with the broader goal of fostering universal reasoning abilities ( Chollet 2019 ) . ExeDec ( Shi et al. 2023b ) incorporates these two ideas by combining program synthesis with task decomposition. As such, ExeDec can be seen as a multi-level transductive-inductive reasoning approach, which has shown to be promising for boosting program synthesis performance ( Li et al. 2024 ) . It employs two interconnected components: a Subgoal Model that iteratively divides complex tasks into subtasks by predicting the subgoal of the next step (high-level transductive reasoning) and a synthesis model that generates programs to solve these subtasks (low-level inductive reasoning). This structured framework enables the Subgoal Model to acquire broadly applicable skills essential for addressing diverse and complex tasks, while the synthesis model focuses on their implementation, outperforming large Language Models on two program synthesis domains Shi et al. 2023b . ExeDec compares its performance against a No-Subgoal Ablation, i.e., a baseline where the Subgoal Model is excluded. Besides the difference in architecture, the key distinction lies in the training of the synthesis model: In ExeDec, the synthesis model focuses purely on program generation, while in the No-Subgoal Ablation, it is tasked with both implicit task decomposition and program generation. To distinguish both synthesis models, we refer to ExeDec’s synthesis model as Synthesizer Model. A deeper analysis of ExeDec’s underlying mechanisms offers insights into refining program synthesis approaches and optimizing task-solving strategies. Our analysis is motivated by the hypothesis that the Subgoal Model plays a nuanced role in boosting ExeDec’s performance and that the repeated invocation of the Synthesizer Model is the major driving factor behind task completion, rather than the Subgoal Model itself. Figure 1 illustrates this dynamic with a single-step task, i.e., a task solvable by a single function and without decomposition. Here, the Subgoal Model generates a subtask prediction that differs from the ground truth ( [42,42] ) causing the Synthesizer Model to produce a subprogram deviating from the target program. In the next step, despite another Subgoal Model inaccuracy, the Synthesizer Model corrects the error and ultimately solves the task. This highlights the Synthesizer Model’s robustness in mitigating decomposition inaccuracies. A key implication is that decomposing tasks more frequently—regardless of decomposition accuracy—can be beneficial, as it allows the Subgoal Model to leverage the Synthesizer Model’s corrective capabilities. The workflow in Figure 1 is a real example generated by ExeDec; additional examples are in Appendix A . The results of the ExeDec study quantitatively support this hypothesis further: Even though, ExeDec achieves a small boost in performance beyond the No-Subgoal Ablation, the No-Subgoal Ablation brings the most significant performance improvement ( Shi et al. 2023b ) . This suggests that the explicit decomposition adds value but may not be critical for all tasks and that the Synthesizer Model has a greater influence on overall task success than previously assumed. Exemplary ExeDec decomposition Task specification: x0=[42,-48] \rightarrow y=[42,42] Ground Truth: x1 = Scanl1 (max) x0 Step 1: • Predicted Subgoal: [-48,42] • Subprogram: x1 = Sort x0 • Execution: x1=[-48,42] Step 2: • Predicted Subgoal: [48,42] • Subprogram: x2 = Zip (max) x0 x1 • Execution: x2=[42,42] Figure 1: ExeDec workflow illustrating the challenges posed by misleading subtasks. The task is taken from the original test set and can be solved by computing the cumulative maximum of the input list. The subgoals are those generated by ExeDec. The decomposition process is shown for a single io pair, while the full workflow with all io pairs is available in Appendix A . Building on these observations, this paper explores the interaction between task decomposition and synthesis within ExeDec. Our key contributions are as follows: 1. We provide insights into the challenges of learning task decomposition across domains, showing that learning is easier in domains with fewer decomposition possibilities. 2. We show that the Synthesizer Model plays a key role in boosting performance, even in the absence of explicit and implicit decomposition guidance. 3. We reveal that the Synthesizer Model, in hindsight, decomposes tasks, even without being trained to do so. 2 Background 2.1 pbe pbe ( pbe ) enables task specification without requiring programming knowledge, hardware familiarity, or coding skills ( Gulwani 2011 ) , making it accessible and versatile across various domains. A pbe task is defined through io pairs that specify a desired behavior (see Figure 1 ). Formally, the specification of a task is a set X={(I_{1},O_{1}),\ldots,(I_{n},O_{n})} , where each pair (I_{i},O_{i}) corresponds to an