CS Paper Radar

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

Terence D. Agbeyegbe, Toneukarin G. Agbeyegbe

cs.AI stat.MEcs.LG ·submitted 2026-11-19 18:47 UTC · v1

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$. 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)$, potentially exceeding nominal $ε$; (iii) the within-unit mean's effective sample size saturates at $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 ($\hatρ=0.435$, $\hatθ=+0.96$) the gap is dormant, whereas on AIME ($\hatρ=0.480$, $\hatθ=-0.15$) the single-unit rule crosses on 24% of prompts at nominal $ε=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.

Closest papers

Nearest neighbours by meaning across the whole index.

Anytime-Valid PAC-Bayes Certificates for Adaptive Test-Time Scaling

cs.LG cs.CLstat.ML ·2026-11-16 ·Xiaoyu Li, Jiangxuan Long
top venue similarity 0.59
Abstract · Accepted at NeurIPS 2026. Xiaoyu Li and Jiangxuan Long contributed equally. 31 pages, 7 figures, 15 tables

Test-time scaling systems often choose how much to sample, which prompt to use, and which verifier or aggregation rule to trust after repeatedly inspecting a calibration set. Standard validation error bars are not valid after this adaptive selection. We model a test-time scaling recipe as a randomized predictor with a random cost and prove a time-uniform PAC-Bayes certificate that holds simultaneously over all calibration times, all posterior mixtures over recipes, and all data-dependent stopping rules. Thus the same event covers the recipe search that precedes deployment, not merely the fixed recipe finally reported. For a finite grid of budgets and verifiers, the penalty is the familiar $\log M/n$, which in the worst case no certificate valid after selection can avoid, while non-uniform priors and localized posterior mixtures can give sharper certificates for structured searches. We specialize the result to self-consistency and show a complementary margin law: plurality voting improves exponentially in the sample budget only on examples where the correct answer is the generator's unique mode; otherwise more compute can provably amplify errors. The same margin analysis yields an oracle water-filling law for compute allocation. A synthetic audit quantifies the optimism caused by adaptive budget selection, and a 192-example GSM8K audit using gpt-4.1-mini generations illustrates risk-cost reporting for a real inference pipeline. At scale, with two models on GSM8K and MATH-500, selected-best error bars fall below the out-of-split GSM8K risk in up to 22.5% of random splits at a nominal 5% while the certificate never does, and on the full GSM8K test split it tightens to 0.109 (held-out risk 0.039). The results give a lightweight, distribution-free way to report risk and compute claims for adaptive inference systems.

0.51

When Stale Constraints Go Unchecked: Budgeted Verification Failures in Inherited Agent Memory

