POPL 2027
Sun 10 - Sat 16 January 2027 Mexico City, Mexico

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.