Quantitative Verification of Infinite-State Networks
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 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. 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. 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 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. 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. 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. 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. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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 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]. 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 𝑐
′
. 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.Where the paper says it
Where the paper says it
Where the paper says it
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 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 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
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
-
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.
-
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.
-
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.
-
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
- A Unary-to-Nonunary Transition in the Accepting-State Spectrum of Right Quotient for Permutation Automata
- Positive-Data Learning of Fixed-Observation Linear MCFGs from Working Binary Presentations
- On the Separability Problem of VASS Reachability Languages
- Exact Accepting-State Spectrum for Reversal of Permutation Automata
- An exact compress-with-another threshold in a binary automaton family
- When Does Tool Use Increase the Expressive Power of Finite-Precision Recurrent Models?