CS Paper Radar

Per-State Signatures and Mean Time-to-Failure: An Algorithm for Systems With Simultaneous Failures

Guido Lagos, Simón Ávila

cs.DS math.OCmath.PR ·submitted 2026-10-15 16:35 UTC · v1
benchmark

Abstract

We present an algorithm that computes the structural signature and the mean time-to-failure (MTTF) of a monotone binary system at every one of its states, rather than only at the state in which all components work. It makes no assumption on the structure function and evaluates it exactly once per state, as many times as needed for the signature of the complete system alone, so computing the MTTF everywhere costs only a factor polynomial in the number of components over computing it once. As a by-product, it identifies all minimal path sets. We assume exchangeable component failure times whose survivor count is a continuous-time Markov chain. This setting admits simultaneous failures, as in the Lévy-frailty Marshall-Olkin, binomial failure rate and lethal-shock models, where the simplifications available for single failures do not apply. We use the per-state MTTF to define threshold repair policies. We show that the per-state signature is a strictly finer decision criterion than the MTTF: signature dominance at a common failure count implies MTTF dominance, but not conversely. Under the Lévy-frailty Marshall-Olkin model the MTTF is monotone in the state, which yields the long-run cost rate of every threshold policy in a single pass. Experiments on 22 benchmark networks with up to 30 components and 31 failure models show that the best MTTF-threshold policy has a median excess cost of 0.36% over the optimal state-based policy, and that it is never worse than the best policy that repairs after a fixed number of failures.

Comment
The manuscript has been submitted to IEEE Transactions on Reliability

Closest papers

Nearest neighbours by meaning across the whole index.

Distinguish or Homogenize: Last-Chance Policy Identification and Risk-Budgeted Recovery under Irreversible Resource Depletion

cs.AI ·2026-09-29 ·Yibo Guo, Xiaodan Wang
similarity 0.61
Abstract

Under irreversible resource depletion, an agent can spend resources to distinguish among latent fault models, or to change the system state so that the remaining models admit a common acceptable continuation--at which point further diagnosis becomes unnecessary. This distinguish-or-homogenize principle identifies a path that existing frameworks for identification, planning, and diagnosis do not make explicit: prior formulations treat the mapping from fault models to acceptable policies as a given, whereas LCPI makes it a function of the agent's own actions. We formalize this principle through Last-Chance Policy Identification (LCPI), where correctness is evaluated at the state the agent reaches rather than at the initial state. The Last Identifiable Margin (LIM) marks the feasibility boundary between distinguishing and homogenizing. For deterministic diagnostic graphs we provide the Exact-LIM recursion; for noisy finite-horizon recovery we propose Risk-Budgeted Compatibility Planning (RBCP), which searches a compatibility-aware frontier under a hard worst-case failure constraint. Across incident recovery on abstract microservice topologies and latent-damage navigation in MiniGrid, RBCP improves risk-feasible recovery while satisfying the failure budget. A sham control--cost-matched actions that preserve model incompatibility--eliminates the gain entirely, confirming that the benefit comes from changing which policies are acceptable for which models, not from extra search or additional budget.

0.23

Convex-Analytic View of Query Selection for Safety Verification of Markov Decision Processes

cs.AI math.OCcs.LO ·2026-10-13 ·Han Bao, Shinsaku Sakaue, Kazuki Watanabe
similarity 0.57
Abstract

Safety verification of a Markov decision process (MDP) asks whether the probabilities of reaching several failure states jointly lie in a convex safe region under every scheduler. Watanabe and Unno (2026) prove safety by refining an outer approximation of the failure probabilities, where each query bounds a nonnegative weighted sum of the probabilities. Their rule selects weights by the largest Euclidean violation. We present a unified framework to measure violation in an explicitly chosen error unit: directions are scored by the support-function gap between the outer approximation and the safe region, normalized by the support function of the unit. We show that the maximal score, when positive, equals the smallest enlargement of the safe region in multiples of that unit that contains the outer approximation. The Euclidean unit recovers the earlier rule; two new rules are generated by the unit cube and the safe region itself. We experimentally evaluate how the choice of measurement rule affects the performance of safety verification for MDPs.

0.22

Same Winners, Different Success Rates: Evaluating How LLM Agents Recover from Failures

