# A Divide-Align-Conquer Strategy for Program Synthesis

arXiv: https://arxiv.org/abs/2301.03094 · HTML: https://mlsanity.com/paper/2301.03094/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 25 references that are in the map.
- First posted on arXiv 8 Jan 2023.

## Builds on (most cited first, 3 of 3)

- [Write, Execute, Assess: Program Synthesis with a REPL](https://mlsanity.com/paper/1906.04604/) (2019)
- [Fast and flexible: Human program induction in abstract reasoning tasks](https://mlsanity.com/paper/2103.05823/) (2021)
- [Representing Partial Programs with Blended Abstract Semantics](https://mlsanity.com/paper/2012.12964/) (2020)

## Built on by (most cited first, 7 of 7)

- [Combining Induction and Transduction for Abstract Reasoning](https://mlsanity.com/paper/2411.02272/) (2024)
- [ARCLE: The Abstraction and Reasoning Corpus Learning Environment for Reinforcement Learning](https://mlsanity.com/paper/2407.20806/) (2024)
- [Relational decomposition for program synthesis](https://mlsanity.com/paper/2408.12212/) (2024)
- [Program Synthesis using Inductive Logic Programming for the Abstraction and Reasoning Corpus](https://mlsanity.com/paper/2405.06399/) (2024)
- [Abductive Symbolic Solver on Abstraction and Reasoning Corpus](https://mlsanity.com/paper/2411.18158/) (2024)
- [Beyond Either-Or Reasoning: Transduction and Induction as Cooperative Problem-Solving Paradigms](https://mlsanity.com/paper/2505.14744/) (2025)
- [Solver-Aware Decompositions for Programming-by-Example: When Dividing Requires Knowing how to Conquer](https://mlsanity.com/paper/2608.03461/) (2026)

## Abstract (arXiv)

A major bottleneck in search-based program synthesis is the exponentially growing search space which makes learning large programs intractable. Humans mitigate this problem by leveraging the compositional nature of the real world: In structured domains, a logical specification can often be decomposed into smaller, complementary solution programs. We show that compositional segmentation can be applied in the programming by examples setting to divide the search for large programs across multiple smaller program synthesis problems. For each example, we search for a decomposition into smaller units which maximizes the reconstruction accuracy in the output under a latent task program. A structural alignment of the constituent parts in the input and output leads to pairwise correspondences used to guide the program synthesis search. In order to align the input/output structures, we make use of the Structure-Mapping Theory (SMT), a formal model of human analogical reasoning which originated in the cognitive sciences. We show that decomposition-driven program synthesis with structural alignment outperforms Inductive Logic Programming (ILP) baselines on string transformation tasks even with minimal knowledge priors. Unlike existing methods, the predictive accuracy of our agent monotonically increases for additional examples and achieves an average time complexity of O(m) in the number m of partial programs for highly structured domains such as strings. We extend this method to the complex setting of visual reasoning in the Abstraction and Reasoning Corpus (ARC) for which ILP methods were previously infeasible.