Exact Ranking Verification Under Shared Min–Max Normalization

Guaranteeing the stability of learned rankings is challenging when uncertain input features are jointly normalized: changing one candidate’s input can alter every candidate’s score. Under shared min–max normalization, independently attainable score extremes may be jointly infeasible, making independent bounds insufficient to determine ranking stability. We develop an exact verification framework for piecewise-constant scorers, including tree ensembles, with one uncertain feature per candidate, fixed remaining inputs, and uncertainty specified by pairwise difference constraints. Our central idea is to characterize which pairs of normalized feature values can occur jointly. We prove that this two-dimensional feasible set has boundary complexity linear in the number of candidates, together with a matching worst-case lower bound. This geometric structure enables a complete top-k verifier that either certifies an unchanged selected set or constructs a feasible counterexample, without enumerating all combinations of score-profile regions. Experiments on controlled workloads demonstrate the computational benefits of the geometric construction. Studies on NFCorpus and SciFact show that modeling shared-query dependencies enables ranking guarantees that are unavailable under independent uncertainty, with most certificates obtained through sufficient shared checks.