PaperlayerView exact revision on arXiv

Source-linked AI summary

Pay Only for Disagreement: Certified No-Regression Verdicts for Model Updates with Matching Label-Complexity Bounds

Vishnu Bindu Balachandran

arXiv:2609.17560v1cs.LGcs.AIcs.CVstat.ML

TL;DR

Production updates can silently worsen deployed models, creating a need for certified promotion decisions that remain valid under sequential monitoring. DISCERN exploits observable disagreement for zero-label or disagreement-only auditing, with matching label-complexity bounds and strong empirical validation.

  • Problem

    Production model updates can silently be worse than the models they replace, but promotion requires certified paired risk-difference decisions on live traffic under sequential stopping.

  • Method

    DISCERN uses a zero-label disagreement-rate certificate and an audited tier that labels sampled disagreements with anytime-valid confidence sequences.

  • Results

    0.0002 miscoverage and 0.986 power with zero false alarms were observed across 6,890 replayed streams and 70 real LoRA update pairs.

  • Takeaways & Limitations

    Matching bounds show that exploiting disagreement can reduce label complexity by a factor of rho relative to pairing-blind auditing while preserving certified promotion decisions.

  • Takeaways & Limitations

    The main guarantees exclude losses that read model internals or judged outputs, while open-ended judged generation and preference-tuned updates remain outside the theory.

Abstract

from arXiv · show

Every production model is updated, by retraining, fine-tuning, quantization, or a silent vendor swap, and each update risks being worse than what it replaced. We formalize update promotion as certified paired risk-difference auditing. Our starting point is a support identity: the risk difference between two models lives on the inputs where they disagree, observable without labels. We build DISCERN, a sequential two-tier protocol. A zero-label tier certifies benign updates whose disagreement rate is below tolerance from unlabeled traffic alone. An audited tier labels only sampled disagreements through an anytime-valid confidence sequence, valid at every stopping time and under any label-routing rule, even an adversarial judge. We prove finite-sample validity and matching label-complexity bounds of order rho^2/eps^2 at the rate level, so exploiting free disagreement provably saves a factor 1/rho over any pairing-blind auditor, and the guarantee composes across an unbounded sequence of promotions from one error budget. Across 14,000+ replayed audit streams over 785 update pairs, including LoRA fine-tunes of language models up to 1.4B parameters, miscoverage is 0.0002 (nominal 5%), power 0.986 with zero false alarms, and 56% of benign updates certify with zero labels. Each audit emits a machine-checkable evidence record for post-market monitoring.

1 Introduction

Production model updates can silently regress, so the paper formalizes promotion as certified paired risk-difference auditing. DISCERN exploits observable disagreement to reduce labeling while providing sequential validity, complexity guarantees, and machine-checkable evidence.

  • Motivation: Labels are unnecessary on agreements because they contribute exactly zero to the paired risk difference, while production updates agree on 80% to 99.9% of traffic.This support structure motivates monitoring disagreement for free and labeling only disagreements.
  • Motivation: The paper frames promotion as deciding whether a candidate update’s paired risk difference is below tolerance or represents a regression.The audit must operate on live traffic, tolerate continuous peeking and data-dependent stopping, and minimize human labels.
  • Contributions: DISCERN uses a zero-label disagreement certificate and an audited tier that samples only disagreements under anytime-valid confidence sequences.The protocol supports paired, per-slice, and family-wise sound verdicts across a sequence of promotions.
  • Theory: The label complexity is order rho^2/epsilon^2 up to logarithmic factors, matching a lower bound and improving over pairing-blind auditing by a factor of rho.The result characterizes the value of observing the disagreement signal rather than labeling traffic uniformly.
  • Empirical validation: Across 6,890 replayed streams and 70 real LoRA update pairs, miscoverage was 0.0002, power was 0.986 with zero false alarms, and label spend followed theory with R2 = 0.999.The evaluation covered 715 feature-space pairs, four modalities, eleven update types, and a held-out confirmation family.
  • Operational impact: Each promotion produces machine-checkable evidence containing the tolerance, confidence, verdict, label spend, stopping time, and per-slice outcomes.The record is intended to support traceable post-market monitoring and system-change evidence.

2 Related Work

