The Best of Times, the Worst of Times: Moment-Based Analysis of Probabilistic Cost Structures

arXiv:2607.25361 · cs.PL · Submitted 2026-07-28 · 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: "The Best of Times, the Worst of Times".

Title and authors: Tom: So, to get into the meat of "The Best of Times, the Worst of Times: Moment-Based Analysis of Probabilistic Cost Structures," they are focusing on how to calculate moments like the average or how spread out things are when costs involve max and min.

Jane: Exactly. The main problem is that those max and min operations mess with standard math; you can't just take the average of two random costs to get the average of their maximum cost, for example.

Tom: Right. So they tackle this by using a bottom-up approach over the program structure, breaking it into smaller pieces as they go.

Jane: And at every piece, instead of just giving one number for that subproblem, they use something called a prefix–tail summary distribution to describe it.

Tom: A prefix–tail distribution means they keep the exact beginning of the cost's probability shape and then use a compact mathematical description for everything else.

Jane: That allows them to track two different kinds of errors as they build up through the program structure—one for how well they capture that overall shape, and one for how accurately they estimate a specific expected value.

Tom: I see it as separating the problem into two error types. The first error is about the shape of what's happening, and the second error is about getting a precise number on that shape.

Jane: That’s key because when you combine these pieces using those max or min operations, the shape error gets translated into an estimation error for your final moments.

Tom: So they show that keeping that distributional shape information is actually more accurate than just using simple averages or guessing based on a few numbers.

Jane: They prove this by showing that retaining the shape information keeps sound intervals for both the first and second moments, which means you still have a guarantee about how much the cost can vary around its expected value.

Tom: And they don't stop at just the mean and variance; they show how to use moment-indexed error bounds when you need to track higher orders, like the third or fourth moment.

Jane: This framework is built with primitives and components that handle addition, choice, repetition, and those extremal operators like max and min all in one system.

Tom: It’s about having a systematic way to analyze these complex probabilistic programs without needing the whole distribution at once.

Jane: And they point out that you can make this analysis smarter by increasing the depth of that prefix—how deep they look locally—or by promoting small subproblems to known results, which trades some analysis time for better accuracy.

Tom: It sounds like a tool that lets you get a good balance between how much computation you spend analyzing and how confident you are in your final cost estimates.

Jane: The real implication is that for systems with nonlinear costs, like quantum repeater waiting times or complex scheduling, we can move past just using simple averages to get more reliable performance predictions.

Tom: So it gives us a rigorous method for when the math gets complicated by those max and min operations in probabilistic programs.

The paper's summary: Tom: So, the paper isn't just sitting there; they suggest ways to make their analysis even better by refining how they handle those error bounds.

Jane: They talk about increasing the depth of that prefix, which means looking deeper into the local structure to reduce those shape errors at smaller steps.

Tom: That way, you cut down on the error introduced when you're just making a quick summary of a small piece of the cost expression.

Jane: And they also suggest using a strategy called moment-directed abstraction when you specifically need to track higher moments, like the third or fourth order ones.

Tom: So if your goal is high precision for those specific orders, you use that specific abstraction instead of just sticking with a simpler one that might be faster to compute.

Jane: They also mention exact subtree promotion as another way to handle small subproblems; you replace them with a known result, which trades analysis time for tighter bounds on that part.

Tom: That sounds like a practical trade-off; you spend more time analyzing the small part, but you get a much better estimate for the whole system.

Jane: The real implication here is that this framework isn't just theoretical; it offers actionable steps to improve the analysis itself so that it's more efficient and precise in practice.

Tom: It means we can use these suggestions to build systems where we can trade off analysis cost for accuracy exactly where it matters most.

Jane: And they also show how you can use an analysis-guided search mechanism to find where the cost estimation is weakest before you even start comparing different system designs.

Tom: That’s a pretty cool feature; it means the tool can actually help guide the design process rather than just being a final check after everything is built.

