Supermartingales, Ranking Functions and Probabilistic Lambda Calculus

Andrew Kenyon-Roberts, Luke Ong

This paper, presented by researchers from the University of Oxford, tackles one of the most fundamental yet difficult questions in probabilistic programming: Will this program eventually finish running?

Specifically, the authors provide a rigorous mathematical framework for proving Almost Sure Termination (AST)—the property that a program terminates with probability 1—in a higher-order functional language.

TL;DR

The authors introduce a powerful method for proving that probabilistic functional programs (using lambda calculus and continuous sampling) will terminate. By combining stochastic processes (supermartingales) with novel concepts like "sparse" ranking functions and "confluent" semantics, they provide a toolkit to verify complex programs that were previously beyond the reach of formal analysis.

What Problem Does This Paper Address?

Probabilistic programming languages (like Stan, Pyro, or Anglican) are essential for Bayesian machine learning, allowing developers to write generative models that computers can then "invert" to perform inference. However, these programs are notoriously difficult to verify.

A central requirement for these models is Almost Sure Termination (AST). If a program has even a tiny chance of looping forever, the resulting probability distributions can be mathematically invalid, leading to incorrect inference. While methods exist to prove AST for simple "imperative" programs (like those with basic while loops), they struggle with:

  1. Higher-order functions: Programs where functions are passed as arguments or returned as results.
  2. Continuous distributions: Sampling from an infinite range of real numbers.
  3. Complex recursion: Programs that make multiple recursive calls in a single step (non-affine recursion).

Methods

The authors build their framework on Probabilistic PCF (PPCF), a version of the simply-typed lambda calculus extended with continuous random sampling and explicit recursion. Their approach centers on three main innovations:

  • Ranking Supermartingales: They define "ranking functions" that map program states to non-negative numbers. If these numbers decrease on average during execution, the program is a "supermartingale." Using Doob’s Optional Sampling Theorem, they prove that the existence of such a function guarantees AST.
  • Antitone and Sparse Extensions:
    • Antitone functions allow for programs that terminate "arbitrarily slowly" by relaxing how much the rank must decrease at each step.
  • Sparse functions allow the programmer to only define the rank at "semantically important" points in the code, ignoring the hundreds of trivial intermediate reduction steps typical in functional languages.
  • Confluent Trace Semantics: In probabilistic settings, the order in which you evaluate code usually matters because it changes the sequence of random samples. The authors introduce a novel "addressing scheme" for random choices that regains confluence. This allows researchers to prove a program terminates using a "custom" evaluation order that is easier to analyze than the standard one.

Datasets

As a theoretical paper in computer science and logic, this work does not use traditional empirical datasets. Instead, the authors evaluate their framework by providing formal proofs for several challenging "benchmark" program types:

  • 1D Random Walks: Biased and unbiased versions.
  • Non-affine recursion: Programs that branch into multiple recursive calls.
  • Higher-order recursion: Programs where the recursive structure itself involves passing functions.

Key Insights and Ideas

  • The "Y" focus: In a typed functional language, the only way a program can fail to terminate is through the recursion operator ($Y$). The authors show that you only need to track $Y$-reduction steps to prove termination, significantly simplifying the math.
  • Regaining Confluence: The most surprising "aha moment" is the proof that one can use alternative reduction strategies to prove AST for the standard strategy. By labeling samples based on their position in the program's skeletal structure rather than the order they are drawn, they make the math "order-independent."
  • Complexity Parity: The paper notes that deciding AST for higher-order programs with continuous distributions is $\Pi^0_2$-complete—the same complexity class as first-order imperative programs, despite the added language features.

Key Results

  • Soundness Theorems: The authors formally prove that if a PPCF term is "rankable" (via standard, antitone, or sparse functions), it is guaranteed to be AST.
  • Broad Applicability: They successfully demonstrate their method on programs that terminate arbitrarily slowly (like the unbiased 1D random walk), which standard ranking methods cannot handle.
  • Theoretical Foundation: They establish the first application of martingales to the probabilistic lambda calculus, bridging the gap between stochastic process theory and functional programming semantics.

Limitations and Future Work

  • Completeness: While the authors prove their method is sound (if a ranking function exists, the program terminates), they have not yet proven it is complete (if a program terminates, a ranking function must exist), though they provide a conjecture that it is.
  • Automation: The ranking functions currently have to be constructed manually by a human expert. The authors suggest that future work should focus on automating the discovery of these functions.
  • Restricted Confluence: The current rules for maintaining confluence are somewhat strict (e.g., restrictions on sampling inside a lambda). Relaxing these rules could make the method even more flexible.

Summary updated

Abstract

We introduce a method for proving almost sure termination in the context of lambda calculus with continuous random sampling and explicit recursion, based on ranking supermartingales. This result is extended in three ways. Antitone ranking functions have weaker restrictions on how fast they must decrease, and are applicable to a wider range of programs. Sparse ranking functions take values only at a subset of the program's reachable states, so they are simpler to define and more flexible. Ranking functions with respect to alternative reduction strategies give yet more flexibility, and significantly increase the applicability of the ranking supermartingale approach to proving almost sure termination, thanks to a novel (restricted) confluence result which is of independent interest. The notion of antitone ranking function was inspired by similar work by McIver, Morgan, Kaminski and Katoen in the setting of a first-order imperative language, but adapted to a higher-order functional language. The sparse ranking function and confluent semantics extensions are unique to the higher-order setting. Our methods can be used to prove almost sure termination of programs that are beyond the reach of methods in the literature, including higher-order and non-affine recursion.
BibTeX
@misc{kenyonroberts2021supermartingales,
  author = {Andrew Kenyon-Roberts and Luke Ong},
  title = {{Supermartingales, Ranking Functions and Probabilistic Lambda Calculus}},
  year = {2021},
  eprint = {2102.11164},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2102.11164},
}
Figure