Research map / Probabilistic and scientific modeling / Variational and generative sampling
A Fast Convoluted Story: Scaling Probabilistic Inference for Integer Arithmetics
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.
Proposes PLIA_t, a tensorised differentiable framework for exact probabilistic linear integer arithmetic that uses FFT convolution in the log domain, yielding orders-of-magnitude faster inference and neurosymbolic learning.
Problem
Exact probabilistic inference over integer-valued random variables is #P-hard and existing methods (knowledge compilation, enumeration) scale poorly; discrete integers also make gradient-based learning difficult in neurosymbolic settings.
Approach
Represent bounded probabilistic integers as tensors of log-probabilities, compute the distribution of sums via FFT convolution (convolution theorem) with a log-conv-exp trick for numerical stability, and express linear operations (constant add/multiply, negation, division, modulo, branching) as tensor manipulations, making everything differentiable.
Key results
- On the first three exact-inference benchmarks PLIA_t reaches domain size 2^24 with under 100 s on CPU and about 1 s on GPU, while Dice takes about 1000 s at 2^15, a speedup on the order of 10^5.
- On MNIST addition with N=50 digits, PLIA_t trains in a median 11.98 minutes with 43.00% accuracy, while DeepProbLog, Scallop and A-NeSI all time out (A-NeSI times out at N=50, Scallop at N=15).
- On visual sudoku G=9, PLIA_t reaches 63.00% accuracy in 6.39 minutes versus 61.50% for A-NeSI at 134.86 minutes; Scallop and DeepProbLog time out.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use tensorized probabilistic integer arithmetic with FFT-based inference instead of Dice's logical-circuit inference | Exact inference for sums of probabilistic integers · Expected value, negative-sum probability, and zero-sum probability benchmarks | inference time: 10^5 | Helped |
| Use tensor representations instead of logical circuits | Probabilistic Luhn checksum inference · Luhn sequences of length 350 | inference time: 10^2 | Helped |
| Use PLIA_t instead of competing neurosymbolic methods | MNIST Addition · N=2, N=4, N=15, and N=50 | training time | Helped |
| Use PLIA_t instead of competing neurosymbolic methods | MNIST Addition · N=2 | accuracy | Mixed |
| Use PLIA_t instead of competing neurosymbolic methods | MNIST Addition · N=4 | accuracy | Hurt |
| Use PLIA_t instead of competing neurosymbolic methods | MNIST Addition · N=15 | accuracy | Helped |
| Use PLIA_t instead of competing neurosymbolic methods | Visual Sudoku · G=4 | accuracy | Hurt |
| Use PLIA_t instead of competing neurosymbolic methods | Visual Sudoku · G=9 | accuracy | Helped |
| Use PLIA_t instead of competing neurosymbolic methods | MNIST Addition and Visual Sudoku · Reported benchmark sizes | predictive accuracy | No clear effect |
| Use a categorical encoding rather than the binary linear-arithmetic encoding (ablation) | Scallop and A-NeSI · Visual Sudoku | runtime | Helped |
| Increase Scallop top-k from lower candidate settings to k=3 (ablation) | Scallop · MNIST Addition, settings that did not time out | runtime | Helped |
| Increase Scallop top-k to k=6 (ablation) | Scallop · Visual Sudoku | runtime | Helped |
Surprising findings
- Dice can outperform PLIA_t on GPU for very small bitwidths due to GPU overhead, though CPU PLIA_t is on par or better there.
Limitations
- Exact inference still grows super-polynomially with recursive expression depth since domain sizes grow (#P-hard in general).
- Memory on CPU was not properly profiled.
- Dice outperforms PLIA_t on GPU for small problem sizes due to overhead.
Experimental setup
Datasets: MNIST visual sudoku
Benchmarks: MNIST addition visual sudoku probabilistic Luhn checksum Dice integer arithmetic benchmarks
Metrics: inference time training time (minutes) test accuracy memory usage
Baselines: Dice DeepProbLog Scallop A-NeSI
Builds on: Dice DeepProbLog log-sum-exp trick
Closest papers by meaning
- On the Hardness of Probabilistic Neurosymbolic Learning (ICML 2024 · similarity 0.84)
- KLay: Accelerating Arithmetic Circuits for Neurosymbolic AI (ICLR 2025 · similarity 0.84)
- CTSketch: Compositional Tensor Sketching for Scalable Neurosymbolic Learning (NeurIPS 2025 · similarity 0.84)
- An Efficient Matrix Multiplication Algorithm for Accelerating Inference in Binary and Ternary Neural Networks (ICML 2025 · similarity 0.84)
- The Gradient of Algebraic Model Counting (AAAI 2025 · similarity 0.84)
- IM-Unpack: Training and Inference with Arbitrarily Low Precision Integers (ICML 2024 · similarity 0.84)
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.