Proving Almost-Sure Termination of Probabilistic Programs via\n Incremental Pruning

Krishnendu Chatterjee, Ehsan Kafshdar Goharshady, Petr Novotný, Jiři Zárevúcky, Đorđe Žikelić

TL;DR

This paper introduces a novel incremental approach to automatically prove that probabilistic programs terminate with probability 1. It overcomes limitations of existing methods by relaxing strict nonnegativity requirements and avoiding 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 programs terminate is a fundamental challenge in computer science. For probabilistic programs, which incorporate randomness, this problem becomes even more complex. Specifically, the "almost-sure termination" problem asks if a program will finish with probability 1, regardless of random choices. Existing methods, like those using "ranking supermartingales" (RSMs), have two major drawbacks: they often require overly strict conditions (like strong nonnegativity) that don't always hold, and they rely on pre-computed "invariants" (assertions about program states). The latter creates an "insufficiency-inefficiency trade-off": weak invariants might not be enough to prove termination, while strong ones are computationally expensive to find. This paper aims to address these limitations by developing a more flexible and efficient automated termination proving technique for probabilistic programs.

Methods

The authors propose an incremental approach to proving almost-sure termination. Instead of relying on pre-computed invariants, their method starts with a simple termination argument and refines it iteratively. This refinement process involves a safety prover that helps identify parts of the program that are not yet proven to terminate. These parts are then "pruned" (effectively removed from consideration for the next step), allowing the algorithm to focus on the remaining, potentially non-terminating, sections.

Key novelties include:

  • Generalized Lexicographic Ranking Supermartingales (GLexRSMs): They relax the strict nonnegativity constraint of previous methods, making the approach applicable to a broader class of programs.
  • Incremental Refinement with Safety Provers: The core of their method is an iterative process where a safety prover helps guide the refinement of the termination argument. This avoids the need for expensive invariant generation upfront.
  • Probabilistic Pruning: Inspired by techniques for non-probabilistic programs, they adapt the idea of pruning parts of the program that are provably terminating. This is adapted to the probabilistic setting by considering sets of paths with positive measure.

Datasets

The paper evaluates its approach on two collections of benchmarks:

  1. Standard Collection: 90 benchmarks previously used for probabilistic analysis, derived from non-probabilistic programs with some probabilistic elements.
  2. General Collection: A larger set of 139 benchmarks, including the standard collection and additional "truly probabilistic" programs, as well as non-probabilistic termination benchmarks.

The authors note that their tool was able to prove termination for some benchmarks that previous tools failed on.

Key Insights and Ideas

  • Relaxing Nonnegativity is Crucial: The strict nonnegativity requirement in classical LexRSMs is a significant hurdle. By generalizing this, the authors unlock the ability to prove termination for programs that were previously untreatable.
  • Invariants are Overkill (Sometimes): The reliance on pre-computed invariants creates a bottleneck. An incremental approach that uses a safety prover to guide refinement is more efficient, especially for programs with simple termination proofs.
  • Pruning is Powerful, Even Probabilistically: The idea of "pruning" parts of a program that are already proven to terminate is effective. Adapting this to probabilistic programs, where counterexamples are sets of paths with positive measure, is a key technical contribution.
  • Cooperation Graphs for Structure: The use of cooperation graphs helps manage the complexity of probabilistic programs by breaking them down into smaller, more manageable components (maximal end components).

Key Results

The paper presents an algorithm that successfully proves almost-sure termination for a significant number of probabilistic programs.

  • Standard Benchmarks: Their tool achieved 66 successes out of 90, slightly trailing a previous "Invariant tool" (71 successes) but demonstrating unique successes on 9 benchmarks, including a challenging example from the literature (Figure 2a).
  • General Benchmarks: The tool achieved 98 successes out of 139, showing good generalization beyond the standard set.
  • Efficiency: The vast majority of successful proofs took less than 1 second, with an average time of 0.435 seconds.
  • Handling Difficult Cases: The approach successfully proved termination for programs that previous methods struggled with, particularly those that did not admit strongly nonnegative LexRSMs or suffered from the invariant insufficiency-inefficiency trade-off.

Limitations and Future Work

  • Affine Programs: The current algorithm is restricted to Affine Probabilistic Programs (APPs), where expressions are linear. The authors suggest extending it to handle polynomial arithmetic by combining their approach with existing techniques for polynomial RSM synthesis and safety checkers.
  • Safety Checker Dependence: The performance and success rate are significantly influenced by the underlying safety checker. Improvements in safety checking could further boost the tool's capabilities.
  • Quantitative Analysis: The authors suggest exploring the applicability of their approach to quantitative analysis of probabilistic programs, such as cost analysis.
  • Non-linear Arithmetic: Explicitly mentioned as a future direction is the extension to programs with non-linear arithmetic.

Summary updated

Abstract

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