  Probabilistic programming provides the means to represent and reason about
complex probabilistic models using programming language constructs. Even simple
probabilistic programs can produce models with infinitely many variables.
Factored inference algorithms are widely used for probabilistic graphical
models, but cannot be applied to these programs because all the variables and
factors have to be enumerated. In this paper, we present a new inference
framework, lazy factored inference (LFI), that enables factored algorithms to
be used for models with infinitely many variables. LFI expands the model to a
bounded depth and uses the structure of the program to precisely quantify the
effect of the unexpanded part of the model, producing lower and upper bounds to
the probability of the query.
