Backpropagation for Effectful Languages I: Finite Probability and Discrete Output Algebraic Effects

What the math gives to ML

The paper gives a compositional reverse-mode AD construction for finite probabilistic programs in which cotangents propagate through the probability effect itself, rather than treating sampling as an opaque nondifferentiable operation. Its transferable asset is exact finite-support differentiation: a probabilistic computation can be represented as a weighted collection of branches, and reverse AD accumulates both derivatives of branch values and derivatives of branch weights. This suggests an effect-handler or compiler pass for small discrete latent modules, mixture layers, and discrete routers, avoiding Monte Carlo score-function noise when the support is tractable. The main practical constraint is support growth, so the first implementation should target categorical variables with small cardinality and add pruning or top-k truncation later.