Estimating the Self-Consistency of LLMs

Robert Nowak · 2025

Read Estimating the Self-Consistency of LLMs by Robert Nowak (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-19489.txt.

Introduction

Firms often ask a language model the same prompt many times and blend the replies to gain trust in the result. Robert Nowak studies how to judge that self-agreement under a fixed budget of calls. His short note weighs two uses of the budget: more distinct prompts, or more repeats of each prompt. The math treats the total as the product of those two counts.

The analysis favors a rough even split, with each count near the square root of the budget. Spending all calls on repeats of a few prompts wastes information. Spreading them too thin leaves agreement untested. The note gives builders a simple rule for planning tests. It also frames agreement itself as a thing that can be measured with care, not just assumed.

Catalog record

CREATORRobert Nowak
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE9 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-19489

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Estimating the Self-Consistency of LLMs
Robert Nowak

Abstract




Systems often repeat the same prompt to large language models (LLMs) and aggregate responses to improve reliability. Common approaches include
self-consistency
or simple majority voting (sample multiple outputs and choose the mode),
prompt ensembling
(rephrasing prompts to reduce wording sensitivity), and
multi-agent debate
(running multiple instances and aggregating their conclusions). Such consensus methods can stabilize outputs and improve accuracy, especially on multi-step reasoning tasks
[
1
]
. This short note analyzes an estimator of the self-consistency of LLMs and the tradeoffs it induces under a fixed compute budget
B=mn
, where
m
is the number of prompts sampled from the task distribution and
n
is the number of repeated LLM calls per prompt; the resulting analysis favors a rough split
m,n\propto\sqrt{B}
. It complements recent work on self-consistency prompting that aggregates multiple sampled reasoning paths to stabilize predictions
[
2
,
3
]
.

Consider a prompt
x
that requires a binary response. Suppose we call an LLM
n
times to ask if this is a positive or negative
x
. Our analysis concerns
self-consistency error
. Assume the
n
responses are independent and identically distributed and let
p(x)
denote the probability of a positive response. The self-consistency error of the LLM on
x
is

{\cal E}(x)=\min\{p(x),1-p(x)\}\ .

Equivalently, taking the model’s most probable label as the reference,
{\cal E}(x)
is the probability that an independently sampled response disagrees with that (majority) label.

The average self-consistency error over a domain of prompts
{\mathcal{X}}
is

{\cal E}\ :=\ \frac{1}{|{\mathcal{X}}|}\sum_{x\in{\mathcal{X}}}{\cal E}(x)\ .

Instead of the uniform distribution of
{\mathcal{X}}
, we can also consider a general distribution
q
over
{\mathcal{X}}
. In that case, the
average self-consistency error rate over a domain of prompts
{\mathcal{X}}
is defined to be

{\cal E}\ :=\ \sum_{x\in{\mathcal{X}}}{\cal E}(x)\,q(x)\ .

To estimate the self-consistency error for a given
x
consider the plug-in estimator based on
\widehat{p}(x)=k/n
, where
k
is the number of calls to the LLM that come back positive,

\widehat{\cal E}(x)\ :=\ \min\{k/n,1-k/n\}\ .

The average error can be estimated by drawing
m
prompts
x_{1},\dots,x_{m}
independently according to the distribution
q
(possibly uniform) from
{\mathcal{X}}
and forming the estimator

\widehat{\cal E}\ :=\ \frac{1}{m}\sum_{i=1}^{m}\widehat{\cal E}(x_{i})\ .

Theorem 1
.

The expected squared error of the estimator
\widehat{\cal E}
satisfies the bound

{\mathbb{E}}[({\cal E}-\widehat{\cal E})^{2}]\ \leq\ \frac{1}{8m}+\frac{1}{\pi n}+\frac{1}{2nm}\ .

The first term is due to the variance incurred by the random subsample of prompts used to form the estimator. The second term is due to the bias inherent in the estimator
\widehat{\cal E}(x)
and the third term is due to its variance. The theorem suggests that given a budget
B
of total calls to the LLM, the upper bound is minimized by taking
m=n=O(\sqrt{B})
(since the third term in the bound is negligible compared to the other two terms). The upper bound is exactly minimized by

m^{*}\;=\;\sqrt{\tfrac{\pi B}{8}},\qquad n^{*}\;=\;\sqrt{\tfrac{8B}{\pi}}\,.

and these real values can be rounded to the nearest integers.

Proof.

Assume that
n
is even and that
p=p(x)\leq 1/2
; similar derivations can be carried out when
n
is odd and/or
p(x)>1/2
. To bound the bias of
\widehat{\cal E}(x)
first note that the expectation of
n\,\widehat{\cal E}(x)
is

\displaystyle{\mathbb{E}}[\min\{k,n-k\}]

\displaystyle=

\displaystyle\sum_{k=0}^{n/2}k\binom{n}{k}p^{k}(1-p)^{n-k}\ +\ \sum_{n/2+1}^{n}(n-k)\binom{n}{k}p^{k}(1-p)^{n-k}

\displaystyle=

\displaystyle\sum_{k=0}^{n}k\binom{n}{k}p^{k}(1-p)^{n-k}\ +\ \sum_{n/2+1}^{n}(n-2k)\binom{n}{k}p^{k}(1-p)^{n-k}

\displaystyle=

\displaystyle np\ +\ \sum_{n/2+1}^{n}(n-2k)\binom{n}{k}p^{k}(1-p)^{n-k}

So the bias is given by

\displaystyle{\cal E}(x)-{\mathbb{E}}[\widehat{\cal E}(x)]

\displaystyle=

\displaystyle\frac{1}{n}\sum_{n/2+1}^{n}(2k-n)\binom{n}{k}p^{k}(1-p)^{n-k}\ \geq\ 0

Next we upper bound the bias. The bound that follows is probably known, but a good reference was not found, so the derivation is included here.
First note that bias is largest when
p=1/2
since
k>n/2
in the sum. So we have the bound

\displaystyle{\cal E}(x)-{\mathbb{E}}[\widehat{\cal E}(x)]

\displaystyle\leq

\displaystyle\frac{1}{n}\sum_{n/2+1}^{n}(2k-n)\binom{n}{k}2^{-n}

The mean of a binomial distribution with parameters
n
and
1/2
is
n/2
, and by symmetry
\sum_{n/2+1}^{n}k\binom{n}{k}2^{-n}=\sum_{k=1}{n/2}k\binom{n}{k}2^{-n}=n/4
. Therefore

\frac{1}{n}\sum_{n/2+1}^{n}2k\binom{n}{k}2^{-n}=1/2.

Next consider

\displaystyle\sum_{n/2+1}^{n}\binom{n}{k}2^{-n}

\displaystyle=

\displaystyle\sum_{n/2}^{n}\binom{n}{k}2^{-n}-\frac{1}{2}\binom{n}{n/2}2^{-n}\ =\ 1/2-\frac{1}{2}\binom{n}{n/2}2^{-n}

Combining this with the previous bound, we have

\displaystyle{\cal E}(x)-{\mathbb{E}}[\widehat{\cal E}(x)]

\displaystyle\leq

\displaystyle\frac{1}{2}\binom{n}{n/2}2^{-n}

This can be further bounded using upper and lower bounds to Stirling’s approximation
[
4
]
. Applying these bounds we have

\displaystyle\binom{n}{n/2}2^{-n}

\displaystyle\leq

\displaystyle 2^{-n}\frac{\sqrt{2\pi n}(n/e)^{n}e^{\frac{1}{12n}}}{(\sqrt{2\pi n/2}((n/2)/e)^{n/2}e^{\frac{1}{6n+1}})^{2}}

\displaystyle=

\displaystyle\sqrt{\frac{2}{\pi n}}e^{\frac{1}{12n}-\frac{2}{6n+1}}\ \leq\ \sqrt{\frac{2}{\pi n}}

This yields the bound

\displaystyle{\cal E}(x)-{\mathbb{E}}[\widehat{\cal E}(x)]

\displaystyle\leq

\displaystyle\sqrt{\frac{1}{2\pi n}}

We can bound the variance of
\widehat{\cal E}(x)
using the fact that
\min\{p,1-p\}
is a
1
-Lipschitz
function in
p
.

\displaystyle{\mathbb{V}}[\widehat{\cal E}(x)]\ =\ {\mathbb{V}}[\widehat{\cal E}(x)-{\cal E}(x)]\ \leq\ {\mathbb{E}}[(\widehat{\cal E}(x)-{\cal E}(x))^{2}]\ \leq\ {\mathbb{E}}[(\widehat{p}(x)-p(x))^{2}]\ \leq\ \frac{1}{4n}\ .

Now consider estimating the overall probability of error
{\cal E}:=\sum_{x\in{\mathcal{X}}}{\cal E}(x)\,q(x)
using
x_{1},\dots,x_{m}
drawn independently according to the distribution
q
. Define
\widehat{\cal E}:=\frac{1}{m}\sum_{i=1}^{m}\widehat{\cal E}(x_{i})
and
\tilde{\cal E}:=\frac{1}{m}\sum_{i=1}^{m}{\cal E}(x_{i})
. The expected squared error of this estimator is bounded as follows.

\displaystyle{\mathbb{E}}[({\cal E}-\widehat{\cal E})^{2}]

\displaystyle=

\displaystyle{\mathbb{E}}[({\cal E}-\tilde{\cal E}+\tilde{\cal E}-\widehat{\cal E})^{2}]

\displaystyle\leq

\displaystyle 2\,{\mathbb{E}}[({\cal E}-\tilde{\cal E})^{2}]+2\,{\mathbb{E}}[(\tilde{\cal E}-\widehat{\cal E})^{2}]

\displaystyle\leq

\displaystyle\frac{1}{8m}+2\,{\mathbb{E}}[(\tilde{\cal E}-\widehat{\cal E})^{2}]\ ,

where we use the fact that
\tilde{\cal E}
is an unbiased estimator of
{\cal E}
and it is the average of
m
random variables in
[0,1/2]
; thus, its variance is at most
\frac{1}{16m}
. We next bound
{\mathbb{E}}[(\tilde{\cal E}-\widehat{\cal E})^{2}]
.

\displaystyle{\mathbb{E}}[(\tilde{\cal E}-\widehat{\cal E})^{2}]

\displaystyle=

\displaystyle\frac{1}{m^{2}}{\mathbb{E}}\Big[\Big(\sum_{i=1}^{m}{\cal E}(x_{i})-\widehat{\cal E}(x_{i})\Big)^{2}\Big]

\displaystyle=

\displaystyle\frac{1}{m^{2}}{\mathbb{E}}\Big[\Big(\sum_{i=1}^{m}{\cal E}(x_{i})-{\mathbb{E}}[\widehat{\cal E}(x_{i})]+{\mathbb{E}}[\widehat{\cal E}(x_{i})]-\widehat{\cal E}(x_{i})\Big)^{2}\Big]

To simplify the notation, let
a_{i}={\cal E}(x_{i})-{\mathbb{E}}[\widehat{\cal E}(x_{i})]
and
b_{i}={\mathbb{E}}[\widehat{\cal E}(x_{i})]-\widehat{\cal E}(x_{i})
,
i=1,\dots,m
.
Then

\displaystyle{\mathbb{E}}[(\tilde{\cal E}-\widehat{\cal E})^{2}]

\displaystyle=

\displaystyle\frac{1}{m^{2}}\sum_{i,j=1}^{m}{\mathbb{E}}[(a_{i}+b_{i})(a_{j}+b_{j})]\ =\ \frac{1}{m^{2}}\sum_{i,j=1}^{m}{\mathbb{E}}[a_{i}a_{j}]+\frac{1}{m^{2}}\sum_{i=1}^{m}{\mathbb{E}}[b_{i}^{2}]

\displaystyle\leq

\displaystyle\frac{1}{2\pi n}+\frac{1}{4nm}

since
{\mathbb{E}}[a_{i}b_{j}]={\mathbb{E}}[a_{i}{\mathbb{E}}[b_{j}|x_{1},\dots,x_{m}]]=0
,
a_{i}\leq\frac{1}{\sqrt{2\pi n}}
, and
{\mathbb{E}}[b_{i}^{2}]\leq\frac{1}{4n}
. So we have

\displaystyle{\mathbb{E}}[({\cal E}-\widehat{\cal E})^{2}]

\displaystyle\leq

\displaystyle\frac{1}{8m}+\frac{1}{\pi n}+\frac{1}{2nm}\ .

∎

Possible Extensions.

Beyond the mean-squared analysis of the binary self-consistency error, one can (i) derive
high-probability
bounds by combining Bernstein (for
\tilde{\cal E}
) with binomial concentration for
\hat{\cal E}(x)
and a union bound over
m
; (ii) extend to
multi-class
settings by replacing
{\cal E}(x)=\min\{p,1-p\}
with
{\cal E}(x)=1-\max_{c}p_{c}(x)
, yielding analogous
1/m
,
1/n
, and
1/(mn)
scalings up to constants; and (iii) model correlated LLM calls via an intraclass correlation
\rho
, inflating the variance term and quantifying the erosion of majority-vote gains. These refinements preserve the optimal budget split
m^{*},\,n^{*}\propto\sqrt{B}
and clarify when departures from iid sampling (e.g., shared randomness, caching) impact the constants.

Acknowledgment.

Read the complete text