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:
- 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.
- 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