Jane: So we're moving from just analyzing a program to actively improving the program by figuring out which parts need more attention first.

The paper's improvements: Tom: So to wrap up, this paper on "The Best of Times, the Worst of Times: Moment-Based Analysis of Probabilistic Cost Structures" shows how you can get solid error bounds on moments for probabilistic programs that use max and min costs.

Jane: It means we don't have to rely only on simple averages when analyzing those complex systems in real life because this method tracks both the distribution shape and the moment estimates separately.

Tom: They prove that retaining the distributional shape information actually gives you more accurate cost predictions than just using simpler scalar approximations.

Jane: And they show that by carefully managing how deep you go into local analysis, like increasing the prefix depth, or using smart abstraction choices, you can get tighter error bounds without making the whole thing impossible to calculate.

Tom: It’s a systematic way to balance how much analysis time you spend against how confident you are in your final numbers.

Jane: The implication is that for real systems—like those with quantum repeater waiting times or RFID collision resolution—we can finally trust the cost predictions because we have concrete intervals on their accuracy.

Tom: It moves us away from just hoping a rough estimate is good enough to be useful, to actually knowing the math behind the uncertainty.

Jane: Lu, what do you think about how this method handles those higher moments?

Lu: I think tracking them with moment-indexed error bounds is really smart because it shows you exactly where the precision loss comes from when you go beyond just the mean and variance.

Meng: From an engineering standpoint, knowing that we have these specific bounds helps us decide what level of refinement is actually necessary for deployment, instead of guessing how much error we can afford.

Lalam: I'm confident in this framework; it rigorously connects the nonlinear cost structure to a moment-based analysis, which means the results are very sure.

Tom: So, if you’re working on something where costs are combining in a nonlinear way and you need to predict the average performance of that system, this paper gives you a systematic way to compute those moments reliably.

Conclusion: Tom: So we've just finished talking about "The Best of Times, the Worst of Times: Moment-Based Analysis of Probabilistic Cost Structures." We looked at how this framework handles costs that use max and min operations instead of simple addition.

Jane: Right. The main idea is that these nonlinear operations break standard moment rules, so they propose a way to track the distribution shape alongside the moment estimates.

Tom: Exactly, and they do it by breaking the cost expression down piece by piece from the bottom up using prefix–tail summaries at each step.

Jane: That means they keep an exact short time prefix of the cost's probability shape and a compact description for everything else in a tail.

Lu: That shape information is crucial because it lets them propagate error bounds on both the distribution's shape and the moment estimates as they climb up the entire program structure.

Meng: So if we have a cost that involves something like taking the maximum of two random variables, just knowing their average isn't enough to predict how big that maximum will be.

Tom: That’s right. It’s about those extremal operations which make simple moment propagation fail because the moments of max or min aren't determined by the moments of the inputs alone.

Jane: They show that keeping that distributional shape information provides more accurate cost predictions than using simpler scalar approximations, because it keeps sound intervals for both the first and second moments.

Lu: That means we still have a guarantee about how much the cost can fluctuate around its expected value even when things get complicated.

Tom: And they don't stop at just the mean and variance; they show how to use moment-indexed error bounds when you need to track those higher orders, like the third or fourth moment.

Jane: This framework is built with primitives that handle addition, choice, repetition, and those max and min operators all in one system.

Meng: From an engineering standpoint, knowing that we have these specific bounds helps us decide what level of refinement is actually necessary for deployment instead of guessing how much error we can afford.

Wrap-up: Lu: They also point out that exact subtree promotion is a way to handle smaller subproblems by replacing them with a known result, which trades analysis time for tighter bounds on those specific parts of the structure.

Tom: It sounds like they've built a very versatile tool that can handle addition, choice, repetition, and those extremal operators like max and min all in one system.

Jane: The real implication here is that this framework isn't just theoretical; it offers actionable steps to improve the analysis itself so that it's more efficient and precise in practice.

Tom: It means we can use these suggestions to build systems where we can trade off analysis cost for accuracy exactly where it matters most.

