Research map / Optimization / Optimizers
The Gradient of Algebraic Model Counting
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.
Generalizes gradients and backpropagation to arbitrary semirings within algebraic model counting, yielding a linear-time, memory-efficient algebraic backprop (Kompyle in Rust) and showing second-order algebraic gradients on tractable circuits are unlikely to be linear-time.
Problem
Learning in statistical-relational and neurosymbolic AI over logic formulas lacks a unified algebraic treatment; existing gradient/backprop implementations on circuits are memory- and time-inefficient, and second-order optimization on tractable circuits is unclear.
Approach
Defines the AMC gradient as the vector of algebraic conditionals to each literal, shows it is a semiring derivation basis, and gives a backpropagation over semirings that uses cancellation and ordering properties to avoid storing cumulative products, achieving O(e) time and O(n) memory without requiring a semifield.
Key results
- Kompyle computes the Prob-semiring algebraic gradient in 7.8 ms versus 7662 ms for PyTorch on average over 100 MC2021 instances.
- The dynamic-programming backprop is about 15x faster than naive backprop in the Prob semiring (19.8 ms vs 289.0 ms).
- Jax runs out of memory on the benchmark circuits in the Prob and Log semirings within 16GB.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add dynamic programming to backpropagation (ablation) | Kompyle · MC2021 competition track 2, Prob semiring | Time (ms): 19.8 ± 0.2 -> 7.8 ± 0.1 | Helped |
| Add dynamic programming to backpropagation (ablation) | Kompyle · MC2021 competition track 2, Bool semiring | Time (ms): 14.6 ± 0.1 -> 4.1 ± 0.0 | Helped |
| Add dynamic programming to backpropagation (ablation) | Kompyle · MC2021 competition track 2, Log semiring | Time (ms): 24.4 ± 0.2 -> 13.9 ± 0.4 | Helped |
| Add dynamic programming to backpropagation (ablation) | Kompyle · MC2021 competition track 2, Fuzzy semiring | Time (ms): 16.9 ± 0.1 -> 9.8 ± 0.3 | Helped |
| Use dynamic programming and semiring optimizations instead of naive backpropagation with cancellation (ablation) | Kompyle · MC2021 competition track 2, Prob semiring | Time (ms): 203.1 ± 0.8 -> 7.8 ± 0.1 | Helped |
| Use dynamic programming and semiring optimizations instead of naive backpropagation with cancellation (ablation) | Kompyle · MC2021 competition track 2, Bool semiring | Time (ms): 10.6 ± 0.0 -> 4.1 ± 0.0 | Helped |
| Use dynamic programming and semiring optimizations instead of naive backpropagation with cancellation (ablation) | Kompyle · MC2021 competition track 2, Log semiring | Time (ms): 167.0 ± 0.5 -> 13.9 ± 0.4 | Helped |
| Use dynamic programming and semiring optimizations instead of naive backpropagation (ablation) | Kompyle · MC2021 competition track 2, Prob semiring | Time (ms): 289.0 ± 1.3 -> 7.8 ± 0.1 | Helped |
| Use dynamic programming and semiring optimizations instead of naive backpropagation (ablation) | Kompyle · MC2021 competition track 2, Bool semiring | Time (ms): 10.9 ± 0.0 -> 4.1 ± 0.0 | Helped |
| Use dynamic programming and semiring optimizations instead of naive backpropagation (ablation) | Kompyle · MC2021 competition track 2, Log semiring | Time (ms): 238.0 ± 1.2 -> 13.9 ± 0.4 | Helped |
| Use dynamic programming and semiring optimizations instead of naive backpropagation (ablation) | Kompyle · MC2021 competition track 2, Fuzzy semiring | Time (ms): 174.7 ± 0.7 -> 9.8 ± 0.3 | Helped |
Surprising findings
- Second-order (Newton-style) preconditioned gradients cannot be computed in linear time on smooth, deterministic, decomposable circuits, unless matrix multiplication admits a faster circuit construction.
Limitations
- Second-order methods remain intractable on tractable circuits under the stated complexity results.
- Hessian-based results do not rule out specific non-field semirings being more favorable.
- Evaluation limited to a single benchmark set of compiled d-DNNF circuits with randomly generated weights.
Experimental setup
Datasets: 2021 Model Counting Competition (track 2) formulas
Benchmarks: MC2021 competition track 2 (100 formulas compiled with d4)
Metrics: runtime (ms) memory usage
Baselines: PyTorch Jax naive backpropagation naive + cancellation backpropagation (All-Marginals)
Builds on: algebraic model counting differentiable algebra (semiring derivations) IndeCateR d4 knowledge compiler
Closest papers by meaning
- Model Counting and Sampling via Semiring Extensions (AAAI 2024 · similarity 0.87)
- A Compositional Atlas for Algebraic Circuits (NeurIPS 2024 · similarity 0.86)
- Engineering an Exact Pseudo-Boolean Model Counter (AAAI 2024 · similarity 0.86)
- On the Hardness of Probabilistic Neurosymbolic Learning (ICML 2024 · similarity 0.86)
- Language Models Need Inductive Biases to Count Inductively (ICLR 2025 · similarity 0.85)
- Verification Learning: Make Unsupervised Neuro-Symbolic System Feasible (ICML 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.