DeGAS: Gradient-Based Optimization of Probabilistic Programs without Sampling

Francesca Randone, Romina Doz, Mirco Tribastone, Luca Bortolussi · 2026

Read DeGAS: Gradient-Based Optimization of Probabilistic Programs without Sampling by Francesca Randone, Romina Doz, Mirco Tribastone, Luca Bortolussi (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-15167.txt.

Introduction

Francesca Randone, Romina Doz, Mirco Tribastone, and Luca Bortolussi tune probabilistic programs without drawing samples. Their 2026 arXiv paper deals with programs that mix chance with code. Such programs can have both continuous and discrete parts.

The team presents DeGAS, a differentiable Gaussian approximate semantics for loopless programs. Programs run under a Gaussian-mixture meaning instead of exact chance. Sharp predicates and discrete branches get a smooth stand-in that fades away. The result is a set of closed-form expressions for the key probabilities. Those forms stay open to gradient-based optimization, with no sampling needed at all.

Catalog record

CREATORFrancesca Randone, Romina Doz, Mirco Tribastone, Luca Bortolussi
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE76 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-15167

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

DeGAS: Gradient-Based Optimization of Probabilistic Programs without Sampling Francesca Randone, Romina Doz, Mirco Tribastone, Luca Bortolussi Abstract We present DeGAS, a differentiable Gaussian approximate semantics for loopless probabilistic programs that enables sample-free, gradient-based optimization in models with both continuous and discrete components. DeGAS evaluates programs under a Gaussian-mixture semantics and replaces measure-zero predicates and discrete branches with a vanishing smoothing, yielding closed-form expressions for posterior and path probabilities. We prove differentiability of these quantities with respect to program parameters, enabling end-to-end optimization via standard automatic differentiation, without Monte Carlo estimators. On thirteen benchmark programs, DeGAS achieves accuracy and runtime competitive with variational inference and MCMC. Importantly, it reliably tackles optimization problems where sampling-based baselines fail to converge due to conditioning involving continuous variables. 1 Introduction Probabilistic programming languages (PPLs) extend general-purpose languages with probabilistic primitives. In recent years they have received significant attention, motivated by their ability to model and analyze inherently stochastic systems such as randomized algorithms [ 18 ] , probabilistic cyber-physical systems [ 22 ] , and machine-learning models [ 8 ] . Probabilistic programs (PPs) typically expose parameters that must be tuned to meet goals: maximize likelihood [ 10 , 5 ] , satisfy safety constraints [ 30 ] , calibrate uncertainty [ 13 ] , or optimize bespoke utilities [ 28 ] . Current practice relies on sampling—either Markov chain Monte Carlo (MCMC) [ 2 ] or variational inference (VI) [ 7 ] . While often effective, these methods can exhibit high-variance gradient estimates and brittle behavior on discontinuous objectives induced by branching and hard conditioning, frequently necessitating problem-specific reparameterization tricks [ 34 , 27 , 1 , 14 , 25 ] . This paper asks the following: Can we obtain gradients for PP objectives without sampling? We answer affirmatively by introducing DeGAS, a differentiable Gaussian-mixture approximate semantics that renders end-to-end evaluation differentiable, enabling optimization with off-the-shelf automatic differentiation (AD) and without Monte Carlo estimators. The key idea is a principled, vanishing smoothing of discrete and measure-zero constructs (e.g., point masses and Boolean predicates), which yields differentiable densities and path probabilities throughout a program’s execution. This delivers deterministic objective values and gradients with respect to the program parameters. DeGAS builds on the SOGA (second-order Gaussian approximation) semantics for a class of loop-free probabilistic programs [ 29 ] . With SOGA, each program state is represented as a Gaussian mixture (GM) and program constructs update mixtures analytically (affine transforms, products, and conditioning via truncation) to approximate the posterior over program variables. DeGAS smooths the discontinuities that arise under branching and conditioning by injecting small Gaussian noise where needed and relaxing predicates accordingly, while preserving closure under mixture operations. We prove differentiability of posterior distributions and path probabilities with respect to parameters, and we show that as the smoothing parameter tends to zero, the differentiable semantics converges to the unsmoothed SOGA semantics under mild regularity conditions. We implement DeGAS in PyTorch leveraging its AD capabilities to provide a sample-free gradient-based optimizer. Numerical experiments show that, on thirteen benchmark programs, DeGAS achieves accuracy and runtime competitive with VI and MCMC. More important, we show DeGAS is able to solve instances of optimization problems for which sampling baselines fail to converge due to the presence of constructs such as conditional statements depending on continuous variables. Structure of the paper. Section 2 reviews related work. Section 3 presents the syntax and defines the differentiable semantics. Section 4 states and proves our main properties (differentiability and convergence). Section 5 reports the experimental results. Section 6 concludes. 2 Related Work To the best of our knowledge, this is the first work that computes gradients of probabilistic programs without sampling. For deterministic programs, the idea of smoothing to achieve sample-free optimization via gradient-free methods has been explored in [ 11 , 12 ] , and successively adapted for automatic differentiation in [ 20 ] . However, as will be shown in Section 4 , the smoothing of deterministic programs does not trivially carry over to PPs. An attempt was made to extend the smoothing to PPs in Leios [ 21 ] . Leios takes as input a discrete or hybrid discrete-continuous PP and approximates it with a fully continuous one using smoothing. The authors notice that the relaxation parameters must be tuned to avoid collapsing any probability event to zero. For example, a variable initially distributed as a Bernoulli after smoothing becomes distributed as a mixture of two components, with means in 0 and 1 and small standard deviations. This implies that the probability of the event x==0 passes from 0.5 to 0 . To avoid this, Leios solves an optimization problem to replace all Booleans predicate depending on smoothed variables. Conceptually, we are close in spirit in that we tackle discontinuities by controlled smoothing. However, the goal is fundamentally different: similarly to the previously mentioned works, Leios aids sampling-based inference; instead, we enable sample-free optimization. For PPs, most of the work has focused on coupling AD with sampling-based inference, designing gradient estimators for discontinuous programs—either to improve MCMC and VI globally [ 34 , 27 , 1 , 14 , 25 ] or only on the discontinuous parts [ 35 , 32 , 23 ] . These approaches still estimate gradients via sampling and are used to run inference faster or more stably. In contrast, we compute deterministic gradients by evaluating a differentiable program semantics; no Monte Carlo appears in the optimization loop. This lets us optimize likelihood and non-likelihood probabilistic objectives directly (such as reachability), not just expected values under a sampler. Some methods start from an input program and compute a second program, whose expected return value is the derivative of the input program’s expected return value [ 3 , 26 ] ; the new program can then be sampled to obtain gradient estimations. We differ in both goal (optimization rather than derivative-estimation for inference) and mechanism: for our smoothing, we leverage the analytical properties of the SOGA/GM semantics [ 29 ] , that yield closed-form truncated moments and CDFs for every node, which we then backpropagate through analytically. 3 Syntax and Semantics SOGA was introduced in [ 29 ] as a semantics for a loop-free PPL that manipulates input variables distributed as GMs. SOGA makes the language closed under GMs, providing an analytical representation of the posterior that enables efficient computation of moments, cumulative distribution functions (CDFs), and probability density functions (PDFs). This semantics is the second-order approximation of a family of approximate semantics based on Gaussian Mixtures, guaranteed to convergence to the true one, and demonstrated high accuracy across a variety of programs. Here, we add the possibility of specifying parameters to be used for optimization. Notation. For a distribution D , let f_{D} denote its pdf. A normal random variable with mean \mu and covariance matrix \Sigma is denoted by \mathcal{N}(\mu,\Sigma) . A GM is a weighted sum of Gaussians, G_{\pi,\mu,\Sigma}=\sum_{i=1}^{c}\pi_{i}\mathcal{N}(\mu_{i},\Sigma_{i}) where c is the number of components and (\pi_{i})_{\{i=1,\ldots,c\}} is the vector of weights satisfying 0\leq\pi_{i}\leq 1 and \sum_{i=1}^{c}\pi_{i}=1 . A Dirac delta centered on x_{0} is denoted by \delta_{x_{0}} . Let x[x_{i}\to e] denote the vector with e as i -th component, and every other component equal to x_{j} . Let \textrm{Marg}_{y}(D) denote the marginal

Read the complete text