# ADEV: Sound Automatic Differentiation of Expected Values of Probabilistic Programs

arXiv: https://arxiv.org/abs/2212.06386 · HTML: https://mlsanity.com/paper/2212.06386/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Dec 2022.

## Built on by (most cited first, 12 of 12)

- [Towards Guaranteed Safe AI: A Framework for Ensuring Robust and Reliable AI Systems](https://mlsanity.com/paper/2405.06624/) (2024)
- [Building Machines that Learn and Think with People](https://mlsanity.com/paper/2408.03943/) (2024)
- [Smoothing Methods for Automatic Differentiation Across Conditional Branches](https://mlsanity.com/paper/2310.03585/) (2023)
- [Differentiating Metropolis-Hastings to Optimize Intractable Densities](https://mlsanity.com/paper/2306.07961/) (2023)
- [Branches of a Tree: Taking Derivatives of Programs with Discrete and Branching Randomness in High Energy Physics](https://mlsanity.com/paper/2308.16680/) (2023)
- [Automated Efficient Estimation using Monte Carlo Efficient Influence Functions](https://mlsanity.com/paper/2403.00158/) (2024)
- [Probabilistic Programming with Programmable Variational Inference](https://mlsanity.com/paper/2406.15742/) (2024)
- [ωPAP Spaces: Reasoning Denotationally About Higher-Order, Recursive Probabilistic and Differentiable Programs](https://mlsanity.com/paper/2302.10636/) (2023)
- [Understanding Automatic Differentiation Pitfalls](https://mlsanity.com/paper/2305.07546/) (2023)
- [Beyond Bayesian Model Averaging over Paths in Probabilistic Programs with Stochastic Support](https://mlsanity.com/paper/2310.14888/) (2023)
- [GradInf: Gradient Estimation as Probabilistic Inference](https://mlsanity.com/paper/2607.07840/) (2026)
- [Sample-Smooth Spaces: A Convenient Category for Differentiable Probabilistic Programming](https://mlsanity.com/paper/2609.26270/) (2026)

## Abstract (arXiv)

Optimizing the expected values of probabilistic processes is a central problem in computer science and its applications, arising in fields ranging from artificial intelligence to operations research to statistical computing. Unfortunately, automatic differentiation techniques developed for deterministic programs do not in general compute the correct gradients needed for widely used solutions based on gradient-based optimization. In this paper, we present ADEV, an extension to forward-mode AD that correctly differentiates the expectations of probabilistic processes represented as programs that make random choices. Our algorithm is a source-to-source program transformation on an expressive, higher-order language for probabilistic computation, with both discrete and continuous probability distributions. The result of our transformation is a new probabilistic program, whose expected return value is the derivative of the original program's expectation. This output program can be run to generate unbiased Monte Carlo estimates of the desired gradient, which can then be used within the inner loop of stochastic gradient descent. We prove ADEV correct using logical relations over the denotations of the source and target probabilistic programs. Because it modularly extends forward-mode AD, our algorithm lends itself to a concise implementation strategy, which we exploit to develop a prototype in just a few dozen lines of Haskell (https://github.com/probcomp/adev).