Semantic Probabilistic Layers for Neuro-Symbolic Learning

Problem

• SOP tasks involve mutually constrained labels, yet unconstrained or constraint-trained classifiers can produce inconsistent outputs at inference time, with costly implications in safety-critical applications.Examples include hierarchical multi-label classification, pathfinding, protein function prediction, interaction prediction, and drug discovery.Source: §1 · p. 1

Illustration

• Figure 1 contrasts invalid predictions from neural and Semantic Loss approaches with SPL’s guaranteed validity on a constrained Warcraft pathfinding task.The figure presents the lowest-cost path problem as an example of complex semantic SOP.Source: Figure 1 · p. 2

Limitations of prior work

• Existing approaches either fail to guarantee test-time consistency, support only restricted symbolic knowledge, or become intractable for moderately complex logical constraints.Differentiable constraint losses can improve learning but do not ensure consistency at test time.Source: §1 · p. 2

SPL contribution

• SPL is introduced as a drop-in predictive layer that models intricate label correlations, enforces prespecified logical constraints, and supports efficient inference and training.The layer is designed to preserve modularity while adding probabilistic and symbolic reasoning.Source: §1 · p. 2

Contributions

• SPL satisfies six stated desiderata—probabilistic semantics, expressivity, consistency, generality, modularity, and efficiency—while outperforming state-of-the-art neuro-symbolic approaches on challenging SOP tasks.The reported empirical scope includes hierarchical multi-label classification and pathfinding, with constraint compliance retained.Source: §1 · p. 2

Task setting

• A fully independent layer models each label separately given the embedding, which limits its ability to represent correlations and logical constraints.Its conditional distribution factorizes across labels, with each marginal computed using a sigmoid of a linear score.Source: §2 · pp. 2–3

Comparison

• Table 1 presents SPL as the only approach satisfying all six neuro-symbolic SOP desiderata.The paper positions this as a comparison against other popular neuro-symbolic approaches.Source: Table 1 · p. 3, §2 · p. 3

Task setting

• Neuro-symbolic SOP predicts L interdependent binary labels from neural embeddings, combining learned label dependencies with logical constraints supplied as formulas over labels and optionally discrete inputs.Examples include hierarchical label implications and paths restricted to edges in an input graph.Source: §2 · pp. 2–3

Design desiderata

• The six desiderata require sound normalized probabilities, expressive correlations, consistency, general logical constraints, modular replacement of neural predictive layers, and efficient computation.Together, these criteria define the target interface for constrained SOP prediction.Source: §2 · p. 3

SPL formulation

• SPL computes p(y | f(x)) as q_Θ(y | f(x)) multiplied by c_K(x,y) and divided by the partition function Z(x), where the constraint circuit is nonzero only for satisfying assignments.q_Θ represents an expressive label distribution, while c_K encodes the logical constraints.Source: §2 · p. 3
• The product circuit removes probability mass from inconsistent assignments, while normalization enables exact gradients and maximum-likelihood end-to-end learning through a neural network.This construction supports general propositional constraints and expressive joint distributions rather than independent label marginals.Source: §2 · p. 4

Efficiency and implementation

• Circuit-based marginalization computes the partition function in time linear in the product-circuit size, preserving efficient inference and consistent test-time MAP prediction.The displayed high-level design replaces a conventional predictive layer with probabilistic and constraint circuits whose product is normalized.Source: §2 · p. 4, Figure 2 · p. 4

3 Realizing SPLs with tractable circuit representations

• SPL represents an expressive conditional distribution and a logical constraint as circuits whose product restricts probability mass to valid label configurations.The probabilistic component qΘ models label distributions, while cK computes the constraint indicator and the partition function normalizes their product.Source: §3 · p. 4

3.1 Representing expressive distributions with probabilistic circuits