Prior work provides paired comparison, anytime-valid inference, label-efficient evaluation, and update-monitoring tools, but not their combination for certified update promotion. DISCERN differs by certifying a fixed paired risk difference with disagreement-dependent sequential label complexity.

  • Paired comparison and update approval: Earlier paired-comparison methods use discordant pairs or instrumental sampling, but typically rely on fixed horizons or asymptotic guarantees rather than deployment-time anytime validity.DISCERN adds sequential certification for each promotion and composition across promotion sequences.
  • Positioning: The paper’s contribution is the combination of zero-label certification, anytime-valid guarantees, optimal label-cost characterization, and promotion-level soundness.These properties distinguish it from concurrent or adjacent sequential model-comparison approaches.
  • Label-efficient evaluation: Single-model active-testing and prediction-powered methods reduce labels for other estimands but do not target certified anytime-valid promotion verdicts or provide matching label-complexity lower bounds.The paired difference is supported by an observable disagreement signal, changing the relevant complexity theory.
  • Disagreement-based active learning: Unlike disagreement-based active learning, DISCERN holds two fixed models and estimates a scalar paired risk difference rather than learning a classifier or shrinking a version space.Its disagreement rate rho is observable and fixed, while epsilon bounds a risk difference rather than excess classification error.
  • Update monitoring: Update-churn and backward-compatibility work measures or reduces disagreement, whereas this paper completes the pipeline by certifying whether disagreement harms the update.This connects operational update monitoring to a certified paired decision.

3 Setting and the Support Identity

The setting compares an incumbent and candidate through their paired loss difference on an i.i.d. stream. Under prediction-determined losses, disagreement supports the entire estimand, yielding a zero-label bound and a principled target for selective labeling.

  • Setting: The paired risk difference is the candidate loss minus incumbent loss, with positive values denoting regression and nonpositive values denoting no worse performance.The audit issues safe or regression verdicts at tolerance epsilon and confidence 1 minus delta.
  • Assumption: Prediction-determined losses make the paired difference exactly zero whenever the models agree on a prediction.This assumption covers standard supervised losses but excludes losses consulting model internals, judged outputs, or preference objectives.
  • Support identity: The support identity is Delta = E[D_t A_t] with |Delta| <= B rho, where A_t marks model disagreement and rho is its observable rate.The sharper rate rho_1 can replace rho for variance-related bounds when disagreements do not change the loss.
  • Consequences: If unlabeled monitoring establishes rho <= epsilon/B, then the risk difference is bounded within tolerance without requesting labels.This is the basis for the zero-label tier and its strict Safe(epsilon) verdict.

4 The Discern Protocol

DISCERN is a two-tier sequential audit: it first seeks a zero-label certificate from unlabeled disagreement monitoring, then labels only disagreements when that certificate cannot fire. Confidence sequences preserve validity under continuous stopping, predictable routing, adversarial judges, and simultaneous slice verdicts.

  • 4.1 Tier 0, the zero-label certificate: Tier 0 maintains a confidence sequence for the disagreement rate and certifies Safe(epsilon) when its upper bound satisfies B rho_t < epsilon.It requests zero labels and fires after O(unlabeled points) when rho <= epsilon/(2B).
  • 4.2 Tier 1, auditing the disagreement region: When Tier 0 cannot fire, DISCERN requests labels only on disagreements using a predictable routing probability bounded below by pi_min.The routing rule may use prior observations, side information, or judge scores, but must not consult the incoming label.
  • 4.2 Tier 1, auditing the disagreement region: Importance-weighted increments and an empirical-Bernstein confidence sequence yield an anytime-valid estimate of the paired risk difference.Combining the two confidence sequences with delta_0 + delta_1 = delta gives an (epsilon, delta)-sound procedure.
  • 4.2 Tier 1, auditing the disagreement region: A stale, biased, or adversarial judge can waste labels but cannot invalidate coverage when routing remains predictable and respects the label-independent floor.The guarantee depends on the routing condition, not on judge quality.
  • Per-slice verdicts: Per-slice confidence sequences with a union allocation provide simultaneous verdicts such as safe overall but regressing on a localized slice.The protocol also trades shadow-scoring compute for reduced human labeling.

5 Theory

