Where to Approximate in Neurosymbolic Inference?

Probabilistic neurosymbolic methods rely on weighted model counting (WMC) to combine neural predictors with symbolic constraints. Exact computation of the WMC, a #P-hard problem, 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: we derive new pipelines that exactly multiply approximated factors and recompress their products via SVD- or interpolation-based schemes. On Sudokus of increasing size, these pipelines produce WMC estimates that are many orders-of-magnitude more accurate than prior methods. Yet, when it comes to neurosymbolic learning, even crude approximations reach competitive accuracy, suggesting that approximation quality matters far more for inference fidelity than for downstream learning. Our pipelines open significant design space for effective approximate compilation of challenging probabilistic reasoning tasks.