Relational Decomposition for Program Synthesis

Céline Hocquette, Andrew CropperIJCAI 2025 · DOI

TL;DR

This paper introduces a novel "relational decomposition" approach to program synthesis, breaking down complex tasks into simpler, relational subtasks. By representing input-output examples as sets of facts and learning relations between them, this method significantly outperforms standard representations and even rivals domain-specific approaches when used with a general-purpose Inductive Logic Programming (ILP) system.

What Problem Does This Paper Address?

Program synthesis aims to automatically generate computer programs from input-output examples. Traditional methods often struggle with learning complex programs that require long sequences of actions or functions. This is because the search space for such programs grows exponentially with their length, making them difficult and time-consuming to learn. The paper addresses this challenge by proposing a new way to represent synthesis tasks that simplifies the learning problem.

Methods

The core innovation is the "relational decomposition" of synthesis tasks. Instead of treating an entire input-output example as a single unit, the authors decompose each example into a set of "facts." For instance, a list [l, i, o, n] is represented as facts like in(1, l), in(2, i), etc., indicating the value at each position. Similarly, the output is also represented as facts. The program synthesis system then learns relational rules that map these input facts to output facts. This is achieved using an off-the-shelf Inductive Logic Programming (ILP) system, which is well-suited for learning relational rules. The key benefit is that learning these simpler relational subtasks is more tractable than learning a single, complex program.

Datasets

The paper evaluates its approach on four diverse and challenging datasets:

  • 1D-ARC: A one-dimensional adaptation of the Abstraction and Reasoning Corpus (ARC).
  • ARC: The standard Abstraction and Reasoning Corpus, which involves visual reasoning tasks.
  • Strings: A dataset for learning string transformation programs, derived from user-provided examples.
  • List functions: A dataset designed to evaluate the ability to identify functions that map input lists to output lists.

Key Insights and Ideas

  • Decomposition is Key: The fundamental insight is that breaking down a complex synthesis problem into smaller, relational subproblems dramatically simplifies the learning process.
  • Facts over Functions: Representing data as sets of facts rather than raw input/output structures allows for more flexible and generalizable learning.
  • ILP as a General Tool: The paper demonstrates that a general-purpose ILP system, when equipped with this relational representation, can achieve competitive or superior performance compared to highly specialized, domain-specific systems.
  • Compactness and Generalization: The decomposed representation leads to more compact programs (fewer rules, each with fewer literals), which, according to the Blumer bound, improves the likelihood of finding a correct and generalizable solution.
  • Implicit Concept Learning: The approach can learn concepts (like "rectangle" or "line") without explicit definitions, by learning rules that capture their relational properties.

Key Results

The paper presents strong empirical results supporting its claims:

  • Outperforming Standard Representations (Q1): The decomposed representation, when used with the POPPER ILP system, significantly outperforms standard undecomposed representations (UD-List, UD-Elem, UD-Str) across all four datasets and various learning time limits. For example, on the strings dataset, accuracy improved from 21% to 71%.
  • Competitive with Domain-Specific Approaches (Q2): The general-purpose ILP system with the decomposed representation is competitive with and often outperforms domain-specific systems. Notably, it surpasses ARGA on ARC, METABIAS on strings, and HL on list functions. For instance, on list functions, the decomposed approach achieved 52% accuracy compared to HL's 35%.
  • Efficiency: The decomposed approach often learns more compact programs, leading to faster and more effective learning.

Limitations and Future Work

  • Bias Simplicity: The authors acknowledge that their intentionally simple bias (raw input elements/pixels and basic arithmetic) is a limitation for certain tasks. They suggest that incorporating more domain-specific relations or general concepts like counting could further improve performance.
  • ILP System Limitations: While the representation is system-agnostic, the chosen ILP system (POPPER) sometimes struggles to find solutions within the given time limits, not due to the representation itself but due to the system's search capabilities. Future work could explore using more advanced ILP systems.
  • Future Directions: The authors suggest exploring the addition of general-purpose concepts like counting to the bias and investigating alternative ILP systems to leverage the benefits of their relational decomposition approach further.

Summary updated

BibTeX
@inproceedings{hocquette2025relational,
  author = {Céline Hocquette and Andrew Cropper},
  title = {{Relational Decomposition for Program Synthesis}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.24963/ijcai.2025/504},
}
Figure