Technical Summary: ADVENT – LLM-Driven Automatic Predicate Invention for ILP

1. Problem Statement

Inductive Logic Programming (ILP) is a machine learning paradigm capable of learning human-interpretable relational rules. However, its performance is heavily constrained by the quality of predefined Background Knowledge (BK). Without suitable predicates, ILP systems cannot discover rules that explain target concepts effectively. Predicate Invention (PI) addresses this by introducing auxiliary predicates to extend the hypothesis space.

Existing PI approaches face two fundamental limitations:

1. Search Space Explosion: Without human guidance, PI devolves into exhaustive syntactic enumeration, making it difficult to automatically discover helpful patterns.
2. Lack of Semantics: Traditional methods operate via syntactic symbol manipulation, producing unnamed predicates (e.g., inv1, inv2) that lack conceptual understanding. This hinders the assessment of relevance for new tasks and prevents effective cross-task knowledge reuse or lifelong learning.

While Large Language Models (LLMs) offer potential for recognizing implicit patterns and generating meaningful predicate definitions, relying solely on LLM reasoning introduces reliability issues, including syntactic violations and overfitting to specific examples.

2. Methodology: ADVENT

The authors propose ADVENT, a neuro-symbolic framework that integrates LLM abductive reasoning with Prolog deductive verification within an ILP pipeline. The system operates on a triadic reasoning cycle (Abduction, Deduction, Induction) across four stages:

A. Representation Check (RC)

Before attempting invention, a lightweight heuristic determines if the current BK is sufficient.

• Mechanism: The system samples 10% of examples and uses 1% as "seeds" for a restricted variable-level search.
• Logic: If the ILP learner can only produce ground unit clauses (covering only the seed) without finding variable-level generalizations, the system triggers the invention loop. If RC passes, the system skips invention and proceeds to rule induction.

B. LLM-PI Loop (Iterative Invention)

When RC fails, an iterative loop begins:

1. Abductive Generation (LLM): The LLM receives the BK schema, a sample of positive/negative examples, and a Knowledge Pool (a list of previously invented predicates with names and definitions). It is prompted to identify implicit patterns and propose candidate predicates with Prolog definitions, arities, and usage modes.
2. Deductive Verification (Prolog): Proposed predicates undergo two layers of validation:
   • Syntactic/Structural Check: Prolog attempts to consult the definition to catch runtime errors or undefined predicates.
   • Behavioral Check: The predicate is executed on a subset of examples. Results are partitioned by class (positive vs. negative) and presented contrastively to the LLM.
3. Refinement: Based on the concrete execution results (e.g., false positives/negatives), the LLM refines the predicate definition. This loop continues until a maximum iteration limit is reached or a valid predicate is found.

C. ILP Rule Induction

Once RC confirms that generalizable patterns exist (either initially or post-invention), the ILP learner (Aleph) performs rule induction.

• The invented auxiliary predicates are injected into the BK.
• The ILP system performs a constant-level search, grounding variables to specific values to capture instance-level distinctions, complementing the LLM's high-level inventions.

D. Knowledge Pool & Cross-Task Reuse

Successful invented predicates and learned rules accumulate in a Knowledge Pool. For subsequent tasks, this pool serves as a reference, allowing the LLM to assess relevance and compose new predicates from prior inventions, supporting cumulative learning.

3. Key Contributions

1. ADVENT Framework: A novel mechanism that pairs LLM abductive generation with Prolog deductive verification to automate predicate invention in ILP.
2. Formal Verification Integration: The integration of a Prolog-based verifier that provides concrete deductive results to guide LLM refinement, addressing the reliability gap in LLM-generated logic.
3. Interpretable Cross-Task Reuse: Demonstration that LLMs can interpret invented predicate definitions to assess relevance, enabling selective reuse and composition of knowledge across tasks while maintaining human interpretability.

4. Experimental Results

The framework was evaluated on nine poker-hand concepts (mapped to the Michalski Train problem to obscure domain knowledge) using seven different LLMs.

• ILP Baseline: ILP alone failed entirely (0/9) in a position-free relational setting and achieved only 6/9 in a position-dependent setting.
• LLM-Driven PI (No Verification): Achieved an average success rate of 58% across models, demonstrating that LLMs can identify implicit patterns (e.g., variable inequality, arithmetic sequences) inaccessible to syntax-driven search.
• Formal Verification (ADVENT): Raising the average success rate to 80%. The confidence intervals did not overlap with the no-verification condition, confirming that Prolog verification effectively guides refinement.
• Comparison with Self-Critique: Formal verification outperformed LLM self-critique in 5 out of 7 models. Self-critique was less reliable, sometimes leading to overfitting on superficial features.
• Knowledge Pool Impact: Utilizing the knowledge pool increased success rates by up to +31 percentage points for compositional concepts (e.g., Straight Flush, Royal Flush). However, for simpler tasks (e.g., Flush), the pool introduced unnecessary complexity, resulting in a slight performance drop, indicating a trade-off between reuse and interference.

5. Significance and Claims

The paper claims that ADVENT offers a promising direction for automating predicate invention and enabling cross-task knowledge reuse in ILP.

• Bridging the Gap: It successfully bridges the gap between the symbolic rigor of ILP and the semantic understanding of LLMs, allowing the system to invent predicates with meaningful names (e.g., has_duplicate_rank) rather than opaque symbols.
• Reliability: The study validates that grounding LLM outputs in formal deductive execution is superior to self-assessment for refining logic programs.
• Limitations: The authors modestly acknowledge current limitations, including the reliance on the LLM's context window for managing the knowledge pool (which may dilute attention as the pool grows) and the evaluation being limited to a transformed poker-hand domain. Future work is proposed to develop selective retrieval mechanisms and test on broader real-world datasets.