💻 computer science

Weakly Non-Negative Supermartingales for Omega-Regular Verification

This paper introduces lazy Streett supermartingales and their lexicographic extensions to enable sound, automated verification of almost-sure $\omega$ -regular properties in probabilistic programs using weakly non-negative polynomial templates, thereby expanding the search space and significantly improving verification success rates over traditional strongly non-negative methods.

Original authors: Toru Takisaka, Hongjie Qing, Libo Zhang

Published 2026-07-21

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Toru Takisaka, Hongjie Qing, Libo Zhang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to solve a mystery inside a computer program. But this isn't a normal program; it's a "probabilistic" one, meaning it makes decisions by rolling dice. Sometimes it goes left, sometimes right, and sometimes it might get stuck in an infinite loop forever. Your job is to prove that, no matter how the dice roll, the program will eventually finish its job or follow a specific set of rules. To do this, mathematicians use a clever tool called a "martingale." Think of a martingale as a magical scorecard. If you can find a scorecard that consistently goes down (or stays controlled) as the program runs, you know the program is safe and will eventually stop.

For a long time, these scorecards had a strict rule: they had to be positive numbers everywhere, like a bank account that never goes into debt. This made finding a scorecard very hard, like trying to find a specific key in a giant pile of keys, but you're only allowed to look at the shiny gold ones. The researchers in this paper asked a simple question: "What if we allow the scorecard to go negative, just for a little while, as long as it behaves nicely when it's actually running?" They discovered that if you relax this rule carefully, you can find scorecards much more easily, proving that complex programs are safe in ways that were previously impossible to check.

The Paper's Big Idea: Lazy Scorecards for Dice-Rolling Programs

This paper introduces a new, more flexible way to build these magical scorecards, which the authors call Lazy Streett Supermartingales. To understand why this is a big deal, let's look at the problem they are solving.

In the world of computer verification, we often deal with programs that have loops. We want to know: "Will this loop ever stop?" or "Will this program keep doing the right thing forever?" To answer this, we use a certificate—a mathematical function that acts like a watchdog. If the watchdog sees the program's value dropping steadily, it knows the program is heading toward a finish line.

However, there's a catch. For decades, these watchdogs had to be strictly non-negative. Imagine a hiker trying to prove they will reach the bottom of a mountain. The old rule said, "You can only count your steps if you are above sea level." If the hiker dips below sea level for a second, the whole proof breaks, even if they are clearly heading down. This made it very hard to find a proof for many programs because the "perfect" scorecard might dip below zero in some theoretical scenarios, even if the program itself never actually gets stuck there.

The authors realized that this strict rule was too picky. They proposed a new kind of scorecard that is weakly non-negative. This is like telling the hiker: "It's okay if you dip below sea level for a moment, as long as you don't stay there forever and as long as you behave nicely when you do."

But here's the tricky part: in a world of rolling dice (probabilistic programs), being "nice" is harder than it sounds. The paper points out a famous trap: if you just relax the rule without thinking, you might accidentally create a "fake" proof. You could have a scorecard that looks like it's going down, but the program actually runs forever because the dice rolls conspire to keep the scorecard negative in a way that tricks the math.

To fix this, the authors invented a very specific set of conditions called "relative well-behavedness." Think of this as a safety net for the dice. It ensures that the random number generators in the program (the dice) don't have "wild" tails that stretch out to infinity. As long as the dice rolls are bounded or behave in a predictable way (which is true for almost all real-world random processes), this safety net guarantees that the "lazy" scorecard won't be tricked. Without this specific condition, the proof would fail when using the complex polynomial equations often found in modern software. With it, the proof becomes rock-solid.

The Solution: "Lazy" and "Streett"

The paper combines two powerful ideas to solve this:

Lazy: This means the scorecard doesn't have to be perfect everywhere. It only has to be strictly positive when the program is in the "danger zone" (the part of the loop we are trying to prove will end). If the program is in a safe zone, the scorecard can be negative, as long as it has a rule that says, "If I'm negative, I stay negative." This prevents the program from using a negative score to cheat its way into an infinite loop.
Streett: This is a fancy name for a type of rule that handles complex, long-term behaviors (called $\omega$ -regular properties). Instead of just asking "Will it stop?", we can ask "Will it keep checking the traffic light forever?" or "Will it eventually visit the post office?" The "Streett" part allows the scorecard to handle these complex, multi-step promises.

