Quantitative Verification of Infinite-State Networks

arXiv:2610.11991 · cs.FL, cs.LO, cs.PL · Submitted 2026-10-08 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: We're looking at the paper: "Quantitative Verification of Infinite-State Networks".

Jane: Here's the gist of the paper. We present a framework for the quantitative verification of acyclic networks of weighted pushdown systems (wPDSs).

Tom: This involves introducing segment tree algebras, a tree-like representation of runs in a wPDS that tracks corresponding weight semantics.

Jane: A saturation procedure computes a sequence of sets of accelerated trees that reaches a fixpoint, leading to an algorithm for QuantReach.

Tom: The framework is based on pumping semirings, which are defined by structural restrictions ensuring exact summarization of recursive network components.

Paper summary: Tom: So wrapping up this discussion on Quantitative Verification of Infinite-State Networks, the core contribution is establishing a framework that uses segment tree algebras and pumping semirings to provide exact quantitative verification for acyclic networks of weighted pushdown systems under specific weight constraints.

Jane: The paper shows that by defining these semirings, they can compute optimal bounds for safety and reachability, which directly translates into knowing the worst-case latency or failure rate for a network configuration.

Lu: They achieve this by unifying language closure computations with weight summaries, providing a tool to rigorously analyze how recursive components behave under those specific algebraic conditions.

Meng: The implication is that we have a more precise mathematical way to model and verify performance guarantees in systems with unbounded local state, provided the underlying structure adheres to the pumping semiring rules they defined.

Lalam: The work gives us concrete results, like computing upper bounds for things such as the Arctic pumping semiring to be cl: zero srv: zero which gives us a tangible number for performance limits in those scenarios <ref:2610.11991#pg1>.

Tom: The main limitation they highlight is that the algorithm terminates in a doubly exponential manner relative to the number of control states of P, so while it's exact under those constraints, scaling up to arbitrary control states will be computationally very hard.

Jane: So, we have this powerful exact tool for verifying these specific network types when the weight domains are restricted, and we know exactly where it stops being practical because of that exponential complexity.

Conclusion: Tom: So we’ve been looking at this paper, "Quantitative Verification of Infinite-State Networks," and basically, they're showing us a way to prove things about these massive systems without having to check every single possibility.

Jane: That’s right. The authors are tackling these infinite-state networks—these things with potentially endless possibilities for what can happen—and they’ve built this framework using something called segment tree algebras and pumping semirings.

Lu: What they did is introduce this tree-like representation of runs that tracks the weight semantics, which is key because it lets them handle all those recursive parts of the network in a structured way.

Meng: From my side, what I’m hearing is that they’ve created an algorithm to get some kind of exact bound on safety and reachability for these networks, provided you stick to certain rules about the underlying mathematical structures.

Lalam: Exactly. The main result they're pushing is Theorem Seven point two, which says they can solve this verification problem if every process in the network follows a specific structural rule called being thin or not thin with respect to its semiring.

Tom: So it’s about finding these optimal bounds for how safe or reachable a system is, and it hinges entirely on those structural rules they call pumping semirings.

Jane: And that structure lets them unify two different types of work—language closure computations and weight summaries—which is pretty cool because they bring together concepts from different areas of logic.

Lu: The complexity analysis shows that the algorithm runs in a doubly exponential time depending on the number of control states, but under those specific thin pumping semiring conditions, they can solve it for any global configuration you throw at them.

Meng: So for someone actually trying to deploy this stuff, it means we can get a concrete upper bound on what might break at scale for these types of systems when we know the weight constraints hold true.

Tom: It’s a powerful tool, but remember that doubly exponential complexity means it's really only practical if the number of control states isn't too big.

Jane: Right. But this opens up a whole new way to think about verifying complex systems, and it sets the stage for figuring out what happens when we add more complicated constraints to these networks down the road.

DHRUV NEVATIA, DAVID BASIN

ETH Zurich

cs.FL, cs.LO, cs.PL

Submitted: 2026-10-08

Updated: 2026-11-08

Comments: Accepted at POPL 2027. Full version with appendices, 46 pages, and 13 figures

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 98/100

The gist: We present a framework for the quantitative verification of acyclic networks of weighted pushdown systems (wPDSs).

Key concepts

Segment Tree Algebras
These are used as a tree-like representation of runs in a weighted pushdown system (wPDS). They track the corresponding weight semantics, helping to manage the complexity of recursive network components during verification.
Saturation Procedure
This procedure computes a sequence of sets of accelerated trees that eventually reaches a fixpoint. This process is central to finding an algorithm for QuantReach, which is used for quantitative verification.
Pumping Semirings
These are structural restrictions placed on semirings to ensure exact summarization of recursive network components. They are crucial for the framework's ability to handle the weight summaries in the networks.
$ ext{S}$-thin and $ ext{S}$-thick Pumping Semirings
Thin or thick pumping semirings dictate how well a system can be summarized. The paper proves that GenConfigReach is solvable under these conditions, allowing computation of optimal bounds for safety, reachability, and cost-bounded reachability.

