Strategic Self-Consistency

# Strategic Self-Consistency
Source: [https://arxiv.org/html/2609.30352](https://arxiv.org/html/2609.30352)
Ander Artola VelascoManuel Gomez\-Rodriguez§Affiliation:†Carnegie Mellon University, Pittsburgh, USA toriq@andrew\.cmu\.eduAffiliation:§Max Planck Institute for Software Systems, Kaiserslautern, Germany \{avelasco, manuel\}@mpi\-sws\.org

###### Abstract

Self\-consistency has become a popular technique for enhancing the reasoning abilities of large language models by generating multiple reasoning paths and selecting the final answer through a majority vote\. However, because model providers typically charge users in proportion to the number of reasoning paths generated, they have a financial incentive to artificially increase the path count\. In this work, we show that an unfaithful provider can exploit this incentive using a simple, efficient algorithm while avoiding detection by an auditor: by generating and strategically reordering additional reasoning paths, the algorithm makes every path appear necessary to reach the majority\. To validate our algorithm, we conduct experiments with multiple instruct models from theLlamaandQwenfamilies, as well as reasoning models distilled fromDeepSeek\-R1, on benchmark datasets spanning mathematics, science, and question answering\. Our results suggest that the distribution of additional reasoning paths generated by our algorithm is heavy\-tailed and that substantial capacity to overcharge remains even under the best possible audit designed to keep the false\-positive rate belowα=0\.1\\alpha=0\.1\.

††∗Equal contribution\. Tori Qiu contributed to this work during an internship at the Max Planck Institute for Software Systems\.## 1Introduction

State\-of\-the\-art large language models \(LLMs\) are commonly accessed as a service\. A user sends a query to an LLM provider, receives an answer, and pays proportionally to the compute the provider reports was necessary to generate the answer using the model it serves, as measured by the total number of consumed tokens\. However, because the user cannot typically verify that the reported compute was actually necessary, the provider has a financial incentive to inflate or waste compute\.

The growing popularity of test\-time compute methods, which improve answer quality by spending additional compute at inference time\([Wei et al\., 2022](https://arxiv.org/html/2609.30352#bib.bib38);[Yao et al\., 2023](https://arxiv.org/html/2609.30352#bib.bib53);[Chow et al\., 2025](https://arxiv.org/html/2609.30352#bib.bib39);[Koh et al\., 2025](https://arxiv.org/html/2609.30352#bib.bib33);[Yoshiyama et al\., 2026](https://arxiv.org/html/2609.30352#bib.bib40)\), sharpens this incentive\. Under self\-consistency\([Wang et al\., 2023](https://arxiv.org/html/2609.30352#bib.bib3)\), one of the most widely used test\-time compute methods, the provider generates multiple reasoning paths using the model it serves and selects the final answer through a majority vote\. In this context, an unfaithful provider can artificially increase the number of reasoning paths and claim that all of them were necessary to determine the answer with high confidence\.

One tempting solution is to require the provider both to commit to an adaptive stopping rule that determines the number of reasoning paths required to identify the answer to a user query through a majority vote\([Aggarwal et al\., 2023](https://arxiv.org/html/2609.30352#bib.bib4);[Feng et al\., 2026](https://arxiv.org/html/2609.30352#bib.bib2);[Huang et al\., 2026](https://arxiv.org/html/2609.30352#bib.bib30)\)and to disclose the entire generated sequence of reasoning paths to the user\. In this work, we show that such a solution fails, even when the reported reasoning paths can be inspected by a powerful third\-party auditor\. More specifically, we make the following contributions:

1. 1\.We introduce a simple and efficient algorithm that an unfaithful provider can use to artificially inflate the number of reasoning paths it generates while making each additional path appear necessary to reach the majority under the provider’s stopping rule\.
2. 2\.We prove that, under natural conditions on the provider’s stopping rule, our algorithm can generate a nontrivial number of additional reasoning paths, and we derive a lower bound on the expected number of additional generations\.
3. 3\.We show that an unfaithful provider running our algorithm can strategically evade an exact likelihood\-ratio audit, highlighting the vulnerability of users in the current pay\-for\-compute market\.

To complement our theoretical results, we conduct experiments with models from theLlamaandQwenfamilies on mathematics, science, and question\-answering benchmarks\. The results suggest that the distribution of additional reasoning paths generated by our algorithm is heavy\-tailed and, even under the best possible audit designed to keep the false positive rate belowα=0\.1\\alpha=0\.1, the provider’s capacity to overcharge remains\.111In the main text, we focus on self\-consistency\. However, in Appendices[A\.4](https://arxiv.org/html/2609.30352#A1.SS4)and[F\.4](https://arxiv.org/html/2609.30352#A6.SS4), we empirically extend the analysis to best\-of\-NNand discuss extensions to sequential search\-and\-verification procedures\.Code for reproducing our experiments is available at[https://github\.com/Human\-Centric\-Machine\-Learning/strategic\-self\-consistency](https://github.com/Human-Centric-Machine-Learning/strategic-self-consistency)\.

Further related work\.Our work builds on a large literature on test\-time compute methods\([Wang et al\., 2023](https://arxiv.org/html/2609.30352#bib.bib3);[Koh et al\., 2025](https://arxiv.org/html/2609.30352#bib.bib33);[Bi et al\., 2025](https://arxiv.org/html/2609.30352#bib.bib34);[Karan and Du, 2026](https://arxiv.org/html/2609.30352#bib.bib32);[Wan et al\., 2025b](https://arxiv.org/html/2609.30352#bib.bib31);[Wu et al\., 2026](https://arxiv.org/html/2609.30352#bib.bib27);[Ramji et al\., 2026](https://arxiv.org/html/2609.30352#bib.bib28);[Komiyama et al\., 2026](https://arxiv.org/html/2609.30352#bib.bib6);[Yoshiyama et al\., 2026](https://arxiv.org/html/2609.30352#bib.bib40)\)\. Most closely related is a line of work on adaptive self\-consistency\([Aggarwal et al\., 2023](https://arxiv.org/html/2609.30352#bib.bib4);[Feng et al\., 2026](https://arxiv.org/html/2609.30352#bib.bib2);[Huang et al\., 2026](https://arxiv.org/html/2609.30352#bib.bib30)\), which develops adaptive stopping rules with statistical guarantees on the final answer\. In contrast, we demonstrate that an unfaithful provider can create the appearance of following these adaptive stopping rules while artificially inflating the number of reasoning paths it generates\.

Our work also connects to a rapidly growing literature on the economic incentives of LLM providers in the market of LLM\-as\-a\-service\([Raghavan, 2024](https://arxiv.org/html/2609.30352#bib.bib23);[Mahmood, 2024](https://arxiv.org/html/2609.30352#bib.bib25);[Qiu et al\., 2025](https://arxiv.org/html/2609.30352#bib.bib24);[Bergemann et al\., 2025](https://arxiv.org/html/2609.30352#bib.bib26);[Laufer et al\., 2024](https://arxiv.org/html/2609.30352#bib.bib20);[Olmedo et al\., 2026](https://arxiv.org/html/2609.30352#bib.bib21);[Chen et al\., 2026](https://arxiv.org/html/2609.30352#bib.bib22);[Velasco et al\., 2026b](https://arxiv.org/html/2609.30352#bib.bib11);[Velasco et al\., 2026a](https://arxiv.org/html/2609.30352#bib.bib12);[Velasco et al\., 2026c](https://arxiv.org/html/2609.30352#bib.bib10)\)\. Within this literature, the works most closely related to consider how unfaithful providers may \(i\) covertly substitute a cheaper, lower\-quality LLM for the one they charge users for running\([Amirizaniani et al\., 2024](https://arxiv.org/html/2609.30352#bib.bib35);[Bourrée et al\., 2025](https://arxiv.org/html/2609.30352#bib.bib9);[Cai et al\., 2025](https://arxiv.org/html/2609.30352#bib.bib13);[Chauvin et al\., 2026](https://arxiv.org/html/2609.30352#bib.bib36);[Zhu et al\., 2026](https://arxiv.org/html/2609.30352#bib.bib37)\), or \(ii\) manipulate the number of tokens billed to users\([Wang et al\., 2025b](https://arxiv.org/html/2609.30352#bib.bib15);[Sun et al\., 2025](https://arxiv.org/html/2609.30352#bib.bib16);[Velasco et al\., 2026c](https://arxiv.org/html/2609.30352#bib.bib10)\)\. To the best of our knowledge, our work is the first to consider unfaithful providers who may strategically increase and reorder additional reasoning paths to overcharge users\.

Finally, the audit procedure we study draws on a strand of the change\-point detection literature focusing on detecting non\-exchangeability\([Vovk et al\., 2003](https://arxiv.org/html/2609.30352#bib.bib14);[Vovk et al\., 2021](https://arxiv.org/html/2609.30352#bib.bib17);[Dandapanthula and Ramdas, 2026](https://arxiv.org/html/2609.30352#bib.bib18);[Saha and Ramdas, 2026](https://arxiv.org/html/2609.30352#bib.bib19)\)\. This literature typically relies on conformal or plug\-in martingales, whereas in our audit procedure, the likelihood ratio can be computed exactly and efficiently\.

## 2Adaptive Self\-Consistency with Count\-Based Stopping

Let𝒜=\{ai\}i∈\[K\]\\mathcal\{A\}=\\\{a\_\{i\}\\\}\_\{i\\in\[K\]\}, withK∈\{2,3,…\}K\\in\\\{2,3,\\ldots\\\}, denote the set of possible answers that the provider’s model can generate for a user’s query,222In practice, a model generates a reasoning path, which eventually yields an answeraia\_\{i\}\. Different reasoning paths may represent the same answer with varying wording and style, but explicitly modeling this variation is not relevant to our analysis\.and letpi≥0p\_\{i\}\\geq 0be the probability of the provider’s model generating answeraia\_\{i\}, with∑i=1Kpi=1\\sum\_\{i=1\}^\{K\}p\_\{i\}=1\.

A provider seeking to improve the quality of the final answer returned to the user can spend additional compute to generate multiple answers from the model and select the most common one as the final answer—a popular strategy known as self\-consistency\([Wang et al\., 2023](https://arxiv.org/html/2609.30352#bib.bib3)\)\. Concretely, the provider generates a sequence𝐲=\(y1,…,yN\)\\mathbf\{y\}=\(y\_\{1\},\\dots,y\_\{N\}\)of independent answers from the model and returns the empirical modeaı^a\_\{\\widehat\{\\imath\}\}, where

ı^∈argmaxi∈\[K\]siandsi=∑j=1N𝟙\[yj=ai\]\.\\widehat\{\\imath\}\\in\\arg\\max\_\{i\\in\[K\]\}s\_\{i\}\\quad\\text\{and\}\\quad s\_\{i\}=\\sum\_\{j=1\}^\{N\}\\mathbbm\{1\}\[y\_\{j\}=a\_\{i\}\]\.\(1\)Thus, self\-consistency usesNNsamples to estimate the mode of the model’s answer distribution—that is, its most likely answerai⋆a\_\{i^\{\\star\}\}, wherei⋆∈arg⁡maxi∈\[K\]⁡pii^\{\\star\}\\in\\arg\\max\_\{i\\in\[K\]\}p\_\{i\}\. Throughout, we assume that this mode is unique\. While increasingNNyields a more reliable estimate ofai⋆a\_\{i^\{\\star\}\}, it also incurs greater computational cost\. This tradeoff has motivated interest in adaptive stopping rules\([Aggarwal et al\., 2023](https://arxiv.org/html/2609.30352#bib.bib4);[Feng et al\., 2026](https://arxiv.org/html/2609.30352#bib.bib2);[Huang et al\., 2026](https://arxiv.org/html/2609.30352#bib.bib30)\), which sequentially evaluate generated answers to decide whether enough answers have been generated to identify the mode with high confidence\. Rather than fixingNNin advance, these rules aim to generate only as many answers as a query requires\.

For the remainder of the main analysis, we consider a setting where the provider commits to an adaptive stopping ruleτ⁡\(s1,…,sK\)∈\{0,1\}\\tau\(s\_\{1\},\\ldots,s\_\{K\}\)\\in\\\{0,1\\\}, where11indicates that the countss1,…,sKs\_\{1\},\\ldots,s\_\{K\}are sufficient to stop and identify the mode with high confidence and00indicates that generation should continue\. The provider discloses to the user the entire sequence of generated answers𝐲\\mathbf\{y\}, together with the empirical modeaı^a\_\{\\widehat\{\\imath\}\}\. We focus on stopping rules that depend on the answer counts\(s1,…,sK\)\(s\_\{1\},\\dots,s\_\{K\}\)rather than on the full sequence𝐲\\mathbf\{y\}, since these counts are sufficient statistics for the answer probabilities\(p1,…,pK\)\(p\_\{1\},\\dots,p\_\{K\}\), and consequently, for the mode of the distribution\. We illustrate two such stopping rules below and discuss additional rules from the literature in Appendix[A](https://arxiv.org/html/2609.30352#A1)\.

###### Example 1\(PPR\-1v1 stopping rule\([Anand Jain et al\., 2022](https://arxiv.org/html/2609.30352#bib.bib1)\)\)\.

The PPR\-1v1 stopping rule constructs a prior\-posterior\-ratio \(PPR\) martingale confidence sequence for the probabilitypı^p\_\{\\widehat\{\\imath\}\}of the empirical mode afterNNobserved answers and stops as soon as this confidence sequence only contains sufficiently high values, declaringaı^a\_\{\\widehat\{\\imath\}\}to be the mode\. Concretely, the PPR\-1v1 stopping rule can be written as

τPPR\-1v1\(s1,…,sK\)=𝟙\[\(1/2\)s\(1\)⋅\(1/2\)s\(2\)∫01qs\(1\)⋅\(1−q\)s\(2\)​𝑑q≤δK−1\],\\displaystyle\\tau\_\{\\text\{PPR\-1v1\}\}\(s\_\{1\},\\dots,s\_\{K\}\)=\\mathbbm\{1\}\\left\[\\frac\{\(1/2\)^\{s\_\{\(1\)\}\}\\cdot\\,\(1/2\)^\{s\_\{\(2\)\}\}\}\{\\int\_\{0\}^\{1\}q^\{s\_\{\(1\)\}\}\\cdot\(1\-q\)^\{s\_\{\(2\)\}\}\\,dq\}\\leq\\frac\{\\delta\}\{K\-1\}\\right\],whereδ∈\(0,1\)\\delta\\in\(0,1\)is a user\-defined bound on the probability that the empirical modeaı^a\_\{\\widehat\{\\imath\}\}does not coincide with the true modeai⋆a\_\{i^\{\\star\}\}at stopping, ands\(1\)≥s\(2\)≥⋯≥s\(K\)s\_\{\(1\)\}\\geq s\_\{\(2\)\}\\geq\\dots\\geq s\_\{\(K\)\}are the ordered answer counts\.

WhileτPPR\-1v1\\tau\_\{\\text\{PPR\-1v1\}\}provides theoretical guarantees on the probability of incorrectly identifying the mode, it can be overly conservative under practical answer\-generation budgets\([Feng et al\., 2026](https://arxiv.org/html/2609.30352#bib.bib2)\)\. Other stopping rules therefore relax these theoretical guarantees in favor of stronger empirical performance\.

###### Example 2\(ASC stopping rule\([Aggarwal et al\., 2023](https://arxiv.org/html/2609.30352#bib.bib4)\)\)\.

The ASC stopping rule approximates the posterior probability that the current empirical mode is the true mode using a uniform prior over the possible answer probabilities\(p1,…,pK\)\(p\_\{1\},\\dots,p\_\{K\}\)\. Specifically, for a fixed parameterγ∈\(0,1\)\\gamma\\in\(0,1\), the stopping rule is:

τASC​\(s1,…,sK\)\\displaystyle\\tau\_\{\\text\{ASC\}\}\(s\_\{1\},\\dots,s\_\{K\}\)=𝟙\[∫1/21qs\(1\)⋅\(1−q\)s\(2\)​𝑑q∫01qs\(1\)⋅\(1−q\)s\(2\)​𝑑q≥γ\]\.\\displaystyle=\\mathbbm\{1\}\\left\[\\frac\{\\int\_\{1/2\}^\{1\}q^\{s\_\{\(1\)\}\}\\cdot\(1\-q\)^\{s\_\{\(2\)\}\}\\,dq\}\{\\int\_\{0\}^\{1\}q^\{s\_\{\(1\)\}\}\\cdot\(1\-q\)^\{s\_\{\(2\)\}\}\\,dq\}\\geq\\gamma\\right\]\.UnlikeτPPR\-1v1\\tau\_\{\\text\{PPR\-1v1\}\},γ\\gammadoes not necessarily bound the probability that the empirical mode is incorrect\.

A provider that faithfully implements a stopping rule generates exactly as many answers as the rule prescribes\. In the next section, however, we show that an unfaithful provider can nonetheless artificially increase the number of generated answers and overcharge the user while making each additional answer appear necessary under the stopping rule\.

## 3Inflating Reasoning Paths Under Adaptive Stopping

Suppose a provider commits to an adaptive stopping ruleτ\\tauthat prescribes stopping afterNNgenerated answers on a given query\. A faithful provider would report the resulting sequence𝐲=\(y1,…,yN\)\\mathbf\{y\}=\(y\_\{1\},\\ldots,y\_\{N\}\)and charge the user for exactly theseNNgenerations\. However, an unfaithful provider has an incentive to continue generating additional answers; if it reports a longer sequence𝐲′=\(y1,…,yN′\)\\mathbf\{y\}^\{\\prime\}=\(y\_\{1\},\\ldots,y\_\{N^\{\\prime\}\}\)withN′\>NN^\{\\prime\}\>N, they can charge the user for the additionalN′−NN^\{\\prime\}\-Ngenerations\.

Algorithm 1It returns a longer compatible sequence of answers1:Stopping rule

τ\\tau, compatible sequence

𝐲=\(y1,…,yN\)\\mathbf\{y\}=\(y\_\{1\},\\ldots,y\_\{N\}\), budget

NmaxN\_\{\\max\}, number of answers

KK, audit significance level

α\\alpha
2:Extended sequence

𝐲′\\mathbf\{y\}^\{\\prime\}
3:

𝐲′←𝐲\\mathbf\{y\}^\{\\prime\}\\leftarrow\\mathbf\{y\}
4:

LastCompatible←𝐲\\texttt\{LastCompatible\}\\leftarrow\\mathbf\{y\}
5:while

len⁡\(𝐲′\)<Nmax\\mathrm\{len\}\(\\mathbf\{y\}^\{\\prime\}\)<N\_\{\\max\}do

6:

m←len⁡\(𝐲′\)m\\leftarrow\\mathrm\{len\}\(\\mathbf\{y\}^\{\\prime\}\)
7:

\(s1′,…,sK′\)←\(s^\{\\prime\}\_\{1\},\\ldots,s^\{\\prime\}\_\{K\}\)\\leftarrowanswer counts of

𝐲′\\mathbf\{y\}^\{\\prime\}
8:

ynew←y\_\{\\mathrm\{new\}\}\\leftarrowanswer of a new reasoning path generated by the model⊳\\trianglerightPr⁡\(ynew=ai\)=pi\\Pr\(y\_\{\\mathrm\{new\}\}=a\_\{i\}\)=p\_\{i\}

9:if

τ⁡\(s1′,…,sK′\)=0\\tau\(s^\{\\prime\}\_\{1\},\\dots,s^\{\\prime\}\_\{K\}\)=0then⊳\\trianglerightThe current sequence does not triggerτ\\tau

10:

𝐲′′=\(y1,…,ym,ynew\)\\mathbf\{y\}^\{\\prime\\prime\}=\(y\_\{1\},\\dots,y\_\{m\},y\_\{\\mathrm\{new\}\}\)
11:else

12:

LastCompatible←𝐲′\\texttt\{LastCompatible\}\\leftarrow\\mathbf\{y\}^\{\\prime\}
13:if

ynew=ymy\_\{\\mathrm\{new\}\}=y\_\{m\}then

14:return

𝐲′\\mathbf\{y\}^\{\\prime\}⊳\\trianglerightCannot defer: the new answer matches the current last answer

15:endif

16:

𝐲′′←\(y1,…,ym−1,ynew,ym\)\\mathbf\{y\}^\{\\prime\\prime\}\\leftarrow\(y\_\{1\},\\ldots,y\_\{m\-1\},y\_\{\\mathrm\{new\}\},y\_\{m\}\)⊳\\trianglerightInsertynewy\_\{\\mathrm\{new\}\}before the last answer

17:

\(s1,…,sK\)←\(s\_\{1\},\\ldots,s\_\{K\}\)\\leftarrowanswer counts of

\(y1,…,ym−1,ynew\)\(y\_\{1\},\\ldots,y\_\{m\-1\},y\_\{\\mathrm\{new\}\}\)
18:if

τ⁡\(s1,…,sK\)=1\\tau\(s\_\{1\},\\ldots,s\_\{K\}\)=1then

19:return

𝐲′\\mathbf\{y\}^\{\\prime\}⊳\\trianglerightCannot defer: the new answer triggers the stopping rule

20:endif

21:endif

22:if

AuditFlag​\(𝐲′′,α\)\\texttt\{AuditFlag\}\(\\mathbf\{y\}^\{\\prime\\prime\},\\alpha\)then⊳\\triangleright𝐲′′\\mathbf\{y\}^\{\\prime\\prime\}exceeds audit threshold \(Eq\. \([4](https://arxiv.org/html/2609.30352#S4.E4)\)\)

23:returnLastCompatible

24:endif

25:

𝐲′←𝐲′′\\mathbf\{y\}^\{\\prime\}\\leftarrow\\mathbf\{y\}^\{\\prime\\prime\}⊳\\trianglerightContinue with the longer, still non\-triggering sequence

26:endwhile

27:return

𝐲′\\mathbf\{y\}^\{\\prime\}

The provider cannot simply report an arbitrary longer sequence𝐲′\\mathbf\{y\}^\{\\prime\}without raising the user’s suspicion\. Since the user knows the stopping ruleτ\\tauand observes the entire reported sequence𝐲′\\mathbf\{y\}^\{\\prime\}, they can verify whether the provider stopped generating answers when prescribed by the rule\. In particular, if any prefix of the reported sequence already triggers the stopping rule, the user can conclude that the provider generated unnecessary answers\. A provider seeking to avoid suspicion is therefore restricted to reporting sequences that are*compatible*with the stopping rule\.

###### Definition 1\(Compatible sequence\)\.

A sequence of answers𝐲=\(y1,…,yN\)\\mathbf\{y\}=\(y\_\{1\},\\ldots,y\_\{N\}\)is*compatible*with a stopping ruleτ\\tauif

τ⁡\(s1n,…,sKn\)=0​for all​n<N,andτ⁡\(s1N,…,sKN\)=1,\\tau\(s\_\{1\}^\{n\},\\dots,s\_\{K\}^\{n\}\)=0\\ \\text\{ for all \}n<N,\\qquad\\text\{and\}\\qquad\\tau\(s\_\{1\}^\{N\},\\dots,s\_\{K\}^\{N\}\)=1,\(2\)wheres1n,…,sKns\_\{1\}^\{n\},\\dots,s\_\{K\}^\{n\}denote the answer counts among the firstnnelements of𝐲\\mathbf\{y\}\.

The definition above captures the intuition that, from the user’s perspective, every answer in a compatible sequence appears necessary to identify the most likely answer with confidence, as prescribed by the stopping ruleτ\\tau\. We next show that an unfaithful provider can artificially increase the number of answers it generates while still reporting a compatible sequence\. To this end, we introduce a simple, heuristic procedure \(Algorithm[1](https://arxiv.org/html/2609.30352#alg1)\) that transforms a sequence𝐲\\mathbf\{y\}of lengthNN, generated by faithfully following stopping ruleτ\\tau, into a longer compatible sequence𝐲′\\mathbf\{y\}^\{\\prime\}of lengthN′≥NN^\{\\prime\}\\geq N, where the additionalN′−NN^\{\\prime\}\-Nanswers are genuinely generated by the model\.

Algorithm[1](https://arxiv.org/html/2609.30352#alg1)starts from the faithfully stopped sequence𝐲\\mathbf\{y\}and extends it one answer at a time\. Specifically, whenever the current sequence\(y1,…,ym−1,ym\)\(y\_\{1\},\\ldots,y\_\{m\-1\},y\_\{m\}\)triggers the stopping rule—and would therefore require a faithful provider to stop—the algorithm generates one additional answerynewy\_\{\\mathrm\{new\}\}from the model and checks whether the sequence\(y1,…,ym−1,ynew\)\(y\_\{1\},\\ldots,y\_\{m\-1\},y\_\{\\mathrm\{new\}\}\), obtained by replacing the last answerymy\_\{m\}withynewy\_\{\\mathrm\{new\}\}, triggers the stopping rule\. If it does not, the algorithm continues from the reordered sequence\(y1,…,ym−1,ynew,ym\)\(y\_\{1\},\\ldots,y\_\{m\-1\},y\_\{\\mathrm\{new\}\},y\_\{m\}\); otherwise, it discardsynewy\_\{\\mathrm\{new\}\}and terminates, returning the most recent compatible sequence\.333In principle, more sophisticated strategies could reorder the entire sequence, rather than only the final pair of answers\. We focus on Algorithm[1](https://arxiv.org/html/2609.30352#alg1)to highlight that even a simple heuristic suffices to artificially increase the number of answers\.Importantly, Algorithm[1](https://arxiv.org/html/2609.30352#alg1)guarantees by construction that any sequence it returns appears, from the user’s perspective, to have stopped exactly as prescribed byτ\\tau\. We formalize this property in the following proposition \(see Appendix[B](https://arxiv.org/html/2609.30352#A2)for the proof\)\.

###### Proposition 2\.

The sequence𝐲′\\mathbf\{y\}^\{\\prime\}returned by Algorithm[1](https://arxiv.org/html/2609.30352#alg1)is compatible with the stopping ruleτ\\tau\.

The proposition above guarantees that an unfaithful provider using Algorithm[1](https://arxiv.org/html/2609.30352#alg1)can make every additional answer appear necessary under the stopping rule, but it does not quantify the benefit that the provider can obtain from this strategy\. To address this, we derive a lower bound on the average number of additional answers in the sequence𝐲′\\mathbf\{y\}^\{\\prime\}reported to the user for a broad class of stopping rules, which we refer to as admissible stopping rules\. This class includes PPR\-1v1 \(Example[1](https://arxiv.org/html/2609.30352#Thmexample1)\) and ASC \(Example[2](https://arxiv.org/html/2609.30352#Thmexample2)\)\.

###### Definition 3\(Admissible stopping rule\)\.

A stopping ruleτ\\tauis*admissible*if it satisfies the following properties\.

1. \(i\)Count invariance:τ⁡\(s1,s2,…,sK\)\\tau\(s\_\{1\},s\_\{2\},\\dots,s\_\{K\}\)depends only on the counts of the first and second most frequent answers, which we write asτ⁡\(s\(1\),s\(2\)\)\\tau\(s\_\{\(1\)\},s\_\{\(2\)\}\)\.
2. \(ii\)Nontriviality:a single observed answer is insufficient to identify the mode with high confidence; that is, ifs\(1\)=1s\_\{\(1\)\}=1ands\(2\)=0s\_\{\(2\)\}=0, thenτ⁡\(s\(1\),s\(2\)\)=0\\tau\(s\_\{\(1\)\},s\_\{\(2\)\}\)=0\.
3. \(iii\)Monotonicity in the second most frequent count:the stopping rule is non\-increasing in the second most frequent count; that is, ifτ⁡\(s\(1\),s\(2\)\)=0\\tau\(s\_\{\(1\)\},s\_\{\(2\)\}\)=0ands\(1\)≥s\(2\)\+1s\_\{\(1\)\}\\geq s\_\{\(2\)\}\+1, thenτ⁡\(s\(1\),s\(2\)\+1\)=0\\tau\(s\_\{\(1\)\},s\_\{\(2\)\}\+1\)=0\.
4. \(iv\)Fixed\-margin monotonicity:ifτ⁡\(s\(1\),s\(2\)\)=0\\tau\(s\_\{\(1\)\},s\_\{\(2\)\}\)=0, thenτ⁡\(s\(1\)\+c,s\(2\)\+c\)=0\\tau\(s\_\{\(1\)\}\+c,s\_\{\(2\)\}\+c\)=0for allc∈ℕ\+c\\in\\mathbb\{N\}^\{\+\}\.

Condition\(i\)\(i\)states that, to determine whether the current empirical mode can be reliably identified as the true mode, only the counts of the two most frequent answers matter, rather than those of the remaining answers or the order in which the answers were generated\. Condition\(i​i\)\(ii\)rules out trivial stopping rules\. Finally, conditions\(i​i​i\)\(iii\)and\(i​v\)\(iv\)capture the intuition that the provider’s confidence in the empirical mode cannot increase either by observing an additional second most frequent answer, which brings its count closer to that of the mode, or by observing the empirical mode and the second most frequent answer in equal measure, which leaves their count difference unchanged\. The following result lower\-bounds the expected number of additional answers obtained from running Algorithm[1](https://arxiv.org/html/2609.30352#alg1)\. We focus here on the case of two answers,K=2K=2, and refer the reader to Appendix[B\.3](https://arxiv.org/html/2609.30352#A2.SS3)for the general case\.

###### Proposition 4\.

Let𝐲=\(y1,…,yN\)\\mathbf\{y\}=\(y\_\{1\},\\dots,y\_\{N\}\)be any sequence of answers compatible with an admissible stopping ruleτ\\tau, and let𝐲′=\(y1′,…,yN′′\)\\mathbf\{y\}^\{\\prime\}=\(y^\{\\prime\}\_\{1\},\\dots,y^\{\\prime\}\_\{N^\{\\prime\}\}\)be a sequence returned by Algorithm[1](https://arxiv.org/html/2609.30352#alg1)\. IfK=2K=2, then it holds that:

𝔼⁡\[N′−N\]≥p\(1\)​p\(2\)​\(p\(1\)d−p\(2\)d\)−d⁡\(p\(1\)−p\(2\)\)​p\(2\)d\+1\(p\(1\)−p\(2\)\)​\(p\(1\)d\+2−p\(2\)d\+2\)whered=s\(1\)−s\(2\)−1,\\mathbb\{E\}\[N^\{\\prime\}\-N\]\\geq\\frac\{p\_\{\(1\)\}p\_\{\(2\)\}\\,\(p\_\{\(1\)\}^\{\\,d\}\-p\_\{\(2\)\}^\{\\,d\}\)\-d\\,\(p\_\{\(1\)\}\-p\_\{\(2\)\}\)\\,p\_\{\(2\)\}^\{\\,d\+1\}\}\{\(p\_\{\(1\)\}\-p\_\{\(2\)\}\)\\,\(p\_\{\(1\)\}^\{\\,d\+2\}\-p\_\{\(2\)\}^\{\\,d\+2\}\)\}\\quad\\text\{ where \}\\quad d=s\_\{\(1\)\}\-s\_\{\(2\)\}\-1,\(3\)where\(s\(1\),s\(2\)\)\(s\_\{\(1\)\},s\_\{\(2\)\}\)denote the answer counts in𝐲\\mathbf\{y\}in non\-increasing order,\(p\(1\),p\(2\)\)\(p\_\{\(1\)\},p\_\{\(2\)\}\)denote the corresponding answer probabilities under the model, and the expectation is taken over the additional answers generated by the model within Algorithm[1](https://arxiv.org/html/2609.30352#alg1)\.

The intuition for the bound, formalized in Appendix[B\.3](https://arxiv.org/html/2609.30352#A2.SS3), follows from the monotonicity properties of admissible stopping rules\. Sampling additional occurrences of the second most frequent answera\(2\)a\_\{\(2\)\}in the sequence𝐲\\mathbf\{y\}requires the provider to generate at least as many occurrences of the most frequent answera\(1\)a\_\{\(1\)\}before the stopping rule can trigger again\. Algorithm[1](https://arxiv.org/html/2609.30352#alg1)can therefore continue extending the sequence as it generates additional occurrences ofa\(2\)a\_\{\(2\)\}\. Accordingly, the lower bound grows asp\(2\)→p\(1\)p\_\{\(2\)\}\\to p\_\{\(1\)\}and the mode of the answer distribution becomes harder to distinguish\. This is more likely for difficult queries, where the model is less confident in its answer\. In contrast, easier queries have answer distributions more concentrated around the mode, leaving less uncertainty for the provider to exploit by generating additional answers\. We verify this relationship empirically in Appendix[F\.1](https://arxiv.org/html/2609.30352#A6.SS1)\. Lastly, while the bound in Proposition[4](https://arxiv.org/html/2609.30352#Thmtheorem4)depends only on the two most frequent answers in the sequence𝐲\\mathbf\{y\}, Appendix[B\.3](https://arxiv.org/html/2609.30352#A2.SS3)derives a tighter lower bound on𝔼⁡\[N′−N\]\\mathbb\{E\}\[N^\{\\prime\}\-N\]that depends on the counts and probabilities of allKKanswers, which can be computed by solving a linear system of equations\.

## 4Auditing Self\-Consistency Reasoning Paths

We showed in the previous section that an unfaithful provider using Algorithm[1](https://arxiv.org/html/2609.30352#alg1)can generate additional self\-consistency reasoning paths that appear necessary under the stopping rule\. In this section, we show how an unfaithful provider can leverage an exact likelihood\-ratio test to ensure the sequence generated by Algorithm[1](https://arxiv.org/html/2609.30352#alg1)remains statistically indistinguishable from one generated faithfully, thereby avoiding detection by an auditor\.

To make this precise, we formalize the auditor’s inspection of a reported sequence𝐲′\\mathbf\{y\}^\{\\prime\}as a hypothesis test with the following null and alternative hypotheses\.

\{H0:𝐲′​∼iid​Categorical​\(p1,…,pK\)\(null\)H1:𝐲′​is generated by Algorithm[1](https://arxiv.org/html/2609.30352#alg1)from​𝐲​∼iid​Categorical​\(p1,…,pK\)\(alternative\)\.\\begin\{cases\}H\_\{0\}:\\mathbf\{y\}^\{\\prime\}\\overset\{\\mathrm\{iid\}\}\{\\sim\}\\mathrm\{Categorical\}\(p\_\{1\},\\ldots,p\_\{K\}\)&\\quad\(\\mathrm\{null\}\)\\\\ H\_\{1\}:\\mathbf\{y\}^\{\\prime\}\\,\\,\\text\{is generated by Algorithm~\\ref\{alg:greedy\_lookahead\} from\}\\,\\,\\mathbf\{y\}\\overset\{\\mathrm\{iid\}\}\{\\sim\}\\mathrm\{Categorical\}\(p\_\{1\},\\ldots,p\_\{K\}\)&\\quad\(\\mathrm\{alternative\}\)\.\\end\{cases\}The null hypothesisH0H\_\{0\}corresponds to a faithful provider who generates a sequence following the stopping rule, whereas the alternativeH1H\_\{1\}corresponds to an unfaithful provider who first generates a sequence𝐲\\mathbf\{y\}following the stopping rule and then applies Algorithm[1](https://arxiv.org/html/2609.30352#alg1)to obtain a longer sequence𝐲′\\mathbf\{y\}^\{\\prime\}\.

An auditor could use any possible test to rejectH0H\_\{0\}, but the celebrated Neyman–Pearson lemma guarantees that, among all tests of a given significance levelα∈\(0,1\)\\alpha\\in\(0,1\), the most powerful is the likelihood\-ratio test, which rejectsH0H\_\{0\}whenever the likelihood ratioℙH1​\(𝐲′\)/ℙH0​\(𝐲′\)\\mathbb\{P\}\_\{H\_\{1\}\}\(\\mathbf\{y\}^\{\\prime\}\)/\\mathbb\{P\}\_\{H\_\{0\}\}\(\\mathbf\{y\}^\{\\prime\}\)exceeds a thresholdcαc\_\{\\alpha\}, chosen so that the test has levelα\\alpha\([Lehmann and Romano, 2005](https://arxiv.org/html/2609.30352#bib.bib43)\)\. Computingcαc\_\{\\alpha\}exactly is typically intractable because it requires knowledge of the distribution of the likelihood ratio underH0H\_\{0\}\. However, since the likelihood ratio is an*e\-value*, setting the threshold to the explicit value1/α1/\\alphaguarantees that the probability of falsely flagging a faithful provider is at mostα\\alpha\([Grünwald et al\., 2024](https://arxiv.org/html/2609.30352#bib.bib7);[Ramdas and Wang, 2025](https://arxiv.org/html/2609.30352#bib.bib8);[Velasco et al\., 2026c](https://arxiv.org/html/2609.30352#bib.bib10)\), resulting in the following hypothesis test:444For ease of exposition, we focus on a setting where the provider reports a single sequence𝐲′\\mathbf\{y\}^\{\\prime\}\. In Appendix[C\.2](https://arxiv.org/html/2609.30352#A3.SS2), we extend our analysis to a setting where the provider reports multiple sequences\.

reject​H0ifℙH1​\(𝐲′\)ℙH0​\(𝐲′\)≥1α\.\\text\{reject \}H\_\{0\}\\quad\\text\{if\}\\quad\\frac\{\\mathbb\{P\}\_\{H\_\{1\}\}\(\\mathbf\{y\}^\{\\prime\}\)\}\{\\mathbb\{P\}\_\{H\_\{0\}\}\(\\mathbf\{y\}^\{\\prime\}\)\}\\geq\\frac\{1\}\{\\alpha\}\.\(4\)
We consider an unfaithful provider who anticipates such an audit and strategically avoids detection by the likelihood\-ratio test in Eq\. \([4](https://arxiv.org/html/2609.30352#S4.E4)\)\. To do so, the provider must compute the likelihood ratio, which we now show can be done efficiently\. The denominator is immediate: underH0H\_\{0\}, the answers are sampled independently from the model, yieldingℙH0​\(𝐲′\)=∏i=1N′pyi′\\mathbb\{P\}\_\{H\_\{0\}\}\(\\mathbf\{y\}^\{\\prime\}\)=\\prod\_\{i=1\}^\{N^\{\\prime\}\}p\_\{y^\{\\prime\}\_\{i\}\}\. Computing the numeratorℙH1​\(𝐲′\)\\mathbb\{P\}\_\{H\_\{1\}\}\(\\mathbf\{y\}^\{\\prime\}\)is more challenging because several distinct executions of Algorithm[1](https://arxiv.org/html/2609.30352#alg1)can return the same reported sequence𝐲′\\mathbf\{y\}^\{\\prime\}, as the following example illustrates\.

###### Example 3\.

Consider a query with three possible answers𝒜=\{a1,a2,a3\}\\mathcal\{A\}=\\\{a\_\{1\},a\_\{2\},a\_\{3\}\\\}, a sequence𝐲′=\(a1,a2,a3,a1\)\\mathbf\{y\}^\{\\prime\}=\(a\_\{1\},a\_\{2\},a\_\{3\},a\_\{1\}\)reported by the provider, and a stopping rule that instructs the provider to stop as soon as any answer is generated twice, that is,τ\(s\(1\),s\(2\)\)=𝟙\{s\(1\)≥2\}\\tau\(s\_\{\(1\)\},s\_\{\(2\)\}\)=\\mathbbm\{1\}\\\{s\_\{\(1\)\}\\geq 2\\\}\. To compute the likelihoodℙH1​\(𝐲′\)\\mathbb\{P\}\_\{H\_\{1\}\}\(\\mathbf\{y\}^\{\\prime\}\), observe that Algorithm[1](https://arxiv.org/html/2609.30352#alg1)must have been executed on one of the following compatible input sequences𝐲\\mathbf\{y\}:

1. 1\.𝐲=\(a1,a2,a3,a1\)\\mathbf\{y\}=\(a\_\{1\},a\_\{2\},a\_\{3\},a\_\{1\}\)\.The algorithm then generates one additionala1a\_\{1\}and discards it, returning𝐲​’=𝐲\\mathbf\{y\}\\textquoteright=\\mathbf\{y\}\. This occurs with probabilityp1⋅p2⋅p3⋅p1⋅p1p\_\{1\}\\cdot p\_\{2\}\\cdot p\_\{3\}\\cdot p\_\{1\}\\cdot p\_\{1\}\.
2. 2\.𝐲=\(a1,a2,a1\)\\mathbf\{y\}=\(a\_\{1\},a\_\{2\},a\_\{1\}\)\.The algorithm must then generatea3a\_\{3\}and construct the partial sequence\(a1,a2,a3,a1\)\(a\_\{1\},a\_\{2\},a\_\{3\},a\_\{1\}\)\. It subsequently generates one additionala1a\_\{1\}and discards it\. This occurs with probabilityp1⋅p2⋅p1⋅p3⋅p1p\_\{1\}\\cdot p\_\{2\}\\cdot p\_\{1\}\\cdot p\_\{3\}\\cdot p\_\{1\}\.
3. 3\.𝐲=\(a1,a1\)\\mathbf\{y\}=\(a\_\{1\},a\_\{1\}\)\.The algorithm first generatesa2a\_\{2\}and swaps it with the second occurrence ofa1a\_\{1\}to obtain\(a1,a2,a1\)\(a\_\{1\},a\_\{2\},a\_\{1\}\), and then generatesa3a\_\{3\}to construct the sequence\(a1,a2,a3,a1\)\(a\_\{1\},a\_\{2\},a\_\{3\},a\_\{1\}\)\. Finally, it generates one additionala1a\_\{1\}and discards it\. This occurs with probabilityp1⋅p1⋅p2⋅p3⋅p1p\_\{1\}\\cdot p\_\{1\}\\cdot p\_\{2\}\\cdot p\_\{3\}\\cdot p\_\{1\}\.

Since these cases are mutually exclusive and exhaust all the ways in which Algorithm[1](https://arxiv.org/html/2609.30352#alg1)can return𝐲′\\mathbf\{y\}^\{\\prime\}, summing their probabilities givesℙH1​\(𝐲′\)=3⋅p13⋅p2⋅p3\\mathbb\{P\}\_\{H\_\{1\}\}\(\\mathbf\{y\}^\{\\prime\}\)=3\\cdot p\_\{1\}^\{3\}\\cdot p\_\{2\}\\cdot p\_\{3\}\.

Algorithm 2It computes the likelihood of an observed sequence underH1H\_\{1\}1:Compatible sequence

𝐲′=\(y1′,…,yN′′\)\\mathbf\{y\}^\{\\prime\}=\(y^\{\\prime\}\_\{1\},\\dots,y^\{\\prime\}\_\{N^\{\\prime\}\}\), stopping rule

τ\\tau, class probabilities

p1,…,pKp\_\{1\},\\dots,p\_\{K\}\.

2:Likelihood of

𝐲′\\mathbf\{y\}^\{\\prime\}under Algorithm[1](https://arxiv.org/html/2609.30352#alg1)

3:

Counts←\(1,0,…,0\)⏟N′​elements\\texttt\{Counts\}\\leftarrow\\underbrace\{\(1,0,\\dots,0\)\}\_\{N^\{\\prime\}\\text\{ elements\}\}
4:

5:for

m=2,…,N′m=2,\\dots,N^\{\\prime\}do

6:

PrevCounts=0\\texttt\{PrevCounts\}=0
7:for

L=0,…,m−2L=0,\\dots,m\-2do

8:PossibleMultipleSwap=True

9:for

k=1,…,Lk=1,\\dots,Ldo

10:

\(s1,…,sK\)←\(s\_\{1\},\\ldots,s\_\{K\}\)\\leftarrowanswer counts of

\(y1′,…,ym−k−1′,ym′\)\(y^\{\\prime\}\_\{1\},\\ldots,y^\{\\prime\}\_\{m\-k\-1\},y^\{\\prime\}\_\{m\}\)
11:if

τ⁡\(s1,…,sK\)=0\\tau\\bigl\(s\_\{1\},\\ldots,s\_\{K\}\\bigr\)=0then

12:PossibleMultipleSwap=False

13:endif

14:endfor

15:ifPossibleMultipleSwapthen

16:

PrevCounts=PrevCounts\+Counts​\[m−L−1\]\\texttt\{PrevCounts\}=\\texttt\{PrevCounts\}\+\\texttt\{Counts\}\[m\-L\-1\]
17:endif

18:endfor

19:

Counts​\[m\]=PrevCounts\\texttt\{Counts\}\[m\]=\\texttt\{PrevCounts\}
20:endfor

21:return

Counts​\[N′\]⋅pyN′′⋅∏i=1N′pyi′\\texttt\{Counts\}\[N^\{\\prime\}\]\\cdot p\_\{y^\{\\prime\}\_\{N^\{\\prime\}\}\}\\cdot\\prod\_\{i=1\}^\{N^\{\\prime\}\}p\_\{y^\{\\prime\}\_\{i\}\}

The intuition from the example above generalizes\. In particular, the provider can efficiently computeℙH1​\(𝐲′\)\\mathbb\{P\}\_\{H\_\{1\}\}\(\\mathbf\{y\}^\{\\prime\}\)for any compatible sequence using the dynamic programming procedure in Algorithm[2](https://arxiv.org/html/2609.30352#alg2)\. Algorithm[2](https://arxiv.org/html/2609.30352#alg2)exploits the observation that every answer in a reported sequence𝐲′=\(y1′,…,yN′′\)\\mathbf\{y\}^\{\\prime\}=\(y^\{\\prime\}\_\{1\},\\dots,y^\{\\prime\}\_\{N^\{\\prime\}\}\)returned by Algorithm[1](https://arxiv.org/html/2609.30352#alg1)is generated by the model\. Each execution generates one additional answer—equal to the last reported answeryN′′y^\{\\prime\}\_\{N^\{\\prime\}\}—which triggers the stopping rule and is discarded\. Hence, the probability of obtaining𝐲′\\mathbf\{y\}^\{\\prime\}from any given compatible input𝐲\\mathbf\{y\}equals∏i=1N′pyi′⋅pyN′′=ℙH0​\(𝐲′\)⋅pyN′′\\prod\_\{i=1\}^\{N^\{\\prime\}\}p\_\{y^\{\\prime\}\_\{i\}\}\\cdot p\_\{y^\{\\prime\}\_\{N^\{\\prime\}\}\}=\\mathbb\{P\}\_\{H\_\{0\}\}\(\\mathbf\{y\}^\{\\prime\}\)\\cdot p\_\{y^\{\\prime\}\_\{N^\{\\prime\}\}\}, independent of𝐲\\mathbf\{y\}\. ComputingℙH1​\(𝐲′\)\\mathbb\{P\}\_\{H\_\{1\}\}\(\\mathbf\{y\}^\{\\prime\}\)therefore reduces to counting the number of compatible input sequences𝐲\\mathbf\{y\}that can produce𝐲′\\mathbf\{y\}^\{\\prime\}\. Algorithm[2](https://arxiv.org/html/2609.30352#alg2)tracks this quantity iteratively in a vectorCounts, whosemm\-th entry stores the number of compatible input sequences capable of generating the prefix\(y1′,…,ym′\)\(y^\{\\prime\}\_\{1\},\\ldots,y^\{\\prime\}\_\{m\}\)\. The final entry,Counts​\[N′\]\\texttt\{Counts\}\[N^\{\\prime\}\], gives the total count of such sequences\. The following proposition formalizes the correctness of this procedure\.555In Appendix[D](https://arxiv.org/html/2609.30352#A4), we further show that Algorithm[2](https://arxiv.org/html/2609.30352#alg2)can be implemented in time linear in the lengthN′N^\{\\prime\}of the reported sequence\.

###### Proposition 5\.

Given an observed sequence of answers𝐲′\\mathbf\{y\}^\{\\prime\}reported by the provider, Algorithm[2](https://arxiv.org/html/2609.30352#alg2)returns the likelihoodℙH1​\(𝐲′\)\\mathbb\{P\}\_\{H\_\{1\}\}\(\\mathbf\{y\}^\{\\prime\}\)\.

As an immediate consequence, the provider can efficiently compute the likelihood ratio in Eq\. \([4](https://arxiv.org/html/2609.30352#S4.E4)\) using the following expression:666In practice, the provider can efficiently estimate the probability of the most frequent answeryN′′y^\{\\prime\}\_\{N^\{\\prime\}\}using the empirical frequency ofyN′′y^\{\\prime\}\_\{N^\{\\prime\}\}among the answers in the generated sequence𝐲\\mathbf\{y\}\.

ℙH1​\(𝐲′\)ℙH0​\(𝐲′\)=Counts​\[N′\]⋅pyN′′⋅ℙH0​\(𝐲′\)ℙH0​\(𝐲′\)=Counts​\[N′\]⋅pyN′′\.\\frac\{\\mathbb\{P\}\_\{H\_\{1\}\}\(\\mathbf\{y\}^\{\\prime\}\)\}\{\\mathbb\{P\}\_\{H\_\{0\}\}\(\\mathbf\{y\}^\{\\prime\}\)\}=\\frac\{\\texttt\{Counts\}\[N^\{\\prime\}\]\\cdot p\_\{y^\{\\prime\}\_\{N^\{\\prime\}\}\}\\cdot\\mathbb\{P\}\_\{H\_\{0\}\}\(\\mathbf\{y\}^\{\\prime\}\)\}\{\\mathbb\{P\}\_\{H\_\{0\}\}\(\\mathbf\{y\}^\{\\prime\}\)\}=\\texttt\{Counts\}\[N^\{\\prime\}\]\\cdot p\_\{y^\{\\prime\}\_\{N^\{\\prime\}\}\}\.To avoid detection, the provider can monitor this ratio while generating additional answers in Algorithm[1](https://arxiv.org/html/2609.30352#alg1)and terminate immediately before the value reaches or exceeds the threshold1/α1/\\alpha\. This is implemented in lines[22](https://arxiv.org/html/2609.30352#alg1.l22)–[24](https://arxiv.org/html/2609.30352#alg1.l24)using the indicator:

AuditFlag\(𝐲,α\):=𝟙\[Counts\[N′\]⋅pyN′≥1α\]\.\\texttt\{AuditFlag\}\(\\mathbf\{y\},\\alpha\):=\\mathbbm\{1\}\\left\[\\texttt\{Counts\}\[N^\{\\prime\}\]\\cdot p\_\{y\_\{N^\{\\prime\}\}\}\\geq\\frac\{1\}\{\\alpha\}\\right\]\.

## 5Experiments

In this section, we evaluate the empirical performance of Algorithm[1](https://arxiv.org/html/2609.30352#alg1)on real queries from popular benchmark datasets across multiple LLM families\. We focus on the ASC stopping rule \(Example[2](https://arxiv.org/html/2609.30352#Thmexample2)\), which has been shown to outperform PPR\-1v1 \(Example[1](https://arxiv.org/html/2609.30352#Thmexample1)\) empirically under a variety of conditions\([Feng et al\., 2026](https://arxiv.org/html/2609.30352#bib.bib2)\)\. In Appendix[F](https://arxiv.org/html/2609.30352#A6), we show that our conclusions extend to other stopping rules, including potentially inadmissible ones\.

Experimental setup\.We consider models from theLlamaandQwenfamilies, including reasoning models distilled fromDeepSeek\-R1, and queries fromGSM8K\([Cobbe et al\., 2021](https://arxiv.org/html/2609.30352#bib.bib45)\)andAIME\([Zhang and Math\-AI, 2025](https://arxiv.org/html/2609.30352#bib.bib46)\)for mathematical reasoning and fromGPQA\([Rein et al\., 2024](https://arxiv.org/html/2609.30352#bib.bib47)\)for question answering\. Following prior work on self\-consistency\([Feng et al\., 2026](https://arxiv.org/html/2609.30352#bib.bib2)\), we first construct an empirical answer distribution per query using128128and3232pre\-generated answers for the instruct and reasoning models, respectively\. For each query, we first process the pre\-generated answers in their original order until the ASC stopping rule triggers\. If the available pre\-generated answers are insufficient to reach faithful stopping, we continue by sampling additional answers with replacement from the empirical answer distribution until the stopping rule is satisfied, yielding𝐲=\(y1,…,yN\)\\mathbf\{y\}=\(y\_\{1\},\\dots,y\_\{N\}\)\. Finally, starting from each sequence𝐲\\mathbf\{y\}, we use Algorithm[1](https://arxiv.org/html/2609.30352#alg1)to generate the reported sequence𝐲′=\(y1′,…,yN′′\)\\mathbf\{y\}^\{\\prime\}=\(y^\{\\prime\}\_\{1\},\\ldots,y^\{\\prime\}\_\{N^\{\\prime\}\}\), sampling the additionalN′−NN^\{\\prime\}\-Nanswers with replacement from the same distribution\. In all experiments, to limit computational overhead, we impose a cap of5,0005,000answers on bothNNandN′−NN^\{\\prime\}\-N\.

Results\.Table[1](https://arxiv.org/html/2609.30352#S5.T1)and Figure[1](https://arxiv.org/html/2609.30352#S5.F1)present summary statistics and the distribution of additional answersN′−NN^\{\\prime\}\-Ngenerated by Algorithm[1](https://arxiv.org/html/2609.30352#alg1)withα=0\.1\\alpha=0\.1\. Across models and benchmark datasets, the results suggest that the distribution of additional answers is heavy\-tailed: most reported sequences contain fewer than55additional answers, while a long tail of sequences contains hundreds, or even thousands, of additional answers \(Table[1](https://arxiv.org/html/2609.30352#S5.T1)\)\. Moreover, the provider’s capacity to overcharge varies substantially across benchmark datasets\. Figure[2](https://arxiv.org/html/2609.30352#S5.F2)shows the9090th percentile of the distribution of additional answersN′−NN^\{\\prime\}\-Nfor different values of the audit thresholdα\\alpha\. Perhaps surprisingly, the provider’s capacity to overcharge remains relatively insensitive to the choice ofα\\alpha\.

Table 1:Summary statistics of the additional answers generated by an unfaithful provider\.For each model and dataset, we report the mean, median, 75th percentile \(P75\), and 90th percentile \(P90\) of the additional answersN′−NN^\{\\prime\}\-Ngenerated by Algorithm[1](https://arxiv.org/html/2609.30352#alg1)on queries fromGSM8K,AIME, andGPQA\. In all experiments, we use the ASC stopping rule \(Example[2](https://arxiv.org/html/2609.30352#Thmexample2)\) withγ=0\.95\\gamma=0\.95and setα=0\.1\\alpha=0\.1\.Figure 1:Distribution of additional answers generated by an unfaithful provider\.For queries fromGSM8K,AIME, andGPQA, the figure shows the complementary cumulative distributionPr⁡\(N′−N≥x\)\\Pr\(N^\{\\prime\}\-N\\geq x\)of additional answersN′−NN^\{\\prime\}\-Ngenerated by Algorithm[1](https://arxiv.org/html/2609.30352#alg1)\. In all experiments, we use the ASC stopping rule \(Example[2](https://arxiv.org/html/2609.30352#Thmexample2)\) withγ=0\.95\\gamma=0\.95and setα=0\.1\\alpha=0\.1\.Figure 2:Influence of the audit threshold on an unfaithful provider’s capacity to overcharge\.For queries fromGSM8K,AIME, andGPQA, the figure shows the9090th percentile of the distribution of additional answersN′−NN^\{\\prime\}\-Ngenerated by Algorithm[1](https://arxiv.org/html/2609.30352#alg1)for different values of the audit thresholdα\\alpha\. In all experiments, we use the ASC stopping rule \(Example[2](https://arxiv.org/html/2609.30352#Thmexample2)\) withγ=0\.95\\gamma=0\.95\.DSabbreviatesDeepSeek\-R1\-Distill\.
## 6Discussion and Limitations

We discuss several assumptions and limitations of our work and propose avenues for future work\.

Methodology\.We have focused on self\-consistency, which is widely used for tasks with verifiable, categorical responses\. This setting admits a clean statistical interpretation, as stopping rules such as PPR\-1v1 offer theoretical guarantees that lend themselves to the analysis in Section[2](https://arxiv.org/html/2609.30352#S2)\. In Appendices[A\.4](https://arxiv.org/html/2609.30352#A1.SS4)and[F\.4](https://arxiv.org/html/2609.30352#A6.SS4), we discuss how our conclusions transfer to adaptive best\-of\-NNand other test\-time compute methods, where stopping rules depend on reward\-model scores or other signals\. Such stopping rules introduce additional challenges because they typically depend on the correctness of a reward function and assumptions about the reward distribution\([Wan et al\., 2025b](https://arxiv.org/html/2609.30352#bib.bib31)\)\. Developing comparable theoretical bounds on overcharging, as well as the corresponding audit mechanisms, is an important direction for future work\.

Furthermore, our lower bound on the provider’s gain in Proposition[4](https://arxiv.org/html/2609.30352#Thmtheorem4)applies only to admissible stopping rules\. This class includes several popular variants, but certain inadmissible stopping rules nonetheless perform well empirically\. In Appendix[F\.3](https://arxiv.org/html/2609.30352#A6.SS3), we demonstrate that our main conclusions extend to such rules\.

Experimental evaluation\.Our experiments cover mathematical reasoning, science, and question\-answering tasks\. It would be valuable to evaluate additional domains, as well as extensions of self\-consistency beyond categorical answers\. For instance, in coding tasks, agreement is determined by voting on the outputs of generated programs over a set of test cases\([Aggarwal et al\., 2023](https://arxiv.org/html/2609.30352#bib.bib4)\)\. Our experiments evaluate ASC in the main text, PPR\-1v1 in Appendix[F\.1](https://arxiv.org/html/2609.30352#A6.SS1), and early\-stopping self\-consistency \(ESC\)\([Li et al\., 2024](https://arxiv.org/html/2609.30352#bib.bib5)\)in Appendix[F](https://arxiv.org/html/2609.30352#A6)as stopping rules\. Future work could also consider confidence\-weighted stopping rules, such as CISC\([Taubenfeld et al\., 2025](https://arxiv.org/html/2609.30352#bib.bib48)\), and more complex multi\-agent test\-time compute procedures, which spawn several models and orchestrate their behavior before aggregating their conclusions\.777[https://docs\.x\.ai/developers/model\-capabilities/text/multi\-agent](https://docs.x.ai/developers/model-capabilities/text/multi-agent)\.

Auditing self\-consistency\.While we have shown that a provider can evade a powerful single\-sequence audit, repeated overcharging may be harder to conceal\. An audit can be deployed online, with evidence aggregated across multiple user queries, thereby constraining how frequently or aggressively the provider can misreport the number of reasoning paths \(see Appendix[C\.2](https://arxiv.org/html/2609.30352#A3.SS2)\)\. Providers could also engage in more sophisticated reordering strategies than the one in Algorithm[1](https://arxiv.org/html/2609.30352#alg1)\. In response, auditors could test for violations of exchangeability across multiple reported sequences\([Vovk et al\., 2003](https://arxiv.org/html/2609.30352#bib.bib14);[Vovk et al\., 2021](https://arxiv.org/html/2609.30352#bib.bib17);[Dandapanthula and Ramdas, 2026](https://arxiv.org/html/2609.30352#bib.bib18);[Saha and Ramdas, 2026](https://arxiv.org/html/2609.30352#bib.bib19)\), albeit with less power than the audit considered in our work\.

Finally, statistical audits could be complemented by measures that directly attest to faithful execution\. For open\-weight models, trusted execution environments or zero\-knowledge proofs could guarantee users that the provider’s computations were carried out faithfully\([Jauernig et al\., 2020](https://arxiv.org/html/2609.30352#bib.bib49);[Sun et al\., 2024](https://arxiv.org/html/2609.30352#bib.bib50)\)\. However, such approaches may be challenging, or even impossible, to implement for proprietary models whose weights and execution details cannot be disclosed\.

## 7Conclusions

To what extent can an LLM\-as\-a\-service provider overcharge a user who pays for compute they cannot directly observe? In our work, we have shown that under self\-consistency, the incentive to report an artificially high number of reasoning paths can be substantial\. Even a provider that commits to a specific stopping rule can generate additional reasoning paths and strategically reorder them so that each appears necessary under the stopping rule—effectively charging the user for computation that was never required\. Strikingly, an unfaithful provider can carry out this manipulation while guaranteeing that the reported sequence remains statistically indistinguishable from one generated by a faithful provider\. As a result, even the most powerful audit cannot reliably detect this deception\. More broadly, our results highlight the risks of opacity in the LLM\-as\-a\-service market and motivate the design of mechanisms that better align providers’ incentives with users’ interests\.

Acknowledgements\.Gomez\-Rodriguez acknowledges support from the European Research Council \(ERC\) under the European Union’s Horizon 2020 research and innovation programme \(grant agreement No\. 101169607\)\.

## References

- Aggarwalet al\.\(2023\)P\. Aggarwal, A\. Madaan, Y\. Yang, and M\. \.Let’s Sample Step by Step: Adaptive\-Consistency for Efficient Reasoning and Coding with LLMs\.InThe 2023 Conference on Empirical Methods in Natural Language Processing,External Links:[Link](https://openreview.net/forum?id=ETNa4Wb65J)Cited by:[§A\.2](https://arxiv.org/html/2609.30352#A1.SS2.p1.1),[§F\.1](https://arxiv.org/html/2609.30352#A6.SS1.p2.2),[§1](https://arxiv.org/html/2609.30352#S1.p3.1),[§1](https://arxiv.org/html/2609.30352#S1.p4.1),[§2](https://arxiv.org/html/2609.30352#S2.p2.2),[§6](https://arxiv.org/html/2609.30352#S6.p4.1),[Example 2](https://arxiv.org/html/2609.30352#Thmexample2)\.
- Amirizanianiet al\.\(2024\)M\. Amirizaniani, E\. Martin, T\. Roosta, A\. Chadha, and C\. ShahAuditLLM: A Tool for Auditing Large Language Models Using Multiprobe Approach\.InProceedings of the 33rd ACM International Conference on Information and Knowledge Management,CIKM ’24,New York, NY, USA,pp\. 5174–5179\.External Links:ISBN 9798400704369,[Link](https://doi.org/10.1145/3627673.3679222),[Document](https://dx.doi.org/10.1145/3627673.3679222)Cited by:[§1](https://arxiv.org/html/2609.30352#S1.p5.1)\.
- Anand Jainet al\.\(2022\)S\. Anand Jain, R\. Shah, S\. Gupta, D\. Mehta, I\. J\. Nair, J\. Vora, S\. Khyalia, S\. Das, V\. J\. Ribeiro, and S\. KalyanakrishnanPAC Mode Estimation using PPR Martingale Confidence Sequences\.InProceedings of The 25th International Conference on Artificial Intelligence and Statistics,G\. Camps\-Valls, F\. J\. R\. Ruiz, and I\. Valera \(Eds\.\),Proceedings of Machine Learning Research, Vol\.151,pp\. 5815–5852\.External Links:[Link](https://proceedings.mlr.press/v151/anand-jain22a.html)Cited by:[§A\.1](https://arxiv.org/html/2609.30352#A1.SS1.p1.1),[§F\.1](https://arxiv.org/html/2609.30352#A6.SS1.p2.2),[Example 1](https://arxiv.org/html/2609.30352#Thmexample1)\.
- Bergemannet al\.\(2025\)D\. Bergemann, A\. Bonatti, and A\. SmolinThe Economics of Large Language Models: Token Allocation, Fine\-Tuning, and Optimal Pricing\.InProceedings of the 26th ACM Conference on Economics and Computation,EC ’25,New York, NY, USA,pp\. 786\.External Links:ISBN 9798400719431,[Link](https://doi.org/10.1145/3736252.3742625),[Document](https://dx.doi.org/10.1145/3736252.3742625)Cited by:[§1](https://arxiv.org/html/2609.30352#S1.p5.1)\.
- Biet al\.\(2025\)Z\. Bi, K\. Han, C\. Liu, Y\. Tang, and Y\. WangForest\-of\-Thought: Scaling Test\-Time Compute for Enhancing LLM Reasoning\.InForty\-second International Conference on Machine Learning,External Links:[Link](https://openreview.net/forum?id=BMJ3pyYxu2)Cited by:[§1](https://arxiv.org/html/2609.30352#S1.p4.1)\.
- Bourréeet al\.\(2025\)J\. G\. Bourrée, A\. Godinot, S\. Biswas, A\. Kermarrec, E\. L\. Merrer, G\. Tredan, M\. de Vos, and M\. VujasinovicRobust ML Auditing using Prior Knowledge\.InForty\-second International Conference on Machine Learning,External Links:[Link](https://openreview.net/forum?id=AiaVCVDuxF)Cited by:[§1](https://arxiv.org/html/2609.30352#S1.p5.1)\.
- Caiet al\.\(2025\)W\. Cai, T\. Shi, X\. Zhao, and D\. SongAre You Getting What You Pay For? Auditing Model Substitution in LLM APIs\.External Links:2504\.04715,[Link](https://arxiv.org/abs/2504.04715)Cited by:[§1](https://arxiv.org/html/2609.30352#S1.p5.1)\.
- Chauvinet al\.\(2026\)T\. Chauvin, C\. Lalanne, E\. L\. Merrer, J\. Loubes, F\. Taiani, and G\. TredanToken\-Efficient Change Detection in LLM APIs\.InForty\-third International Conference on Machine Learning,External Links:[Link](https://openreview.net/forum?id=7cMlZZYZT0)Cited by:[§1](https://arxiv.org/html/2609.30352#S1.p5.1)\.
- Chenet al\.\(2026\)Y\. Chen, G\. Zhang, and M\. HardtLeaderboard Incentives: Model Rankings under Strategic Post\-Training\.InForty\-third International Conference on Machine Learning,External Links:[Link](https://openreview.net/forum?id=r6wfuAKmVb)Cited by:[§1](https://arxiv.org/html/2609.30352#S1.p5.1)\.
- Chowet al\.\(2025\)Y\. Chow, G\. Tennenholtz, I\. Gur, V\. Zhuang, B\. Dai, A\. Kumar, R\. Agarwal, S\. Thiagarajan, C\. Boutilier, and A\. FaustInference\-Aware Fine\-Tuning for Best\-of\-N Sampling in Large Language Models\.InThe Thirteenth International Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=77gQUdQhE7)Cited by:[§A\.4](https://arxiv.org/html/2609.30352#A1.SS4.p2.1),[§1](https://arxiv.org/html/2609.30352#S1.p2.1)\.
- Cobbeet al\.\(2021\)K\. Cobbe, V\. Kosaraju, M\. Bavarian, M\. Chen, H\. Jun, L\. Kaiser, M\. Plappert, J\. Tworek, J\. Hilton, R\. Nakano,et al\.Training Verifiers to Solve Math Word Problems\.arXiv preprint arXiv:2110\.14168\.Cited by:[Appendix E](https://arxiv.org/html/2609.30352#A5.p2.1),[§5](https://arxiv.org/html/2609.30352#S5.p2.1)\.
- Dalalet al\.\(2026\)G\. Dalal, A\. Hallak, G\. Chechik, and Y\. ZiserMore Test\-Time Compute Can Hurt: Overestimation Bias in LLM Beam Search\.External Links:2603\.15377,[Link](https://arxiv.org/abs/2603.15377)Cited by:[§A\.4](https://arxiv.org/html/2609.30352#A1.SS4.p3.1)\.
- Dandapanthula and Ramdas \(2026\)S\. Dandapanthula and A\. RamdasOffline changepoint localization using a matrix of conformal p\-values\.Transactions on Machine Learning Research\.Note:External Links:ISSN 2835\-8856,[Link](https://openreview.net/forum?id=bo2WlznUOc)Cited by:[§1](https://arxiv.org/html/2609.30352#S1.p6.1),[§6](https://arxiv.org/html/2609.30352#S6.p5.1)\.
- Fenget al\.\(2026\)A\. Feng, M\. Alonso, A\. Odonnat, V\. Feofanov, and I\. RedkoOptimal Self\-Consistency for Efficient Reasoning with Large Language Models\.InForty\-third International Conference on Machine Learning,External Links:[Link](https://openreview.net/forum?id=sUTC7JE781)Cited by:[§A\.3](https://arxiv.org/html/2609.30352#A1.SS3.p2.1),[§F\.1](https://arxiv.org/html/2609.30352#A6.SS1.p2.1),[§1](https://arxiv.org/html/2609.30352#S1.p3.1),[§1](https://arxiv.org/html/2609.30352#S1.p4.1),[§2](https://arxiv.org/html/2609.30352#S2.p2.2),[§2](https://arxiv.org/html/2609.30352#S2.p4.1),[§5](https://arxiv.org/html/2609.30352#S5.p1.1),[§5](https://arxiv.org/html/2609.30352#S5.p2.1)\.
- Grünwaldet al\.\(2024\)P\. Grünwald, R\. de Heide, and W\. KoolenSafe Testing\.Journal of the Royal Statistical Society Series B: Statistical Methodology86\(5\),pp\. 1091–1128\.External Links:ISSN 1369\-7412,[Document](https://dx.doi.org/10.1093/jrsssb/qkae011),[Link](https://doi.org/10.1093/jrsssb/qkae011),https://academic\.oup\.com/jrsssb/article\-pdf/86/5/1091/60648648/qkae011\.pdfCited by:[§4](https://arxiv.org/html/2609.30352#S4.p3.1)\.
- Huanget al\.\(2025\)A\. Huang, A\. Block, Q\. Liu, N\. Jiang, A\. Krishnamurthy, and D\. J\. FosterIs Best\-of\-N the Best of Them? Coverage, Scaling, and Optimality in Inference\-Time Alignment\.InForty\-second International Conference on Machine Learning,External Links:[Link](https://openreview.net/forum?id=QnjfkhrbYK)Cited by:[§A\.4](https://arxiv.org/html/2609.30352#A1.SS4.p2.1)\.
- Huanget al\.\(2026\)J\. Huang, W\. Ma, and Z\. ZhouOptimal Bayesian Stopping for Efficient Inference of Consistent LLM Answers\.InForty\-third International Conference on Machine Learning,External Links:[Link](https://openreview.net/forum?id=JXN3npSRRD)Cited by:[§A\.3](https://arxiv.org/html/2609.30352#A1.SS3.p1.1),[§1](https://arxiv.org/html/2609.30352#S1.p3.1),[§1](https://arxiv.org/html/2609.30352#S1.p4.1),[§2](https://arxiv.org/html/2609.30352#S2.p2.2)\.
- Jauerniget al\.\(2020\)P\. Jauernig, A\. Sadeghi, and E\. StapfTrusted Execution Environments: Properties, Applications, and Challenges\.IEEE Security & Privacy18\(2\),pp\. 56–60\.External Links:[Document](https://dx.doi.org/10.1109/MSEC.2019.2947124)Cited by:[§6](https://arxiv.org/html/2609.30352#S6.p6.1)\.
- Karan and Du \(2026\)A\. Karan and Y\. DuReasoning with Sampling: Your Base Model is Smarter Than You Think\.InThe Fourteenth International Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=Vsgq2ldr4K)Cited by:[§1](https://arxiv.org/html/2609.30352#S1.p4.1)\.
- Kimet al\.\(2026\)J\. Kim, N\. Yang, K\. Min, and K\. JungReliability\-Aware Adaptive Self\-Consistency for Efficient Sampling in LLM Reasoning\.InFindings of the Association for Computational Linguistics: ACL 2026,M\. Liakata, V\. P\. Moreira, J\. Zhang, and D\. Jurgens \(Eds\.\),San Diego, California, United States,pp\. 21575–21590\.External Links:[Link](https://aclanthology.org/2026.findings-acl.1085/),[Document](https://dx.doi.org/10.18653/v1/2026.findings-acl.1085),ISBN 979\-8\-89176\-395\-1Cited by:[§A\.3](https://arxiv.org/html/2609.30352#A1.SS3.p1.1)\.
- Kohet al\.\(2025\)J\. Y\. Koh, S\. M\. McAleer, D\. Fried, and R\. SalakhutdinovTree Search for Language Model Agents\.Transactions on Machine Learning Research\.Note:External Links:ISSN 2835\-8856,[Link](https://openreview.net/forum?id=QF0N3x2XVm)Cited by:[§A\.4](https://arxiv.org/html/2609.30352#A1.SS4.p3.1),[§1](https://arxiv.org/html/2609.30352#S1.p2.1),[§1](https://arxiv.org/html/2609.30352#S1.p4.1)\.
- Komiyamaet al\.\(2026\)J\. Komiyama, D\. Oba, and M\. OyamadaBest\-of\-Infinity: Asymptotic Performance of Test\-Time LLM Ensembling\.InThe Fourteenth International Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=3qiCnLf3jf)Cited by:[§1](https://arxiv.org/html/2609.30352#S1.p4.1)\.
- Lauferet al\.\(2024\)B\. Laufer, J\. Kleinberg, and H\. HeidariFine\-Tuning Games: Bargaining and Adaptation for General\-Purpose Models\.InProceedings of the ACM Web Conference 2024,WWW ’24,New York, NY, USA,pp\. 66–76\.External Links:ISBN 9798400701719,[Link](https://doi.org/10.1145/3589334.3645366),[Document](https://dx.doi.org/10.1145/3589334.3645366)Cited by:[§1](https://arxiv.org/html/2609.30352#S1.p5.1)\.
- Lehmann and Romano \(2005\)E\. L\. Lehmann and J\. P\. RomanoTesting Statistical Hypotheses\.3 edition,Springer Texts in Statistics,Springer Science\+Business Media\(en\)\.Cited by:[§4](https://arxiv.org/html/2609.30352#S4.p3.1)\.
- Liet al\.\(2024\)Y\. Li, P\. Yuan, S\. Feng, B\. Pan, X\. Wang, B\. Sun, H\. Wang, and K\. LiEscape Sky\-high Cost: Early\-stopping Self\-Consistency for Multi\-step Reasoning\.InThe Twelfth International Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=ndR8Ytrzhh)Cited by:[§A\.3](https://arxiv.org/html/2609.30352#A1.SS3.p1.1),[§F\.3](https://arxiv.org/html/2609.30352#A6.SS3.p1.1),[§6](https://arxiv.org/html/2609.30352#S6.p4.1)\.
- Mahmood \(2024\)R\. MahmoodPricing and Competition for Generative AI\.InThe Thirty\-eighth Annual Conference on Neural Information Processing Systems,External Links:[Link](https://openreview.net/forum?id=8LbJfEjIrT)Cited by:[§1](https://arxiv.org/html/2609.30352#S1.p5.1)\.
- Olmedoet al\.\(2026\)R\. Olmedo, B\. Schölkopf, and M\. HardtComputational Arbitrage in AI Model Markets\.InForty\-third International Conference on Machine Learning,External Links:[Link](https://openreview.net/forum?id=0xUvKZSQxV)Cited by:[§1](https://arxiv.org/html/2609.30352#S1.p5.1)\.
- Qiuet al\.\(2025\)T\. Qiu, B\. Laufer, J\. Kleinberg, and H\. HeidariModeling the Economic Impacts of AI Openness Regulation\.InThe Thirty\-ninth Annual Conference on Neural Information Processing Systems,External Links:[Link](https://openreview.net/forum?id=iSDKE8vec6)Cited by:[§1](https://arxiv.org/html/2609.30352#S1.p5.1)\.
- Raghavan \(2024\)M\. RaghavanCompetition and Diversity in Generative AI\.arXiv preprint arXiv:2412\.08610\.Cited by:[§1](https://arxiv.org/html/2609.30352#S1.p5.1)\.
- Ramanet al\.\(2026\)V\. Raman, H\. Asi, and S\. KaleAdaBoN: Adaptive Best\-of\-N Alignment\.External Links:2505\.12050,[Link](https://arxiv.org/abs/2505.12050)Cited by:[§A\.4](https://arxiv.org/html/2609.30352#A1.SS4.p2.2)\.
- Ramdas and Wang \(2025\)A\. Ramdas and R\. WangHypothesis Testing with E\-values\.Foundations and Trends in Statistics1\(1\-2\),pp\. 1–390\.External Links:ISSN 2978\-4212,[Document](https://dx.doi.org/10.1561/3600000002),[Link](https://doi.org/10.1561/3600000002),https://www\.emerald\.com/ftstat/article\-pdf/1/1\-2/1/11146063/3600000002en\.pdfCited by:[§C\.2](https://arxiv.org/html/2609.30352#A3.SS2.p4.1),[§4](https://arxiv.org/html/2609.30352#S4.p3.1)\.
- Ramjiet al\.\(2026\)K\. Ramji, T\. Naseem, and R\. F\. AstudilloThinking Without Words: Efficient Latent Reasoning with Abstract Chain\-of\-Thought\.arXiv preprint arXiv:2604\.22709\.Cited by:[§1](https://arxiv.org/html/2609.30352#S1.p4.1)\.
- Reinet al\.\(2024\)D\. Rein, B\. L\. Hou, A\. C\. Stickland, J\. Petty, R\. Y\. Pang, J\. Dirani, J\. Michael, and S\. R\. BowmanGPQA: A Graduate\-Level Google\-Proof Q&A Benchmark\.InFirst Conference on Language Modeling,External Links:[Link](https://openreview.net/forum?id=Ti67584b98)Cited by:[Appendix E](https://arxiv.org/html/2609.30352#A5.p2.1),[§5](https://arxiv.org/html/2609.30352#S5.p2.1)\.
- Saha and Ramdas \(2026\)A\. Saha and A\. RamdasDistribution\-free changepoint localization after sequential change detection\.arXiv preprint arXiv:2606\.01256\.Cited by:[§1](https://arxiv.org/html/2609.30352#S1.p6.1),[§6](https://arxiv.org/html/2609.30352#S6.p5.1)\.
- Sunet al\.\(2025\)G\. Sun, Z\. Wang, B\. Tian, M\. Liu, Z\. Shen, S\. He, Y\. He, W\. Ye, Y\. Wang, and A\. LiCoIn: Counting the Invisible Reasoning Tokens in Commercial Opaque LLM APIs\.External Links:2505\.13778,[Link](https://arxiv.org/abs/2505.13778)Cited by:[§1](https://arxiv.org/html/2609.30352#S1.p5.1)\.
- Sunet al\.\(2024\)H\. Sun, J\. Li, and H\. ZhangzkLLM: Zero Knowledge Proofs for Large Language Models\.InProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security,CCS ’24,New York, NY, USA,pp\. 4405–4419\.External Links:ISBN 9798400706363,[Link](https://doi.org/10.1145/3658644.3670334),[Document](https://dx.doi.org/10.1145/3658644.3670334)Cited by:[§6](https://arxiv.org/html/2609.30352#S6.p6.1)\.
- Taubenfeldet al\.\(2025\)A\. Taubenfeld, T\. Sheffer, E\. Ofek, A\. Feder, A\. Goldstein, Z\. Gekhman, and G\. YonaConfidence Improves Self\-Consistency in LLMs\.InFindings of the Association for Computational Linguistics: ACL 2025,W\. Che, J\. Nabende, E\. Shutova, and M\. T\. Pilehvar \(Eds\.\),Vienna, Austria,pp\. 20090–20111\.External Links:[Link](https://aclanthology.org/2025.findings-acl.1030/),[Document](https://dx.doi.org/10.18653/v1/2025.findings-acl.1030),ISBN 979\-8\-89176\-256\-5Cited by:[§6](https://arxiv.org/html/2609.30352#S6.p4.1)\.
- Velascoet al\.\(2026a\)A\. A\. Velasco, D\. Rontogiannis, S\. Tsirtsis, and M\. Gomez\-RodriguezTest\-Time Compute Games\.External Links:2601\.21839,[Link](https://arxiv.org/abs/2601.21839)Cited by:[Appendix E](https://arxiv.org/html/2609.30352#A5.p1.1),[Appendix E](https://arxiv.org/html/2609.30352#A5.p4.1),[§F\.4](https://arxiv.org/html/2609.30352#A6.SS4.p1.1),[§1](https://arxiv.org/html/2609.30352#S1.p5.1)\.
- Velascoet al\.\(2026b\)A\. A\. Velasco, S\. Tsirtsis, N\. Okati, and M\. G\. RodriguezIs Your LLM Overcharging You? Tokenization, Transparency, and Incentives\.InForty\-third International Conference on Machine Learning,External Links:[Link](https://openreview.net/forum?id=aGaBFE9pta)Cited by:[§1](https://arxiv.org/html/2609.30352#S1.p5.1)\.
- Velascoet al\.\(2026c\)A\. A\. Velasco, S\. Tsirtsis, and M\. G\. RodriguezAuditing Pay\-Per\-Token in Large Language Models\.InThe 29th International Conference on Artificial Intelligence and Statistics,External Links:[Link](https://openreview.net/forum?id=6lboj007YA)Cited by:[§1](https://arxiv.org/html/2609.30352#S1.p5.1),[§4](https://arxiv.org/html/2609.30352#S4.p3.1)\.
- Vovket al\.\(2003\)V\. Vovk, I\. Nouretdinov, and A\. GammermanTesting Exchangeability On\-Line\.InProceedings of the Twentieth International Conference on International Conference on Machine Learning,ICML’03,pp\. 768–775\.External Links:ISBN 1577351894Cited by:[§1](https://arxiv.org/html/2609.30352#S1.p6.1),[§6](https://arxiv.org/html/2609.30352#S6.p5.1)\.
- Vovket al\.\(2021\)V\. Vovk, I\. Petej, I\. Nouretdinov, E\. Ahlberg, L\. Carlsson, and A\. GammermanRetrain or not retrain: Conformal test martingales for change\-point detection\.InProceedings of the Tenth Symposium on Conformal and Probabilistic Prediction and Applications,L\. Carlsson, Z\. Luo, G\. Cherubin, and K\. An Nguyen \(Eds\.\),Proceedings of Machine Learning Research, Vol\.152,pp\. 191–210\.External Links:[Link](https://proceedings.mlr.press/v152/vovk21b.html)Cited by:[§1](https://arxiv.org/html/2609.30352#S1.p6.1),[§6](https://arxiv.org/html/2609.30352#S6.p5.1)\.
- Wanet al\.\(2025a\)G\. Wan, Y\. Wu, J\. Chen, and S\. LiReasoning Aware Self\-Consistency: Leveraging Reasoning Paths for Efficient LLM Sampling\.InProceedings of the 2025 Conference of the Nations of the Americas Chapter of the Association for Computational Linguistics: Human Language Technologies \(Volume 1: Long Papers\),L\. Chiruzzo, A\. Ritter, and L\. Wang \(Eds\.\),Albuquerque, New Mexico,pp\. 3613–3635\.External Links:[Link](https://aclanthology.org/2025.naacl-long.184/),[Document](https://dx.doi.org/10.18653/v1/2025.naacl-long.184),ISBN 979\-8\-89176\-189\-6Cited by:[§A\.3](https://arxiv.org/html/2609.30352#A1.SS3.p1.1)\.
- Wanet al\.\(2025b\)G\. Wan, Z\. S\. Xu, S\. Zorc, M\. Baucells, M\. Hu, H\. Wang, and S\. LiBEACON: Bayesian Optimal Stopping for Efficient LLM Sampling\.arXiv preprint arXiv:2510\.15945\.Cited by:[§A\.4](https://arxiv.org/html/2609.30352#A1.SS4.p2.2),[§1](https://arxiv.org/html/2609.30352#S1.p4.1),[§6](https://arxiv.org/html/2609.30352#S6.p2.1)\.
- Wanget al\.\(2025a\)X\. Wang, S\. Feng, Y\. Li, P\. Yuan, Y\. Zhang, C\. Tan, B\. Pan, Y\. Hu, and K\. LiMake Every Penny Count: Difficulty\-Adaptive Self\-Consistency for Cost\-Efficient Reasoning\.InFindings of the Association for Computational Linguistics: NAACL 2025,L\. Chiruzzo, A\. Ritter, and L\. Wang \(Eds\.\),Albuquerque, New Mexico,pp\. 6919–6932\.External Links:[Link](https://aclanthology.org/2025.findings-naacl.383/),[Document](https://dx.doi.org/10.18653/v1/2025.findings-naacl.383),ISBN 979\-8\-89176\-195\-7Cited by:[§A\.3](https://arxiv.org/html/2609.30352#A1.SS3.p2.1)\.
- Wanget al\.\(2023\)X\. Wang, J\. Wei, D\. Schuurmans, Q\. V\. Le, E\. H\. Chi, S\. Narang, A\. Chowdhery, and D\. ZhouSelf\-Consistency Improves Chain of Thought Reasoning in Language Models\.InThe Eleventh International Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=1PL1NIMMrw)Cited by:[§1](https://arxiv.org/html/2609.30352#S1.p2.1),[§1](https://arxiv.org/html/2609.30352#S1.p4.1),[§2](https://arxiv.org/html/2609.30352#S2.p2.1)\.
- Wanget al\.\(2025b\)Z\. Wang, G\. Sun, Y\. He, Z\. Shen, B\. Tian, and A\. LiPredictive Auditing of Hidden Tokens in LLM APIs via Reasoning Length Estimation\.External Links:2508\.00912,[Link](https://arxiv.org/abs/2508.00912)Cited by:[§1](https://arxiv.org/html/2609.30352#S1.p5.1)\.
- Weiet al\.\(2022\)J\. Wei, X\. Wang, D\. Schuurmans, M\. Bosma, F\. Xia, E\. Chi, Q\. V\. Le, D\. Zhou,et al\.Chain\-of\-thought prompting elicits reasoning in large language models\.Advances in neural information processing systems35,pp\. 24824–24837\.Cited by:[§1](https://arxiv.org/html/2609.30352#S1.p2.1)\.
- Wuet al\.\(2026\)Y\. Wu, Y\. Wang, Z\. Ye, T\. Du, S\. Jegelka, and Y\. WangWhen More is Less: Understanding Chain\-of\-Thought Length in LLMs\.InThe Fourteenth International Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=6QDFsYxtI1)Cited by:[§1](https://arxiv.org/html/2609.30352#S1.p4.1)\.
- Yaoet al\.\(2023\)S\. Yao, D\. Yu, J\. Zhao, I\. Shafran, T\. L\. Griffiths, Y\. Cao, and K\. R\. NarasimhanTree of Thoughts: Deliberate Problem Solving with Large Language Models\.InThirty\-seventh Conference on Neural Information Processing Systems,External Links:[Link](https://openreview.net/forum?id=5Xc1ecxO1h)Cited by:[§A\.4](https://arxiv.org/html/2609.30352#A1.SS4.p3.1),[§1](https://arxiv.org/html/2609.30352#S1.p2.1)\.
- Yoshiyamaet al\.\(2026\)A\. Yoshiyama, A\. Ashirmatov, J\. Hübotter, I\. Hakimi, and A\. KrauseTest\-Time Scaling with Weak Verifiers via Self\-Play\.InDeep Learning for Code: Towards Human\-Centered Coding Agents,External Links:[Link](https://openreview.net/forum?id=oYX0DXuv7a)Cited by:[§1](https://arxiv.org/html/2609.30352#S1.p2.1),[§1](https://arxiv.org/html/2609.30352#S1.p4.1)\.
- Zhang and Math\-AI \(2025\)Y\. Zhang and T\. Math\-AIAmerican Invitational Mathematics Examination \(AIME\) 2025\.Cited by:[Appendix E](https://arxiv.org/html/2609.30352#A5.p2.1),[§5](https://arxiv.org/html/2609.30352#S5.p2.1)\.
- Zhuet al\.\(2026\)X\. Zhu, Y\. Ye, T\. Qiu, H\. Zhu, S\. Tan, A\. Mannan, J\. Michala, R\. Popa, and W\. NeiswangerAuditing Black\-Box LLM APIs with a Rank\-Based Uniformity Test\.InInternational Conference on Learning Representations,Vol\.2026,pp\. 54232–54261\.Cited by:[§1](https://arxiv.org/html/2609.30352#S1.p5.1)\.

## Appendix AAdmissibility of Stopping Rules

In this section, we show that the stopping rules described in Examples[1](https://arxiv.org/html/2609.30352#Thmexample1)and[2](https://arxiv.org/html/2609.30352#Thmexample2)of Section[2](https://arxiv.org/html/2609.30352#S2)are admissible,*i\.e\.*, that they satisfy Definition[3](https://arxiv.org/html/2609.30352#Thmtheorem3)\. We then discuss how the conditions in Definition[3](https://arxiv.org/html/2609.30352#Thmtheorem3)apply to other adaptive stopping rules proposed in the literature\.

### A\.1Admissibility of PPR\-1v1

We verify that the PPR\-1v1 stopping rule\([Anand Jain et al\., 2022](https://arxiv.org/html/2609.30352#bib.bib1)\)satisfies the four conditions of Definition[3](https://arxiv.org/html/2609.30352#Thmtheorem3)\. Recall that this stopping rule is defined as

τPPR\-1v1​\(s\(1\),s\(2\)\)\\displaystyle\\tau\_\{\\text\{PPR\-1v1\}\}\(s\_\{\(1\)\},s\_\{\(2\)\}\)=𝟙\[f\(12;s\(1\)\+1,s\(2\)\+1\)≤δK−1\],\\displaystyle=\\mathbbm\{1\}\\Bigl\[f\\Bigl\(\\frac\{1\}\{2\};s\_\{\(1\)\}\+1,s\_\{\(2\)\}\+1\\Bigr\)\\leq\\frac\{\\delta\}\{K\-1\}\\Bigr\],whereffdenotes the density of the Beta distribution:

f⁡\(12,s\(1\)\+1,s\(2\)\+1\)=\(1/2\)s\(1\)⋅\(1/2\)s\(2\)∫01qs\(1\)⋅\(1−q\)s\(2\)​𝑑q\.f\\Bigl\(\\frac\{1\}\{2\};s\_\{\(1\)\}\+1,s\_\{\(2\)\}\+1\\Bigr\)=\\frac\{\(1/2\)^\{s\_\{\(1\)\}\}\\cdot\\,\(1/2\)^\{s\_\{\(2\)\}\}\}\{\\int\_\{0\}^\{1\}q^\{s\_\{\(1\)\}\}\\cdot\(1\-q\)^\{s\_\{\(2\)\}\}\\,dq\}\.
Thus, a sequence with counts\(s\(1\),s\(2\)\)\(s\_\{\(1\)\},s\_\{\(2\)\}\)does*not*trigger the stopping rule wheneverf⁡\(12,s\(1\)\+1,s\(2\)\+1\)\>δK−1f\\Bigl\(\\frac\{1\}\{2\};s\_\{\(1\)\}\+1,s\_\{\(2\)\}\+1\\Bigr\)\>\\frac\{\\delta\}\{K\-1\}\.

- i\)Count invariance follows immediately because the stopping decision depends only on the current leader and runner\-up counts, regardless of their identities or the order of preceding samples\.
- ii\)Nontriviality, orτPPR\-1v1​\(1,0\)=0\\tau\_\{\\text\{PPR\-1v1\}\}\(1,0\)=0, follows from Lemma[1](https://arxiv.org/html/2609.30352#Thmlemma1)\.
- iii\)Monotonicity in the second most frequent count follows from Lemma[2](https://arxiv.org/html/2609.30352#Thmlemma2)\.
- iv\)Fixed\-margin monotonicity follows from Lemma[3](https://arxiv.org/html/2609.30352#Thmlemma3)\.

###### Lemma 1\(Nontriviality of PPR\-1v1\)\.

A single observation is insufficient to trigger PPR\-1v1 stopping; that is,τPPR\-1v1​\(1,0\)=0\\tau\_\{\\text\{PPR\-1v1\}\}\(1,0\)=0\.

###### Proof of Lemma[1](https://arxiv.org/html/2609.30352#Thmlemma1)\.

Fix anyδ∈\(0,1\)\\delta\\in\(0,1\)andK≥2K\\geq 2\. We want to showτPPR\-1v1​\(1,0\)=0\\tau\_\{\\text\{PPR\-1v1\}\}\(1,0\)=0\. Evaluating the Beta density at\(s\(1\),s\(2\)\)=\(1,0\)\(s\_\{\(1\)\},s\_\{\(2\)\}\)=\(1,0\)gives:

f⁡\(12,1\+1,0\+1\)\\displaystyle f\\Bigl\(\\frac\{1\}\{2\};1\+1,0\+1\\Bigr\)=2−\(1\+0\)​\(0\+1\+1\)⋅\(1\+0\)\!1\!​\(1\+0−1\)\!=1\.\\displaystyle=2^\{\-\(1\+0\)\}\(0\+1\+1\)\\cdot\\frac\{\(1\+0\)\!\}\{1\!\(1\+0\-1\)\!\}=1\.
Sinceδ∈\(0,1\)\\delta\\in\(0,1\)andK≥2K\\geq 2, we haveδK−1≤δ<1\\frac\{\\delta\}\{K\-1\}\\leq\\delta<1\. Therefore,f⁡\(12,1\+1,0\+1\)\>δK−1f\(\\frac\{1\}\{2\};1\+1,0\+1\)\>\\frac\{\\delta\}\{K\-1\}, so the stopping condition is not satisfied andτPPR\-1v1​\(1,0\)=0\\tau\_\{\\text\{PPR\-1v1\}\}\(1,0\)=0\. ∎

###### Lemma 2\(Monotonicity in the second most frequent count of PPR\-1v1\)\.

Suppose that counts\(s\(1\),s\(2\)\)\(s\_\{\(1\)\},s\_\{\(2\)\}\), withs\(1\)≥s\(2\)\+1s\_\{\(1\)\}\\geq s\_\{\(2\)\}\+1, do not trigger PPR\-1v1\. Then\(s\(1\),s\(2\)\+1\)\(s\_\{\(1\)\},s\_\{\(2\)\}\+1\)also do not trigger PPR\-1v1\.

###### Proof of Lemma[2](https://arxiv.org/html/2609.30352#Thmlemma2)\.

Assume thatτPPR\-1v1​\(s\(1\),s\(2\)\)=0\\tau\_\{\\text\{PPR\-1v1\}\}\(s\_\{\(1\)\},s\_\{\(2\)\}\)=0\. To showτPPR\-1v1​\(s\(1\),s\(2\)\+1\)=0\\tau\_\{\\text\{PPR\-1v1\}\}\(s\_\{\(1\)\},s\_\{\(2\)\}\+1\)=0, compare the Beta densities*after*and*before*incrementing the second most frequent count:

f⁡\(12,s\(1\)\+1,s\(2\)\+2\)f⁡\(12,s\(1\)\+1,s\(2\)\+1\)\\displaystyle\\frac\{f\(\\frac\{1\}\{2\};\\;s\_\{\(1\)\}\+1,s\_\{\(2\)\}\+2\)\}\{f\(\\frac\{1\}\{2\};\\;s\_\{\(1\)\}\+1,s\_\{\(2\)\}\+1\)\}=\(s\(1\)\+s\(2\)\+2\)​\(s\(1\)\+s\(2\)\+1\)\!2\(s\(1\)\+s\(2\)\+1\)​s\(1\)\!​\(s\(2\)\+1\)\!⋅2\(s\(1\)\+s\(2\)\)​s\(1\)\!​s\(2\)\!\(s\(1\)\+s\(2\)\+1\)​\(s\(1\)\+s\(2\)\)\!\\displaystyle=\\frac\{\(s\_\{\(1\)\}\+s\_\{\(2\)\}\+2\)\(s\_\{\(1\)\}\+s\_\{\(2\)\}\+1\)\!\}\{2^\{\(s\_\{\(1\)\}\+s\_\{\(2\)\}\+1\)\}s\_\{\(1\)\}\!\\,\(s\_\{\(2\)\}\+1\)\!\}\\cdot\\frac\{2^\{\(s\_\{\(1\)\}\+s\_\{\(2\)\}\)\}\\,s\_\{\(1\)\}\!\\,s\_\{\(2\)\}\!\}\{\(s\_\{\(1\)\}\+s\_\{\(2\)\}\+1\)\(s\_\{\(1\)\}\+s\_\{\(2\)\}\)\!\}=\(s\(1\)\+s\(2\)\+2\)​\(s\(1\)\+s\(2\)\+1\)\!2​\(s\(2\)\+1\)\!⋅s\(2\)\!\(s\(1\)\+s\(2\)\+1\)\!\\displaystyle=\\frac\{\(s\_\{\(1\)\}\+s\_\{\(2\)\}\+2\)\(s\_\{\(1\)\}\+s\_\{\(2\)\}\+1\)\!\}\{2\(s\_\{\(2\)\}\+1\)\!\}\\cdot\\frac\{s\_\{\(2\)\}\!\}\{\(s\_\{\(1\)\}\+s\_\{\(2\)\}\+1\)\!\}=\(s\(1\)\+s\(2\)\+2\)​s\(2\)\!2​\(s\(2\)\+1\)\!=s\(1\)\+s\(2\)\+22​\(s\(2\)\+1\)\.\\displaystyle=\\frac\{\(s\_\{\(1\)\}\+s\_\{\(2\)\}\+2\)s\_\{\(2\)\}\!\}\{2\(s\_\{\(2\)\}\+1\)\!\}=\\frac\{s\_\{\(1\)\}\+s\_\{\(2\)\}\+2\}\{2\(s\_\{\(2\)\}\+1\)\}\.
Sinces\(1\)\>s\(2\)s\_\{\(1\)\}\>s\_\{\(2\)\}, we haves\(1\)\+s\(2\)\+2\>2​\(s\(2\)\+1\)s\_\{\(1\)\}\+s\_\{\(2\)\}\+2\>2\(s\_\{\(2\)\}\+1\), meaning the ratio above is greater than one\. Furthermore, sinceτPPR\-1v1​\(s\(1\),s\(2\)\)=0\\tau\_\{\\text\{PPR\-1v1\}\}\(s\_\{\(1\)\},s\_\{\(2\)\}\)=0, it follows thatf⁡\(12,s\(1\)\+1,s\(2\)\+1\)\>δK−1f\\bigl\(\\frac\{1\}\{2\};s\_\{\(1\)\}\+1,s\_\{\(2\)\}\+1\\big\)\>\\frac\{\\delta\}\{K\-1\}and:

f⁡\(12,s\(1\)\+1,s\(2\)\+2\)\>f⁡\(12,s\(1\)\+1,s\(2\)\+1\)\>δK−1\.\\displaystyle f\\left\(\\frac\{1\}\{2\};s\_\{\(1\)\}\+1,s\_\{\(2\)\}\+2\\right\)\>f\\left\(\\frac\{1\}\{2\};s\_\{\(1\)\}\+1,s\_\{\(2\)\}\+1\\right\)\>\\frac\{\\delta\}\{K\-1\}\.Thus,τPPR\-1v1​\(s\(1\),s\(2\)\+1\)=0\\tau\_\{\\text\{PPR\-1v1\}\}\(s\_\{\(1\)\},s\_\{\(2\)\}\+1\)=0\. ∎

###### Lemma 3\(Fixed\-margin monotonicity of PPR\-1v1\)\.

Suppose that counts\(s\(1\),s\(2\)\)\(s\_\{\(1\)\},s\_\{\(2\)\}\)do not trigger PPR\-1v1\. Then, holding the margins\(1\)−s\(2\)s\_\{\(1\)\}\-s\_\{\(2\)\}fixed, incrementing both counts by a common positive integer also does not trigger PPR\-1v1\.

###### Proof of Lemma[3](https://arxiv.org/html/2609.30352#Thmlemma3)\.

Assume thatτPPR\-1v1​\(s\(1\),s\(2\)\)=0\\tau\_\{\\text\{PPR\-1v1\}\}\(s\_\{\(1\)\},s\_\{\(2\)\}\)=0and fix anyc∈ℕ\+c\\in\\mathbb\{N\}^\{\+\}\. We first establish the result forc=1c=1by comparing the Beta densities before and after incrementing both counts:

f⁡\(12,s\(1\)\+2,s\(2\)\+2\)f⁡\(12,s\(1\)\+1,s\(2\)\+1\)\\displaystyle\\frac\{f\\bigl\(\\frac\{1\}\{2\};s\_\{\(1\)\}\+2,s\_\{\(2\)\}\+2\\bigr\)\}\{f\\bigl\(\\frac\{1\}\{2\};s\_\{\(1\)\}\+1,s\_\{\(2\)\}\+1\\bigr\)\}=\(s\(1\)\+s\(2\)\+3\)\!22​\(s\(1\)\+1\)\!​\(s\(2\)\+1\)\!⋅s\(1\)\!​s\(2\)\!\(s\(1\)\+s\(2\)\+1\)\!\\displaystyle=\\frac\{\(s\_\{\(1\)\}\+s\_\{\(2\)\}\+3\)\!\}\{2^\{2\}\\,\(s\_\{\(1\)\}\+1\)\!\\,\(s\_\{\(2\)\}\+1\)\!\}\\cdot\\frac\{s\_\{\(1\)\}\!\\,s\_\{\(2\)\}\!\}\{\(s\_\{\(1\)\}\+s\_\{\(2\)\}\+1\)\!\}=\(s\(1\)\+s\(2\)\+3\)​\(s\(1\)\+s\(2\)\+2\)4​\(s\(1\)\+1\)​\(s\(2\)\+1\)\.\\displaystyle=\\frac\{\(s\_\{\(1\)\}\+s\_\{\(2\)\}\+3\)\(s\_\{\(1\)\}\+s\_\{\(2\)\}\+2\)\}\{4\(s\_\{\(1\)\}\+1\)\(s\_\{\(2\)\}\+1\)\}\.
To determine whether this ratio exceeds one, subtract the denominator from the numerator:

\(s\(1\)\+s\(2\)\+3\)​\(s\(1\)\+s\(2\)\+2\)−4​\(s\(1\)\+1\)​\(s\(2\)\+1\)\\displaystyle\(s\_\{\(1\)\}\+s\_\{\(2\)\}\+3\)\(s\_\{\(1\)\}\+s\_\{\(2\)\}\+2\)\-4\(s\_\{\(1\)\}\+1\)\(s\_\{\(2\)\}\+1\)=\(s\(1\)−s\(2\)\)2\+s\(1\)\+s\(2\)\+2\.\\displaystyle=\(s\_\{\(1\)\}\-s\_\{\(2\)\}\)^\{2\}\+s\_\{\(1\)\}\+s\_\{\(2\)\}\+2\.
Since\(s\(1\)−s\(2\)\)2\+s\(1\)\+s\(2\)\+2\>0\(s\_\{\(1\)\}\-s\_\{\(2\)\}\)^\{2\}\+s\_\{\(1\)\}\+s\_\{\(2\)\}\+2\>0, we havef⁡\(12,s\(1\)\+2,s\(2\)\+2\)\>f⁡\(12,s\(1\)\+1,s\(2\)\+1\)f\\bigl\(\\frac\{1\}\{2\};s\_\{\(1\)\}\+2,s\_\{\(2\)\}\+2\\bigr\)\>f\\bigl\(\\frac\{1\}\{2\};s\_\{\(1\)\}\+1,s\_\{\(2\)\}\+1\\bigr\)\. Iterating the same argumentcctimes givesf⁡\(12,s\(1\)\+c\+1,s\(2\)\+c\+1\)\>f⁡\(12,s\(1\)\+1,s\(2\)\+1\)\>δK−1f\(\\frac\{1\}\{2\};s\_\{\(1\)\}\+c\+1,s\_\{\(2\)\}\+c\+1\)\>f\(\\frac\{1\}\{2\};s\_\{\(1\)\}\+1,s\_\{\(2\)\}\+1\)\>\\frac\{\\delta\}\{K\-1\}, and thereforeτPPR\-1v1​\(s\(1\)\+c,s\(2\)\+c\)=0\\tau\_\{\\text\{PPR\-1v1\}\}\(s\_\{\(1\)\}\+c,s\_\{\(2\)\}\+c\)=0\.

∎

### A\.2Admissibility of ASC

We verify that the ASC Beta criterion\([Aggarwal et al\., 2023](https://arxiv.org/html/2609.30352#bib.bib4)\)with confidence parameterγ∈\(3/4,1\)\\gamma\\in\(3/4,1\)satisfies the four conditions of Definition[3](https://arxiv.org/html/2609.30352#Thmtheorem3)\. Recall that the ASC stopping rule is:

τASC​\(s\(1\),s\(2\)\)\\displaystyle\\tau\_\{\\text\{ASC\}\}\(s\_\{\(1\)\},s\_\{\(2\)\}\)=𝟙\[∫1/21qs\(1\)⋅\(1−q\)s\(2\)​𝑑q∫01qs\(1\)⋅\(1−q\)s\(2\)​𝑑q≥γ\]\.\\displaystyle=\\mathbbm\{1\}\\Bigl\[\\frac\{\\int\_\{1/2\}^\{1\}q^\{s\_\{\(1\)\}\}\\cdot\(1\-q\)^\{s\_\{\(2\)\}\}\\,dq\}\{\\int\_\{0\}^\{1\}q^\{s\_\{\(1\)\}\}\\cdot\(1\-q\)^\{s\_\{\(2\)\}\}\\,dq\}\\geq\\gamma\\Bigr\]\.
For convenience, define:

H⁡\(s\(1\),s\(2\)\)\\displaystyle H\(s\_\{\(1\)\},s\_\{\(2\)\}\):=∫1/21qs\(1\)⋅\(1−q\)s\(2\)​𝑑q∫01qs\(1\)⋅\(1−q\)s\(2\)​𝑑q\.\\displaystyle:=\\frac\{\\int\_\{1/2\}^\{1\}q^\{s\_\{\(1\)\}\}\\cdot\(1\-q\)^\{s\_\{\(2\)\}\}\\,dq\}\{\\int\_\{0\}^\{1\}q^\{s\_\{\(1\)\}\}\\cdot\(1\-q\)^\{s\_\{\(2\)\}\}\\,dq\}\.
A sequence with counts\(s\(1\),s\(2\)\)\(s\_\{\(1\)\},s\_\{\(2\)\}\)does*not*trigger the ASC stopping rule wheneverH⁡\(s\(1\),s\(2\)\)<γH\(s\_\{\(1\)\},s\_\{\(2\)\}\)<\\gamma\. For integer counts, the beta\-binomial identity gives:

H⁡\(s\(1\),s\(2\)\)\\displaystyle H\(s\_\{\(1\)\},s\_\{\(2\)\}\)=Pr​\(Xs\(1\)\+s\(2\)\+1≤s\(1\)\),where​Xs\(1\)\+s\(2\)\+1∼Binom⁡\(s\(1\)\+s\(2\)\+1,12\)\.\\displaystyle=\\text\{Pr\}\\bigl\(X\_\{s\_\{\(1\)\}\+s\_\{\(2\)\}\+1\}\\leq s\_\{\(1\)\}\\bigr\),\\qquad\\text\{ where \}X\_\{s\_\{\(1\)\}\+s\_\{\(2\)\}\+1\}\\sim\\mathrm\{Binom\}\\Bigl\(s\_\{\(1\)\}\+s\_\{\(2\)\}\+1,\\frac\{1\}\{2\}\\Bigr\)\.
We use this representation to verify the four admissibility conditions\.

- i\)Count invariance follows immediately becauseH⁡\(s\(1\),s\(2\)\)H\(s\_\{\(1\)\},s\_\{\(2\)\}\), and hence theτASC\\tau\_\{\\text\{ASC\}\}stopping decision, depends only on counts\(s\(1\),s\(2\)\)\(s\_\{\(1\)\},s\_\{\(2\)\}\)\.
- ii\)Nontriviality, orτASC​\(1,0\)=0\\tau\_\{\\text\{ASC\}\}\(1,0\)=0, follows from Lemma[4](https://arxiv.org/html/2609.30352#Thmlemma4)\.
- iii\)Monotonicity in the second most frequent count follows from Lemma[5](https://arxiv.org/html/2609.30352#Thmlemma5)\.
- iv\)Fixed\-margin monotonicity follows from Lemma[6](https://arxiv.org/html/2609.30352#Thmlemma6)\.

###### Lemma 4\(Nontriviality of ASC\)\.

For anyγ\>3/4\\gamma\>3/4, a single observation is insufficient to trigger the ASC Beta criterion; that is,τASC​\(1,0\)=0\\tau\_\{\\text\{ASC\}\}\(1,0\)=0\.

###### Proof of Lemma[4](https://arxiv.org/html/2609.30352#Thmlemma4)\.

Fors\(1\)=1s\_\{\(1\)\}=1ands\(2\)=0s\_\{\(2\)\}=0,

H⁡\(1,0\)\\displaystyle H\(1,0\)=∫1/21q​𝑑q∫01q​𝑑q=34\.\\displaystyle=\\frac\{\\int\_\{1/2\}^\{1\}q\\;dq\}\{\\int\_\{0\}^\{1\}q\\;dq\}=\\frac\{3\}\{4\}\.Therefore, wheneverγ\>34\\gamma\>\\frac\{3\}\{4\}, we haveH⁡\(1,0\)<γH\(1,0\)<\\gamma, and henceτASC​\(1,0\)=0\\tau\_\{\\text\{ASC\}\}\(1,0\)=0\. ∎

###### Lemma 5\(Monotonicity in the second most frequent count of ASC\)\.

Suppose that counts\(s\(1\),s\(2\)\)\(s\_\{\(1\)\},s\_\{\(2\)\}\), withs\(1\)≥s\(2\)\+1s\_\{\(1\)\}\\geq s\_\{\(2\)\}\+1, do not trigger the ASC stopping rule\. Then\(s\(1\),s\(2\)\+1\)\(s\_\{\(1\)\},s\_\{\(2\)\}\+1\)also do not trigger the ASC stopping rule\.

###### Proof of Lemma[5](https://arxiv.org/html/2609.30352#Thmlemma5)\.

Assume thatτASC​\(s\(1\),s\(2\)\)=0\\tau\_\{\\text\{ASC\}\}\(s\_\{\(1\)\},s\_\{\(2\)\}\)=0, and letm=s\(1\)\+s\(2\)\+1m=s\_\{\(1\)\}\+s\_\{\(2\)\}\+1\. Using the beta\-binomial representation,H⁡\(s\(1\),s\(2\)\)=Pr​\(Xm≤s\(1\)\)H\(s\_\{\(1\)\},s\_\{\(2\)\}\)=\\text\{Pr\}\(X\_\{m\}\\leq s\_\{\(1\)\}\)\. After increasing the runner\-up count by one,H⁡\(s\(1\),s\(2\)\+1\)=Pr​\(Xm\+1≤s\(1\)\)H\(s\_\{\(1\)\},s\_\{\(2\)\}\+1\)=\\text\{Pr\}\(X\_\{m\+1\}\\leq s\_\{\(1\)\}\)\. WriteXm\+1=Xm\+BX\_\{m\+1\}=X\_\{m\}\+B, whereB∼Bernoulli⁡\(12\)B\\sim\\mathrm\{Bernoulli\}\(\\frac\{1\}\{2\}\)is independent ofXmX\_\{m\}\. Then:

H⁡\(s\(1\),s\(2\)\+1\)\\displaystyle H\(s\_\{\(1\)\},s\_\{\(2\)\}\+1\)=Pr​\(Xm\+B≤s\(1\)\)\\displaystyle=\\text\{Pr\}\(X\_\{m\}\+B\\leq s\_\{\(1\)\}\)=Pr​\(Xm≤s\(1\)−1\)\+12​Pr​\(Xm=s\(1\)\)\\displaystyle=\\text\{Pr\}\(X\_\{m\}\\leq s\_\{\(1\)\}\-1\)\+\\frac\{1\}\{2\}\\text\{Pr\}\(X\_\{m\}=s\_\{\(1\)\}\)=Pr​\(Xm≤s\(1\)\)−12​Pr​\(Xm=s\(1\)\)\\displaystyle=\\text\{Pr\}\(X\_\{m\}\\leq s\_\{\(1\)\}\)\-\\frac\{1\}\{2\}\\text\{Pr\}\(X\_\{m\}=s\_\{\(1\)\}\)<H⁡\(s\(1\),s\(2\)\)\.\\displaystyle<H\(s\_\{\(1\)\},s\_\{\(2\)\}\)\.
Thus, increasing the runner\-up count strictly decreases the ASC confidence in the empirical leader\. From our assumption thatτASC​\(s\(1\),s\(2\)\)=0\\tau\_\{\\text\{ASC\}\}\(s\_\{\(1\)\},s\_\{\(2\)\}\)=0, we knowH⁡\(s\(1\),s\(2\)\)<γH\(s\_\{\(1\)\},s\_\{\(2\)\}\)<\\gammaand thereforeH⁡\(s\(1\),s\(2\)\+1\)<H⁡\(s\(1\),s\(2\)\)<γH\(s\_\{\(1\)\},s\_\{\(2\)\}\+1\)<H\(s\_\{\(1\)\},s\_\{\(2\)\}\)<\\gamma\. This showsτASC​\(s\(1\),s\(2\)\+1\)=0\\tau\_\{\\text\{ASC\}\}\(s\_\{\(1\)\},s\_\{\(2\)\}\+1\)=0\. ∎

###### Lemma 6\(Fixed\-margin monotonicity of ASC\)\.

Suppose that counts\(s\(1\),s\(2\)\)\(s\_\{\(1\)\},s\_\{\(2\)\}\)do not trigger the ASC stopping rule withγ\>3/4\\gamma\>3/4\. Then, holdings\(1\)−s\(2\)s\_\{\(1\)\}\-s\_\{\(2\)\}fixed, incrementing both counts by a common positive integer also does not trigger the ASC stopping rule\.

###### Proof of Lemma[6](https://arxiv.org/html/2609.30352#Thmlemma6)\.

Assume thatτASC​\(s\(1\),s\(2\)\)=0\\tau\_\{\\text\{ASC\}\}\(s\_\{\(1\)\},s\_\{\(2\)\}\)=0and fix anyc∈ℕ\+c\\in\\mathbb\{N\}^\{\+\}\.Letm=s\(1\)\+s\(2\)\+1m=s\_\{\(1\)\}\+s\_\{\(2\)\}\+1andXm∼Binom⁡\(m,12\)X\_\{m\}\\sim\\mathrm\{Binom\}\(m,\\frac\{1\}\{2\}\)so thatH⁡\(s\(1\),s\(2\)\)=Pr​\(Xm≤s\(1\)\)H\(s\_\{\(1\)\},s\_\{\(2\)\}\)=\\text\{Pr\}\(X\_\{m\}\\leq s\_\{\(1\)\}\)\. After increasing both counts by one, we haveH⁡\(s\(1\)\+1,s\(2\)\+1\)=Pr​\(Xm\+2≤s\(1\)\+1\)H\(s\_\{\(1\)\}\+1,s\_\{\(2\)\}\+1\)=\\text\{Pr\}\(X\_\{m\+2\}\\leq s\_\{\(1\)\}\+1\)\. WriteXm\+2=Xm\+B1\+B2X\_\{m\+2\}=X\_\{m\}\+B\_\{1\}\+B\_\{2\}, whereB1,B2B\_\{1\},B\_\{2\}are independentBernoulli⁡\(12\)\\mathrm\{Bernoulli\}\(\\frac\{1\}\{2\}\)random variables\. Conditioning onXmX\_\{m\},

H⁡\(s\(1\)\+1,s\(2\)\+1\)\\displaystyle H\(s\_\{\(1\)\}\+1,s\_\{\(2\)\}\+1\)=Pr​\(Xm≤s\(1\)−1\)\+34​Pr⁡\(Xm=s\(1\)\)\+14​Pr⁡\(Xm=s\(1\)\+1\)\\displaystyle=\\text\{Pr\}\(X\_\{m\}\\leq s\_\{\(1\)\}\-1\)\+\\frac\{3\}\{4\}\\Pr\(X\_\{m\}=s\_\{\(1\)\}\)\+\\frac\{1\}\{4\}\\Pr\(X\_\{m\}=s\_\{\(1\)\}\+1\)=H⁡\(s\(1\),s\(2\)\)\+14​\[Pr​\(Xm=s\(1\)\+1\)−Pr⁡\(Xm=s\(1\)\)\]\.\\displaystyle=H\(s\_\{\(1\)\},s\_\{\(2\)\}\)\+\\frac\{1\}\{4\}\\Bigl\[\\text\{Pr\}\(X\_\{m\}=s\_\{\(1\)\}\+1\)\-\\Pr\(X\_\{m\}=s\_\{\(1\)\}\)\\Bigr\]\.ForXm∼Binom⁡\(m,12\)X\_\{m\}\\sim\\mathrm\{Binom\}\(m,\\frac\{1\}\{2\}\)ands\(2\)≤s\(1\)s\_\{\(2\)\}\\leq s\_\{\(1\)\},

Pr​\(Xm=s\(1\)\+1\)Pr​\(Xm=s\(1\)\)\\displaystyle\\frac\{\\text\{Pr\}\(X\_\{m\}=s\_\{\(1\)\}\+1\)\}\{\\text\{Pr\}\(X\_\{m\}=s\_\{\(1\)\}\)\}=m−s\(1\)s\(1\)\+1=s\(2\)\+1s\(1\)\+1≤1\.\\displaystyle=\\frac\{m\-s\_\{\(1\)\}\}\{s\_\{\(1\)\}\+1\}=\\frac\{s\_\{\(2\)\}\+1\}\{s\_\{\(1\)\}\+1\}\\leq 1\.Therefore,Pr​\(Xm=s\(1\)\+1\)≤Pr​\(Xm=s\(1\)\)\\text\{Pr\}\(X\_\{m\}=s\_\{\(1\)\}\+1\)\\leq\\text\{Pr\}\(X\_\{m\}=s\_\{\(1\)\}\)which impliesH⁡\(s\(1\)\+1,s\(2\)\+1\)≤H⁡\(s\(1\),s\(2\)\)H\(s\_\{\(1\)\}\+1,s\_\{\(2\)\}\+1\)\\leq H\(s\_\{\(1\)\},s\_\{\(2\)\}\)\. Iterating the same argumentcctimes givesH⁡\(s\(1\)\+c,s\(2\)\+c\)≤H⁡\(s\(1\),s\(2\)\)H\(s\_\{\(1\)\}\+c,s\_\{\(2\)\}\+c\)\\leq H\(s\_\{\(1\)\},s\_\{\(2\)\}\)for anyc∈ℕ\+c\\in\\mathbb\{N\}^\{\+\}\. From our assumption thatτASC​\(s\(1\),s\(2\)\)=0\\tau\_\{\\text\{ASC\}\}\(s\_\{\(1\)\},s\_\{\(2\)\}\)=0, we haveH⁡\(s\(1\),s\(2\)\)<γH\(s\_\{\(1\)\},s\_\{\(2\)\}\)<\\gamma\. Thus,H⁡\(s\(1\)\+c,s\(2\)\+c\)≤H⁡\(s\(1\),s\(2\)\)<γH\(s\_\{\(1\)\}\+c,s\_\{\(2\)\}\+c\)\\leq H\(s\_\{\(1\)\},s\_\{\(2\)\}\)<\\gamma\. This showsτASC​\(s\(1\)\+c,s\(2\)\+c\)=0\\tau\_\{\\text\{ASC\}\}\(s\_\{\(1\)\}\+c,s\_\{\(2\)\}\+c\)=0, as required\. ∎

### A\.3Additional Self\-Consistency Stopping Rules

The admissibility conditions in Definition[3](https://arxiv.org/html/2609.30352#Thmtheorem3)characterize stopping rules that depend only on the counts of the empirical mode and runner\-up and satisfy natural monotonicity properties\. Here, we briefly review other adaptive self\-consistency methods from the literature, many of which use information beyond the top\-two counts and are therefore not admissible\. For example, Early\-Stopping Self\-Consistency \(ESC\)\([Li et al\., 2024](https://arxiv.org/html/2609.30352#bib.bib5)\)stops when all responses within a fixed recent window agree\. Since stopping then depends only on which responses appear in the most recent window rather than on cumulative answer counts, ESC violates count invariance and is not admissible\. Other methods leverage additional information beyond the answer counts\. Reliability\-Aware Adaptive Self\-Consistency \(ReASC\)\([Kim et al\., 2026](https://arxiv.org/html/2609.30352#bib.bib41)\)augments response counts with the model’s confidence in its generated responses, as measured by the token probabilities assigned to each reasoning path\. Reasoning\-Aware Self\-Consistency \(RASC\)\([Wan et al\., 2025a](https://arxiv.org/html/2609.30352#bib.bib44)\)instead uses a learned network to extract features from individual reasoning paths and estimate their quality\. Similarly,[Huang et al\. \(2026\)](https://arxiv.org/html/2609.30352#bib.bib30)augment the top two response counts with an informative prior over query difficulty, estimated from past model generations on similar queries\.

Beyond determining the number of samples for an individual query,[Feng et al\. \(2026\)](https://arxiv.org/html/2609.30352#bib.bib2)propose BlendASC, which combines adaptive stopping with a shared inference budget across a*set*of queries and allocates samples according to their relative uncertainty\. Whether a particular query receives another sample therefore depends not only on its own response counts but also on the states of the other queries competing for the shared budget\. Consequently, BlendASC cannot in general be represented by a fixed per\-query ruleτ⁡\(s\(1\),s\(2\)\)\\tau\(s\_\{\(1\)\},s\_\{\(2\)\}\)and is not admissible\. Similarly, Difficulty\-Adaptive Self\-Consistency \(DSC\)\([Wang et al\., 2025a](https://arxiv.org/html/2609.30352#bib.bib42)\)uses estimates of query difficulty across a set of queries to allocate compute\.

### A\.4Extensions Beyond Self\-Consistency

Although our main analysis focuses on self\-consistency, Algorithm[1](https://arxiv.org/html/2609.30352#alg1)exploits features shared by a broader class of sequential test\-time compute methods\.

Adaptive best\-of\-NN\.Best\-of\-NN\([Chow et al\., 2025](https://arxiv.org/html/2609.30352#bib.bib39);[Huang et al\., 2025](https://arxiv.org/html/2609.30352#bib.bib29)\)generatesNNindependent reasoning paths, scores each one using an auxiliary scoring model, and returns the highest\-scoring path as the final response\. In this context, adaptive stopping rules can similarly decide how many reasoning paths should be generated\. The simplest example is a threshold rule that stops once the provider observes a candidate whose reward, assigned by a reward modelRR, exceeds some targetr∗r^\{\*\}:

τ⁡\(y1,…,yn\)\\displaystyle\\tau\(y\_\{1\},\\ldots,y\_\{n\}\)=𝟙\[maxi≤nR\(yi\)≥r∗\]\.\\displaystyle=\\mathbbm\{1\}\\left\[\\max\_\{i\\leq n\}R\(y\_\{i\}\)\\geq r^\{\*\}\\right\]\.More sophisticated adaptive best\-of\-NNstopping rules may depend not only on the highest observed reward, but also on the empirical reward distribution, posterior uncertainty, or the expected value of drawing an additional sample\([Wan et al\., 2025b](https://arxiv.org/html/2609.30352#bib.bib31);[Raman et al\., 2026](https://arxiv.org/html/2609.30352#bib.bib52)\)\. Nevertheless, as we illustrate empirically in Appendix[F\.4](https://arxiv.org/html/2609.30352#A6.SS4), an unfaithful provider can adapt the logic of Algorithm[1](https://arxiv.org/html/2609.30352#alg1)to reorder the sequence of answers, and hence the associated sequence of rewards, so that additional paths appear necessary before the stopping rule is triggered\.

Sequential search\-then\-verify procedures\.Search\-then\-verify methods do not draw independent samples, but maintain a partial solution that is repeatedly expanded with additional candidates, scored by a verifier, and pruned\. The procedure stops once the search finds a candidate accepted by the verifier or further search appears unpromising\([Yao et al\., 2023](https://arxiv.org/html/2609.30352#bib.bib53);[Koh et al\., 2025](https://arxiv.org/html/2609.30352#bib.bib33);[Dalal et al\., 2026](https://arxiv.org/html/2609.30352#bib.bib51)\)\. These search steps are history\-dependent, unlike the independent answer draws of self\-consistency and best\-of\-NN\. However, we conjecture that the logic underlying Algorithm[1](https://arxiv.org/html/2609.30352#alg1)could be extended to generate additional search steps and reorder so that the resulting compute appears necessary\. We leave empirical evaluation of this extension to future work\.

## Appendix BDeferred Proofs for Section[3](https://arxiv.org/html/2609.30352#S3)

This section establishes the theoretical guarantees underlying Algorithm[1](https://arxiv.org/html/2609.30352#alg1)\. Appendix[B\.1](https://arxiv.org/html/2609.30352#A2.SS1)first proves that every sequence returned by Algorithm[1](https://arxiv.org/html/2609.30352#alg1)is compatible with the provider’s stopping rule\. Appendix[B\.2](https://arxiv.org/html/2609.30352#A2.SS2)then derives two consequences of admissibility that characterize a sequence at faithful stopping\. Finally, Appendix[B\.3](https://arxiv.org/html/2609.30352#A2.SS3)derives a lower bound on the number of additional reasoning paths generated by Algorithm[1](https://arxiv.org/html/2609.30352#alg1)\.

### B\.1Proposition[2](https://arxiv.org/html/2609.30352#Thmtheorem2)

###### Proof of Proposition[2](https://arxiv.org/html/2609.30352#Thmtheorem2)\.

For eachT≥NT\\geq N, letP⁡\(T\)P\(T\)be the statement that whenever the current sequence𝐲\(T\)\\mathbf\{y\}^\{\(T\)\}maintained by Algorithm[1](https://arxiv.org/html/2609.30352#alg1)has lengthTT, no prefix of lengthj<Tj<Ttriggers the stopping ruleτ\\tau, and the current value ofLastCompatibleis compatible withτ\\tau\(Definition[1](https://arxiv.org/html/2609.30352#Thmtheorem1)\)\. We prove by induction thatP⁡\(T\)P\(T\)holds throughout the execution of Algorithm[1](https://arxiv.org/html/2609.30352#alg1)\.

Base case\.AtT=NT=N, the sequence𝐲\(N\)\\mathbf\{y\}^\{\(N\)\}is the faithfully stopped sequence𝐲\\mathbf\{y\}, which is compatible withτ\\tauby assumption\. Hence,NNis the first length at whichτ\\tautriggers, so no prefix of lengthj<Nj<Ntriggersτ\\tau\. Furthermore,LastCompatibleis initialized to𝐲=𝐲\(N\)\\mathbf\{y\}=\\mathbf\{y\}^\{\(N\)\}, which is compatible withτ\\tau\. Thus,P⁡\(N\)P\(N\)holds\.

Inductive step\.SupposeP⁡\(t\)P\(t\)holds for somet≥Nt\\geq N, and suppose Algorithm[1](https://arxiv.org/html/2609.30352#alg1)continues to a sequence of lengtht\+1t\+1\. Write𝐲\(t\)=\(y1,…,yt\)\\mathbf\{y\}^\{\(t\)\}=\(y\_\{1\},\\ldots,y\_\{t\}\)for the current sequence, and letynewy\_\{\\mathrm\{new\}\}denote the answer from a newly generated reasoning path\. The algorithm constructs a candidate sequence𝐲′′\\mathbf\{y\}^\{\\prime\\prime\}in one of two ways\. If𝐲\(t\)\\mathbf\{y\}^\{\(t\)\}does not triggerτ\\tau, it appends the new answer, giving𝐲′′=\(y1,…,yt,ynew\)\\mathbf\{y\}^\{\\prime\\prime\}=\(y\_\{1\},\\ldots,y\_\{t\},y\_\{\\mathrm\{new\}\}\)\. If𝐲\(t\)\\mathbf\{y\}^\{\(t\)\}triggersτ\\tau, the algorithm first setsLastCompatibleto𝐲\(t\)\\mathbf\{y\}^\{\(t\)\}—which is compatible withτ\\tau, since it triggersτ\\tauwhile, by the inductive hypothesis, no shorter prefix does—and then inserts the new answer before the final one, giving𝐲′′=\(y1,…,yt−1,ynew,yt\)\\mathbf\{y\}^\{\\prime\\prime\}=\(y\_\{1\},\\ldots,y\_\{t\-1\},y\_\{\\mathrm\{new\}\},y\_\{t\}\)\. In either case,LastCompatibleremains compatible withτ\\taubecause it is unchanged and compatible by the inductive hypothesis in the first and updated to the compatible sequence𝐲\(t\)\\mathbf\{y\}^\{\(t\)\}in the second\. We now consider the two possible outcomes of the iteration\.

1. 1\.*Termination\.*The algorithm returns the current sequence𝐲\(t\)\\mathbf\{y\}^\{\(t\)\}when the new answer cannot be deferred, either becauseynew=yty\_\{\\mathrm\{new\}\}=y\_\{t\}or because the reordered prefix\(y1,…,yt−1,ynew\)\(y\_\{1\},\\ldots,y\_\{t\-1\},y\_\{\\mathrm\{new\}\}\)triggersτ\\tau\. This can occur only when𝐲\(t\)\\mathbf\{y\}^\{\(t\)\}triggersτ\\tau\. By the inductive hypothesis, no shorter prefix does, so𝐲\(t\)\\mathbf\{y\}^\{\(t\)\}is compatible withτ\\tau\. Alternatively, if the audit flags𝐲′′\\mathbf\{y\}^\{\\prime\\prime\}, the algorithm returnsLastCompatible, which is compatible\. Thus, in either case, the returned sequence is compatible withτ\\tau\.
2. 2\.*Continuation\.*Suppose the algorithm accepts𝐲′′\\mathbf\{y\}^\{\\prime\\prime\}and continues with a sequence of lengtht\+1t\+1\. Every prefix of𝐲′′\\mathbf\{y\}^\{\\prime\\prime\}of length at mostt−1t\-1coincides with a prefix of𝐲\(t\)\\mathbf\{y\}^\{\(t\)\}and hence does not triggerτ\\tauby the inductive hypothesis\. The prefix of lengthttequals𝐲\(t\)\\mathbf\{y\}^\{\(t\)\}when the new answer is appended, in which case it does not trigger by construction\. When the new answer is reordered, the prefix of lengthttis\(y1,…,yt−1,ynew\)\(y\_\{1\},\\ldots,y\_\{t\-1\},y\_\{\\mathrm\{new\}\}\), which does not trigger by the check in Algorithm[1](https://arxiv.org/html/2609.30352#alg1)\. Therefore, no prefix of𝐲′′\\mathbf\{y\}^\{\\prime\\prime\}of lengthj<t\+1j<t\+1triggersτ\\tau\. SinceLastCompatiblealso remains compatible,P⁡\(t\+1\)P\(t\+1\)holds\.

Whenever the algorithm continues it preservesP⁡\(T\)P\(T\), and whenever it terminates, it returns a sequence that is already compatible\. Thus, the sequence returned by Algorithm[1](https://arxiv.org/html/2609.30352#alg1)is compatible withτ\\tau\. ∎

### B\.2Minimum Count Margin at Stopping

We next derive two properties of admissible stopping rules that are useful for the lower\-bound analysis\. First, an admissible stopping rule can only trigger when the most frequent answer count leads the runner\-up by at least two\. Second, the answer that triggers stopping must be the empirical mode\.

###### Proposition 6\(Minimum stopping margin\)\.

Letτ\\taube an admissible stopping rule satisfying Definition[3](https://arxiv.org/html/2609.30352#Thmtheorem3)\. Ifτ⁡\(s\(1\),s\(2\)\)=1\\tau\(s\_\{\(1\)\},s\_\{\(2\)\}\)=1, thens\(1\)−s\(2\)≥2s\_\{\(1\)\}\-s\_\{\(2\)\}\\geq 2\. Furthermore, if𝐲=\(y1,…,yN\)\\mathbf\{y\}=\(y\_\{1\},\\ldots,y\_\{N\}\)is compatible withτ\\tau, thenyN=a\(1\)Ny\_\{N\}=a^\{N\}\_\{\(1\)\}, wherea\(1\)N,…,a\(K\)Na^\{N\}\_\{\(1\)\},\\ldots,a^\{N\}\_\{\(K\)\}denote the answers ordered by their counts in𝐲\\mathbf\{y\}\.

###### Proof of Proposition[6](https://arxiv.org/html/2609.30352#Thmtheorem6)\.

We first show thatτ\\taucannot trigger when the margins\(1\)−s\(2\)s\_\{\(1\)\}\-s\_\{\(2\)\}is zero or one\. By nontriviality,τ⁡\(1,0\)=0\\tau\(1,0\)=0\. Fixed\-margin monotonicity then impliesτ⁡\(b\+1,b\)=0\\tau\(b\+1,b\)=0for anyb≥0b\\geq 0\. Thus,τ\\taucannot trigger whens\(1\)−s\(2\)=1s\_\{\(1\)\}\-s\_\{\(2\)\}=1\. Next, consider a tie\. Sinceτ⁡\(b\+1,b\)=0\\tau\(b\+1,b\)=0for anyb≥0b\\geq 0, monotonicity in the second most frequent count impliesτ⁡\(b\+1,b\+1\)=0\\tau\(b\+1,b\+1\)=0\. Thus, the rule cannot trigger when the two most frequent counts are equal either\. Sinces\(1\)≥s\(2\)s\_\{\(1\)\}\\geq s\_\{\(2\)\}by definition, any triggering configuration must satisfys\(1\)−s\(2\)≥2s\_\{\(1\)\}\-s\_\{\(2\)\}\\geq 2\.

It remains to show that the triggering answeryNy\_\{N\}must be the most frequent answera\(1\)Na^\{N\}\_\{\(1\)\}\. Suppose for contradiction thatyN≠a\(1\)Ny\_\{N\}\\neq a^\{N\}\_\{\(1\)\}\. RemovingyNy\_\{N\}leaves the counts\(1\)s\_\{\(1\)\}ofa\(1\)Na^\{N\}\_\{\(1\)\}unchanged, while the second most frequent count either \(i\) remains ats\(2\)s\_\{\(2\)\}or \(ii\) becomess\(2\)−1s\_\{\(2\)\}\-1\. In case \(i\), the preceding prefix of lengthN−1N\-1already has counts top\-two counts\(s\(1\),s\(2\)\)\(s\_\{\(1\)\},s\_\{\(2\)\}\)\. By count invariance, it already triggersτ\\tau, contradicting thatNNis the first stopping time\. In case \(ii\), the preceding prefix has counts\(s\(1\),s\(2\)−1\)\(s\_\{\(1\)\},s\_\{\(2\)\}\-1\)\. Ifτ⁡\(s\(1\),s\(2\)−1\)=0\\tau\(s\_\{\(1\)\},s\_\{\(2\)\}\-1\)=0, then monotonicity in the second most frequent count impliesτ⁡\(s\(1\),s\(2\)\)=0\\tau\(s\_\{\(1\)\},s\_\{\(2\)\}\)=0, contradicting the assumption thatτ⁡\(s\(1\),s\(2\)\)=1\\tau\(s\_\{\(1\)\},s\_\{\(2\)\}\)=1\. Otherwise,τ⁡\(s\(1\),s\(2\)−1\)=1\\tau\(s\_\{\(1\)\},s\_\{\(2\)\}\-1\)=1, which again contradicts thatNNis the first stopping time\. Hence,yN=a\(1\)Ny\_\{N\}=a^\{N\}\_\{\(1\)\}\. ∎

### B\.3Lower Bound on Additional Answers

In this section, we lower\-bound the expected number of additional answers𝔼⁡\[N′−N\]\\mathbb\{E\}\[N^\{\\prime\}\-N\]reported by an unfaithful provider running Algorithm[1](https://arxiv.org/html/2609.30352#alg1)beyond the faithful stopping time, under no audit \(α=0\\alpha=0\)\. In particular, we prove Proposition[4](https://arxiv.org/html/2609.30352#Thmtheorem4)\.

###### Proof of Proposition[4](https://arxiv.org/html/2609.30352#Thmtheorem4)\.

Fix a sequence𝐲=\(y1,…,yN\)\\mathbf\{y\}=\(y\_\{1\},\\ldots,y\_\{N\}\)compatible with an admissible stopping ruleτ\\tau, and writea\(1\)N,…,a\(K\)Na^\{N\}\_\{\(1\)\},\\ldots,a^\{N\}\_\{\(K\)\}for the answers ordered by their counts in𝐲\\mathbf\{y\}, with corresponding model probabilitiesp\(1\),…,p\(K\)p\_\{\(1\)\},\\ldots,p\_\{\(K\)\}\. Let𝐙=\(Z1,Z2,…\)\\mathbf\{Z\}=\(Z\_\{1\},Z\_\{2\},\\ldots\)denote the sequence of i\.i\.d\. answers that Algorithm[1](https://arxiv.org/html/2609.30352#alg1)draws from the model during continuation\. Conditional on𝐲\\mathbf\{y\},N′N^\{\\prime\}is a deterministic function of𝐙\\mathbf\{Z\}, and all expectations below are taken over𝐙\\mathbf\{Z\}conditional on𝐲\\mathbf\{y\}\.

By Proposition[6](https://arxiv.org/html/2609.30352#Thmtheorem6), the triggering answer isyN=a\(1\)Ny\_\{N\}=a^\{N\}\_\{\(1\)\}\. Removing this answer leaves the prefix\(y1,…,yN−1\)\(y\_\{1\},\\ldots,y\_\{N\-1\}\), whose two most frequent answers are stilla\(1\)Na^\{N\}\_\{\(1\)\}anda\(2\)Na^\{N\}\_\{\(2\)\}\. Define their count margin as:

d:=s\(1\)N−1−s\(2\)N−1=s\(1\)N−s\(2\)N−1≥1,d:=s^\{N\-1\}\_\{\(1\)\}\-s^\{N\-1\}\_\{\(2\)\}=s^\{N\}\_\{\(1\)\}\-s^\{N\}\_\{\(2\)\}\-1\\geq 1,where the inequality follows from the minimum stopping margin of Proposition[6](https://arxiv.org/html/2609.30352#Thmtheorem6)\. We begin by expressing the expected number of additional answers𝔼⁡\[N′−N\]\\mathbb\{E\}\[N^\{\\prime\}\-N\]using the tail\-sum formula,

𝔼⁡\[N′−N\]=∑k=1∞ℙ⁡\(N′−N≥k\),\\mathbb\{E\}\[N^\{\\prime\}\-N\]=\\sum\_\{k=1\}^\{\\infty\}\\mathbb\{P\}\(N^\{\\prime\}\-N\\geq k\),and lower\-bound each term by restricting attention to executions of Algorithm[1](https://arxiv.org/html/2609.30352#alg1)that provably do not terminate\. For eachk≥1k\\geq 1, letℰk\\mathcal\{E\}\_\{k\}be the event that\(Z1,…,Zk\)∈\{a\(1\)N,a\(2\)N\}k\(Z\_\{1\},\\ldots,Z\_\{k\}\)\\in\\\{a^\{N\}\_\{\(1\)\},a^\{N\}\_\{\(2\)\}\\\}^\{k\}and

0≤∑t=1j\(𝟙\{Zt=a\(2\)N\}−𝟙\{Zt=a\(1\)N\}\)≤dfor allj≤k\.0\\leq\\sum\_\{t=1\}^\{j\}\\big\(\\mathds\{1\}\\\{Z\_\{t\}=a^\{N\}\_\{\(2\)\}\\\}\-\\mathds\{1\}\\\{Z\_\{t\}=a^\{N\}\_\{\(1\)\}\\\}\\big\)\\leq d\\quad\\text\{for all \}j\\leq k\.\(5\)Condition \([5](https://arxiv.org/html/2609.30352#A2.E5)\) ensures that the margin ofa\(1\)Na^\{N\}\_\{\(1\)\}overa\(2\)Na^\{N\}\_\{\(2\)\}never exceeds its valueddfrom the non\-triggering prefix, while simultaneously keepinga\(1\)Na^\{N\}\_\{\(1\)\}as the most frequent answer\. Thus, onℰk\\mathcal\{E\}\_\{k\},a\(1\)Na^\{N\}\_\{\(1\)\}remains the most frequent answer throughout the firstkkcontinuation draws, and the difference between the counts of the most and second\-most frequent answers lies in\[0,d\]\[0,d\]for everyj≤kj\\leq k\.

By monotonicity in the second most frequent count and fixed\-margin monotonicity \(Definition[3](https://arxiv.org/html/2609.30352#Thmtheorem3)\), none of these intermediate prefixes triggersτ\\tau\. Algorithm[1](https://arxiv.org/html/2609.30352#alg1)therefore incorporatesZ1,…,ZkZ\_\{1\},\\ldots,Z\_\{k\}without terminating, implyingℰk⊆\{N′−N≥k\}\\mathcal\{E\}\_\{k\}\\subseteq\\\{N^\{\\prime\}\-N\\geq k\\\}\. Consequently,

𝔼⁡\[N′−N\]≥∑k=1∞ℙ⁡\(ℰk\)\.\\mathbb\{E\}\[N^\{\\prime\}\-N\]\\geq\\sum\_\{k=1\}^\{\\infty\}\\mathbb\{P\}\(\\mathcal\{E\}\_\{k\}\)\.
To bound the above sum, observe that each sequence\(z1,…,zk\)∈\{a\(1\)N,a\(2\)N\}k\(z\_\{1\},\\ldots,z\_\{k\}\)\\in\\\{a^\{N\}\_\{\(1\)\},a^\{N\}\_\{\(2\)\}\\\}^\{k\}can be viewed as a path on\{0,1,…,d\}\\\{0,1,\\ldots,d\\\}that starts at00, steps right ona\(2\)Na^\{N\}\_\{\(2\)\}, and steps left ona\(1\)Na^\{N\}\_\{\(1\)\}\. The eventℰk\\mathcal\{E\}\_\{k\}requires the path to stay within\{0,…,d\}\\\{0,\\ldots,d\\\}, which we call a*safe*path\. Grouping the probability\-weighted safe paths by their endpointssgives:

𝔼⁡\[N′−N\]≥∑s=0dg⁡\(s\)−1,\\mathbb\{E\}\[N^\{\\prime\}\-N\]\\geq\\sum\_\{s=0\}^\{d\}g\(s\)\-1,\(6\)whereg⁡\(s\)g\(s\)denotes the total probability mass of all safe paths ending atss, withg⁡\(0\)g\(0\)including the empty path; the−1\-1removes the contribution of this empty path\. A safe path ending atssmust arise either by extending a safe path ending ats−1s\-1by ana\(2\)Na^\{N\}\_\{\(2\)\}\-step or by extending a safe path ending ats\+1s\+1by ana\(1\)Na^\{N\}\_\{\(1\)\}\-step\. Hence,ggsolves the linear system:

\{g⁡\(0\)=1\+p\(1\)⋅g⁡\(1\),g⁡\(s\)=p\(2\)⋅g⁡\(s−1\)\+p\(1\)⋅g⁡\(s\+1\),s=1,…,d−1,g⁡\(d\)=p\(2\)⋅g⁡\(d−1\)\.\\begin\{cases\}g\(0\)=1\+p\_\{\(1\)\}\\cdot g\(1\),\\\\ g\(s\)=p\_\{\(2\)\}\\cdot g\(s\-1\)\+p\_\{\(1\)\}\\cdot g\(s\+1\),&s=1,\\ldots,d\-1,\\\\ g\(d\)=p\_\{\(2\)\}\\cdot g\(d\-1\)\.\\end\{cases\}\(7\)The coefficient matrix in Eq\. \([7](https://arxiv.org/html/2609.30352#A2.E7)\) is Toeplitz and, sincep\(1\)\+p\(2\)≤1p\_\{\(1\)\}\+p\_\{\(2\)\}\\leq 1, nonsingular\. To solve the system, define a sequence\(ξj\)j≥−1\(\\xi\_\{j\}\)\_\{j\\geq\-1\}byξ−1=0\\xi\_\{\-1\}=0,ξ0=ξ1=1\\xi\_\{0\}=\\xi\_\{1\}=1, and

ξj=ξj−1−p\(1\)​p\(2\)⋅ξj−2,j≥2\.\\xi\_\{j\}=\\xi\_\{j\-1\}\-p\_\{\(1\)\}p\_\{\(2\)\}\\cdot\\xi\_\{j\-2\},\\quad j\\geq 2\.\(8\)We claim thatg⁡\(s\)=p\(2\)s⋅ξd−s/ξd\+1g\(s\)=p\_\{\(2\)\}^\{\\,s\}\\cdot\\xi\_\{d\-s\}/\\xi\_\{d\+1\}solves Eq\. \([7](https://arxiv.org/html/2609.30352#A2.E7)\)\. Rearranging Eq\. \([8](https://arxiv.org/html/2609.30352#A2.E8)\) asξm=ξm\+1\+p\(1\)​p\(2\)​ξm−1\\xi\_\{m\}=\\xi\_\{m\+1\}\+p\_\{\(1\)\}p\_\{\(2\)\}\\,\\xi\_\{m\-1\}, we verify each of the three equations in Eq\. \([7](https://arxiv.org/html/2609.30352#A2.E7)\)\. First,

1\+p\(1\)​g​\(1\)=1\+p\(1\)​p\(2\)​ξd−1ξd\+1=ξd\+1\+p\(1\)​p\(2\)​ξd−1ξd\+1=ξdξd\+1=g⁡\(0\)\.1\+p\_\{\(1\)\}g\(1\)=1\+p\_\{\(1\)\}p\_\{\(2\)\}\\frac\{\\xi\_\{d\-1\}\}\{\\xi\_\{d\+1\}\}=\\frac\{\\xi\_\{d\+1\}\+p\_\{\(1\)\}p\_\{\(2\)\}\\,\\xi\_\{d\-1\}\}\{\\xi\_\{d\+1\}\}=\\frac\{\\xi\_\{d\}\}\{\\xi\_\{d\+1\}\}=g\(0\)\.Second, for1≤s≤d−11\\leq s\\leq d\-1,

p\(2\)​g​\(s−1\)\+p\(1\)​g​\(s\+1\)=p\(2\)s​ξd−s\+1\+p\(1\)​p\(2\)​ξd−s−1ξd\+1=p\(2\)s​ξd−sξd\+1=g⁡\(s\)\.p\_\{\(2\)\}g\(s\-1\)\+p\_\{\(1\)\}g\(s\+1\)=p\_\{\(2\)\}^\{\\,s\}\\frac\{\\xi\_\{d\-s\+1\}\+p\_\{\(1\)\}p\_\{\(2\)\}\\,\\xi\_\{d\-s\-1\}\}\{\\xi\_\{d\+1\}\}=p\_\{\(2\)\}^\{\\,s\}\\frac\{\\xi\_\{d\-s\}\}\{\\xi\_\{d\+1\}\}=g\(s\)\.Third, sinceξ0=ξ1\\xi\_\{0\}=\\xi\_\{1\},

p\(2\)​g​\(d−1\)=p\(2\)d​ξ1ξd\+1=p\(2\)d​ξ0ξd\+1=g⁡\(d\)\.p\_\{\(2\)\}g\(d\-1\)=p\_\{\(2\)\}^\{\\,d\}\\frac\{\\xi\_\{1\}\}\{\\xi\_\{d\+1\}\}=p\_\{\(2\)\}^\{\\,d\}\\frac\{\\xi\_\{0\}\}\{\\xi\_\{d\+1\}\}=g\(d\)\.Combining Eq\. \([6](https://arxiv.org/html/2609.30352#A2.E6)\) withg⁡\(0\)≥1g\(0\)\\geq 1then yields

𝔼⁡\[N′−N\]≥∑s=0dg⁡\(s\)−1≥∑s=1dp\(2\)s​ξd−sξd\+1\.\\mathbb\{E\}\[N^\{\\prime\}\-N\]\\geq\\sum\_\{s=0\}^\{d\}g\(s\)\-1\\geq\\sum\_\{s=1\}^\{d\}p\_\{\(2\)\}^\{\\,s\}\\frac\{\\xi\_\{d\-s\}\}\{\\xi\_\{d\+1\}\}\.\(9\)To obtain an explicit expression from Eq\. \([9](https://arxiv.org/html/2609.30352#A2.E9)\), we solve the recurrence in Eq\. \([8](https://arxiv.org/html/2609.30352#A2.E8)\) in closed form, treating the casep\(1\)\+p\(2\)=1p\_\{\(1\)\}\+p\_\{\(2\)\}=1separately because it admits a cleaner expression\.

Casep\(𝟏\)\+p\(𝟐\)<𝟏\\bm\{p\_\{\(1\)\}\+p\_\{\(2\)\}<1\}\.When more than two answers have positive probability, the characteristic polynomial associated with Eq\. \([8](https://arxiv.org/html/2609.30352#A2.E8)\) isx↦x2−x\+p\(1\)​p\(2\)x\\mapsto x^\{2\}\-x\+p\_\{\(1\)\}p\_\{\(2\)\}\. Its roots are real, sincep\(1\)\+p\(2\)<1p\_\{\(1\)\}\+p\_\{\(2\)\}<1impliesp\(1\)​p\(2\)<1/4p\_\{\(1\)\}p\_\{\(2\)\}<1/4, and are given by

1±1−4​p\(1\)​p\(2\)2=p\(1\)​p\(2\)​e∓arccosh⁡\(12​p\(1\)​p\(2\)\)\.\\frac\{1\\pm\\sqrt\{1\-4p\_\{\(1\)\}p\_\{\(2\)\}\}\}\{2\}=\\sqrt\{p\_\{\(1\)\}p\_\{\(2\)\}\}\\;e^\{\\mp\\operatorname\{arccosh\}\\left\(\\frac\{1\}\{2\\sqrt\{p\_\{\(1\)\}p\_\{\(2\)\}\}\}\\right\)\}\.The solution to Eq\. \([8](https://arxiv.org/html/2609.30352#A2.E8)\) is therefore

ξn=\(p\(1\)​p\(2\)\)n/2​sinh⁡\(\(n\+1\)​ϑ\)sinh⁡ϑ=\(p\(1\)​p\(2\)\)n/2​Un​\(12​p\(1\)​p\(2\)\),ϑ:=arccosh⁡\(12​p\(1\)​p\(2\)\),\\xi\_\{n\}=\(p\_\{\(1\)\}p\_\{\(2\)\}\)^\{n/2\}\\,\\frac\{\\sinh\\\!\\big\(\(n\+1\)\\vartheta\\big\)\}\{\\sinh\\vartheta\}=\(p\_\{\(1\)\}p\_\{\(2\)\}\)^\{n/2\}\\,U\_\{n\}\\\!\\left\(\\frac\{1\}\{2\\sqrt\{p\_\{\(1\)\}p\_\{\(2\)\}\}\}\\right\),\\quad\\vartheta:=\\operatorname\{arccosh\}\\\!\\left\(\\frac\{1\}\{2\\sqrt\{p\_\{\(1\)\}p\_\{\(2\)\}\}\}\\right\),whereUnU\_\{n\}is the degree\-nnChebyshev polynomial of the second kind\. Substituting into Eq\. \([9](https://arxiv.org/html/2609.30352#A2.E9)\),

𝔼⁡\[N′−N\]≥1\(p\(1\)​p\(2\)\)\(d\+1\)/2​Ud\+1​\(12​p\(1\)​p\(2\)\)​∑s=1dp\(2\)s​\(p\(1\)​p\(2\)\)\(d−s\)/2​Ud−s​\(12​p\(1\)​p\(2\)\)\.\\mathbb\{E\}\[N^\{\\prime\}\-N\]\\geq\\frac\{1\}\{\(p\_\{\(1\)\}p\_\{\(2\)\}\)^\{\(d\+1\)/2\}\\,U\_\{d\+1\}\\\!\\left\(\\frac\{1\}\{2\\sqrt\{p\_\{\(1\)\}p\_\{\(2\)\}\}\}\\right\)\}\\sum\_\{s=1\}^\{d\}p\_\{\(2\)\}^\{\\,s\}\\,\(p\_\{\(1\)\}p\_\{\(2\)\}\)^\{\(d\-s\)/2\}\\,U\_\{d\-s\}\\\!\\left\(\\frac\{1\}\{2\\sqrt\{p\_\{\(1\)\}p\_\{\(2\)\}\}\}\\right\)\.\(10\)
Casep\(𝟏\)\+p\(𝟐\)=𝟏\\bm\{p\_\{\(1\)\}\+p\_\{\(2\)\}=1\}\.When only two answers have positive probability, the characteristic polynomial factors asx↦x2−\(p\(1\)\+p\(2\)\)​x\+p\(1\)​p\(2\)x\\mapsto x^\{2\}\-\(p\_\{\(1\)\}\+p\_\{\(2\)\}\)x\+p\_\{\(1\)\}p\_\{\(2\)\}, with distinct rootsp\(1\)p\_\{\(1\)\}andp\(2\)p\_\{\(2\)\}under the unique\-mode assumptionp\(1\)≠p\(2\)p\_\{\(1\)\}\\neq p\_\{\(2\)\}\. Henceξn=\(p\(1\)n\+1−p\(2\)n\+1\)/\(p\(1\)−p\(2\)\)\\xi\_\{n\}=\(p\_\{\(1\)\}^\{\\,n\+1\}\-p\_\{\(2\)\}^\{\\,n\+1\}\)/\(p\_\{\(1\)\}\-p\_\{\(2\)\}\), and Eq\. \([9](https://arxiv.org/html/2609.30352#A2.E9)\) becomes:

𝔼⁡\[N′−N\]≥∑s=1dp\(2\)s​p\(1\)d−s\+1−p\(2\)d−s\+1p\(1\)d\+2−p\(2\)d\+2=p\(1\)​p\(2\)​\(p\(1\)d−p\(2\)d\)−d⁡\(p\(1\)−p\(2\)\)​p\(2\)d\+1\(p\(1\)−p\(2\)\)​\(p\(1\)d\+2−p\(2\)d\+2\)\.\\displaystyle\\mathbb\{E\}\[N^\{\\prime\}\-N\]\\geq\\sum\_\{s=1\}^\{d\}p\_\{\(2\)\}^\{\\,s\}\\,\\frac\{p\_\{\(1\)\}^\{\\,d\-s\+1\}\-p\_\{\(2\)\}^\{\\,d\-s\+1\}\}\{p\_\{\(1\)\}^\{\\,d\+2\}\-p\_\{\(2\)\}^\{\\,d\+2\}\}=\\frac\{p\_\{\(1\)\}p\_\{\(2\)\}\\,\(p\_\{\(1\)\}^\{\\,d\}\-p\_\{\(2\)\}^\{\\,d\}\)\-d\\,\(p\_\{\(1\)\}\-p\_\{\(2\)\}\)\\,p\_\{\(2\)\}^\{\\,d\+1\}\}\{\(p\_\{\(1\)\}\-p\_\{\(2\)\}\)\\,\(p\_\{\(1\)\}^\{\\,d\+2\}\-p\_\{\(2\)\}^\{\\,d\+2\}\)\}\.\(11\)This proves Proposition[4](https://arxiv.org/html/2609.30352#Thmtheorem4)\. ∎

Tighter generalized bounds\.The bounds in Eqs\. \([10](https://arxiv.org/html/2609.30352#A2.E10)\) and \([11](https://arxiv.org/html/2609.30352#A2.E11)\) count only paths whose answers lie in\{a\(1\)N,a\(2\)N\}\\\{a^\{N\}\_\{\(1\)\},a^\{N\}\_\{\(2\)\}\\\}, discarding the probability mass of every execution of Algorithm[1](https://arxiv.org/html/2609.30352#alg1)that samples an answer in\{a\(3\)N,…,a\(K\)N\}\\\{a^\{N\}\_\{\(3\)\},\\ldots,a^\{N\}\_\{\(K\)\}\\\}\. Accounting for these paths yields a tighter lower bound\. For eachi\>1i\>1, define the initial margin between the leader and answera\(i\)Na^\{N\}\_\{\(i\)\}in the non\-triggering prefix by

di:=s\(1\)N−1−s\(i\)N−1=∑t=1N−1𝟙\{yt=a\(1\)N\}−∑t=1N−1𝟙\{yt=a\(i\)N\}\.d\_\{i\}:=s^\{N\-1\}\_\{\(1\)\}\-s^\{N\-1\}\_\{\(i\)\}=\\sum\_\{t=1\}^\{N\-1\}\\mathds\{1\}\\\{y\_\{t\}=a^\{N\}\_\{\(1\)\}\\\}\-\\sum\_\{t=1\}^\{N\-1\}\\mathds\{1\}\\\{y\_\{t\}=a^\{N\}\_\{\(i\)\}\\\}\.Let𝒮=∏i=2K\{0,1,…,di\}\\mathcal\{S\}=\\prod\_\{i=2\}^\{K\}\\\{0,1,\\ldots,d\_\{i\}\\\}denote the lattice of allowable relative displacements\. We say that an execution of Algorithm[1](https://arxiv.org/html/2609.30352#alg1)is*safe*if, after each draw, the margin ofa\(1\)Na^\{N\}\_\{\(1\)\}over every other answera\(i\)Na^\{N\}\_\{\(i\)\}stays in\{0,…,di\}\\\{0,\\ldots,d\_\{i\}\\\}\. As before, every such prefix is non\-triggering\. Grouping safe paths by their displacement vector𝐬=\(s2,…,sK\)\\mathbf\{s\}=\(s\_\{2\},\\ldots,s\_\{K\}\)gives

𝔼⁡\[N′−N\]≥∑𝐬∈𝒮g⁡\(𝐬\)−1,\\mathbb\{E\}\[N^\{\\prime\}\-N\]\\geq\\sum\_\{\\mathbf\{s\}\\in\\mathcal\{S\}\}g\(\\mathbf\{s\}\)\-1,whereg⁡\(𝐬\)g\(\\mathbf\{s\}\)is the total probability mass of safe paths ending at𝐬\\mathbf\{s\}, withg⁡\(𝟎\)g\(\\mathbf\{0\}\)including the empty path\. These masses satisfy:

g\(𝐬\)=𝟙\{𝐬=𝟎\}\+p\(1\)g\(𝐬\+𝟏\)1\{𝐬\+𝟏∈𝒮\}\+∑i=2Kp\(i\)g\(𝐬−𝐞i\)1\{𝐬−𝐞i∈𝒮\},g\(\\mathbf\{s\}\)=\\mathds\{1\}\\\{\\mathbf\{s\}=\\mathbf\{0\}\\\}\+p\_\{\(1\)\}\\,g\(\\mathbf\{s\}\+\\mathbf\{1\}\)\\,\\mathds\{1\}\\\{\\mathbf\{s\}\+\\mathbf\{1\}\\in\\mathcal\{S\}\\\}\+\\sum\_\{i=2\}^\{K\}p\_\{\(i\)\}\\,g\(\\mathbf\{s\}\-\\mathbf\{e\}\_\{i\}\)\\,\\mathds\{1\}\\\{\\mathbf\{s\}\-\\mathbf\{e\}\_\{i\}\\in\\mathcal\{S\}\\\},\(12\)where𝟎=\(0,…,0\)\\mathbf\{0\}=\(0,\\ldots,0\),𝟏=\(1,…,1\)\\mathbf\{1\}=\(1,\\ldots,1\), and𝐞i\\mathbf\{e\}\_\{i\}the standard basis vector inℝK−1\\mathbb\{R\}^\{K\-1\}associated with answera\(i\)Na^\{N\}\_\{\(i\)\}\. Unlike the top\-two bound, Eq\. \([12](https://arxiv.org/html/2609.30352#A2.E12)\) has no closed form in general, but it can be evaluated by solving the finite linear system over𝒮\\mathcal\{S\}\.

## Appendix CAuditing Reported Sequences via Likelihoods

### C\.1Proposition[5](https://arxiv.org/html/2609.30352#Thmtheorem5)

We now show that Algorithm[2](https://arxiv.org/html/2609.30352#alg2)correctly counts the distinct sampling trajectories that could have produced an observed sequence𝐲′\\mathbf\{y\}^\{\\prime\}—that is, the distinct sequences𝐲\\mathbf\{y\}from which Algorithm[1](https://arxiv.org/html/2609.30352#alg1)could have generated𝐲′\\mathbf\{y\}^\{\\prime\}—and therefore returns the likelihoodℙH1​\(𝐲′\)\\mathbb\{P\}\_\{H\_\{1\}\}\(\\mathbf\{y\}^\{\\prime\}\)\.

###### Proof of Proposition[5](https://arxiv.org/html/2609.30352#Thmtheorem5)\.

Let𝐲′=\(y1′,…,yN′′\)\\mathbf\{y\}^\{\\prime\}=\(y^\{\\prime\}\_\{1\},\\ldots,y^\{\\prime\}\_\{N^\{\\prime\}\}\)be a sequence compatible withτ\\tau\. For each1≤j≤N′1\\leq j\\leq N^\{\\prime\}, let𝒯j​\(𝐲′\)\\mathcal\{T\}\_\{j\}\(\\mathbf\{y\}^\{\\prime\}\)denote the set of distinct sequences𝐲\\mathbf\{y\}such that, during the execution of Algorithm[1](https://arxiv.org/html/2609.30352#alg1)on𝐲\\mathbf\{y\}, the variableLastCompatiblecan take the value\(y1′,…,yj′\)\(y^\{\\prime\}\_\{1\},\\dots,y^\{\\prime\}\_\{j\}\)\. We prove by induction that Algorithm[2](https://arxiv.org/html/2609.30352#alg2)computesCounts​\[j\]=\|𝒯j​\(𝐲′\)\|\\texttt\{Counts\}\[j\]=\|\\mathcal\{T\}\_\{j\}\(\\mathbf\{y\}^\{\\prime\}\)\|for every1≤j≤N′1\\leq j\\leq N^\{\\prime\}\. It then follows thatℙH1\(𝐲′\)=Counts\[N′\]⋅pyN′′∏i=1N′pyi′\\mathbb\{P\}\_\{H\_\{1\}\}\(\\mathbf\{y\}^\{\\prime\}\)=\\texttt\{Counts\}\[N^\{\\prime\}\]\\cdot p\_\{y^\{\\prime\}\_\{N^\{\\prime\}\}\}\\prod\_\{i=1\}^\{N^\{\\prime\}\}p\_\{y^\{\\prime\}\_\{i\}\}\.

Base case\.Forj=1j=1, the reported prefix is\(y1′\)\(y^\{\\prime\}\_\{1\}\)\. There is a single sequence𝐲=\(y1′\)\\mathbf\{y\}=\(y^\{\\prime\}\_\{1\}\)for which the execution of Algorithm[1](https://arxiv.org/html/2609.30352#alg1)generatesLastCompatible=\(y1′\)\\texttt\{LastCompatible\}=\(y^\{\\prime\}\_\{1\}\), soCounts​\[1\]=1\\texttt\{Counts\}\[1\]=1\.

Inductive step\.Fix2≤j≤N′2\\leq j\\leq N^\{\\prime\}and suppose the claim holds for all shorter prefixes\. Consider any𝐲\\mathbf\{y\}that produces\(y1′,…,yj′\)\(y^\{\\prime\}\_\{1\},\\ldots,y^\{\\prime\}\_\{j\}\)asLastCompatibleduring the execution of Algorithm[1](https://arxiv.org/html/2609.30352#alg1)\. The final answeryj′y^\{\\prime\}\_\{j\}must have reached positionjjafter some unique numberL∈\{0,…,j−2\}L\\in\\\{0,\\ldots,j\-2\\\}of consecutive swaps\. IfL=0L=0, thenyj′y^\{\\prime\}\_\{j\}was generated directly after the reported prefix of lengthj−1j\-1, without being reordered\. IfL\>0L\>0, thenyj′y^\{\\prime\}\_\{j\}was generated after the shorter prefix\(y1′,…,yj−L−1′\)\(y^\{\\prime\}\_\{1\},\\ldots,y^\{\\prime\}\_\{j\-L\-1\}\)and subsequently permuted pastLLgenerated answers\. Such a trajectory is feasible only if, for everyk=1,…,Lk=1,\\ldots,L, the stopping ruleτ\\tautriggers on the answer counts of\(y1′,…,yj−k−1′,yj′\)\(y^\{\\prime\}\_\{1\},\\ldots,y^\{\\prime\}\_\{j\-k\-1\},y^\{\\prime\}\_\{j\}\), which is precisely the condition checked byPossibleMultipleSwap​\(j,L\)\\texttt\{PossibleMultipleSwap\}\(j,L\)in Algorithm[2](https://arxiv.org/html/2609.30352#alg2)\.

For a fixedLL, the portion of the trajectory preceding the generation ofyj′y^\{\\prime\}\_\{j\}can be any trajectory producing the prefix\(y1′,…,yj−L−1′\)\(y^\{\\prime\}\_\{1\},\\ldots,y^\{\\prime\}\_\{j\-L\-1\}\)\. By the inductive hypothesis, there areCounts​\[j−L−1\]\\texttt\{Counts\}\[j\-L\-1\]such trajectories\. However, each complete trajectory has a unique value ofLL, so the sets of trajectories corresponding to the different values ofLLare disjoint\. Therefore,Counts​\[j\]=∑L=0j−2𝟙​\[PossibleMultipleSwap​\(j,L\)\]⋅Counts​\[j−L−1\]\\texttt\{Counts\}\[j\]=\\sum\_\{L=0\}^\{j\-2\}\\mathbbm\{1\}\[\\texttt\{PossibleMultipleSwap\}\(j,L\)\]\\cdot\\texttt\{Counts\}\[j\-L\-1\], which is exactly the update performed in line[16](https://arxiv.org/html/2609.30352#alg2.l16)of Algorithm[2](https://arxiv.org/html/2609.30352#alg2)\. Hence,Counts​\[j\]=\|𝒯j​\(𝐲′\)\|\\texttt\{Counts\}\[j\]=\|\\mathcal\{T\}\_\{j\}\(\\mathbf\{y\}^\{\\prime\}\)\|\.

It remains to convert this trajectory count into a likelihood\. Any trajectory that produces the observed sequence𝐲′\\mathbf\{y\}^\{\\prime\}contains theN′N^\{\\prime\}reported model draws, together with one final unreported draw equal toyN′′y^\{\\prime\}\_\{N^\{\\prime\}\}that causes Algorithm[1](https://arxiv.org/html/2609.30352#alg1)to terminate\. Each such trajectory has probabilitypyN′′​∏i=1N′pyi′p\_\{y^\{\\prime\}\_\{N^\{\\prime\}\}\}\\prod\_\{i=1\}^\{N^\{\\prime\}\}p\_\{y^\{\\prime\}\_\{i\}\}underH1H\_\{1\}\. Summing over theCounts​\[N′\]=\|𝒯N′​\(𝐲′\)\|\\texttt\{Counts\}\[N^\{\\prime\}\]=\|\\mathcal\{T\}\_\{N^\{\\prime\}\}\(\\mathbf\{y\}^\{\\prime\}\)\|trajectories that produce𝐲′\\mathbf\{y\}^\{\\prime\}givesℙH1\(𝐲′\)=Counts\[N′\]⋅pyN′′∏i=1N′pyi′\\mathbb\{P\}\_\{H\_\{1\}\}\(\\mathbf\{y\}^\{\\prime\}\)=\\texttt\{Counts\}\[N^\{\\prime\}\]\\cdot p\_\{y^\{\\prime\}\_\{N^\{\\prime\}\}\}\\prod\_\{i=1\}^\{N^\{\\prime\}\}p\_\{y^\{\\prime\}\_\{i\}\}, as required\. ∎

### C\.2Auditing Multiple Sequences

Section[4](https://arxiv.org/html/2609.30352#S4)considers an auditor who observes a single reported sequence𝐲′\\mathbf\{y\}^\{\\prime\}\. In practice, however, a provider serves a stream of queries, and an auditor may observe sequences reported in response to many of them—either because a single user submits multiple queries, or because the auditor pools transcripts across multiple users\. The likelihood\-ratio audit of Eq\. \([4](https://arxiv.org/html/2609.30352#S4.E4)\) extends naturally to this setting\.

Suppose the auditor observesMMreported sequences𝐲1,𝐲2,…,𝐲M\\mathbf\{y\}\_\{1\},\\mathbf\{y\}\_\{2\},\\ldots,\\mathbf\{y\}\_\{M\}, corresponding to queriesx1,x2,…,xMx\_\{1\},x\_\{2\},\\ldots,x\_\{M\}\. For each queryjj, define the likelihood ratio:

ej:=ℙH1​\(𝐲j\)ℙH0​\(𝐲j\)\.\\displaystyle e\_\{j\}:=\\frac\{\\mathbb\{P\}\_\{H\_\{1\}\}\(\\mathbf\{y\}\_\{j\}\)\}\{\\mathbb\{P\}\_\{H\_\{0\}\}\(\\mathbf\{y\}\_\{j\}\)\}\.
Assuming that the model’s generations are independent across queries conditional on the queries, the joint likelihood ratio of theMMreported sequences is:

EM\\displaystyle E\_\{M\}:=∏j=1Mej=∏j=1MℙH1​\(𝐲j∣xj\)∏j=1MℙH0​\(𝐲j∣xj\)\.\\displaystyle:=\\prod\_\{j=1\}^\{M\}e\_\{j\}=\\frac\{\\prod\_\{j=1\}^\{M\}\{\\mathbb\{P\}\}\_\{H\_\{1\}\}\(\\mathbf\{y\}\_\{j\}\\mid x\_\{j\}\)\}\{\\prod\_\{j=1\}^\{M\}\{\\mathbb\{P\}\}\_\{H\_\{0\}\}\(\\mathbf\{y\}\_\{j\}\\mid x\_\{j\}\)\}\.
Thus, evidence from multiple reported sequences can be accumulated by multiplying their individual likelihood ratios\. Importantly, this product retains the e\-value interpretation used in Section[4](https://arxiv.org/html/2609.30352#S4)\. UnderH0H\_\{0\}, eacheje\_\{j\}has conditional expectation one given all previously observed queries and reported sequences\. Hence, the process\(EM\)M≥0\(E\_\{M\}\)\_\{M\\geq 0\}is a nonnegative martingale underH0H\_\{0\}withE0=1E\_\{0\}=1\. An auditor can reject the null hypothesis wheneverEM≥1αE\_\{M\}\\geq\\frac\{1\}\{\\alpha\}\. By Ville’s inequality, the probability that a faithful provider is ever falsely flagged is at mostα\\alpha\([Ramdas and Wang, 2025](https://arxiv.org/html/2609.30352#bib.bib8)\):

ℙH0​\(supM≥1EM≥1α\)\\displaystyle\\mathbb\{P\}\_\{H\_\{0\}\}\\left\(\\sup\_\{M\\geq 1\}E\_\{M\}\\geq\\frac\{1\}\{\\alpha\}\\right\)≤α\.\\displaystyle\\leq\\alpha\.Thus, the audit remains valid as additional queries are observed, while evidence against a provider that repeatedly uses Algorithm[1](https://arxiv.org/html/2609.30352#alg1)can accumulate across queries\. This imposes a stronger constraint a strategic unfaithful provider, who must now ensure that

Ej−1⋅ℙH1​\(𝐲j\)ℙH0​\(𝐲j\)<1α\\displaystyle E\_\{j\-1\}\\cdot\\frac\{\\mathbb\{P\}\_\{H\_\{1\}\}\(\\mathbf\{y\}\_\{j\}\)\}\{\\mathbb\{P\}\_\{H\_\{0\}\}\(\\mathbf\{y\}\_\{j\}\)\}<\\frac\{1\}\{\\alpha\}for every queryjjin order to avoid detection\. To this end, the provider can modify Algorithm[1](https://arxiv.org/html/2609.30352#alg1)by replacing the single\-sequence audit condition with:

AuditFlag\(𝐲,α,𝐲1,…𝐲j−1\):=𝟙\[Ej−1⋅Counts\[N′\]⋅pyN′≥1α\]\\texttt\{AuditFlag\}\(\\mathbf\{y\},\\alpha,\\mathbf\{y\}\_\{1\},\\dots\\mathbf\{y\}\_\{j\-1\}\):=\\mathbbm\{1\}\\left\[E\_\{j\-1\}\\cdot\\,\\texttt\{Counts\}\[N^\{\\prime\}\]\\cdot\\,p\_\{y\_\{N^\{\\prime\}\}\}\\geq\\frac\{1\}\{\\alpha\}\\right\]where𝐲1,…,𝐲j−1\\mathbf\{y\}\_\{1\},\\dots,\\mathbf\{y\}\_\{j\-1\}are thej−1j\-1previously reported sequences andEj−1=∏ℓ=1j−1eℓE\_\{j\-1\}=\\prod\_\{\\ell=1\}^\{j\-1\}e\_\{\\ell\}is their cumulative likelihood ratio\.

## Appendix DComputing Likelihoods in Linear Time

To avoid detection by an auditor, a strategic provider must repeatedly evaluate the likelihood of its reported sequence to ensure that it remains below the audit’s rejection threshold \(Algorithm[1](https://arxiv.org/html/2609.30352#alg1)\)\. However, a direct implementation of Algorithm[2](https://arxiv.org/html/2609.30352#alg2)is expensive\. EachCounts​\[j\]\\texttt\{Counts\}\[j\]is computed using nested loops over possible swap lengths, and each iteration re\-evaluates the stopping ruleτ\\tauon a prefix of lengthO⁡\(N′\)O\(N^\{\\prime\}\), resulting inΘ⁡\(N′3\)\\Theta\(\{N^\{\\prime\}\}^\{3\}\)running time overall\.

Algorithm[3](https://arxiv.org/html/2609.30352#alg3)computes the same likelihood inO⁡\(N′​K\)O\(N^\{\\prime\}K\)time, linear in the reported sequence lengthN′N^\{\\prime\}for fixedKK\. The speedup follows from the observation that, for a fixed endpointjj, if the answeryj′y^\{\\prime\}\_\{j\}could have been generated earlier and pushed forward throughLLconsecutive swaps, then it could also have been pushed through any smaller number of swaps\. Thus, the feasible swap lengths form a single contiguous interval\. This allows us to express the sum definingCounts​\[j\]\\texttt\{Counts\}\[j\]as a contiguous range sum and to precompute the endpoint of this interval in a single pass\.

Collapsing the sum over swap lengths\.Algorithm[2](https://arxiv.org/html/2609.30352#alg2)computes:

Counts​\[j\]:=∑L=0j−2𝟙​\[PossibleMultipleSwap​\(j,L\)\]⋅Counts​\[j−L−1\],\\displaystyle\\texttt\{Counts\}\[j\]:=\\sum\_\{L=0\}^\{j\-2\}\\mathbbm\{1\}\[\\texttt\{PossibleMultipleSwap\}\(j,L\)\]\\cdot\\texttt\{Counts\}\[j\-L\-1\],where evaluatingPossibleMultipleSwap​\(j,L\)\\texttt\{PossibleMultipleSwap\}\(j,L\)requires checking each of theLLintermediate swaps\. More precisely,

PossibleMultipleSwap\(j,L\)=⋀k=1L\[τ\(s\(1\),s\(2\)∣y1′,…,yj−k−1′,yj′\)=1\],\\displaystyle\\texttt\{PossibleMultipleSwap\}\(j,L\)=\\bigwedge\_\{k=1\}^\{L\}\\left\[\\,\\tau\\bigl\(s\_\{\(1\)\},s\_\{\(2\)\}\\mid y^\{\\prime\}\_\{1\},\\ldots,y^\{\\prime\}\_\{j\-k\-1\},y^\{\\prime\}\_\{j\}\\bigr\)=1\\,\\right\],whereτ\(s\(1\),s\(2\)∣⋅\)\\tau\(s\_\{\(1\)\},s\_\{\(2\)\}\\mid\\cdot\)denotesτ\\tauapplied to the two largest answer counts of the sequence supplied after the conditioning bar\. Once a conjunct fails for someLL, it fails for all largerLL\. Therefore, for eachjj, the feasible swap lengthsLLform a contiguous window\{0,1,…,Lmax​\(j\)\}\\\{0,1,\\ldots,L\_\{\\max\}\(j\)\\\}, and:

Counts​\[j\]=∑L=0Lmax​\(j\)Counts​\[j−L−1\]=∑i=j−1−Lmax​\(j\)j−1Counts​\[i\]\.\\displaystyle\\texttt\{Counts\}\[j\]=\\sum\_\{L=0\}^\{L\_\{\\max\}\(j\)\}\\texttt\{Counts\}\[j\-L\-1\]=\\sum\_\{i=j\-1\-L\_\{\\max\}\(j\)\}^\{j\-1\}\\texttt\{Counts\}\[i\]\.We evaluate this range sum in constant time by maintaining the prefix sumsS⁡\[j\]=∑i=1jCounts​\[i\]S\[j\]=\\sum\_\{i=1\}^\{j\}\\texttt\{Counts\}\[i\], withS⁡\[j\]=0S\[j\]=0forj≤0j\\leq 0\. This reduces each entry to a single subtraction onceLmax​\(j\)L\_\{\\max\}\(j\)is known:

Counts​\[j\]=S⁡\[j−1\]−S⁡\[j−2−Lmax​\(j\)\]\.\\displaystyle\\texttt\{Counts\}\[j\]=S\[j\-1\]\-S\\bigl\[j\-2\-L\_\{\\max\}\(j\)\\bigr\]\.Thus, computingCounts​\[j\]\\texttt\{Counts\}\[j\]requires onlyO⁡\(1\)O\(1\)time once the feasible swap interval has been identified\.

ComputingL𝐦𝐚𝐱​\(j\)\\bm\{L\_\{\\max\}\(j\)\}efficiently\.It remains to computeLmax​\(j\)L\_\{\\max\}\(j\)without explicitly checking every intermediate swap,*i\.e\.*, looping overkk\. Consider a prefix\(y1′,…,ym′\)\(y^\{\\prime\}\_\{1\},\\ldots,y^\{\\prime\}\_\{m\}\)that does not triggerτ\\tau\. A swap involvingyj′y^\{\\prime\}\_\{j\}is feasible at this prefix precisely when appendingyj′y^\{\\prime\}\_\{j\}would triggerτ\\tau\. For each prefix lengthmm, define:

σ⁡\(m\)\\displaystyle\\sigma\(m\)=\{vif appending answervto the length\-mprefix triggersτ,Noneotherwise\.\\displaystyle=\\begin\{cases\}v&\\text\{if appending answer $v$ to the length\-$m$ prefix triggers $\\tau$,\}\\\\ \\texttt\{None\}&\\text\{otherwise\.\}\\end\{cases\}By Proposition[6](https://arxiv.org/html/2609.30352#Thmtheorem6), whenever a triggering answer exists, it must be ithe unique empirical leader of the prefix\. Hence, thekk\-th swap condition for endpointjjsatisfiesτ\(s\(1\),s\(2\)∣y1′,…,yj−k−1′,yj′\)=1⇔σ\(j−k−1\)=yj′\\tau\(s\_\{\(1\)\},s\_\{\(2\)\}\\mid y^\{\\prime\}\_\{1\},\\ldots,y^\{\\prime\}\_\{j\-k\-1\},y^\{\\prime\}\_\{j\}\)=1\\iff\\sigma\(j\-k\-1\)=y^\{\\prime\}\_\{j\}\. Therefore,Lmax​\(j\)L\_\{\\max\}\(j\)is exactly the number of consecutive prefixesj−2,j−3,…j\-2,j\-3,\\ldotsfor which appendingyj′y^\{\\prime\}\_\{j\}would trigger stopping\.

To compute this quantity efficiently, letruns​\[m\]\\texttt\{runs\}\[m\]denote the length of the maximal consecutive run ending atmmfor whichσ\\sigmatakes the same non\-Nonevalue\. Then,

Lmax​\(j\)\\displaystyle L\_\{\\max\}\(j\)=\{runs​\[j−2\]ifσ⁡\(j−2\)=yj′,0otherwise\.\\displaystyle=\\begin\{cases\}\\texttt\{runs\}\[j\-2\]&\\text\{if $\\sigma\(j\-2\)=y^\{\\prime\}\_\{j\}$,\}\\\\ 0&\\text\{otherwise\.\}\\end\{cases\}Onceσ⁡\(m\)\\sigma\(m\)andruns​\[m\]\\texttt\{runs\}\[m\]have been precomputed,Lmax​\(j\)L\_\{\\max\}\(j\)can then be obtained inO⁡\(1\)O\(1\)time\.

Overall running time\.All required quantities can be computed in a single pass over the reported sequence\. For each prefix lengthmm, Algorithm[3](https://arxiv.org/html/2609.30352#alg3)updates the running answer counts, extracts the two most frequent answers and their counts, tests whether appending the current empirical leader to the current prefix would triggerτ\\tau, and updates the corresponding run length\.

Maintaining the answer counts takes constant time per newly observed answer, while identifying the two largest counts and the empirical leader requiresO⁡\(K\)O\(K\)time per prefix\. The preprocessing stage therefore requiresO⁡\(N′​K\)O\(N^\{\\prime\}K\)time\. Once this preprocessing is complete, computingLmax​\(j\)L\_\{\\max\}\(j\),Counts​\[j\]\\texttt\{Counts\}\[j\], and the corresponding prefix sum each requiresO⁡\(1\)O\(1\)time per position\. Algorithm[3](https://arxiv.org/html/2609.30352#alg3)therefore computes the likelihood inO⁡\(N′​K\)O\(N^\{\\prime\}K\)time overall\.

Algorithm 3It computes the likelihood of an observed sequence underH1H\_\{1\}in linear time1:Input:Reported compatible sequence

𝐲′=\(y1′,…,yN′′\)\\mathbf\{y\}^\{\\prime\}=\(y^\{\\prime\}\_\{1\},\\dots,y^\{\\prime\}\_\{N^\{\\prime\}\}\), stopping rule

τ\\tau, answer probabilities

p1,…,pKp\_\{1\},\\dots,p\_\{K\}\.

2:Output:Likelihood

𝒫H1​\(𝐲′\)\\mathcal\{P\}\_\{H\_\{1\}\}\(\\mathbf\{y\}^\{\\prime\}\)under Algorithm[1](https://arxiv.org/html/2609.30352#alg1)

3:

Counts←\(1,0,…,0\)⏟N′​elements\\texttt\{Counts\}\\leftarrow\\underbrace\{\(1,0,\\dots,0\)\}\_\{N^\{\\prime\}\\text\{ elements\}\}
4:

S←\(1,0,…,0\)⏟N′​elementsS\\leftarrow\\underbrace\{\(1,0,\\dots,0\)\}\_\{N^\{\\prime\}\\text\{ elements\}\}⊳\\trianglerightPrefix sumsS​\[j\]=∑t≤jCounts​\[t\]S\[j\]=\\sum\_\{t\\leq j\}\\texttt\{Counts\}\[t\]

5:

σ←\(None,…,None\)⏟N′​elements\\sigma\\leftarrow\\underbrace\{\(\\texttt\{None\},\\ldots,\\texttt\{None\}\)\}\_\{N^\{\\prime\}\\text\{ elements\}\}⊳\\trianglerightσ⁡\[j\]\\sigma\[j\]is the answer whose appending at positionjjtriggersτ\\tau, elseNone

6:

runs←\(0,…,0\)⏟N′​elements\\texttt\{runs\}\\leftarrow\\underbrace\{\(0,\\ldots,0\)\}\_\{N^\{\\prime\}\\text\{ elements\}\}⊳\\trianglerightruns​\[j\]\\texttt\{runs\}\[j\]is the length of the maximal equal\-σ\\sigmarun ending atjj

7:

s←\(0,…,0\)s\\leftarrow\(0,\\ldots,0\)⊳\\trianglerightKKelements tracking answer counts

8:/\*\* Single pass over each prefix to buildσ\\sigmaandruns:O⁡\(N′​K\)O\(N^\{\\prime\}K\)\*\*/

9:for

j=1,…,N′−1j=1,\\dots,N^\{\\prime\}\-1do

10:

s⁡\[yj′\]←s⁡\[yj′\]\+1s\[y^\{\\prime\}\_\{j\}\]\\leftarrow s\[y^\{\\prime\}\_\{j\}\]\+1
11:

v⋆←arg⁡maxv⁡s⁡\[v\]v^\{\\star\}\\leftarrow\\arg\\max\_\{v\}s\[v\];

s\(1\),s\(2\)←s\_\{\(1\)\},s\_\{\(2\)\}\\leftarrowtwo largest entries of

ss
12:if

s\(1\)\>s\(2\)s\_\{\(1\)\}\>s\_\{\(2\)\}and

τ⁡\(s\(1\),s\(2\)\)=0\\tau\(s\_\{\(1\)\},s\_\{\(2\)\}\)=0and

τ⁡\(s\(1\)\+1,s\(2\)\)=1\\tau\(s\_\{\(1\)\}\+1,s\_\{\(2\)\}\)=1then

13:

σ⁡\[j\]←v⋆\\sigma\[j\]\\leftarrow v^\{\\star\}⊳\\trianglerightAppendingv⋆v^\{\\star\}to the length\-jjprefix triggersτ\\tau

14:endif

15:if

σ⁡\[j\]≠None\\sigma\[j\]\\neq\\texttt\{None\}and

σ⁡\[j\]=σ⁡\[j−1\]\\sigma\[j\]=\\sigma\[j\-1\]then

16:

runs​\[j\]←runs​\[j−1\]\+1\\texttt\{runs\}\[j\]\\leftarrow\\texttt\{runs\}\[j\-1\]\+1⊳\\trianglerightExtend the run of prefixes with the same triggering answer

17:else

18:

runs\[j\]←𝟙\[σ\[j\]≠None\]\\texttt\{runs\}\[j\]\\leftarrow\\mathbbm\{1\}\[\\sigma\[j\]\\neq\\texttt\{None\}\]
19:endif

20:endfor

21:/\*\* BuildCountsusing thatCounts​\[j\]=∑L=0LmaxCounts​\[j−L−1\]\\texttt\{Counts\}\[j\]=\\sum\_\{L=0\}^\{L\_\{\\max\}\}\\texttt\{Counts\}\[j\{\-\}L\{\-\}1\]is a contiguous window:O⁡\(N′\)O\(N^\{\\prime\}\)\*\*/

22:for

j=2,…,N′j=2,\\ldots,N^\{\\prime\}do

23:if

\(j−2\)≥1\(j\-2\)\\geq 1and

σ⁡\[j−2\]=yj′\\sigma\[j\-2\]=y^\{\\prime\}\_\{j\}then

24:

Lmax←runs​\[j−2\]L\_\{\\max\}\\leftarrow\\texttt\{runs\}\[j\-2\]
25:else

26:

Lmax←0L\_\{\\max\}\\leftarrow 0
27:endif

28:

Counts​\[j\]←S⁡\[j−1\]−S⁡\[j−2−Lmax\]\\texttt\{Counts\}\[j\]\\leftarrow S\[j\-1\]\-S\[j\-2\-L\_\{\\max\}\]
29:

S⁡\[j\]←S⁡\[j−1\]\+Counts​\[j\]S\[j\]\\leftarrow S\[j\-1\]\+\\texttt\{Counts\}\[j\]
30:endfor

31:return

Counts​\[N′\]⋅pyN′′⋅∏i=1N′pyi′\\texttt\{Counts\}\[N^\{\\prime\}\]\\cdot p\_\{y^\{\\prime\}\_\{N^\{\\prime\}\}\}\\cdot\\prod\_\{i=1\}^\{N^\{\\prime\}\}p\_\{y^\{\\prime\}\_\{i\}\}

## Appendix EAdditional Experimental Details

Our experiments in Section[5](https://arxiv.org/html/2609.30352#S5)rely on the dataset released by[Velasco et al\. \(2026a\)](https://arxiv.org/html/2609.30352#bib.bib12), which contains LLM outputs for multiple test\-time compute methods across several benchmark datasets and is publicly available on Hugging Face\.999[https://huggingface\.co/datasets/Human\-Centric\-Machine\-Learning/strategic\-ttc\-data](https://huggingface.co/datasets/Human-Centric-Machine-Learning/strategic-ttc-data)Specifically, we use model outputs generated under self\-consistency and best\-of\-NNacross three datasets\. We refer the reader to Appendix D of[Velasco et al\. \(2026a\)](https://arxiv.org/html/2609.30352#bib.bib12)for a detailed description of the data\-generation procedure\.

Datasets\.We use LLM outputs from three datasets:GSM8K,GPQA, andAIME\.GSM8K\([Cobbe et al\., 2021](https://arxiv.org/html/2609.30352#bib.bib45)\)is a mathematics benchmark consisting of grade\-school\-level problems,GPQA\([Rein et al\., 2024](https://arxiv.org/html/2609.30352#bib.bib47)\)is a multiple\-choice STEM question\-answering benchmark, andAIME\([Zhang and Math\-AI, 2025](https://arxiv.org/html/2609.30352#bib.bib46)\)is a mathematical reasoning benchmark based on problems from the American Invitational Mathematics Examination\. All three datasets provide verifiable ground\-truth answers for each query and are publicly available on Hugging Face\.101010[https://huggingface\.co/datasets/openai/gsm8k](https://huggingface.co/datasets/openai/gsm8k),111111[https://huggingface\.co/datasets/Idavidrein/gpqa](https://huggingface.co/datasets/Idavidrein/gpqa),121212[https://huggingface\.co/datasets/Maxwell\-Jia/AIME\_2024](https://huggingface.co/datasets/Maxwell-Jia/AIME_2024)

Models\.From theLlamafamily, we considerLlama\-3\-8B\-Instruct,Llama\-3\.1\-8B\-Instruct,Llama\-3\.2\-1B\-Instruct, andLlama\-3\.2\-3B\-Instruct\. From theQwenfamily, we considerQwen\-2\-0\.5B\-Instruct,Qwen\-2\-1\.5B\-Instruct,Qwen\-2\-7B\-Instruct,Qwen\-2\.5\-3B\-Instruct, andQwen\-2\.5\-7B\-Instruct\. We additionally consider three reasoning models distilled fromDeepSeek\-R1:DeepSeek\-R1\-Distill\-Llama\-8B,DeepSeek\-R1\-Distill\-Qwen\-1\.5B, andDeepSeek\-R1\-Distill\-Qwen\-7B\. For the best\-of\-NNexperiments in Appendix[F\.4](https://arxiv.org/html/2609.30352#A6.SS4), we use theArmoRM\-Llama3\-8B\-v0\.1reward model to score the outputs generated by these models\. All the models are publicly available through Hugging Face\.

Generation details\.The model outputs were generated using the temperature settings recommended in their official Hugging Face model cards: temperature0\.60\.6for theLlamafamily and temperature0\.70\.7for theQwenfamily\. Neither top\-ppnor top\-kksampling was used\. For each query, the dataset contains128128outputs for non\-reasoning models and3232outputs for reasoning models\. See[Velasco et al\. \(2026a\)](https://arxiv.org/html/2609.30352#bib.bib12)for details regarding prompt formatting\.

Licenses\.TheLlama\-3models andArmoRM\-Llama3\-8B\-v0\.1are licensed under the LLAMA 3 COMMUNITY LICENSE AGREEMENT\.131313[https://www\.llama\.com/llama3/license/](https://www.llama.com/llama3/license/)TheLlama\-3\.1models are licensed under the LLAMA 3\.1 COMMUNITY LICENSE AGREEMENT\.141414[https://www\.llama\.com/llama3\_1/license/](https://www.llama.com/llama3_1/license/)TheLlama\-3\.2models are licensed under the LLAMA 3\.2 COMMUNITY LICENSE AGREEMENT\.151515[https://www\.llama\.com/llama3\_2/license/](https://www.llama.com/llama3_2/license/)TheQwenmodels are licensed under the Tongyi Qianwen LICENSE AGREEMENT\.161616[https://github\.com/QwenLM/Qwen/blob/main/Tongyi%20Qianwen%20LICENSE%20AGREEMENT/](https://github.com/QwenLM/Qwen/blob/main/Tongyi%20Qianwen%20LICENSE%20AGREEMENT/)TheDeepSeek\-R1\-Distill\-Llama\-8B,DeepSeek\-R1\-Distill\-Qwen\-1\.5B, andDeepSeek\-R1\-Distill\-Qwen\-7Bmodels are licensed under the MIT License\.GPQAandAIMEare licensed under Creative Commons Attribution 4\.0, andGSM8Kis licensed under MIT License\. Thestrategic\-ttc\-datadataset used in our experiments is also licensed under the MIT License\.

## Appendix FAdditional Experimental Results

In this section, we present additional experimental results that complement those in Section[5](https://arxiv.org/html/2609.30352#S5)\.

### F\.1Experimental Results on Synthetic Data

We first empirically examine how the answer\-probability distribution\(p1,…,pK\)\(p\_\{1\},\\ldots,p\_\{K\}\)affects the expected number of additional answers𝔼⁡\[N′−N\]\\mathbb\{E\}\[N^\{\\prime\}\-N\]generated by Algorithm[1](https://arxiv.org/html/2609.30352#alg1)\.

Experimental setup\.Motivated by the lower bound in Proposition[4](https://arxiv.org/html/2609.30352#Thmtheorem4), and as well as prior theoretical results showing that the sample complexity of mode identification depends on the probability between the two most likely answers\([Feng et al\., 2026](https://arxiv.org/html/2609.30352#bib.bib2)\), we construct answer\-probability distributions\(p1,…,pK\)\(p\_\{1\},\\dots,p\_\{K\}\)with modea1a\_\{1\}by varying the gapΔ=p1−p2\\Delta=p\_\{1\}\-p\_\{2\}and spreading the remaining probability mass uniformly acrossa2,…,aKa\_\{2\},\\dots,a\_\{K\}:

p1=1\+\(K−1\)​ΔK,p2=…=pK=1−ΔK\.\\displaystyle p\_\{1\}=\\frac\{1\+\(K\-1\)\\Delta\}\{K\},\\qquad p\_\{2\}=\\ldots=p\_\{K\}=\\frac\{1\-\\Delta\}\{K\}\.ForK=2K=2, we consider2020equally spaced values ofΔ∈\[0\.1,0\.9\]\\Delta\\in\[0\.1,0\.9\]\. For each resulting answer\-probability distribution, we sample1,0001,000faithfully stopped sequences𝐲=\(y1,…,yN\)\\mathbf\{y\}=\(y\_\{1\},\\dots,y\_\{N\}\)under both the PPR\-1v1 stopping rule\([Anand Jain et al\., 2022](https://arxiv.org/html/2609.30352#bib.bib1)\)\(Example[1](https://arxiv.org/html/2609.30352#Thmexample1)\) and the ASC stopping rule\([Aggarwal et al\., 2023](https://arxiv.org/html/2609.30352#bib.bib4)\)\(Example[2](https://arxiv.org/html/2609.30352#Thmexample2)\)\. For ASC, we setγ=0\.95\\gamma=0\.95following[Aggarwal et al\. \(2023\)](https://arxiv.org/html/2609.30352#bib.bib4); for PPR\-1v1, we setδ=0\.1\\delta=0\.1\. Starting from each faithfully stopped sequence𝐲\\mathbf\{y\}, we run Algorithm[1](https://arxiv.org/html/2609.30352#alg1)withα=0\\alpha=0, corresponding to no audit, to obtain𝐲′=\(y1′,…,yN′′\)\\mathbf\{y\}^\{\\prime\}=\(y^\{\\prime\}\_\{1\},\\dots,y^\{\\prime\}\_\{N^\{\\prime\}\}\)\.

Results\.Figure[3](https://arxiv.org/html/2609.30352#A6.F3)shows the empirical mean number of additional answers,𝔼⁡\[N′−N\]\\mathbb\{E\}\[N^\{\\prime\}\-N\], as a function of the top\-two probability gapp\(1\)−p\(2\)p\_\{\(1\)\}\-p\_\{\(2\)\}\. Consistent with Proposition[4](https://arxiv.org/html/2609.30352#Thmtheorem4), the number of additional answers increases asp\(1\)→p\(2\)p\_\{\(1\)\}\\to p\_\{\(2\)\}, exceeding the lower bound by a substantial margin\. This shows that Algorithm[1](https://arxiv.org/html/2609.30352#alg1)has greater opportunity to extend a sequence when the LLM’s answer\-probability distribution assigns similar probabilities to the two most likely answers\.

Figure 3:Additional answers generated by Algorithm[1](https://arxiv.org/html/2609.30352#alg1)on synthetic distributions\.ForK=2K=2, we report the empirical mean number of additional answersN′−NN^\{\\prime\}\-Ngenerated by Algorithm[1](https://arxiv.org/html/2609.30352#alg1)\(dotted lines\), together with the theoretical lower bound from Proposition[4](https://arxiv.org/html/2609.30352#Thmtheorem4)\(solid lines\), as a function of the top\-two probability gapp\(1\)−p\(2\)p\_\{\(1\)\}\-p\_\{\(2\)\}\. The shaded regions indicate±2\\pm 2standard errors of the average\.
### F\.2Additional Cost to Users

Section[5](https://arxiv.org/html/2609.30352#S5)measures overcharging in terms of the number of additional reasoning paths generated by Algorithm[1](https://arxiv.org/html/2609.30352#alg1)\. In practice, however, users are typically billed by the number of tokens the model generates, and reasoning paths can vary substantially in length\. This distinction is particularly important for reasoning models, whose outputs may contain long reasoning traces and incur substantially greater token costs per additional sample\. As a consequence, even a modest number of additional answers generated by Algorithm[1](https://arxiv.org/html/2609.30352#alg1)can result in a substantial price increase for the user\. To quantify this effect, Figure[4](https://arxiv.org/html/2609.30352#A6.F4)converts the token counts of the additional reasoning paths generated by Algorithm[1](https://arxiv.org/html/2609.30352#alg1)into monetary units and reports the resulting billing overcharge, in U\.S\. cents, across models and datasets\.

![Refer to caption](https://arxiv.org/html/2609.30352v1/asc_alpha=0.1_billing_overcharge.png)Figure 4:Price increase from additional answers\.For each query, we plot the additional price, measured in U\.S\. cents, charged for theN′−NN^\{\\prime\}\-Nadditional reasoning paths generated by Algorithm[1](https://arxiv.org/html/2609.30352#alg1), as a function of the faithful stopping timeNN\. Color indicates the estimated top\-two probability gapp^\(1\)−p^\(2\)\\hat\{p\}\_\{\(1\)\}\-\\hat\{p\}\_\{\(2\)\}, with smaller gaps corresponding to more difficult queries\. We set the audit threshold toα=0\.1\\alpha=0\.1and use the ASC stopping rule withγ=0\.95\\gamma=0\.95\.
### F\.3Experiments with Inadmissible Stopping Rules

An admissible stopping rule \(Definition[3](https://arxiv.org/html/2609.30352#Thmtheorem3)\) is required only for the theoretical lower bound in Proposition[4](https://arxiv.org/html/2609.30352#Thmtheorem4)\. However, the compatibility guarantee in Proposition[2](https://arxiv.org/html/2609.30352#Thmtheorem2)does not require the stopping rule to be admissible\. Algorithm[1](https://arxiv.org/html/2609.30352#alg1)can be applied to construct a longer answer sequence for any stopping rule while still ensuring that the longer sequence is compatible with the rule\. To evaluate whether Algorithm[1](https://arxiv.org/html/2609.30352#alg1)remains effective outside the admissible class, we consider Early\-Stopping Self\-Consistency \(ESC\)\([Li et al\., 2024](https://arxiv.org/html/2609.30352#bib.bib5)\)with a window size of55, which is an inadmissible stopping rule \(see Appendix[A\.3](https://arxiv.org/html/2609.30352#A1.SS3)\)\. Figure[5](https://arxiv.org/html/2609.30352#A6.F5)shows that Algorithm[1](https://arxiv.org/html/2609.30352#alg1)still generates a substantial number of additional reasoning paths under ESC across models and datasets\.

Figure 5:Distributions of additional reasoning paths under ESC\.For queries fromGSM8K,AIME, andGPQA, each panel shows the complementary cumulative distributionPr⁡\(N′−N≥x\)\\Pr\(N^\{\\prime\}\-N\\geq x\)of the number of additional reasoning paths generated by Algorithm[1](https://arxiv.org/html/2609.30352#alg1)beyond the faithful stopping time\. Colors denote datasets, and line width distinguishes model variants within each family\. We use ESC stopping rule with window size55as the stopping rule and setα=0\.1\\alpha=0\.1\.Figure[6](https://arxiv.org/html/2609.30352#A6.F6)examines the effect of the audit threshold under ESC\. Across models and datasets, imposing the audit reduces the provider’s ability to extend some sequences, but substantial overcharging remains at the 90th percentile even forα=0\.1\\alpha=0\.1\.

Figure 6:Influence of the audit threshold under ESC\.For queries fromGSM8K,AIME, andGPQA, we report the9090th percentile of the number of additional answersN′−NN^\{\\prime\}\-Ngenerated by Algorithm[1](https://arxiv.org/html/2609.30352#alg1)using ESC for different audit thresholdsα\\alpha\. The settingα=0\\alpha=0corresponds to no audit\.DSabbreviatesDeepSeek\-R1\-Distill\.
### F\.4Adaptive Best\-of\-N Experiments

We next show that the conclusions of Section[5](https://arxiv.org/html/2609.30352#S5)extend beyond self\-consistency to adaptive best\-of\-NN\. We again use the dataset of[Velasco et al\. \(2026a\)](https://arxiv.org/html/2609.30352#bib.bib12), which includes a reward score for each generated answer computed usingRLHFlow/ArmoRM\-Llama3\-8B\-v0\.1\. We consider a simple threshold\-based stopping rule that instructs the provider to stop as soon as it observes a reasoning path with reward at leastr∗=1\.25⋅median⁡\(R1,…,RNcal\)r^\{\*\}=1\.25\\cdot\\operatorname\{median\}\(R\_\{1\},\\ldots,R\_\{N\_\{\\mathrm\{cal\}\}\}\), whereR1,…,RNcalR\_\{1\},\\ldots,R\_\{N\_\{\\mathrm\{cal\}\}\}denote reward scores from a calibration sample\. In our experiments, the calibration sample consists of all pre\-generated answers \(Ncal=128N\_\{\\mathrm\{cal\}\}=128for instruct models andNcal=32N\_\{\\mathrm\{cal\}\}=32for reasoning models\)\.

Starting from the faithfully stopped sequence, we adapt the logic of Algorithm[1](https://arxiv.org/html/2609.30352#alg1)to the reward\-based stopping rule, where whenever a reasoning path crosses the reward threshold, the provider generates an additional path and attempts to reorder it so that the reported sequence remains compatible with the stopping rule\. Figure[7](https://arxiv.org/html/2609.30352#A6.F7)shows that this strategy can generate additional reasoning paths across model families and datasets, suggesting that the opportunity for strategic continuation is not unique to count\-based self\-consistency\.

Figure 7:Distributions of additional reasoning paths under adaptive best\-of\-N\\bm\{N\}\.For queries fromGSM8K,AIME, andGPQA, each panel shows the complementary cumulative distributionPr⁡\(N′−N≥x\)\\Pr\(N^\{\\prime\}\-N\\geq x\)of additional reasoning paths generated beyond the faithful stopping time by adapting Algorithm[1](https://arxiv.org/html/2609.30352#alg1)to a reward\-threshold stopping rule\. Colors denote datasets, and line width distinguishes model variants within each family\. These experiments setα=0\.1\\alpha=0\.1\.Auditing adaptive best\-of\-N\\bm\{N\}\.Adaptive best\-of\-NNrequires a different auditing procedure from the one developed for self\-consistency in Section[4](https://arxiv.org/html/2609.30352#S4)\. While Eq\. \([4](https://arxiv.org/html/2609.30352#S4.E4)\) evaluates answer sequences under an iid categorical model, best\-of\-NNstops according to continuous reward scores\. An audit must therefore evaluate whether the observed reward trajectory, including the timing of threshold crossing, is plausible under faithful execution\. A sufficiently informative audit must distinguish between reward magnitudes and the ordering of reward scores, rather than reducing each reasoning path to whether its reward exceedsr∗r^\{\*\}\. This parallels the likelihood\-ratio audit in Section[4](https://arxiv.org/html/2609.30352#S4), which uses the full sequence of answer identities to accumulate evidence against a provider who reorders answers\. Developing analogous audits for adaptive best\-of\-NN—for instance, by testing whether the observed reward sequence is consistent with iid draws from the model’s reward distribution—is an important direction for future work\.