acceptodds
Under review as a conference paper at ICLR 2027

Exact Ranking Verification Under Shared Min–Max Normalization

Abstract

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.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
shared min-max normalization, certified ranking robustness, learning to rank, computational geometry

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_TnQ8OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

The paper studies the problem of determining if a learning-to-rank model's selected top-kk candidates is indeed stable. Here, the issue that can cause instability is that candidate feature values may be uncertain, and a change in values can cause the min/max values used to normalize all candidate values to be different - causing all candidate's normalized feature values to change, which can change the decision of the top-kk candidates. The paper studies the problem where there is a single feature rr which is uncertain. Given a matrix BB where the entry BijB_{ij} guarantees that ri−rj<Bijr_i - r_j < B_{ij} and a top-kk set of candidates SS, and for each candidate a mapping of normalized values (i.e. the range [0, 1]) to scores, the paper gives an algorithm which determines if the set SS is always a top-kk, or there exists a vector of feature values rr such that it meets the constraints imposed by BB, and selects a different set of top-kk candidates.

The paper also conducts experiments on synthetic and real-world datasets, and against baselines to study how efficient their algorithm is in being able to certify the top-kk candidate set is stable.

Critical strengths

The problem identified by the paper is quite interesting and seems to be one that can be easily overlooked, but cause significant issues in learning-to-rank (and maybe other similar type of classification systems). Normalization is commonly used in data science, and the potential for uncertainty in the feature values (e.g. quantization) leading to different top-kk ranked set is not something expected. This paper could bring awareness for this problem, and a tool to find out whether this possibility exists for a given model and data.

Critical weaknesses

A major issue is that the paper currently is extremely hard to read, and the presentation and discussion can be improved significantly, currently, it is difficult to gain a good understanding and intuition of most things in the paper despite my efforts. This could limit the impact and significance of the work for ML research/practitioners. Some issues in particular:

  • The introduction discusses some of the background behind studying this problem and motivating setup (normalization), but could be improved by discussing some real-impact (e.g. how much these models are used in practice), and maybe some brief introduction to why being able to verify the stability of a top-kk set matters, to give readers a better understanding.
  • max and min sometimes lack the subscript to indicate the domain the max/min function is operating over, especially in line 110,
  • Many times, notations are used without definition, such as dd at lines 109-110, and the notation (Bji)j(B_{ji})_j at lines 114-115, QijQ_{ij} at line 147, and so on, which makes it harder to understand the results.
  • In section 3, it could be clearer which bolded paragraphs aim to give a sketch of Theorem 2, and which of Theorem 3.
  • At line 303, the discussion transitions towards evaluating the value of the algorithm from Theorem 3, but it is very poorly signposted and little context or significance for each discussion is given for each of the paragraphs from here onwards.
  • In section 4, the baselines are not clearly mentioned anywhere (VERITAS, Z3) - it may be in the appendix, but it should be briefly described in the main text as well for readers.
  • In section 4, the datasets used are also not clearly mentioned; for example, how the synthetic datasets are constructed.
  • Throughout there are many strange wording/phrasings. Some examples: in Theorem 3, "Failure of invariance yields a full rational potential in P(B) selecting a different set." -- when this is simply that the algorithm will provide as output a vector of features that gives a S′≠SS' \neq S that has S′S' as top-kk set? There is also a lot of mention of a binary64 machine in section 3; while aligned with real-world computation, it is very odd to see it brought up in the theoretical discussion.
Questions for authors
  1. How well does the joint uncertainty model the real-world use of such data? Is it a practical assumption to make in general? For example, it seems to me that given feature values, a more natural assumption is that each value is individually noisy? Maybe I misunderstood something, so I would like some clarification.

  2. How can the results of this work be applied? For example, suppose that I use this method and find that my learnt top-kk set is unstable - there can exist a raw feature vector that can lead to a different top-kk set being selected by the learning model. How should I interpret/use this result?

7 comments

Thank you for your valuable comments. We retain the problem/results and clarify applications and limits.

W1 — Readability

Section 2 adds inputs/setting/outputs/notation; Section 3 links example/workflow. Figure 1 previews verification (p. 3), Figure 2 incompatible marginal extremes (p. 4). Validate inputs, test unresolved selected–outsider pairs against the compact exact joint image, then recover a raw witness or exclude every adverse pair to certify.

Use translates of (0,ξ,t1,t2)(0,\xi,t_1,t_2), 1≤ξ≤5/41\le\xi\le5/4, t1,t2∈[−1,2]t_1,t_2\in[-1,2], ∣t1−t2∣≤1/4|t_1-t_2|\le1/4. Candidates p,qp,q cannot both normalize to interior values: the others would need span ≥1, violating their bound. Scores: pp is 0 on [1/8,3/8)[1/8,3/8), else 1; qq is 1/21/2 on [5/8,7/8)[5/8,7/8), else −1; others −2. When pp scores 0, qq normalizes to 1 and scores −1. Thus pp wins despite its marginal minimum below qq's maximum.

W2 — Explain applications, prevalence and top-kk stability's value.

Section 1 cites gradient-boosted tree rerankers (LightGBM, Ke et al., 2017) and QueryLevelNorm features (LETOR 4.0 documentation). These establish context; prevalence of our precise contract is unmeasured. Offline senders certify lower precision preserves a set, escalate or revert (p. 1). Measured savings concern payload, not production benefit.

W3 — Specify minimum/maximum domains.

Section 2 defines [m]={1,…,m}[m]=\{1,\ldots,m\}, indexes min⁡j∈[m]rj\min_{j\in[m]}r_j, max⁡j∈[m]rj\max_{j\in[m]}r_j and contrast extrema, and maps constant raw vectors to zero (pp. 2–3). Introduction minimum μ\mu avoids candidate-index collisions.

W4 — Define contrasts, bounds and QijQ_{ij}.**

Before geometry, Section 2/Table 1 defines r∈Rmr\in\mathbb R^m, c(i)=(ri−rj)j∈[m]c^{(i)}=(r_i-r_j)_{j\in[m]}, raw zone P(B)\mathcal P(B), bounds (−Bji)j∈[m](-B_{ji})_{j\in[m]}, (Bij)j∈[m](B_{ij})_{j\in[m]}. Joint image Qij={(zi(r),zj(r)):r∈P(B)}\mathcal Q_{ij}=\{(z_i(r),z_j(r)):r\in\mathcal P(B)\} contains attainable normalized features, distinct from scores Fi(zi)F_i(z_i) (pp. 2–3).

W5 — Separate Theorems 2/3's explanations.