DISCERN provides anytime-valid, two-tier certification for model updates, combining zero-label disagreement screening with audited confidence sequences and matching lower bounds. Its guarantees remain valid under adaptive routing, compose across promotion sequences, and extend softly to some score-reading losses.

  • 5 Theory: Theorem 4 guarantees no false Safe or Regression verdict at any stopping time, while Theorem 5 preserves coverage under every predictable routing rule, including an adversarial judge.The guarantee holds jointly for disagreement-rate and risk-difference confidence sequences with probability at least 1 −(δ0 + δ1).
  • 5.2 Label-complexity upper bounds: Theorem 7 certifies ε-benign updates and detects updates with ∆≥2ε using disagreement-focused labeling and anytime-valid confidence sequences.The same bounds apply symmetrically to Regression verdicts, with ε replaced by ∆.
  • 5.2 Label-complexity upper bounds: Total audited-tier label cost is eO(B2ρ2Lδ/ε2), while updates with Bρ ≤ε/2 receive certification after unlabeled monitoring with zero labels.The audited tier is invoked only where the quadratic term is active; Tier 0 removes the low-disagreement regime.
  • 5.3 Matching label-complexity lower bounds: The audited regime has matching label complexity eΘ(ρ2/ε2), whereas the low-disagreement Tier-0 regime requires zero labels; the intermediate window has constant rate.The matching characterization holds up to logarithmic factors.
  • 5.3 Matching label-complexity lower bounds: Pairing-aware auditing saves a factor Θ(1/ρ) over pairing-blind auditing because observing agreement on unlabeled traffic enables labeling only disagreements.At small disagreement rates, the resulting savings can exceed 1000× on real update pairs.
  • 5.5 Sequences of promotions: A single error budget can cover an unbounded promotion sequence, with δ(k) proportional to k−2 and only logarithmic growth in the cost of later audits.This family-wise guarantee prevents any regressing update from ever being certified Safe except with probability δseq.
  • 5.6 Beyond prediction-determined losses: The hard support identity applies only to prediction-determined losses; Lipschitz score-reading losses receive a soft extension, while matching soft-regime lower bounds and judged generation remain open.The extension replaces the disagreement rate with soft-disagreement moments such as E[ηt] and E[ηt^2].
  • 5.7 Beyond stationarity: Under distribution shift, the fixed risk difference ∆ is not identifiable as a stationary target, so the confidence sequence instead covers a running weighted average of conditional means.The paper explicitly distinguishes this valid shifted target from certifying a fixed ∆.

6 Experiments

Across feature-space and language-model update pairs, DISCERN maintained sound verdicts while substantially reducing labeling, with zero-label certification handling many benign updates. Its validity, power, drift handling, and label-efficiency results matched the protocol’s intended operating regimes.

  • 6.2 Validity, power, and false alarms: 0.0002 empirical miscoverage and 0.986 power with zero false alarms were achieved across the main validation battery, with the held-out confirmation reproducing every number.The main battery covered 4,290 streams; injected regressions had Δ≥2% and were evaluated within 5,000 points.
  • 6.3 Label efficiency and the two-tier ledger: 56% of 1,672 benign certifiable audits finished with zero labels, while 98.2% of benign pilot pairs certified within 20,000 unlabeled points at ε = 2%.The zero-label regime covered common updates such as quantization, routine retraining, and hyperparameter changes.
  • 6.3 Label efficiency and the two-tier ledger: 327 median labels versus 2,906 for uniform labeling yielded a seven- to nine-fold saving on audited benign updates, with label spend linear in disagreement rate at R2 = 0.999.Tightening ε from 2% to 1% increased median audited-tier spend from 600 to 1,015 labels on the moderate-ρ band.
  • 6.4 Head-to-head label economics against sequential baselines: 28× lower labeling cost than the active-testing baseline isolated disagreement-supported routing as the source of the audited-band advantage.The baseline used the same judge, Horvitz–Thompson correction, and confidence sequence, while PPI-style labeling was slower than uniform labeling in this paired-difference setting.
  • 6.5 Repairing drift with a windowed confidence sequence: A windowed confidence sequence restored near-nominal calibration under drift, with miscoverage 0.0001 versus 0.063 under smooth drift and 0.065 versus 0.156 under adversarial bursts.The flat confidence sequence remains intended for traffic-averaged verdicts, while the windowed variant targets regime-local alarms.

7 Deployment and Governance Artifact

Each completed audit produces a machine-checkable evidence record that supports retrospective verification and composition across successive model promotions.

  • Each audit records its tolerance, confidence, final intervals, verdict, stopping time, label count, routing trace, and per-slice table.The logged increments allow a third party to recompute the boundary crossing after the audit.

8 Limitations and Scope

The guarantees are scoped to prediction-determined losses and several deployment settings remain outside the paper’s supported or fully developed scope.

  • The support identity applies to losses depending on inputs through predictions, excluding score-reading calibration and preference or reward losses.A soft extension covers Lipschitz score-reading losses, but the standard certified guarantees target the prediction-determined class.
  • The experiments contain no DPO or RLHF update pairs because preference-tuned chat updates require the internals extension.The paper also leaves adaptive budget allocation, optimal slice allocation, and certification against unknown subpopulations open.

