CS Paper Radar

Where to Approximate in Neurosymbolic Inference?

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

cs.LG ·submitted 2026-11-10 10:22 UTC · v1
top venue

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.

Comment
Accepted to NeurIPS 2026

Closest papers

Nearest neighbours by meaning across the whole index.

DPNL: A DPLL-based Algorithm for Probabilistic Neurosymbolic Learning

cs.AI ·2026-10-05 ·Thomas Jean-Michel Valentin, Pierre Genev{è}s, Luisa Sophie Werner, Sarah Chlyah, Nabil Laya{ï}da +1 more
similarity 0.68
Abstract

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.

0.36

Challenges, Opportunities, and Misconceptions in Neurosymbolic AI

cs.AI ·2026-11-06 ·Giuseppe Marra, Pierre Genevès, Meghyn Bienvenu, Thomas Schiex, Sylvie Thiébaux +1 more
similarity 0.65
Abstract

We examine opportunities for neurosymbolic AI alongside increasingly powerful neural models, particularly with regards to efficiency, safety and interpretability. We identify two major challenges: ensuring semantic alignment between neural and symbolic components, and managing the computational cost of symbolic inference and learning. We discuss representative methodological approaches to these challenges and address several common misconceptions concerning differentiability, independence assumptions, and scalability. This paper synthesizes perspectives developed through discussions in the Neurosymbolic Programming and Reasoning (NPR) working group at the 2026 CNRS workshop Neurosymbolic Methods and Their Applications in Data Science, rather than providing an exhaustive survey.

0.22

Auto-Formalizing Neuro-Symbolic Predictors

cs.LG cs.AI ·2026-10-01 ·Samuele Bortolotti, Weixin Chen, Han Zhao, Andrea Passerini, Stefano Teso +1 more
benchmarkcode/data similarity 0.65
Abstract

Neuro-Symbolic (NeSy) predictors incorporate prior knowledge into the prediction process of neural networks, ensuring that outputs satisfy specified constraints, making them particularly suitable for high-stakes applications where compliance with domain knowledge is essential. A key bottleneck in this paradigm is the acquisition of symbolic constraints: encoding domain knowledge into logical formulas remains a manual and expert-intensive process. In this work, we investigate the extent to which auto-formalization via LLMs can systematically translate textual knowledge into symbolic knowledge that can be plugged into NeSy predictors. To this end, we introduce auto-nesy-bench, a new benchmark for evaluating constraint formalization and its impact on downstream accuracy of NeSy predictors. Through an extensive evaluation across several domains, we find that LLMs can formalize constraints to a meaningful extent, generating formulas that are often similar to those provided by human experts. Moreover, when the generated formulas are syntactically valid, they can lead to high-quality downstream predictions. The code and benchmark are available at https://unitn-sml.github.io/auto-nesy-bench/.

0.24

Learning to Bound: Monotonic, Calibrated Neural Upper Bounds for MPE Inference

cs.LG cs.AI ·2026-10-29 ·Akshay Vyas, Hailiang Dong, Shivvrat Arya, Brij Malhotra, Tahrima Rahman +2 more
similarity 0.64
Abstract · 37 pages, 4 figures

Probabilistic graphical models (PGMs) compactly encode structured joint distributions, but Most Probable Explanation (MPE), which finds the highest-probability assignment to unobserved variables, remains computationally intractable in large, densely structured models. Anytime systematic search, such as branch-and-bound (B&B), is a popular approach, but its efficiency depends on tight admissible upper bounds that are often prohibitively expensive to compute using classical methods like Mini-Bucket Elimination (MBE). We introduce Learning to Bound (L2B), a data-driven framework that amortizes bound computation cost by training a neural predictor. L2B targets two key properties required for effective search bounds: admissibility, which is achieved via statistical calibration techniques, and progressive tightening as evidence accumulates, which is enforced through structural architectural constraints that ensure monotonicity by construction. Across challenging benchmarks, L2B delivers tighter, monotonic bounds at orders-of-magnitude lower cost on every PGM family, and yields measurable improvements when integrated with branch-and-bound on high-treewidth instances.

0.21

Compressed Simulation-Based Inference: Neural Posterior Estimation for Massive Data via Low-Dimensional Sketches

cs.LG stat.MLstat.COstat.ME ·2026-11-16 ·Michael Wieck-Sosa, Cosma Rohilla Shalizi
similarity 0.64
Abstract