Section 3 separately labels Theorem 2's small-image and Theorem 3's complete-decision sketches (pp. 5–6), linking workflow/example (pp. 4–6). Fixed extrema/positive reciprocal range linearize cell feasibility. Projective minimum-only/maximum-only/joint caps factor into O(m)O(m) frontier pieces despite m(m−1)m(m-1) roles. Construction is O(m2)O(m^2) after closure; matching lower bound concerns size, not optimal runtime. A changed top-kk set has a selected–outsider inversion: checking every owned adverse-cell intersection, including priority ties, is complete; a hit extends to a full raw witness. Closure/profiles/rational bit costs/replay cost extra. Implemented signed Grouped differs from analytical hybrid dispatch.

W6 — Explain the experimental transition and significance.

Section 4 introduces constructed efficiency/retrieval shared modeling, then data/targets/baselines. Paragraphs separate original computation, external search, scalability, shared gains, natural profiles and applications (pp. 7–10). Tables 3/4/5: original completion/invariant attribution/executed precision. Complete/shared-modeling gains differ; no general Grouped speed advantage is claimed on natural retrieval. Fixed selections from reused post-review TEST are not untouched confirmation.

W7 — Explain VERITAS, Z3 and other baselines.

Before Table 3 (p. 7), Grouped merges extrema roles, Clipped clips roles, Cartesian enumerates roles/cells, and active tables tabulate scale constraints: four in-house implementations. Z3, de Moura/Bjørner, 2008 solves our raw-zone QF_LRA encoding. VERITAS, Devos et al., 2021 contributes native constrained tree-ensemble search with our Cartesian role-feasibility oracle, not an independent geometry proof. Domains/targets/screens/replay/budgets are stated; caps are non-decisions; original/later studies stay separate.

W8 — Data and construction

NFCorpus/BEIR SciFact use 323/300 TEST queries, frozen 100-tree seven-feature LambdaRank, stored 384-dimensional MiniLM vectors, BM25 top-32.

Boteva et al., 2016, Wadden et al., 2020, Thakur et al., BEIR 2021 establish provenance, not robustness. Only similarity varies. Original 8/16-bit top-1/top-3 targets use midpoints; later policies fix original-query targets (Section 4, p. 7).

16 graph cases use ring/bridge shortest-path distances plus candidate offset differences: m=8,16,32,64m=8,16,32,64, profiles 32/128. 36 frontier cases pair 18 analytical invariants/18 counterexamples by changing a bridge bound, retaining profiles: computation, not prevalence. Section 4/C.5 specify three fresh-process rotated repetitions, five-second adapter CPU cap, charging imports/closure/preparation/screens/solving/replay. MiniLM/Qwen3 comparisons use 16 NFCorpus DEV queries/model. LETOR 4.0: 32 TRAIN queries, 46 features, PageRank-only uncertainty; 480 conditions give 430 invariants/50 counterexamples, all invariants marginal-certified or trivial full-set cases (F).

W9 — Simplify “full rational potential”; separate binary64 details.

Theorem 3 now calls it a “feasible rational raw-feature vector” in P(B)\mathcal P(B): supplied differences hold, selected set differs from SS (p. 5). Theory assumes supplied real score cells, rational endpoints, exact ownership/comparable scores. Binary64 uses exact preimages (B); arithmetic/tie assumptions remain.

Q1 — When shared uncertainty applies

Either fits its perturbation source. A common query qq, fixed documents viv_i give ri=vi⊤qr_i=v_i^\top q. For q=q0+eq=q_0+e, ∣eℓ∣≤ρ|e_\ell|\le\rho, ρ≥0\rho\ge0, ri−rj≤(vi−vj)⊤q0+ρ∥vi−vj∥1=Bij.r_i-r_j\le(v_i-v_j)^\top q_0+\rho\|v_i-v_j\|_1=B_{ij}. Independent intervals give no-smaller radius ρ(∥vi∥1+∥vj∥1)\rho(\|v_i\|_1+\|v_j\|_1). Identical documents give zero difference: input dependence, not universal correlated noise (Section 1, p. 2).

Independent raw noise fits Corollary 4 (p. 5); normalization can couple outputs. The linear-image result allows many query coordinates to change one similarity/candidate with text/pool/six inputs fixed; no arbitrary multi-feature changes. Use source-appropriate domains and cheap exact checks: m≥4m\ge4 and strictly positive off-diagonal bounds give full-square images/complete exact marginals. Zero/negative bounds do not imply joint solving is necessary (Section 3).

Q2 — How can the results of this work be applied?

A counterexample diagnoses domain sensitivity; distinguish abstract/query domains. Missing certification does not prove instability.

OutcomeMeaning and action
InvariantSet retained domain-wide for fixed model/pool/evaluator/ties; transmit covered representation.
Raw-zone counterexampleAllowed abstract vector changes set; inspect comparison, test realizability or raise precision.
Replayed query-cell counterexampleAllowed numerical query changes set; narrow domain, raise precision or fall back/reverify.
Query-cell invariant despite zone violationOuter zone is too permissive; no demonstrated query failure.
Cap/failed witness searchCap: property undecided. Failed query search after zone violation: realizability unknown. Escalation/fallback is not certification.

Invariance transfers to represented queries, counterexamples need not. Numerical realizability is not text realizability; sets guarantee neither order, relevance nor recall.

Reference arithmetic. Stored binary32 query fixes reference with the same ordered pool/frozen ranker. Similarities are exact dot products of stored binary32 document vectors with that query or the exact decoded midpoint. Exact pool min–max maps constants to zero, followed by one binary64 nearest-even rounding. Native LightGBM 4.6.0 uses it plus six frozen binary64 inputs, document-ID ties. Exact-preimage profiles preserve branches/scores. This exact-dot/once-rounded contract does not certify arbitrary BLAS/GPU dots or sequential float32 pipelines. Receiver decoding/scoring matches. Certification retains reference membership across the decoded query’s cell (J.9–J.10, K.1).

Complete residuals. All 623 TEST queries, original models/top-32, 8/16 bits, midpoint k=1,3k=1,3, three repetitions, 30s/condition, 2s strong screens: after cheap falsification and completed strong screens, Grouped/Cartesian/adapted VERITAS resolve identical 21/1,292 NFCorpus and 9/1,200 SciFact residuals as raw counterexamples, with constraint/exact/native replay. The 30/2,492 adverse decisions are neither extra invariants nor Grouped-exclusive (K.4, pp. 87–88).

Query audit. An unconditional hash sample takes 200 conditions, 25/dataset/8-or-16-bit/kk stratum, original models/pools/midpoint targets: 132 zone invariants, 67 query counterexamples among 68 zone-adverse cases, and one query-cell invariant overlapping an earlier gap. In broader 890/367 NFCorpus/SciFact adverse cohorts, nine distinct gaps are proved; 287/145 remain unknown (Section 4, p. 9; J.8, pp. 77–78). All 200 samples resolve, without estimating population tightness; broader unknowns remain unclassified.

Executed lazy policy. Fix the original-query reference, try 8/10/12/14/16 bits, send the first certified representation, else binary32; unvisited precisions are not prepared. Use first 16 queries/dataset in the earlier hash order, original models, supplied top-32/stored 384-dimensional embeddings, k=1,3k=1,3, four policies, three serial rotated repetitions. All 768/768 complete with reference-matching received sets: 64 query/kk cases. Policies: binary32, independent complete, shared sufficient/complete; complete policies use Grouped, sufficient never does (Table 5, p. 9; J.10, pp. 79–80).

DatasetkkIndependent bytesShared bytesShared saving/binary32, % [95% CI]Seconds: binary32/shared complete
NFCorpus166458661.95 [51.82,68.57]0.00430/0.89457
NFCorpus370667056.49 [47.14,62.73]0.00409/1.05065
SciFact147844271.30 [68.96,73.25]0.00406/0.59566
SciFact376064058.44 [49.09,65.06]0.00413/0.79235

Means shown; binary32 is 1,540 bytes. Include four-byte vector header; exclude common four-byte transport frame/network headers. Rows have 16 query clusters × three repetitions/policy; descriptive CIs use 2,000 cluster resamples after repetition averaging. Shared saves 56.49–71.30% versus binary32, 5.10–15.79% versus independent. Shared policies choose identical precision on all 192 paired requests: 9/192 fallbacks each versus independent 18/192, or 3/64 versus 6/64 distinct cases. Complete resolves nine residual precision-stage counterexamples, saving no extra bytes: shared-modeling gains.

Offline Linux/i7-13700K: one numerical thread, warm assets/fresh preparation, no cross-request reference/profile/decision cache. Charge required reference acquisition, profile/domain construction, provenance, all attempted stages, codec, IPv4 loopback transport and receiver ranking. Binary32 pays no certification/redundant sender reference. Exclude text embedding, retrieval, one-time asset/process startup. Budgets: 30s solver/reached precision, 2s/strong screen, 120s cooperative certificate deadline, 180s hard request guard; reject late certificates. None failed, timed out or remained unstarted.

Shared-complete means are 0.596–1.051s versus binary32 0.00406–0.00430s; shared-sufficient is 0.597–1.043s. Payload savings cost more computation/loopback latency. Reused TEST establishes no production savings/cache economics/latency gain. Linux/Windows times stay separate.

Witness-to-action cases. Four deterministic historical top-3 (k=3k=3) cases outside the primary cohort give 16 completed requests; three certificate policies independently choose identical precision/case, retaining reference (J.11, pp. 79–80).

Dataset/queryAttempted bitsCertified bits/bytesMeaning
NFCorpus/PLAIN-17728,10,1212/580Midpoint/reference agree; old 8-bit query witness replays; 12 bits retains reference.
NFCorpus/PLAIN-12148,10,12,14,1616/772Old midpoint/reference differ; reference retained.
SciFact/1308,10,1212/580Midpoint/reference agree; old 8-bit query witness replays; 12 bits retains reference.
SciFact/3128,1010/484Reference retained; old witness missing, no new realizability claim.

Three witnesses pass fresh exact/native replay; missing fourth not replaced. PLAIN-1772/130 witnesses lie outside 10-bit/finer cells: escalation narrows uncertainty, not repairs the same perturbation. PLAIN-1214's witness is the original query, in every tested cell; old midpoint top-3 has MED-1003, fixed reference instead MED-1010, preserved at 16 bits. Inspect target/domain together; these cases enter no primary timings and establish neither prevalence nor text attacks.

Reviewer_JEN9OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

We are given mm candidates and a difference matrix BB. Each candidate ii has one uncertain scalar rir_i. The difference ri−rjr_i-r_j between uncertain scalars is upper bounded by the matrix entry BijB_{ij}. Scores are normalised with shared min-max normalisation: zi(r)=ri−min⁡jrjmax⁡jrj−min⁡jrjz_i(r)=\frac{r_i-\min_j r_j}{\max_{j} r_j - \min_j r_j}. Call a vector rr legal if ri−rj≤Bijr_i -r_j \le B_{ij}. The paper studies top-kk rank verification with respect to the normalised scores under pertubations that are consistent with the difference matrix, i.e., for all legal vectors rr.

First, the authors consider two fixed candidates ii and jj. The normalised pair image QijQ_{ij} is the set of points (zi(r),zj(r))(z_i(r),z_j(r)) over all legal vectors rr. This region is particularly important for top-kk rank verification: If ii is in the top-kk candidate set, jj is not in the candidate set, and QijQ_{ij} contains a point where jj outranks ii, then this leads to a change in the top-kk for that point. As a first main result, the authors show that the set QijQ_{ij} has straight-line complexity O(m)O(m) and can be constructed in O(m2)O(m^2) operations. These geometric insights are then used to give upper bounds on the complexity of top-kk verification, as they allow to prevent the comparison of all combinations of score-profile regions.

Critical strengths
  • The structural insights on the regions QijQ_{ij} are nice. They seem like a relevant and non-trivial contribution. The usage of these regions seems like a very natural approach within the context of top-kk verification.
Critical weaknesses
  • The paper is unnecessarily difficult to understand for non-experts. It starts in the introduction where notation like rjr_j, BI,jB_{I,j}, zi(r)z_i(r) and P(B)\mathcal{P}(B) is used with being introduced. Then, the problem at hand is never explicitly introduced (there is no paragraph that explicitly says this is the input, this is the setting, this is what we want to do).
  • The bounds obtained by Theorems 2 and 3 are not put into context. Do these improve over previous results? Are there complementing lower bounds? What do they mean within the context of the current state-of-the-art? (For theorem 2, the authors give a lower bound)
  • From the main body of the paper, it is tough to reconstruct the full approach. An overview section that gives the full high-level idea would be very helpful. (I fully admit that this might partially have to do with my lack of expertise on this topic.)
Questions for authors
  • Can you discuss the meaning of your results compared to the state-of-the-art?
6 comments

Thank you for your valuable comments. These are essential to understanding the result. We have added an input/setting/output paragraph and notation table in Section 2, connected the example to a numbered workflow in Section 3, and separated the two theorem explanations. We also clarify the meaning of the complexity bounds before the experiments. The central problem and guarantees are retained.