Terminology

Summary

We present a framework for the quantitative verification of acyclic networks of weighted pushdown systems (wPDSs). p. 0

Where the paper says it

Existing decidability results for networks of pushdown systems are largely qualitative, and do not extend to quantitative analyses, which must jointly track traces and weights. We present a framework for the quantitative verification of acyclic networks of weighted pushdown systems.

This involves introducing segment tree algebras, a tree-like representation of runs in a wPDS that tracks corresponding weight semantics. p. 8
Where the paper says it

Given a pumping semiring S, a wPDS ⟨P, S, wt⟩, and two configurations 𝑐, 𝑐′ ∈ Config(P), wt [[𝑐, 𝑐′ ]] can be effectively computed. 4 SEGMENT TREE ALGEBRAS In this section, we describe a novel representation of runs in a wPDS.

A saturation procedure computes a sequence of sets of accelerated trees that reaches a fixpoint, leading to an algorithm for QuantReach. p. 0
Where the paper says it

The class admits domains with infinite ascending chains, such as the arctic semiring and downward-closed languages. Over these, we give a terminating saturation algorithm computing quantitative reachability exactly, resting on two ideas: segment tree algebras, a compositional representation of runs, and thermal extensions, which symbolically separate accelerated weights so that further acceleration remains exact.

The framework is based on pumping semirings, which are defined by structural restrictions ensuring exact summarization of recursive network components. p. 0
Where the paper says it

We present a framework for the quantitative verification of acyclic networks of weighted pushdown systems. Finitely summarising a recursive network component requires collapsing the infinite family of runs obtained by pumping its nested loops, and doing so exactly, rather than by over-approximation, is a standing difficulty.

The main result is Theorem 7. p. 3
Where the paper says it

This motivates the need for a principled approach that can tackle the analysis of all such networks. 2 Contributions Our principal result, developed in Section 7, is a framework for the quantitative verification of networks of wPDSs, where we provide the first quantitative verification algorithms for networks of pushdown systems.

2, which states that GenConfigReach can be solved for acyclic networks where every process's semiring S p is at most S p-thin (or at least S p-thin). This allows for the computation of optimal bounds for safety, reachability, and cost-bounded reachability. p. 0
Where the paper says it

Over these, we give a terminating saturation algorithm computing quantitative reachability exactly, resting on two ideas: segment tree algebras, a compositional representation of runs, and thermal extensions, which symbolically separate accelerated weights so that further acceleration remains exact. We use this to compute upward and downward closures of context-free languages uniformly, and to lift the algorithm to acyclic networks over thin pumping semirings, yielding the first quantitative safety and reachability analyses for networks of pushdown systems.

The framework unifies language closure computations and weight summaries. p. 1
Where the paper says it

One of the main ingredients in their algorithm is the computation of language closures. For instance, the downward closure of a set of words is the set of all subsequences of words in that set.

The complexity analysis shows that the algorithm terminates in a doubly exponential manner in the number of control states of P. For at most S-thin and at least S-thin pumping semirings, GenConfigReach can be solved for arbitrary global configurations c, c'. For example, for the Arctic pumping semiring, the worst-case upper bound is computed to be cl: 0, srv: 0. p. 2
Where the paper says it

A natural question is: “Are 𝑥 units sufficient for the client to clear its backlog? ” This amounts to computing the worst-case cost of reaching the target global state ⟨cl : idle,srv : fin⟩, from the initial state ⟨cl : 𝑖𝑛cl ,srv : 𝑖𝑛srv⟩, over all interleavings of the two processes; 𝑥 suffices when it exceeds this cost.

The decision problem ConfigReach is decidable for networks where all wPDSs are PDSs (Boolean semirings). p. 6
Where the paper says it

Essentially, we obtain a decision procedure for a quantitative variant of the reachability problem for wPDSs, as introduced in [44], but for a much larger class of semirings. In Section 7, we show that these semirings play a vital role in the quantitative verification of wPDS networks.

The complexity analysis shows that the algorithm terminates in a doubly exponential manner in the number of control states of P, with the weight domain contributing only to the base.

Furthermore, for countable sets of words W (e), a sequence of traces tau dagger 1 tau dagger 2 tau dagger 3 is constructed. p. 1

Where the paper says it

For instance, the downward closure of a set of words is the set of all subsequences of words in that set. The downward closure of the set of traces between two configurations of a PDS can be effectively computed as the language accepted by an NFA of size exponential in that of the input PDS [14].

Since S is at most S-thin, it can be shown that the weighted sum of these traces converges to a value a, i. p. 6
Where the paper says it

A weighted pushdown system is a 3-tuple ⟨P, S, wt⟩, where P = ⟨𝑄, 𝐴, Γ, Trans⟩ is a PDS, S = ⟨𝑆, ⊕, ⊗, 0, 1⟩ is an idempotent semiring, and wt : Trans → 𝑆 \ {0} is a weight function that assigns a non-zero value from 𝑆 to each transition in P. Given two configurations 𝑐, 𝑐′ ∈ Config(P), let Paths(𝑐, 𝑐′ ) := {𝛿1 · · · 𝛿𝑛 ∈ Trans∗ | 𝑐 𝛿1 ==⇒ · · · 𝛿𝑛 ==⇒ 𝑐 ′ } be the (possibly infinite) set of traces from 𝑐 to 𝑐 ′ .

e., sum n in N wt*(tau dagger n) = a. p. 6
Where the paper says it

To compute wtex [[⟨𝑞1, ⊣⟩, ⟨𝑞2, ⊣⟩]], we aggregate all these weights by taking their maximum, which is the infinite value ∞. If we instead switch to the tropical semiring, the infinite sum equals its least value, 3.

If S is at least S-thin, an auxiliary wPDS is constructed, and by using a topological order on the linear network N', GenConfigReach for the original network N is computed. Under this condition, it is shown that sum tau' in X wt*(tau') = wt*(tau) = a.

The algorithm employs two variants: a top-down approach for at most S-thin semirings (Algorithm 2/3), which uses TDSub to compute fixpoints based on an observation automaton A L recognizing the language L, and a bottom-up approach for at least S-thin semirings (Algorithm 4/5), which uses BUSub to compute fixpoints based on the observation automaton A L. p. 0

Where the paper says it

Over these, we give a terminating saturation algorithm computing quantitative reachability exactly, resting on two ideas: segment tree algebras, a compositional representation of runs, and thermal extensions, which symbolically separate accelerated weights so that further acceleration remains exact. We use this to compute upward and downward closures of context-free languages uniformly, and to lift the algorithm to acyclic networks over thin pumping semirings, yielding the first quantitative safety and reachability analyses for networks of pushdown systems.

The top-down approach relies on an asynchronous product, and the bottom-up approach utilizes an intersection of upward-closed constraint languages. p. 3
Where the paper says it

The same phenomenon occurs in networks with several hierarchical rate-limiting servers, such as those in the Linux kernel [36] and cloud-native applications like Envoy [17, 18] and DynamoDB [4]. This motivates the need for a principled approach that can tackle the analysis of all such networks.

The linearisation step reduces the network N to N' where processes have at most one parent and one child, simplifying computation by ensuring no process is merged or duplicated. The traces in this wPDS track both their upward closure and their weight with respect to wt. p. 0
Where the paper says it

Quantitative Verification of Infinite-State Networks DHRUV NEVATIA, ETH Zurich DAVID BASIN, ETH Zurich Many network protocols and distributed systems combine recursion, unbounded local state, and quantitative behaviour such as cost, latency, or reliability. Existing decidability results for networks of pushdown systems are largely qualitative, and do not extend to quantitative analyses, which must jointly track traces and weights.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Quantitative Verification of Acyclic Networks can be performed for networks of weighted pushdown systems by computing a sequence of sets of accelerated trees that reaches a fixpoint in polynomial time relative to the number of control states and exponentially in the size of the network.

  2. The system can compute GenConfigReach, which determines if a global configuration c is reachable from some configuration in C1 and whether every trace from C1 to c satisfies an upper bound r, for acyclic networks where process weight domains are thin pumping semirings.

  3. For specific classes of pumping semirings, the system can compute the worst-case latency or cost across all traces, such as using the Arctic semiring to find a bound on the worst-case cost of reaching a target global state.

  4. The system can compute optimal bounds for safety, reachability, and cost bounded reachability problems by reducing them to GenConfigReach over specific auxiliary networks N0 constructed from the input network N.

Abstract

Many network protocols and distributed systems combine recursion, unbounded local state, and quantitative behaviour such as cost, latency, or reliability. Existing decidability results for networks of pushdown systems are largely qualitative, and do not extend to quantitative analyses, which must jointly track traces and weights. We present a framework for the quantitative verification of acyclic networks of weighted pushdown systems. Finitely summarising a recursive network component requires collapsing the infinite family of runs obtained by pumping its nested loops, and doing so exactly, rather than by over-approximation, is a standing difficulty. We give a class of weight domains where this is possible: pumping semirings, those in which the weights accumulated by such a family collapse to a closed form; informally, the domain must be unable to count iterations. The class admits domains with infinite ascending chains, such as the arctic semiring and downward-closed languages. Over these, we give a terminating saturation algorithm computing quantitative reachability exactly, resting on two ideas: segment tree algebras, a compositional representation of runs, and thermal extensions, which symbolically separate accelerated weights so that further acceleration remains exact. We use this to compute upward and downward closures of context-free languages uniformly, and to lift the algorithm to acyclic networks over "thin" pumping semirings, yielding the first quantitative safety and reachability analyses for networks of pushdown systems.

Related papers