# Relational decomposition for program synthesis

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 49 references that are in the map.
- First posted on arXiv 22 Aug 2024.

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

- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [Large Language Models as General Pattern Machines](https://mlsanity.com/paper/2307.04721/) (2023)
- [RobustFill: Neural Program Learning under Noisy I/O](https://mlsanity.com/paper/1703.07469/) (2017)
- [Hypothesis Search: Inductive Reasoning with Language Models](https://mlsanity.com/paper/2309.05660/) (2023)
- [Write, Execute, Assess: Program Synthesis with a REPL](https://mlsanity.com/paper/1906.04604/) (2019)
- [Inductive logic programming at 30: a new introduction](https://mlsanity.com/paper/2008.07912/) (2020)
- [LLMs and the Abstraction and Reasoning Corpus: Successes, Failures, and the Importance of Object-based Representations](https://mlsanity.com/paper/2305.18354/) (2023)
- [Learning programs by learning from failures](https://mlsanity.com/paper/2005.02259/) (2020)
- [Learning to Infer and Execute 3D Shape Programs](https://mlsanity.com/paper/1901.02875/) (2019)
- [Code Repair with LLMs gives an Exploration-Exploitation Tradeoff](https://mlsanity.com/paper/2405.17503/) (2024)
- [Graphs, Constraints, and Search for the Abstraction and Reasoning Corpus](https://mlsanity.com/paper/2210.09880/) (2022)
- [Few-Shot Bayesian Imitation Learning with Logical Program Policies](https://mlsanity.com/paper/1904.06317/) (2019)
- [Making sense of sensory input](https://mlsanity.com/paper/1910.02227/) (2019)
- [One Model for the Learning of Language](https://mlsanity.com/paper/1711.06301/) (2017)
- [Discovering State and Action Abstractions for Generalized Task and Motion Planning](https://mlsanity.com/paper/2109.11082/) (2021)
- [CrossBeam: Learning to Search in Bottom-Up Program Synthesis](https://mlsanity.com/paper/2203.10452/) (2022)
- [Generalized Planning for the Abstraction and Reasoning Corpus](https://mlsanity.com/paper/2401.07426/) (2024)
- [Learning logic programs by combining programs](https://mlsanity.com/paper/2206.01614/) (2022)
- [A Divide-Align-Conquer Strategy for Program Synthesis](https://mlsanity.com/paper/2301.03094/) (2023)
- [Program Synthesis with Best-First Bottom-Up Search](https://mlsanity.com/paper/2310.04327/) (2023)

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

- [Combining Induction and Transduction for Abstract Reasoning](https://mlsanity.com/paper/2411.02272/) (2024)
- [Tackling the Abstraction and Reasoning Corpus with Vision Transformers: the Importance of 2D Representation, Positions, and Objects](https://mlsanity.com/paper/2410.06405/) (2024)
- [Shedding Light in Task Decomposition in Program Synthesis: The Driving Force of the Synthesizer Model](https://mlsanity.com/paper/2503.08738/) (2025)
- [Vector Symbolic Algebras for the Abstraction and Reasoning Corpus](https://mlsanity.com/paper/2511.08747/) (2025)
- [An Empirical Comparison of Cost Functions in Inductive Logic Programming](https://mlsanity.com/paper/2503.07554/) (2025)
- [From Global to Factor-Wise Expert Composition in Discrete Diffusion Models](https://mlsanity.com/paper/2607.11758/) (2026)

## Abstract (arXiv)

We introduce a relational approach to program synthesis. The key idea is to decompose synthesis tasks into simpler relational synthesis subtasks. Specifically, our representation decomposes a training input-output example into sets of input and output facts respectively. We then learn relations between the input and output facts. We demonstrate our approach using an off-the-shelf inductive logic programming (ILP) system on four challenging synthesis datasets. Our results show that (i) our representation can outperform a standard one, and (ii) an off-the-shelf ILP system with our representation can outperform domain-specific approaches.