arXiv：cs.AI· Janis Zenkner, Tobias Sesterhenn, Tim Grams, Christian Bartelt·· 4 小时前
Solver-Aware Decompositions：让分解器知道求解器如何求解的 PBE 框架
Solver-Aware Decompositions for Programming-by-Example: When Dividing Requires Knowing how to Conquer
AI 导读
针对基于分解的 Programming-by-Example 方法，论文提出 Solver-Aware Decomposition（SAD）训练框架：在保留 GT 子目标监督的同时，用策略梯度以冻结学习型合成器的交叉熵损失作为奖励在线优化分解器。
正文
Abstract: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. Execution-decomposition approaches such as ExeDec 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 online with policy gradients against a frozen learned synthesizer. Each sampled subgoal is rewarded by the synthesizer's cross-entropy loss on the target program - a continuous 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 and under zero-shot transfer to an external list-processing benchmark. Moreover, SAD solves tasks that a GT decomposition oracle fails - empirical evidence, under an identical synthesizer and search procedure, that GT decompositions are not universally optimal for bounded solvers.
| Comments: | Accepted at NeurIPS 2026 |
| Subjects: | Artificial Intelligence (cs.AI) |
| Cite as: | arXiv:2608.03461 [cs.AI] |
| (or arXiv:2608.03461v2 [cs.AI] for this version) | |
| https://doi.org/10.48550/arXiv.2608.03461 arXiv-issued DOI via DataCite |
Submission history
From: Janis Zenkner [view email]
[v1]
Tue, 4 Aug 2026 10:57:31 UTC (513 KB)
[v2]
Thu, 8 Oct 2026 14:06:46 UTC (514 KB)
来源：arXiv：cs.AI · arxiv.org