acceptodds
Under review as a conference paper at ICLR 2027

Two Calls, Two Moments, and the Vote-Accuracy Curve of Repeated LLM Inference

Abstract

Repeated sampling can improve LLM accuracy, and quantifying the gains from additional calls is essential for allocating test-time compute. We study binary decisions, a fundamental setting where repeated answers to the same question are aggregated by majority vote. We show that two independently sampled responses per example in a validation set with known answers constrain the latent distribution of example-level success probabilities to a class consistent with the paired outcomes. Optimizing over this class yields sharp accuracy and gain bounds at every finite voting budget. A shared large-sample confidence region accounts for validation uncertainty. We also obtain sharp infinite-vote bounds and moment-matched forecasts of the vote-accuracy curve. On QNLI and QQP, our method successfully distinguishes settings with voting gains above a target margin from those with little room for improvement.

Primary area:
learning theory
Keywords:
test-time scaling, majority voting, partial identification, moment problems, confidence regions

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 2 reviews, above 85% of the others.
Reviewer_ERVGOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper asks whether a small number of repeated responses can help decide if further sampling is worthwhile. It connects paired correctness observations to moment constraints on example success probabilities, then derives the best and worst voting accuracies consistent with those constraints. The main results include explicit bounds for three votes, a numerical method for other finite budgets, and bounds for the limiting accuracy. The experiments examine voting gains, changes in model rankings, and forecasts obtained from moment matching.

Critical strengths
  1. The bounds make a useful distinction between estimating the moments accurately and identifying the voting curve. Even with exact moments, different populations can have different voting gains. The attaining distributions show that this ambiguity is unavoidable with the available information, which gives the bounds a clear interpretation.

  2. The authors are careful about what the experiments establish. Q04 and N05 are fixed before evaluation on separate data, and the appendix explicitly distinguishes checks that reuse responses from independent coverage validation. The matched direct prompting control for N05 is also reported, even though it outperforms the randomized protocol after voting.

Critical weaknesses
  1. The experiments do not establish when collecting two responses on more examples is preferable to collecting more responses on fewer examples. Q04 and N05 demonstrate useful certificates, but the GSM8K bounds cannot resolve the observed gain at nine calls. Some uncertainty comes from knowing only two moments and would remain with more validation examples. A comparison under the same total call budget is needed to assess the advantage over directly estimating voting gains.

  2. In Table 10, the moments are estimated from the first two responses, while empirical voting accuracies use all five. LDGP’s small errors therefore do not yet establish prediction accuracy on separate response records. The confidence intervals also rely on the Wald approximation, whose coverage is not assessed by the checks in Appendix B.5 or Table 7, as the authors acknowledge. Given the 0.5 percentage point decision threshold, separate checks of forecasting accuracy and interval coverage would help establish whether these conclusions are reliable.

Questions for authors
  1. Under the same total validation call budget, how does collecting two responses per example compare with collecting five responses on fewer examples? The latter can estimate both three vote and five vote gains using the subset estimator in Appendix C. How often does each design correctly resolve the 0.5 percentage point threshold?

  2. For GSM8K, could you report gain intervals at three, five, and nine calls, both with the estimated moments fixed and after Wald projection? This would distinguish uncertainty from moment estimation from the ambiguity that remains even when the moments are known.

  3. Could you check Wald region coverage through multinomial simulations at the sample sizes and pair probabilities of Q04, N05, and N04, including nearby probabilities? This requires no additional LLM calls and would help assess calibration around the 0.5 percentage point threshold.

  4. Could Table 10’s three vote forecasts be evaluated by fitting the moments on two responses and measuring majority accuracy on the remaining three? The existing records allow this check. Please include uncertainty in the errors, since using fewer evaluation responses will introduce additional noise.

4 comments

Thank you for your careful review. We appreciate your constructive comments.

We have uploaded a revised version: changed text is in blue, new appendix sections have blue titles, and red margin notes name the review point each change addresses.

W1, Q1

A validation design's cost is set by the budgets it must cover. To compare budgets up to K, direct repeats take K calls on each of N examples and identify accuracy at budgets up to K; the infinite-vote endpoint would require calls per example to grow along with N. Two labeled calls per example require only N to grow: 2N calls estimate the exact envelopes at every odd budget and at the infinite-vote endpoint (Theorems 4.1 and 4.3). With our N=8192, budgets up to nine calls take 9N=73,728 calls by direct repeats and 2N=16,384 by pairs.

