Solver-Aware Decompositions for Programming-by-Example: When Dividing Requires Knowing how to Conquer

• URL: http://arxiv.org/abs/2608.03461v1
• Date: Tue, 04 Aug 2026 10:57:31 GMT
• Title: Solver-Aware Decompositions for Programming-by-Example: When Dividing Requires Knowing how to Conquer
• Abstract summary: Decomposition-based Programming-by-example (PBE) scales performance by splitting tasks into subtasks that a learned synthesizer solves.<n>Current approaches train the decomposer to imitate ground-truth ( GT) subgoals, implicitly treating decomposition quality as intrinsic to the task.<n>We propose Solver-Aware Decomposition (SAD), a training framework that retains supervised training on GT subgoals as a structural scaffold.
• Score: 8.770341884978981
• License: http://creativecommons.org/licenses/by/4.0/
• 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. 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.

Related papers

• PCTD: Preference-Guided Counterfactual Task Decomposition for Agent Tool Retrieval [32.19528642807244]
  Task decomposition aims to transform ambiguous instructions into executable atomic subtasks.<n>Rewards for task decomposition can easily induce reward hacking in reinforcement learning-based methods.<n>We propose PCTD, a Preference-guided Counterfactual Task Decomposition framework.
  arXiv  Detail & Related papers  (2026-07-17T07:15:41Z)
• LC-ERD: Mining Latent Logic for Self-Evolving Reasoning via Consistency-Regulated Reward Decomposition [55.572260012037084]
  We introduce LC-ERD (Logic-Consistent Endogenous Reward Decomposition), a framework framing self-alignment as latent structure mining.<n>We derive a Variational Logic Potential by aggregating consensus from the model's Latent Logic Expertise.<n>Experiments show LC-ERD delivers a robust self-evolution path, uncovering trade-offs between logic consistency and accuracy.
  arXiv  Detail & Related papers  (2026-05-19T07:27:50Z)
• CellScientist: Dual-Space Hierarchical Orchestration for Closed-Loop Refinement of Virtual Cell Models [62.281480231694]
  Virtual Cell Modeling (VCM) requires models that not only predict perturbation responses, but also support targeted revision when predictions fail.<n>Current LLM-assisted modeling face a refinement-routing problem: prediction discrepancies are observed through executable implementations.<n>We propose CellScientist, a dual-space hierarchical framework that couples a high-level hypothesis space with a low-level executable implementation space.
  arXiv  Detail & Related papers  (2026-05-08T06:40:24Z)
• How LLMs Fail and Generalize in RTL Coding for Hardware Design? [56.361436215029045]
  We introduce a new error taxonomy grounded in problem solvability, inspired by cognitive theory.<n>Our taxonomy categorizes failures into syntactic, semantic, solvable functional, and unsolvable functional types.
  arXiv  Detail & Related papers  (2026-04-26T14:34:49Z)
• Training LLMs for Multi-Step Tool Orchestration with Constrained Data Synthesis and Graduated Rewards [76.49428173793386]
  LLMs must invoke multiple dependent APIs in the correct order while propagating intermediate outputs.<n>Training models to handle such faces two obstacles: existing environments focus on simple per-turn function calls with simulated data, and binary rewards.<n>We present a framework addressing both challenges. First, we construct a reinforcement learning environment backed by a large-scale cache of real API responses, enabling a data synthesis pipeline that samples valid multi-step orchestration traces.<n>Second, we propose a graduated reward design that decomposes correctness into atomic validity and orchestration.
  arXiv  Detail & Related papers  (2026-03-25T18:31:39Z)
• Automated Skill Decomposition Meets Expert Ontologies: Bridging the Granularity Gap with LLMs [1.2891210250935148]
  This paper investigates automated skill decomposition using Large Language Models (LLMs)<n>Our framework standardizes the pipeline from prompting and generation to normalization and alignment with ontology nodes.<n>To evaluate outputs, we introduce two metrics: a F1-score that uses optimal embedding-based matching to assess content accuracy, and a hierarchy-aware F1-score that credits structurally correct placements to assess granularity.
  arXiv  Detail & Related papers  (2025-10-13T12:03:06Z)
• Automatic Rank Determination for Low-Rank Adaptation via Submodular Function Maximization [56.78271181959529]
  SubLoRA is a rank determination method for Low-Rank Adaptation (LoRA) based on submodular function.<n>Our method combines solid theoretical foundations, second-order accuracy, and practical computational efficiency.
  arXiv  Detail & Related papers  (2025-07-02T15:56:40Z)
• Shedding Light in Task Decomposition in Program Synthesis: The Driving Force of the Synthesizer Model [2.355460994057843]
  Task decomposition is a fundamental mechanism in program synthesis, enabling complex problems to be broken down into manageable subtasks.<n>In this work, we develop REGISM, an adaptation of ExeDec that removes decomposition guidance and relies solely on iterative execution-driven synthesis.<n>Our findings indicate that ExeDec exhibits significant advantages in length generalization and concept composition tasks, likely due to its explicit decomposition strategies.
  arXiv  Detail & Related papers  (2025-03-11T06:30:49Z)
• Efficient Reactive Synthesis Using Mode Decomposition [0.0]
  We propose a novel decomposition algorithm based on modes. The input to our algorithm is the original specification and the description of the modes. We show how to generate sub-specifications automatically and we prove that if all sub-problems are realizable the full specification is realizable.
  arXiv  Detail & Related papers  (2023-12-14T08:01:35Z)
• ExeDec: Execution Decomposition for Compositional Generalization in Neural Program Synthesis [54.18659323181771]
  We characterize several different forms of compositional generalization that are desirable in program synthesis. We propose ExeDec, a novel decomposition-based strategy that predicts execution subgoals to solve problems step-by-step informed by program execution at each step.
  arXiv  Detail & Related papers  (2023-07-26T01:07:52Z)
• Are Random Decompositions all we need in High Dimensional Bayesian Optimisation? [4.31133019086586]
  We find that data-driven learners of decompositions can be easily misled towards local decompositions that do not hold globally. A random tree-based decomposition sampler exhibits favourable theoretical guarantees that effectively trade off maximal information gain and functional mismatch between the actual black-box and its surrogate. Those results motivate the development of the random decomposition upper-confidence bound algorithm (RDUCB) that is straightforward to implement - (almost) plug-and-play.
  arXiv  Detail & Related papers  (2023-01-30T12:54:46Z)
• Inducing Transformer's Compositional Generalization Ability via Auxiliary Sequence Prediction Tasks [86.10875837475783]
  Systematic compositionality is an essential mechanism in human language, allowing the recombination of known parts to create novel expressions. Existing neural models have been shown to lack this basic ability in learning symbolic structures. We propose two auxiliary sequence prediction tasks that track the progress of function and argument semantics.
  arXiv  Detail & Related papers  (2021-09-30T16:41:19Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.