acceptodds
Under review as a conference paper at ICLR 2027

Graph-Certified Anytime-Valid Testing: What a Dependency Graph Buys, and What Certification Costs

Abstract

Sequential monitoring of many machine-learning systems requires combining evidence from streams that share observations or sources of randomness. Multiplying evidence as if the streams were independent invalidates the test; dependence-agnostic aggregation preserves validity but discards structure. We study *graph-certified* anytime-valid testing, in which a conditional dependency graph licenses exactly those products of local betting factors that are supported on independent sets, and a predictable learner allocates wealth across them. Our results are two-sided. On the positive side, the achievable log-growth multiplier is the *independence number* , not the chromatic quantity ; the two coincide on vertex-transitive graphs but the gap can be strict off that class, and understates the multiplier by up to on stars and grids in our sweep. On the negative side, a dependency graph is a notion and cannot express weak dependence, so certification has a price: on a corrupted-clique family we compute it in closed form and show it rises from under exact duplication to the full clique size as within-clique dependence vanishes. We give the domination result that actually justifies restricting to independent sets in the bounded-bet regime the algorithm uses, show that a -approximate maximum-weight independent set inflates the expected rejection time by at most , and introduce a balanced certified test that is within of the better of the certified product and the cumulative mean, extending the sparse/dense trade-off known for independent streams to certified dependence. Across null trajectories per graph every valid method stays below while the independence product inflates to –. Finally, on growth rate a graph neural policy is beaten by a strong non-neural policy using the same certificate—on this problem the structure, not the representation learning, carries most of the gain—though the two are competitive on expected detection time, and we report both rather than the more flattering one.

Primary area:
learning theory
Keywords:
anytime-valid inference, e-values, test martingales, sequential testing, dependency graphs, independence number, multiple testing, sequential auditing, graph neural networks, betting

Reviews

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

The paper is about the problem of continuously monitoring multiple machine learning system using one-sided sequential hypothesis testing. At each time, there are observations from each machine learning system from which betting factors (e-values) can be computed and used for evidence against the null hypothesis, which states that every system is working normally. Observations from the different machine learning systems are assumed to follow a given certified dependency graph, representing conditional independence relations. The authors combine evidence against the null in a test supermartingale by multiplying betting factors over independent sets of nodes in the dependency graph. The central research questions is regarding what can be gained from having access to such a dependency graph compared to no dependency information, and what is lost compared to having the full joint distribution over the observations from different systems.

Critical strengths

The problem of continuous monitoring of machine learning systems seem relevant, and sequential hypothesis testing with supermartingales does seem like a principled way of solving the problem, yet in itself is not a novel contribution. Attempting to solve the problem given a dependency graph could be an interesting choice that potentially could result in better monitoring. Theoretical contributions in terms of mathematical theorems I consider as a strength of the paper.

Critical weaknesses

The presentation is poor in several aspects. It lacks explanations of mathematical definitions, terminology and statements, and many central assumptions are not discussed. The abstract and introduction are written for a reader already familiar with the details of the paper, with a fairly incomprehensible list of contributions. There are also instances of statements of the form "it is X, not Y", yet with no clear motivation why one would think it was Y in the first place. As an example, in the abstract and introduction the authors state that the achievable log-growth multiplier is the independency number α(D)\alpha(D), and not the chromatic quantity n/χf(D)n/\chi_f(D). Neither the log-growth multiplier, the independency number, nor the chromatic quantity is defined or discussed; what does these quantities represents? log-growth multiplier of what? Statements of this sort without proper explanation or reference provide very little substance and make the paper extremely hard to read.

Regarding the content of the paper, it lacks a discussion around the assumptions and the applicability to practical settings. The assumption of having a certified dependency graph could be interesting, yet from my understanding it is difficult to obtain reliable dependency graphs and different graph structure modeling approaches may result in vastly different dependency graphs. It might therefore be important to test the robustness against errors in the dependency graph. The authors does acknowledge the issue of an incorrectly specified dependency graph in section 10 on discussion and limitations. However, the paper would benefit from investigating such dependency graph errors experimentally and/or theoretically, especially given that it may be very difficult of obtaining reliable dependency graphs in practice.

It is assumed that there are observations in [−1,1][-1,1] such that larger values provide more evidence against the null, but it is not explained how realistic such observations are. The practical relevance of the results are not so clear from the theory and the paper would benefit from a better discussion on this. Experiments are not done against machine learning systems, which is the supposed domain of interest, but are instead applied to synthetic graphs with a given dependency graph. Even so, the result does not demonstrate that the papers approach give any advantage over other methods. It is therefore highly unclear if the theory has any practical relevance for monitoring of machine learning systems. It may be difficult to obtain such data, although the paper lists some sources of dependencies in real world settings, but the paper would benefit from a discussion regarding this regardless.

Finally, the experiments are to my understanding involving randomness. However, results are mostly reported without any uncertainty quantification, e.g., some kind of error bars to reported numbers, and it is therefore not clear how statistically significant the results are. The authors mention a Monte Carlo standard error for figure 1, but otherwise it seems largely to be omitted. For scientific rigour, this should be included.

Questions for authors