We ran your equal-cost comparison at prespecified budgets. On the existing records, 8190 calls give 4095 pairs (P) or 1638 five-call examples (D), with 1000 row resamples per condition. P samples a uniform pair per record and projects a nominal 95% bivariate Wald region onto both budgets; D estimates subset gains with two 97.5% paired-normal intervals (95% jointly). A correct resolution places the entire interval on the same side of the 0.5-point threshold as the empirical gain.

P resolves N04, a gain below the target, in 87.2%/83.7% of replications at three/five votes and Q05 in 24.3%/18.8%; D resolves these in 100%/100% and 100%/99.8%, and the other 16 settings, whose envelopes contain the target, in 3.4–100%; at a prespecified budget D resolves at least as often as P throughout. The maximum wrong-resolution rate is 0.7% (MC SE below 1.6 points), conditional on the records.

Appendix I.1 gives the first-order criterion. With m_P the margin by which the envelope clears the target, m_D≥m_P that of the gain, s_P, s_D the per-example standard deviations and c_P, c_D the critical values, pairs need fewer calls when

2(cPsP/mP)2<K(cDsD/mD)2,2(c_Ps_P/m_P)^2<K(c_Ds_D/m_D)^2,

that is, when the envelope is tight relative to the gain or K is large, since the left side does not grow with K. When the envelope contains the target, only direct repeats resolve the decision.

On the separate Q04/N05 triple records, 3072 calls give 1536 pairs or 1024 triples; over 1000 resamples, pair/triple correct-resolution rates are Q04 8.9%/92.8% and N05 66.3%/100% (MC SEs at most 1.49 points). The designs thus work in sequence: pairs give the envelope across budgets for 2N calls, and direct repeats verify the budget chosen from it. The revised version adds this comparison and the cost across budgets (Section 6.1; Appendix I.1).

Q2

The paper determines exactly when the two moments settle the sign and what settles it otherwise. By the finite-support result (Theorem 4.1), the envelope at every budget is exact for every moment pair, attained by laws with at most three support points. Theorem 4.2 turns this into an explicit criterion: for mu>1/2, three-vote accuracy exceeds mu for every compatible population exactly when rho<1−1/(2mu). Q04 and N05 meet it, so their lower certificates are positive.

At the GSM8K estimates (mu=91.23%) the criterion fails, so the exact envelopes span both signs at three, five and nine calls, whatever the precision of mu and nu. The sign is then fixed by higher moments: three-vote accuracy depends on the latent law only through nu and the third moment (Section 4.2), and R labeled calls identify accuracy at every odd budget up to R; beyond R the finite-support envelopes extend with at most R+1 support points (Section 4, after Theorem 4.1). The nine-call record supplies these moments and shows strict-majority gains of 0.42, 0.61 and 0.85 points at three, five and nine calls (Table 6, Appendix D.2). The revised version reports the exact envelopes and their Wald projections at three, five and nine calls (Table 13); they bound strict-majority correctness, whereas the GSM8K evaluation also reports plurality.

Our reply to W2, Q3 and Q4 follows in a second comment.

W2, Q3

Simulated Wald coverage is within about 0.3 points of nominal for Q04/N05 and below nominal for N04; an exact binomial check supports the N04 decision. Simulations use 20,000 multinomial replications/scenario, re-estimating covariance each time; N=6144 for Q04/N05 and 8192 for N04. Nearby scenarios multiply discordance by 0.8/1.2 and rescale the concordant cells:

SettingNominal0.8xOriginal1.2x
Q0497.50%97.38%97.56%97.70%
N0597.50%97.20%97.47%97.51%
N0495.00%94.27%94.52%94.72%
N0499.72%99.42%99.54%99.54%

Q04/N05's 97.5% marginal levels give nominal 95% joint coverage; 99.72% is Bonferroni across 18 settings. MC SEs are 0.03–0.16 points.

For N04, 51/8192 disagreements give a one-sided Clopper–Pearson upper limit 0.0090 at level 1−0.05/18. The paper’s bounds give three-/five-vote gain upper limits 0.452/0.465 points, below 0.5, assuming iid item pairs and conditional-iid voting. The revised version adds the coverage simulation and the exact check (Appendix I.4).

Q4

On separate responses, three-vote LDGP forecasts have mean absolute error 0.288 points. Table 10 uses shared responses, so we fit LDGP on calls 1–2 and evaluate majority on calls 3–5; SEs account for item-level covariance through the joint influence function. The revised version adds this evaluation as Table 15, with each setting's error (positive for overprediction) and its 95% delta-method interval.

