💻 computer science

On Higher-Order Probabilistic Verification via the Weighted Relational Model of Linear Logic

This paper establishes the decidability of almost sure termination for a class of Probabilistic Higher-Order Recursion Schemes (PHORS) extending affine systems by utilizing weighted relational semantics of linear logic to prove that their associated generating functions are algebraic.

Original authors: Ugo Dal Lago, Guido Fiorillo, Paolo Pistone

Published 2026-05-01

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ugo Dal Lago, Guido Fiorillo, Paolo Pistone

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

The Big Picture: The "Will It Ever Stop?" Problem

Imagine you are watching a computer program run. This program is a bit like a choose-your-own-adventure book, but with a twist: at every page, there is a coin flip. Heads, you go left; tails, you go right. Some paths lead to an ending (the program stops), while others might lead you in circles forever.

The big question computer scientists ask is: "Will this program eventually stop, or will it run forever?"

For simple programs, we can answer this easily. But for complex, "higher-order" programs (programs that can pass other programs around like data), this question becomes incredibly hard. In fact, for the most general type of these probabilistic programs, the answer is: We can never know for sure. It is mathematically impossible to create a universal tool that checks every single one of these programs and tells you if it stops.

The Authors' Solution: Counting with Magic Math

The authors of this paper, Ugo Dal Lago, Guido Fiorillo, and Paolo Pistone, didn't try to solve the impossible problem for every program. Instead, they asked: "Can we find a special, useful group of these programs where we can prove they stop?"

They found a way to do this by translating the problem into a different language: Algebraic Generating Functions.

The Analogy: The Infinite Recipe Book

Imagine the program is a recipe book. Every time the program makes a choice (a coin flip), it writes down a step.

If the program stops after 1 step, that's one path.
If it stops after 2 steps, that's another path.
If it stops after 1,000 steps, that's another.

Because the program is probabilistic, some paths are more likely than others. The authors' method creates a special mathematical "recipe card" (called a generating function) that summarizes the entire infinite history of the program.

Think of this card like a magic calculator:

The Probability of Stopping: If you plug the number 1 into this calculator, it tells you the total probability that the program will ever finish. If the result is 1, it means the program is guaranteed to stop (almost surely).
The Average Time: If you tweak the calculator slightly (take a derivative), it tells you the average number of steps it takes to finish.

The Secret Ingredient: Linear Logic and "Bounded" Usage

How did they build this magic calculator? They used a tool from a branch of math called Linear Logic.

In normal math, you can use a number as many times as you want. In Linear Logic, resources are precious. You have to track exactly how many times you use an ingredient.

The Problem: If a program uses a variable (an ingredient) an infinite, uncontrolled number of times, the math gets messy and the "magic calculator" breaks.
The Fix: The authors introduced a rule called "Bounded Exponentials."

The Metaphor: Imagine you are baking a cake.

Unbounded: You have a magical oven that can bake infinite cakes at once. You lose track of how many you made. The math explodes.
Bounded (The Authors' Rule): You have a rule that says, "You can use this specific ingredient at most 2 times," or "at most 5 times." Even if the program is complex, as long as it respects these "usage limits," the math stays tidy.

By forcing the programs to respect these limits, the authors proved that the "magic calculator" (the generating function) always results in a polynomial equation. This is a huge deal because polynomial equations are solvable. We have known, reliable methods to solve them.

What Did They Actually Achieve?

The paper claims three main things:

A New Translation Method: They showed how to take a complex probabilistic program and translate it directly into a system of polynomial equations using a "weighted relational model." This model counts exactly how many times the program uses its inputs.
Solving the "Affine" Case (and more): Previous researchers had shown that if a program uses every input at most once (called "affine"), we can decide if it stops. The authors went further. They showed that even if a program uses an input a fixed, small number of times (like 2 or 3 times), we can still solve the equation and decide if it stops.
Handling "Infinite" Parameters: They found a clever trick to handle cases where a program uses a variable an infinite number of times, but only if that variable acts like a formal parameter (like a placeholder in a template) rather than a dynamic resource. This allowed them to solve even larger classes of programs.

The Bottom Line

The authors didn't invent a new computer language. Instead, they built a bridge between two worlds:

The messy, unpredictable world of probabilistic higher-order programming.
The clean, solvable world of algebraic equations.

By building this bridge, they proved that for a significant and useful class of these programs, we can finally answer the question: "Will it stop?" with a definite "Yes" or "No," using standard mathematical tools rather than guessing. They essentially turned an unsolvable mystery into a solvable math puzzle.

1. Problem Statement

The paper addresses the Almost Sure Termination (AST) and Positive Almost Sure Termination (PAST) problems for Probabilistic Higher-Order Recursion Schemes (PHORS).

Context: PHORS are probabilistic extensions of Higher-Order Recursion Schemes (HORS), equivalent to the simply-typed $\lambda$ -calculus with a fixpoint operator and probabilistic choices.
The Challenge: While termination is decidable for standard HORS (order-2 and above), the AST problem for PHORS is undecidable (specifically $\Pi^0_2$ -complete) starting from order 2.
Existing Limitations: Previous decidability results were limited to:
- Order-1 PHORS.
- Affine PHORS (PAHORS): Programs where variables are used at most once (linear/affine types).
- These results relied heavily on automata theory (e.g., tree stack automata) or game semantics.
Goal: The authors aim to identify a broader class of PHORS (beyond affine) for which AST and PAST are decidable, using a novel approach based on generating functions and linear logic, rather than automata.

2. Methodology

The core methodology involves translating the probabilistic execution of a PHORS into the computation of formal power series (generating functions) using the weighted relational model of linear logic.

A. Weighted Relational Semantics

The authors utilize the weighted relational model over a continuous semiring (specifically $\mathbb{R}_{\ge 0}^{\infty}[[z]]$ ).

Interpretation: Terms are interpreted as families of formal power series where coefficients represent probabilities.
The Variable $z$ : A distinguished variable $z$ is introduced to count the number of probabilistic choices (reduction steps).
Probabilistic Choice: The operation $M \oplus_p N$ is interpreted as $p \cdot z \cdot \llbracket M \rrbracket + (1-p) \cdot z \cdot \llbracket N \rrbracket$ .
Generating Function: For a PHORS $G$ $G$ , the interpretation yields a generating function $a_G(z) = \sum_{n=0}^{\infty} P(G \downarrow n) z^n$ $a_{G} (z) = \sum_{n = 0}^{\infty} P (G ↓ n) z^{n}$ , where $P(G \downarrow n)$ $P (G ↓ n)$ is the probability that $G$ $G$ terminates in exactly $n$ $n$ steps.
- AST: Decidable if $a_G(1) = 1$ .
- PAST: Decidable if the expected number of steps $a'_G(1) < \infty$ .

B. Algebraic Power Series and FAS

The central insight is that if the generating function $a_G(z)$ is algebraic (i.e., it satisfies a system of polynomial equations), then AST and PAST become decidable via the Existential Theory of the Reals (ETR).

The Obstacle: General PHORS generate infinite systems of equations (due to higher-order types), which are not necessarily algebraic.
The Solution: The authors restrict the language to classes where the infinite system of equations can be reduced to a Finite Algebraic System (FAS). This is achieved by bounding the "usage" of inputs.

3. Key Contributions

1. Combinatorial Characterization via Linear Logic

The paper provides the first combinatorial study of PHORS termination using the weighted relational model. It establishes a direct link between the usage of variables in a program and the algebraic nature of its generating function.

2. Introduction of PBHORS $<\infty$ (Finitely Bounded PHORS)

The authors define a new class of programs, PBHORS $<\infty$ , which extends the affine class (PAHORS) by allowing bounded non-linearity.

Type Discipline: Uses graded types of the form $!_k A \multimap B$ , meaning a function can use its input of type $A$ at most $k$ times.
Result: For any PHORS in this class, the associated generating function is algebraic.
Linearization: The authors prove that any PBHORS $<\infty$ can be effectively transformed (linearized) into an equivalent affine PHORS (PAHORS). While this transformation may cause an exponential blow-up in size, it proves that the class is semantically equivalent to the affine case, thereby inheriting decidability.

3. Introduction of PBHORS $^\infty$ (Parametric Bounded PHORS)

To capture even more complex programs, the authors introduce PBHORS $^\infty$ , which allows unbounded usage of specific parameters (infinite grades $!_\infty$ ).

Mechanism: Variables with infinite grade are treated as formal parameters rather than concrete inputs. The generating function becomes a series with coefficients in a ring of power series over these parameters.
Compositionality: This class is closed under composition. The authors show that a closed PBHORS $^\infty$ can be reduced to a parametric PBHORS $<\infty$ .
Result: The generating functions for this larger class remain algebraic, preserving decidability for AST and PAST.

4. Decidability Proofs

The paper proves that for both PBHORS $<\infty$ and PBHORS $^\infty$ :

The generating function $a_G(z)$ is the minimal solution of a finite system of polynomial equations.
AST is decidable by checking if the minimal non-negative solution at $z=1$ equals 1.
PAST is decidable by checking if the derivative of the solution at $z=1$ is finite.
These checks are performed using the decidability of the first-order theory of the reals (Tarski's theorem).

4. Key Results

Algebraicity: The generating functions for all programs in the defined classes are algebraic power series. This contrasts with general PHORS, where generating functions can be non-algebraic (e.g., related to indexed grammars).
Decidability: AST and PAST are decidable for the extended classes PBHORS $<\infty$ and PBHORS $^\infty$ .
Complexity: The decision procedure has a time complexity that is polynomial in the size of the program for a fixed order, but grows super-exponentially with the order (due to the size of the generated FAS).
Semilinearity: The set of step counts for which a program terminates is a semilinear set (a union of linear sets), a property derived from the algebraic nature of the series.
Comparison with Affine: The new classes strictly extend the affine PHORS (PAHORS) of Li et al. [38]. For example, they can handle programs where a function is used twice (bounded non-linearity) or where parameters are duplicated arbitrarily (infinite grades), provided the structure fits the type discipline.

5. Significance and Impact

New Paradigm: The paper shifts the verification of probabilistic higher-order programs from automata-theoretic methods (which are complex and specific to affine types) to algebraic/combinatorial methods. This opens the door to applying tools from analytic combinatorics (e.g., asymptotic analysis, singularity analysis) to probabilistic verification.
Robustness of Affine Results: The work demonstrates that the decidability of AST for affine PHORS is not an isolated phenomenon but part of a broader algebraic structure. It shows that the "fragility" of decidability (where minor extensions break it) can be managed by carefully controlling variable usage via graded types.
Modularity: The composability of PBHORS $^\infty$ allows for modular verification, where components can be analyzed separately as parametric systems and then composed.
Open Problems: The authors suggest that this framework could be extended to D-finite power series (solutions to linear differential equations) and could potentially help resolve the exact position of the AST problem within the arithmetic hierarchy.

In summary, the paper successfully bridges Linear Logic, Formal Power Series, and Probabilistic Verification, providing a powerful, algebraic framework to decide termination for a significantly larger class of higher-order probabilistic programs than previously possible.