Tensorizing Probabilistic Programs for Accelerated Exact Inference
We introduce a scalable approach to exact inference for discrete probabilistic programs, by compiling them to tensor computations. Prevailing approaches largely realize inference by compiling to irregular symbolic representations such as decision diagrams. Diverging from this established path, we build a compiler that translates probabilistic programs into functional array code, while lowering control flow (i.e., stochastic branching and bounded loops) straight into tensor flow. We formalize the source probabilistic language, the target array language, and the compilation between them. We prove the correctness of the compiler in the Lean prover, establishing a mathematical foundation for tensorized exact inference. Empirical results show that by casting exact inference as dense tensor programs run on CPUs or GPUs, our approach yields orders-of-magnitude speedups over state-of-the-art methods.