acceptodds
Under review as a conference paper at ICLR 2027

When Can Voting Help, Hurt, or Change Course? Exact Structure of Binary Test-Time Aggregation

Abstract

Increasing a voting budget can improve or reduce population accuracy, and an initial gain or loss need not persist. We give a complete structural classification of these curves for binary unweighted majority under infinitely exchangeable correctness indicators, with an arbitrary latent success-probability law . The classification is encoded by the signed voting signature The complete odd-budget curve and this signature determine each other: the initial accuracy gives its total signed mass, and successive budget increments give its higher moments. Reflection-symmetric differences between latent laws are exactly the changes invisible to voting. A weighted total-variation constraint characterizes every attainable signature, and a minimum-mass allocation to the two reflected branches, completed by symmetric probability mass, gives every population producing its curve. Consequently, the full curve identifies the latent population precisely when no symmetric mass remains to redistribute.

Primary area:
learning theory
Keywords:
majority voting, test-time scaling, exchangeability, identifiability, moment problems

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 4 reviews, above 85% of the others.
Reviewer_dA6vOpenReview ↗
Rating
3(+1)
Confidence
1
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

The paper aims to characterize how aggregating (by unweighted majority vote) multiple predictions at test time can affect the results of the votes. The characterization is done through a mathematical classification of the accuracy curves that can arise as the number of votes increases. The paper provides a rigorous mathematical framework for it, and derives a voting signature formula that fully determines the curves studied.

Critical strengths

The mathematical framework developed for the study at hand looks very well-thought and very solid.

Critical weaknesses

The paper is only theoretical and makes little effort to explain how useful it could be in practical scenarios. In that vein, the title is a bit misleading, as it teases the reader with a practical question that is never really answered. Hence, although the math looks good, the motivation of the paper and its potential applications are underdeveloped and may prevent it from reaching a wide audience, as the contributions and take-home messages are unclear.

Questions for authors

Although the paper is exclusively theoretical, and likely good in that regard, I believe it would be much more impactful if it was clarified in various ways and if it was connected to practical applications and examples for the general machine learning / data science community. Can you please clarify, for a less-specialized audience:

  • The goal of the paper: what problem is targeted by the paper?
  • The motivation of the paper: why exactly is the paper important and needed?
  • The contributions of the paper: what exactly is novel and is provided in the paper to achieve its goal?
  • The practical uses of the paper: how exactly can/should the paper be used in practice?
5 comments

Thank you for your careful reading. We appreciate your concrete 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 (only theoretical), Q1 (goal)

The goal is to answer the title question exactly for a fixed predictor on binary questions under unweighted majority: how accuracy can change as votes are added, and what such a curve reveals about the population of questions (Sections 3–5). Figure 1 shows five exact curves that all start at 75% one-call accuracy and then stay constant, fall quickly, dip and later surpass the starting value, rise and then fall, or rise slowly. The revised introduction states the goal, motivation, contributions and practical use in these plain terms.

Q2 (motivation)

More votes do not always help: Chen et al. observed GPT-3.5 majority accuracy on MMLU Physics first rising and then falling with more calls, and Khan et al. a slight decline as GPT-4-Turbo judge votes increased (revised introduction). The paper characterizes exactly when a curve rises, falls or reverses (Section 5). One-call accuracy and small-budget gains do not settle whether more votes will help, and even the whole curve may not identify the population: an equal mixture of questions with q=0.8 and q=0.2 has the same constant 50% curve as questions that all have q=0.5. The signature identifies exactly which differences voting observes and which it discards, and so what a scaling experiment can reveal.

Q3 (contributions)

There are four results. We say exactly which differences between populations of questions voting can never detect: those symmetric under exchanging q and 1−q (Theorem 3.2). We describe every accuracy-versus-budget curve that can occur and every population producing it (Proposition 4.2), and give the exact condition under which only one population produces a curve (Corollary 4.4). Finally, we show that J repeated calls per question determine the accuracies at budgets up to J and, in general, no further (Section 6).

Q4 (practical uses)