Jane: And they also show how you can use an analysis-guided search mechanism to find where the cost estimation is weakest before you even start comparing different system designs.

Lu: That sounds like a really practical application for guiding system design rather than just analyzing a finished one.

Tom: So the implication is that we can use this structure not just for checking if a program works, but for actively improving it by guiding refinement based on where the cost estimation is weakest.

Jane: It's about making our analysis more interactive and less about running one big check at the end.

Lu: To wrap up, "The Best of Times, the Worst of Times: Moment-Based Analysis of Probabilistic Cost Structures" gives us a rigorous tool to compute moments for probabilistic programs involving max and min by using prefix–tail surrogates.

Tom: This whole work gives us a clear path forward for analyzing these kinds of systems in a scalable way.

Jane: It moves us away from just hoping a rough estimate is good enough to be useful because we have concrete intervals on the accuracy for systems like quantum repeater waiting times.

Meng: I think what’s most valuable is that they give us explicit error bounds on both the shape and the moments, so we know exactly how much confidence we can place in our cost predictions.

Wrap-up: Lu: It’s a framework that lets us see how those nonlinear operations contract into moment-based analysis by summarizing each subproblem with that prefix–tail surrogate distribution.

Tom: So if you’re working on something where costs are combining in a nonlinear way and you need to predict the average performance of that system, this paper gives you a systematic way to compute those moments reliably.

Jane: And for those interested in how it works practically, the authors show how to use geometric prefix–tail summaries for expectation queries while keeping track of moment-indexed error bounds when you need higher orders.

Lu: It proves that retaining distributional shape information allows for sound propagation of error bounds on both the shape and the moment estimates through hierarchical composition.

Tom: This is important because it means we can move beyond simple additive cost analyses when dealing with real systems where costs interact nonlinearly, like in contention resolution protocols.

Meng: It’s a solid framework, but I still see the challenge of making sure that abstracting doesn't introduce too much shape error before we hit those moments.

Jane: Exactly. And for those who want to see how this works practically, they show how to use moment-indexed error bounds when you need to estimate things like the third or fourth moments if you set up the summaries correctly.

Tom: So the paper is showing that you don't have to choose between perfect accuracy and tractability when dealing with these complex cost structures.

Jane: It’s about being smart about what information you keep at each step of the analysis process.

Lu: The final point is that this method provides abstract semantics that propagate both distributional error and moment error, which allows for local precision refinement or exact subtree promotion when it seems beneficial for tightness.

Meng: So it's a system that can automatically suggest improvements based on where the cost structure is most uncertain.

Tom: And by using this method, we get concrete error bounds on the moments we care about for systems like quantum repeater waiting times.

CHENYU ZHOU, DI WANG, THOMAS REPS

University of Southern California · Peking University · University of Wisconsin-Madison

cs.PL

Submitted: 2026-07-28

Updated: 2026-11-17

Comments: 52 pages

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

Importance score: 100/100

The gist: This paper presents a compositional cost analysis framework designed to compute moments (mean, variance…

Key concepts

Prefix–Tail Surrogate Distribution
This summary captures the distribution of a cost by keeping an exact short part (prefix) and a compact parametric description (tail) of the rest. This is used to summarize subproblems, allowing error bounds to be propagated accurately through the hierarchical cost structure.
Distributional Shape Error ($\epsilon$)
This error measures how much the summary's shape deviates from the true distribution's shape. The framework tracks this separately from moment error, showing that abstraction preserves shape information but introduces this specific type of error.
Query Expectation Bound ($\delta$)
This bound specifically tracks the accuracy of estimating a required expectation (like the mean). The analysis shows that while abstraction introduces distributional shape error, nonlinear composition translates this into moment estimation errors bounded by $\delta$.

Terminology

Summary

This paper presents a compositional cost analysis framework designed to compute moments (mean, variance, and higher orders) of costs arising from probabilistic programs where local costs combine not only additively but also through extremal operations like and. p. 0

Where the paper says it

The Best of Times, the Worst of Times: Moment-Based Analysis of Probabilistic Cost Structures CHENYU ZHOU, University of Southern California, USA DI WANG, Peking University, China THOMAS REPS, University of Wisconsin-Madison, USA This paper studies how to compute the moments—mean, variance, and beyond—of the cost (e. , running time) of certain probabilistic programs, in which local costs combine not only additively but also via the extremal operations max and min.

Such costs are common in areas like contention-resolution protocols or quantum repeater waiting times. p. 0
Where the paper says it

, running time) of certain probabilistic programs, in which local costs combine not only additively but also via the extremal operations max and min. Such costs arise naturally—for instance, the number of rounds of a contention-resolution protocol, the waiting time of a quantum repeater, and the completion time of a fork-join computation—but fall outside the scope of moment-based analyses developed for additive costs.

