Solver-Aware Decompositions for Programming-by-Example: When Dividing Requires Knowing how to Conquer
Decomposition-based Programming-by-example (PBE) scales performance by splitting tasks into subtasks that a learned synthesizer solves: a decomposer predicts intermediate subgoals, and a synthesizer generates programs conditioned on them. Current approaches train the decomposer to imitate ground-truth ( GT) subgoals, implicitly treating decomposition quality as intrinsic to the task. We challenge this assumption: for bounded solvers with fixed inductive biases, GT decompositions reflect the annotator's factorization choices - not the solver's search dynamics. A decomposer trained to match GT decompositions may therefore propose subgoals that are logically valid yet intractable for the solver. We propose Solver-Aware Decomposition (SAD), a training framework that retains supervised training on GT subgoals as a structural scaffold, while additionally optimizing the decomposer via direct feedback from a frozen synthesizer. Subgoals are rewarded based on the synthesizer's loss on the target program - a signal of subtask difficulty that encourages decompositions the solver can act on. Our experiments reveal an accuracy paradox: higher agreement with GT decompositions does not improve synthesis success - even though the synthesizer was trained on the very same GT data the decomposer is optimized to mimic. SAD instead learns decompositions that trade GT alignment for solver tractability, yielding consistent gains in synthesis and end-to-end task accuracy across two PBE domains. Moreover, SAD solves tasks that a GT decomposition oracle fails - empirical evidence that GT decompositions are not universally optimal for bounded solvers, and that decomposition quality is solver-relative, not intrinsic.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
DynASP2.5: Dynamic Programming on Tree Decompositions in Action
A vibrant theoretical research area are efficient exact parameterized algorithms. Very recent solving competitions such as the PACE challenge show that there is also increasing practical interest in the parameterized alg…
Steiner Tree Problem"Model and Run" Constraint Networks with a MILP Engine
Constraint Programming (CP) users need significant expertise in order to model their problems appropriately, notably to select propagators and search strategies. This puts the brakes on a broader uptake of CP. In this pa…
On Dynamic Programming Decompositions of Static Risk Measures in Markov Decision Processes
Optimizing static risk-averse objectives in Markov decision processes is difficult because they do not admit standard dynamic programming equations common in Reinforcement Learning (RL) algorithms. Dynamic programming de…
Reinforcement Learning (RL)Approximately Optimal Core Shapes for Tensor Decompositions
This work studies the combinatorial optimization problem of finding an optimal core tensor shape, also called multilinear rank, for a size-constrained Tucker decomposition. We give an algorithm with provable approximatio…
Combinatorial OptimizationTractability and Decompositions of Global Cost Functions
Enforcing local consistencies in cost function networks is performed by applying so-called Equivalent Preserving Transformations (EPTs) to the cost functions. As EPTs transform the cost functions, they may break the prop…
ARC