Synthesizing Programs by Unifying Partial Solutions

16 concepts8 papers1 proposal

Program synthesis often feels like searching for a needle in a haystack. Traditional synthesis frameworks—such as standard Counter-Example Guided Inductive Synthesis (CEGIS) or monolithic sequence-to-sequence neural networks—attempt to generate a complete, global program that satisfies all specifications or input-output examples simultaneously.

As the complexity of a task grows, this monolithic approach hits a wall. The search space explodes exponentially, and a single edge case can invalidate an entire candidate program, forcing the search algorithm to restart or wander aimlessly through an astronomical space of code tokens.

To bypass this bottleneck, a powerful paradigm has emerged: divide-and-conquer program synthesis. Instead of demanding a single program that works for everything all at once, this strategy decomposes the synthesis task into smaller, manageable sub-problems, solves them independently to generate partial solutions, and then systematically unifies them into a valid global program.

Two Dimensions of Decomposition

How do you break a complex programming problem into smaller pieces? The literature reveals two primary strategies: partitioning the input space or decomposing the problem structure.

1. Input Space Partitioning (Per-Example Synthesis)

Instead of finding a program that satisfies all input-output pairs simultaneously, the synthesizer finds simple expressions that work for specific subsets of the inputs.

For instance, Alur et al. introduced the Synthesis Through Unification (STUN) framework, which explicitly separates the search into finding partial solutions for disjoint input subsets and then merging them.

In the neural network domain, Shrivastava et al. proposed N-PEPS, a method that first discovers "per-example" solutions. Because a program only needs to satisfy a single example, these fragments are incredibly easy to find and provide high-signal building blocks for the final program logic.

2. Structural and Specification Decomposition

Alternatively, a problem can be broken down by its logical components or execution steps.

In the context of spreadsheet string manipulation, Gulwani demonstrated that synthesis becomes highly efficient when decomposed into independent sub-problems like learning substrings, identifying loop patterns, and determining conditional logic.

For low-level code generation, Srinivasan et al. showed that complex machine code semantic specifications can be split into independent sub-formulas; the system synthesizes instruction sequences for each sub-formula and simply concatenates the results.

More recently, Zhao et al. leveraged component and variable elimination to isolate individual subtasks, simplifying the synthesis of intricate divide-and-conquer algorithmic paradigms.

The Unification Mechanism: Stitching the Pieces Together

Decomposition is only half the battle. The core magic of this paradigm lies in the unification phase—how independent, partial solutions are combined into a cohesive whole.

Decision-Tree Unification

When partial solutions are synthesized for specific subsets of the input space, the global program must route each incoming input to the correct partial solution. This is naturally modeled as conditional branching logic (if-then-else).

As highlighted in the 2016 and 2017 Syntax-Guided Synthesis Competitions (Alur et al.; Alur et al.), state-of-the-art solvers like EUSolver achieve massive performance gains by combining enumerative search with decision-tree learning. The solver finds simple terms that work for subsets of the specification, and then uses a machine learning decision-tree algorithm to automatically learn the branching conditions that glue those terms together.

               [ Input Space ]
                      |
             (Decision Condition)
             /                \
       [ True ]             [ False ]
         /                        \
[ Partial Solution A ]    [ Partial Solution B ]

Aggregators and Modifiers

When tasks are decomposed structurally rather than by input subsets, unification relies on grammatical or neural assembly rules.

Raza et al. designed a framework that uses an initialization phase to find small code snippets for sub-tasks, followed by a search phase that systematically explores combinations using explicit aggregator and modifier rules.

In deep learning contexts, Shrivastava et al. bypassed rigid rule-based combination by training a neural "Cross Aggregator" to intelligently stitch per-example fragments into a single global program.

Why It Works: Intuition Behind the Efficiency

Why does breaking a problem apart and unifying it later outperform searching for a complete solution directly?

  • Exponential to Linear Search Space Reduction: Searching for a single, complex program of length $N$ takes time exponential in $N$ ($O(B^N)$, where $B$ is the branching factor of the grammar). If a divide-and-conquer strategy splits the task into two independent sub-problems of length $N/2$, the search complexity drops to $O(B^{N/2}) + O(B^{N/2})$, a massive reduction in the size of the search space.
  • High-Signal Feedback: In a monolithic search, a candidate program that fails on 1 out of 100 examples provides very little structural feedback; it is simply marked "incorrect." By focusing on individual examples or sub-problems, the synthesizer receives clear, high-signal fragments that are guaranteed to be correct for at least a portion of the specification.
  • Separation of Concerns: Unification-based synthesis separates the problem of what computation to perform (handled by the partial solutions) from the problem of when to perform it (handled by the decision tree or aggregator). This modularity mirrors how human programmers naturally write code—tackling core logic and edge cases independently before wiring them together.

Key Foundational Work

Synthesis Through Unification (2015) — contributed 3 concept elements to this direction.
Synthesis of machine code from semantics (2015) — contributed 2 concept elements to this direction.
Automating string processing in spreadsheets using input-output examples (2011) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_divide_and_conquer_synthesis_a0bbac20,
  title = {divide-and-conquer synthesis},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/divide-and-conquer-synthesis/rdr_a0bbac20c14e4f3f88a0bde0d7256327},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_divide_and_conquer_synthesis_a0bbac20_v1,
  title = {divide-and-conquer synthesis},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/divide-and-conquer-synthesis/rdr_a0bbac20c14e4f3f88a0bde0d7256327/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake