acceptodds
Under review as a conference paper at ICLR 2027

Anytime-Valid Distribution Shift Detection via Predictive Rank Martingales

Abstract

Many sequential distribution shift detectors update a growing reference set with incoming observations. After a change, this update contaminates the reference set with post-change observations and can weaken subsequent evidence. Keeping the calibration sample fixed mitigates this contamination, but repeated reuse induces dependence among fixed-reference ranks, so arguments based on independent conformal p-values do not apply. We derive the exact conditional null distribution of the next rank given the preceding ranks and use it to construct a predictive rank martingale (PRM). Thresholding a PRM gives distribution-free, finite-sample anytime marginal type I error control. To target specific departures, we apply a pre-specified feature to each rank, center the resulting payoff under the predictive null law, and use Online Newton Step (ONS) to adapt the bet. Order and dispersion features target directional and center-versus-tail changes, respectively. For any Lipschitz feature with nonzero induced contrast under the alternative, we establish a finite-window detection guarantee and show that the test is consistent as the initial calibration size increases. At a fixed calibration size, however, we derive a power ceiling for every distribution-free detection procedure. Across synthetic and real data, our PRM methods achieve better detection performance than conditional conformal test martingale (CCTM).

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
Distribution shift detection, Anytime-valid inference, Conformal test martingales, Sequential hypothesis testing

Reviews

Among:
Shape:
1234this paper, Top 32%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.50 over 4 reviews, above 68% of the others.
Reviewer_8zvjOpenReview ↗
Rating
2(+1)
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper proposes predictive rank martingales for sequential detection problem, using a fixed calibration sample. The paper derives thte conditional null distribution of ranks, and constructs testing-by-betting procedures that is anytime-valid and control false alarm risk. The paper also shows detection guarantees and fixed-calibration power limits. Experiments are conducted on synthetic dataset and CIFAR-10C.

Critical strengths
  • The paper presents a predictive-rank construction with finite sample to achieve anytime-valid change detection.
  • The paper sheds light on the limitations that is imposed by a finite calibration sample.
Critical weaknesses

Note that the following represents my initial impression of the paper, and I am open to discussion. I welcome any corrections to my potential misunderstandings.

Critical presentation issue

I found the abstract and introduction unusually difficult to follow. The introduction moves into specialized methodological comparisons before adequately explaining what is the established problems, what is the challenge, who else are suffering from it, and why do we have to care. The opening of Introduction states a classical change detection problem to control error, but it does not tell what is new about the task (at this point, I thought the task is quickest changepoint detection. Only afterwards I realized that there is restriction like unknown distribution, different from the classic QCD).

The second and third paragraphs of Intoduction introduces technical terms in rapid succession. In hindsight after reading the paper fully, I noitce that the authors identify reference contaminatino and dependence from calibration reuses as challenges, but at a first glance these challenges are explained through a comparison between existing techniques, requiring readers to already understand the methodological distinction, whose importance the introduction should establish.

The introduction bluntly ends without clear insights that readers should take home. The contribution list follows, but their significance is not brought forward effectively. Thus, the paper including Introduction needs substantial restructuring around the established problem, unresolved obstacle, proposed insight, and results.

Limited novelty and insufficient experimental support

The paper's contribution is narrower than the collection of method names and guarantees initially suggests. Shaer et al. 2026 already study fixed-reference distribution shift monitoring, identify the calibration reusing problem, use adaptive ONS betting, and provide stopping time guarantees. Thus, keeping reference fixed, using an order-based score and adapting bets carry limited novelty.

The novelty resides in the predictive null law of the reused reference, but the derivations relies on classical uniform spacing and Dirichlet-conjugacy arguments, if I understand correctly. The paper therefore needs to establish more clearly what practical or theoretical capability it adds.

A further limitation is the strong i.i.d. assumption. Real-world time series data are rarely independent stream, so the proposed approach has a substantial practical limitation. If I understand correctly, temporally dependent stream does not necessarily have to obey the proposed predictive rank law: the anytime false-alarm guarantee does not automatically extend to real-world settings.

The experimental evaluation is also limited. The synthetic experiments reflect the directional and dispersion features being studied. A dispersion sensitive, confidence band-corrected baseline is needed to isolate the benefit of predictive centering. The CIFAR with one pretrained ResNet is also restrictive: they are tested on corrupted monitoring stream shifted from its first observation. Together with the i.i.d. assumption issue, the paper does not fully showcase it's effectiveness and practical relevance.

Questions for authors

Please provide point-by-point to my concerns above.

Reviewer_MayFOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies sequential testing of whether incoming observations have the same distribution as a fixed reference sample. Reusing this sample makes the ranks of successive observations dependent. The authors derive their exact conditional distribution under the null: if Nt−1,jN_{t-1,j} previous observations have rank jj relative to a reference sample of size nn, then the next observation has that rank with probability (1+Nt−1,j)/(n+t)(1+N_{t-1,j})/(n+t). This identity allows the construction of nonnegative martingales and hence tests whose probability of ever falsely rejecting is at most α\alpha, averaged over both the reference sample and the incoming observations.

The proposed tests apply a fixed function to each rank, subtract its conditional null expectation, and adaptively choose a betting coefficient. The paper considers functions sensitive to location and dispersion changes, as well as an average of the resulting martingales. It proves finite-sample detection bounds and consistency as the reference sample grows, provided the chosen function has a nonzero expectation under the alternative on the population quantile scale. It also establishes limitations on the power of any distribution-free procedure with a fixed reference sample. The authors' experiments on synthetic shifts and classifier outputs from CIFAR-10-C show faster detection than the two conformal testing baselines considered.

Critical strengths
  1. The paper gives a simple and exact solution to the dependence introduced by reusing a reference sample. This matters because treating the resulting ranks as independent would invalidate the usual martingale argument, while controlling reference-sample estimation error through a uniform confidence band can be conservative. The conditional rank distribution provides a direct construction with finite-sample false-alarm control over an unlimited monitoring horizon, including distributions with ties through randomized tie-breaking.
  2. The paper explains both when detection is possible and why unlimited monitoring cannot generally compensate for a small reference sample. The finite-window guarantee connects detection time to the expectation of the chosen rank function under the alternative. The complementary impossibility results distinguish limitations of the proposed algorithm from limitations of the statistical problem itself. In particular, comparing the alternative with the null under which all observations follow the stream distribution gives a useful explanation of why power can remain below one even with infinitely many incoming observations.
Critical weaknesses
  1. The experimental comparisons do not fully separate the benefit of the conditional rank construction from the choice of statistic and betting rule. In the symmetric-shift experiments, the proposed dispersion statistic has a nonzero population signal, whereas the baselines use a directional statistic whose population signal is zero. These results demonstrate the importance of choosing an appropriate statistic, but provide less evidence for the advantage of the new construction itself. Appendix C.1 also specifies different betting ranges and updates across methods. The location-shift results are more informative, but a comparison with matched betting choices would make the source of the improvement clearer.
  2. The theory leaves a substantial gap between the universal power limitation and the performance of the proposed procedure at a fixed reference-sample size. Theorem 8 bounds the power of every valid procedure, whereas Theorem 4 guarantees high power when the reference sample is sufficiently large. These results do not establish how close the proposed method comes to the attainable power at a given reference size. This is particularly relevant because the strongest practical motivation and some of the largest empirical gains concern small reference samples.
Questions for authors
  1. To clarify the experimental comparison, how much of the location-shift advantage remains when the methods use comparable betting ranges and adaptation rules? Appendix C.1 appears to use a more restricted betting range for the standard conformal baseline than for the proposed method.
  2. As an additional comparison, can the standard conformal martingale be run with a statistic sensitive to dispersion, such as a centered function of ∣2p−1∣\lvert 2p-1 \rvert? Its performance on the symmetric alternatives would help distinguish the contribution of the statistic from that of the fixed-reference construction.
  3. For Gaussian location shifts, how close is the proposed method’s eventual detection probability to the explicit upper bound in Remark 9, particularly for small reference samples and weak shifts? A numerical comparison over a sufficiently long horizon would help assess whether the remaining loss of power is largely unavoidable or specific to the proposed procedure.
Reviewer_RrnmOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3(+1)
Read review
Paper summary

The paper studies anytime-valid distribution shift detection using ranks relative to a fixed calibration set. It combines a Pólya predictive law with feature-based betting and Online Newton Step, and develops detection guarantees and fixed-calibration power limitations. Experiments on synthetic shifts and CIFAR-10-C report favorable detection performance.

Critical strengths

Theorem 8 and Remark 9 provide an informative characterization of the limitations imposed by a fixed calibration set, even with unlimited monitoring.

The construction clearly separates validity from feature choice, and the portfolio offers a simple way to combine detection directions while preserving validity.

Figure 4 provides substantial empirical support for type I error control under the studied null, with PRM rejection probabilities close to the nominal level.

Critical weaknesses
  1. The contribution beyond existing predictive rank results needs clarification.

Gazin, Blanchard, and Roquain, Transductive conformal inference with adaptive scores (AISTATS 2024), already provide the corresponding sequential Pólya predictive formula in Theorem A.1(i), Equation (27). This work is not cited. Since the exact predictive law is emphasized as a key contribution, its relationship to Theorem 1 materially affects my assessment of novelty. Please clarify which results are inherited from this characterization and which constitute the paper’s new contributions.

  1. The empirical comparison does not fully isolate the benefit of the proposed construction.

PRM and Standard CTM use different betting bounds, online update settings, and clipping rules (§2.5 and Appendix C.1). Consequently, it is unclear how much of the observed improvement comes from predictive centering rather than these configuration choices. A controlled comparison with matched betting configurations in a representative setting would help resolve this concern.

Questions for authors

No specific questions.

Reviewer_4gjcOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies sequential distribution-shift detection by comparing an online stream with a fixed calibration sample. Under the null, both are i.i.d. from the same unknown distribution. The proposed Predictive Rank Martingale (PRM) uses the conditional null law of each new rank to account for dependence caused by repeated use of the calibration sample.

PRM centers a chosen rank feature by its predictive null mean and updates a betting wealth process using predictable coefficients. The resulting nonnegative martingale provides distribution-free, finite-sample anytime false-alarm control:

sup⁡PPr⁡H0(P)(sup⁡t≥1Mt≥1/α)≤α.\textstyle \sup_P \Pr_{H_0(P)}\left(\sup_{t\ge1} M_t \ge 1/\alpha\right) \le \alpha.

This guarantee is marginal over the calibration sample and the online stream. Online Newton Step adapts the bets. Order and dispersion features target different changes and can be combined through a wealth mixture.

The analysis establishes finite-window detection guarantees for Lipschitz features with nonzero population contrast, subject to sufficient calibration data, and extends them to delayed changes. It also gives consistency as the calibration size grows and characterizes limits on attainable power with a fixed reference sample. Experiments on synthetic shifts and CIFAR-10-C compare detection performance with CTM/CCTM baselines and illustrate the effect of feature choice.

Critical strengths

1. Useful detection guarantees that account for dependence.

Section 3.1 (Theorem 4) and Appendix A.11 (Theorem 12) provide finite-sample detection bounds under nonzero feature contrast and sufficient calibration size. The analysis accounts for how an observed rank changes later predictive centers and how the ONS state accumulated before a change affects detection. These results connect calibration size, signal strength, and detection delay, providing meaningful additional analysis beyond the null-validity construction.

2. A useful alternative to the calibration correction used by the closest method.

The closest method, CCTM by Shaer et al. (2026) [1], bets on the fixed-reference empirical CDF and uses a uniform DKW confidence band to account for calibration uncertainty, yielding PAC calibration-conditional control. PRM instead centers its payoff using the exact distribution of the next rank given past ranks and constructs a nonnegative martingale. This gives distribution-free, finite-sample anytime marginal type-I error control, jointly over the random reference sample and stream, without a confidence-band correction or separate calibration-failure parameter in the validity construction (Introduction; Theorem 1; Proposition 2).

3. Clear analysis of the information limits imposed by fixed calibration.

Theorem 8 gives a power ceiling that applies to every distribution-free procedure satisfying the stated marginal validity requirement. Its Gaussian example in Remark 9 shows that eventual detection probability can remain strictly below one even with an unlimited online stream. This identifies a limitation shared by all such detectors and explains why the paper studies consistency as calibration size increases. Theorem 7 and Appendix B also clarify the different implications of exact conditional, PAC conditional, and marginal validity.

4. Faster detection across the reported location-shift benchmarks.

Section 4.1 reports that under the reported parameter settings, Order PRM reaches 80% detection using 10.2%-23.1% fewer observations than CCTM across all nine immediate, delayed, and gradual location-shift settings. These comparisons use closely related order-sensitive statistics. Section 5 also shows gains with limited calibration data: with 50 reference observations, Order PRM reaches 80% detection after 20 observations, compared with 94 for CCTM and 40 for Standard CTM. Appendix C.5 extends the evaluation to larger calibration samples.

5. Clear feature choices for detecting different types of change.

Section 2.3 gives a concrete reason for including a dispersion feature: Gaussian scale changes have zero order contrast but nonzero dispersion contrast. Section 2.6 then combines the order and dispersion tests while preserving anytime validity, with at most log 2 loss in log wealth relative to the better component. This provides a simple way to cover both types of change. The strength is the useful implementation of classical rank features and standard martingale mixtures.

Reference

[1] Shalev Shaer, Yarin Bar, Drew Prinster, and Yaniv Romano. "Testing For Distribution Shifts with Conditional Conformal Test Martingales." ICML 2026. https://proceedings.mlr.press/v306/shaer26a.html

Critical weaknesses

1. The central predictive identity has an exact overlap with an existing work that is not cited.

The first contribution includes the predictive law in Theorem 1, Equation (1). However, Gazin, Blanchard, and Roquain [1] already give the corresponding identity in Theorem A.1(i), Equation (27), under exchangeability and absence of ties.

Their conformal p-values are defined by

pt=1+∑i=1n1Si≥Sn+tn+1.\textstyle p_t = \frac{1+\sum_{i=1}^{n}\mathbf{1}\\{S_i\ge S_{n+t}\\}}{n+1}.

Taking the reference scores to be the negatives of the calibration observations and the test scores to be the negatives of the stream observations gives

Si=−Yi,Sn+t=−Xt,pt=Rtn+1.\textstyle S_i=-Y_i, \qquad S_{n+t}=-X_t, \qquad p_t=\frac{R_t}{n+1}.

Their Equation (27) states

