Research map / Optimization / Optimizers
On the Hardness of Probabilistic Neurosymbolic Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies the complexity of differentiating weighted model counting for probabilistic neurosymbolic learning, proves hardness and tractability during training, and proposes WeightME, an unbiased gradient estimator based on weighted model sampling.
Problem
Gradients of probabilistic logical reasoning (weighted model counting) are needed to train probabilistic neurosymbolic models, but exact and approximate gradient computation is #P-hard and approximating with PAC guarantees is NP-hard in general.
Approach
Shows gradient approximation becomes tractable once a single implicant dominates the WMC (as network outputs become confident); introduces WeightME, an unbiased estimator built on weighted model sampling that needs only a constant (or logarithmic-in-SAT-calls) number of samples for (epsilon, delta) guarantees.
Key results
- WeightME attains the highest average gradient cosine similarity on all benchmarks at initialization (e.g., 0.784 on MCC2021, 0.955 on ROAD-R), above product t-norm (0.643 and 0.918).
- SFE (interpretation sampling) achieves near-zero cosine similarity (0.035 on MCC2021, 0.006 on ROAD-R), since it usually fails to sample a model.
- In optimization experiments on 33 easy MCC instances, none of the tested polynomial approximation methods consistently optimizes the log-likelihood, even with 90% concept supervision.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use WeightME instead of the Product t-norm | gradient estimation · MCC2021 | cosine similarity: 0.643 ± 0.259 -> 0.784 ± 0.248 | Helped |
| use WeightME instead of the Product t-norm | gradient estimation · MCC2022 | cosine similarity: 0.592 ± 0.188 -> 0.721 ± 0.259 | Helped |
| use WeightME instead of the Product t-norm | gradient estimation · MCC2023 | cosine similarity: 0.537 ± 0.310 -> 0.821 ± 0.172 | Helped |
| use WeightME instead of unweighted model sampling | gradient estimation · ROAD-R | cosine similarity: 0.946 ± 0.014 -> 0.955 ± 0.009 | Helped |
| use unweighted model sampling instead of WeightME | gradient estimation · MCC2022 | cosine similarity: 0.721 ± 0.259 -> 0.578 ± 0.332 | Hurt |
| use polynomial approximation methods to optimize formula log-likelihood | biased gradient approximation methods · 33 easy Model Counting Competition instances | log-likelihood optimization | Hurt |
| add 90% accurate concept supervision | biased gradient approximation methods · 33 easy Model Counting Competition instances | negative log-likelihood | Helped |
Surprising findings
- Biased polynomial approximations such as the product t-norm and Gumbel-Softmax struggle to optimize even on instances where exact solving is feasible.
- Gradient variance is a misleading metric here: estimators can achieve low variance by returning zero gradients.
Limitations
- Experiments use only propositional CNF benchmarks; first-order neurosymbolic systems are not studied.
- DNF formulas are not considered, though they admit tractable approximation.
- Results depend on the chosen benchmarks and may not generalize to all neurosymbolic tasks.
Experimental setup
Datasets: MCC2021 benchmarks MCC2022 benchmarks MCC2023 benchmarks ROAD-R
Benchmarks: MCC2021 MCC2022 MCC2023 ROAD-R MNIST-addition
Metrics: cosine similarity between approximate and exact gradient runtime maximum log-likelihood achieved during optimization
Baselines: Interpretation sampling (SFE) IndeCateR Product t-norm Godel t-norm Straight-through estimator Gumbel-Softmax Semantic strengthening k-best (MPE) k-optimal Unweighted model sampling I-MLE
Builds on: REINFORCE / score function estimator IndeCateR CMSGen d4 knowledge compiler hash-based approximate model counting
Closest papers by meaning
- On the Independence Assumption in Neurosymbolic Learning (ICML 2024 · similarity 0.91)
- EM-NeSy: Expectation Maximization for Neurosymbolic Learning (NeurIPS 2026 · similarity 0.87)
- Right for the Right Reasons: Avoiding Reasoning Shortcuts via Prototypical Neurosymbolic AI (NeurIPS 2025 · similarity 0.86)
- The Gradient of Algebraic Model Counting (AAAI 2025 · similarity 0.86)
- Neurosymbolic Reinforcement Learning: Playing MiniHack with Probabilistic Logic Shields (AAAI 2025 · similarity 0.85)
- Relational Neurosymbolic Markov Models (AAAI 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.