Neural posterior estimation (NPE) is a popular Bayesian simulation-based inference (SBI) approach that uses neural networks trained on simulated data--parameter pairs to approximate the posterior given a user-chosen prior. For high-dimensional observations, NPE methods typically approximate the conditional density of the parameter given a user-chosen or learned summary statistic, rather than the entire dataset, due to the curse of dimensionality. However, both approaches face challenges: hand-crafting good summaries for complex models requires considerable effort from scientists, while learning them from massive datasets can be prohibitively computationally expensive. To address these challenges, we propose approximating the conditional density of a parameter given low-dimensional sketches of the data. We show that, for a model with a $p$-dimensional parameter, only $2p+1$ random sketches are needed for posterior consistency. We compare with state-of-the-art embedding networks for NPE, and we find that our method \emph{matches} the best embedding network's performance while \emph{increasing computational efficiency}.

0.05

Exhaustive Canonical Skeletons Generation: A Formal Dataset for Decomposable Symbolic Regression

cs.LG ·2026-10-14 ·Giorgio Morales, Anikó Ekárt
publishedbenchmarkdataset similarity 0.64
Abstract · Accepted to appear in IEEE Computational Intelligence Letters

Neural symbolic regression (SR) models require diverse datasets of mathematical expressions for robust training. However, existing datasets rely predominantly on stochastic sampling methods, which suffer from high structural redundancy and incomplete functional coverage. To address this, we introduce an exhaustive dataset of univariate canonical skeletons generated via a deterministic constrained context-free grammar. A canonical skeleton acts as a generic structural representation that subsumes more specific functional forms, eliminating redundant expressions and avoiding repeated computational efforts. Although our dataset consists of univariate skeletons, it is designed to support the decomposable SR paradigm to solve multivariate SR problems without assuming linear separability. Furthermore, we pair this dataset with a sampling strategy that generates clean numerical data without triggering numerical instabilities or relying on artificial protected operators. Canonicalizing two existing neural SR datasets reveals that our dataset is substantially more compact, eliminates structural repetitions, and achieves a uniform operator distribution free of simplicity bias. Finally, we establish a benchmark of 150 SR problems across three tiers, on which state-of-the-art SR methods are shown to struggle significantly.

0.27

Latent Path Exploration via Potential-Guided Subtrajectory Balance

cs.CL cs.LG ·2026-10-29 ·Xiaoling Zeng, Qi Zhang
similarity 0.64
Abstract

Continuous latent reasoning enables language models to perform intermediate computation without generating explicit reasoning traces. Advances in stochastic latent reasoning allow multiple paths to be sampled in continuous space, but stochasticity alone does not ensure effective exploration. A key challenge is guiding stochastic transitions between intermediate latent states toward useful reasoning paths. We introduce SubLAT, which couples a relative answer potential with Subtrajectory Balance to learn stochastic latent exploration. The relative potential evaluates the answer support of sampled states against replacement states, with a correctness signal at the terminal state. Subtrajectory Balance relates potential differences to forward and backward transition densities across subtrajectories of different lengths. The model is jointly trained with answer supervision, CoT supervision, and representation distillation. Experiments on arithmetic and deductive reasoning show increasing solution coverage with larger sampling budgets across in-domain and out-of-domain benchmarks, as well as improvements on several structural OOD benchmarks. Trajectory analyses reveal progressive divergence among sampled latent paths and higher mean relative potentials for correct trajectories across arithmetic benchmarks.

0.10

Lightweight Representation Learning for Low Tucker Rank Tensors

cs.LG cs.AI ·2026-10-31 ·Hiroki Hasegawa, Yukihiko Okada
benchmark similarity 0.64
Abstract · 26 pages

Low Tucker rank tensors provide compact representations of multidimensional dependencies, but standard learning pipelines can incur substantial computational and memory overhead from redundant intermediate quantities. We reduce this overhead without modifying the underlying representation objective or parameterization. Our approach combines three complementary components: (i) sequential extraction of only task-required spectral components, avoiding unnecessary full decompositions; (ii) factor-wise multilinear contractions without materializing large Kronecker operators; and (iii) compact latent-state updates without storing full ambient tensor iterates. These components preserve the algebraic operations and learning trajectories of the original algorithms while reducing their computational and memory footprints. Across five low Tucker rank tensor estimators, our implementations match the original trajectories to numerical precision (relative discrepancies of $10^{-16}$ to $10^{-13}$), while reducing per-iteration runtime by up to $3.12\times$ and resident memory by up to $616\times$ ($99.8\%$) on the main order-3 benchmark at $n=100$, with memory reductions exceeding $900\times$ across the full evaluation suite. These results show that substantial computational redundancy can be eliminated from Tucker representation learning without changing the underlying model or learned representation.

0.32