betaFeedback

WorksMathematics

Realized versus Population Reliability: Anytime-Valid Self-Consistency Certification under Correlated Reasoning

Abstract

Self-consistency certification treats repeated sampling from a language model as sequential evidence accumulation and stops when an anytime-valid e-process crosses a threshold, guaranteeing finite-sample Type I error control by Ville's inequality. Prior constructions assume sampled rollouts are conditionally independent. We show this assumption fails in practice: reasoning streams are positively correlated through shared reasoning prefixes or across-prompt heterogeneity, changing not merely certificate efficiency but the hypothesis certified. Modeling dependence via a per-unit latent state (the random-effects / intraclass-correlation structure) induces exchangeable, equi-correlated increments with correlation ρρ. Correlation splits the single null into a realized null about the drawn belief and a population null about average model behavior, which coincide only when ρ=0ρ=0. We show: (i) the standard betting e-process remains anytime-valid for the realized null, not the population null; (ii) read as a population-null test, a suitable mixture has asymptotic crossing probability at least π=P(μ(Z)>0)π=P(μ(Z)>0), potentially exceeding nominal εε; (iii) the within-unit mean's effective sample size saturates at 1/ρ1/ρ, so extra within-unit rollouts cannot restore population validity; and (iv) a prompt-level e-process restores population validity, with optimal allocation at one rollout per prompt under a pure rollout budget. Simulations and Claude Haiku 4.5 rollouts confirm this regime dependence: on GSM8K (ρ^=0.435\hatρ=0.435, θ^=+0.96\hatθ=+0.96) the gap is dormant, whereas on AIME (ρ^=0.480\hatρ=0.480, θ^=−0.15\hatθ=-0.15) the single-unit rule crosses on 24% of prompts at nominal ε=0.05ε=0.05, while the prompt-level procedure declines (0.00). This correctness result identifies which reliability claim an anytime-valid certificate actually supports under dependence.

Introduction