cs.AI cs.LGcs.MA ·2026-09-28 ·Dong Xu, Zhangfan Yang, Jiantao Wu, Shipeng Zhang, Zexuan Zhu +3 more
similarity 0.57
Abstract · 44 pages, 2 figures

Evaluating how LLM agents recover from mid-task failures is central to deploying reliable agentic systems. Existing checkpoint-based benchmarks measure recovery by comparing which action is selected as best across independent runs, a quantity known as set agreement. However, set agreement is a purely ordinal measure that records which action wins without reflecting the absolute level of performance. When all actions fail, they tie at zero reward, and independent runs produce the same tied set with high probability, creating an illusion of stability that masks near-zero recovery success. We formalize this limitation through a set-path symmetry result, proving that for equal-cost Bernoulli actions the success probabilities (0.9, 0.8) and (0.2, 0.1) yield identical best-action-set distributions at every sample size. No procedure based solely on which action wins can distinguish these two regimes. We further prove that certifying exact population ties is impossible in finite time, and that the assignment of outcomes to checkpoints carries information beyond marginal outcome distributions. The pooled success probability is the missing scalar that resolves the ordinal ambiguity. Experiments on 864 frozen RecoveryBench episodes and two planning cohorts totaling 3,456 responses confirm the theoretical predictions. Agreement and held-out quality can move in opposite directions, and permuting checkpoint-to-action bindings changes 8 to 13 percent of cell-level conclusions. Based on these findings, we propose reporting four diagnostic quantities (agreement, all-zero fraction, held-out success, and pooled success) that expose this failure mode with no additional data collection.

0.25

Harmonic-Mean Aggregation of Continuous-Time Markov Chains with Reachability Error Bounds

cs.LO ·2026-11-16 ·Bingqing Hu, Landon Taylor, Zhen Zhang
similarity 0.55
Abstract

Abstracting a continuous-time Markov chain by grouping its states into blocks raises a fundamental question: which rates should the abstract chain use when states within a block have different exit rates and transition probabilities? We study harmonic-mean aggregation, which matches the mean waiting time and next-block distribution of a local experiment that uniformly selects a state within the block and observes its next jump. Equivalently, the abstract transition rates are averages of the concrete rates with inverse-exit-rate weights. Since the aggregation does not preserve reachability probabilities in general, we derive theoretical error bounds for time-bounded reachability. We decompose the error into a blockwise mean and centered-within-block deviations, and show that the rate mismatch has zero weighted mean. Exploiting this cancellation and differences between abstract reachability values, we obtain bounds valid at every time horizon through a linear comparison system with two quantities per block, without computing concrete reachability values. All results are formalized and proven in Lean 4.

0.35

When AI Agents Should Repair, Replan, or Abandon: A Threshold Theory of Plan Commitment

cs.AI ·2026-11-14 ·Gaurav Tewari
benchmark similarity 0.55
Abstract · 22 pages, 6 figures, 3 tables

AI agents often discover mid-execution that their plan is broken, for example when an action fails or a tool is withdrawn. Deployed systems use conventions such as retry loops or "always replan," and a recent benchmark finds no fixed strategy dominates. This paper derives the optimal policy. In the model, a disruption destroys the causal support of part of a plan; repair is a partial reset that preserves the plan's structure, replanning is a full reset, and changing a plan is costly because others have conditioned on it. The optimal policy is a threshold in effective disruption depth: repair shallow damage, replan after deep damage, and abandon the goal when even a fresh plan is not worth its cost. Depth depends on plan structure. In expectation, a single broken action forces 1+R(G)/n actions to be revalidated, where R(G) counts the pairs of actions joined by a dependency path; to first order, a fully serial plan switches to replanning at raw damage about w times smaller than a plan of w parallel chains. A closed-form stability-price threshold determines when a worse repaired plan should be kept over a better fresh one. As language-model planners push replanning costs toward zero, the stability price becomes the only force sustaining plan commitment. Under repeated disruptions, revision frictions make commitment hysteresis optimal: the agent keeps executing a plan it would never choose fresh, and each repair adds patch debt until the debt outweighs repair's cost advantage and the agent rebuilds. A value-of-diagnosis result states when measuring damage is worth its compute and shows that "always replan" is optimal when damage is predictably deep and replanning is the better fallback. A separately implemented numerical checker tests each proposition (zero violations; 1.6 million static-model evaluations), and the model's regime map reproduces that benchmark's regime flips qualitatively.

