Mathematical Boundaries of Repeated Sampling Voting: How Two Calls Predict the Accuracy Curve of LLM Reasoning

This article presents a mathematical theoretical study on the repeated reasoning voting mechanism of large language models (LLMs). The core finding is that the accuracy boundaries under any majority voting budget can be predicted using only two independent calls, providing a new theoretical framework for computational optimization during testing.

Current LLM reasoning faces a dilemma: a single call may be unstable, while multiple sampling votes improve accuracy but increase computational costs. In practice, there is a lack of theoretical guidance to determine when to stop sampling and the expected benefits, leading to over-investment in resources or insufficient sampling. Additionally, the benefits of repeated sampling are uneven—some samples have inherent uncertainty, and simply increasing calls cannot resolve systematic errors.

The study establishes a concise mathematical framework and finds that the binary correctness of repeated reasoning can be characterized by two statistics:

1. First moment: Average accuracy of a single call, reflecting the model's overall mastery but failing to distinguish between stable and occasional correct cases;
2. Second moment: Correctness correlation, estimating the correlation coefficient between different calls for the same sample via two calls, revealing recoverable noise and stable systematic errors. Based on these two moments, the accuracy interval under any voting budget can be bounded, and the effect can be predicted without multiple actual calls.

The study addresses the infinite-dimensional moment problem using convex optimization duality theory, proving that the optimal boundary for any finite voting budget can be achieved by a discrete distribution containing only three atoms. This finding has three implications:

• Computational tractability: Simplified to a low-dimensional optimization problem;
• Accuracy guarantee: The boundary is exact rather than approximate;
• Interpretability: The three atoms correspond to the intuitive classification of easy, hard, and medium samples.

The study focuses on three-vote majority voting (the minimal useful budget) and finds that it has a concise closed-form solution, with the interval width strictly bounded within 1/8. It also proposes the 'Certified Improvement Criterion': when the two moments meet specific conditions, it can be proven that three-vote voting is necessarily better than single-vote. This provides practitioners with a decision-making tool: using two calls to determine whether increasing votes is worth it and the range of benefits.

Validated on the QNLI and QQP datasets, the actual observed three-vote and five-vote accuracies fall within the theoretically predicted intervals. When adjusting sampling temperature or using random model mixing, 'weaker' model configurations can sometimes surpass 'stronger' single-call configurations through voting, providing new ideas for model integration strategies.

Significance for engineering practitioners:

1. Cost-benefit analysis: Predict return on investment before increasing computation;
2. Dynamic budget allocation: Adjust sampling times based on sample difficulty;
3. Model selection guidance: Determine between a single strong model or a multi-medium model voting strategy. Macroscopically, this study promotes the shift of AI from experience-driven to theory-guided, and the two-moment framework may become a fundamental tool in the field.