A Taxonomy of Distance Metrics for Time-Sensitive Importance Splitting: Timer Bounds, Resampling, and the Global Age
2026-07-20 • Logic in Computer Science
Logic in Computer SciencePerformance
AI summaryⓘ
The authors study a method called importance splitting (ISPLIT) used to estimate rare event probabilities in systems where timing matters. They improve this method by reconsidering how timer values are handled during simulations, allowing the importance to be evaluated based on all possible timer states rather than just one sampled value. They also use the overall elapsed time to stop simulations that can't reach the target anymore. Their new approach clarifies the role of timing in estimating importance and shows better accuracy in experiments.
importance splittingnon-Markovian modelsimportance functiontimer resamplingrare eventssimulation pruningelapsed timedistance metricsprobability estimationtime-sensitive models
Authors
Gabriel Dengler, Carlos E. Budde, Laura Carnevali
Abstract
Importance splitting (ISPLIT) evaluates the probabilities of rare events in non-Markovian models. It requires a heuristic importance function (IFUN) that estimates the distance to the target. While including timer evaluations in the IFUN can substantially improve the effectiveness of ISPLIT, the existing time-sensitive IFUNs evaluate simulation states with respect to single sampled timer values. Thus, reaching highly important states requires simultaneously sampling specific combinations of timer values, yielding several unproductive simulation runs. In this paper, we revisit time-sensitive ISPLIT with the goal of steering simulation runs towards important states. First, we study how timer values can be resampled conditioned on the elapsed time. The importance can be evaluated by considering the set of feasible timer values, decoupling importance estimation from timer samples. Second, we exploit the global age of a simulation to identify and prune the executions that can no longer reach the target within the remaining time budget. Together, these ideas lead to a taxonomy of distance metrics clarifying the role of timer bounds, resampling, and the global age. In particular, for models with unbounded timers, we show that time-sensitive IFUNs collapse to ordinary IFUNs under resampling. Experiments demonstrate that the proposed formulations substantially improve the accuracy of ISPLIT estimators.