=\frac{1+\sum_{k=1}^{i}\mathbf{1}\\{p_k=j/(n+1)\\}}{n+1+i}.$$ Substituting i = t - 1 yields exactly the paper's identity: $$\textstyle \Pr(R_t=j\mid\mathcal G_{t-1}) =\frac{1+N_{t-1,j}}{n+t}.$$ The rescaling preserves the history filtration. Moreover, the earlier theorem explicitly states that the transition law is independent of the batch size. For the fixed-score specialization above, it therefore applies to every finite prefix of the stream. This exact predecessor is absent from the paper's related work and bibliography, although classical Pólya-urn results are cited around the same section. The omission substantially affects the assessment of the first contribution for this paper: the continuous-null predictive identity is already established. **2. Once the predictive law is available, the validity construction and betting strategy provide only a limited independent algorithmic novelty.** The martingale part of Theorem 1 follows directly from the known conditional probabilities. For any predictable probability vector, the proposed factor satisfies $$\textstyle \mathbb E_0\bigg[\frac{q_{t,R_t}}{\pi_{t,R_t}}\\,\bigg|\\,\mathcal G_{t-1}\bigg] =\sum_{j=1}^{n+1}\pi_{t,j}\frac{q_{t,j}}{\pi_{t,j}} =1.$$ Non-negativity and Ville's inequality then give the anytime false-alarm guarantee. This is a valid construction, but the jump from the predictive law to a test martingale looks to me like a very standard conditional-expectation argument. The feature-based version likewise subtracts the predictable null mean: $$\textstyle a_j=h\big(\frac{j-1}{n}\big), \qquad Z_t=a_{R_t}-\sum_j\pi_{t,j}a_j.$$ Consequently, predictable admissible bets give $$\textstyle \mathbb E_0[1+\lambda_t Z_t\mid\mathcal G_{t-1}]=1.$$ This centering-and-betting principle has an explicit overlap with preceding works. Waudby-Smith and Ramdas [2], Section 5.2, Equations (32)-(34), construct linear betting products centered by a time-varying conditional null mean. Shekhar and Ramdas [3], Definition 5, already use projected ONS updates based on the log-wealth gradient and accumulated squared gradients. CCTM [4] also uses ONS in the fixed-reference monitoring setting itself. The earlier betting papers use different observation schemes, so these comparisons do not establish that the complete PRM detector already exists. They do establish that much of the construction following the predictive identity is an application of existing machinery. This and along with Weakness 1 mentioned, makes the method seem like a special case and combination of established ideas. One can make the case for a substantial contribution only when we consider the additional detection analysis and the practical benefit of this particular combination. **3. CCTM can also attain marginal anytime validity after recalibration.** In the shared continuous-null setting, CCTM by Shaer et al. [4] can be retuned to achieve a prescribed marginal anytime false-alarm level by adjusting its testing level and calibration-failure probability. The submission itself explains this conversion in Appendix B.1. Thus, marginal anytime validity is already attainable through the closest prior method. PRM obtains this guarantee through a direct predictive-rank martingale, avoiding CCTM's confidence-band correction and separate calibration-failure parameter. This distinction can be useful, since recalibrating CCTM may reduce detection performance. However, the marginal guarantee itself provides limited additional novelty over CCTM. The significance of the advance therefore depends on the additional analysis and the practical benefits of this construction. **4. The symmetric-shift comparisons do not isolate the benefit of predictive centering.** Section 4.2 considers alternatives with zero order contrast but nonzero dispersion contrast. The comparison between Order PRM and Dispersion PRM appropriately demonstrates the benefit of choosing a feature that responds to these changes. However, the comparison of Dispersion PRM and its portfolio against order-sensitive CTM/CCTM baselines changes both the feature and the treatment of calibration uncertainty. It therefore provides limited evidence about the additional benefit of predictive centering when the monitored feature is held fixed. A comparison with a valid dispersion-feature CTM baseline, and a suitably adapted CCTM baseline with the required calibration correction, would clarify how much improvement comes from PRM's construction. This concern is specific to interpreting the symmetric-shift gains; the order-feature comparisons on location shifts remain useful evidence. **References** [1] Ulysse Gazin, Gilles Blanchard, and Etienne Roquain. "Transductive conformal inference with adaptive scores." AISTATS 2024. See Equation (1), Section 2.1, and Theorem A.1(i), Equation (27). https://proceedings.mlr.press/v238/gazin24a/gazin24a.pdf [2] Ian Waudby-Smith and Aaditya Ramdas. "Estimating means of bounded random variables by betting." See Section 5.2, Equations (32)-(34), and Appendices B.5-B.6. https://arxiv.org/abs/2010.09686 [3] Shubhanshu Shekhar and Aaditya Ramdas. "Nonparametric Two-Sample Testing by Betting." See Section 2.1 and Definition 5. https://arxiv.org/abs/2112.09162 [4] Shalev Shaer, Yarin Bar, Drew Prinster, and Yaniv Romano. "Testing For Distribution Shifts with Conditional Conformal Test Martingales." ICML 2026. See Sections 3.1-3.3 and Algorithms 1-2. https://proceedings.mlr.press/v306/shaer26a.html
Questions for authors

The following questions focus on the issues that could materially change my assessment. My main uncertainty concerns the size of the contribution beyond the existing predictive law and betting machinery, and how clearly the evidence establishes the benefits of the proposed construction.

  1. Could you clarify the relationship to the existing predictive rank law and identify the precise novelty of the construction?

Gazin, Blanchard, and Roquain [1], Theorem A.1(i), Equation (27), provide the same conditional predictive probabilities as your Equation (1) under the continuous null. Taking the negatives of the observations as their scores gives

