Where to spend approximation in neurosymbolic inference: APRICOT's tensor-train recompression cuts weighted model count error by orders of magnitude
Synopsis
Probabilistic neurosymbolic inference combines neural predictions with symbolic constraints by computing a weighted model count, which is #P-hard exactly, and existing methods each place approximation at a different stage. APRICOT unifies bottom-up compilation into a three-step pipeline and instantiates factor compilation and product recompression with tensor trains, yielding weighted model count estimates orders of magnitude more accurate than prior methods across six tasks in Sudoku, arithmetic reasoning and scene understanding, with better downstream learning where symbolic factors are tightly coupled.
Interpretation
Weighted model counting in neurosymbolic inference no longer has only two options, exact compilation or an independence approximation; approximation can enter at factor compilation, at factor multiplication, or at combining the remaining factors. Earlier practice either relied on exact circuit compilation or assumed factors independent and replaced the joint count by a product of per-factor counts, without a systematic comparison of where to approximate. On 4x4, 6x6 and 9x9 Sudoku, exact SDD compilation is already infeasible at 6x6 and no existing compiler solves 9x9, while the tensor-train pipelines reach lower log model-count error at comparable compilation time.
Representing each constraint factor as a tensor train, multiplying exactly and then recompressing the product keeps dependencies between factors while controlling size. Tensor trains had been used to compress isolated factors but not inside a full compilation pipeline, and the rank growth after multiplication was not addressed. On the harder CLEVR-Diff, MNISTMul and CLEVR-CountDiff, the full tensor-train reduction APRICOT C scales beyond the evaluated SDD compiler, and its weighted model count estimates are substantially more accurate than independence reduction; on MNISTAdd both SDDs and APRICOT exploit the carry-chain structure to scale with the number of digits.
Whether preserving factor dependencies pays off depends on whether the program introduces auxiliary symbolic variables that must agree across factors. Independence approximation is already competitive on Visual Sudoku and CLEVR-Diff, where all baselines reach close to 99% concept accuracy, leaving little room for improvement. On the arithmetic tasks with carries and on CLEVR-CountDiff, exact compilation and APRICOT C clearly outperform independence reduction, while CLEVR-Diff, also a scene-understanding task, shows no such gap.
Perspective
The evaluation covers a compilation ablation on 4x4, 6x6 and 9x9 Sudoku, Visual Sudoku classification and completion, and weighted inference plus learning on MNISTAdd, MNISTMul, CLEVR-Diff and CLEVR-CountDiff; compilation runs on one NVIDIA A10G GPU, SDD compilation runs on CPU with a 64 GiB memory cap and a two-hour limit, training has a six-hour wall-clock limit, and results are averaged over ten runs.
The independence approximation has unbounded error and depends on how the constraint is written, with the same 4x4 Sudoku estimated about 24 orders of magnitude apart under categorical and Boolean encodings; on 9x9 Sudoku, heavily recompressed points can achieve good aggregate error while missing the actual models; some runs fail to converge, with one and three of ten APRICOT runs failing on CLEVR-CountDiff at m=8 and m=16 respectively; most tensor-train decompositions and recompressions are not tailored to sparse Boolean tensors.