acceptodds
Under review as a conference paper at ICLR 2027

A Logically Complete Model Family for Gradient-Based Rule Learning

Abstract

Inductive Logic Programming (ILP) learns logical rules from data, forming an interpretable machine learning model. Neuro-symbolic ILP is an emerging area where logical rules are discovered via gradient-based learning. However, existing models are limited to constrained language biases, hampering further applicability for complex rules. In this work, we propose a neuro-symbolic ILP model family that is logically complete for Horn rules. Our model relaxes all syntactically correct rules into continuous spaces and estimates the gradient to search for the semantically correct solutions. In particular, the gradient involves direct learning of logical variables, which is intractable in existing models. Experiments on standard benchmarks and recently proposed benchmarks with complex rules show that our model outperforms existing methods and LLMs.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
Inductive Logic Programming, Differentiable Inductive Logic Programming, Neuro-Symbolic AI

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_xw24OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper introduces a differentiable ILP system (gradient-based rule learning). The system parametrizes Horn rules using embeddings that are mapped to distributions over head atoms, body atoms and logical variables. Unlike existing systems, the system is logically complete for Horn rules.

Critical strengths

The method empirically outperforms the evaluated existing gradient-based rule learners.

The method seems to support richer rules than most differentiable ILP systems (e.g. supporting predicates of arbitrary arity).

Critical weaknesses

The paper is difficult to read. The notation is dense, and the main text lacks examples.

There are problems with the experiments. First, the experimental and reproducibility details are mostly delegated to the code. The appendix should provide enough details regarding these, as code may become unavailable in the future. Second, it is a weakness that the paper does not compare empirically to non-differentiable rule learners.

The contribution / novelty is insufficiently positioned with respect to differentiable propositional rule learners. For instance, Debot et al. [1] already represent rules as embeddings that are mapped to factorized distributions over symbolic literals, they also evaluate rules symbolically, and extract discrete rules by argmax. This is all similar to what the proposed method does. A major difference is that this method extends these ideas to first-order rules, but it should clearly position this extension relative to propositional differentiable rule learners. There may be other works like [1] that I am not aware of that also use similar ideas.

[1] Debot et al. Interpretable concept-based memory reasoning. NeurIPS 2024.

Questions for authors

See weaknesses above.

Reviewer_QX4XOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes the Horn Rule Network (HRN), a neuro-symbolic inductive logic programming framework that learns function-free Horn-rule programs through gradient-based optimization over a parameterized distribution of discrete rule structures.

Given background facts, positive and negative target examples, and a set of symbolic hyperparameters, HRN constructs rules by probabilistically selecting head atoms, subsets of body atoms subject to cardinality constraints, and logical-variable assignments for individual argument positions. The sampled programs are evaluated through symbolic forward chaining, with balanced accuracy serving as the reward. The model employs a nested REINFORCE gradient estimator to optimize the sampling distribution and subsequently extracts deterministic, interpretable rules.

The paper's principal contributions include a fine-grained parameterization that supports direct learning of variable-binding structures, a constructive expressivity result establishing completeness for finite sets of function-free Horn rules, an unbiased gradient estimator that removes irrelevant variable assignments, and a sampling procedure for cardinality-constrained body-atom selection.

Experiments on standard ILP benchmarks and the higher-arity GeoILP benchmark demonstrate improvements over several existing neuro-symbolic approaches and the evaluated LLM baselines.

Critical strengths

1. Expressive and fine-grained representation of Horn-rule structures

A major strength is the ability to represent atom selection, multiple occurrences of the same predicate, and variable assignments at individual argument positions within a unified stochastic framework.

Variable binding determines how different relational atoms are connected through shared logical variables. Consequently, directly learning these binding structures constitutes a substantive extension of the representational space, rather than merely increasing the number of learnable predicate-selection parameters.

Together with the constructive completeness result, this provides a principled route toward reducing dependence on restrictive, hand-designed rule templates.

2. Coherent integration of stochastic program search and explicit symbolic execution

Another strength is the separation between learning a distribution over discrete programs and executing the sampled programs through symbolic forward chaining.

This avoids requiring the logical execution procedure itself to be differentiable with respect to discrete variable assignments.

The authors develop specialized components for this formulation, including cardinality-constrained body-atom sampling, nested gradient estimation, and the removal of irrelevant variable assignments while preserving unbiasedness.

The resulting framework retains explicit symbolic execution and produces inspectable rules. The experimental results provide initial evidence that this combination is practically useful.

Critical weaknesses

1. Insufficient justification of the embedding parameterization, parameter separation, and stochastic factorization