LDGP is a point forecast: it selects one latent distribution compatible with the moments, whereas the sharp interval covers every compatible population, so its accuracy is reported apart from Q3's coverage.

We hope these responses address your concerns, and we would be grateful if you would consider raising your score.

Thank you for the explanations and the effort you put into the rebuttal. Your responses helped clarify my understanding of the paper, and I have increased my score after considering the additional explanations.

Thank you for the careful reading of our responses and for raising your score. We are glad the explanations clarified the paper, and we would be happy to answer any further questions.

Reviewer_FXvDOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper investigates whether repeated calls to a LLM, aggregated by majority vote, improve accuracy on binary questions. The idea is to make two independent calls on each of N validation questions with known answers. The resulting correctness pairs estimate the first two moments of the distribution of question-specific success probabilities, equivalently capturing average accuracy and pairwise correctness correlation. These moments do not uniquely determine voting accuracy. The authors therefore derive lower and upper bounds on accuracy at each voting budget, and on gains between budgets, by optimizing over all compatible success-probability distributions. They use classical moment-optimization techniques to obtain a three-point-support reduction and quadratic dual bounds, with explicit formulas for three votes and the infinite-vote limit. A joint, asymptotic confidence region accounts for validation uncertainty, while optional parametric models provide point forecasts. The resulting intervals can help determine whether additional calls are worth their cost, although they may be inconclusive and do not automatically identify an optimal budget. Experiments on binary language tasks illustrate this use. The guarantees rely on independent calls conditional on each question and a fixed inference procedure.

Critical strengths

• The paper clearly introduces the practical question, explains why single-call accuracy does not determine the benefit of voting, and connects the statistical formulation to decisions about inference budgets. • Determining whether additional LLM calls justify their cost is practically relevant. A straightforward approach is to evaluate several voting budgets directly on labeled validation data, which requires many calls per example. The proposed two-call procedure offers an appealing alternative: it bounds the gains compatible with the observed moments without specifying the latent distribution. • The analysis goes beyond loose sufficient bounds by characterizing sharp accuracy intervals and providing compatible distributions that attain the finite-budget endpoints. Although the small-support reduction and polynomial duality are classical, their application yields a coherent and useful analysis.

Critical weaknesses

• The analysis assumes that repeated calls on a fixed question are independent and have the same success probability. This is plausible for separately sampled generations under a stable inference procedure, but it need not hold when calls share hidden serving state, use correlated randomness, or incorporate feedback from previous responses. Under such dependence, the probability of two correct responses need not equal the second moment of the question-specific success probability, undermining the central identification step. The paper would benefit from stronger empirical checks and a sensitivity analysis showing how violations affect the conclusions. • The two-sided accuracy guarantees apply directly to binary majority voting. For multiple-choice or open-ended tasks, the most frequent answer can be correct without receiving a strict majority, and its success depends on how probability is distributed among incorrect answers. Consequently, the two correctness moments are insufficient to characterize the deployed aggregation rule. Although the paper acknowledges this distinction, it limits applicability to many prominent uses of repeated LLM inference. • The experiments on QNLI and QQP demonstrate that the bounds can sometimes establish gains or rule out a target improvement. However, broader evidence is needed to assess how often the intervals are informative and how much validation compute the method saves.

Questions for authors
  1. How sensitive are the accuracy and gain bounds to violations of conditional independence between repeated calls? Can the authors quantify robustness to weaker, practically plausible forms of dependence?
  2. Under the same total validation-call budget, how does the proposed two-call procedure compare with directly evaluating voting on fewer questions and with existing majority-vote bounds?
3 comments

Thank you for your thoughtful review. We appreciate your detailed questions.

We have uploaded a revised version: changed text is in blue, new appendix sections have blue titles, and red margin notes name the review point each change addresses.

W1 (independent calls), Q1

Section 3, Eq. (1), assumes conditionally i.i.d. Bernoulli(q) correctness calls for a fixed question and inference protocol. The protocol sends separate requests without previous outputs/context and uses per-condition/item/repeat seeds. Across all ten call pairs in each of 18 conditions, the maximum within-condition ranges are 1.09 points for the mean and 1.56 for joint correctness. These lie below the 95% quantiles, 1.34 and 1.83 points (p=0.22 and 0.20), of the same maxima when call order is permuted within items, and Cochran's Q detects no difference in per-call accuracy after Bonferroni correction over the 18 conditions (smallest p=0.028). Pair stability is consistent with exchangeable calls; conditional independence is a stronger property, so we add a sensitivity analysis.

