We present a new approach to scaling up exact inference for probabilistic programs, using generating functions (GFs) as a compilation target. Existing exact-inference methods that compile to circuit representations, such as binary decision diagrams (BDDs), achieve strong state-of-the-art results. We show that a compiler targeting GFs can be similarly competitive—and, in some cases, even more scalable—on a range of inference problems where BDD-based methods perform well.

We present a formal model of this compiler, providing the first definition of GF compilation for a functional probabilistic language. We prove that this compiler is correct with respect to a denotational semantics. Our approach is implemented in a probabilistic programming system called 𝙶𝚎𝚗𝚒 and evaluated on a range of inference problems. Our results establish GF compilation as a principled and powerful paradigm for exact inference: it offers strong scalability, good expressiveness, and a solid theoretical foundation.