Proving Almost-Sure Termination of Probabilistic Programs via Incremental Pruning

Krishnendu Chatterjee, Ehsan Kafshdar Goharshady, Petr Novotný, Jiri Zárevúcky, Dorde Zikelic

TL;DR

This paper introduces a novel incremental approach to automatically prove that probabilistic programs terminate with probability 1 (almost-sure termination). It overcomes limitations of existing methods by relaxing strict nonnegativity requirements and eliminating the need for pre-computed program invariants, making termination proving more efficient and applicable to a wider range of programs.

What Problem Does This Paper Address?

Proving that a program will eventually halt is a fundamental challenge in computer science, known as the termination problem. For probabilistic programs, which incorporate randomness, this problem becomes more complex. Specifically, the "almost-sure termination" problem asks if a probabilistic program halts with probability 1. Existing methods, like those using lexicographic ranking supermartingales (LexRSMs), are sound but suffer from two key drawbacks:

  1. Restrictive Nonnegativity: LexRSMs often require all their components to be non-negative in every reachable program state, a condition that is not always met in practice and can be overly strict.
  2. Invariant Dependency & Insufficiency-Inefficiency Trade-off: Current algorithms rely on pre-computed program invariants. If these invariants are too weak, they might not be sufficient to prove termination, even if a termination proof exists. Conversely, strong invariants are computationally expensive to derive. This creates a trade-off between the effectiveness and efficiency of the termination proof.

This paper aims to address these limitations by developing a more flexible and efficient approach to proving almost-sure termination.

Methods

The authors propose two main contributions:

  1. Generalized Lexicographic Ranking Supermartingales (GLexRSMs): They introduce a relaxed definition of LexRSMs. Instead of requiring all components to be non-negative everywhere, GLexRSMs only require nonnegativity in specific program states where it's relevant for ranking transitions. This makes the approach applicable to a broader set of programs.
  2. Incremental Pruning Algorithm: This is the core of their novel approach. It's an iterative method that doesn't rely on pre-computed invariants. The algorithm starts with a simple termination argument and incrementally refines it. It uses a safety prover to identify "counterexamples" (situations where termination might not be guaranteed). These counterexamples are then used to "prune" parts of the program that are already proven to terminate, allowing the algorithm to focus on the remaining, potentially problematic, parts. This process is inspired by similar incremental techniques for non-probabilistic programs but adapted for the probabilistic setting, which involves handling counterexamples as sets of paths with positive measure.

Datasets

The authors evaluated their approach on two collections of benchmarks:

  • Standard Collection: 90 benchmarks previously used for probabilistic analysis, derived from non-probabilistic benchmarks by introducing probabilistic assignments and transitions.
  • General Collection: A larger set of 139 benchmarks, including "truly probabilistic" programs and non-probabilistic termination benchmarks, to assess the tool's generalization capabilities.

Key Insights and Ideas

  • Relaxing Nonnegativity is Crucial: The strict nonnegativity requirement in classical LexRSMs is a significant hurdle. By relaxing it to a "generalized" form, the authors enable termination proofs for programs that were previously untreatable.
  • Incremental Refinement is Powerful: The idea of iteratively refining a termination argument, guided by a safety prover, is a key innovation. This avoids the need for expensive upfront invariant computation and allows the system to focus its effort where it's most needed.
  • Pruning as a Core Mechanism: The algorithm effectively "prunes" parts of the program that are proven to terminate, simplifying the problem incrementally. This is analogous to how one might simplify a complex system by removing known-to-be-safe components.
  • Bridging Non-Probabilistic and Probabilistic Techniques: The work successfully adapts successful incremental techniques from non-probabilistic program analysis to the probabilistic domain, overcoming conceptual challenges related to probabilistic counterexamples.

Key Results

  • The proposed algorithm, implemented as a tool, demonstrates strong performance on both standard and general benchmark sets.
  • On the standard collection, their tool achieved a high number of successful proofs, even outperforming a previous "Invariant tool" on some benchmarks (9 unique successes) and proving termination for programs that the previous tool couldn't handle (e.g., the program in Figure 2a).
  • The tool generally generalizes well beyond the standard benchmark set, as shown by its performance on the general collection.
  • The vast majority of successful proofs completed in under 1 second, indicating high efficiency.

Limitations and Future Work

  • Safety Checker Dependency: The authors note that in many cases, failure to prove termination was due to the safety checker failing. This suggests that improvements in safety checking technology could significantly benefit their approach.
  • Non-Affine Arithmetic: The current algorithm is restricted to affine probabilistic programs (APPs) due to efficiency reasons and the reliance on linear programming for synthesis. The authors suggest that extending the approach to handle polynomial arithmetic is a promising direction for future work, potentially by combining their method with existing techniques for polynomial RSM synthesis.
  • Quantitative Analysis: Exploring the applicability of their approach to quantitative analysis of probabilistic programs (e.g., cost analysis) is also identified as an interesting avenue for future research.

Summary updated

Abstract

The extension of classical imperative programs with real-valued random variables and random branching gives rise to probabilistic programs. The termination problem is one of the most fundamental liveness properties for such programs. The qualitative (aka almost-sure) termination problem asks whether a given program terminates with probability 1. Ranking functions provide a sound and complete approach for termination of non-probabilistic programs, and their extension to probabilistic programs is achieved via ranking supermartingales (RSMs). RSMs have been extended to lexicographic RSMs to handle programs with involved control-flow structure, as well as for compositional approach. There are two key limitations of the existing RSM-based approaches: First, the lexicographic RSM-based approach requires a strong nonnegativity assumption, which need not always be satisfied. The second key limitation of the existing RSM-based algorithmic approaches is that they rely on pre-computed invariants. The main drawback of relying on pre-computed invariants is the insufficiency-inefficiency trade-off: weak invariants might be insufficient for RSMs to prove termination, while using strong invariants leads to inefficiency in computing them. Our contributions are twofold: First, we show how to relax the strong nonnegativity condition and still provide soundness guarantee for almost-sure termination. Second, we present an incremental approach where the process of computing lexicographic RSMs proceeds by iterative pruning of parts of the program that were already shown to be terminating, in cooperation with a safety prover. In particular, our technique does not rely on strong pre-computed invariants. We present experimental results to show the applicability of our approach to examples of probabilistic programs from the literature.
BibTeX
@misc{chatterjee2020proving,
  author = {Krishnendu Chatterjee and Ehsan Kafshdar Goharshady and Petr Novotný and Jiri Zárevúcky and Dorde Zikelic},
  title = {{Proving Almost-Sure Termination of Probabilistic Programs via Incremental Pruning}},
  year = {2020},
  eprint = {2008.06295},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2008.06295},
}
Figure