Suppose each call retains conditional marginal success probability q and, after every positive-probability history, its success probability differs from q by at most epsilon. The pair moment then differs from E[Q²] by at most epsilon. Sequential coupling bounds the error of any K-call event by min{1,(K−1)epsilon}: couple the first call exactly and each later draw with mismatch probability at most epsilon, then use a union bound.

We enlarge the moment confidence region's second coordinate by ±epsilon, intersect with the feasible latent-moment cone, project the sharp bounds and enlarge the event interval by (K−1)epsilon. The single-call baseline is unchanged. At the confidence levels used in the paper, lower three-vote gains (points) are:

epsilonQ04N05
00.6970.719
0.00010.6660.688
0.00050.5430.564
0.0010.3900.410

The Q04/N05 half-point decisions remain certified up to epsilon=0.0005, and at epsilon=0.001 the lower gains fall below the target. Epsilon is a user-chosen sensitivity parameter; confidence-region coverage assumes iid items. The revised version adds the pair-stability check and this sensitivity analysis (Appendix I.6).

W2 (binary majority)

Section 4’s two-sided interval is for binary majority under Section 3. For multiclass/open-ended tasks it bounds strict-majority correctness, so the method provides a lower bound on plurality accuracy. GSM8K reports both; two-sided plurality bounds need wrong-answer allocation beyond two correctness moments.

W3 (informativeness of the bounds), Q2

On how often the intervals are informative: for the half-point target, the bounds certify gains for Q04 and N05 within each protocol and exclude that gain for N04 at three and five calls. In the other direct-prompt settings, every recorded moment pair is also attained by a population with equal accuracy at every budget, so the sign of the gain there is fixed by higher moments from the recorded calls (reply to wBTm, Q2).

On validation compute, the two designs differ in how cost grows with the budget. Covering budgets up to K by direct repeats takes K calls on each of N examples. Two calls per example estimate, for 2N calls, the exact range of voting accuracy compatible with the two moments at every odd budget and at the infinite-vote endpoint (Theorems 4.1 and 4.3), and certify each budget whose range lies on one side of the target, as for N04. With N=8192, budgets up to nine calls take 73,728 calls by direct repeats and 16,384 by pairs. For a single budget fixed in advance, the case direct repeats are built for, they resolve the half-point decision at least as often at equal cost in every setting: at 8190 calls, pairs resolve N04 in 87.2%/83.7% of replications at three/five votes and Q05 in 24.3%/18.8%, and five-call evaluation resolves both in at least 99.8% (full comparison in the reply to ERVG).

On existing majority-vote bounds: our lower endpoint is always at least a C-bound-type bound. For odd K, define the correctness margin M_K=K^−1 sum_{j=1}^K(2B_j−1). Under the model in Section 3, E[MK]=2μ−1,E[MK2]={1+(K−1)(4ν−4μ+1)}/K.E[M_K]=2\mu-1,\qquad E[M_K^2]=\lbrace 1+(K-1)(4\nu-4\mu+1)\rbrace /K. For mu>1/2, Cantelli gives the C-bound-type bound Pr⁡(MK>0)≥(2μ−1)2/E[MK2];\Pr(M_K>0)\ge(2\mu-1)^2/E[M_K^2]; for mu≤1/2 this argument gives zero. Our sharp lower endpoint minimizes majority accuracy over latent laws with these moments, so it is at least this bound pointwise and after minimization over the same confidence region. PAC-Bayes learning guarantees rest on different training assumptions, so the matched-information comparison is with the C-bound. The revised version adds the equal-cost comparison (Appendix I.1) and this C-bound comparison (Proposition I.1).

Thank you for the positive assessment; we hope these clarifications strengthen your support for acceptance.

I would like to thank the authors for the clarifications. I maintain my positive score. the concerns I raised are hard to solve, but I appreciate the explanations provided.

Thank you for your follow-up and for your continued positive assessment. We would be happy to discuss any further questions.

Comments on the paper

1 comment

Thank you for your detailed review. We appreciate your helpful suggestions.

We have uploaded a revised version: changed text is in blue, new appendix sections have blue titles, and red margin notes name the review point each change addresses.

