cs.LGNov 10, 2026

Where to Approximate in Neurosymbolic Inference?

Authors: Samy Badreddine, Emile van Krieken, Luciano Serafini, Antonio Vergari

Organizations: Sony AI · University of Trento · Vrije Universiteit Amsterdam · University of Edinburgh

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.

Figures & tables

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. DPNL: A DPLL-based Algorithm for Probabilistic Neurosymbolic Learning

    Oct 5, 2026Thomas Jean-Michel Valentin, Pierre Genev{è}s, Luisa Sophie Werner +3Probabilistic LogicNeurosymbolic Learning

  2. EM-NeSy: Expectation Maximization for Neurosymbolic Learning

    Jun 12, 2026Annegret Seibt, Luc De Raedt, Giuseppe MarraSymbolic ReasoningExpectation-Maximization

  3. Forethought: Verifiable Reasoning from Neurosymbolic Primitive Programming

    Jul 5, 2026Vishvesh Bhat, Emmanuel Anaya Gonzalez, Jay Vaghasiya +1Symbolic ReasoningEfficient Language Model Reasoning