In the quest to make Large Language Models (LLMs) more reliable, researchers have turned to "self-consistency"—sampling multiple reasoning paths and picking the majority answer. To do this efficiently, we need "anytime-valid" certificates: statistical tools that tell us exactly when we have enough evidence to stop sampling while guaranteeing a low error rate.
A new paper by Terence and Toneukarin Agbeyegbe reveals a hidden trap in these certificates. It turns out that the standard assumption—that each reasoning sample is independent—is often false in practice. This isn't just a minor statistical technicality; it fundamentally changes what the certificate is actually proving.
TL;DR
Standard reliability certificates for LLMs assume reasoning samples are independent, but real-world rollouts are often correlated due to shared prefixes or varying prompt difficulty. This correlation causes certificates to measure the reliability of a specific reasoning path (realized null) rather than the model's overall performance (population null), leading to massive over-certification of unreliable models on hard tasks.
What Problem Does This Paper Address?
When we query an LLM multiple times for the same prompt, we usually assume each "rollout" is an independent attempt. Based on this, we use "e-processes" (a type of sequential test) to stop sampling as soon as we are confident in the answer.
However, the authors point out two major ways independence fails:
- Shared Latents: In techniques like "tree-of-thought," rollouts might share a common reasoning prefix. They are only independent after that prefix is set.
- Across-Prompt Heterogeneity: If you are trying to certify a model's performance across a whole task, prompts vary in difficulty. This "between-unit" variance makes the pooled samples look correlated.
When samples are correlated, the "null hypothesis" (the thing we are trying to disprove) splits in two. Are we testing if the model is good on average (Population Null), or are we testing if this specific reasoning path it just took is good (Realized Null)? Standard methods accidentally target the latter, which can be dangerously misleading if your goal is to deploy a generally reliable system.
Methods
The authors introduce a Dependent Evidence Model using a random-effects structure. They model a latent state $Z$ (representing a prompt or a reasoning plan) that is drawn once. All rollouts for that unit are conditionally independent given $Z$, but marginally, they are equicorrelated with a correlation coefficient $\rho$.
Key theoretical contributions summarized in the paper include:
- Validity Dichotomy: Proving that standard betting-based certificates remain valid for the realized null but fail for the population null.
- Information Saturation: Showing that if $\rho > 0$, you hit a point of diminishing returns. No matter how many more samples you take from the same prompt, your effective sample size is capped at $1/\rho$.
- The Remedy: Proposing a prompt-level e-process that accumulates evidence across different independent prompts rather than within one.
Datasets
The researchers evaluated their findings using:
- GSM8K: A benchmark of grade-school math word problems (relatively easy for modern models).
- AIME: Problems from the American Invitational Mathematics Examination (significantly harder).
- Model: All real-world tests were performed using Claude Haiku 4.5 at temperature 1.0.
- Synthetic Data: Used to precisely validate the "information saturation" and "over-certification" mechanisms.
Key Insights and Ideas
- The "Aha" Moment on Correlation: Correlation doesn't just make your test slower; it changes the question the test is answering. A certificate might tell you "this specific answer is likely correct given the current reasoning path," while the model is actually failing the broader task.
- The $1/\rho$ Wall: This is a sobering result for "test-time scaling." If your reasoning paths are correlated (e.g., $\rho = 0.5$), taking 100 samples is statistically equivalent to taking only 2 independent ones. You cannot "sample your way out" of a bad reasoning prefix.
- Regime Dependence: The authors found that on easy tasks (GSM8K), the model is so consistent that this statistical gap is "dormant." But on hard tasks (AIME), the gap becomes a chasm.
- Counter-intuitive Budgeting: To certify a model's general reliability, the best strategy is often to take one rollout per prompt across many prompts, rather than many rollouts for a few prompts.
Key Results
The most striking results came from the AIME benchmark:
- The Failure: On AIME, Claude Haiku 4.5 had a negative population margin ($\hat{\theta} = -0.15$), meaning it was generally unreliable. However, the standard single-unit certificate fired on 24% of prompts, even though the target error rate ($\epsilon$) was set to only 5%. This is a massive "over-certification."
- The Fix: When the authors applied their proposed prompt-level remedy, the certification rate dropped to 0.00, correctly identifying that the model had not met the reliability threshold.
- Real-world Correlation: They measured $\hat{\rho} \approx 0.44$ on GSM8K and $\hat{\rho} \approx 0.48$ on AIME, confirming that high correlation is a standard feature of LLM reasoning rollouts.
Limitations and Future Work
- Serial Dependence: The current model assumes "exchangeable" rollouts (any two are equally correlated). It doesn't yet account for more complex serial dependencies where, for example, the 10th sample is more like the 9th than the 1st.
- Hierarchical Branching: Future work could extend this to "prefix-tree" models to better capture the structure of branching reasoning paths.
- Power vs. Control: While the paper ensures we don't certify bad models (Type I error control), it doesn't guarantee we will quickly certify good ones (Power), especially when the model's performance is near the decision boundary.
Summary updated