A user with J labeled calls per question can apply two results without estimating the signature. Section 6 shows that these calls determine the accuracy at every odd budget up to J and, in general, at no larger budget, so claims about larger budgets or limiting accuracy require more calls per question or an assumption on the population near q=1/2. Within the identified range, the accuracy of an m-vote majority (odd m≤J) is estimated by the average majority correctness over m-call subsets, and a larger budget is adopted when a simultaneous lower confidence bound on its gain, from paired per-question differences, exceeds the cost of the extra calls (Appendix G of the revised version). The signature fixes which gains and curve shapes can occur at budgets beyond the data.

Repeated calls from three LLMs on QNLI and QQP illustrate the rule. For QNLI with Llama-3.1-8B at temperature 1, three calls gain 1.388 points over one (standard error 0.100), whereas for Qwen2.5-7B the gain is 0.077 points (standard error 0.040); the reply to Reviewer G3nk gives all 18 conditions.

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

Reviewer_dA6vOpenReview ↗

What was removed, and why not using page 10?

I thank the authors for their clear answers to my questions and to other reviewers' questions. I also appreciate the changes made in the paper in that regard, although they are quite minimalistic (maybe due to lack of space?).

I simply would like to draw the attention of the authors that the revised version of the paper, even in the rebuttal phase, can contain 10 pages. Given that the previous manuscript was already at 9 pages, and the current revision is still at 9, I am wondering which parts disappeared, and why?

Stated differently, I strongly encourage authors to keep their initial content if it was relevant, and to use fully the extra page allowed so that the clarifications asked by the reviewers are completely handled, and not too compressed (as it is a bit the case now).

I do not think that this comment will be difficult to address, and I am willing to increase my score once done, because I feel that the answers provided in the rebuttal are satisfying but do not yet fully transfer to the manuscript.

Thank you for the prompt and positive follow-up.

The revision now uses all ten pages. All theorems, propositions, equations and figures of the submission remain in the main text with their original numbers, and the few original sentences shortened in the first revision are restored (introduction; Sections 2, 4 and 5). The clarifications are now in the main text:

  • Table 1 (Section 3) collects the notation.
  • Section 5 explains the curves of Figure 1, what the infinite-reversal example means, and the source of the total-variation bound.
  • Section 6 adds the budget comparison from repeated calls: subset estimator, paired gain, simultaneous lower bound and adoption rule.
  • Appendix G adds the covariance, the finite-sample bound and an illustration on the repeated-call records (G.1).

New text is in blue with red margin notes; restored original sentences are in black. We will keep the manuscript up to date as the discussion continues.

We would be grateful if you would consider raising your score.

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

