Answer-Frontier Data Structures: Maintaining Nearest Alternative Answers Under Dynamic Updates

Abstract

Most data structures are designed around one operational question: what is the answer now? In a dynamic system, however, an equally important question is how close that answer is to changing, which alternative would appear first, and what smallest admissible intervention would realize the change. We introduce Answer-Frontier Data Structures (AFDS), an abstraction that augments a current query answer with a bounded frontier of alternative answers, minimum transition costs, and intervention witnesses. The abstraction exposes frontier-active, answer-silent updates, in which the reported answer is unchanged although nearby alternatives change. For weighted shortest paths under bounded edge-weight perturbations, we derive an exact nonnegative-weight pairwise transition radius, formulate the global alternative-optimality radius as a linear program, and prove a cached primal-dual certificate for exact radius reuse after weight updates. Experiments show that length order and intervention order can disagree and that pairwise sensitivity can underestimate global transition cost. Among 738 answer-silent updates, 68.70% changed the frontier. Cached certification eliminates 44.44% of exact LP solves in the principal scaling benchmark with zero frontier mismatches and a 1.50× aggregate speedup; exhaustive weighted-K₄ testing found zero incorrect accepted certificates across 7,196 update/target cases. These results establish the answer frontier as a distinct dynamic information object rather than another shortest-path algorithm.