• Smooth, decomposable probabilistic circuits compactly encode expressive distributions and can be conditioned on neural features through a differentiable gating function.The gating function maps feature embeddings to circuit parameters, creating an interface between a feature extractor and the probabilistic circuit.Source: §3.1 · p. 5

3.2 Encoding logical formulas with constraint circuits

• Constraint circuits compute an indicator for whether each input-label assignment satisfies the logical formula, using deterministic sum units and indicator input functions.Logical representations such as OBDDs and SDDs can be translated into these circuits by replacing conjunctions with products and disjunctions with sums.Source: §3.2 · p. 6

3.3 Efficient inference in SPLs

• Compatible smooth and decomposable circuits evaluate SPL normalization in O(|q||c|) time, and determinism gives MAP inference in the same complexity.Compatibility requires matching decompositions for product units with the same scope, while alternative approximate MAP procedures are used for non-deterministic PCs.Source: §3.3 · p. 6
• Table 2 reports that SPLs outperform all loss-based competitors on the neuro-symbolic benchmarks while guaranteeing consistent predictions.The reported comparison concerns the reproduced simple path prediction and preference-learning benchmarks.Source: Table 2 · p. 7

3.4 A single-circuit SPL

• The single-circuit SPL parameterizes a deterministic constraint circuit directly, reducing two-circuit product and renormalization costs while retaining distributions supported on valid configurations.Compared with the two-circuit design, its capacity depends more strongly on constraint compilation; overparameterization can slow training and require approximate MAP inference.Source: §3.4 · p. 7

• Energy-based models capture higher-order label dependencies but typically sacrifice probabilistic semantics, efficiency, or support for hard constraints.Source: §4 · p. 7
• Loss-based methods cannot guarantee consistency at test time, while fuzzy-logic losses may also lack probabilistic soundness and syntax invariance.Source: §4 · pp. 7–8
• Table 3 emphasizes that valid SPL paths can have near-ground-truth costs even when competitors obtain higher Hamming scores with invalid predictions.Source: Table 3 · p. 8, §4 · p. 8
• Consistency-layer alternatives remain restricted: MultiplexNet supports only disjunctive normal form, while HMCCN relies on fuzzy-logic-representable constraints.Source: §4 · p. 8
• SPLs avoid solver calls for MAP inference or gradient computation and use conditional circuits that can parameterize richer distributions than independent-label approaches.Source: §4 · p. 8

• The evaluation reports exact-match accuracy, consistency, and Hamming score across standard neuro-symbolic SOP benchmarks, with SPL guaranteed to produce 100% consistent predictions.Source: §5 · p. 8

Simple path prediction & preference learning

• The simple-path dataset contains 1,600 examples generated from randomly sparsified 4 × 4 grids and split 60/20/20 across training, validation, and test sets.Source: §5 · pp. 8–9
• The preference-learning task predicts a strict total order over four unseen sushi types from preferences over six types, using data from 5,000 individuals.Source: §5 · p. 9
• SPL outperforms all competitors on simple path prediction and preference learning while guaranteeing consistent predictions.Source: §5 · p. 9

Warcraft Shortest Path

• SPL outperforms competitors by approximately +23% over FIL and +19% over SL, consistently delivering meaningful paths very close to ground-truth cost, even when routes differ substantially.Source: §5 · p. 9

Hierarchical Multi-Label Classification

• On 11 of 12 HMLC datasets, SPL significantly outperforms HMCNN in exact match and performs comparably on one, with nearly identical Hamming scores.Source: §5 · p. 9, Table 4 · p. 9

• SPLs integrate complex probabilistic reasoning and logical constraints on top of any neural-network classifier while retaining efficient inference and training.Source: §6 · p. 10
• They improve current state-of-the-art performance on challenging benchmarks including pathfinding and hierarchical multi-label classification.Source: §6 · p. 10
• Future directions include constraints spanning multiple networks, automatically learned constraints, integration with large language models, and human-in-the-loop learning.Source: §6 · p. 10

A Proofs