p_t=\frac{R_t}{n+1}, \qquad \sigma(p_1,\ldots,p_{t-1})=\mathcal G_{t-1}.$$ Their transition law is also explicitly independent of the batch size, so the fixed-score specialization applies to every finite prefix of the stream. This reference does not appear in the submitted version. Could you explicitly discuss this equivalence and clarify which parts of Theorem 1 and the monitoring construction are claimed as new? 2. **Additional theoretical contribution relative to CCTM.** Please compare Theorem 4 and the delayed-change extension with CCTM's Theorem 3.3 (Shaer et al. [2]), specifying differences in assumptions, calibration requirements, error criteria, and detection conclusions. Please account for CCTM's marginal-level recalibration discussed in Appendix B.1 and identify the main steps that go beyond existing betting and ONS arguments provided. 3. **Separating feature choice from predictive centering.** The within-PRM comparison already demonstrates the benefit of the dispersion feature. Can you provide a comparison with valid CTM/CCTM variants using the same feature, comparable betting updates, and a common marginal false-alarm target, to clarify the additional benefit of predictive centering? I am open to improving my score if the response establishes a substantial contribution beyond the existing predictive law and provides convincing support for the claimed advantages over the closest prior work. **References** [1] Ulysse Gazin, Gilles Blanchard, and Etienne Roquain. "Transductive conformal inference with adaptive scores." AISTATS 2024. See Theorem A.1(i), Equation (27). https://proceedings.mlr.press/v238/gazin24a/gazin24a.pdf [2] Shalev Shaer, Yarin Bar, Drew Prinster, and Yaniv Romano. "Testing For Distribution Shifts with Conditional Conformal Test Martingales." ICML 2026. See Sections 3.1-3.3 and Theorem 3.3. https://proceedings.mlr.press/v306/shaer26a.html

Comments on the paper

1 comment

Dear Area Chair and Reviewers,

We have uploaded the revised manuscript. The tables below summarize the changes made in response to each reviewer. Comment numbers follow our earlier replies. All locations refer to the revised manuscript.

Reviewer 4gjc

CommentTypeChangeWhere
Q1ClarificationCited Gazin et al. and clarified our contributionsSecs. 1, 2.2; App. A.1
Q2DiscussionCompared assumptions, error control and detection guarantees with CCTMReply only
Q3New experimentCompared dispersion CTM/CCTM under both betting updates, including marginally recalibrated CCTMSec. 4.2; Apps. C.2, D.2, Tables 15–23

Reviewer Rrnm

CommentTypeChangeWhere
Q1ClarificationExplained the connection to Gazin et al. and what our work addsSecs. 1, 2.2; App. A.1
Q2New experimentCompared betting updates across calibration sizes on synthetic and real dataSec. 4.1; App. D.1, Tables 4–14

Reviewer MayF

CommentTypeChangeWhere
Q1Clarification, new experimentClarified baseline defaults and compared betting updatesApps. C.1–C.2, D.1, Tables 4–14
Q2New experimentAdded CTM/CCTM comparisons using the same dispersion featureSec. 4.2; Apps. C.2, D.2, Tables 15–23
Q3New experimentCompared long-horizon power with the Gaussian upper bound for small calibration samplesApp. D.4, Table 26

Reviewer 8zvj

CommentTypeChangeWhere
Q1PresentationRewrote the explanation of the problem, challenges, main idea and resultsAbstract, Sec. 1
Q2ClarificationClarified prior work and our contributionsSecs. 1, 2.2; App. A.1
Q3ClarificationExplained the assumptions and limits for dependent dataSecs. 2.1, 6
Q4New experimentAdded dispersion CTM/CCTM baselines and comparisonsSec. 4.2, Figures 2–4; Apps. C.2, D.2, Tables 15–23
Q5New experimentAdded a second network, delayed and gradual shifts, and two sampling designsSec. 5; App. D.3, Tables 24–25

The PRM construction and main theoretical guarantees remain unchanged. The revision adds experimental comparisons, clarifies the connection to prior work, and improves the presentation.

Thank you for your time and feedback,

The authors

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.