# Lexicographic Ranking Supermartingales: An Efficient Approach to Termination of Probabilistic Programs

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Sep 2017.

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

- [Policy Verification in Stochastic Dynamical Systems Using Logarithmic Neural Certificates](https://mlsanity.com/paper/2406.00826/) (2024)
- [Control-Data Separation and Logical Condition Propagation for Efficient Inference on Probabilistic Programs](https://mlsanity.com/paper/2101.01502/) (2021)
- [Probabilistic unifying relations for modelling epistemic and aleatoric uncertainty: semantics and automated reasoning with theorem proving](https://mlsanity.com/paper/2303.09692/) (2023)
- [Neural Proofs for Sound Verification and Control of Complex Systems](https://mlsanity.com/paper/2512.18389/) (2025)
- [Value Functions as Supermartingale Certificates](https://mlsanity.com/paper/2605.31524/) (2026)

## Abstract (arXiv)

Probabilistic programs extend classical imperative programs with real-valued random variables and random branching. The most basic liveness property for such programs is the termination property. The qualitative (aka almost-sure) termination problem given a probabilistic program asks whether the program terminates with probability 1. While ranking functions provide a sound and complete method for non-probabilistic programs, the extension of them to probabilistic programs is achieved via ranking supermartingales (RSMs). While deep theoretical results have been established about RSMs, their application to probabilistic programs with nondeterminism has been limited only to academic examples. For non-probabilistic programs, lexicographic ranking functions provide a compositional and practical approach for termination analysis of real-world programs. In this work we introduce lexicographic RSMs and show that they present a sound method for almost-sure termination of probabilistic programs with nondeterminism. We show that lexicographic RSMs provide a tool for compositional reasoning about almost sure termination, and for probabilistic programs with linear arithmetic they can be synthesized efficiently (in polynomial time). We also show that with additional restrictions even asymptotic bounds on expected termination time can be obtained through lexicographic RSMs. Finally, we present experimental results on abstractions of real-world programs to demonstrate the effectiveness of our approach.