0.14

TTL Approximations for a Family of CLOCK-Like Cache Replacement Policies

cs.OS cs.PF ·2026-11-18 ·Yirong Wang, Peter Desnoyers, Benny Van Houdt
top venue similarity 0.54
Abstract · Accepted and presented at IFIP Performance 2026. To appear in ACM SIGMETRICS Performance Evaluation Review

While CLOCK-like cache replacement policies are highly appealing in practice due to their frugal memory usage and implementation simplicity, analytical models for their performance remain limited. The difficulty stems from the "eviction hand" itself. As it scans sequentially for an evictee, sparing objects with survival counters along the way, it inherently entangles the state of one cached object with the next. This strong coupling heavily obscures the system's steady state. To address this gap, we introduce a time-to-live (TTL) approximation for a family of eviction policies---which we term CLOCK($K$)---that decouples individual object dynamics using a globally fixed timer. In contrast to the intrinsic coupling induced by assuming a fixed cache capacity, such a TTL proxy yields a tractable matrix-analytic solution for the steady-state miss ratio functions across a broad and highly expressive class of phase-type renewal traffic. Among other benefits, this effectively reduces the analysis per-object to solving a linear system of order $O(Kd)$, where $d$ is the phase dimension. Moreover, our model for CLOCK($K$) recovers the canonical CLOCK when $K=1$ and FIFO when $K=0$, while empirically exhibiting Schur-concavity under the Independent Reference Model (IRM). Finally, we validate the model against a suite of trace-driven simulations.

0.36

Threshold Structure of Optimal Policies in Restart POMDPs

cs.LG math.OCmath.PR ·2026-08-11 ·Konstantin Avrachenkov, Alexey Piunovskiy, Yi Zhang
publishedtheory similarity 0.54
Abstract · 8 pages, the paper has been accepted to IEEE CDC 2026

We study a Restart POMDP (Partially Observable Markov Decision Process) on a general Borel state space, where the controller either lets the hidden state evolve unobserved or restarts the system and observes the new state. Exploiting a sufficient-statistic representation consisting of the last observed state and the elapsed time since restart, we reduce the problem to a fully observed MDP. Under a natural one-step cost deterioration condition, we prove that optimal policies have a threshold structure in the elapsed time for both the discounted and total undiscounted cost criteria. When the state space is partially ordered and the kernel is stochastically monotone, we further show that the optimal threshold is nonincreasing in the state. For the average cost criterion, under additional assumptions of geometric ergodicity and domination of the transient gain, we establish analogous threshold results via the vanishing discount approach, after showing the uniform boundedness of the optimal thresholds and relative value functions.

0.25

Quantitative coverability for probabilistic well-structured transition systems

cs.LO cs.FL ·2026-09-22 ·Raphaël Faure, Alain Finkel, Gaspard Fougea, Lina Ye
similarity 0.53
Abstract · 25 pages

Well-structured transition systems (WSTS) provide a classical framework for the verification of infinite-state systems, but their probabilistic extensions lack a unified treatment of quantitative coverability: path-enumeration algorithms assume a finite branching degree, while alternative approximation schemes defer some computations, such as probabilities over a bounded horizon, to the model at hand. We introduce probabilistic well-structured transition systems (pWSTS), Markov chains over countable state sets whose underlying transition systems are WSTS, with no a priori assumption on the branching degree. This class encompasses any WSTS equipped with a Markov kernel, such as probabilistic vector addition systems (pVAS) and probabilistic lossy channel systems (pLCS). For an effective subclass, we solve the approximate quantitative coverability problem over bounded horizons, and over infinite horizons under decisiveness, requiring no probabilistic information beyond individual transition probabilities. We then identify a general source of decisiveness: every stochastically monotone pWSTS is decisive with respect to every upward-closed set. We finally instantiate the framework on multi-type Galton--Watson processes, a classical model of population dynamics whose offspring distributions may have infinite support. Under mild assumptions on the reproduction laws, these processes are effective pWSTS, and they are stochastically monotone, hence decisive. Approximate quantitative coverability is therefore computable for them over both horizons, with a proof that uses none of the traditional tools: neither generating functions nor any case distinction between regimes.

0.40