The model introduces multiple sets of predicate, argument, logical-variable, HEAD/BODY, and atom embeddings, together with learnable projection matrices, to parameterize categorical and Bernoulli distributions.

Although some parameter-sharing and separation decisions have intuitive motivations arising from the symbolic roles of the corresponding objects, these requirements do not uniquely determine the proposed parameterization.

For example, the same discrete action space could be parameterized directly using free categorical and Bernoulli logits, without explicitly enumerating complete candidate programs.

Consequently, the current evidence makes it difficult to isolate whether the reported performance improvements primarily arise from the broader rule language, the fine-grained action-space design, the embedding-based parameter sharing, or the particular gradient-estimation procedure.

The expressivity construction demonstrates that the chosen parameterization is sufficiently expressive, but does not independently establish that it is preferable to simpler alternatives in terms of optimization efficiency or generalization.

Furthermore, the independence assumptions in Section 4.2.5 simplify the probabilistic representation, whereas the correctness of a program can depend on highly coordinated choices across many variables.

A clearer justification of this factorization, including its trade-offs between computational simplicity and coordinated exploration, would strengthen the methodological contribution.

It would also be helpful to distinguish independence among sampled random variables from coupling induced by shared learnable parameters.

2. Limited analysis of the optimization challenges connecting representational capacity to reliable program discovery

The proposed method optimizes a distribution over many local stochastic choices using rewards computed from complete programs.

However, the paper does not sufficiently characterize the optimization challenges arising from coordination among variable assignments, sparse or uninformative rewards, sampled rules that fail to derive useful facts, and premature concentration on suboptimal structures.

The sensitivity analyses in Appendix D are valuable. In particular, the observed performance deterioration when increasing the maximum number of body atoms or the number of auxiliary predicates suggests that increasing expressive capacity does not necessarily improve learnability.

Nevertheless, these phenomena are primarily attributed to greater optimization difficulty, without sufficiently identifying the underlying bottlenecks.

Another related concern is the distinction between optimizing the expected reward over sampled programs and extracting a single deterministic program.

A high expected reward does not automatically guarantee that the extracted program performs equally well, particularly when multiple explanations are compatible with the observations or when the learned distribution has not concentrated sufficiently.

The paper would benefit from clarifying which properties are theoretically guaranteed, which are empirically observed, and whether the intended objective is to discover any high-performing program or to recover a particular underlying rule system.

These concerns do not imply that unique identification or global convergence is required. Rather, they concern whether the empirical evidence adequately characterizes the reliability of the proposed learning procedure.

Questions for authors

Overall

The overall quality of the paper is good, hence in the first round of reviewing I am giving a 3 score. However, there are some issues need to be further discussed to improve the overall soundness.

Q3, Q4 and partially Q7 are questions that I think are important, and providing more explanation on these topics would be very beneficial and I will raise my score accordingly if they are discussed. Other questions are interesting but not that important / directly relevant to the topic, hence the authors are not required to answer them all.

Question

Q1. Clarification: What is the precise boundary between the predefined symbolic language and the learned rule system?

Could the authors explicitly distinguish the predefined symbolic vocabulary, the learnable program structure, and the fixed logical inference semantics?

In particular, how are the number of universal meta-rules, the variable budget, maximum body size, multiplicity, and the number and arities of auxiliary predicates selected for each benchmark?

Are these settings determined through a uniform procedure independent of the final evaluation, or do they rely on prior knowledge about the structure of the target solution?

Although Section 4.1 describes the specification of auxiliary predicates and their arities, it would be useful to understand how much structural prior information is introduced through these capacity choices in the actual experiments.

This clarification is important for interpreting the scope of automatic rule discovery and the claim of reduced dependence on expert-defined rule templates.

Q2. Clarification: How do the CWA/OWA assumptions correspond to the data semantics and learning objective?

Section 4.2.2 distinguishes CWA and OWA modes primarily through whether background predicates are permitted in rule heads.

Could the authors clarify which parts of the background knowledge are assumed complete and which may be missing?

In particular, how are negative target examples constructed under the OWA setting, and how does the evaluation avoid treating unknown facts as false when the underlying knowledge is incomplete?

Does the proposed OWA mode primarily allow the model to infer additional background facts through learned rules, or does it introduce other mechanisms for handling incomplete knowledge?

Clarifying this distinction would help establish that the evaluation protocol is consistent with the intended semantics of incomplete background knowledge.

Q3. Evidence/Ablation: Why is embedding-based parameterization preferable to directly learning the distribution parameters?

