ResearchPod Summary
Programming-by-example (PBE) systems often use a two-stage architecture: a decomposer splits a task into subgoals, and a synthesizer generates code for those subgoals. Traditionally, these decomposers are trained via supervised learning to mimic human-annotated ground-truth (GT) decompositions. This paper investigates whether GT decompositions are actually optimal for the downstream synthesizer, or if the synthesizer's own inductive biases and search dynamics make certain human-chosen subgoals intractable.
The authors introduce Solver-Aware Decomposition (SAD), a training framework that treats decomposition as a solver-dependent decision problem. While SAD retains supervised training on GT data as a structural scaffold, it adds a reinforcement learning objective using Self-Critical Sequence Training (SCST). In this loop, a frozen synthesizer provides feedback: the decomposer is rewarded based on the synthesizer's cross-entropy loss on the target program. This forces the decomposer to prioritize subgoals that the specific, bounded synthesizer finds easy to solve, rather than subgoals that merely look like human-written examples.
The study reveals an 'accuracy paradox': models that achieve higher agreement with human GT decompositions often perform worse at actual program synthesis. SAD consistently outperforms solver-blind baselines across multiple PBE domains, including in challenging length-generalization tasks. Crucially, the authors show that SAD can solve tasks where a GT-decomposition oracle fails, providing empirical evidence that GT decompositions are not universally optimal and that decomposition quality is relative to the solver's capabilities.
This work challenges the implicit assumption that structural similarity to human data is the best proxy for performance in modular AI systems. By demonstrating that decomposition should be optimized for downstream 'usability' rather than imitation, the authors provide a new paradigm for training hierarchical models where the components have different, but interacting, inductive biases.
AI-generated third-party summary by ResearchPod. Not official content or an endorsement by the paper authors or affiliated organizations.