Abstract
We study termination of higher-order probabilistic functional programs with recursion, stochastic conditioning and sampling from continuous distributions. Reasoning about the termination probability of programs with continuous distributions is hard, because the enumeration of terminating executions cannot provide any non-trivial bounds. We present a new operational semantics based on traces of intervals, which is sound and complete with respect to the standard sampling-based semantics, in which (countable) enumeration can provide arbitrarily tight lower bounds. Consequently we obtain the first proof that deciding almost-sure termination (AST) for programs with continuous distributions is $\Pi^0_2$-complete. We also provide a compositional representation of our semantics in terms of an intersection type system. In the second part, we present a method of proving AST for non-affine programs, i.e., recursive programs that can, during the evaluation of the recursive body, make multiple recursive calls (of a first-order function) from distinct call sites. Unlike in a deterministic language, the number of recursion call sites has direct consequences on the termination probability. Our framework supports a proof system that can verify AST for programs that are well beyond the scope of existing methods. We have constructed prototype implementations of our method of computing lower bounds of termination probability, and AST verification.
Introduction
In the realm of formal verification, program termination is traditionally a binary property. However, the rise of probabilistic programming—used in fields ranging from machine learning to robotics—requires a more nuanced approach. In these systems, we ask: what is the probability that a program terminates? A program is defined as Almost-Sure Terminating (AST) if it finishes its execution with probability 1.
While robust tools exist for programs with discrete probabilistic choices (e.g., coin flips), programs that sample from continuous distributions (e.g., Gaussian or Uniform distributions) present significant theoretical and practical hurdles. In a continuous state space, any single execution path occurs with probability zero, rendering standard path-counting techniques ineffective. Furthermore, existing methods often struggle with non-affine recursion, where a function body may trigger multiple recursive calls. This paper introduces a novel semantic framework and verification techniques to address these challenges.
Methodology
Interval-based Operational Semantics
The core difficulty in analyzing continuous distributions is the uncountable nature of the execution space. Standard sampling-based semantics, as shown in Figure 1, rely on precise real-valued samples which do not easily lend themselves to lower-bound computations via enumeration.
To resolve this, the authors propose a novel interval-based operational semantics (Figure 2). Instead of tracking exact values, this semantics tracks "traces of intervals." By grouping uncountably many individual executions into countable sets of interval-based paths, the authors create a framework where one can compute increasingly tight lower bounds on termination probability. This approach is proven to be both sound and complete with respect to the standard sampling-based model.
Counting-based Recursion Analysis
To handle non-affine recursion, the authors shift the focus from the size of function arguments to the number of recursive calls. They instrument programs to count pending calls and model the execution as a random walk on integers. If the "drift" of this random walk is biased toward zero, the program is guaranteed to be AST. This reduction simplifies complex program behavior into a decidable mathematical problem.
Game-Playing and Type Systems
To automate analysis when branching depends on random values, the environment is treated as an adversary in a two-player game. If a program terminates regardless of the environment's "strategy" (i.e., which branch is taken), it provides a safe lower bound for AST. These concepts are formalized into an intersection type system, allowing for the compositional derivation of termination probabilities and expected execution times.
Results and Evaluation
The authors implemented their methods in prototype tools and evaluated them against a suite of benchmark probabilistic programs, including models of geometric distributions, 1D biased random walks, and complex non-affine terms like a "faulty 3D printer" model.
Key Insights
- Complexity Bounds: The paper establishes that deciding AST for programs with continuous distributions is $\Pi^0_2$-complete in the arithmetic hierarchy—the same complexity class as discrete programs.
- Efficiency: AST verification for complex non-affine terms typically took less than a second, demonstrating the computational efficiency of the random walk reduction.
- Precision: For lower-bound computation, the interval-based tool provided extremely tight bounds (e.g., $0.999999...$) within milliseconds to seconds.
Conclusion
This research provides a foundational framework for the termination analysis of higher-order probabilistic programs. By introducing interval-based semantics and a call-counting approach for non-affine recursion, the authors enable the verification of programs that were previously beyond the reach of state-of-the-art methods. Future work includes extending the implementation to handle non-linear constraints and developing a unified framework that combines call-counting with traditional size-based ranking functions.
Summary updated