Some software failures happen once in a billion runs, for example a counter that overflows only after an unlucky streak of random increments, or a controller whose drift crosses a safety threshold only under rare noise. Running the program many times and counting failures (plain Monte Carlo) cannot measure such probabilities, and symbolic execution cannot either, because every branch inside a loop doubles the number of paths. A standard workaround is multilevel splitting. It clones simulation runs that make progress toward the failure and kills those that do not, so the tiny probability becomes a product of moderate ones. Splitting needs an importance function, a score saying how close a program state is to failing, and for real programs nobody knows how to write one automatically. This note proposes to compute that score from algebraic loop analysis. Tools such as Polar already derive exact closed-form formulas for the moments of program variables after $n$ loop iterations. We evaluate those formulas from the current state of a running simulation to get a cheap analytic estimate of how likely that state is to reach the failure in the iterations that remain. That estimate is the splitting score.
The design has one useful property. Splitting stays unbiased whatever score it uses, and a bad score only increases variance. Moment-based tail estimates are known to be unreliable far out in the tail, and that weakness is the main reason nobody uses them as final answers. Here it does not matter, because the moments only need to rank states, and the simulation produces the number. The proposal also tests, with a pre-stated condition for dropping it, whether a hyperbolic embedding of the branch-decision tree helps the score handle control flow that loop moments cannot see.
Core Claim
For a probabilistic loop with state $x$ at iteration $n$, horizon $T$, and rare event "variable $X$ exceeds threshold $t$ by time $T$," define the score
$$s(x,n) = -\log \min_{1\le k\le K} \frac{\mathbb{E}[X_T^k \mid X_n = x]}{t^k},$$
where $\mathbb{E}[X_T^k \mid X_n = x]$ is the $k$-th moment of $X$ at the horizon, given the state at iteration $n$. It comes from the closed form computed once, symbolically in the initial state and in the remaining iteration count $T-n$. $K$ is a small maximum moment order. The inner quantity is Markov's inequality applied to each moment, minimized over order, so $s$ is a rough upper-bound proxy for $-\log \mathbb{P}(\text{reach} \mid x, n)$ (for $X$ that can be negative, even $k$ or $|X|$ moments are used). Our claim is that using $s$ as the splitting importance function gives lower work-normalized relative variance than the natural score (the raw value of $X$), than control-flow distance, and than cross-entropy importance sampling. We expect the gain to be largest exactly where those alternatives fail. That includes events that depend jointly on time remaining and on drift, events over coupled variables, and probabilities from $10^{-6}$ to $10^{-12}$, where cross-entropy cannot start because no initial run hits the event.
Two things make this different from prior work. First, the score does not need to be sound. Polar restricts loop guards to finitely-valued variables with constant branch probabilities, because general inequality guards run into the open Skolem and Positivity problems. We can drop such guards, or replace them with their horizon-bounded relaxation, when computing $s$, since an imprecise score only costs variance. Second, the score is evaluated at every split point without unrolling the loop. The simulation therefore never enumerates paths, which avoids path explosion.
Relation to Prior Work
The method comes from algebraic loop analysis. Polar extracts recurrences over expected values and solves them into exponential-polynomial closed forms in $n$ and symbolic parameters. We reuse it unchanged as the moment oracle, and add what it lacks: any connection to tail probabilities. The work on (Un)Solvable loop analysis and on C-finite recurrences under nested nondeterministic branches widens the loops that admit such closed forms. When an individual variable is unsolvable, we take moments of the solvable polynomial combinations those methods synthesize. The closest prior work linking loop moments to probabilities is Moment-based Density Elicitation with Applications in Probabilistic Loops, which rebuilds whole densities from closed-form moments using orthogonal polynomial ($K$-series) expansions. It guarantees $L_1$/$L_2$ convergence but does not evaluate tails below $10^{-6}$, where polynomial expansions oscillate. We use moments for ranking rather than reconstruction, and treat $K$-series as a competitor plug-in estimator.
On the rare-event side, two papers supply the problem and the baselines. Feedback Control for Statistical Model Checking of Cyber-Physical Systems runs importance splitting on a hidden Markov model learned from traces, so it ignores program code. We keep splitting but take the score from the code's own recurrences. Cross-entropy optimisation of importance sampling parameters tilts the probabilities of guarded commands, which keeps the search low-dimensional, and estimates probabilities down to $10^{-28}$. It needs initial runs that hit the event, and we target that cold-start regime.
On the path side, Probabilistic symbolic execution computes path probabilities as volumes of path-condition polytopes. That is #P-hard and still unrolls loops. Under-Approximating Loops in C Programs jumps to deep loop states with closed-form auxiliary paths but computes no probabilities. We borrow its acceleration idea only as an ablation baseline: seed cross-entropy with one deterministically accelerated failing trace. The survey Symbolic execution for software testing: three decades later documents why loops with internal branches defeat bounded unrolling, which is why exact path enumeration is not a baseline here.
The hyperbolic component is a constraint and a hypothesis, not the core. Poincaré Embeddings shows that trees embed with low distortion in low-dimensional hyperbolic space, where the distance from the origin encodes depth. We deliberately do not use distance from the root as the splitting score, which is the idea suggested by the research file. In an execution tree that distance is essentially depth, and depth says nothing about closeness to failure.
Research Program
We will build a splitting engine for probabilistic loop programs in the Polar input language and in PRISM guarded-command models. For each benchmark, Polar is run once with the initial state left symbolic, giving closed forms for $\mathbb{E}[X_T^k]$ as functions of the start state and of $T-n$. These are compiled into fast numeric functions. During adaptive multilevel splitting, the levels are set as quantiles of $s$ over the current particle population. Each particle's score is a polynomial evaluation, so the cost per split is small and independent of $T$.
Three technical questions need answers. The first is how to choose $K$ and whether to mix Markov-type and Cantelli-type bounds. Higher orders sharpen the bound but grow numerically. The second is how to handle guards. We will compare three ways of computing the score: dropping the guard, freezing it at its current value, and enumerating the guard's finitely many values weighted by their current probabilities. The third is how to handle events defined by several variables. Here we compute the score on a polynomial combination, for instance a linear functional suggested by the event's defining inequality, and test whether invariant-derived combinations from the unsolvable-loop work give better scores than raw variables.
For programs whose loop is preceded or interleaved by data-dependent branching that Polar cannot summarize, the moment score is blind to which branch region a run is in. The secondary arm targets this case. Particles' sequences of branch decisions form an online prefix tree. We embed this tree in the Lorentz model of hyperbolic space, which avoids the instability near the Poincaré boundary noted in the literature. The discrete score is the negative hyperbolic distance from a particle's prefix to the nearest prefix that has previously gone furthest toward failure, and it is added to $s$. Because this must be learned from data, it is used only in later splitting rounds, and the rounds that set levels are kept separate from the rounds that estimate the probability, so the estimate stays unbiased.
Baselines
The naive reference is plain Monte Carlo at equal simulation budget. On the Incrementer-or-Resetter benchmark, Feedback Control for SMC reports that it gives "a zero estimator." We expect the same at every probability below $10^{-6}$. A second simple reference is splitting with the natural score, the event variable's own value, with the same adaptive levels and particle count as ours. This is the baseline most likely to compete on single-variable random walks, and isolating it is essential.
The strongest existing methods are two. The first is the FC-SSC splitting pipeline. On Incrementer-or-Resetter it reports a mean estimate of $1.204 \times 10^{-4}$ with variance $5.599 \times 10^{-8}$ against a target near $2.44 \times 10^{-4}$, a roughly twofold underestimate. Beating it means matching its budget and being closer to the target with lower variance. The second is guarded-command cross-entropy importance sampling. It reports about $10^7$ variance reduction on the $\approx 10^{15}$-state chemical reaction network at probabilities near $10^{-28}$, and estimates within 1.7% of PRISM's exact value on the repair model. We run it on the same PRISM models with its own tuning protocol and the same total simulation count, including the iterations it spends on cross-entropy updates. Beating it means lower work-normalized relative variance at equal or better accuracy against PRISM ground truth. Where it simply cannot start, we report that as a failure rather than tuning around it. On the chemical network itself we expect at best parity, because importance sampling is well matched to that model, and we state that in advance.
A non-simulation competitor is the $K$-series density from the same Polar moments, integrated over the tail. No reported result found on Lacuna for $K$-series accuracy at tail probabilities below $10^{-6}$, so we measure it ourselves. The ablations isolate the key ingredient. One replaces $s$ with the same Markov bound computed at fixed $n$ without conditioning on the current state. Another seeds cross-entropy with a single failing trace found by Kroening-style deterministic acceleration. For the hyperbolic arm, the comparisons are control-flow-graph shortest distance to the failure location, a Euclidean embedding of the same prefix tree at matched and at 40× dimension, and no discrete term at all. Every method gets the same simulation budget, wall-clock limit, and number of tuning runs.
Why not just…?
Why not just split on the event variable itself? For a one-dimensional random walk with constant drift, the raw value of $X$ is close to the ideal importance function, and our score may add nothing. This is a real threat. Our score should win when the remaining horizon matters, because a state at a high value with no time left is worthless, and when drift reverses, as in mean-reverting Vasicek or Taylor-rule dynamics. It should also win on coupled variables such as the robot and turning-vehicle models. The head-to-head comparison at matched budget settles this. If the natural score ties everywhere, the claim fails.
Why not just read the tail off the moments and skip simulation? $K$-series and Gram-Charlier expansions match low-order moments but oscillate in the extreme tail, and Markov-type bounds can be loose by orders of magnitude. Neither gives an unbiased estimate or a confidence interval. We report both plug-ins against ground truth to show the gap. The interesting outcome would be if the moment bound alone were within a small constant factor of the truth, because that would make simulation optional on easy benchmarks.
Why not use hyperbolic distance from the tree root as the reaction coordinate? That distance tracks depth in the execution tree, and depth is available without any embedding and does not track proximity to failure. This is why we demoted hyperbolic geometry to a secondary, target-relative term with its own Euclidean and control-flow-distance controls. If it does not beat control-flow distance on the branching benchmarks, we drop it.
Why not adaptive stress testing or reinforcement learning? These methods, such as ScenePilot and Coverage Aware Active Evaluation, find failures but do not track likelihood ratios, so they give no unbiased probability. We include such a search only as a failure-finding comparison and report its time to first hit.
Proposed Experiments
The benchmarks are the probabilistic loops from the density-elicitation and Polar evaluations: 1D and 2D random walks, Vasicek, Taylor rule, turning vehicle, differential-drive robot, 2D robotic arm, and rimless wheel. For each we set thresholds so the target probability spans $10^{-4}$ to $10^{-12}$. We add Incrementer-or-Resetter and dining philosophers from the FC-SSC paper, and the chemical reaction network and repair model from the cross-entropy paper.
Ground truth comes from closed-form Gaussian probabilities for the Gaussian walks, PRISM numerical solution for the repair model and for Incrementer-or-Resetter where its state space allows, and $10^{10}$-run Monte Carlo for the moderate thresholds. Metrics are relative error against ground truth, empirical coefficient of variation over 100 independent repetitions, and work-normalized relative variance (variance times cost divided by $p^2$). We also report hit rate and the fraction of runs that never start. For the hyperbolic arm, we use variants of these loops prefixed by synthetic branch trees with 10 to 30 data-dependent decisions.
The decisive check is the scaling plot of work-normalized relative variance against $p$. If our score keeps that quantity roughly flat from $10^{-4}$ to $10^{-12}$, while natural-score splitting and cross-entropy grow polynomially or fail, the claim holds. If the curves coincide, loop moments add nothing and the claim fails. A second check is whether the guard-dropping relaxation costs variance on guarded loops relative to exact guard enumeration. A third is the pre-registered rule for the hyperbolic arm, which is kept only if it beats control-flow distance by a clear margin over the 100 repetitions.
References
- Polar: An Algebraic Analyzer for (Probabilistic) Loops
- (Un)Solvable loop analysis
- On Polynomial Expressions with C-Finite Recurrences in Loops with Nested Nondeterministic Branches
- Moment-based Density Elicitation with Applications in Probabilistic Loops
- Feedback Control for Statistical Model Checking of Cyber-Physical Systems
- Cross-Entropy Optimisation of Importance Sampling Parameters for Statistical Model Checking
- Probabilistic symbolic execution
- Under-Approximating Loops in C Programs for Fast Counterexample Detection
- Symbolic execution for software testing: three decades later
- Poincaré Embeddings for Learning Hierarchical Representations
- ScenePilot: Controllable Boundary-Driven Critical Scenario Generation for Autonomous Driving
- Coverage Aware Active Evaluation for Failure Discovery with Paired Systems