Universal probabilistic programming systems (PPSs) provide a powerful framework for specifying rich and complex probabilistic models. However, this expressiveness comes at the cost of substantially complicating the process of drawing inferences from the model. In particular, inference can become challenging when the support of the model varies between executions. Though general-purpose inference engines have been designed to operate in such settings, they are typically inefficient, often relying on proposing from the prior to make transitions. To address this, we introduce a new inference framework: Divide, Conquer, and Combine (DCC). DCC divides the program into separate straight-line sub-programs, each of which has a fixed support allowing more powerful inference algorithms to be run locally, before recombining their outputs in a principled fashion. We show how DCC can be implemented as an automated and general-purpose PPS inference engine, and empirically confirm that it can provide substantial performance improvements over previous approaches. Universal PPSs, such as Church (Goodman et al., 2008) , Venture (Mansinghka et al., 2014) , Anglican (Wood et al., 2014) and Pyro (Bingham et al., 2018) , are set up to try and support the widest possible range of models a user might wish to write. Though this means that such systems can be used to write models which would be otherwise difficult to encode, this expressiveness comes at the cost of significantly complicating the automation of inference. In particular, models may contain variables with mixed types or have varying, or even unbounded, dimensionalities; characteristics which cause significant challenges at the inference stage. In this paper, we aim to address one of the most challenging of these complicating factors: variables whose very existence is stochastic, often, though not always, leading to the overall dimensionality of the model varying between realizations. Some very basic inference algorithms, such as importance sampling from the prior, are able to deal with this problem naturally, but they are catastrophically inefficient for all but the most simple models. Sequential Monte Carlo (Wood et al., 2014) and variational (Paige, 2016) approaches can sometimes also be applied, but only offer improvements for models with particular exploitable structures. MCMC approaches, on the other hand, are difficult to apply due to the need to construct proposals able to switch between the different variable configurations, something which is difficult to achieve even in a problem specific manner, let alone automate for generic problems. Moreover, ensuring these proposals remain efficient can be almost impossible, as different configurations might not have natural similarities or "neighboring regions"; the problem is analogous to running MCMC on a highly multi-modal distribution without any knowledge of where the different modes are. In short, there are a wide range of models for which no effective PPS-suitable inference methods currently exist. More discussion can be seen in Appendix B. To this end, we introduce a new framework-Divide, Conquer, and Combine (DCC)-for performing inference in such models. DCC works by dividing the program into separate straight-line sub-programs with fixed support, conquering these separate sub-problems using an inference strategy that exploits the fixed support to remain efficient, and then combining the resulting sub-estimators to an overall approximation of the posterior. By splitting the original program up into its separate configurations, we effectively transfer this transitioning problem to one of estimating the marginal likelihood for the different models, something which is typically much easier to achieve. Furthermore, this approach also allows us to introduce meta-strategies for allocating resources between sub-problems, thereby explicitly controlling the exploration-exploitation trade-off in a manner akin to Rainforth et al. (2018) ; Lu et al. (2018) . To demonstrate its potential utility, we implement a specific realization of our DCC framework as an automated and general-purpose inference engine in the PPS Anglican (Wood et al., 2014) , finding that it is able to achieve substantial performance improvements and tackle more challenging models than existing approaches. In this paper, we have proposed Divide, Conquer and Combine (DCC), a new inference strategy for probabilistic programs with stochastic support. We have shown that by breaking down the overall inference problem into a number of separate inferences of subprograms of fixed support, the DCC framework can provide substantial performance improvements over existing approaches which directly target the full program. To realize this potential, we have shown how to implement a particular instance of DCC as an automated engine in the PPS Anglican, and demonstrated its effectiveness through two example problems. Anglican inherits its general syntax from Clojure, extending this with two special forms: sample and observe, between which the distribution of the program is defined. sample statements are used to draw random variables from provided probability distributions, while observe statements are used to condition on data. Informally, they can be respectively thought of as prior and likelihood terms. The density of an Anglican program is derived by executing it in a forward manner, drawing from sample statements when encountered, and keeping track of density components originating from both the sample and observe terms. Specifically, let {x i } nx i=1 = x 1 , . . . , x nx represent the random variables generated from the encountered sample statements, where the i-th encountered sample statement has a lexical program address a i , an input η i , and a density f a i (x i |η i ). Analogously, let {y j } ny j=1 = y 1 , . . . , y ny represent the observed values of the n y encountered observe statements, which have lexical addresses b j and corresponding densities g b j (y j |φ j ), where φ j is analogous to η i . The program density is now given by π(x) = γ(x)/Z where and the associated reference measure is implicitly defined through the encountered sample statements. Note here that everything (i.e. n x , n y , x 1:nx , y 1:ny , a 1:nx , b 1:ny , η 1:nx , and φ 1:ny ) is a random variable, but each is deterministically calculable given x 1:nx . See Rainforth (2017, §4.3.2) for a more detailed introduction. We denote an execution trace (i.e. realization) of an Anglican program by the sequence of the addresses of sample statements and the corresponding variables, namely [a i , For clarity, we refer to the sequence a 1:nx as the path of a trace and x 1:nx as the draws. A program with stochastic support can now be more formally defined as one for which the path a 1:nx varies between different realizations: a different value for the path corresponds to a different configuration of variables being sampled.
Divide, Conquer, and Combine is a new inference scheme that can be performed on the probabilistic programs with stochastic support, i.e. the very existence of variables is stochastic.