Where to Approximate in Neurosymbolic Inference?
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
| Pipeline | Schedule | Rank | Time (s) | |
| 216\ {\color[rgb]{0.0078,0.5,0.5078}\overset{R=6}{\longrightarrow}}\ {\color[rgb]{1,0.5,0.0039}\overset{169\times}{\longrightarrow}}\ {\color[rgb]{0.5,0,0.5}\overset{42\times}{\longrightarrow}}\ {\color[rgb]{0.9844,0.1953,0.6016}5} | Dependency-first | 500 | 42.4 | 1.30 |
| 216\ {\color[rgb]{0.0078,0.5,0.5078}\overset{R=6}{\longrightarrow}}\ {\color[rgb]{1,0.5,0.0039}\overset{183\times}{\longrightarrow}}\ {\color[rgb]{0.5,0,0.5}\overset{28\times}{\longrightarrow}}\ {\color[rgb]{0.9844,0.1953,0.6016}5} | Random | 500 | 94.7 | 3.41 |
| 216\ {\color[rgb]{0.0078,0.5,0.5078}\overset{R=6}{\longrightarrow}}\ {\color[rgb]{1,0.5,0.0039}\overset{144\times}{\longrightarrow}}\ {\color[rgb]{0.5,0,0.5}\overset{67\times}{\longrightarrow}}\ {\color[rgb]{0.9844,0.1953,0.6016}5} | Dependency-first | 50 | 5.1 | 1.97 |
Neuro-Symbolic Reasoning
Neuro-symbolic reasoning combines learned neural models with explicit logic, rules, knowledge structures, or executable tools to solve structured tasks.
See all 295 papers