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 . 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 , potentially exceeding nominal ; (iii) the within-unit mean's effective sample size saturates at , 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 (, ) the gap is dormant, whereas on AIME (, ) the single-unit rule crosses on 24% of prompts at nominal , 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 , 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.
A dependent evidence model (§ 3). We transport the random-effects / intraclass correlation model from clustered data to the reasoning stream: a latent state is drawn once per certification unit, with rollouts conditionally i.i.d. given . This induces exchangeable, equicorrelated increments with correlation , where and denote the between- and within-unit variances. Consequently, the single null splits into a realized null (, governing the unit’s conditional mean) and a population null (, governing the overall mean).
Which null is controlled (§ 4). The standard betting e-process is not a supermartingale under the population null because the data eventually reveal , so the marginal validity argument breaks whenever the fraction of units with positive realized drift satisfies
. 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 , potentially exceeding the nominal error level Proposition 4.5.
An impossibility (Section 5). For the within-unit sample mean, the variance-equivalent effective sample size tends to Theorem 5.1; the within-unit mean converges to the realized belief , and does not in general converge to the population drift . Without additional structural information or independent units, a realized-null certificate does not yield a population-null guarantee.
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.
Unknown and beyond exchangeability (Section 7). Realized-null validity needs no knowledge of ; population validity under unknown 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.
Measurement (Section 8). Simulation confirms the mechanism and its repair. On real rollouts (Claude Haiku 4.5) we measure the across-prompt on two benchmarks: GSM8K (), where strong self-consistency () leaves the gap dormant, and AIME (, ), 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 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 , 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 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 and serial dependence. Section 8 reports simulations and the measured . 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 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 adapted to a filtration is a supermartingale if almost surely for all .
Theorem 2.2 [11]. If is a non-negative supermartingale with , then for any threshold , .
Definition 2.3 (Test supermartingale). A test supermartingale (the canonical form of an e-process) for a null is a non-negative supermartingale under with .
Corollary 2.4 (Anytime-valid test). If is a test supermartingale under , the rule that rejects at satisfies , regardless of when or whether one stops.
The value is the “evidence against ” accumulated by stage . Corollary 2.4 is immediate: and Theorem 2.2 applies with .
Two baseline constructions
For self-consistency [13], fix a candidate answer using a separate pilot sample. One possible increment compares with a fixed runner-up : , with population margin . Our experiments instead compare with its complement: , with mean . Both statistics satisfy , and the martingale arguments below apply to either after fixing the statistic. Unless stated otherwise, , (the conditional mean, formalized in § 3), and (the population drift) refer to the leader-versus-complement statistic used in the experiments. The null is .
Beta-mixture (Martingale Majority Certificate). Cordero-Encinar & Duncan [2025] place a Beta prior on the leader probability over the alternative and form the mixture likelihood-ratio process relative to , which is a martingale at (and a supermartingale for ) and crosses at the boundary .
Betting / Robbins-stitched. For a betting fraction , the product satisfies when , hence is a supermartingale; mixing over a geometric grid [10, 8] yields the law-of-the-iterated-logarithm boundary . 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 versus boundary gap, is orthogonal to our question and we do not pursue it. Both are valid test supermartingales for under independence; our concern is what “” 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 with cumulative evidence . A latent state , taking values in a measurable space , is drawn once at the start of the unit. Conditional on , the increments are independent and identically distributed with
We collect the marginal moments that govern the process:
Here is the population drift, the between-unit variance (dispersion of the belief), the mean within-unit variance, and 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 ; it is what a certificate actually sees. The oracle filtration additionally resolves the latent state. Crucially, : the decision-maker never observes the belief, only its noisy consequences.
Proposition 3.2 (Exchangeability and equicorrelation). Under Definition 3.1 with , the increments are exchangeable, and for every ,
The common pairwise correlation is exact, irrespective of any heterogeneity in the conditional variances .
Proof. Exchangeability is immediate from conditional i.i.d. structure. For , the law of total covariance and conditional independence give
Dividing by the marginal variance yields .
Proposition 3.3 (Variance of the within-unit mean). Let . Under Definition 3.1 with ,
with the convention when .
Proof. By Proposition 3.2, . Substituting and gives , hence the stated .
Proposition 3.3 is the seed of the impossibility result in § 5: when , averaging within a single unit cannot drive the variance below , so the within-unit mean is a consistent estimator of the realized belief , not of the population drift .
Remark 3.4 (Recovery of the independent model). iff iff almost surely. In that case the latent state is degenerate, and 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 special case of what follows.
Remark 3.5 (Why the observed filtration misbehaves). Under the oracle filtration the conditional mean is constant, . Under the observed filtration it is the posterior mean of the belief given the data, , which is not constant in and converges to 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,
The realized null concerns the drawn belief,
Remark 3.7 (Equivalence only at ). Since a.s. iff iff , the two nulls are equivalent precisely when the increments are uncorrelated. Whenever 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 , and conflating them is the error this paper is about.
Definition 3.8 (Realized-alternative probability). Write for the probability that the realized belief favors the certified outcome.
Under with one may still have : the average belief disfavors the outcome while individual draws favor it. This wedge between and 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 be the answer selected on an independent pilot sample and fix it before the held-out evidence stream begins. In the empirical implementation , with . Its conditional mean is ; a positive value means that 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 index the prompt together with its terminal answer distribution, drawn from the task distribution; conditional on the held-out rollouts are independent, with the leader-versus-complement margin for that prompt. The population drift , incorporating the random pilot-selection procedure, is the average margin over the task. Thus states that a pilot-selected answer has probability at most one half on average. Here measures how much the leader margin varies across prompts relative to within-prompt sampling noise.
Shared latent within a prompt. Let 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 the continuations are independent, but marginally they are correlated through the shared prefix. Even a single-prompt certificate then accumulates evidence about , 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, , and the certificate controls the corresponding fixed-candidate margin ( 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 is fixed from a separate pilot slice of rollouts (as in § 8), the held-out score is . The realized mean 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 averages this score across freshly drawn prompts and their corresponding random pilots. Fixing 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 .
Assumptions
We restate the regularity conditions of § 2 conditionally on the latent state.
Assumption 3.11 (Conditional sub-Gaussian increments). There exists such that for all and ,
Remark 3.12. Assumption 3.11 holds for bounded increments with by Hoeffding’s lemma applied conditionally on . It governs concentration within a unit; the between-unit dispersion 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 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 .
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 ; governs only efficiency (betting fraction and allocation).
| Result | Target | Filtration | Dependence | Type |
| Thm 4.2 (realized validity) | oracle (cond. on ) | exchangeable | finite-sample, anytime | |
| Prop 4.5 (over-certification) | observed | exch., | asymptotic lower bound | |
| Thm 5.1 (saturation) | estimation of | observed | exch., | exact variance, a.s. limit |
| Thm 6.2 (remedy) | unit-level | indep. across units | finite-sample, anytime |
Table 1.
The marginal supermartingale property fails
Consider the betting e-process with applied to the observed stream. Under the population null one might hope is an -supermartingale, as in § 2. It is not.
Proposition 4.1 (Failure under the population null). Under Definition 3.1, suppose but . Then with is not an -supermartingale under . If instead almost surely (so ), the conditioning argument of Theorem 4.2 shows is a supermartingale and no failure occurs; thus is the operative condition, not alone.
Proof. By Remark 3.5, , the posterior mean of given the data. Hence . On the event that the observed history favors a positive belief, which has positive probability whenever , the posterior mean is positive even though , so there. The supermartingale inequality is violated, so Ville’s inequality cannot be invoked under on the observed filtration.
The break is not pathological: it is the process learning the realized belief. The repair is to condition on .
Validity for the realized null
Theorem 4.2 (Realized-null validity). Let be the betting e-process with , or its stitched mixture over a fixed grid of such , built from the increments , and . Under Definition 3.1,
That is, the procedure is an exact, anytime-valid test of the realized null .
Proof. Work on the oracle filtration . Conditional on with , the increments are i.i.d. with non-positive mean, so for the betting process and is a non-negative -supermartingale with under . (For the stitched mixture the same holds by convexity: it is an average over a fixed grid of of conditional supermartingales, and a convex combination of conditional supermartingales is one.) Ville’s inequality applied conditionally gives for a.e. such . Averaging the conditional bound over yields , and multiplying by 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 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 , so that the mixture is a test supermartingale for the conditional law given . 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 . 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 holds () but . For a fixed let and . The betting process then satisfies
In particular, let decrease to zero and let with . The mixture satisfies
These crossing probabilities refer to the population-null data-generating law and need not be bounded by . The second conclusion does not necessarily hold for a fixed finite betting grid.
Proof. Conditional on , bounded increments are i.i.d. For each fixed , the strong law gives almost surely. Hence on , establishing the first claim. If , then and . Thus some sufficiently small positive has . The positive-weight term then diverges, and so does . Integrating this conditional almost-sure statement over and using continuity from below gives the second bound.
Remark 4.6 (Lower bound, not equality). The lower bound applies to the countable mixture specified in Proposition 4.5, not necessarily to the finite grid used in the experiments. On realized-negative units (), conditional supermartingale validity bounds additional crossing probability by at most . 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 , a quantity unrelated to the nominal level .
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 ; alone does not determine . A certificate calibrated to may have a population-null crossing rate much larger than , 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 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 :
almost surely, and ; the within-unit mean is consistent for the realized belief and is not a consistent estimator of .
The variance-equivalent effective sample size for the within-unit sample mean is . This is a design-effect calculation for that estimator, not a universal information bound for every estimator or structured parametric model.
Proof. Conditional on , the increments are i.i.d. with mean , so the strong law gives a.s.; the variance statement and are Proposition 3.3. Since is non-degenerate when , does not converge to the constant .
Corollary 5.2 (Single-unit budget guarantees are vacuous for the population null). The high-probability budget guarantee of the independent theory—“with probability the certificate stops within rollouts”—bounds the time to resolve the realized drift . As a statement about the population drift it is vacuous as grows: additional samples from the same unit reduce negligibly and add essentially no information about .
Remark 5.3 (The design effect). Theorem 5.1 is the cluster-sampling design effect [4] 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 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 (e.g. distinct prompts drawn from the task). For unit draw rollouts and form the within-unit mean . The are independent across with and .
Theorem 6.2 (Population validity). For a betting fraction , the prompt-level process is a non-negative supermartingale under with . Hence satisfies as an exact, anytime-valid test of the population null. Mixing over a geometric grid recovers the law-of-the-iterated-logarithm boundary in the number of units .
Proof. Let . The are independent with mean , so when ; the supermartingale property and follow, and Corollary 2.4 gives the bound. The stitched mixture over applies unchanged at the unit level.
The key shift is the index: evidence is accumulated over units, each contributing a single near-independent summary , 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 rollouts and there are units, for a total of rollouts, with . The variance of the pooled estimator is
which is strictly increasing in . Under a pure rollout budget , the variance-minimizing allocation is therefore : one rollout per unit, spread over as many units as possible. If instead each unit carries a
fixed prefill/encoding cost and each rollout a cost , with total cost held fixed, the optimum is
The feasible minimizer over integer is obtained by comparing the admissible integers nearest .
Proof. The first display is with and ; monotonicity in is immediate. For the two-cost model, substitute into to obtain ; differentiating in and setting the derivative to zero gives , i.e. , and 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 , which shrinks as correlation grows.
Unknown and Beyond Exchangeability
Unknown . Realized-null validity (Theorem 4.2) needs no knowledge of ; it follows purely from exchangeability. Population validity (Theorem 6.2) also holds for any fixed regardless of , since it conditions only on independence across units. What depends on is efficiency: the optimal betting fraction and allocation involve , which is unknown when 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 to the realized spread of the . 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 . It does not cover arbitrary serial dependence within a unit. When depends on in an unrestricted way, there is no 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 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 , , or .
Synthetic validation of the mechanism
We generate latent-belief rollouts: a per-unit belief is drawn from a mixture calibrated to , and conditional on it the increments are sampled i.i.d. We estimate by the one-way ANOVA intraclass correlation, track and , and run both the single-unit certificate and the prompt-level remedy.
| Quantity | Single-unit certificate | Prompt-level remedy |
| Recovered (ICC) | 0.091 (planted 0.091) | |
| limit | (saturates) | |
| limit | ||
| Realized-null Type I | 0.005 | N/A |
| Population-null certification rate | 0.32 () | 0.033 at |
Table 2. Synthetic study (population null true, , , planted ). The single-unit certificate controls the realized null but over-certifies the population null toward ; the prompt-level remedy restores population validity, including at the least-favorable .
The numbers track the theory exactly: the ICC recovers the planted (Proposition 3.2); flattens onto and caps near $1/\rho$ (Theorem 5.1); the single-unit certificate holds the realized null far below while certifying the population null at 0.32 and climbing toward \theta \le 0$ (Proposition 4.5); and the prompt-level construction restores validity, sitting at 0.033 at the binding (Theorem 6.2). The conservativeness () 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 rule appears only under the two-cost model (Proposition 6.3).
Measuring on two real benchmarks
The synthetic study sets by hand. Two empirical questions determine whether the theoretical gap has practical consequences: whether on real models, and, separately, whether the population null () ever holds alongside .
We measure the across-prompt 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 against that fixed leader; and 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: 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 : 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 (), 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 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 with , 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 reflecting genuinely low reliability rather than an artifact of leader selection. (Accuracy and the self-consistency margin are related but distinct: a model can be confidently consistent on a wrong answer, so 40% accuracy bounds difficulty, not directly.)
| Pilot-agreement bin | single-unit rate | ||||
| [0.0, 0.3] | 60 | -0.70 | 0.03 | 0.11 | 0.00 |
| (0.3, 0.5] | 37 | -0.34 | 0.16 | 0.14 | 0.03 |
| (0.5, 0.7] | 16 | -0.14 | 0.25 | 0.11 | 0.06 |
| (0.7, 0.9] | 11 | +0.74 | 1.00 | 0.07 | 0.73 |
| (0.9, 1.0] | 26 | +0.97 | 1.00 | 0.04 | 1.00 |
Table 5. AIME by difficulty (pilot-agreement bins; estimates on held-out). As difficulty falls (left to right), sweeps from to while 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 rollouts) | (95% CI) | median agr. | |||
| GSM8K (300 30) | 0.435 [0.208, 0.619] | 2.3 | +0.96 | 0.99 | 1.00 |
| AIME (150 30) | 0.480 [0.405, 0.544] | 2.1 | −0.15 | 0.33 | 0.30 |
Table 3. Across-prompt correlation and the boundary, two benchmarks (Claude Haiku 4.5, temperature 1, split-sample leader). On both, is bounded well away from zero. The benchmarks differ in : 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 , the regime where over-certification can occur. Both intervals are cluster bootstraps over prompts, (Remark 8.1).
Remark 8.1 (Inference caveat). On easy prompts the scores pile at the boundary (GSM8K median agreement 1.00), violating the within-group normality the classical -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 averages held-out scores over sampled prompts and pilot-selected leaders. The fraction classifies units by the sign of their finite-sample held-out mean, and is therefore a descriptive proxy for 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 .
The contrast in Table 4 is the central empirical result. The estimated population margin is negative on AIME (): 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 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; , ) | Rate |
| Single-unit certification rate (per prompt) | 0.240 |
| Prompt-level population certification rate (bootstrap) | 0.000 |
| Nominal level | 0.05 |
Table 4. Over-certification on AIME (Claude Haiku 4.5, 150 prompts). At the whole-benchmark level the estimated population margin is negative (), yet single-unit certificates fire on nearly one prompt in four, while the prompt-level remedy declines.

Figure 1. The empirical wedge on AIME. Across pilot-agreement bins (hard at left, easy at right): mean held agreement and 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 , 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 the two diverge by enough that the aggregate single-unit certification rate (0.24) bears no relation to the nominal . 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 () but dormant, because is far from the boundary; on a hard task it is empirically salient (, ), 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 ; the within-prompt shared-prefix , 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 30 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 30 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 . 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 over the grid , rejecting when (); is the one-way ICC(1) with a cluster bootstrap over prompts (). 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 . 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 converts a vague intuition into a number: with , 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 , 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 (), is operationally small because is large; the distinction matters most where reliability is genuinely in question.
Limitations and future work
The real-data study measures the across-prompt ; the within-prompt shared-prefix , 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 () 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]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]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
- [4]Kish, L. (1965). Survey Sampling. Wiley, New York.
- [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
- [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.
- [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
- [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
- [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
- [11]Ville, J. (1939). Étude critique de la notion de collectif. Gauthier-Villars, Paris.
- [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