9 Conclusion

The paper turns paired model-update auditing into a theory of anytime-valid, disagreement-aware certification with zero-label coverage and matching label-complexity bounds.

  • The theory gives label complexity eΘ(ρ^2/ε^2) up to logarithmic factors and a Θ(ρ) separation from pairing-blind auditing.The separation prices the benefit of running both models on unlabeled traffic before requesting labels.
  • Anytime-valid certificates remain robust to arbitrary predictable label routing, including an adversarial judge, because validity tracks a conditional mean rather than i.i.d. increments.The confidence-sequence construction applies to martingale increments whose conditional mean is the paired risk difference.
  • The audited-tier label count is controlled by the disagreement rate and routing probability rather than by labeling every traffic point.Labels are requested only on sampled disagreements, while a uniform baseline labels the full stream.

B.6 Proof of Theorem 8

The lower-bound construction makes disagreement-only labeling necessary for distinguishing a safe and boundary-regression world, while the campaign’s preregistered gates quantify the protocol’s empirical behavior.

  • The two constructed worlds are observationally identical on unlabeled traffic and differ only in label distributions on the disagreement atom.Labels on agreement points are constant and reveal no information, whereas disagreement labels distinguish the worlds.
  • Sequential change-of-measure forces any sound procedure to collect enough labeled disagreements before safely distinguishing the two worlds.The argument applies to adaptive routing and stopping, with the informative count being the number of labeled disagreement points at stopping.
  • Pairing-blind procedures pay for uninformative agreement labels, whereas uniform labeling achieves a larger label requirement governed by variance scale ρ.The pairing-blind observation law places mass 1−ρ on zero-information outcomes, producing the stated separation.
  • The slice-wise confidence sequences retain simultaneous validity after thinning each stream and applying a union bound across slices.Detection rates are then controlled using the length of each slice’s own stream.
  • The pilot passed all four preregistered gates with 0.21% miscoverage, approximately zero median label ratio, 98.2% zero-label certification, and 100% power with zero false alarms.The gates required at most 7% miscoverage, a median label ratio of at most 0.35, at least half benign pairs certified without labels, and at least 95% power with zero false alarms.

Appendix D. Tolerance Scaling and Censoring

At ε = 0.5%, some moderate-ρ audits exceed the stream cap, so median label spend at that tolerance is censored to certifying audits.

  • 600 labels at ε = 2%, 1,015 at 1%, and 1,012 at 0.5% were the observed median spends for certifying moderate-ρ audits.The 0.5% value is censored because some audits did not certify within the cap.
  • 30,000/40,000/60,000 points cap streams at ε = 2%/1%/0.5%, respectively.
  • The 2%→1% increase matches the range-regime prediction of Lemma 15, while the censored 0.5% cell does not affect the paper’s claims.

Appendix E. Baseline Instantiation Sweep

The baseline sweeps show that importance correction and power tuning do not improve over uniform labeling for this paired estimand, while DISCERN certifies the same cohort with fewer labels.

  • Table 4 evaluates labeling rate and surrogate quality on 29 audited-band pairs with identical streams and tight range 2/q −1.
  • DISCERN certifies the same cohort at a median of 70 labels, whereas no swept prediction-powered configuration beats uniform labeling.
  • The power-tuning sweep uses λ ∈ {0.25, 0.5, 0.75}; no configuration beats uniform, so power tuning does not rescue the prediction-powered family.
  • At q = 1, the prediction-powered correction reconstructs D_t exactly and therefore coincides with uniform labeling.
  • For q < 1, importance correction enlarges the increment range faster than subsampling saves labels, including with an oracle surrogate.

Appendix F. Reproducibility

The reproducibility package makes the experiments CPU-replayable apart from the LoRA fine-tunes and provides scripts, artifacts, records, and protocols for reproducing the reported analyses.

  • The complete pipeline is orchestrated by one resumable script with atomic per-audit artifacts, frozen-gate evaluation, figure generation, and final status reporting.
  • All experiments are CPU-replayable except the LoRA fine-tunes, which use one commodity GPU for about three GPU-hours total.
  • The release includes the audit engine, update-pair builders, 14,233 per-stream records, and one-command reproduction of every table and figure.
  • The preregistration with frozen gates and timestamped amendments, reserved-seed protocol, and full package are available to reviewers and planned for public release.
  • Table 6 provides authoritative accounting of every replayed audit stream across disjoint campaigns, with abstract summaries rounded down to 14,000+.
Loading 2609.17560v1…