The authors call their new tool Lazy Streett Supermartingales. They proved mathematically that if you use these tools with polynomial equations (a common type of math used in programming), and if the random number generators in the program are "relatively well-behaved" (meaning they don't have wild, unbounded tails), then the proof is solid.

Why This Matters: The Results

The researchers didn't just write a theory; they built a tool to test it. They took 170 different computer programs (benchmarks) that were already known to be tricky. They ran their new "lazy" method against the old "strict" method.

The results were impressive. The old method, which demanded the scorecard never go negative, managed to verify 88 of the 170 programs. The new "lazy" method, which allowed the scorecard to dip below zero under controlled conditions (and with the "relative well-behaved" safety net), successfully verified 128 programs. That is a jump of about 20 to 23.5 percentage points.

In simple terms, by relaxing the rules just a tiny bit and being smart about how they relaxed them—specifically by ensuring the random dice rolls are "relative well-behaved"—the authors found a way to prove that many more programs are safe than we could before. They showed that we don't need to throw away the "negative" possibilities; we just need to understand them better. This makes it much easier for computers to automatically check if our software is reliable, especially when that software involves randomness, like AI or simulations.

The paper concludes that this approach is not just a theoretical curiosity but a practical upgrade. It opens the door to verifying more complex systems without getting stuck on the rigid requirement that every mathematical step must be positive. It's a reminder that sometimes, to find the truth, you have to be willing to look at the shadows, not just the light.

Technical Summary: Weakly Non-Negative Supermartingales for Omega-Regular Verification

1. Problem Statement

Martingale-based methods are central to the verification of probabilistic programs, particularly for certifying almost-sure termination and the almost-sure satisfaction of $\omega$ -regular properties. A significant bottleneck in the algorithmic applicability of these methods is the requirement for strong global non-negativity of the supermartingale certificates. While restricting the search space to tractable classes (e.g., linear or polynomial templates) is necessary for automated synthesis, the strict non-negativity constraint often excludes simple, valid certificates that lie outside the search space.

Relaxing the non-negativity requirement (allowing "weakly non-negative" functions) enlarges the search space but introduces a critical challenge: in the probabilistic setting, naive relaxations are unsound. Unlike the non-probabilistic case, a function that decreases in expectation but can take arbitrarily negative values may fail to certify almost-sure termination or $\omega$ -regular satisfaction. Prior work established soundness for weakly non-negative lexicographic ranking supermartingales (RSMs) only under restrictive conditions: linear templates, linear arithmetic updates, and specific "well-behaved" sampling distributions. These limitations hinder the application of weak non-negativity to general polynomial probabilistic programs and broader $\omega$ -regular specifications.

2. Methodology and Technical Approach

The paper introduces Lazy Streett Supermartingales (Lazy SSMs) and their lexicographic extension, Lazy LexSSMs, to address these limitations. The methodology rests on three core technical pillars:

A. Relatively Well-Behaved Distributions

The authors identify that the existing "well-behavedness" condition, tailored for linear templates, is too restrictive for polynomial templates. Specifically, under polynomial functions, even uniform distributions over intervals fail the standard well-behavedness condition because the "mean shortfall" of a polynomial can remain constant while the probability of negativity vanishes.

To overcome this, the paper introduces Relative Well-Behavedness. This new condition establishes a trade-off: if the probability of a polynomial function being negative vanishes, the mean shortfall must vanish relative to the mean value of the function. The authors prove that all bounded-support distributions satisfy this relative condition for polynomial templates. This generalization is essential for extending soundness proofs from linear to polynomial settings.

B. Soundness Proof via Fractional-Power Transforms

The soundness proof for Lazy SSMs employs a novel strategy distinct from prior linear proofs. Instead of directly analyzing the multi-dimensional lexicographic object, the authors:

Isolate the soundness proof for one-dimensional Lazy SSMs.
Utilize a fractional-power transform of the supermartingale, $(\eta^+)^\theta$ for $\theta \in (0,1)$ .
Leverage the relative well-behavedness condition and Jensen's inequality to show that this transformed function satisfies the conditions of a strongly non-negative Streett Supermartingale (SSM).
This transformation allows the ranking condition of the original weakly non-negative function to be translated into a valid ranking condition for the transformed, non-negative function, thereby certifying almost-sure satisfaction.

C. Compositional Lexicographic Lifting

The paper provides a compositional account of lexicographic certificates. It demonstrates that a lexicographic SSM is equivalent to a sequence of one-dimensional SSMs that jointly certify the target property.

Decomposition: An $\omega$ -regular Streett condition $(S_{Fin}, S_{Inf})$ is decomposed into a sequence of Streett pairs $(S^{(i)}_{Fin}, S^{(i)}_{Inf})$ .
Equivalence: The authors prove that a sequence of one-dimensional Lazy SSMs, each witnessing a specific decomposed Streett pair, is equivalent to a single lexicographic Lazy SSM.
Benefit: This approach simplifies the soundness proof for multi-dimensional martingales, reducing it to a corollary of the one-dimensional case, avoiding the complex analysis of non-standard lexicographic orders.

D. Program MDPs

The formalism is defined over Program MDPs, a subclass of Markov Decision Processes (MDPs) that abstracts the specific properties of probabilistic control flow graphs (pCFGs). This abstraction explicitly axiomatizes properties like independent updates and finite variety of randomization, clarifying the scope of the soundness results and allowing for measurable (non-linear) program updates.

3. Key Contributions

Lazy Streett Supermartingales (Lazy SSMs): A new martingale notion combining "lazy" (weakly non-negative) RSMs and Streett supermartingales. This enables the certification of almost-sure satisfaction of general $\omega$ -regular properties (not just termination) with weak non-negativity.
Polynomial Soundness under Bounded Support: The paper proves the soundness of polynomial Lazy SSMs under the assumption of relative well-behavedness. Crucially, it shows that all bounded-support distributions satisfy this condition, significantly broadening the class of applicable probabilistic programs compared to prior work which required "well-behaved" distributions and linear arithmetic.
Compositional Lexicographic Framework: A new proof strategy that lifts the soundness of one-dimensional SSMs to lexicographic variants via a sequence of one-dimensional certificates, simplifying the theoretical analysis.
Automated Synthesis Algorithm: An algorithm for synthesizing polynomial Lazy LexSSMs that incrementally constructs a sequence of certificates, handling the incomparability of conditions at different program locations via "STAB" (stability at negativity) and "WORST" (worst-case unaffecting) options.

4. Experimental Results

The authors evaluated their approach on 170 synthetic benchmarks of polynomial probabilistic programs with $\omega$ -regular specifications (derived from LTL-VerP benchmarks). The experiments compared three variants:

STR: Strongly non-negative LexSSM (baseline).
WORST: Lazy LexSSM with the "WORST" option.
STAB: Lazy LexSSM with the "STAB" option.

Results:

The baseline (STR) successfully verified 88 instances (51.7%).
The WORST variant verified 128 instances (75.2%).
The STAB variant verified 122 instances (71.7%).
The union of WORST and STAB successes reached 134 instances (78.8%).

This represents an increase in verification success of 20.0–23.5 percentage points over the strongly non-negative baseline. The results demonstrate that relaxing the non-negativity requirement substantially improves the algorithmic applicability of template-based synthesis for $\omega$ -regular verification.

5. Significance and Claims

The paper claims to significantly generalize the scope of weakly non-negative martingale methods. By moving from linear to polynomial templates and from reachability (termination) to general $\omega$ -regular properties, the authors extend the utility of weak non-negativity to a broader class of probabilistic programs.

The significance lies in:

Soundness under Practical Assumptions: The shift to "relative well-behavedness" allows the use of common bounded-support distributions (like uniform distributions) with polynomial templates, which were previously ruled out by stricter conditions.
Theoretical Unification: The paper unifies the concepts of lazy RSMs and Streett supermartingales, providing a compositional framework that simplifies the verification of complex $\omega$ -regular properties.
Practical Impact: The experimental results confirm that the theoretical relaxation of constraints translates directly into a higher success rate for automated verification tools, making the verification of complex probabilistic programs more feasible.

The authors maintain a modest tone regarding the limitations, noting that the synthesis algorithm is not known to be complete or polynomial-time due to the incomparability of martingale conditions at different locations, a limitation inherited from the underlying lazy RSM synthesis problem.