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

Oct 5, 2026

DPNL: A DPLL-based Algorithm for Probabilistic Neurosymbolic Learning

Probabilistic Neurosymbolic Learning (PNL) combines neural predictions with symbolic reasoning, enabling end-to-end learning from final-output supervision without labels for intermediate concepts. A central challenge is probabilistic inference: state-of-the-art approaches often rely on materializing the logical provenance of a query, which can itself become a major computational bottleneck. We introduce Dynamic Probabilistic Neurosymbolic Learning (DPNL), an oracle-guided framework that avoids requiring complete provenance materialization before inference. DPNL lazily explores the space of intermediate assignments, while oracles resolve entire regions that can already be certified to produce or exclude the target output. We establish conditions ensuring soundness and termination. ApproxDPNL extends the same search with early termination while maintaining certified bounds on the exact output probability, providing controlled approximation guarantees. The oracle interface decouples inference from the representation of the symbolic component, enabling problem-specific reasoning within the same framework. Experiments on several neurosymbolic tasks show that DPNL and ApproxDPNL substantially extend the range of problem instances tractable by probabilistic neurosymbolic inference.
Jun 12, 2026

EM-NeSy: Expectation Maximization for Neurosymbolic Learning

Neurosymbolic (NeSy) models integrate neural networks and symbolic reasoning for robust and interpretable AI. State-of-the-art NeSy models require that the symbolic component is expressed in a differentiable way, often complicating the use of approximate inference. We propose EM-NeSy which casts probabilistic NeSy learning as an instance of the Expectation-Maximization (EM) algorithm. In the expectation step, we compute the posterior over the neurally predicted symbols conditioned on the label via probabilistic inference. In the maximization step, we update the neural parameters based on this posterior using gradient descent only through the neural component. This formulation unlocks the full potential of the EM algorithm for NeSy learning. It allows NeSy to extend naturally to approximate reasoning without any additional modifications or differentiability requirements of the symbolic component. Furthermore, it recovers the standard end-to-end gradient-based NeSy setting under exact inference. Our experimental results demonstrate the scalability and computational efficiency of EM-NeSy.
Jul 5, 2026

Forethought: Verifiable Reasoning from Neurosymbolic Primitive Programming

Modern agentic workflows decompose user requests into sequences of tool calls with correctly resolved parameters, the results of which are processed through reasoning traces in the language model's context window. The prevailing route to improving such reasoning is test-time scaling, which trains models to search over long chains of thought; but the resulting capability is entangled in model weights, cannot be checked step by step, and is costly at inference. We present Forethought, a neurosymbolic reasoning system built from a library of symbolic and neural primitives composed through a typed domain-specific language. The results are reasoning programs: concrete representations of the model's work, in which every step carries an output contract that is checked at design time and enforced at execution time. Symbolic steps hold by construction, while learned steps are contract-checked and empirically validated, giving an explicit boundary between what is guaranteed and what is measured. Instantiated as a tool-calling execution kernel and evaluated on four standard tool-calling benchmark suites, Forethought improves end-to-end accuracy by a median of 32% relative to prompting the same base model directly, and reaches the highest aggregate accuracy among the evaluated configurations, though only by a margin within single-run noise over a frontier model. Systems pairing small open models with Forethought's fixed small-model layer match that frontier model, and a pipeline with a non-reasoning responder outperforms its reasoning sibling while requiring only a single fine-tuning stage. Removing the contract-and-control layer erases most of these gains, showing that checked structure, not decomposition alone, drives the improvement. Our results show the potential of rich symbolic orchestrators for building language-model agents that are more accurate, reliable, and auditable.