The deployment of large language models (LLMs) in reasoning tasks has revealed a fundamental tension between reliability and computational cost. Test-time scaling—including sampling multiple tiple responses, extending context windows, and running additional reasoning steps—improves output quality but consumes resources. The question of when to stop is both statistical (is there sufficient evidence for the conclusion?) and economic (is further computation worth the cost?). For self-consistency [13], where an LLM is queried repeatedly at positive temperature and the majority answer is selected, a recent line of work makes this rigorous: Cordero-Encinar & Duncan [ [6] formalize a Martingale Majority Certificate that, via test supermartingales and Ville’s inequality [11], stops with exact, finite-sample, anytime-valid Type I error control. This replaces the heuristic “sample a fixed number of times” with a principled certificate.

The gap: dependence

Every certificate in this line, and the broader anytime-valid toolkit it draws on [8, 9], assumes the rollouts are conditionally independent increments with a single drift parameter. While essential for the underlying theory, this assumption fails to hold in the two regimes of greatest practical interest.

Shared latent within a prompt. Tree-of-thought branching, prefix-shared decoding, and batched or speculative sampling produce rollouts that are independent only after conditioning on a reasoning prefix or plan that is itself sampled once. Marginally, the rollouts are correlated through the shared prefix.

Across-prompt aggregation. A deployment-level claim—“this model is reliable on this task”—pools evidence across a population of prompts. Prompts differ in difficulty: a model is rock-solid on easy items and scattered on hard ones, so the per-prompt margin is dispersed. That dispersion is exactly between-unit variance, and it makes the pooled increments correlated.

In both regimes the increments are positively correlated, and correlation does something more consequential than inflate variance. It splits the null hypothesis in two. The realized null concerns whether, for this prompt’s drawn reasoning, the certified answer is favored; the population null asks whether the answer is favored on average over the model’s randomness or the task distribution. When the increments are independent, these coincide. When they are correlated, they come apart by exactly the correlation ρ\rho, and a procedure that looks valid may be silently certifying the wrong one.

Contributions

This is a correctness contribution, not an efficiency one. We do not propose a faster certificate; we identify which reliability claim an anytime-valid certificate is entitled to make once rollouts are correlated, and we repair it when the population claim is the target.

  1. A dependent evidence model (§ 3). We transport the random-effects / intraclass correlation model from clustered data to the reasoning stream: a latent state ZZ is drawn once per certification unit, with rollouts conditionally i.i.d. given ZZ. This induces exchangeable, equicorrelated increments with correlation ρ=σB2σB2+σW2\rho= \frac{\sigma_B^2}{\sigma_B^2 + \sigma_W^2}, where σB2\sigma_B^2 and σW2\sigma_W^2 denote the between- and within-unit variances. Consequently, the single null splits into a realized null (μ(Z)≤0\mu(Z) \le0, governing the unit’s conditional mean) and a population null (θ=E[μ(Z)]≤0\theta= \mathbb{E}[\mu(Z)] \le0, governing the overall mean).

  1. Which null is controlled (§ 4). The standard betting e-process is not a supermartingale under the population null because the data eventually reveal ZZ, so the marginal validity argument breaks whenever the fraction of units with positive realized drift satisfies

π=P(μ(Z)>0)>0\pi= \mathbb{P}(\mu(Z) > 0) > 0. But it survives, exactly, for the realized null Theorem 4.2. Read as a population-null certificate, a suitable mixture has asymptotic population-null crossing probability at least π\pi, potentially exceeding the nominal error level ϵ\epsilon Proposition 4.5.

  1. An impossibility (Section 5). For the within-unit sample mean, the variance-equivalent effective sample size tends to 1/ρ1/\rho Theorem 5.1; the within-unit mean converges to the realized belief μ(Z)\mu(Z), and does not in general converge to the population drift θ\theta. Without additional structural information or independent units, a realized-null certificate does not yield a population-null guarantee.

  1. A remedy (Section 6). Genuine independence lives across units, so the e-process must too. A prompt-level e-process on within-unit means restores exact population validity Theorem 6.2, and an allocation analysis shows that, under a pure rollout budget, the variance-minimizing choice is one rollout per prompt; a per-prompt cost is required before extra rollouts help Proposition 6.3.

  1. Unknown ρ\rho and beyond exchangeability (Section 7). Realized-null validity needs no knowledge of ρ\rho; population validity under unknown ρ\rho uses variance-adaptive betting. Arbitrary serial dependence within a unit is genuinely open and is where dependence-robust (HAC / near-epoch-dependent) machinery is required.

  1. Measurement (Section 8). Simulation confirms the mechanism and its repair. On real rollouts (Claude Haiku 4.5) we measure the across-prompt ρ\rho on two benchmarks: GSM8K (ρ^=0.435\hat{\rho} = 0.435), where strong self-consistency (θ^=+0.96\hat{\theta} = +0.96) leaves the gap dormant, and AIME (ρ^=0.480\hat{\rho} = 0.480, θ^=−0.15<0\hat{\theta} = -0.15 < 0), where the estimated population margin is negative and over-certification occurs. Read as a population-null test, the single-unit rule produces single-prompt crossings on 24% of prompts, versus a nominal ϵ=0.05\epsilon= 0.05 population-test level, while the prompt-level remedy declines.

Relation to prior certificates. Our results do not contradict Cordero-Encinar & Duncan [ [6] or its successors. For a single prompt with independently sampled rollouts ρ=0\rho= 0, the two nulls coincide, and those certificates are exactly correct for the margin they target. The point is that under the correlation present in shared-prefix decoding and in across-prompt aggregation, the same construction controls the realized null while the application often wants the population null. Dey & Bhandari [ [7] study asymptotically optimal sequential multiple testing in an equicorrelated Gaussian model, the same correlation structure we adopt, but from a fixed-procedure optimality viewpoint; we work in the anytime-valid e-process framework and isolate the hypothesis-identification problem that dependence creates. Closest in setting is Ota et al. [ [5], who give anytime-valid certification of a target answer as the mode of the response distribution under data-driven stopping and an unknown answer-category set, with minimax rates and experiments on open models over hard benchmarks; that work operates under independence and addresses the unknown category set, whereas we address dependence and the realized-versus-population identification, which are complementary axes. Akter et al. [ [2] similarly build self-normalized empirical-Bernstein e-processes for LLM generation under unknown centering. Finally, Cordero-Encinar & Duncan [ [6] explicitly name applying anytime-valid certificates to correlated rollouts as future work; the present paper takes up exactly that problem.

Outline

Section 2 recalls the anytime-valid toolkit as the ρ=0\rho= 0 baseline. Section 3 develops the dependent evidence model and the two nulls. Section 4 establishes which null the standard certificate controls and the over-certification of the population null. Section 5 proves the information-saturation impossibility. Section 6 gives the prompt-level remedy and allocation. Section 7 treats unknown ρ\rho and serial dependence. Section 8 reports simulations and the measured ρ\rho. Section 9 discusses scope and limitations.

Background: the independent baseline

We recall the anytime-valid machinery in the form we need, treating it throughout as the ρ=0\rho= 0 special case of the dependent model of § 3.

Ville's inequality and test supermartingales

The challenge of sequential testing is optional stopping: when the decision to stop depends on the data, fixed-sample guarantees fail. Ville’s inequality is the remedy.

Definition 2.1 (Supermartingale). An integrable sequence (Mn)n≥1(M_n)_{n\geq1} adapted to a filtration (Fn)n≥1(\mathcal{F}_n)_{n\geq1} is a supermartingale if E[Mn∣Fn−1]≤Mn−1\mathbb{E}[M_n \mid\mathcal{F}_{n-1}] \leq M_{n-1} almost surely for all n≥2n \geq2.

Theorem 2.2 [11]. If (Mn)n≥1(M_n)_{n\geq1} is a non-negative supermartingale with E[M1]≤1\mathbb{E}[M_1] \leq1, then for any threshold u>0u > 0, P(sup⁡n≥1Mn≥u)≤1/u\mathbb{P}\left(\sup_{n\geq1} M_n \geq u\right) \leq1/u.

Definition 2.3 (Test supermartingale). A test supermartingale (the canonical form of an e-process) for a null H0H_0 is a non-negative supermartingale (En)n≥1(E_n)_{n\geq1} under H0H_0 with E0[E1]≤1\mathbb{E}_0[E_1] \leq1.

Corollary 2.4 (Anytime-valid test). If (En)n≥1(E_n)_{n\geq1} is a test supermartingale under H0H_0, the rule τ=inf⁡{n≥1:En≥1/ϵ}\tau= \inf\{n \geq1 : E_n \geq1/\epsilon\} that rejects H0H_0 at τ\tau satisfies P0(τ<∞)≤ϵ\mathbb{P}_0(\tau< \infty) \leq\epsilon, regardless of when or whether one stops.

The value EnE_n is the “evidence against H0H_0” accumulated by stage nn. Corollary 2.4 is immediate: {τ<∞}={sup⁡n≥1En≥1/ϵ}\{\tau< \infty\} = \{\sup_{n\geq1} E_n \geq1/\epsilon\} and Theorem 2.2 applies with u=1/ϵu = 1/\epsilon.

Two baseline constructions

For self-consistency [13], fix a candidate answer cc using a separate pilot sample. One possible increment compares cc with a fixed runner-up rr: Ynpair=1{Xn=c}−1{Xn=r}∈{−1,0,+1}Y_n^{\mathrm{pair}} = \mathbb{1}\{X_n = c\} - \mathbb{1}\{X_n = r\} \in\{-1,0,+1\}, with population margin pc−prp_c - p_r. Our experiments instead compare cc with its complement: Yn=1{Xn=c}−1{Xn≠c}∈{−1,+1}Y_n = \mathbb{1}\{X_n = c\} - \mathbb{1}\{X_n \ne c\} \in\{-1,+1\}, with mean 2pc−12p_c - 1. Both statistics satisfy ∣Yn∣≤B=1|Y_n| \leq B = 1, and the martingale arguments below apply to either after fixing the statistic. Unless stated otherwise, YnY_n, μ\mu (the conditional mean, formalized in § 3), and θ\theta (the population drift) refer to the leader-versus-complement statistic used in the experiments. The null is H0:θ≤0H_0 : \theta\leq0.

Beta-mixture (Martingale Majority Certificate). Cordero-Encinar & Duncan [2025] place a Beta prior π\pi on the leader probability over the alternative (θ>0)(\theta> 0) and form the mixture likelihood-ratio process EnBeta=∫Ln(θ) π(dθ)E_n^{\mathrm{Beta}} = \int L_n(\theta)\,\pi(d\theta) relative to θ=0\theta= 0, which is a martingale at θ=0\theta= 0 (and a supermartingale for θ≤0\theta\leq0) and crosses 1/ϵ1/\epsilon at the boundary Sn≳2n(log⁡(1/ϵ)+12log⁡n)S_n \gtrsim\sqrt{2n(\log(1/\epsilon) + \frac{1}{2}\log n)}.

Betting / Robbins-stitched. For a betting fraction λ∈[0,1/B]\lambda\in[0,1/B], the product Mn=∏t≤n(1+λYt)M_n = \prod_{t\leq n}(1 + \lambda Y_t) satisfies E0[1+λYt∣Ft−1]=1+λθ≤1\mathbb{E}_0[1 + \lambda Y_t \mid\mathcal{F}_{t-1}] = 1 + \lambda\theta\leq1 when θ≤0\theta\leq0, hence is a supermartingale; mixing λ\lambda over a geometric grid [10, 8] yields the law-of-the-iterated-logarithm boundary Sn≳2σ2n(log⁡(1/ϵ)+Clog⁡log⁡n)S_n \gtrsim\sqrt{2\sigma^2 n(\log(1/\epsilon) + C\log\log n)}. The betting form is the one we carry into the dependent setting, because its supermartingale property is what dependence disrupts.

Remark 2.5 (Scope of this paper). The efficiency comparison between these constructions, specifically the log⁡n\log n versus log⁡log⁡n\log\log n boundary gap, is orthogonal to our question and we do not pursue it. Both are valid test supermartingales for θ≤0\theta\le0 under independence; our concern is what “θ≤0\theta\le0” even means, and which null these processes control, once the increments are correlated.

The Dependent Evidence Model

Section 2 treated the evidence increments as conditionally independent with a single drift parameter. That is the right model for one canonical case and the wrong model for several others. When an LLM is queried multiple times for a fixed prompt with independent samples, the rollouts are genuinely independent and the constructions of Section 2 apply verbatim. But independence fails whenever the increments share sampled structure: rollouts that branch from a common reasoning prefix, batched or speculative decoding that reuses randomness, or an aggregate certificate that pools evidence across a population of prompts to make a claim about the model rather than about a single query. In each of these the increments are correlated, and the correlation changes not merely the efficiency of a certificate but the very hypothesis it certifies.

We formalize this through a latent state drawn once per certification unit and shared across that unit’s increments. The construction is the random-effects (intraclass-correlation) model familiar from clustered data, transported to the reasoning stream.

Latent-belief evidence processes

Definition 3.1 (Latent-belief evidence process). A certification unit emits increments Y1,Y2,…Y_1,Y_2,\ldots with cumulative evidence Sn=∑t=1nYtS_n=\sum_{t=1}^{n}Y_t. A latent state ZZ, taking values in a measurable space Z\mathcal{Z}, is drawn once at the start of the unit. Conditional on ZZ, the increments (Yt)t≥1(Y_t)_{t\ge1} are independent and identically distributed with

μ(Z):=E[Yt∣Z],Var⁡(Yt∣Z)=σW2(Z),∣Yt∣≤B a.s.\mu(Z):=\mathbb{E}[Y_t\mid Z], \qquad\operatorname{Var}(Y_t\mid Z)=\sigma_W^2(Z), \qquad|Y_t|\le B\ \text{a.s.}

We collect the marginal moments that govern the process:

θ:=E[μ(Z)],σB2:=Var⁡(μ(Z)),σW2:=E[σW2(Z)],σ2:=σB2+σW2.\theta:=\mathbb{E}[\mu(Z)], \qquad\sigma_B^2:=\operatorname{Var}(\mu(Z)), \qquad\sigma_W^2:=\mathbb{E}[\sigma_W^2(Z)], \qquad\sigma^2:=\sigma_B^2+\sigma_W^2.

Here θ\theta is the population drift, σB2\sigma_B^2 the between-unit variance (dispersion of the belief), σW2\sigma_W^2 the mean within-unit variance, and σ2=Var⁡(Yt)\sigma^2=\operatorname{Var}(Y_t) the marginal variance by the law of total variance.

Two filtrations matter, and the gap between them drives every result that follows. The observed filtration is Fn=σ(Y1,…,Yn)\mathcal{F}_n=\sigma(Y_1,\ldots,Y_n); it is what a certificate actually sees. The oracle filtration Gn=σ(Z,Y1,…,Yn)\mathcal{G}_n=\sigma(Z,Y_1,\ldots,Y_n) additionally resolves the latent state. Crucially, Z∉FnZ\notin\mathcal{F}_n: the decision-maker never observes the belief, only its noisy consequences.

Proposition 3.2 (Exchangeability and equicorrelation). Under Definition 3.1 with σW2>0\sigma_W^2>0, the increments (Yt)(Y_t) are exchangeable, and for every t≠st\ne s,

Cov⁡(Yt,Ys)=σB2,Corr⁡(Yt,Ys)=ρ:=σB2σB2+σW2∈[0,1).\operatorname{Cov}(Y_t,Y_s)=\sigma_B^2,\qquad\operatorname{Corr}(Y_t,Y_s)=\rho:=\frac{\sigma_B^2}{\sigma_B^2+\sigma_W^2}\in[0,1).

The common pairwise correlation ρ\rho is exact, irrespective of any heterogeneity in the conditional variances σW2(Z)\sigma_W^2(Z).

Proof. Exchangeability is immediate from conditional i.i.d. structure. For t≠st \ne s, the law of total covariance and conditional independence give

Cov⁡(Yt,Ys)=E[Cov⁡(Yt,Ys∣Z)]+Cov⁡(E[Yt∣Z],E[Ys∣Z])=0+Var⁡(μ(Z))=σB2.\operatorname{Cov}(Y_t,Y_s)=\mathbb{E}\left[\operatorname{Cov}(Y_t,Y_s\mid Z)\right]+\operatorname{Cov}\left(\mathbb{E}[Y_t\mid Z],\mathbb{E}[Y_s\mid Z]\right)=0+\operatorname{Var}(\mu(Z))=\sigma_B^2.

Dividing by the marginal variance σ2=σB2+σW2>0\sigma^2=\sigma_B^2+\sigma_W^2>0 yields ρ\rho.

Proposition 3.3 (Variance of the within-unit mean). Let Yˉn=Sn/n\bar{Y}_n=S_n/n. Under Definition 3.1 with σW2>0\sigma_W^2>0,

Var⁡(Yˉn)=σB2+σW2n=σ2neff,neff:=n1+(n−1)ρ⟶n→∞1ρ,\operatorname{Var}(\bar{Y}_n)=\sigma_B^2+\frac{\sigma_W^2}{n}=\frac{\sigma^2}{n_{\mathrm{eff}}},\qquad n_{\mathrm{eff}}:=\frac{n}{1+(n-1)\rho}\longrightarrow_{n\to\infty}\frac{1}{\rho},

with the convention 1/0:=∞1/0:=\infty when ρ=0\rho=0.

Proof. By Proposition 3.2, Var⁡(Yˉn)=n−2[nσ2+n(n−1)σB2]=σW2/n+σB2\operatorname{Var}(\bar{Y}_n)=n^{-2}[n\sigma^2+n(n-1)\sigma_B^2]=\sigma_W^2/n+\sigma_B^2. Substituting σB2=ρσ2\sigma_B^2=\rho\sigma^2 and σW2=(1−ρ)σ2\sigma_W^2=(1-\rho)\sigma^2 gives Var⁡(Yˉn)=σ2{1+(n−1)ρ}/n\operatorname{Var}(\bar{Y}_n)=\sigma^2\{1+(n-1)\rho\}/n, hence the stated neffn_{\mathrm{eff}}.

Proposition 3.3 is the seed of the impossibility result in § 5: when ρ>0\rho>0, averaging within a single unit cannot drive the variance below σB2\sigma_B^2, so the within-unit mean is a consistent estimator of the realized belief μ(Z)\mu(Z), not of the population drift θ\theta.

Remark 3.4 (Recovery of the independent model). ρ=0\rho=0 iff σB2=0\sigma_B^2=0 iff μ(Z)=θ\mu(Z)=\theta almost surely. In that case the latent state is degenerate, Fn\mathcal{F}_n and Gn\mathcal{G}_n carry the same information about the drift, and Definition 3.1 collapses to the conditionally independent process of § 2. The constructions and guarantees recalled there are the ρ=0\rho=0 special case of what follows.

Remark 3.5 (Why the observed filtration misbehaves). Under the oracle filtration the conditional mean is constant, E[Yn+1∣Gn]=μ(Z)\mathbb{E}[Y_{n+1}\mid\mathcal{G}_n]=\mu(Z). Under the observed filtration it is the posterior mean of the belief given the data, E[Yn+1∣Fn]=E[μ(Z)∣Fn]\mathbb{E}[Y_{n+1}\mid\mathcal{F}_n]=\mathbb{E}[\mu(Z)\mid\mathcal{F}_n], which is not constant in nn and converges to μ(Z)\mu(Z) as the data accumulate. The observed process therefore learns the realized drift over time. This is the mechanism that breaks the marginal supermartingale property under the population null and forces the distinction between the two hypotheses below; we make it precise in § 4.

Two null hypotheses

Correlation splits the single null of § 2 into two hypotheses that coincide only in the degenerate case.

Definition 3.6 (Population and realized nulls). The population null concerns the model’s average behavior,

H0pop: θ≤0versusH1pop: θ>0.H_0^{\mathrm{pop}}:\ \theta\le0 \qquad\text{versus}\qquad H_1^{\mathrm{pop}}:\ \theta>0.

The realized null concerns the drawn belief,

H0rel: μ(Z)≤0versusH1rel: μ(Z)>0.H_0^{\mathrm{rel}}:\ \mu(Z)\le0 \qquad\text{versus}\qquad H_1^{\mathrm{rel}}:\ \mu(Z)>0.

Remark 3.7 (Equivalence only at ρ=0\rho=0). Since μ(Z)=θ\mu(Z)=\theta a.s. iff σB2=0\sigma_B^2=0 iff ρ=0\rho=0, the two nulls are equivalent precisely when the increments are uncorrelated. Whenever ρ>0\rho>0 they are distinct events, and a procedure that controls one need not control the other.

The two nulls answer different questions. The realized null asks whether, for this unit’s drawn reasoning, the certified outcome is favored: a claim about the particular prompt-and-prefix in front of the decision-maker. The population null asks whether the outcome is favored on average over the model’s randomness or over the population of prompts: a claim about the system. For a single high-stakes query the realized null may be exactly what one wants; for a deployment-level reliability guarantee the population null is the target. The two come apart by ρ\rho, and conflating them is the error this paper is about.

Definition 3.8 (Realized-alternative probability). Write π:=P(μ(Z)>0)\pi:= \mathbb{P}(\mu(Z)>0) for the probability that the realized belief favors the certified outcome.

Under H0popH_0^{\mathrm{pop}} with σB2>0\sigma_B^2 > 0 one may still have π>0\pi> 0: the average belief disfavors the outcome while individual draws favor it. This wedge between θ≤0\theta\le0 and π>0\pi> 0 is the quantity that a single-unit certificate silently exploits, and it reappears as the over-certification rate in § 4.

Instantiation: dependent self-consistency

We recast the self-consistency process of § 2 inside the latent-belief model. Let cc be the answer selected on an independent pilot sample and fix it before the held-out evidence stream begins. In the empirical implementation Yt=21{Xt=c}−1∈{−1,+1}Y_t = 2\mathbf{1}\{X_t = c\} - 1 \in\{-1,+1\}, with B=1B = 1. Its conditional mean is μ(Z)=2pc(Z)−1\mu(Z) = 2p_c(Z) - 1; a positive value means that cc receives more than half the conditional answer probability, not merely that it is the most probable individual answer. The latent state admits two readings, both of practical relevance.

Across-prompt aggregation. Let ZZ index the prompt together with its terminal answer distribution, drawn from the task distribution; conditional on ZZ the held-out rollouts are independent, with μ(Z)=2pc(Z)−1\mu(Z) = 2p_c(Z) - 1 the leader-versus-complement margin for that prompt. The population drift θ=E[2pc(Z)−1]\theta= \mathbb{E}[2p_c(Z)-1], incorporating the random pilot-selection procedure, is the average margin over the task. Thus H0popH_0^{\mathrm{pop}} states that a pilot-selected answer has probability at most one half on average. Here ρ\rho measures how much the leader margin varies across prompts relative to within-prompt sampling noise.

Shared latent within a prompt. Let ZZ be a sampled reasoning prefix or latent plan that a batch of rollouts conditions on, as in tree-of-thought or prefix-shared decoding; conditional on ZZ the continuations are independent, but marginally they are correlated through the shared prefix. Even a single-prompt certificate then accumulates evidence about μ(Z)\mu(Z), the margin under the drawn prefix, rather than about the prompt’s unconditional margin.

Remark 3.9 (Relation to independent self-consistency). For a single prompt with independently sampled rollouts there is no shared latent, ρ=0\rho= 0, and the certificate controls the corresponding fixed-candidate margin (2pc−12p_c - 1 in our empirical implementation) exactly; the guarantees of § 2 are unaffected. The dependent regime arises only under the two structures above. We state this explicitly because the distinction is easy to miss: the issue is not that anytime-valid self-consistency certificates are invalid, but that under correlation they certify the realized null when the population null is what the application requires.

Remark 3.10 (The estimand under a pilot-selected leader). When the answer cc is fixed from a separate pilot slice of rollouts (as in § 8), the held-out score is Yt=21{Xt=c}−1Y_t = 2\mathbf{1}\{X_t = c\} - 1. The realized mean μ(Z)\mu(Z) measures the conditional majority probability of the pilot-selected answer, not its probability of being correct or its margin over the second most likely answer. The population mean θ\theta averages this score across freshly drawn prompts and their corresponding random pilots. Fixing cc before observing the held-out sequence preserves the conditional martingale argument. For the population-level construction, independent units must include independently drawn pilots; conditioning on all realized pilots is not generally compatible with the common-mean assertion E[Uq]=θ\mathbb{E}[U_q] = \theta.

Assumptions

We restate the regularity conditions of § 2 conditionally on the latent state.

Assumption 3.11 (Conditional sub-Gaussian increments). There exists σW>0\sigma_W > 0 such that for all λ∈R\lambda\in\mathbb{R} and t≥1t \ge1,

E[eλ(Yt−μ(Z))∣Z]≤eλ2σW2/2a.s.\mathbb{E}\left[e^{\lambda(Y_t-\mu(Z))} \mid Z\right] \le e^{\lambda^2\sigma_W^2/2} \quad\text{a.s.}

Remark 3.12. Assumption 3.11 holds for bounded increments with σW2=B2\sigma_W^2 = B^2 by Hoeffding’s lemma applied conditionally on ZZ. It governs concentration within a unit; the between-unit dispersion σB2\sigma_B^2 is unrestricted beyond having a finite second moment.

Assumption 3.13 (Exchangeable dependence). The increments follow the latent-belief structure of Definition 3.1: conditionally i.i.d. given a single latent state ZZ drawn once per unit.

Assumption 3.13 is the working dependence model for the rest of the paper. It captures shared-belief correlation exactly but excludes arbitrary serial dependence within a unit, where the conditioning argument of § 4 no longer applies. We return to that more general case, and to the tools required for it, in § 7.

What the Certificate Controls

We now apply the standard betting e-process to a correlated stream and determine which hypothesis it certifies. The headline is a dichotomy: the marginal supermartingale property fails under the population null but the certificate remains exactly valid for the realized null, and reading it as a population-null certificate can invalidate population-null Type I error control. Table 1 summarizes the scope of each result, its target null, the filtration on which it holds, and the dependence assumption, so the central distinction is not misread; none of the validity guarantees requires knowledge of ρ\rho.

Table 1: Scope of the main results. “Anytime” denotes exact, finite-sample validity at data-dependent stopping times. None of the validity guarantees requires knowing ρ\rho; ρ\rho governs only efficiency (betting fraction and allocation).

ResultTargetFiltrationDependenceType
Thm 4.2 (realized validity)H0rel:μ(Z)≤0H_0^{\mathrm{rel}} : \mu(Z) \le0oracle Gn\mathcal{G}_n (cond. on ZZ)exchangeablefinite-sample, anytime
Prop 4.5 (over-certification)H0pop:θ≤0H_0^{\mathrm{pop}} : \theta\le0observed Fn\mathcal{F}_nexch., π>0\pi> 0asymptotic lower bound
Thm 5.1 (saturation)estimation of θ\thetaobserved Fn\mathcal{F}_nexch., ρ>0\rho> 0exact variance, a.s. limit
Thm 6.2 (remedy)H0pop:θ≤0H_0^{\mathrm{pop}} : \theta\le0unit-level Hq\mathcal{H}_qindep. across unitsfinite-sample, anytime

Table 1.

The marginal supermartingale property fails

Consider the betting e-process Mn=∏t=1n(1+λYt)M_n = \prod_{t=1}^{n}(1+\lambda Y_t) with λ∈(0,1/B]\lambda\in(0,1/B] applied to the observed stream. Under the population null θ≤0\theta\le0 one might hope MnM_n is an Fn\mathcal{F}_n-supermartingale, as in § 2. It is not.

Proposition 4.1 (Failure under the population null). Under Definition 3.1, suppose θ≤0\theta\le0 but π=P(μ(Z)>0)>0\pi= \mathbb{P}(\mu(Z) > 0) > 0. Then Mn=∏t≤n(1+λYt)M_n = \prod_{t \le n}(1 + \lambda Y_t) with λ∈(0,1/B]\lambda\in(0,1/B] is not an Fn\mathcal{F}_n-supermartingale under H0popH_0^{\mathrm{pop}}. If instead μ(Z)≤0\mu(Z) \le0 almost surely (so π=0\pi= 0), the conditioning argument of Theorem 4.2 shows MnM_n is a supermartingale and no failure occurs; thus π>0\pi> 0 is the operative condition, not σB2>0\sigma_B^2 > 0 alone.

Proof. By Remark 3.5, E[Yn+1∣Fn]=E[μ(Z)∣Fn]\mathbb{E}[Y_{n+1} \mid\mathcal{F}_n] = \mathbb{E}[\mu(Z) \mid\mathcal{F}_n], the posterior mean of μ(Z)\mu(Z) given the data. Hence E[Mn+1∣Fn]=Mn(1+λE[μ(Z)∣Fn])\mathbb{E}[M_{n+1} \mid\mathcal{F}_n] = M_n(1 + \lambda\mathbb{E}[\mu(Z) \mid\mathcal{F}_n]). On the event that the observed history favors a positive belief, which has positive probability whenever π>0\pi> 0, the posterior mean E[μ(Z)∣Fn]\mathbb{E}[\mu(Z) \mid\mathcal{F}_n] is positive even though θ≤0\theta\le0, so E[Mn+1∣Fn]>Mn\mathbb{E}[M_{n+1} \mid\mathcal{F}_n] > M_n there. The supermartingale inequality is violated, so Ville’s inequality cannot be invoked under H0popH_0^{\mathrm{pop}} on the observed filtration.

The break is not pathological: it is the process learning the realized belief. The repair is to condition on ZZ.

Validity for the realized null

Theorem 4.2 (Realized-null validity). Let (En)(E_n) be the betting e-process Mn=∏t≤n(1+λYt)M_n = \prod_{t \le n}(1 + \lambda Y_t) with λ∈[0,1/B]\lambda\in[0,1/B], or its stitched mixture over a fixed grid of such λ\lambda, built from the increments (Yt)(Y_t), and τ=inf⁡{n:En≥1/ϵ}\tau= \inf\{n : E_n \ge1/\epsilon\}. Under Definition 3.1,

P({sup⁡nEn≥1/ϵ}∩{μ(Z)≤0})≤ϵ,andP(certify⁡∣μ(Z)≤0)≤ϵ.\mathbb{P}\left(\{\sup_n E_n \ge1/\epsilon\} \cap\{\mu(Z) \le0\}\right) \le\epsilon, \qquad\text{and} \qquad\mathbb{P}(\operatorname{certify} \mid\mu(Z) \le0) \le\epsilon.

That is, the procedure is an exact, anytime-valid test of the realized null H0rel:μ(Z)≤0H_0^{\mathrm{rel}} : \mu(Z) \le0.

Proof. Work on the oracle filtration Gn=σ(Z,Y1,…,Yn)\mathcal{G}_n = \sigma(Z,Y_1,\ldots,Y_n). Conditional on Z=zZ = z with μ(z)≤0\mu(z) \le0, the increments are i.i.d. with non-positive mean, so for the betting process E[1+λYt∣Gt−1,Z=z]=1+λμ(z)≤1\mathbb{E}[1 + \lambda Y_t \mid\mathcal{G}_{t-1}, Z = z] = 1 + \lambda\mu(z) \le1 and (En)(E_n) is a non-negative Gn\mathcal{G}_n-supermartingale with E[E1∣Z=z]≤1\mathbb{E}[E_1 \mid Z = z] \le1 under P(⋅∣Z=z)\mathbb{P}(\cdot\mid Z = z). (For the stitched mixture the same holds by convexity: it is an average over a fixed grid of λ\lambda of conditional supermartingales, and a convex combination of conditional supermartingales is one.) Ville’s inequality applied conditionally gives P(sup⁡nEn≥1/ϵ∣Z=z)≤ϵ\mathbb{P}(\sup_n E_n \ge1/\epsilon\mid Z = z) \le\epsilon for a.e. such zz. Averaging the conditional bound over {μ(Z)≤0}\{\mu(Z) \le0\} yields P(certify⁡∣μ(Z)≤0)≤ϵ\mathbb{P}(\operatorname{certify} \mid\mu(Z) \le0) \le\epsilon, and multiplying by P(μ(Z)≤0)≤1\mathbb{P}(\mu(Z) \le0) \le1 gives the joint bound.

Remark 4.3 (On the Beta-mixture). We state Theorem 4.2 for betting-based e-processes because their supermartingale property holds conditionally on ZZ by the one-line argument above. The Beta-mixture certificate of Cordero-Encinar & Duncan [2025] is also realized-null valid, but this requires specifying its likelihood under the latent model: the Beta prior must be placed on the conditional leader probability pc(Z)p_c(Z), so that the mixture is a test supermartingale for the conditional law given ZZ. Under that reading the same conditioning argument applies; we restrict the statement to the betting form to avoid asserting it for an unspecified likelihood.

Remark 4.4 (What this buys and does not). Theorem 4.2 is good news for single-query certification: even under shared-prefix correlation, the standard certificate exactly controls the error of the claim “for the reasoning actually drawn, this answer is favored.” It needs no knowledge of ρ\rho. What it does not deliver is a statement about the model’s average behavior, and the next result shows the two can be far apart.

Over-certification of the population null

Proposition 4.5 (Over-certification). Suppose H0popH_{0}^{\mathrm{pop}} holds (θ≤0\theta\le0) but π=P(μ(Z)>0)>0\pi= \mathbb{P}(\mu(Z) > 0) > 0. For a fixed 0<λ<1/B0 < \lambda< 1/B let gλ(z)=E[log⁡(1+λYt)∣Z=z]g_{\lambda}(z) = \mathbb{E}[\log(1 + \lambda Y_t) \mid Z = z] and Aλ={z:gλ(z)>0}A_{\lambda} = \{z : g_{\lambda}(z) > 0\}. The betting process Mn(λ)=∏t≤n(1+λYt)M_n(\lambda) = \prod_{t \le n}(1 + \lambda Y_t) then satisfies

lim⁡n→∞P(sup⁡t≤nMt(λ)≥1/ϵ)≥P(Z∈Aλ).\lim_{n \to\infty} \mathbb{P}\left(\sup_{t \le n} M_t(\lambda) \ge1/\epsilon\right) \ge\mathbb{P}(Z \in A_{\lambda}).

In particular, let λj∈(0,1/B)\lambda_j \in(0,1/B) decrease to zero and let wj>0w_j > 0 with ∑jwj=1\sum_j w_j = 1. The mixture En=∑jwjMn(λj)E_n = \sum_j w_j M_n(\lambda_j) satisfies

lim⁡n→∞P(sup⁡t≤nEt≥1/ϵ)≥π.\lim_{n \to\infty} \mathbb{P}\left(\sup_{t \le n} E_t \ge1/\epsilon\right) \ge\pi.

These crossing probabilities refer to the population-null data-generating law and need not be bounded by ϵ\epsilon. The second conclusion does not necessarily hold for a fixed finite betting grid.

Proof. Conditional on Z=zZ = z, bounded increments are i.i.d. For each fixed 0<λ<1/B0 < \lambda< 1/B, the strong law gives n−1log⁡Mn(λ)→gλ(z)n^{-1}\log M_n(\lambda) \to g_{\lambda}(z) almost surely. Hence Mn(λ)→∞M_n(\lambda) \to\infty on AλA_{\lambda}, establishing the first claim. If μ(z)>0\mu(z) > 0, then g0(z)=0g_0(z) = 0 and ddλgλ(z)∣λ=0=μ(z)>0\left.\frac{d}{d\lambda}g_{\lambda}(z)\right|_{\lambda=0} = \mu(z) > 0. Thus some sufficiently small positive λj\lambda_j has gλj(z)>0g_{\lambda_j}(z) > 0. The positive-weight term wjMn(λj)w_jM_n(\lambda_j) then diverges, and so does EnE_n. Integrating this conditional almost-sure statement over {μ(Z)>0}\{\mu(Z) > 0\} and using continuity from below gives the second bound.

Remark 4.6 (Lower bound, not equality). The lower bound π\pi applies to the countable mixture specified in Proposition 4.5, not necessarily to the finite grid used in the experiments. On realized-negative units (μ(Z)≤0\mu(Z) \le0), conditional supermartingale validity bounds additional crossing probability by at most ϵ(1−π)\epsilon(1-\pi). At finite sample sizes, positive-drift units may not have crossed even if their asymptotic log-growth is positive. The qualitative point is what matters: the error is governed by π\pi, a quantity unrelated to the nominal level ϵ\epsilon.

Remark 4.7 (The practical reading). Draw many rollouts from one prompt (or pool a difficult task) and certify the plurality answer: a threshold crossing supplies evidence about the realized conditional margin (subject to its test error), not the average margin over prompts. With positively correlated rollouts these are different claims, and the gap depends on the distribution of realized means, including π\pi; ρ\rho alone does not determine π\pi. A certificate calibrated to ϵ=0.05\epsilon= 0.05 may have a population-null crossing rate much larger than ϵ\epsilon, as the proposition demonstrates.

The Impossibility: Information Saturation

Over-certification might seem fixable by sampling harder, that is, by taking more rollouts from the same unit. It is not. Under ρ>0\rho> 0 a single unit carries a bounded amount of information about the population drift, no matter the budget.

Theorem 5.1 (Information saturation). Under Definition 3.1 with ρ>0\rho> 0:

  1. Yˉn→μ(Z)\bar{Y}_n \to\mu(Z) almost surely, and Var⁡(Yˉn)→σB2>0\operatorname{Var}(\bar{Y}_n) \to\sigma_B^2 > 0; the within-unit mean is consistent for the realized belief μ(Z)\mu(Z) and is not a consistent estimator of θ\theta.

  2. The variance-equivalent effective sample size for the within-unit sample mean is neff=n/(1+(n−1)ρ)→1/ρn_{\mathrm{eff}} = n/(1 + (n - 1)\rho) \to1/\rho. This is a design-effect calculation for that estimator, not a universal information bound for every estimator or structured parametric model.

Proof. Conditional on ZZ, the increments are i.i.d. with mean μ(Z)\mu(Z), so the strong law gives Yˉn→μ(Z)\bar{Y}_n \to\mu(Z) a.s.; the variance statement and neffn_{\mathrm{eff}} are Proposition 3.3. Since μ(Z)\mu(Z) is non-degenerate when σB2>0\sigma_B^2>0, Yˉn\bar{Y}_n does not converge to the constant θ\theta.

Corollary 5.2 (Single-unit budget guarantees are vacuous for the population null). The high-probability budget guarantee of the independent theory—“with probability 1−δ1-\delta the certificate stops within O(σ2log⁡(1/ϵ)/θ2)O(\sigma^2\log(1/\epsilon)/\theta^2) rollouts”—bounds the time to resolve the realized drift μ(Z)\mu(Z). As a statement about the population drift θ\theta it is vacuous as nn grows: additional samples from the same unit reduce Var⁡(Yˉn)\operatorname{Var}(\bar{Y}_n) negligibly and add essentially no information about θ\theta.

Remark 5.3 (The design effect). Theorem 5.1 is the cluster-sampling design effect [4] 1+(n−1)ρ1+(n-1)\rho transplanted to rollouts. It is the sharp negative result the independent theory lacks: it explains why the cheap move of repeatedly sampling one prompt cannot deliver a population guarantee, and points to what must replace it.

The Remedy: Certifying Across Units

If θ\theta is the target, the genuine independence lives across units, so the e-process must be built there.

A prompt-level e-process

Definition 6.1 (Prompt-level evidence). Index independent certification units q=1,2,…q=1,2,\ldots (e.g. distinct prompts drawn from the task). For unit qq draw nqn_q rollouts and form the within-unit mean Uq:=Yˉnq∈[−B,B]U_q:=\bar{Y}_{n_q}\in[-B,B]. The UqU_q are independent across qq with E[Uq]=θ\mathbb{E}[U_q]=\theta and Var⁡(Uq)=σB2+σW2/nq\operatorname{Var}(U_q)=\sigma_B^2+\sigma_W^2/n_q.

Theorem 6.2 (Population validity). For a betting fraction λ∈[0,1/B]\lambda\in[0,1/B], the prompt-level process MQ:=∏q=1Q(1+λUq)M_Q:=\prod_{q=1}^{Q}(1+\lambda U_q) is a non-negative supermartingale under H0pop:θ≤0H_0^{\mathrm{pop}}:\theta\leq0 with E0[M1]≤1\mathbb{E}_0[M_1]\leq1. Hence τ=inf⁡{Q:MQ≥1/ϵ}\tau=\inf\{Q:M_Q\geq1/\epsilon\} satisfies P0(τ<∞)≤ϵ\mathbb{P}_0(\tau<\infty)\leq\epsilon as an exact, anytime-valid test of the population null. Mixing λ\lambda over a geometric grid recovers the law-of-the-iterated-logarithm boundary in the number of units QQ.

Proof. Let Hq=σ(U1,…,Uq)\mathcal{H}_q=\sigma(U_1,\ldots,U_q). The UqU_q are independent with mean θ\theta, so E[1+λUq∣Hq−1]=1+λθ≤1\mathbb{E}[1+\lambda U_q\mid\mathcal{H}_{q-1}]=1+\lambda\theta\leq1 when θ≤0\theta\leq0; the supermartingale property and E0[M1]≤1\mathbb{E}_0[M_1]\leq1 follow, and Corollary 2.4 gives the bound. The stitched mixture over λ\lambda applies unchanged at the unit level.

The key shift is the index: evidence is accumulated over units, each contributing a single near-independent summary UqU_q, rather than over correlated rollouts within one unit.

Budget allocation

How should a fixed budget be split between more units and more rollouts per unit? The answer inverts the naive intuition.

Proposition 6.3 (Allocation). Suppose every unit draws nn rollouts and there are QQ units, for a total of N=QnN=Qn rollouts, with σB2>0\sigma_B^2>0. The variance of the pooled estimator θ^=Q−1∑qUq\hat{\theta}=Q^{-1}\sum_q U_q is

Var⁡(θ^)=σB2+σW2/nQ=nσB2+σW2N,\operatorname{Var}(\hat{\theta})=\frac{\sigma_B^2+\sigma_W^2/n}{Q}=\frac{n\sigma_B^2+\sigma_W^2}{N},

which is strictly increasing in nn. Under a pure rollout budget NN, the variance-minimizing allocation is therefore n=1n=1: one rollout per unit, spread over as many units as possible. If instead each unit carries a

fixed prefill/encoding cost cp>0c_p > 0 and each rollout a cost cr>0c_r > 0, with total cost C=Q(cp+ncr)C = Q(c_p + nc_r) held fixed, the optimum is

ncontinuous⋆=cpcr⋅σW2σB2=cpcr⋅1−ρρ.n^\star_{\mathrm{continuous}} = \sqrt{\frac{c_p}{c_r}\cdot\frac{\sigma_W^2}{\sigma_B^2}} = \sqrt{\frac{c_p}{c_r}\cdot\frac{1-\rho}{\rho}}.

The feasible minimizer over integer n≥1n \ge1 is obtained by comparing the admissible integers nearest max⁡{1,ncontinuous⋆}\max\{1,n^\star_{\mathrm{continuous}}\}.

Proof. The first display is Var⁡(Uq)/Q\operatorname{Var}(U_q)/Q with Var⁡(Uq)=σB2+σW2/n\operatorname{Var}(U_q) = \sigma_B^2 + \sigma_W^2/n and Q=N/nQ = N/n; monotonicity in nn is immediate. For the two-cost model, substitute Q=C/(cp+ncr)Q = C/(c_p + nc_r) into Var⁡(θ^)=(σB2+σW2/n)/Q\operatorname{Var}(\hat{\theta}) = (\sigma_B^2 + \sigma_W^2/n)/Q to obtain Var⁡(θ^)=C−1(σB2+σW2/n)(cp+ncr)\operatorname{Var}(\hat{\theta}) = C^{-1}(\sigma_B^2 + \sigma_W^2/n)(c_p + nc_r); differentiating in nn and setting the derivative to zero gives crσB2=cpσW2/n2c_r\sigma_B^2 = c_p\sigma_W^2/n^2, i.e. ncontinuous⋆=(cp/cr)(σW2/σB2)n^\star_{\mathrm{continuous}} = \sqrt{(c_p/c_r)(\sigma_W^2/\sigma_B^2)}, and σW2/σB2=(1−ρ)/ρ\sigma_W^2/\sigma_B^2 = (1-\rho)/\rho by Proposition 3.2.

Remark 6.4 (Correcting the naive intuition). The instinct that more rollouts per prompt always helps is wrong for the population null: under a pure rollout budget it strictly hurts, because rollouts past the first are correlated and contribute less than independent units. Extra rollouts per unit pay off only to amortize a genuine per-unit cost, and even then only up to ncontinuous⋆∝(1−ρ)/ρn^\star_{\mathrm{continuous}} \propto\sqrt{(1-\rho)/\rho}, which shrinks as correlation grows.

Unknown and Beyond Exchangeability

Unknown ρ\rho. Realized-null validity (Theorem 4.2) needs no knowledge of ρ\rho; it follows purely from exchangeability. Population validity (Theorem 6.2) also holds for any fixed λ\lambda regardless of ρ\rho, since it conditions only on independence across units. What depends on ρ\rho is efficiency: the optimal betting fraction and allocation involve Var⁡(Uq)=σB2+σW2/n\operatorname{Var}(U_q) = \sigma_B^2 + \sigma_W^2/n, which is unknown when ρ\rho is. We therefore recommend a variance-adaptive bet at the unit level, such as an empirical-Bernstein betting fraction in the style of Waudby-Smith & Ramdas [2024], or the Catoni construction of Wang & Ramdas [2023] for heavy-tailed summaries, which is valid without a variance bound and adapts λ\lambda to the realized spread of the UqU_q. This keeps the population guarantee exact while letting the procedure learn the correlation it faces.

Beyond exchangeability. The conditioning argument of § 4 uses Assumption 3.13: a single latent state drawn once per unit, with conditional independence given ZZ. It does not cover arbitrary serial dependence within a unit. When YtY_t depends on Yt−1Y_{t-1} in an unrestricted way, there is no ZZ to condition on and the supermartingale property is not recovered by enlarging the filtration. Handling that regime requires either a mixing or near-epoch-dependence rate on the within-unit process, or a block construction that forms approximately independent summaries from contiguous blocks of rollouts. This is the natural point of contact with dependence-robust inference (HAC/near-epoch-dependent estimation), and we flag it as the principal open direction rather than claim it solved.

Experiments

We report three studies. A controlled simulation confirms every theoretical claim and exhibits the over-certification mechanism and its repair (§ 8.1). We then measure the across-prompt ρ\rho on two real benchmarks chosen to straddle the boundary: GSM8K, where a strong model is nearly always self-consistent, and AIME, where it is not (Section 8.2), and on AIME exhibit the over-certification occurring and the prompt-level remedy correcting it (§ 8.3). All runs fix SEED = 456; difficulty is read off a pilot slice of rollouts and every estimate is computed on a disjoint held-out slice, so selecting on difficulty cannot bias θ\theta, π\pi, or ρ\rho.

Synthetic validation of the mechanism

We generate latent-belief rollouts: a per-unit belief μ(Z)\mu(Z) is drawn from a mixture calibrated to ρ=0.09\rho= 0.09, and conditional on it the increments are sampled i.i.d. We estimate ρ\rho by the one-way ANOVA intraclass correlation, track Var⁡(Yˉn)\operatorname{Var}(\bar{Y}_n) and neffn_{\mathrm{eff}}, and run both the single-unit certificate and the prompt-level remedy.

QuantitySingle-unit certificatePrompt-level remedy
Recovered ρ\rho (ICC)0.091 (planted 0.091)
Var⁡(Yˉn)\operatorname{Var}(\bar{Y}_n) limit0.090=σB20.090 = \sigma_B^2 (saturates)
neffn_{\mathrm{eff}} limit≈11≈1/ρ\approx11 \approx1/\rho
Realized-null Type I0.005N/A
Population-null certification rate0.32 (→π=0.37\to\pi= 0.37)0.033 at θ=0\theta= 0

Table 2. Synthetic study (population null true, θ≤0\theta\le0, π=0.37\pi= 0.37, planted ρ=0.09\rho= 0.09). The single-unit certificate controls the realized null but over-certifies the population null toward π\pi; the prompt-level remedy restores population validity, including at the least-favorable θ=0\theta= 0.

The numbers track the theory exactly: the ICC recovers the planted ρ\rho (Proposition 3.2); Var⁡(Yˉn)\operatorname{Var}(\bar{Y}_n) flattens onto σB2\sigma_B^2 and neffn_{\mathrm{eff}} caps near $1/\rho$ (Theorem 5.1); the single-unit certificate holds the realized null far below ϵ=0.05\epsilon= 0.05 while certifying the population null at 0.32 and climbing toward π=0.37eventhough\pi= 0.37 even though\theta \le 0$ (Proposition 4.5); and the prompt-level construction restores validity, sitting at 0.033 ≤0.05\le0.05 at the binding θ=0\theta= 0 (Theorem 6.2). The conservativeness (<ϵ< \epsilon) is expected of anytime-valid tests and is not under-powering. Under a pure rollout budget the variance is minimized at one rollout per unit, and the (cp/cr)(1−ρ)/ρ\sqrt{(c_p/c_r)(1-\rho)/\rho} rule appears only under the two-cost model (Proposition 6.3).

Measuring ρ\rho on two real benchmarks

The synthetic study sets ρ\rho by hand. Two empirical questions determine whether the theoretical gap has practical consequences: whether ρ>0\rho> 0 on real models, and, separately, whether the population null (θ≤0\theta\le0) ever holds alongside π>0\pi> 0.

We measure the across-prompt ρ\rho on two benchmarks with a single production model (Claude Haiku 4.5) at temperature 1: GSM8K [1] and AIME [AIME, 1983–2024]. For each prompt a pilot slice fixes the leader and the prompt’s difficulty; the disjoint held-out rollouts are scored ±1\pm1 against that fixed leader; and ρ\rho is the one-way ICC on the held-out matrix with a cluster-bootstrap interval (resample prompts, recompute the ICC, take the 2.5/97.5 percentiles). The split removes the data-adaptive-leader bias of scoring against a leader chosen from the same rollouts.

Two readings. First, the premise holds on both benchmarks: ρ^=0.44\hat{\rho} = 0.44 on GSM8K and 0.48 on AIME, with effective per-prompt sample sizes of only about two. By Theorem 5.1 this is a budgeting fact independent of difficulty, since the diminishing-returns effect depends on the intraclass correlation and does not establish a hard cutoff after three rollouts. Second, and this is what GSM8K alone could not show, the two benchmarks sit on opposite sides of the boundary. On GSM8K θ^=+0.96\hat{\theta} = +0.96: the model is so self-consistent that realized and population conclusions agree for essentially every prompt, and the gap of Proposition 4.5, though present (ρ>0\rho> 0), has nothing to act on. This holds in aggregate across difficulty: 283 of 300 prompts are unanimous and only 17 fall below pilot agreement 0.9 (too few to certify either way), with held-out plurality accuracy 0.97, so no GSM8K regime with appreciable mass approaches the boundary, and in contrast to AIME, where binning by pilot agreement sweeps θ\theta from −0.70 to +0.97 (Table 5). On AIME the model scatters; its pilot-selected answer receives less than half of held-out answers on average, so θ^=−0.15<0\hat{\theta} = -0.15 < 0 with π^=0.33\hat{\pi} = 0.33, indicating an estimated negative population drift, while about one-third of prompts have positive observed held-out margins. The held-out plurality matches the ground-truth answer in only 38% of AIME prompts, consistent with θ<0\theta< 0 reflecting genuinely low reliability rather than an artifact of leader selection. (Accuracy and the self-consistency margin θ\theta are related but distinct: a model can be confidently consistent on a wrong answer, so 40% accuracy bounds difficulty, not θ\theta directly.)

Pilot-agreement binnnθ^\hat{\theta}π^\hat{\pi}ρ^\hat{\rho}single-unit rate
[0.0, 0.3]60-0.700.030.110.00
(0.3, 0.5]37-0.340.160.140.03
(0.5, 0.7]16-0.140.250.110.06
(0.7, 0.9]11+0.741.000.070.73
(0.9, 1.0]26+0.971.000.041.00

Table 5. AIME by difficulty (pilot-agreement bins; estimates on held-out). As difficulty falls (left to right), θ\theta sweeps from −0.70-0.70 to +0.97+0.97 while π\pi and the single-unit certification rate track the realized side. The drift crosses zero between the (0.5, 0.7] and (0.7, 0.9] bins, where the single-unit rate jumps from 0.06 to 0.73.

Benchmark (prompts ×\times rollouts)ρ^\hat{\rho} (95% CI)1/ρ^1/\hat{\rho}θ^\hat{\theta}π^\hat{\pi}median agr.
GSM8K (300 ×\times 30)0.435 [0.208, 0.619]2.3+0.960.991.00
AIME (150 ×\times 30)0.480 [0.405, 0.544]2.1−0.150.330.30

Table 3. Across-prompt correlation and the boundary, two benchmarks (Claude Haiku 4.5, temperature 1, split-sample leader). On both, ρ^\hat{\rho} is bounded well away from zero. The benchmarks differ in θ\theta: GSM8K is easy and the leader is strongly favored on average, so the realized–population gap is structurally present but operationally invisible; AIME is hard and the leader is not favored on average, placing the negative estimated population margin and positive estimated π\pi, the regime where over-certification can occur. Both intervals are cluster bootstraps over prompts, B=2000B = 2000 (Remark 8.1).

Remark 8.1 (Inference caveat). On easy prompts the ±1\pm1 scores pile at the boundary (GSM8K median agreement 1.00), violating the within-group normality the classical FF-based interval assumes. We therefore report cluster bootstraps for both benchmarks: resample prompts with replacement, recompute the ICC, take the 2.5/97.5 percentiles, which serves as the defensible interval for clustered, non-normal scores.

Remark 8.2 (Interpretation of empirical margins). The reported θ^\hat{\theta} averages held-out scores over sampled prompts and pilot-selected leaders. The fraction π^\hat{\pi} classifies units by the sign of their finite-sample held-out mean, and is therefore a descriptive proxy for P(μ(Z)>0)\mathop{\mathrm{P}}(\mu(Z) > 0) rather than an error-free estimate of latent signs. In particular, a percentage of promptwise crossings is not an estimate of the Type I error rate for a population test: repeated independent realizations under a specified population-null law would be needed to estimate that rate. The prompt-bootstrap crossing frequency is likewise a descriptive resampling statistic, not a proof of the nominal size bound.

Over-certification, exhibited and repaired (AIME)

On AIME we run the single-unit betting certificate on each prompt’s held-out stream and the prompt-level certificate across prompts, at ϵ=0.05\epsilon= 0.05.

The contrast in Table 4 is the central empirical result. The estimated population margin is negative on AIME (θ^=−0.15\hat{\theta} = -0.15): the model’s pilot-selected answer is not, on average, favored in held-out rollouts. Yet, used as a test of the population null, the single-unit certificate produces crossings on 24.0% of individual prompts, exceeding the nominal ϵ=0.05\epsilon= 0.05 population-test level numerically, while the prompt-level certificate, which accumulates one near-independent summary per prompt, declines in these prompt-bootstrap resamples (observed rate 0.000). Table 5 and Figure 1 show the mechanism: the single-unit crossings come entirely from the high-agreement prompts, on which the model is confidently consistent, while the large mass of scattered hard prompts pulls the population drift negative. The drift crosses zero between the middle bins, where the single-unit rate jumps from 0.06 to 0.73.

Quantity (whole benchmark; θ^=−0.15\hat{\theta} = -0.15, π^=0.33\hat{\pi} = 0.33)Rate
Single-unit certification rate (per prompt)0.240
Prompt-level population certification rate (bootstrap)0.000
Nominal level ϵ\epsilon0.05

Table 4. Over-certification on AIME (Claude Haiku 4.5, 150 prompts). At the whole-benchmark level the estimated population margin is negative (θ^=−0.15\hat{\theta} = -0.15), yet single-unit certificates fire on nearly one prompt in four, while the prompt-level remedy declines.

AIME: population drift collapses on hard prompts while the single-unit certificate fires only on the easy tail

Figure 1. The empirical wedge on AIME. Across pilot-agreement bins (hard at left, easy at right): mean held agreement (θ+1)/2(\theta+ 1)/2 and π=P(μq>0)\pi= \mathrm{P}(\mu_q > 0) rise together, while the single-unit certification rate stays near zero across the low-agreement bins, which hold most of the mass and pull the population drift to θ^=−0.15\hat{\theta} = -0.15, and climbs to 1.00 only on the high-agreement minority. That minority is the 24% the single-unit certificate fires on, even though the estimated population margin is negative.

Reading the contrast correctly. The 24.0% of single-unit certifications are not errors in the realized sense. By Theorem 4.2 each crossing is covered by a test whose error probability is controlled under its realized null; no individual crossing proves that its alternative is true; crossings on such prompts may reflect positive realized margins, but their latent signs cannot be determined exactly from the finite held-out samples. The data bear this out directly: among the 101 prompts with nonpositive estimated held-out means not one single-unit certificate fires (0/101), a descriptive observation consistent with realized-null validity, and the entire 24.0% comes from the 49 prompts with positive estimated held-out means (firing rate 0.74), which should not be equated with proof of true positive conditional means. The over-certification is relative to the population null: reading those certifications as evidence that the model is reliable on AIME is the error, because the estimated average leader-versus-complement margin is negative. A single-prompt certificate answers a narrower question than a deployment-level reliability claim, and under ρ=0.48\rho= 0.48 the two diverge by enough that the aggregate single-unit certification rate (0.24) bears no relation to the nominal ϵ\epsilon. The prompt-level construction targets the population null directly; its lack of observed crossings is consistent with, but does not establish, the validity theorem.

Regime dependence, empirically. GSM8K and AIME together make the point that neither makes alone: the realized–population gap is one phenomenon with two faces. On an easy task with a strong model it is structurally present (ρ=0.44\rho= 0.44) but dormant, because θ\theta is far from the boundary; on a hard task it is empirically salient (ρ^=0.48\hat{\rho} = 0.48, θ^<0\hat{\theta} < 0), with promptwise crossings on 24% of sampled prompts despite a negative mean held-out margin. The distinction matters exactly where reliability is genuinely in question.

Scope of the measurement. We measure the across-prompt ρ\rho; the within-prompt shared-prefix ρ\rho, which threatens even single-prompt certificates, requires tree-of-thought or prefix-shared generation and is not measured here. The reported runs use a single named production model; a reproducible open-model replication (e.g. on gpt-oss-20b or Qwen3-30B) is the natural robustness check but could alter the estimated magnitudes and even the qualitative pattern.

Protocol and reproducibility

All runs fix SEED= 456 and query Claude Haiku 4.5 (snapshot claude-haiku-4-5-20251001) via the Anthropic Messages API at temperature 1.0 with 8 concurrent workers. GSM8K: the public test split [1], 300 prompts ×\times30 rollouts, max_tokens= 512, prompt “Solve the problem. Show brief reasoning, then end with a line ‘The answer is ⟨number⟩’.”; a pilot of 10 rollouts fixes the leader and the disjoint 20 held-out rollouts are scored. AIME: the 1983–2024 set [AIME, 1983–2024] (HuggingFace datasets-server, no token required), 150 integer-answer problems ×\times30 rollouts, max_tokens= 1024, prompt “Solve this AIME problem. The answer is an integer from 0 to 999. . . .”; a pilot of 10 rollouts fixes the leader and difficulty bin and the disjoint 20 held-out rollouts are scored ±1\pm1. Answers are extracted by a regular expression preferring an explicit “answer is” or \boxed{} field and otherwise the trailing integer. Both the single-unit and prompt-level certificates use the stitched betting mixture E=1∣Λ∣∑λ∈Λ∏t(1+λYt)E = \frac{1}{|\Lambda|}\sum_{\lambda\in\Lambda}\prod_t(1+\lambda Y_t) over the grid Λ={0.1,0.2,0.3,0.4,0.5}\Lambda= \{0.1,0.2,0.3,0.4,0.5\}, rejecting when E≥1/ϵ=20E \ge1/\epsilon= 20 (ϵ=0.05\epsilon= 0.05); ρ\rho is the one-way ICC(1) with a cluster bootstrap over prompts (B=2000B = 2000). The source code and saved rollout matrices accompany this submission as supplementary material for peer review, and will be deposited in a public repository upon publication.

Discussion

What the guarantees do

They identify the hypothesis. The central service of this paper is not a new certificate but a clarification: under correlation, an anytime-valid self-consistency certificate controls the realized null (Theorem 4.2), an exact and useful guarantee for single-query decisions, and silently differs from the population null by ρ\rho. Naming which claim is being made is the prerequisite for trusting it.

They remain anytime-valid. Both the realized-null reading and the prompt-level population construction are exact and finite-sample, holding at data-dependent stopping times. The repair changes the index of accumulation, not the underlying Ville machinery.

They are honest about budget. The effective-sample-size cap 1/ρ1/\rho converts a vague intuition into a number: with ρ^≈0.45\hat{\rho} \approx0.45, a single prompt is worth only about two independent rollouts for the population question, no matter how many one draws.

What they do not

No guarantee under arbitrary serial dependence. The exchangeable latent-belief model is the working assumption; unrestricted within-unit serial dependence is open (§ 7).

No detection guarantee. As in the independent theory, Type I control is not power: near the boundary θ≈0\theta\approx0, certification of the population null may require many units.

Practical impact is regime-dependent On easy benchmarks with strong models the realized–population gap, though structurally present (ρ>0\rho> 0), is operationally small because θ\theta is large; the distinction matters most where reliability is genuinely in question.

Limitations and future work

The real-data study measures the across-prompt ρ\rho; the within-prompt shared-prefix ρ\rho, which threatens even single-prompt certificates, requires tree-of-thought or prefix-shared generation and is not measured here. The over-certification is demonstrated on AIME, where the estimated population margin is negative (θ^<0\hat{\theta} < 0) and single-unit certificates fire on 24% of the observed prompts while the prompt-level procedure does not cross; a reproducible open-model replication is the natural robustness check. A hierarchical (prefix-tree) correlation model would refine Theorem 5.1’s constant for branching rollouts, and the serial-dependence extension via mixing/near-epoch-dependence rates is the principal theoretical opening. We regard the present contribution as resolving the identification question of which reliability an anytime-valid certificate certifies under correlation, isolating the conditions under which over-certification materializes, and providing the construction that restores the population guarantee when that is the target.

References

  1. [1]Cobbe, K., Kosaraju, V., Bavarian, M., Chen, M., Jun, H., Kaiser, Ł., Plappert, M., Tworek, J., Hilton, J., Nakano, R., Hesse, C., & Schulman, J. (2021). Training verifiers to solve math word problems. arXiv:2110.14168.arxiv.org/abs/2110.14168
  2. [2]Akter, S. N., Shihab, I. F., & Sharma, A. (2025). Anytime-valid answer sufficiency certificates for LLM generation via sequential information lift. arXiv:2510.06478.arxiv.org/abs/2510.06478
  3. [4]Kish, L. (1965). Survey Sampling. Wiley, New York.
  4. [5]Ota, H., Iwase, N., Ichihara, Y., Komiyama, J., & Imaizumi, M. (2026). CITE: Anytime-valid statistical inference in LLM self-consistency. arXiv:2605.05873.arxiv.org/abs/2605.05873
  5. [6]Cordero-Encinar, P. & Duncan, A. B. (2025). Certified self-consistency: Statistical guarantees and test-time training for reliable reasoning in LLMs. arXiv:2510.17472.
  6. [7]Dey, M. & Bhandari, S. K. (2023). Asymptotically optimal sequential multiple testing procedures for correlated normal. arXiv preprint arXiv:2309.16657.arxiv.org/abs/2309.16657
  7. [8]Howard, S. R., Ramdas, A., McAuliffe, J., & Sekhon, J. (2021). Time-uniform, nonparametric, nonasymptotic confidence sequences. The Annals of Statistics, 49(2), 1055–1080.DOI
  8. [9]Ramdas, A., Grinwald, P., Vovk, V., & Shafer, G. (2023). Game-theoretic statistics and safe anytime-valid inference. Statistical Science, 38(4), 576–601.arxiv.org/abs/2210.01948
  9. [10]Robbins, H. (1970). Statistical methods related to the law of the iterated logarithm. The Annals of Mathematical Statistics, 41(5), 1397–1409.
  10. [11]Ville, J. (1939). Étude critique de la notion de collectif. Gauthier-Villars, Paris.
  11. [13]Wang, X., Wei, J., Schuurmans, D., Le, Q., Chi, E., Narang, S., Chowdhery, A., & Zhou, D. (2023). Self-consistency improves chain of thought reasoning in language models. ICLR.arxiv.org/abs/2203.11171

Paper details

vlnc:W_9fw8maeu
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents