- 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- 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- candidates. The paper studies the problem where there is a single feature which is uncertain. Given a matrix where the entry guarantees that and a top- set of candidates , 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 is always a top-, or there exists a vector of feature values such that it meets the constraints imposed by , and selects a different set of top- 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- 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- 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- 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 at lines 109-110, and the notation at lines 114-115, 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 that has as top- 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
-
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.
-
How can the results of this work be applied? For example, suppose that I use this method and find that my learnt top- set is unstable - there can exist a raw feature vector that can lead to a different top- set being selected by the learning model. How should I interpret/use this result?
7 comments
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: , 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 : supplied differences hold, selected set differs from (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 , fixed documents give . For , , , Independent intervals give no-smaller radius . 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: 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.
| Outcome | Meaning and action |
|---|---|
| Invariant | Set retained domain-wide for fixed model/pool/evaluator/ties; transmit covered representation. |
| Raw-zone counterexample | Allowed abstract vector changes set; inspect comparison, test realizability or raise precision. |
| Replayed query-cell counterexample | Allowed numerical query changes set; narrow domain, raise precision or fall back/reverify. |
| Query-cell invariant despite zone violation | Outer zone is too permissive; no demonstrated query failure. |
| Cap/failed witness search | Cap: 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 , 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/ 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, , four policies, three serial rotated repetitions. All 768/768 complete with reference-matching received sets: 64 query/ cases. Policies: binary32, independent complete, shared sufficient/complete; complete policies use Grouped, sufficient never does (Table 5, p. 9; J.10, pp. 79–80).
| Dataset | Independent bytes | Shared bytes | Shared saving/binary32, % [95% CI] | Seconds: binary32/shared complete | |
|---|---|---|---|---|---|
| NFCorpus | 1 | 664 | 586 | 61.95 [51.82,68.57] | 0.00430/0.89457 |
| NFCorpus | 3 | 706 | 670 | 56.49 [47.14,62.73] | 0.00409/1.05065 |
| SciFact | 1 | 478 | 442 | 71.30 [68.96,73.25] | 0.00406/0.59566 |
| SciFact | 3 | 760 | 640 | 58.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 () 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/query | Attempted bits | Certified bits/bytes | Meaning |
|---|---|---|---|
| NFCorpus/PLAIN-1772 | 8,10,12 | 12/580 | Midpoint/reference agree; old 8-bit query witness replays; 12 bits retains reference. |
| NFCorpus/PLAIN-1214 | 8,10,12,14,16 | 16/772 | Old midpoint/reference differ; reference retained. |
| SciFact/130 | 8,10,12 | 12/580 | Midpoint/reference agree; old 8-bit query witness replays; 12 bits retains reference. |
| SciFact/312 | 8,10 | 10/484 | Reference 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.
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), 1≤ξ≤5/4, t1,t2∈[−1,2], ∣t1−t2∣≤1/4. Candidates p,q cannot both normalize to interior values: the others would need span ≥1, violating their bound. Scores: p is 0 on [1/8,3/8), else 1; q is 1/2 on [5/8,7/8), else −1; others −2. When p scores 0, q normalizes to 1 and scores −1. Thus p wins despite its marginal minimum below q's maximum.
W2 — Explain applications, prevalence and top-k 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}, indexes minj∈[m]rj, maxj∈[m]rj and contrast extrema, and maps constant raw vectors to zero (pp. 2–3). Introduction minimum μ avoids candidate-index collisions.
W4 — Define contrasts, bounds and Qij.**
Before geometry, Section 2/Table 1 defines r∈Rm, c(i)=(ri−rj)j∈[m], raw zone P(B), bounds (−Bji)j∈[m], (Bij)j∈[m]. Joint image Qij={(zi(r),zj(r)):r∈P(B)} contains attainable normalized features, distinct from scores Fi(zi) (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) frontier pieces despite m(m−1) roles. Construction is O(m2) after closure; matching lower bound concerns size, not optimal runtime. A changed top-k 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.