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

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 $D$ 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* $\alpha (D)$, not the chromatic quantity $n/{\chi }_f(D)$; the two coincide on vertex-transitive graphs but the gap can be strict off that class, and $n/{\chi }_f$ understates the multiplier by up to $1.80\times$ on stars and grids in our sweep. On the negative side, a dependency graph is a $0/1$ 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 $1$ under exact duplication to the full clique size $r$ 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 $\rho$-approximate maximum-weight independent set inflates the expected rejection time by at most $1/\rho$, and introduce a balanced certified test that is within $\log 2$ 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 $\alpha$ while the independence product inflates to $0.080$–$0.132$. 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.