Where to Approximate in Neurosymbolic Inference?

Samy Badreddine, Emile van Krieken, Luciano Serafini, Antonio VergariarXiv 2026 · arXiv

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):

  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.
  2. 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.
  3. Step III (Final Reduction): If multiple circuits remain, combine them using an independence assumption.
Figure 1: Where can we approximate when compiling structured-decomposable circuits? We unify bottom-up approaches in a three-step pipeline: (Step I) compiles each factor ϕj into an exact or relaxed circuit, (Step II) multiplies the resulting N circuits down to K exactly or using recom- pression strategies, and (Step III) combines any K > 1 remaining circuits with an independence (fuzzy) approximation. Existing methods correspond to specific combinations of exact or approximate operations, but the framework also allows for new TT-based APRICOT strategies yet to be explored.

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.

Visualizing Tensor Train operations: (a) a single factor, (b) exact multiplication, and (c) recompression via TT-ROUND.

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 MNISTAdd or CLEVR-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.
Pareto front showing APRICOT (blue/violet/green) achieving much lower error than SDD-based methods (yellow) on Sudoku.
Learning performance: APRICOT (green line) maintains high accuracy on complex tasks where fuzzy methods (pink line) degrade.

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

Abstract

Probabilistic neurosymbolic methods rely on weighted model counting (WMC) to combine neural predictors with symbolic constraints. Exact WMC is #P-hard and typically scales poorly, so many methods resort to approximations. By unifying existing approaches under a three-step bottom-up approximate compilation pipeline, we study where approximation budget is best allocated. Inspired by tensor networks, we instantiate two steps with tensor train decompositions and derive new pipelines that exactly multiply approximated factors and recompress their products via SVD- or interpolation-based schemes. Across six tasks in Sudoku, arithmetic reasoning, and scene understanding, and across increasing problem sizes, our pipelines produce WMC estimates orders-of-magnitude more accurate than prior methods. This translates into stronger downstream learning on tasks where reasoning relies on tight interactions between symbolic factors, where cruder approximations ignore these dependencies. Our pipelines open novel design space for effective approximate compilation of challenging probabilistic reasoning tasks.
BibTeX
@misc{badreddine2026where,
  author = {Samy Badreddine and Emile van Krieken and Luciano Serafini and Antonio Vergari},
  title = {{Where to Approximate in Neurosymbolic Inference?}},
  year = {2026},
  eprint = {2611.13862},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.13862},
}
Figure