This paper provides a complete mathematical and structural characterization of population-level accuracy curves Vn(Π)V_n(\Pi) under unweighted binary majority voting (2n+12n+1 calls) as the test-time voting budget nn grows, assuming infinitely exchangeable correctness indicators (which, by de Finetti's theorem, correspond to item-level success probabilities Q∼ΠQ \sim \Pi on [0,1][0, 1]). The core insight is that consecutive odd-budget accuracy increments satisfy Vn+1(Π)−Vn(Π)=(2n+1n+1)∫[0,1/4]rn+1ωΠ(dr),V_{n+1}(\Pi) - V_n(\Pi) = \binom{2n+1}{n+1} \int_{[0, 1/4]} r^{n+1} \omega_\Pi(\mathrm{d}r), where r=q(1−q)r = q(1-q) measures an item's proximity to the chance threshold q=1/2q=1/2, and ωΠ\omega_\Pi is the signed voting signature—the pushforward of the signed measure (2q−1)Π(dq)(2q-1)\Pi(\mathrm{d}q) onto [0,1/4][0, 1/4]. Using this representation, the authors establish:

  1. The full odd-budget curve and the signature ωΠ\omega_\Pi uniquely determine each other via a Hausdorff-type moment relation on [0,1/4][0, 1/4]. Two latent distributions yield the exact same voting curve if and only if their difference is reflection-symmetric around q=1/2q=1/2. All realizable signatures are characterized via a singular weighted total-variation constraint c(ωΠ)=∫[0,1/4)(1−4r)−1/2∣ωΠ∣(dr)≤1c(\omega_\Pi) = \int_{[0, 1/4)} (1-4r)^{-1/2} |\omega_\Pi|(\mathrm{d}r) \le 1, proving that a voting curve uniquely identifies the underlying population Π\Pi if and only if c(ωΠ)=1c(\omega_\Pi) = 1.
  2. The signature coordinates characterize when voting curves are monotone and discretely concave/convex, how competing opposite signs at different scales rr cause non-monotonic reversals (including an explicit construction with infinitely many direction changes), and why every binary majority curve nonetheless has total variation bounded by 1/21/2.
  3. From JJ repeated calls per item across NN items, the grouped binomial count law point-identifies signature moments sks_k (and thus odd-budget accuracies) up to degree 2k+1≤J2k+1 \le J, while higher moments and the infinite-budget limit V∞(Π)V_\infty(\Pi) remain unidentifiable without further assumptions. The paper derives sharp convergence rates to V∞(Π)V_\infty(\Pi) under signature support gaps (exponential) and local margin conditions Π(∣Q−1/2∣≤t)≤Ctκ\Pi(|Q - 1/2| \le t) \le C t^\kappa (power-law rate M−κ/2M^{-\kappa/2}), and concludes by showing via a counterexample why a scalar correctness probability qq cannot parameterize KK-choice plurality voting curves for K≥3K \ge 3. Validation is theoretical, supported by exact analytical examples (Figure 1, Example 4.3, Example 5.2) and self-contained proofs in the appendices.
Critical strengths
  1. While prior work (e.g., Chen et al., 2024) noted that heterogeneous item difficulties can cause non-monotonic majority-vote scaling curves and derived the forward increment identity (Equation 1), this paper solves the inverse and realizability problems completely. By recognizing that Vn+1−VnV_{n+1} - V_n is proportional to the (n+1)(n+1)-th moment of the signed pushforward measure ωΠ\omega_\Pi under the folding map r=q(1−q)r = q(1-q), the authors reduce the analysis of binary voting curves to classical measure theory (Stone–Weierstrass moment uniqueness and Jordan decomposition on [0,1/4][0, 1/4]). This yields a necessary-and-sufficient characterization of attainable voting curves, invisible population redistributions (reflection-symmetric slack), unique population identifiability (c(ωΠ)=1c(\omega_\Pi) = 1), and the universal 1/21/2 total-variation bound.
  2. Sections 6 and 7 connect idealized infinite-budget curves with finite-evaluation constraints. Relating factorial moments of JJ-repeat binomial counts to the identifiable prefix of the voting curve (2k+1≤J2k+1 \le J) and proving uniform non-identifiability of higher moments and the asymptotic endpoint V∞(Π)V_\infty(\Pi) (even for population NPMLE) provides a clear boundary for test-time scaling evaluations. Furthermore, the distinction between convergence rates governed by signature support gaps (which allow symmetric mass near 1/21/2 without slowing convergence) versus population margin conditions near 1/21/2 (with matching Θ(M−κ/2)\Theta(M^{-\kappa/2}) upper and lower bounds) is complete and informative.
Critical weaknesses
  1. The exact signature theory relies on the one-dimensional nature of binary voting, where every incorrect vote lands on the single alternative option. As shown in Section 7.1 (Theorem 7.4), many practical LLM test-time scaling benchmarks (e.g., MMLU multiple-choice or open-ended generation with self-consistency) involve K≥3K \ge 3 options or semantic equivalence classes where error dispersion versus concentration across wrong answers alters both finite-budget plurality accuracy and the infinite-budget limit. Because the paper contains no empirical experiments on real LLM repeated-sampling traces (e.g., estimating s^k\widehat{s}_k or testing the framework on actual binary verification/adjudication tasks), the practical applicability of the estimators and bounds to real-world test-time compute scaling remains undemonstrated.
  2. Once the known binomial increment identity Pn+1(q)−Pn(q)=(2n+1n+1){q(1−q)}n+1(2q−1)P_{n+1}(q) - P_n(q) = \binom{2n+1}{n+1} \{q(1-q)\}^{n+1}(2q-1) (Chen et al., 2024, Lemma 6) is written down, the change of variables r=q(1−q)r = q(1-q) directly turns the increments into the power moments of a signed measure on [0,1/4][0, 1/4]. From that point, the main structural results in Sections 3 and 4 follow from standard applications of the Hausdorff moment problem / Stone–Weierstrass theorem and the Jordan decomposition of signed measures. While the exposition is clear and the resulting constructions (such as Example 5.2 and the 1/21/2 total variation bound) are neat, the underlying mathematical techniques are elementary.
Questions for authors
  1. In Section 6 (Theorem 6.1) and Appendix E (Propositions E.1–E.2), you derive unbiased estimators s^k\hat{s}_k for the signature moments and plug-in estimators ω^N,J\hat{\omega}_{N,J} from JJ repeats on NN items. However, there is no empirical illustration on actual LLM datasets (such as the binary consultancy task of Khan et al., 2024, or binary reward-model/verifier tasks). When JJ is moderate, unbiased factorial-moment estimators s^k\hat{s}_k involve alternating binomial sums (Equation 9) and amplification factors (2k−1k)−1\binom{2k-1}{k}^{-1} in Proposition E.2. Have you evaluated the finite-sample variance of s^k\hat{s}_k or the tightness of the bounds in Proposition E.2 on real LLM binary verification benchmarks?
  2. In Section 7.1, you show that for K≥3K \ge 3, a scalar correctness probability p0=qp_0 = q cannot determine the plurality curve unless wrong answers are symmetric. Could a low-dimensional effective signature (for instance, tracking p0p_0 and the maximum competing wrong probability max⁡j≥1pj\max_{j \ge 1} p_j, or the effective number of competing wrong options) provide partial-identification bounds or approximate curve characterizations for multiple-choice benchmarks?
3 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.

W2

Theorem 3.2 uses the change of variables r=q(1−q) and moment uniqueness to show that the curve and the signature determine each other. The classification adds two steps: Proposition 4.2 gives the exact probability-mass condition for a signed measure to be a population's signature and constructs every population realizing it, and Corollary 4.4 gives the necessary and sufficient condition for a curve to determine its population. The condition is μ({1/4})=0\mu(\lbrace1/4\rbrace)=0 and ∫[0,1/4)(1−4r)−1/2∣μ∣(dr)≤1\int_{[0,1/4)}(1-4r)^{-1/2}|\mu|(dr)\le1, and the realizing laws are exactly a minimal law of that mass plus any reflection-symmetric measure of the remaining mass.

W1, Q1

The results are theorems about binary majority voting itself: they hold for every predictor queried repeatedly with fresh randomness, on every binary task, including verification and judging, and the estimators of Section 6 apply to any such repeated-call record. We illustrate them on two binary verification tasks, whether a sentence answers a question (QNLI) and whether two questions are duplicates (QQP), with Llama-3.1-8B, Phi-4-mini and Qwen2.5-7B at temperatures 0.2, 1 and 2, each with N=8192 items and J=5 calls. The new Appendix G gives the estimator and SEs used below.

For an item with c correct calls, the average majority score over m-call subsets (odd m≤J) and the signature statistic are

z_{J,k}(c)=\frac{h_{J,2k+1}(c)-h_{J,2k-1}(c)}{\binom{2k-1}{k}}.$$ The statistic z_{J,k} equals the factorial statistic of Theorem 6.1 at every c, by uniqueness of degree-J Bernstein coefficients, and each h_{J,m} is a sum of positive terms, in place of the alternating sums in Eq. (9). We average z over items, estimate its covariance by dividing the item-level sample covariance by N, and compute gain SEs from paired item differences. The 3−1 and 5−3 gains equal 100 s1 and 300 s2, so the table reports both signature moments with their SEs; across the 18 conditions, SE(s1) lies between 0.0002 and 0.0014 and SE(s2) between 0.00007 and 0.0007. Below, N/Q are QNLI/QQP and L/P/W are Llama/Phi/Qwen; gains and SEs are percentage points. |Task/model/T|3−1 gain(SE)|5−3 gain(SE)| |---|---:|---:| |N/L/0.2|+0.111(0.049)|-0.033(0.060)| |N/L/1.0|+1.388(0.100)|+0.641(0.123)| |N/L/2.0|+1.620(0.106)|+0.846(0.162)| |N/P/0.2|+0.112(0.048)|-0.037(0.059)| |N/P/1.0|+0.939(0.087)|+0.275(0.105)| |N/P/2.0|+1.338(0.093)|+0.637(0.133)| |N/W/0.2|+0.011(0.021)|-0.040(0.022)| |N/W/1.0|+0.077(0.040)|+0.092(0.052)| |N/W/2.0|+0.055(0.045)|+0.084(0.064)| |Q/L/0.2|-0.042(0.065)|-0.022(0.072)| |Q/L/1.0|+1.470(0.132)|+0.447(0.166)| |Q/L/2.0|+1.730(0.140)|+0.839(0.209)| |Q/P/0.2|-0.098(0.038)|+0.000(0.041)| |Q/P/1.0|+0.026(0.076)|-0.048(0.092)| |Q/P/2.0|+0.117(0.085)|+0.205(0.117)| |Q/W/0.2|+0.027(0.024)|-0.007(0.026)| |Q/W/1.0|-0.004(0.047)|-0.011(0.060)| |Q/W/2.0|+0.033(0.050)|+0.004(0.075)| The Llama one-to-three gains at T=1 and T=2 are 1.388–1.730 points (SEs at most 0.140), whereas at T=0.2 every gain is at most 0.112 points in absolute value. On tightness, Proposition E.2 is a deterministic continuity bound: it limits how far a signature functional can differ between populations whose curves agree to within epsilon. For phi(r)=r^k its approximation term is zero and its observation-error term is 2 epsilon/binom(2k−1,k), so a curve known to within epsilon=0.001 fixes s1 to within 0.002. It concerns ambiguity among compatible populations, whereas the SEs concern sampling error. Q2 The summaries you propose give the three-call accuracy exactly and two-sided bounds at every budget. On the multiclass part of W1, the abstract and Section 3 specify binary majority, and Theorem 7.4 shows why q alone cannot characterize plurality. For iid categorical calls with K labels, correct probability q=p0, largest competitor u=max_{j≥1}p_j, H=sum_{j≥1}p_j² and uniform tie-breaking, $$A_{3,K}(p)=q^3+3q^2(1-q)+q\lbrace (1-q)^2-H\rbrace .$$ The last term is a three-way tie with two distinct wrong labels. At three calls, q and the effective competitor count (1−q)²/H suffice when q<1. For any m, let S_m sum m iid variables taking 1, −1 and 0 with probabilities q, u and 1−q−u. Then $$\max\lbrace 0,1-(K-1)\Pr(S_m\le0)\rbrace \le A_{m,K}(p)\le\Pr(S_m\ge0).$$ The upper bound compares with the largest competitor, and the lower bound is a union bound over competitors; Pr(Bin(m,q)>m/2) is another lower bound. The endpoint is 1 if q>u and 0 if q<u, and at q=u it depends on the number of maximal labels (Proposition F.1). Thank you for the positive assessment; we hope these clarifications strengthen your support for acceptance.

Thank you for the clarification and I decide to maintain my score.

Thank you for your follow-up and for your continued support of the paper.

Reviewer_X1GsOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

A common setup revolves around aggregating language model responses to various questions via majority voting. It has been observed in the existing literature that increasing the number of language model calls does not necessarily increase/decrease/maintain accuracy. Building on this phenomenon, this paper characterizes binary majority voting accuracy curves. This characterization relies on deriving a “signed voting signature” for each curve and proving there is a one-to-one correspondence between curves and these signed signatures. The authors then determine the set of “admissible” signatures; that is, signatures that can be produced by some probability law. Additionally, the authors characterize when different laws map to the same signature. Finally, the authors provide conditions on the signature for when the curve is monotone and an example where there is a curve that changes directions infinitely many times.

Critical strengths
  • The signed voting signature provides a convenient, approachable quantity for understanding and analyzing voting accuracy curves. The paper also provides interesting insights into when two different laws yield the same curve. There are also some nice sufficient conditions on the signature for when the curve is monotone, which is a desirable feature.
Critical weaknesses
  • I found the paper to be lacking in motivation as to why this characterization is useful. In particular, it is not clear to me how this characterization helps practically to inform the number of language model calls that should be used to optimize accuracy.

  • I believe the paper would need a solid rewrite before acceptance. For one, the introduction is very short and again does not contain much motivation for the problem. The paper would also benefit from a dedicated preliminaries section. I also think a more detailed description of how this paper relates to Chen et al. (2024), would be useful for the reader since this seems to be the closest related work.

Questions for authors
  • How would one use this characterization to practically inform the budget selection in an experiment?

  • Can you provide a more detailed explanation of how this work compares to that of Chen et al (2024)?

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 (motivation), Q1 (budget selection)

The characterization tells an experimenter which budget comparisons an evaluation can settle. J labeled calls per item identify the accuracy at every odd budget up to J, because the gain from 2k−1 to 2k+1 calls is binom(2k−1,k) times an identified signature moment; gains at larger budgets are not all identified (Section 6).

To choose a budget, one fixes in advance the candidate odd budgets up to J and a worthwhile gain tau, or a cost lambda per extra call. For an item with c correct calls out of J, the average majority score over m-call subsets is

hJ,m(c)=∑t>m/2(ct)(J−cm−t)/(Jm).h_{J,m}(c)=\sum_{t>m/2}\binom ct\binom{J-c}{m-t}/\binom Jm.

With C_i the count for item i, the mean of h_{J,b}(C_i)−h_{J,a}(C_i) over items estimates the gain from budget a to budget b, with a standard error from the paired item differences. Under iid items, a Hoeffding bound gives lower bounds that hold simultaneously for the prespecified comparisons. A larger budget is adopted when this bound exceeds tau, or lambda(b−a), and is then evaluated on held-out items.

The revised Appendix G states the estimator, its standard errors and this rule. We applied it to repeated calls from three LLMs on QNLI and QQP, 18 conditions with N=8192 questions and J=5 calls each; the reply to Reviewer G3nk gives all of them. For QNLI with Llama-3.1-8B at temperature 1, three calls gain 1.388 points over one (SE 0.100), whereas for Qwen2.5-7B at the same temperature the gain is 0.077 points (SE 0.040). With 95% lower confidence bounds of 1.19 points for Llama and about zero for Qwen, the rule buys the two extra calls for the first model whenever they are worth less than 1.19 points, and keeps one call for the second.

W2 (rewrite, preliminaries, Chen et al.)

The paper asks what whole voting curves and finite budgets identify, because one-call accuracy and early gains do not determine the later direction, and even a whole curve can hide population differences: equal masses at q=0.8 and q=0.2 give the same constant 50% curve as q=0.5.

In Section 3, an item is a labeled binary question, and q is the fixed predictor's success probability on it. Q~Pi describes its variation across items. Conditional on Q the correctness bits are iid Bernoulli(Q), and averaging the binomial majority probability gives V_n. The folding variable q(1−q) groups each probability with its reflection, and the signed weight 2q−1 records their imbalance.

The revised introduction adds this motivation, defines items, q and Pi at first use, and gives the q=0.8/0.2 example; Section 3 provides the formal setup.

Q2 (comparison with Chen et al.)

Chen et al. (2024) give the forward identity and analyze a two-type mixture: its monotone and reversing regimes and its accuracy-maximizing number of calls. Both works start from the binomial law of the majority on one question. Our results use nothing beyond it and give a complete model of binary majority-vote accuracy curves for every latent law on [0,1] (Section 3). The signed signature is an exact coordinate system for the curve: the curve and the signature determine each other (Theorem 3.2), so every question about a curve becomes a question about one signed measure on [0,1/4]. In these coordinates, we classify every attainable curve together with every population that produces it (Proposition 4.2), and give the exact condition for a curve to identify its population (Corollary 4.4). Section 5 characterizes monotone and reversing shapes, including infinitely many reversals, and bounds every curve's total variation by 1/2. Section 6 determines what J repeated calls per item identify; Section 7 gives the limit and its convergence rates. A two-type mixture corresponds to a signature with at most two atoms, so the regimes of Chen et al. are one case of this classification. The revised related-work section gives this comparison point by point.

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

Thank you for your detailed response. I have raised my score to 3.

Thank you for reading our response and for raising your score. We would be glad to answer any further questions during the discussion period.

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

Majority voting is often expected to reduce prediction errors. However, previous work has both observed and theoretically analyzed that accuracy need not increase monotonically with the number of voters. This paper pushes forward this understanding by providing an exact inverse characterization for binary, unweighted majority voting. It introduces a signed voting signature that captures the imbalance in population mass, and proves that this signature contains the information in the accuracy-versus-budget curve. The paper further characterizes which signatures are realizable, as well as the different populations producing the same curve. These results clarify what voting performance can and cannot reveal about heterogeneity across items.

Critical strengths

As I understand it, the fact that majority-vote accuracy need not increase monotonically with the number of samples of voters is already known, as the authors also acknowledged. For me, the main strength is the inverse characterization. Even knowing the accuracy at every voting budget generally does not identify the latent population. Theorem 3.2 characterizes exactly which population differences are visible or invisible to the full curve, Proposition 4.2 gives the compatible populations, and Corollary 4.4 establishes when the population is uniquely identifiable. The characterization is fairly complete, with the necessary and sufficient conditions. It provides a more complete picture beyond what was known before: simply recognizing cancellation or nonmonotonicity.

Critical weaknesses

For binomial-tail formula, I believe there are also other earlier literatures using that, see e.g., Lacasse et al. 2010 and Zantedeschi et al. 2021. You might want to consider adding them.

  • Lacasse et al. (2010), Learning with Randomized Majority Votes
  • Zantedeschi et al. (2021), Learning Stochastic Majority Votes by Minimizing a PAC-Bayes Generalization Bound

Notation definition: The overall organization is pretty ok. But I personally find the initial introduction of “item,” Q∼ΠQ\sim \Pi, and more, in Introduction is quite compressed and abstract. Similar for some notions and definitions in Section 3. It would be helpful to state at first using some small concrete examples when defining the notions. Making these roles explicit at first use would make the subsequent arguments easier to follow. More connecting motivation for the definitions would also help.

Questions for authors
  1. Example 5.2 shows that the voting curve can change direction infinitely often, which I find surprising and interesting. Could the authors clarify the significance of this construction for understanding or evaluating test-time voting? It seems to be a pretty specific construction to me.
  2. Section 7.1 shows why the scalar success probability is insufficient for general multiclass plurality. Does any part of the inverse characterization in Sections 3 & 4 carry over, or does establishing such a characterization remain open?
3 comments

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.

W1 (earlier literature)

We now cite Lacasse et al. (2010) and Zantedeschi et al. (2021) in the related-work section. They study randomized voting and generalization; we also start from the binomial tail, and Section 3 credits Chen et al. for the forward identity. Our contribution is the inverse classification for a fixed predictor: the attainable budget curves, the compatible populations and exact uniqueness (Sections 3–4).

W2 (notation)

An item is a labeled binary question, q is the success probability of the fixed predictor and protocol on it, and Pi is the distribution of q across questions. Section 3 states this formally: the correctness bits of repeated calls are infinitely exchangeable, so by de Finetti's theorem they are iid Bernoulli(Q) given Q~Pi. A small example shows the roles of these objects. If half the questions have q=0.8 and half have q=0.2, accuracy is at chance at every budget, exactly as with q=0.5 everywhere, because reflected contributions cancel; the signed signature records the imbalance that remains. The revised introduction states this definition and example in two sentences where Pi first appears.

Q1

Example 5.2 shows the limits of extrapolating from finitely many budgets: eventual monotonicity can fail because imbalances ever closer to chance can dominate in turn with alternating signs. A trend observed over finitely many budgets therefore need not persist. Section 5 adds that with finitely many nonzero scales the largest eventually fixes the direction, and that every curve has total variation at most 1/2. A curve can therefore reverse infinitely often and still converge.

Q2

Appendix F extends the representation to multiclass voting as averages of voting polynomials. Binary folding and reflection do not determine how errors are allocated among wrong labels, so the multiclass results are stated in q and the largest wrong-label probability u. With q=p0, the endpoint is 1 for q>u and 0 for q<u, and at equality the number of tied maximal labels matters (Proposition F.1).

In addition, the three-call accuracy has a closed form in q and the sum of squared wrong-label probabilities, and at every budget the accuracy is bounded on both sides in terms of q, u and the number of labels. A multiclass inverse classification would characterize the multivariate polynomial information across all budgets and compatible populations; the binary case is the one in which it reduces to the signed signature.

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

Thanks for the clarification. I have decided to keep my score.

Thank you for your follow-up and for your continued positive assessment.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.