← 研踪 PaperTrailarXiv:2608.03461 · v3
Solver-Aware Decompositions for Programming-by-Example: When Dividing Requires Knowing How to Conquer
首次提交 2026-08-04 18:57
版本更新 2026-11-02 19:13
雷达观测 2026-11-04 23:42
摘要
Decomposition-based Programming-by-Example splits a task into subtasks: a decomposer predicts intermediate subgoals, and a learned synthesizer generates a program for each subgoal. Execution-decomposition approaches train the decomposer to imitate ground-truth (GT) subgoals and thereby treat decomposition quality as a property of the task alone. A learned synthesizer, however, has its own inductive biases, and GT subgoals reflect how the annotator factorized the task, not what this synthesizer can solve. A decomposer that imitates them can therefore propose subgoals that are logically valid but intractable for the synthesizer. Motivated by this observation, we propose Solver-Aware Decompositions (SAD), which keeps supervised training on GT subgoals as a structural scaffold and additionally trains the decomposer online with self-critical policy gradients against a frozen synthesizer. Each sampled subgoal is rewarded with the negative cross-entropy of the synthesizer on the target program, a continuous signal of how difficult the subtask is for this synthesizer. Our experiments show an accuracy paradox: with the synthesizer fixed, a GT-supervised decomposer agrees more often with the GT subgoals, yet its subgoals lead to lower synthesis accuracy, although the synthesizer was trained on the same GT data. On two list-processing domains, SAD improves synthesis and task accuracy over the GT-supervised decomposer, both in-distribution and under length generalization; the same holds under zero-shot transfer to an external benchmark and for a fine-tuned language model. Even an oracle that receives the GT subgoals at inference time, with the same synthesizer and search, fails on tasks that SAD solves, and fewer than 2% of SAD's solutions to these tasks match the GT program. Decomposition quality is therefore not a property of the task: it depends on the synthesizer that executes the subgoals.
作者备注：Accepted at NeurIPS 2026
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v3 · 2026-11-02 19:13 · 最新观测版本
Solver-Aware Decompositions for Programming-by-Example: When Dividing Requires Knowing How to Conquer
Decomposition-based Programming-by-Example splits a task into subtasks: a decomposer predicts intermediate subgoals, and a learned synthesizer generates a program for each subgoal. Execution-decomposition approaches train the decomposer to imitate ground-truth (GT) subgoals and thereby treat decomposition quality as a property of the task alone. A learned synthesizer, however, has its own inductive biases, and GT subgoals reflect how the annotator factorized the task, not what this synthesizer can solve. A decomposer that imitates them can therefore propose subgoals that are logically valid but intractable for the synthesizer. Motivated by this observation, we propose Solver-Aware Decompositions (SAD), which keeps supervised training on GT subgoals as a structural scaffold and additionally trains the decomposer online with self-critical policy gradients against a frozen synthesizer. Each sampled subgoal is rewarded with the negative cross-entropy of the synthesizer on the target program, a continuous signal of how difficult the subtask is for this synthesizer. Our experiments show an accuracy paradox: with the synthesizer fixed, a GT-supervised decomposer agrees more often with the GT subgoals, yet its subgoals lead to lower synthesis accuracy, although the synthesizer was trained on the same GT data. On two list-processing domains, SAD improves synthesis and task accuracy over the GT-supervised decomposer, both in-distribution and under length generalization; the same holds under zero-shot transfer to an external benchmark and for a fine-tuned language model. Even an oracle that receives the GT subgoals at inference time, with the same synthesizer and search, fails on tasks that SAD solves, and fewer than 2% of SAD's solutions to these tasks match the GT program. Decomposition quality is therefore not a property of the task: it depends on the synthesizer that executes the subgoals.
查看此版本解读 →查看此版本原文 ↗