Scaling Integer Arithmetic in Probabilistic Programs
This addresses a bottleneck in probabilistic programming languages for researchers and practitioners dealing with complex discrete models, representing an incremental improvement by leveraging existing knowledge compilation techniques.
The paper tackled the challenge of scaling probabilistic inference for high-dimensional discrete distributions involving integers by introducing a binary encoding strategy that exploits the logical structure of integer arithmetic, and demonstrated that this approach scales to much larger integer distributions with arithmetic.
Distributions on integers are ubiquitous in probabilistic modeling but remain challenging for many of today's probabilistic programming languages (PPLs). The core challenge comes from discrete structure: many of today's PPL inference strategies rely on enumeration, sampling, or differentiation in order to scale, which fail for high-dimensional complex discrete distributions involving integers. Our insight is that there is structure in arithmetic that these approaches are not using. We present a binary encoding strategy for discrete distributions that exploits the rich logical structure of integer operations like summation and comparison. We leverage this structured encoding with knowledge compilation to perform exact probabilistic inference, and show that this approach scales to much larger integer distributions with arithmetic.