Q1 (two-call bound at equal cost)

The cost of the two-call bound stays at two calls per example whatever range of budgets it covers. To compare or choose among budgets up to K, direct repeats take K calls on each of N examples, NK calls in all, and identify accuracy at budgets up to K; the infinite-vote endpoint would require calls per example to grow along with N. Two labeled calls per example require only N to grow: 2N calls estimate the exact envelope at every odd budget and at the infinite-vote endpoint (Theorems 4.1 and 4.3), and settle every budget whose envelope lies on one side of the target, as N04's upper bounds do at three and five calls. With N=8192, as in our direct-prompt settings, covering budgets up to nine calls takes 9N=73,728 calls by direct repeats and 2N=16,384 by pairs.

The equal-cost comparison has a first-order criterion (Appendix I.1). For budget K and target τ, let m_P be the margin by which the population envelope clears τ and m_D≥m_P the margin of the gain itself, with per-example standard deviations s_P, s_D and critical values c_P, c_D. The costs at which the two designs reach their thresholds are

CP=2(cPsP/mP)2,CD=K(cDsD/mD)2,C_P=2(c_Ps_P/m_P)^2,\qquad C_D=K(c_Ds_D/m_D)^2,

so pairs are the better option when C_P<C_D: when the envelope is tight relative to the gain, or when K is large, since C_P does not grow with K. On Q04 the two-call lower bound lies far below the direct interval, and direct repeats resolve more often. On the complete Q04 records, 3072 calls give 1536 paired examples or 1024 triples. Over 1000 resamples with uniform response pairs and a 0.5-point target, pairs resolve the decision in 8.9% of replications and triples in 92.8% (Monte Carlo SEs 0.90/0.82 points); N05 gives 66.3%/100%. The two designs therefore work together: the paired calls give the envelope over all odd budgets at a fixed cost of 2N calls, and direct repeats then verify the budget chosen from it. The revised version adds this comparison and the cost across budgets (Section 6.1; Appendix I.1).

Q2 (model choice and gain sign)

The bounds in the paper certify call budgets within a fixed protocol: Q04/N05 exceed the half-point target at three calls. In the reported experiments the model and protocol choice is the same with and without the bounds: direct prompting at 84.28% exceeds randomized N05 after three votes at 81.15%, and the N09/N06 rank reversal is measured from the repeat records.

The bounds address decisions against a target gain. With simultaneous 95% confidence over the 18 settings, N04's exact upper bounds rule out a gain above 0.5 points at three and five calls (0.452 and 0.465 points). In the other direct-prompt settings, each recorded moment pair (mu,nu) is also attained by a population with equal accuracy at every budget: the three weights

1−3μ+2ν,4(μ−ν),2ν−μ1-3\mu+2\nu,\quad 4(\mu-\nu),\quad 2\nu-\mu

are nonnegative and sum to one, and placing them at q=0, 1/2, 1 reproduces both moments with accuracy mu at every odd budget. By Theorem 4.1 these envelopes are exact, so the sign of the gain in these settings is fixed by higher moments, which the five recorded calls supply (Table 7).

Q3 (call pairs and seeds)

Other call pairs give the same moments within sampling variation. Across all ten pairs in each of 18 five-call conditions, the largest within-condition ranges are 1.09 points for mu and 1.56 for nu, below the 95% quantiles 1.34 and 1.83 points (p=0.22 and 0.20) obtained when call order is permuted within items. Cochran's Q detects no difference in per-call accuracy after Bonferroni correction (smallest p=0.028 over 18 conditions). Each call uses a condition/item/repeat seed and a fresh prompt without previous context. Conditional independence is a stronger property than pair stability, so we add a sensitivity check.

It assumes each call retains marginal success probability q and every next-call success probability conditional on the previous history differs from q by at most epsilon. The resulting pair-moment error is at most epsilon, and a sequential coupling bounds the K-call event error by (K−1)epsilon. Enlarging the moment region and the event interval accordingly gives Q04/N05 lower three-vote gains of 0.543/0.564 percentage points at epsilon=0.0005, compared with 0.697/0.719 at epsilon=0 and 0.390/0.410 at epsilon=0.001. Epsilon is a user-chosen sensitivity parameter; under this model the half-point conclusion holds for dependence up to epsilon=0.0005. The revised version adds the pair-stability check and this sensitivity analysis (Appendix I.6).

Thank you for the positive assessment; we hope these clarifications strengthen your support for acceptance.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.