Given the difficulty for me to follow the paper, pinning down the most important questions for improving the paper becomes hard. My questions are as follows:

  1. In both the abstract and the introduction it is stated that "the achievable log-growth multiplier is the independence number α(D)\alpha(D), not the chromatic quantity n/χf(D)n/\chi_f(D)" (without defining either quantity). However, stating that something is X and not Y implies that there should be a clear reason to believe it was Y apriori. Why would one believe naively that it should be n/χf(D)n/\chi_f(D)? In fact, the paper states on line 210-212 that this is not a previously stated growth rate, so it is unclear to me why it is discussed, and the subsequent discussion is not clarifying this. Can the authors clarify this point?
  2. It is assumed that we observe ZtZ_t, a vector with elements in [−1,1][-1,1]. The experiment seem to construct synthetic data for which such vectors can be observed. How can one construct or define such variables for real-world data?
  3. Is the assumption of having a reliable dependency graph justified in some real-world scenarios? How robust is the method to errors or noise in the dependency graph?
  4. Are the experimental results reported statistically significant? For example, for figures 2-4, how many simulations are the results based on? What would the error bars be in terms of, e.g., standard deviation?
Reviewer_wAyVOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper studied the problem called “graph-certified anytime-valid testing”, referred to some previous work in statistics. As I understand it, it aims at validating results from various sources that may change in time, and may be obtained using not necessarily independent randomness. However, I couldn’t fully understand the setting and the solutions.

  1. Several key notation is not explained – the authors assume that the ICLR readers should know what are dependency (D) and representation (R) graphs of the setup, the meaning of P0\mathcal{P}_0, VV, certificate, validity, and many other things. There is no single example, picture, etc.

  2. The setup itself is very narrow and arbitrary – it only states that there are vectors ZtZ_t observable at each time tt, hypothesis H0H_0 that these vectors observe non-positive expected drift at each monitored coordinate, and defines what a predictable learner does, without stating what is the objective of the problem that needs to be solved. What is time-validity? What is graph certification? How randomness is revealed and independence between observed sub-vectors (Z_{v}){v \in A} and (Z{v})_{v \in B} are tested? Are ZvZ_v the same as ZtZ_t defined earlier? If yes, what is the meaning of sets A,BA,B subsets of VV (and what is VV)? If not, why the same notation of ZZ with a sub-index is used in two different meaning, even on the same page (nr 2).

Therefore, the paper in the current form does not merit acceptance for ICLR’27.

Critical strengths

None.

Critical weaknesses

The paper is not formalized enough to be able to understand and evaluate theoretical results.

Questions for authors

I think the paper should be carefully revised, all terms defined mathematically, including the formalism of the measurement process and the problem's objectives. See my questions in the summary as examples (but they do not cover all ambiguities in the paper).

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

The paper proposes a graph-based anytime analysis where essentially a dependency graph is constructed across streams and is used to aggregate evidence. The paper proposes using independent sets over a suitably defined dependency graph and analyzes

Critical strengths

Potentially interesting idea to use independent sets over a dependency graph in this setting. This could be promising as a research direction.

Critical weaknesses
  • The writing is quite bad, bordering on unreadable. The paper uses notation and terminology without ever establishing it and just hopes that the reader will deal with it. It's quite clear that there was quite heavy AI usage in the writing. I personally have no issue with AI usage but the paper needs to be clearly written and understandable, otherwise there's no way for a general ML audience to pick up anything from it.

Let me provide some examples to illustrate this clearly. Consider for example the following sentence from the introduction on the first page:

"The streams, however, are rarely independent. Endpoints share evaluation units, sensors share weather, evaluation tasks share prompts. Multiplying local evidence as though the streams were independent breaks (1)."

  • What is 'local evidence'? Evidence of what? What makes it 'local'? Is locality with respect to the dependency graph, is it with respect to time, or some other spatial property?
  • Why do we have to multiply evidence? What are we trying to achieve and how is multiplication relevant? What does it mean for that to break equation 1 and why is that a problem?

Here is an attempt at writing some of this a little differently in a way that can be addressed to a machine learning audience:

"Each stream produces a numerical score at each round, which we convert into a nonnegative betting factor. This factor determines how wealth changes when the new observation arrives. The account starts at 1, and each update multiplies its current value by the new factor. Wealth therefore carries forward the effects of earlier observations, allowing evidence to build as monitoring continues. We construct the factors so that, under the null hypothesis and given everything observed so far, the expected value of the next factor is at most 1. Consequently, the account has no expected increase under the null, and accumulated wealth beyond some threshold can be used to trigger an alarm. To combine observations from several streams within the same round, we may multiply their factors when the streams are conditionally independent given the past. This preserves the expected-value guarantee. On the other hand, multiplying factors from dependent streams can break it."

There are numerous places where this happens in the paper so the reader, unless they are a specialist on this precise topic, will struggle to understand the setting. For example 3.2 starts talking about r-coloring without explaining the connection to independent sets and talks about 'geometric mean process'.

Here is what could be written right before that to actually make this readable.

“We now compare our averaging rule with a benchmark based on graph coloring. A proper coloring partitions the streams into independent sets, so each set of nodes marked with the same color form a valid betting product. One way to combine these products is their geometric mean.”

In my view, this needs to be done carefully for the entire paper before it can be considered for publication at this venue.

Questions for authors

n/a

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.