Relational Decomposition for Program Synthesis - Céline Hocquette

The way a problem is represented can determine whether it is solvable at all.

Céline Hocquette, AI researcher at Ndea and former postdoctoral researcher at the University of Oxford, discusses her paper “Relational Decomposition for Program Synthesis”, which introduces a representation-driven approach to inductive program synthesis based on decomposing examples into relational facts.

The paper emerged from Hocquette’s long-standing engagement with inductive logic programming (ILP), beginning with her doctoral work at Imperial College London under Stephen Muggleton and continuing through her time in Andrew Cropper’s group in Oxford. Motivated by the scalability limits of learning long chains of reasoning, the work reflects a broader intellectual trajectory focused on making symbolic learning systems more efficient by rethinking representation and decomposition rather than adding domain-specific heuristics.

In This Episode -

• Inductive logic programming (ILP)

• Deductive vs. inductive program synthesis

• Relational vs. functional programs

• Decomposing examples into logical facts

• Datasets: ARC-AGI, 1D-ARC, strings, list functions

• Systems & approaches: POPPER, ARGA, METABIAS, BEN, Hacker-Like

References -

• https://github.com/logic-and-learning-lab/Popper

• https://andrewcropper.com/

• ARC-AGI - https://arcprize.org/arc-agi

• 1D-ARC - https://arxiv.org/abs/2305.18354

• ARGA - https://arxiv.org/abs/2210.09880

• METABIAS - https://www.doc.ic.ac.uk/~shm/Papers/ECAI-546.pdf

• BEN - https://arxiv.org/abs/2301.03094

• Hacker-Like - https://www.nature.com/articles/s41467-024-50966-x

About the Paper -

“Relational Decomposition for Program Synthesis”

Céline Hocquette, Andrew Cropper

arXiv, 2024

The paper proposes transforming inductive program synthesis problems into sets of relational input–output facts, allowing systems to learn smaller, reusable logical rules instead of long functional compositions. This decomposition significantly improves scalability and generalization when learning programs from few examples across strings, lists, and ARC-style reasoning tasks.

https://arxiv.org/abs/2408.12212

About the Guest -

Céline Hocquette, Technical Staff at Ndea, works on program synthesis, inductive logic programming, and symbolic reasoning. She completed her PhD at Imperial College London and previously held a research position at the University of Oxford in Andrew Cropper’s lab. Her work focuses on scalable learning of interpretable programs from small data.

https://celinehocquette.github.io/

Credits -

• Host & Music: Bryan Landers, Technical Staff, Ndea

• Editor: Alejandro Ramirez

• https://x.com/ndea

• https://x.com/bryanlanders

• https://ndea.com