This paper addresses a fundamental bottleneck in neurosymbolic (NeSy) AI: how to efficiently combine neural network predictions with hard symbolic constraints. When we ask a model to solve a Sudoku or perform multi-digit arithmetic, we need to compute the Weighted Model Count (WMC)—the probability that the neural "perceptions" satisfy the logical rules.
The catch? Exact WMC is #P-hard. It doesn't just scale poorly; it hits a brick wall. This paper, "Where to Approximate in Neurosymbolic Inference?", provides a systematic map of the approximation landscape and introduces a powerful new toolkit called APRICOT.
TL;DR
The authors introduce a unified three-stage pipeline for approximate neurosymbolic inference, showing that approximating symbolic factors using Tensor Train (TT) decompositions is far superior to standard "fuzzy" independence assumptions. Their framework, APRICOT, produces WMC estimates that are orders-of-magnitude more accurate than prior methods and scales to massive problems, like 9x9 Sudoku, that are currently impossible for exact compilers.
What Problem Does This Paper Address?
Neurosymbolic systems aim to get the best of both worlds: the perception of deep learning and the reasoning of symbolic logic. However, the "reasoning" part usually involves knowledge compilation—turning logic into a computational circuit.
For complex problems, these circuits grow exponentially. To stay tractable, most researchers resort to "fuzzy" approximations that assume different parts of the logic are independent. The authors demonstrate that these independence assumptions are often disastrously wrong, sometimes missing the true probability by 24 orders of magnitude. The core question is: If we have to approximate to stay fast, where and how should we do it to maintain accuracy?
Methods
The authors propose a unified three-step bottom-up compilation pipeline (see Figure 1):
- Step I (Factor Compilation): Compile individual logical factors (e.g., "this cell must be different from that cell") into circuits. APRICOT uses TT-SVD to represent these as low-rank Tensor Trains.
- Step II (Multiplication & Recompression): Multiply these factors together. To prevent the representation from exploding, APRICOT uses "rounded multiplication"—algebraic schemes like TT-ROUND or HATT that compress the product back down to a manageable size.
- Step III (Final Reduction): If multiple circuits remain, combine them using an independence assumption.
The key innovation is the use of Tensor Trains (TTs). TTs are a type of tensor network that can represent high-dimensional data (like a Sudoku constraint) very compactly. By performing "recompression" during the multiplication phase, APRICOT preserves the dependencies between variables that fuzzy methods simply throw away.
Datasets
The authors evaluated their framework across six diverse tasks:
- Sudoku (4x4, 6x6, 9x9): Used for both unweighted model counting and visual classification/completion.
- MNISTAdd & MNISTMul: Predicting the sum or product of two multi-digit numbers from images.
- CLEVR-Diff & CLEVR-CountDiff: Scene understanding tasks requiring the model to reason about object attributes (e.g., "are all objects different?").
Key Insights and Ideas
- Independence is a "Crude" Approximation: In Sudoku, assuming factors are independent leads to massive errors because the constraints are tightly coupled.
- The "Where" Matters: Approximating at the factor level (Step I) and product level (Step II) is much more effective than waiting until the end to apply a fuzzy independence assumption (Step III).
- Auxiliary Variables are the Stress Test: Tasks like arithmetic use "carries"—hidden variables that link different parts of the problem. Fuzzy methods fail here because they can't enforce that a carry "produced" by one digit matches the carry "received" by the next. APRICOT handles this by keeping these variables jointly marginalized within the tensor structure.
Key Results
- Inference Accuracy: On 9x9 Sudoku, APRICOT achieved a Pareto front of accuracy vs. time that far surpassed existing methods. While exact compilers (like SDDs) failed to even finish, APRICOT provided estimates with very low log-error.
- Downstream Learning: In tasks with complex dependencies (like
MNISTAddorCLEVR-CountDiff), the superior inference of APRICOT translated directly into better training. It matched exact compilation where feasible and significantly outperformed fuzzy baselines as problem sizes grew.
Limitations and Future Work
The authors note that current TT recompression algorithms (like TCI and RSI) are general-purpose and not specifically optimized for the sparse, Boolean tensors found in logic. Future work could involve developing "logic-aware" tensor decompositions. Additionally, they suggest further study into how different ways of writing a program (factorization) impact the success of these approximate methods.
Summary updated