W1 — Explicit inputs, setting, outputs, and notation

Section 2 and Table 1 now state the input/setting/output contract explicitly (pp. 2–3), and the Introduction defines its notation at first use. The inputs are a fixed pool of mm candidates, a nonempty zone of finite rational difference bounds, complete piecewise-constant score profiles FiF_i, a proposed size-kk set SS, and a fixed total tie priority. Each profile consists of finitely many ordered, nonempty intervals forming a disjoint partition of [0,1][0,1], with rational endpoints, explicit endpoint ownership, and exactly comparable scores. Exactly one raw feature per candidate varies; all other inputs remain fixed. Writing [m]={1,…,m}[m]=\{1,\ldots,m\}, the uncertainty and normalization are

z_i(r)=\frac{r_i-\min_{v\in[m]}r_v}{\max_{v\in[m]}r_v-\min_{v\in[m]}r_v}.$$ Here $r_i$ is a raw feature, $B_{ij}$ bounds its difference from $r_j$, and $\mathcal P(B)$ is the set of feasible raw vectors. Constant raw vectors map to zero. The ranker compares learned scores $F_i(z_i)$, not normalized feature values alone. The output is either a certificate that $S$ is unchanged throughout the zone or a feasible raw vector that changes it. A resource cap produces no decision. **W2 — Meaning of the theorem bounds and lower bounds** Theorem 2 gives a compact exact representation for signed difference zones; Theorem 3 gives procedure-specific upper bounds for using that representation in ranking verification. The improvement is specialized geometric representation and profile processing, rather than the first availability of exact tree-ensemble verification or a universal runtime advantage over existing solvers. For Theorem 2, up to $m(m-1)$ extrema roles yield an exact pair image with only $O(m)$ boundary complexity, constructible in $O(m^2)$ arithmetic/comparison operations after closure. Factored minimum-only and maximum-only caps restrict the frontier, while diagonal pieces merge. The matching example proves a worst-case output-size lower bound, not runtime optimality. The image may be nonconvex and contain lower-dimensional pieces (Section 3, pp. 4–5). The structural reason is that, in transformed coordinates, minimum-only and maximum-only caps provide at most $m$ step locations and levels; the joint caps contribute collinear diagonal pieces that merge. At most seven patches suffice. This exploits the extrema-role structure: general segment envelopes can have $O(N\alpha(N))$ complexity and admit $O(N\log N)$ construction ([Hershberger, 1989](https://www.sciencedirect.com/science/article/pii/0020019089901361)). Our tighter representation is not obtained by treating the role boundaries as arbitrary segments. Theorem 3 processes profiles without enumerating every profile-cell combination. For profile sizes $P_i,P_j$, with $N\le m(m-1)$ eligible extrema roles, Table 2 gives: | Complete procedure | Per-pair upper bound | | --- | --- | | Generic role/cell feasibility | $O(m^2P_iP_j)$ exact LP calls; LP cost additional | | Batched role-polygon sweep | $O(N(P_i+P_j))$ operations | | Active-scale tables | $O(m^2+P_iP_j)$ operations | | Grouped image/profile processing | $O(m^2+(m+P_i+P_j)\log(2+m+P_i+P_j))$ operations | For dense roles and $P_i=P_j=\Theta(m^2)$, the stated polygon/table procedures cost $O(m^4)$, versus $O(m^2\log m)$ for Grouped. At $P_i=P_j=\Theta(m)$, both Grouped and active tables cost $O(m^2)$. Full verification sums the relevant pair costs; closure, profile construction, rational bit costs, and replay are additional. These are upper bounds for specified procedures, not lower bounds against all competing algorithms (pp. 5–6). We do not provide a matching runtime lower bound for Theorem 3. Its automatic hybrid dispatch remains analytical, rather than an implemented dispatch claim.

W3 — A complete workflow and a four-candidate example

Figure 1 now previews the complete verification path, and Section 3 gives a numbered procedure before the theorem statements (pp. 3–4). The geometry and decision proof explanations are separately labeled. The workflow is:

  1. Validate the inputs, prepare the closed bounds, check the constant-input branch, and apply sufficient checks.
  2. For each unresolved selected–outsider pair, construct its jointly attainable normalized image Qij={(zi(r),zj(r)):r∈P(B)}Q_{ij}=\{(z_i(r),z_j(r)):r\in\mathcal P(B)\}.
  3. Test whether that image intersects score cells in which the outsider wins, including the fixed tie rule.
  4. Recover and replay a feasible raw counterexample if an intersection exists; otherwise certify after every relevant pair is excluded.

The pairwise reduction is exact: changing a top-kk set requires an outsider to outrank a selected candidate. The key difficulty is that independently attainable score extrema can require incompatible raw vectors.

The four-candidate example illustrates this directly. Consider all translates of (0,ξ,t1,t2)(0,\xi,t_1,t_2), where ξ∈[1,5/4]\xi\in[1,5/4], t1,t2∈[−1,2]t_1,t_2\in[-1,2], and ∣t1−t2∣≤1/4|t_1-t_2|\le1/4. Call the first two candidates p,qp,q. Their normalized values cannot both be interior: that would require t1,t2t_1,t_2 to supply a span of at least one, contradicting ∣t1−t2∣≤1/4|t_1-t_2|\le1/4. Give pp score 0 on [1/8,3/8)[1/8,3/8) and 1 elsewhere; give qq score 1/21/2 on [5/8,7/8)[5/8,7/8) and −1-1 elsewhere; the remaining scores are −2-2. Whenever pp scores 0, qq must normalize to 1 and score −1-1; otherwise pp scores 1 and exceeds every competitor. Thus pp always wins, although its marginal minimum is below qq's marginal maximum. The joint image excludes precisely the misleading adverse combination (Figure 2, p. 4): the sufficient marginal test is inconclusive, but the joint test certifies. This invariant example has no counterexample; the replay step describes the alternative outcome when an adverse intersection exists.

Q1 — Can you discuss the meaning of your results compared to the state-of-the-art?

Exact tree-ensemble verification already exists, including Kantchelian et al. (ICML 2016) and VERITAS (Devos et al., ICML 2021). Our contribution is the specialized normalized-pair representation and its processing bound for a fixed ranker with one uncertain feature per candidate. Adapted VERITAS in our experiments uses an exact role-feasibility oracle supplied by our implementation. Section 5 explains that relationship and distinguishes other settings, including large-spread ensemble restrictions and certified image retrieval (p. 10). A compact exact representation does not imply that Grouped must always be the fastest solver; our comparisons identify where its computational benefit occurs and where it does not.

Calzavara et al., Verifiable Boosted Tree Ensembles (IEEE S&P 2025) obtains polynomial L∞L_\infty verification by imposing large-spread restrictions on boosted ensembles. RetrievalGuard (Wu et al., ICML 2022) certifies smoothed image-retrieval Recall@1 under bounded perturbations. Those model restrictions and quality properties differ from retaining exact top-kk membership for our fixed normalized ranker; we make no timing comparison to either method. The contribution is specialized geometry under the stated contract, not an exponential-to-polynomial result for arbitrary tree verification.

The separate post-review comparison uses 90 constructed cases, six methods, and three repetitions: 1,620 calls. Five seeds cover profile/core/group axes and ten constant-profile controls; the primary profile axis fixes c=10,k=2,m=12c=10,k=2,m=12, with bounds, target, and priorities matched within each seed/label. Persistent Windows calls have a 10-second wall limit, five-million counted-work and 2,048-bit Python-rational limits, a sampled 8-GiB RSS guard, and a 512-MiB native VERITAS search cap. Preparation, closure, screens, and replay are charged; imports/startup and model-to-profile extraction are excluded because profiles are supplied. Direct Z3 (de Moura and Bjørner, TACAS 2008) uses linear real arithmetic; adapted VERITAS uses our Cartesian role-feasibility oracle.

Grouped and Clipped complete 90/90 cases; Cartesian and Z3 complete 75/90, adapted VERITAS 70/90, and active tables 25/90. Completion requires all three repetitions. At 1,024 profile cells, Grouped and Clipped complete all five invariant cases in median 2.442/3.935 seconds; the other four methods complete none. At 16 cells, Cartesian and VERITAS are faster, at 0.177/0.196 seconds versus Grouped's 0.304 seconds. Active-table failures hit the work cap, not necessarily the deadline, and native instrumentation differs across libraries: the Python-rational counter does not bound native Z3 arithmetic. Section 4 and Appendix C.6 retain these limits and the original five-second results separately; timings on different surviving case sets are not matched speed comparisons.

A 512-condition natural-profile census finds no condition meeting the fixed high-complexity timing criterion across the original and larger selected models; one strong-screen cap remains recorded (Appendix E.6). The conditional timing campaign was therefore not triggered. Natural-query timings likewise show no overall Grouped advantage. The evidence locates the observed benefit in the constructed high-profile regime, rather than establishing its prevalence in natural workloads.

The census uses 32 previously hash-fixed queries per dataset, m=32m=32, 8/16 bits and k=1,3k=1,3, comparing original 100-tree models with already selected 200/300-tree models. Pools, bounds and other features are matched, while each model has its own fixed unquantized-reference target. The gate requires at least 32/128 conditions per model whose maximum per-candidate reachable profile size is at least 64 cells and which have a residual after completed stronger checks; every model has 0/128. The capped condition's known maximum is 35, so retaining that unknown cannot change the gate result. This checks effective profile complexity rather than equating tree count with verification difficulty.

An independently formulated raw-zone SMT audit corroborates all 18 original controlled invariants: 16 at 60 seconds and two after 300-second retries (Appendix C.6). This is an additional correctness check with a distinct budget, not a replacement for the proof or independent proof-kernel validation. It does not turn the original short-budget comparison into an equal-budget speed result. We therefore claim a specialized exact representation, conditional computational gains, and independent corroboration of these controlled invariants, not general superiority over the state of the art.

For that audit, every tested zone has a negative bound, which forces a positive raw range and excludes constants. The independent encoding uses 0≤z≤10\le z\le1, min⁡z=0\min z=0, max⁡z=1\max z=1, t>0t>0, and zi−zj≤Bijtz_i-z_j\le B_{ij}t. Forward, set t=1/range⁡(r)t=1/\operatorname{range}(r); conversely, r=z/tr=z/t reconstructs a feasible raw vector. Independently derived rounded-profile guards and adverse comparisons complete the formula, without importing the geometric verifier's closure or preimage helpers. This explains what was corroborated and why the longer-budget checks do not replace the original five-second result of 8/18 completed invariants.

Reviewer_KdkBOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper verifies whether a top-k ranking remains the same when each candidate's raw feature is uncertain (represented by pairwise difference bounds) and passes through shared min-max normalization before a tree ensemble. It shows that exact per-candidate bounds can fail here, and proves that the exact joint image of two normalized values has a tight O(m) edge boundary, computable in O(m^2) after closure. This yields a complete verifier that certifies the ranking or returns a counterexample.

Critical strengths
  1. The paper addresses an established problem, top-k ranking verification, and identifies a gap in shared normalization that couples candidates’ scores.
  2. Within-query min-max normalization is common in learning to rank, and the paper shows it makes standard per-candidate verification incomplete; even exact marginal bounds can fail to certify a ranking that is invariant. The four-candidate example in Section 3 (Figure 2) makes this concrete.
  3. For signed difference zones, up to m(m-1) min/max roles contribute to the pair image, yet its boundary has only O(m) edges because two of each role’s three caps depend only on the minimum or only on the maximum, and the remaining joint cap only creates slope -1 edges that merge. A matching worst-case lower bound (Proposition 10) shows this boundary size cannot be improved.
  4. Sweeping the two score profiles along the O(m) boundary avoids checking every pair of profile cells (Proposition 11). With one uncertain feature per candidate and the other inputs fixed, the method applies to any piecewise-constant scorer, including non-monotone ones.
Critical weaknesses
  1. In Table 3, shared constraints raise certified conditions from 735 to 824 of 1292 on NFCorpus and from 747 to 833 of 1200 on SciFact, but cheap shared screens already reach 823 and 832. 2)The selected min-max models also show no significant change from the original ones, since both bootstrap intervals include zero. Without shared normalization, each candidate’s score depends only on its own raw value, and verification becomes much simpler. It is therefore unclear when practitioners would face this problem rather than avoid it.
  2. Only one scalar per candidate is uncertain, and all other inputs are fixed. In the retrieval models, only one of seven features varies, and in the LETOR study only PageRank varies while the other 45 per-query normalized features stay fixed. Realistic perturbations would often move several normalized features simultaneously, and each candidate’s score would no longer be a one-dimensional profile. Does the O(m) pair-image result extend to that case?
  3. Section 4 reports NDCG@1 lower bounds (116 vs. 114 of 323 NFCorpus queries). The certified quality property is mentioned there but not defined, and the property, the validation-selected models, and the protocol appear only in Appendix J6-J7. The appendix also notes that this study was designed after the TEST outcomes were known, and that only one of the two additional certificates is new relative to the earlier identity certificates.
  4. Notation is hard to follow. r, z_i(r), and P(B) are used in Section 1 before they are defined in Section 2. The main text never states that r is a vector in Real^m (this appears only in Appendix A), and the contrast vector d is made explicit only in Appendix A. Letters are reused with different meanings (d in Sections 2 and 3; u, v as indices and as coordinates), and the appendix switches to U and N_i(r) for B and z_i. A notation table, a running example through Section 3, and moving tie and endpoint handling to the appendix
Questions for authors

Q1: What share of total runtime does O(m^3) closure take at m = 32, and how does the full cost scale to larger pools (for example, m = 128 or 256)?

Q2: How loose is the difference zone relative to the true quantization cells? For the conditions without a confirmed real-query counterexample (beyond the 559 of 890), is this a search-budget limit, or are those witnesses genuinely unrealizable?

Q3: Why are the NDCG@1 results reported in Section 4 while the certified property, models, and protocol are only in Appendix J.6-J.7? Given that the study was designed after the TEST outcomes and complete verification adds two certificates (116 vs. 114), only one of them is new; do you see it as a contribution of the paper or as exploratory?

Q4: With several uncertain features per candidate, each score is no longer a one-dimensional profile. Does the O(m) pair-image result extend to that setting, or would verification fall back to the generic polyhedral formulation, and at what cost?

6 comments

Thank you for distinguishing the theoretical contribution from its practical scope. We retain the problem/theorem assumptions, clarify the contract in Sections 1–3 and separate original/post-review evidence in Section 4.

W1a — Complete verification's added value

On original 100-tree rankers, BM25 top-32 pools, 8/16-bit cells and midpoint k=1,3k=1,3 targets:

DatasetConditionsIndependent completeOriginal shared screensShared complete
NFCorpus1,292735823824
SciFact1,200747832833

Stronger role-envelope screens recover each last invariant. Table 4 (Section 4, pp. 8–9) attributes most gains to shared modeling. The post-review audit of all 323/300 TEST queries gives Grouped, Cartesian and adapted VERITAS identical common checks, cheap raw-potential falsification and stronger screens: three repetitions, 30s/condition, 2s strong-screen cap. After screens finish, all backends/repetitions resolve identical 21/1,292 and 9/1,200 residuals as raw-zone counterexamples, with exact constraint/native-score replay (K.4). These 30/2,492 adverse decisions are neither extra invariants nor Grouped-exclusive gains; raw witnesses need not be query-realizable.

Computational gains depend on profile complexity: 90 constructed cases, five seeds, six methods, three repetitions, 10s wall cap and separate common work limits. Grouped/Clipped complete 90/90, Cartesian/Z3 75 each, adapted VERITAS 70, active tables 25. At 1,024 cells, c=10,m=12,k=2c=10,m=12,k=2, Grouped/Clipped finish all five invariant cases in median 2.442/3.935s; the other four finish none. For five corresponding adverse cases, Grouped/Cartesian/Clipped/Z3 medians are 0.401/6.014/0.543/1.092s. At 16 cells, Cartesian/VERITAS are faster: 0.177/0.196 versus Grouped's 0.304s. Profiles, indexed BB, targets and priorities match; model-to-profile extraction is excluded. Section 4/C.6 separate these regimes from original five-second comparisons.

Kantchelian et al., ICML 2016 give optimal mixed-integer evasion; Devos et al., ICML 2021/VERITAS give general tree-ensemble verification. We specialize computation for shared normalization, not access to exact answers. Adapted VERITAS uses our exact role-feasibility oracle, not an independent geometry proof.

The natural-model census (E.6): 32 previously hash-fixed queries/dataset, m=32m=32, bits 8/16, k=1,3k=1,3; 128 conditions/model, 512 total. Pools, indexed BB, priorities/fixed features match; model-specific unquantized-reference targets stay fixed across bits. Authenticated saved native-qualified profiles/model-selection receipts entail no new fit/fresh-extraction timing. Merged adjacent equal-score cells intersect exact rounded-preimage sharp marginal hulls.

Dataset/modelMean merged cells/candidateReachable max, 8/16 bitsCommon/finished-strong residuals, of 128Strong unknowns
NFCorpus/original10043.8037/254/521
NFCorpus/selected20046.0735/251/480
SciFact/original10026.9726/242/410
SciFact/selected30057.4453/243/430

The pre-fixed gate requires ≥32/128 conditions/model with maximum reachable cells/candidate ≥64 and a residual after completed strong screening; all have 0/128. The original NFCorpus unknown hits 2s but has max 35 cells: gate unchanged, unknown retained, conditional timing untriggered. Tree count alone does not establish the controlled-gain regime; this is neither a complete-decision census nor general retrieval superiority.

W1b — Why retain normalization?

Removal is reasonable for a different ranker. For our fixed trained contract, raw minimum μ\mu and range R>0R>0 give zi<t  ⟺  ri<μ+tRz_i<t\iff r_i<\mu+tR: thresholds depend on shared extrema. Learned candidate-specific Fi(zi)F_i(z_i) rank candidates, so deletion generally changes the certified function (Section 1).

Qin et al., Information Retrieval 2010 describe LETOR; LETOR 4.0 author documentation supplies QueryLevelNorm features. OpenSearch normalization uses min–max to rescale differing keyword/vector scores before fusion. These motivate, not establish necessity/deployment prevalence; we claim no coverage of its fusion or special zero/constant-score conventions.

The intervals compare selected/original min–max, not raw/min–max. Raw, TRAIN-fixed affine and query min–max have equal eight-configuration searches/fit counts, including an extra quantization-augmentation option per transform. Recipes use NFCorpus DEV/text-grouped SciFact TRAIN, then SciFact refits on all TRAIN; all six choose ordinary training. Designed after TEST observations, equal fits imply neither equal training CPU nor selected capacity (J.6).

Selected-model TEST NDCG@10RawFixed affineMin–max
NFCorpus0.3323810.3352320.332550
SciFact0.7274930.7210000.728092

No quality advantage or equivalence is established; auditing retained normalization does not recommend adoption for prediction.

Supplementary exact-real extensions (M, pp. 90–91): let P(B)={r:ri−rj≤Bij ∀i,j}\mathcal P(B)=\{r:r_i-r_j\le B_{ij}\ \forall i,j\}; retain finite downstream piecewise-constant profiles, exact endpoint ownership and fixed tie priority.

Positive affine postprocessing: for rational ai>0,bia_i>0,b_i, yi=aizi+biy_i=a_i z_i+b_i and a finite rational interval partition for GiG_i on [bi,bi+ai][b_i,b_i+a_i], define Fi(t)=Gi(ait+bi)F_i(t)=G_i(a_i t+b_i) on [0,1][0,1]. Endpoints l,ul,u pull back to (l−bi)/ai,(u−bi)/ai(l-b_i)/a_i,(u-b_i)/a_i; positivity preserves order/ownership, a partition of [0,1][0,1], scores and adverse comparisons. Constant raw inputs give zi=0,yi=biz_i=0,y_i=b_i; [−1,1][-1,1] uses ai=2,bi=−1a_i=2,b_i=-1. Other min–max supplied-profile hypotheses/resulting sizes still apply. This neither removes min–max nor treats arbitrary affine final scorers. Machine profiles must encode the composition, including added rounding.

Softmax: for fixed τ>0\tau>0, m≥2m\ge2, finite BB and nonempty P(B)\mathcal P(B), sτ(P(B))={p≥0:∑ipi=1, pi≤eBij/τpj ∀i,j},sτ,i(r)=eri/τ/∑verv/τ.s_\tau(\mathcal P(B))=\{p\ge0:\sum_i p_i=1,\ p_i\le e^{B_{ij}/\tau}p_j\ \forall i,j\},\qquad s_{\tau,i}(r)=e^{r_i/\tau}/\sum_v e^{r_v/\tau}. Necessity: pi/pj=e(ri−rj)/τp_i/p_j=e^{(r_i-r_j)/\tau}. Conversely, any zero pjp_j forces all pi=0p_i=0, contradicting the simplex. Thus p>0p>0, and ri=τlog⁡pir_i=\tau\log p_i satisfies the differences and recovers pp. This compact polytope lies inside the positive simplex. Add adverse owned cells pi∈Ii,pj∈Ijp_i\in I_i,p_j\in I_j: excluding all adverse selected–outsider cell pairs certifies the target; feasible full pp yields a raw witness. Even rational B,τB,\tau can yield irrational exponential/log values. Exact comparisons, strict endpoints and machine exponentials need a separate backend; min–max construction/bit-complexity bounds do not transfer. Wei et al., AISTATS 2023 give convex softmax bounds; our exact zone image need not equal reachable neural logits. Direct probabilities preserve logit order; downstream candidate-specific profiles make this nontrivial.

Nonnegative ℓ1\ell_1: for r≥0r\ge0, ri−rj≤Bijr_i-r_j\le B_{ij} and ∑iri>0\sum_i r_i>0, the exact image is {p≥0:∑ipi=1, ∃t>0: pi−pj≤tBij ∀i,j}.\{p\ge0:\sum_i p_i=1,\ \exists t>0:\ p_i-p_j\le tB_{ij}\ \forall i,j\}. Forward t=1/∑irit=1/\sum_i r_i, p=trp=tr; backward r=p/tr=p/t: differences/normalization are preserved, specializing Charnes–Cooper, 1962. Adverse cells give linear feasibility in (p,t)(p,t); t>0t>0 excludes unattainable limits at t=0t=0. This is nonnegative exact sum division, not signed ℓ1\ell_1, ℓ2\ell_2, LayerNorm, RMSNorm or epsilon clamping. Softmax/ℓ1\ell_1 are proved, unimplemented formulations, not new experiments; sharp linear min–max pair complexity/machine guarantees do not transfer.

W2 — Several uncertain features

No: the linear theorem requires one uncertain ranker feature and fixed others. PageRank-only tests do not certify all-feature robustness. B.18 (p. 39) gives an unimplemented, exponentially branching polyhedral fallback, detailed in Q4, not an efficient linear-image extension.

W3 — Quality diagnostic

We now define the fixed-anchor test beside the results: the midpoint winner outranks every lower-grade candidate throughout the domain. It sufficiently bounds NDCG@1 while allowing equal-relevance identity changes, but is incomplete. The post-outcome protocol is explicit; this is exploratory, not predictive improvement/independent confirmation. Q3 supplies formula/protocol/counts.

W4 — Define quantities/zone/vectors before use, resolve symbol collisions/aliases, and add notation, an example and clearer tie/endpoint placement.

Section 2/Table 1 states inputs/setting/outputs, distinguishing raw r∈Rmr\in\mathbb R^m, contrasts c(i)=(ri−rj)j∈[m]c^{(i)}=(r_i-r_j)_{j\in[m]}, normalized features and scores.

Section 3 links the four-candidate example, numbered workflow and separate Theorem 2/3 sketches. The Introduction defines quantities/zone at first use; minimum μ\mu, query radius ρ\rho, example ξ\xi and labels p,qp,q avoid collisions. J.7 defines alias U=P(B)U=\mathcal P(B) and raw-input score si(r)=Fi(zi(r))s_i(r)=F_i(z_i(r)). Property-defining ties/constants stay in the main contract; detailed endpoint/machine-preimage arguments stay in B.

Q1 What share of total runtime does O(m^3) closure take at m = 32, and how does the full cost scale to larger pools (for example, m = 128 or 256)?

At m=32m=32, closure takes 18.99%/22.88% of Grouped wall time (NFCorpus/SciFact): eight fixed queries/dataset, three repetitions, four conditions/request (midpoint k=1,3k=1,3, 8/16 bits), supplied pools, fresh native-qualified profiles, full verification/replay; retrieval/text encoding/startup excluded. Grouped means: 2.2203/1.8663s; adapted VERITAS: 2.2244/1.7975s (K.5, p. 88), not general Grouped superiority.

For fixed viv_i and nonempty bounded common-query set QQ, Bij=sup⁡q∈Q(vi−vj)⊤qB_{ij}=\sup_{q\in Q}(v_i-v_j)^\top q. Splitting via kk gives Bij≤Bik+BkjB_{ij}\le B_{ik}+B_{kj}: no path beats its direct edge, so shortest-path closure is unchanged. A common query supplies feasibility; diagonals are zero; suprema handle open/owned endpoints. Exact reconstruction/equality/provenance checks from ordered documents/cell skip only input-BB closure for all backends. Arbitrary/unqualified matrices and subsequent normalized-bound closure keep generic paths. Closedness does not equate zone/query image.

The follow-up uses four previously hash-selected TEST queries/dataset, original 100-tree models, natural BM25 top-128/256 pools, pool-specific original-query references, bits 8/16, k=1,3k=1,3; shared screens/shortcut precede complete solvers as needed. Three serial rotated repetitions use 180s/condition on Windows/Ryzen 9 9950X3D, single-thread libraries. Retrieval/features, fresh native-qualified profiles, references, bounds, per-request support reconstruction/equality, solving/replay/cleanup are charged; one-time assets/model/index loading excluded.

Dataset/backend128 generic, s128 fast, sFast/generic [95% CI]256 fast, s
NFCorpus/Grouped36.4759.1880.2519 [0.2484, 0.2553]23.284
NFCorpus/Cartesian36.4709.0780.2489 [0.2439, 0.2539]22.871
NFCorpus/adapted VERITAS36.2008.9630.2476 [0.2426, 0.2526]22.710
SciFact/Grouped35.0176.9720.1991 [0.1966, 0.2016]20.360
SciFact/Cartesian34.7396.6910.1926 [0.1915, 0.1937]19.807
SciFact/adapted VERITAS34.7886.6870.1922 [0.1908, 0.1932]19.802

Means cover 12 requests (four queries × three repetitions); CIs use 10,000 query-cluster resamples after repetition averaging: descriptive, not untouched population confirmation. Grouped saves 74.81%/80.09% at 128, including support-provenance costs 0.610/0.658s (128), 2.107/2.155s (256), but is 2.50%/4.27% slower than optimized adapted VERITAS at 128. Generic-256 is unmeasured; no matched speedup there.

All 216 requests/864 runs finish without final caps/failures: 621 invariant/243 counterexample evaluations across backends/modes/repetitions, not distinct conditions. Hashes/verdicts match; all counterexamples pass independent raw/native replay, not an invariant proof. Exact integer-Floyd leaves 32 distinct support matrices unchanged. Every backend passes modified-bound, reordered-input, subsequent-constructor and inconsistent-input tests; 24 premeasurement generic/fast qualifications agree. Provenance is charged; this is not closure-log subtraction. Different m32/larger-pool boundaries prohibit scaling ratios; these audit costs are not online search latency (Section 4/K.5).

Q2 — Query realizability

Both missed witnesses and genuine gaps occur; unknowns remain unclassified. Zone invariance transfers to represented queries; raw violations need not. Exact auditing of 60 earlier unresolved conditions found 51 query counterexamples and nine cell invariants despite zone violations.

An unconditional condition-ID hash sample selects 25/dataset/bit/kk stratum: original 100-tree models, top-32, 8/16 bits, k=1,3k=1,3, no outcome selection. The 100 conditions/dataset span 91/90 queries; midpoint targets match across domains. Each selected unknown gets 90s, then unresolved cases get 300s (three NFCorpus retries, none SciFact). All 200 resolve:

Comments on the paper

1 comment
AuthorsOpenReview ↗

Rebuttal Summary

Dear Area Chair and Reviewers,

We sincerely appreciate all reviewers for their time and insightful feedback. We are glad that all reviewers found that:

  • [TnQ8] An overlooked problem in learned ranking. The reviewer highlighted how uncertainty in a shared input, such as a quantized query, can change which candidates a fixed model selects. They saw value in a tool that can determine whether this can happen for a given model and candidate set.

  • [KdkB] A tight geometric result. The reviewer highlighted our four-candidate example: even exact score bounds for each candidate can leave a stable ranking uncertified because the adverse scores cannot occur together. They also recognized that, on signed difference zones, quadratically many possible choices of the minimum and maximum give rise to a region with only linear boundary complexity, with a matching lower bound.

  • [JEN9] A natural route from geometry to verification. The reviewer described the structure of the jointly attainable region as a relevant, nontrivial contribution and saw its use in top-kk verification as natural. A change in membership requires an outsider to outrank a selected candidate under the same feasible input. The region tells us exactly which pairs of normalized values can occur together.

In response to the questions raised by reviewers, we have provided further detail from the following perspectives:

  1. Computational gains. [JEN9, KdkB] The verifier uses the pair boundary to avoid testing every score-cell pair. We prove a tight bound on boundary size and an upper bound on runtime. With a five-second CPU budget, Grouped completed 36/36 controlled cases in all three runs versus 21/36 for adapted VERITAS, with no overall speed advantage on full NFCorpus or SciFact workloads. At 128 candidates (four queries per dataset), skipping redundant closure cut Grouped’s full audit time by 74.81% on NFCorpus and 80.09% on SciFact. All backends could use this shortcut.

  2. Shared modeling and complete verification. [KdkB, TnQ8] The method handles both independent raw noise and shared-query uncertainty. Relative to independent uncertainty, shared constraints yielded 89 additional certificates on NFCorpus and 86 on SciFact. Stronger sufficient checks recovered all of them. Complete verification found raw counterexamples for all 21 NFCorpus and nine SciFact cases left open by inexpensive checks.

  3. Practical use. [TnQ8, KdkB] Our offline policy sent the first certified precision or fell back to binary32. It preserved the reference top-kk set with 56–71% smaller mean payloads than binary32 at higher local latency. Fallbacks fell from 18/192 with independent uncertainty to 9/192 with shared uncertainty. Of 200 audited conditions, 132 were raw-domain invariants, 67 had replayed query counterexamples, and one was invariant throughout the query cell despite a raw-domain violation.

  4. Scope. [KdkB] The linear boundary theorem covers one uncertain feature per candidate. For multiple uncertain features, our theoretical formulation is exact but may require exponential enumeration. We present the exploratory NDCG@1 guarantee alongside its model-selection protocol and results. Of two additional NFCorpus quality certificates, one was new relative to earlier identity certificates.

During the discussion phase, [JEN9] acknowledged the improvements to the manuscript, and [TnQ8] noted that our response clarified how the method handles independent noise and how practitioners could use it. Both reviewers asked us to make the paper’s contributions easier to follow. In response, we further polish the abstract and introduction and brought the problem’s inputs and outputs together in Section 2. Section 3 now uses a single four-candidate example to show how the two main results fit together. Theorem 2 characterizes which pairs of normalized values can occur under the same input, and Theorem 3 uses that characterization to determine whether the top-kk set can change. Section 4 introduces the datasets, baselines, and computational budgets before presenting the results of each comparison.

Considering our detailed rebuttal and the existing scores, we are confident that the solidness and comprehensiveness of our work align with ICLR standards. Our work stands out for several pioneering aspects:

  1. On signed difference zones, we prove that the boundary of the jointly attainable pair region has tight linear complexity in the number of candidates.
  2. This geometry yields a complete verifier that either certifies top-kk membership or returns a feasible raw counterexample.
  3. In our offline precision-selection study, certification preserved the reference top-kk set while reducing mean query payloads by 56–71%, at higher local latency.

We thank the reviewers and the Area Chair for their time and consideration.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.