• Under smoothness, decomposability, compatibility, and determinism, SPL normalization and MAP inference both run in O(|q||c|) time.Source: A Proofs · p. 15
• Deterministic circuits permit MAP-state computation in linear time in circuit size, which gives the theorem’s MAP bound after constructing the product circuit.Source: A Proofs · p. 15
• The proof forms a product circuit in O(|q||c|) and then uses linear-time marginalization, yielding exact evaluation of the SPL normalization term.Source: A Proofs · p. 15

B Compiling logical formulas into circuits

• Bottom-up compilation combines Boolean sub-functions according to a variable ordering, using indicator, sum, and product units to represent satisfying assignments.Source: B Compiling logical formulas into… · pp. 15–16
• The compiled constraint circuit can be combined with label distributions to form a mixture over valid solutions, such as enforcing that cat or dog implies animal.Source: B Compiling logical formulas into… · pp. 16–17
• Compilation may produce circuits exponential in constraint size in the worst case, although repeated substructure can yield compact circuits in practice.Source: B Compiling logical formulas into… · p. 17

C Overparameterize the single-circuit SPL

• Replication averages multiple circuit copies, whereas mixture multiplication replaces one local marginal with k mixture models combined through cross-product rewiring.Both strategies add parameters beyond those available in the original constraint circuit.Source: C Overparameterize the single-circuit… · p. 17
• Although these strategies relax determinism, they do not change the distribution’s support, so every prediction remains consistent with the encoded constraint.Source: C Overparameterize the single-circuit… · p. 17

D.1 Simple path prediction and preference learning

• The simple path task predicts the unique shortest path in randomly sparsified 4 × 4 grids from source, destination, and subgraph inputs.The dataset contains 1,600 examples split 60/20/20 across training, validation, and test sets.Source: §D.1 · p. 17
• Preference learning predicts a strict total ordering over four unseen sushi types from each user’s preferences over six types, using data from 5,000 individuals.Source: §D.1 · p. 17
• The baselines use five-layer and three-layer MLPs with 50 hidden units per layer for path prediction and preference learning, respectively, with FIL and semantic-loss variants.Source: §D.1 · p. 18
• SPL hyperparameters are selected on validation performance by searching learning rates, overparameterization factors k ∈ {2, 4, 8}, and mixture counts m ∈ {2, 4, 8}.Source: §D.1 · p. 18

D.2 Hierarchical Multi-Label Classification

• The HMLC evaluation covers 12 real-world tasks across genomics, medical imaging, microalgae classification, and text categorization, with 56–4,130 output classes and sparse labels.Source: §D.2 · p. 18

D.3 Warcraft pathfinding

• The task predicts the minimum-cost path from the top-left to bottom-right grid vertices, with terrain types determining vertex costs.Source: §D.3 · pp. 18–19
• Unlike the prior setup, the model uses four-neighbor connectivity and predicts path edges rather than vertices to avoid ambiguous path encodings.Source: §D.3 · pp. 18–19
• Table 5 compares single-circuit SPL configurations using circuit copies m, gating layers, and overparameterization factor k, reporting exact-match percentages on HMLC validation sets.Source: Table 5 · p. 19
• The path constraint is compiled with Graphillion and restricted to paths shorter than 29, while SPL uses a two-circuit implementation with mixtures searched over {2, 4, 8}.Source: §D.3 · p. 19

D.4 A study on the effect of overparameterization in SPL

• The ablation varies circuit copies m, gating-function depth, and overparameterization factor k to study their effects on single-circuit SPL.Source: §D.4 · p. 19
• Across 12 HMLC datasets, larger mixture settings and at least four replicas generally improve exact-match performance, while two gating layers perform best on nine datasets.Source: §D.4 · p. 19
• SPL paths are always valid and can remain close in global cost to the ground truth even when they do not exactly match it, unlike some invalid baseline paths.Source: Figure 4 · p. 20