Have the authors considered a baseline that retains the same atom candidates, variable budget, body-size constraints, symbolic executor, and sampling budget, but directly learns categorical and Bernoulli logits instead of using the proposed embedding-based scores?

Such a comparison would help separate the benefits of the expressive action space from those of the embedding factorization.

If the main advantages arise from parameter sharing, capacity control, or improved optimization geometry, it would be valuable to provide evidence supporting these mechanisms.

Additionally, the atom-scoring branch contains a linear projection followed by an inner product:

(Wca)⊤ν=ca⊤(W⊤ν),(Wc_a)^\top\nu=c_a^\top(W^\top\nu),

where (cac_a) denotes the concatenated embeddings.

This suggests that, considered in isolation, the projection and query vector can be combined into an effective parameter vector.

How should the role of this factorization be interpreted, particularly in light of the sensitivity to atom embedding dimensions?

Q4. Clarification/Evidence: What motivates the specific parameter separation and independence assumptions?

Could the authors distinguish between parameter-separation decisions that are necessary to preserve symbolic expressivity and those introduced primarily for modeling convenience or optimization?

For instance, allowing different occurrences of the same predicate to have different argument assignments appears important for representing general rules. However, this requirement does not uniquely determine the proposed embedding and parameter-sharing scheme.

More broadly, what motivates the independence assumptions among argument assignments, among different meta-rules, and between atom and variable choices?

Since program correctness often requires coordinated assignments across multiple argument positions, how does the proposed factorization facilitate the discovery of such joint structures?

Are there empirical observations indicating that shared embeddings improve coordination, or that failures are associated with difficulties in learning the required joint binding patterns?

Q5. Clarification: How does the proposed training procedure correspond to standard REINFORCE, and what objective is actually optimized?

My understanding is that the distribution over atom and variable assignments can be interpreted as a structured policy, a complete sampled program as an action, symbolic forward chaining as the evaluator, and balanced accuracy as the reward.

Under this interpretation, the framework resembles a structured one-step policy-gradient problem rather than an RL system that selects new actions at each iteration of forward chaining.

Could the authors clarify this correspondence and identify which components constitute the main methodological differences from standard score-function estimation?

Furthermore, does the implementation strictly follow the estimator in Equation 7, or are additional techniques employed, such as reward baselines, reward normalization, gradient clipping, or other variance-reduction mechanisms?

Section 4.5 mentions an entropy regularization coefficient (λ\lambda), whereas Equation 6 presents only the expected reward. Could the authors specify the complete objective actually used during training, including the entropy term, its scope, and any scheduling strategy?

It would also be helpful to explain how the atom and variable sample sizes (NaN^a) and (NvN^v) are selected.

These details are particularly important for interpreting the exploration behaviour and reproducing the optimization results.

Q6. Evidence/Ablation: What are the principal sources of optimization difficulty as the symbolic search space grows?

As the number of argument positions, candidate logical variables, body atoms, rule slots, and auxiliary predicates increases, which factors dominate the optimization difficulty?

Potential explanations include a decreasing probability of sampling useful programs, difficulties in assigning credit to individual stochastic choices, increased gradient variance, and higher symbolic execution costs.

It would be particularly informative to provide a small number of targeted diagnostics, such as the fraction of sampled programs that derive useful target facts, reward and entropy trajectories, or success rates under matched computation budgets.

Comparisons with simple random search or a more direct REINFORCE baseline over the same action space, where feasible, could further clarify whether performance improvements arise primarily from the representation of the search space or from the proposed learning strategy.

Importantly, I would not assume that optimization difficulty necessarily increases monotonically with the number of logical variables. The dependence structure of the reward and the degree of coordination required among local choices may be equally important.

A more systematic account of these factors could help explain the different sensitivity patterns observed in Appendix D.

It would also be useful to distinguish variability in final performance across random seeds from the variance of the gradient estimator at a fixed parameter setting.

Q7. Clarification/Evidence: What convergence behaviour is observed, and how does the method handle multiple compatible explanations?

Section 4.3 suggests that the learned distributions are expected to collapse to, or approximate, deterministic distributions.

What empirical evidence supports this behaviour?

In particular, could the authors distinguish between numerical convergence of model parameters, concentration of the sampling distribution, and stability of the final extracted program?

If multiple distinct rule systems explain the same training examples, what behaviour is expected from HRN?

Is the objective simply to discover any rule system that satisfies the observations, or is there an intended notion of recovering a particular underlying explanation?

Across different random seeds, do the learned programs mainly differ through semantically equivalent variable renamings, or can they yield genuinely different predictions on unseen examples?

Have the authors observed cases in which the sampling distribution remains diffuse while the extracted program is stable, or cases in which expected sampled-program performance differs substantially from extracted-program performance?

Q8. Clarification: How is forward chaining implemented, and which program representation is used in the final evaluation?

Does the implementation execute forward chaining until no additional facts can be derived, as described by the fixed-point formulation in Section 3.2, or does it impose a finite deduction-depth limit?

If a depth limit is used, how is it selected, and is it consistent across training and evaluation?

It would also be helpful to distinguish the number of optimization iterations, the number of Monte Carlo samples, and the number of forward-chaining rounds, since these correspond to different computational costs.

Finally, do the reported benchmark results evaluate the single deterministic program extracted according to Section 4.4, individual sampled programs, or an aggregation of predictions from multiple sampled programs?

This distinction is important because the training objective evaluates expected performance over a distribution of programs, whereas the final intended output is an interpretable symbolic rule system.

Clarifying the evaluation target would establish more directly which empirical results support the quality of the final extracted programs.

Q9. Writing

The overall writing quality is good and human like. However, Section 4.2 is a bit confusing as multiple notations are introduced at once. The presentation could be benefited from adding visualizations in the appendix to more clearly show the corresponding relationships between notations and the objects, so as the formulations.

Another useful addition would be an explicit distinction between what is specified and what is learned. The predicate vocabulary, predicate arities, number of rule slots, maximum number of body atoms, variable budget, multiplicity, and number and arities of auxiliary predicates are specified in advance. In contrast, the concrete atom selections, variable assignments, and continuous parameters are learned.

This distinction is important for interpreting the generality of the proposed method: HRN learns concrete rule systems within a predefined symbolic language rather than learning logical semantics themselves.

Reviewer_Ltd8OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper introduces the Horn Rule Network (HRN), a neuro-symbolic Inductive Logic Programming (ILP) framework designed to learn function-free Horn rules without relying on restrictive, hand-crafted rule templates or narrow language biases (e.g., limiting predicates to unary/binary arity or rule bodies to at most two atoms). To overcome the non-differentiability of discrete forward chaining with respect to logical variables, HRN embeds predicates, arguments, variables, and universal meta-rules into continuous spaces and models atom and variable unifications probabilistically. The model is trained by maximizing expected balanced accuracy via a nested REINFORCE gradient estimator paired with a linear-time conditional sampling algorithm for bounded body atoms. Theoretical proofs establish HRN's logical completeness for finite sets of Horn rules and the unbiasedness of its gradient estimator, while experiments on standard ILP tasks and the high-arity GeoILP benchmark show superior performance over existing neuro-symbolic baselines and LLMs.

Critical strengths
  1. Meaningful and Important Problem Formulation
  2. Novelty of Direct Variable Unification via Stochastic Relaxation
  3. Sound Algorithmic Innovations in Constrained Sampling and Gradient Estimation
  4. Strong Empirical Gains and Memory Scalability on High-Arity Benchmarks
Critical weaknesses
  1. Trade-off Between Differentiable Deduction and Black-Box REINFORCE Variance While the paper pitches HRN as a gradient-based neuro-symbolic model, it abandons differentiable forward chaining entirely. Instead, discrete rules are sampled, passed into a black-box symbolic ForwardChaining operator, and scored via non-differentiable balanced accuracy using REINFORCE. Since classical forward chaining yields a sparse, step-function reward, policy gradient methods without a learned baseline or control variate suffer from severe gradient variance and sample inefficiency as the search space grows.

  2. Omission of Modern Symbolic ILP Baselines and Incomplete Benchmark Evaluation

  1. Missing Symbolic Baselines: The introduction notes that modern symbolic ILP solvers (e.g., Popper / MDL-based Popper by Cropper & Morel 2021a; Hocquette et al. 2024) handle noisy data and arbitrary arities, and HRN directly borrows its symbolic hyperparameter parameterization (B, V) from them. Yet no symbolic ILP solvers are included in Table 1 or Table 2.
  2. Restricted Scope on GeoILP: The authors only evaluate on 12 basic-level tasks from GeoILP. It is unclear how many total tasks or higher difficulty tiers exist in GeoILP (Chen et al., 2025) and why they were omitted.
  1. Limited Novelty of Using REINFORCE for Rule Structure Optimization The high-level idea of using REINFORCE to optimize discrete rule structures over a non-differentiable symbolic engine is standard and somewhat incremental compared to genuinely differentiable forward-chaining methods. Rather than differentiating through logical deduction, HRN treats forward chaining as a black-box reward function.
Questions for authors

See the comments above.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.