cs.IR cs.AIcs.CL ·2026-08-26 ·Kazuki Nakayashiki
similarity 0.58
Abstract · 41 pages, 3 figures, 18 tables. v3: adds four prospectively frozen, externally deposited experiments (interleaved replication with a repaire…

Provenance links keep the evidence behind an inherited belief reachable; an agent with a verification budget must still choose which links to inspect. We study a consolidated memory that states a decision constraint and whose source record has since been superseded by a record that withdraws it: provenance is immutable, the current record has changed, and the memory is stale. In a controlled six-memory scenario with a budget of two records, sixteen language models rarely re-verified a constraint that read as settled: they inspected its provenance path in about one episode in five and, once the constraint had been superseded, produced stale-consistent decisions in 77.3%, 74.7% and 74.7% of episodes across a primary run, a replication and a held-out domain. Re-assigning one of the same two slots to the critical path removed most of them: +74.0, +72.7 and +61.3 points (positive in every model), +80.7 in a prospectively frozen interleaved replication with a repaired non-critical control, and +62.0 on a panel of 10 models from 9 organisations; a corrected re-run of the held-out scenario gave +73.3. The forced-critical policy uses experimenter knowledge of the critical path: it quantifies how much stale-decision risk the same budget can recover and is not a scheduler. Two further deposited experiments locate the failure and a remedy: in this store the constraint's path is selected in 17.0% of episodes at two slots and 88.7% at four of six (above uniform allocation), and at two slots a one-sentence, target-blind rule (prefer memories that state a limit on a candidate direction) moved the agent's own allocation onto the constraint's path and recovered the oracle contrast on decisions (+89.3 points) where that constraint limits the tempting action, while a content-free freshness cue did not materially redirect allocation and a content-matched control rule changed neither selection nor decisions.

0.42

Evidence Before Expansion: Reuse, Spawn, or Defer in Lifelong Expert Pools

cs.LG cs.AIcs.NE ·2026-08-20 ·Kentaro Oda
benchmarktheory similarity 0.58
Abstract · 8 pages, 4 figures

Streaming systems that maintain a pool of expert models must repeatedly decide whether to reuse an existing expert for arriving data, spawn a new one, or defer. We present a decision layer that makes all three outcomes statistically meaningful. Reuse and spawn are posed as one-sided sequential hypotheses on a conditional (mechanism-level) discrepancy, separated by an indifference zone; defer is exactly the state in which neither betting e-process has accumulated sufficient evidence. We prove finite-time anytime validity for the observable surrogate discrepancy of a predictable discriminator sequence, and an unconditional one-sided transfer to the population quantity in which each side's slack is the excess risk of a single discriminator; an empirically observed downward-bias regularity makes the spawn side exactly conservative. Recency without sacrificing the guarantee is obtained by a restarted e-detector: a bank of unwindowed betting supermartingales at geometrically spaced restart times (O(log t) memory), with the error budget spent over restart instances, which preserves lifetime anytime validity; spending over expert-creation order likewise controls multiplicity for unboundedly many experts. On synthetic multi-concept streams, Electricity, Covertype, and the recurrence-heavy INSECTS benchmark, the instance-accounted restarted bank achieves zero false spawns and zero false reuses after switches and matches or exceeds the retired windowed heuristic (INSECTS-reoccurring accuracy 0.675), making the deployed algorithm and the guaranteed algorithm one and the same.

0.24

Latent Coherence: Do Frontier Language Models' Probability Judgments Obey the Law of Total Probability?

cs.CL ·2026-10-22 ·Peter Potash
code/data similarity 0.58
Abstract · 15 pages

LawZero's Scientist AI trains a Predictor toward the Bayesian posterior, with an objective that penalizes inconsistent probabilities among latent explanations. We ask whether current frontier language models, with no such training, are already consistent in this sense zero-shot: do their probability judgments satisfy the law of total probability, $P(X)=\sum_z P(z)P(X|z)$, when the latent $z$ must be inferred from records in the context? In separate single-turn calls, models are asked for $P(X)$, for $P(z)$ over the latent's states, and for $P(X|z)$; a causal family applies the same test to $P(y|do(x))$ and the back-door adjustment. Every query has an exact ground-truth probability, and a subset of items is asked in three wordings to separate persistent incoherence from rewording noise. Across seven models, GPT-6.1 Sol and Claude Opus 5.5 are the most coherent (mean absolute residual 0.08 and 0.12 log-odds, about 2 percentage points). Claude Haiku 5.5, Gemini 3.8 Flash and DeepSeek V4-Pro show persistent incoherence (0.27-0.35 log-odds) that is mostly item-specific rather than a shared offset. Within every model, larger residuals go with larger errors against the truth (Spearman 0.40-0.62), so the residual, which needs no ground truth, flags unreliable answers. Reasoning length does not predict coherence, across models or within a model across rewordings of the same question. Simple consistency checks pass almost everywhere; the failures are specific to reasoning through a latent variable. Code and data: https://github.com/ppotash/latent-coherence

0.38

Diagnosing Sampled LLM Reasoning in Formal Geometry: Coverage, Realization, and Validity Evidence

cs.AI ·2026-09-26 ·Xiao Yue, Guangzhi Qu
similarity 0.58
Abstract

Repeated sampling can reveal a correct numerical answer without yielding either a reliable system output or a supported derivation. We present Coverage, Realization, and Validity Evidence (CRV), an evaluation protocol for sampled large language model (LLM) reasoning over formal geometry states. Coverage is answer availability, realization is readout accuracy on the frozen candidate pool, and validity evidence is a label-blinded critic judgment of derivational support rather than a proof certificate. CRV freezes each candidate pool before comparing readouts and analyzes covered failures by correct-answer multiplicity and within-problem discrimination. On HardShift441, a 441-problem set for which a reference solver leaves 406 problems unsolved, a LoRA-adapted Qwen2.5-7B generator obtains 24.2% average single-sample accuracy and 68.9% pass@16, whereas verifier-weighted self-consistency (WSC) reaches 38.0%. Readout accuracy is particularly low when the correct answer occurs only once or twice in the pool. In a separate constructed audit of 195 covered problems, the critic labels 12 correct-answer representatives as supported, 181 as refuted, and two as uncertain. These results show that coverage, realization, and validity evidence from the critic are distinct quantities and should be reported separately.

0.29

Calibration-Free Early Stopping for Chain-of-Thought Reasoning via E-processes

cs.CL cs.AIcs.LG ·2026-10-18 ·Dong-Jae Lee, Gyojin Han, Junmo Kim
top venue similarity 0.58
Abstract · EMNLP 2026 Findings

Reasoning large language models (LLMs) benefit from test-time scaling, motivating adaptive policies that spend tokens when they help and stop early otherwise. Existing rules halt when a confidence or stability signal crosses a threshold, but such thresholds rarely transfer across models and datasets, and validation-calibrated rules lose their guarantee under shifts in test-time horizon or signal dynamics. We reframe adaptive stopping as sequential evidence accumulation along the reasoning trajectory rather than threshold calibration on held-out data. Our framework runs two e-processes on a shared per-chunk signal: a commit stream tracks the signal's position relative to its slow trend, and an abstain stream tracks its signed velocity, making the two anti-correlated by construction. Under signal-level nulls on the per-chunk increments, Ville's inequality yields an anytime-valid signal-level false-alarm bound at user-specified significance levels, with no held-out calibration. Across various model--dataset combinations, the framework matches or exceeds calibration-based stopping on the token--accuracy Pareto front using zero calibration data, and the same significance level transfers unchanged across cells where calibration becomes infeasible.

0.43

When Can a Machine Trust a Statute? A Survival Certificate for Machine-Extracted Legal Logic

cs.AI cs.CL ·2026-09-01 ·Surya Saka
theory similarity 0.57
Abstract · 18 pages, 9 figures, 13 tables (6 main text, 7 appendix). Code, data products, and preregistration to be released on GitHub

Statutes are increasingly parsed by machines before people read them, and the parsers disagree: on Missouri's statutes, two independently written extractors diverge on numeric-threshold presence at a false-negative rate of 0.43. We ask what formal logic survives such noise. We build a passive survival certificate for the Duquenne-Guigues implication basis of machine-extracted statutory contexts: per-attribute inter-extractor disagreement is measured, replayed against the basis in 1,000 Monte Carlo trials, and an implication is certified only when a one-sided Wilson 95% lower bound on survival reaches 0.95; every certified implication carries premise spans and a minimal counterexample. On 29,365 Missouri sections and 502 Indian central-Act sections, the preregistered held-out gate passes (10 statute families across 7 Titles exact; 16 across 11 with 5% tolerance), yet under one globally deployed error model 93.2% of held-out chapters fall below the informativeness floor, and a 2x2 factorial assigns that to calibration-rate transfer, not selection. The certificate is usable but fragile: deploy it per-chapter-calibrated or error-tolerant. Code, data products, and the audit trail, including one retracted claim, are released.

0.30

What Counts as Evidence? Epistemic Cue Utilization in Large Language Models

cs.CY ·2026-10-08 ·Jinchang Zhang, Kaijun Jiang, Guoyu Lu
benchmark similarity 0.57
Abstract

Which information actually shapes a language model's judgment when sources disagree? We study epistemic cue utilization through a controlled benchmark of 500 scenarios and five complementary tracks separating cue identification, cue influence, and competition between source, temporal, and presentation cues. Across 13 LLMs, nearly identical recognition of relative source reliability can accompany effects ranging from negligible to complete choice reversal when source histories are exchanged. The resulting profiles distinguish models that rely on source history from those more responsive to evidence lineage, event time, or presentation order. We then intervene on three Qwen checkpoints using matched sham material, fact restatement, structured evidence records, and an additional weighting principle. Restatement increases reliability sensitivity in the two 27B models, and adding the principle increases it by a further 39.2 and 47.2 percentage points relative to the ledger. The 9B model instead changes its sensitivity to evidence lineage without a comparable reliability response. Verified-state accuracy remains 100\% throughout these interventions. Together, the benchmark and interventions show that identifying an epistemic cue and allowing it to influence judgment are distinct, experimentally measurable aspects of model behavior.

0.08