The primary challenge addressed is that the nonlinear nature of and prevents simple moment propagation, as the moments of a maximum or minimum are not determined by the moments of its arguments alone. p. 0
Where the paper says it

Such costs arise naturally—for instance, the number of rounds of a contention-resolution protocol, the waiting time of a quantum repeater, and the completion time of a fork-join computation—but fall outside the scope of moment-based analyses developed for additive costs. The difficulty is that max and min are nonlinear: the moments of max(𝑋, 𝑌) are not determined by those of 𝑋 and 𝑌, so propagating moments alone fails.

The core methodology involves a bottom-up, compositional analysis over a hierarchical cost expression. p. 0

Where the paper says it

We present a compositional cost analysis for a family of probabilistic programs whose cost structure can be represented as a hierarchical cost expression. The analysis proceeds bottom-up through the hierarchical structure, solving local recurrence equations at each node and summarizing each subproblem with a surrogate distribution.

At each node in this structure, the analysis summarizes the subproblem using a prefix–tail surrogate distribution. This surrogate consists of an exact short-time prefix and a compact parametric tail capturing the remaining probability mass. This summary is crucial because retaining distributional shape information allows for sound propagation of error bounds on both distributional shape and moment estimates. p. 0
Where the paper says it

Each surrogate consists of an exact short-time prefix and a compact parametric tail. The analysis tracks two kinds of error bounds—one on distributional shape, one on the moment estimates—yielding sound bounds on the first, second, and higher moments.

The framework formally defines the problem of computing such surrogates, aiming to find a compact summary gamma(s kappa) and an estimated expectation bE(s kappa), subject to error bounds epsilon kappa (for distributional shape) and delta kappa (for the query expectation). p. 2

Where the paper says it

2 We formulate the problem of computing surrogate distributions and equipping them with error guarantees. Given a cost expression 𝑒, a target query 𝑄—here we will use expectation—and a precision parameter 𝜅, the goal is to compute a compact summary 𝑠𝜅, a surrogate distribution 𝛾 (𝑠𝜅), and an estimated expectation bE(𝑠𝜅), with error bounds 𝜖𝜅 and 𝛿𝜅 such that 𝑑 (J𝑒K,𝛾 (𝑠𝜅)) ≤ 𝜖𝜅 and |E(J𝑒K) − bE(𝑠𝜅)| ≤ 𝛿𝜅, where 𝑑 is a distance on cost distributions.

A key insight is that abstraction introduces distributional shape error but preserves moment information, while nonlinear composition converts this shape error into moment error. p. 9
Where the paper says it

00227 translates into the nonzero 𝛿𝑟 . In short: abstraction introduces shape error but no moment error; nonlinear composition converts shape error into moment error.

The analysis tracks two distinct types of errors: a distributional bound (epsilon) and a query-specific expectation bound (delta). p. 9

Where the paper says it

At the root, the nonzero query error comes from the fact that the root takes a maximum of the two approximate child distributions; child shape errors can affect the expected maximum. This separation is the main insight behind our method: a single distributional bound would be sound but too conservative as an expectation estimate, while a pure expectation bound would be too weak to propagate through future maxima.

The separation between these bounds is vital: abstraction yields shape error without moment error, but nonlinear composition translates that shape error into moment estimation errors. p. 9
Where the paper says it

00227 translates into the nonzero 𝛿𝑟 . In short: abstraction introduces shape error but no moment error; nonlinear composition converts shape error into moment error.

The framework is built around primitives (a kernel) and application-specific components (plugins). For expectation queries, the main body utilizes a geometric prefix–tail summary. p. 2

Where the paper says it

In our instantiation for expectation queries, we use a geometric tail, which provides closed-form probabilities and expectations, and supports efficient composition and error propagation. Figure 1 illustrates the two-part approximation: in each subplot, the blue curve represents the ground-truth cost distribution, and the red/purple dashed curve represents the surrogate: the part on the left of the dotted vertical line is the precise prefix and the part on the right is the approximate tail.

Higher-moment queries require moment-indexed error bounds. p. 2
Where the paper says it

Figure 1 illustrates the two-part approximation: in each subplot, the blue curve represents the ground-truth cost distribution, and the red/purple dashed curve represents the surrogate: the part on the left of the dotted vertical line is the precise prefix and the part on the right is the approximate tail. The approach is not tied to this particular choice: richer tails, such as mixtures of geometric components or phase-type distributions, can be incorporated when suitable abstractions and error bounds are available for higher-moment queries.

The analysis demonstrates that retaining distributional shape yields more accurate estimates than scalar or hand-designed approximations while preserving sound intervals. p. 3
Where the paper says it

The quantities of interest include response-time distributions and deadline-miss probabilities, both of which depend critically on the distributional structure that would be lost when scalar summaries are used. Our work makes the following contributions: • We formulate the problem of cost-distribution summarization for (recursive) stochastic cost programs: compute (i) a compact surrogate distribution while (ii) tracking two kinds of error bounds—one on distributional shape, one on the moment estimates—yielding sound bounds on the first, second, and higher moments.

The paper introduces several contributions:

  1. Cost-Distribution Summarization: Formulating the problem of computing compact surrogate distributions while tracking both distributional shape and moment error bounds, allowing for sound bounds on first, second, and higher moments through compositional propagation over the hierarchical structure.

  2. Prefix–Tail Abstraction: Introducing a mechanism that stores an exact prefix and a compact representation of the remaining mass, preserving queried moments (and lower moments) of the abstracted distribution.

  3. Abstract Semantics with Error Bounds: Providing an abstract semantics that propagates bounds on both distributional error and moment error, supporting local precision refinement and exact-subproblem promotion as sound trade-offs between analysis cost and bound tightness.

The framework is versatile, handling probabilistic programs with addition, choice, repetition, and extremal operators (,). p. 1

Where the paper says it

Sequential execution composes by addition (𝑋 +𝑌), but synchronization constructs such as barriers involve maximum (the completion time is max(𝑋, 𝑌)), while races and redundancy involve minimum (the first successful result arrives at time min(𝑋, 𝑌)). Probabilistic control flow introduces mixtures, and repetition introduces random sums.

The operator contracts are classified: same-index operators act pointwise on survival functions; convolutional operators (+ and random repetition) combine inputs across time indices. For j at least 2, these convolutional operators become cross-moment operators. p. 2
Where the paper says it

A small generative specification can expand into a large stochastic state space, and exact distribution-based methods may become infeasible even when the high-level problem structure is highly regular. Scalar summaries have the opposite problem: they scale, but for some operators, such as max and min, it is not possible to compute the correct scalar summary from scalar-valued child summaries (as illustrated above).

Specific moment relations for sums (like M 2(X+Y)) and repetitions (like M 2(Repeat N(X))) are derived, which are essential for higher-order moment tracking. p. 3
Where the paper says it

