When we want a machine to learn a computer program from examples, we face a fundamental combinatorial challenge. Traditional Inductive Logic Programming (ILP) searches for a set of logical rules that explain a dataset. However, if the system searches blindly through every possible combination of predicates, the number of potential programs explodes exponentially. This search space becomes entirely untractable when we ask the system to learn recursive definitions (programs that call themselves) or to invent entirely new sub-routines from scratch.
As surveyed by Andrew Cropper et al. in Turning 30: New Ideas in Inductive Logic Programming, modern symbolic AI overcomes this bottleneck through a framework known as Meta-Interpretive Learning (MIL). Instead of building programs from raw, low-level logical syntax, MIL uses higher-order structural blueprints to tightly constrain and guide the search.
Metarules as Inductive Blueprints
The core insight behind MIL is that while the specific logic of a program changes from task to task, the structural patterns of useful algorithms are often highly repetitive. MIL formalizes these patterns using metarules—higher-order logical templates that act as blueprints for valid rules.
To understand how a metarule works, consider a standard first-order logical rule like: $$\text{ancestor}(X, Y) \leftarrow \text{parent}(X, Z), \text{ancestor}(Z, Y)$$
In traditional ILP, a learner would have to discover this exact combination of predicates atom by atom. In contrast, an MIL system is given a higher-order template, such as the Chain Rule: $$P(X, Y) \leftarrow Q(X, Z), R(Z, Y)$$
In this template, $X$, $Y$, and $Z$ are standard first-order variables representing data objects. Crucially, $P$, $Q$, and $R$ are higher-order variables that represent predicates themselves. As emphasized by Zheng Zhang et al. in A Critical Review of Inductive Logic Programming Techniques for Explainable AI, these metarules dramatically prune the hypothesis space. The learner no longer asks "What random sequence of symbols should I write next?" but rather "Which existing predicates can I plug into the slots $P$, $Q$, and $R$ to satisfy this template?"
The Mechanics of Meta-Interpretive Proof Search
How does an MIL system actually determine the correct predicate assignments for these templates? It frames the learning process as a proof-search within a specialized meta-interpreter.
As outlined by Katsumi Inoue et al. in Inductive Logic Programming: Challenges, a meta-interpreter treats both the background logic rules and the training data as objects within a higher-order logic framework. When given positive and negative examples of a target concept, the meta-interpreter attempts to prove that the positive examples are true.
- Abduction and Unification: To complete the proof, the meta-interpreter fetches a metarule and attempts to unify its higher-order variables ($P, Q, R$) with actual predicates available in the background knowledge.
- Constraint Generation: Every time the meta-interpreter binds a higher-order variable to a predicate, it generates a hypothesis.
- Program Derivation: If the meta-interpreter successfully finds a set of predicate bindings that proves all positive examples while avoiding any negative ones, the proof concludes.
The authors of Ultra-Strong Machine Learning: comprehensibility of programs learned with ILP demonstrate that because this learning process is grounded in formal proof-search, the resulting programs are inherently human-readable and explainable, allowing AI systems to effectively act as transparent tutors for relational concepts.
Unlocking Recursion and Predicate Invention
The true power of framing program induction as a meta-interpretive proof-search is that it naturally solves the two hardest problems in program synthesis: recursion and predicate invention.
Natural Recursion
Because metarules can allow the same higher-order variable to appear in both the head and the body of a template (e.g., $P(X, Y) \leftarrow Q(X, Z), P(Z, Y)$), the meta-interpreter can naturally bind $P$ to the target predicate itself. As Andrew Cropper notes in The Automatic Computer Scientist, this bridges the gap between low-level logic and high-level algorithmic structures, making the discovery of complex recursive algorithms highly tractable from only a handful of examples.
Dynamic Predicate Invention
What happens if a complex task requires an intermediate concept that does not exist in the background knowledge? For instance, defining grandparent requires an intermediate concept of a parent.
During the proof-search, if the meta-interpreter cannot satisfy a metarule using existing predicates, it can dynamically invent a new predicate symbol (e.g., inv1). It then treats inv1 as a new object, using a separate metarule to define it. As shown by Céline Hocquette in Can Meta-Interpretive Learning outperform Deep Reinforcement Learning of Evaluable Game strategies?, this capability allows MIL to build up complex, hierarchical strategies from scratch.
Target Task: Find an ancestor strategy
│
├──► Apply Metarule: P(X,Y) <- Q(X,Z), R(Z,Y)
│ ├── Bind P to 'ancestor'
│ ├── Bind Q to 'parent'
│ └── Bind R to a brand new symbol: 'inv1' (Predicate Invention)
│
└──► Define 'inv1' recursively via another Metarule
└── 'inv1' becomes a reusable sub-routine
This capacity for hierarchical concept building allows agents to continuously refine symbolic world models online (Enrique Crespo-Fernandez et al., Continual learning and refinement of causal models through dynamic predicate invention) and discover reusable building blocks entirely through autonomous exploration or "play" (Andrew Cropper, Playgol: Learning Programs Through Play).
Optimizing and Scaling the Search
While metarules significantly narrow down the search space, scaling MIL to complex real-world domains requires optimizing how these templates are selected, evaluated, and managed.
Resource Efficiency over Textual Brevity
Traditional inductive learning often relies on Occam's Razor, favoring the shortest textual program. However, the shortest code is not necessarily the most computationally efficient. To address this, Andrew Cropper introduced systems like $Metagol_O$ (Learning Efficient Logic Programs), which alter the meta-interpreter's proof-search to optimize for resource efficiency (such as execution time or action costs) rather than mere textual length. This allows robotic agents to derive generalized strategies that minimize physical movement (Andrew Cropper et al., Learning Efficient Logical Robot Strategies Involving Composable Objects).
Scaling via Higher-Order Abstractions and Forgetting
As the library of background knowledge and invented predicates grows, the meta-interpreter can become bogged down by redundant options. To scale to thousands of sequential tasks, systems must learn to prune their own knowledge bases. In Forgetting to Learn Logic Programs, Andrew Cropper introduced the concept of intentionally "forgetting" redundant or underutilized predicates to keep the proof-search fast.
Furthermore, by expanding metarules to support higher-order abstractions like map and until, systems like $Metagol_{ho}$ can bypass complex first-order recursive logic entirely, synthesizing highly concise programs that manipulate other programs (Andrew Cropper et al., Learning Higher-Order Programs through Predicate Invention).
Neuro-Symbolic Integration
The latest frontier in scaling MIL involves combining the perceptual strengths of deep learning with the mathematical rigor of symbolic induction. For example, the ILP-CoT framework introduced by Yifei Peng et al. in Abductive Logical Rule Induction by Bridging Inductive Logic Programming and Multimodal Large Language Models uses Multimodal Large Language Models to look at raw data and propose the high-level structural metarules.
By allowing a neural network to guess the shape of the solution, the symbolic engine can bypass the combinatorial explosion of template selection entirely, focusing its exact mathematical proof-search only on the most plausible rule architectures.
Key Foundational Work
Inductive Logic Programming: Challenges (2016) — contributed 2 concept elements to this direction.
Learning Efficient Logic Programs (2015) — contributed 2 concept elements to this direction.
Learning Efficient Logical Robot Strategies Involving Composable Objects (2015) — contributed 1 concept elements to this direction.