Solver-Aware Decomposition Improves Programming-by-Example Synthesis

Programming-by-Example (PBE) systems often rely on decomposing complex tasks into simpler subtasks, which are then solved by a learned synthesizer. Traditionally, the decomposer is trained to mimic human-annotated "ground-truth" subgoals. However, this approach can lead to a paradox where logically valid decompositions are still intractable for the specific solver. Researchers propose Solver-Aware Decomposition (SAD), a training framework that moves beyond mere imitation of ground-truth data. SAD incorporates direct feedback from the synthesizer during training, rewarding subgoals based on how easily the synthesizer can achieve the target program. This means the decomposer learns to generate subgoals that the solver can actually "conquer," even if they deviate from human-defined optimal paths. Experiments demonstrate that SAD consistently improves synthesis and end-to-end task accuracy across different PBE domains. Crucially, it shows that higher agreement with ground-truth decompositions does not necessarily lead to better synthesis success, highlighting that decomposition quality is relative to the solver's capabilities, not an intrinsic property of the task itself.