Research map / Architectures and efficiency / RNNs and normalization
Solver-Aware Decompositions for Programming-by-Example: When Dividing Requires Knowing how to Conquer
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes SAD, which trains an ExeDec-style subgoal decomposer with supervised GT subgoals plus self-critical policy gradient using a frozen synthesizer's cross-entropy as reward, showing an "accuracy paradox" where higher GT alignment does not yield better synthesis.
Problem
Decomposition-based programming-by-example trains decomposers to imitate ground-truth subgoals, which may be logically valid yet intractable for a bounded learned synthesizer.
Approach
Optimize the decomposer online with self-critical policy gradients using the frozen synthesizer's cross-entropy on the GT program as reward, retaining supervised GT subgoal loss as a structural scaffold, so decompositions are judged by solver tractability rather than GT similarity.
Key results
- On Deepcoder length generalization, SAD achieves 79.8% synthesis accuracy vs 64.3% for solver-blind, while solver-blind has 63.3% decomposition accuracy vs 21.5% for SAD.
- On Lambdabeam zero-shot transfer to Rule et al. benchmark, SAD solves 42.3% of 129 tasks vs 33.0% for solver-blind.
- On RobustFill, SAD and solver-blind are statistically indistinguishable (94.1% vs 94.1% in-distribution), consistent with the falsifiability prediction.
Surprising findings
- Higher decomposition accuracy (GT alignment) does not translate into higher synthesis accuracy: the solver-blind baseline has 2-3x higher decomposition accuracy yet lower synthesis accuracy.
- SAD solves a consistent subset of tasks that a ground-truth decomposition oracle fails to solve under the same synthesizer and beam.
Limitations
- Decomposer must be retrained whenever the frozen synthesizer changes.
- Single-step training constraint fixes decomposition granularity; multi-step reward not modeled.
- Requires ground-truth programs at training time; not applicable to specification-only settings.
Experimental setup
Datasets: DeepCoder PBE tasks (generated) Lambdabeam PBE tasks (generated) RobustFill string tasks Rule et al. list-processing benchmark (zero-shot)
Benchmarks: DeepCoder Lambdabeam RobustFill Rule et al. list-processing benchmark
Metrics: task accuracy decomposition accuracy synthesis accuracy
Baselines: ExeDec solver-blind baseline GT decomposition oracle beam oracle
Builds on: ExeDec self-critical sequence training RobustFill DeepCoder
Closest papers by meaning
- HYSYNTH: Context-Free LLM Approximation for Guiding Program Synthesis (NeurIPS 2024 · similarity 0.85)
- ExeDec: Execution Decomposition for Compositional Generalization in Neural Program Synthesis (ICLR 2024 · similarity 0.85)
- Program Synthesis via Test-Time Transduction (NeurIPS 2025 · similarity 0.85)
- Primal Generation, Dual Judgment: Self-Training from Test-Time Scaling (NeurIPS 2026 · similarity 0.85)
- PEARL: Solver-in-the-Loop Interactive Optimization Modeling from Natural Language (NeurIPS 2026 · similarity 0.84)
- ReGAL: Refactoring Programs to Discover Generalizable Abstractions (ICML 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.