Estimating the Self-Consistency of LLMs

Robert NowakarXiv 2025 · DOI · arXiv

TL;DR

When evaluating how often an LLM disagrees with itself (its "self-consistency error"), researchers face a trade-off: should they test many different prompts a few times each, or a few prompts many times? This paper mathematically proves that to minimize estimation error under a fixed budget, you should split your resources roughly equally, scaling both the number of prompts and the number of repetitions by the square root of your total budget ($m, n \propto \sqrt{B}$).

What Problem Does This Paper Address?

Large Language Models (LLMs) are notoriously stochastic. To improve reliability, engineers often use "self-consistency" strategies—running the same prompt multiple times and taking a majority vote. However, measuring a model's inherent self-consistency error (the probability that a random sample will disagree with the majority label) is expensive.

If you have a fixed budget of $B$ total API calls, you have a dilemma:

  1. High $m$, Low $n$: Test many different prompts ($m$) but only sample each one a few times ($n$). This gives you a good look at the prompt variety but a very noisy, biased estimate of each prompt's individual consistency.
  2. Low $m$, High $n$: Test only a few prompts ($m$) but sample them many times ($n$). This gives you a very precise look at those specific prompts but might fail to represent the broader task distribution.

The paper seeks the "Goldilocks zone"—the optimal allocation of $m$ and $n$ to get the most accurate estimate of a model's average self-consistency error.

Methods

The author performs a theoretical statistical analysis of a "plug-in estimator" for self-consistency error.

  • The Metric: The paper defines the error for a single prompt $x$ as $\mathcal{E}(x) = \min\{p(x), 1-p(x)\}$, where $p(x)$ is the probability of a positive response.
  • The Estimator: Since we don't know the true $p(x)$, we estimate it using $k/n$ (the fraction of positive results in $n$ trials).
  • The Analysis: The paper derives an upper bound for the Expected Squared Error of this estimate. This involves decomposing the error into:
  • Variance from prompt sampling: The risk that the $m$ prompts you chose aren't representative.
  • Bias from the estimator: The "min" function is inherently biased when using small sample sizes.
  • Variance from LLM sampling: The noise inherent in the $n$ calls per prompt.

Datasets

Not discussed in the paper. This is a theoretical mathematical note; it provides a proof and a framework rather than an empirical evaluation on specific LLM benchmarks.

Key Insights and Ideas

  • The Bias of "Min": A key insight is that the estimator is naturally biased. Because we take the minimum of the observed probabilities, we tend to underestimate the true error when $n$ is small.
  • The Square Root Rule: The most significant takeaway is that to minimize the total error bound, $m$ and $n$ should grow at the same rate. Specifically, the optimal values are $m^* \approx \sqrt{\pi B / 8}$ and $n^* \approx \sqrt{8B / \pi}$.
  • Symmetry in Scaling: While many researchers might intuitively prioritize more prompts ($m$) over more repetitions ($n$), the math suggests that the bias introduced by low $n$ is just as damaging as the variance introduced by low $m$.

Key Results

The paper provides a concrete upper bound for the expected squared error: $$\mathbb{E}[(\mathcal{E} - \hat{\mathcal{E}})^2] \leq \frac{1}{8m} + \frac{1}{\pi n} + \frac{1}{2nm}$$

From this bound, the author derives the optimal budget split:

  • Optimal Prompts ($m^*$): $\sqrt{\frac{\pi B}{8}}$
  • Optimal Repetitions ($n^*$): $\sqrt{\frac{8B}{\pi}}$

For example, if you have a budget of $B=1000$ calls, the math suggests testing roughly 20 prompts about 50 times each, rather than testing 500 prompts twice or 1 prompt 1000 times.

Limitations and Future Work

  • Binary Focus: The primary derivation assumes binary (positive/negative) responses. While the author notes that this can be extended to multi-class settings (using $1 - \max_c p_c(x)$), the detailed bounds for those cases are left for future work.
  • IID Assumption: The analysis assumes that LLM responses are independent and identically distributed (i.i.d.). In practice, factors like KV-caching or shared randomness in API clusters might introduce correlations that could "erode" the gains of majority voting.
  • Worst-Case Bias: The bias bound is tightest when the model is most uncertain ($p=0.5$). If a model is already very consistent, the required $n$ might be lower in practice than the theoretical "worst-case" suggests.

Summary updated

BibTeX
@misc{nowak2025estimating,
  author = {Robert Nowak},
  title = {{Estimating the Self-Consistency of LLMs}},
  year = {2025},
  eprint = {2509.19489},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2509.19489},
}
Figure