The quantities of interest include response-time distributions and deadline-miss probabilities, both of which depend critically on the distributional structure that would be lost when scalar summaries are used. Our work makes the following contributions: • We formulate the problem of cost-distribution summarization for (recursive) stochastic cost programs: compute (i) a compact surrogate distribution while (ii) tracking two kinds of error bounds—one on distributional shape, one on the moment estimates—yielding sound bounds on the first, second, and higher moments.

The analysis is sound under the independence assumption. p. 0

Where the paper says it

Each surrogate consists of an exact short-time prefix and a compact parametric tail. The analysis tracks two kinds of error bounds—one on distributional shape, one on the moment estimates—yielding sound bounds on the first, second, and higher moments.

Evaluation on problems such as quantum repeater waiting times, RFID collision resolution, and fork–join computations confirms that retaining distributional shape provides superior accuracy compared to simpler approximations, with specific findings regarding the impact of prefix depth (H), greedy refinement strategies (CEGAR), and moment-directed abstraction (M2-directed) on error reduction. p. 0
Where the paper says it

In addition, precision can be increased by refining the surrogate representation, trading additional computation for tighter bounds. We implemented our method in a tool, called Dickens, and evaluated its capabilities on three problems: quantum repeater waiting times, RFID collision resolution, and completion times of fork–join computations.

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. Automated analysis of probabilistic programs with additive, extremal, mixture, and repetition costs can be performed by composing cost-expression trees using a tree interpreter to compute distribution-valued approximations for costs like mean and variance.

  2. The system can compute an error bounded summary s k for a cost expression e, where the summary consists of an exact short-time prefix and a compact parametric tail, tracking two kinds of error bounds: one on distributional shape and one on moment estimates.

  3. For expectation queries, the analysis preserves the queried moment by choosing a geometric tail parameter lambda so that the abstraction preserves expectation, while tracking distributional error separately to capture shape changes.

  4. The framework can analyze higher raw moments up to order k by using moment-parametric prefix-tail summaries, where the tail family is matched to the target order or local moment-bias bounds are reported when a simpler tail is used.

  5. The system supports refinement through two methods: increasing the prefix depth H to improve local abstraction errors or exact subtree promotion for small subproblems to replace them with an oracle leaf, trading analysis cost for tighter bounds.

  6. An analysis-guided search mechanism can be used to improve repeater tree schemes by identifying which local losses would need additional refinement before design comparison can be analyzed, and it can also find a repeater tree whose error bounded interval witnesses improvement over initial schemes.

Abstract

Many practical costs---such as the completion time of a quantum repeater, the rounds of an RFID collision-resolution protocol, or the response time of a fork--join computation---are described by hierarchical cost expressions: a tree of independent subcomputations with nonnegative integer costs, combined by addition, max, and min. We compute their moments with sound error bounds. Moment-based analyses for additive costs do not apply, because the moments of (X,Y) are not determined by those of X and Y; propagating full distributions becomes expensive as trees grow; and scalable approximations are hand-derived for specific structures and lack error bounds. Our analysis proceeds bottom-up, summarizing each subtree by a surrogate distribution: an exact short-horizon prefix plus a compact parametric tail fitted to preserve the queried moment. Each prefix is computed exactly from the children's prefixes---for a retry, whose cost sums an unbounded number of attempts, by solving a local recurrence equation---so all approximation is confined to the tails. Abstraction introduces shape error but no moment error; nonlinear operators, such as max and min, convert shape error into moment error. The analysis tracks two bounds, one on shape error and one on moment error. Tracking both lets it report a sound interval for the mean, the second moment, and the variance. Lengthening the prefix, or solving subtrees exactly, narrows the interval at the cost of additional computation. For quantum-repeater chains of up to 4096 links with high swap-success probability, our Dickens tool bounds the mean completion time within 1%, whereas the exact Markov-chain solution exhausts memory with 16 links, and the best hand-derived approximation we evaluated has 47% error with 64 links. Dickens also bounds second moments, variances, and deadline-miss probabilities, and handles RFID and fork--join costs.

Sources

Related papers