  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.

Artificial Intelligence;Programming Languages