acceptodds
Under review as a conference paper at ICLR 2027

Information-Rate Limits of Test-Time Reasoning

11 views

Abstract

Test-time reasoning systems spend compute by sampling candidate solutions and using a verifier to select among them, but more samples help only when the selection signal can identify the correct rollout. We formalize this coverage-precision gap by modeling verifier-guided inference as adaptive hypothesis testing through a feedback channel. The verifier's per-query information capacity yields an algorithm-independent lower bound on the number of queries needed for reliable recovery, with matching behavior in query-rich settings and collapse when the verifier is uninformative. Empirically, we hold rollouts fixed and vary only the selector across math, code, and multiple-choice benchmarks and two model families: oracle selectors expose latent gains, while practical selectors recover only part of them and corrupted verifiers collapse toward the single-sample baseline. A corrupted-oracle calibration places practical selectors—a trained process reward model, majority voting, an LLM-as-judge verifier, and log-probability ranking—on a common capacity-equivalent axis. Where information is directly measurable, the trained PRM and judge order consistently by realized information and captured gain, turning verifier quality into a measurable bottleneck for test-time compute.

Primary area:
learning theory
Keywords:
test-time compute, verifier capacity, inference-time scaling, process reward models, hypothesis testing, information theory

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_rmv5OpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper investigates the information-theoretic limits of verifier-guided test-time reasoning, focusing on how verifier quality affects the benefits of additional inference-time computation. The authors formulate inference as an adaptive hypothesis-testing problem and derive an algorithm-independent lower bound on verifier query complexity, along with a conditional achievability upper bound and an impossibility result for uninformative verifiers. Experiments across reasoning benchmarks show that stronger verifiers recover more accuracy gains from additional rollouts, while weaker verifiers lead to diminishing returns. The paper further introduces a capacity-equivalent metric to compare practical selection strategies.

Critical strengths
  1. The paper provides an information-theoretic perspective on verifier-guided test-time reasoning by formulating it as adaptive hypothesis testing. The derived lower bound is algorithm-independent, while the conditional upper bound helps characterize when the information-theoretic limit can be approached.
  2. The paper conducts comprehensive experiments spanning multiple reasoning benchmarks, model families, and verification strategies.
  3. Beyond establishing a lower bound, the paper examines both achievability under information-rich verification and impossibility when verifier feedback cannot distinguish hypotheses. These results help clarify the conditions under which additional verification queries can or cannot improve inference reliability.
Critical weaknesses
  1. While the framework provides an information-theoretic interpretation of verifier-guided test-time scaling, its practical implications remain limited. The main insights are largely consistent with existing intuition and empirical observations, and it is unclear whether the theoretical analysis offers substantially new insights beyond formalizing these known phenomena.

  2. Theorem 1 derives the query complexity lower bound using the worst-case verifier capacity CVC_V, which may substantially overestimate the information obtainable under practical query constraints. For example, a perfect equality verifier has CV=1C_V=1 bit, but under a uniform prior over MM hypotheses, a single equality query provides only h2(1/M)h_2(1/M) bits of information. With only singleton equality queries available, even an optimal policy requires Θ(M)\Theta(M) expected queries for exact recovery, whereas the proposed lower bound scales only as Ω(log⁡M)\Omega(\log M). Moreover, the matching upper bound relies on the C-rich assumption, which may not hold for practical Best-of-N verification. These gaps raise concerns about the tightness and practical relevance of the theoretical characterization.

  3. The theoretical analysis primarily focuses on verifier information capacity, while largely abstracting away the capabilities of the inference policy in generating and exploring candidate solutions. Although the lower bound applies to arbitrary adaptive policies, it does not explicitly account for the candidate distribution or the probability of generating a correct solution. In practical test-time scaling, performance depends not only on the verifier's ability to identify correct candidates but also on whether the inference policy can generate them in the first place. Consequently, policies with substantially different coverage and search capabilities may share the same theoretical bound, limiting its ability to characterize their actual scaling behavior.

Questions for authors

Please refer to the "Weakness" part.

2 comments
AuthorsOpenReview ↗

Response to Reviewer rmv5: Tightness vs. Singleton Equality Queries and Post-Prompt Generator Conditioning

We thank Reviewer rmv5 for the supportive assessment (3/3 across Presentation, Informativeness, and Soundness) and for raising two important theoretical questions regarding bound tightness and generator coverage.

  1. Tightness of Theorem 1 vs. singleton equality queries & CC-richness:
    • You are completely right: a singleton equality verifier Ot=1{Y^t=Y⋆}O_t=\mathbf{1}\lbrace\hat Y_t=Y^\star\rbrace over MM uniform hypotheses yields at most h2(1/M)=O((log⁡M)/M)h_2(1/M)=O((\log M)/M) bits per query and thus requires Ω(M)\Omega(M) expected queries, not log⁡M/CV\log M / C_V.
    • In Section 4 and Proposition 1 (Appendix A.2), we have sharpened this distinction explicitly: CC-rich achievability (E[τ∣x]≤(log⁡M+log⁡(1/δ))/C+O(log⁡log⁡M)\mathbb{E}[\tau\mid x]\le (\log M+\log(1/\delta))/C + O(\log\log M)) characterizes structured/subset or process-level verifiers (e.g., unit-test suites or step-level PRMs that eliminate a constant fraction of hypotheses per step), whereas unstructured singleton equality queries lie in the degenerate O((log⁡M)/M)O((\log M)/M) regime where Ω(M)\Omega(M) scaling is unavoidable.
    • We also added Table 2 (Appendix B) verifying Theorem 1 directly via sequential posterior-stopping trials on the non-vacuous high-ambiguity subsets (log⁡2M^eff>1\log_2 \hat M_{\mathrm{eff}}\gt 1) of GSM8K and MATH.
  2. Incorporating generator capability / coverage:
    • We revised Definition 2, Lemma 1, and Theorem 1 to explicitly condition on the prompt xx (F0=σ(x,U)\mathcal{F}_0=\sigma(x,U)). Under this formulation, the generator's capability determines the post-prompt residual hypothesis space Hx\mathcal{H}_x and effective packing size M^eff=2H(p^∣x)\hat M_{\mathrm{eff}}=2^{H(\hat p\mid x)} (as well as the latent coverage ceiling), while CVC_V governs how efficiently the verifier resolves that remaining post-prompt ambiguity. Thus, stronger generators shrink log⁡M^eff\log \hat M_{\mathrm{eff}} (e.g., 394/500 GSM8K problems have log⁡2M^eff≤0.5\log_2 \hat M_{\mathrm{eff}}\le 0.5 and require minimal verification), while weaker generators or harder tasks (Llama MATH, 62.862.8% pass@1, mean log⁡2M^eff=2.47\log_2 \hat M_{\mathrm{eff}}=2.47 on ambiguous items) expose large latent headroom where verifier capacity dominates.
Reviewer_rmv5OpenReview ↗

Thank you for your rebuttal!

The rebuttal addresses my main technical concerns regarding the tightness of Theorem 1 and the role of generator capability/coverage. However, my concern regarding the novelty and practical significance of the theoretical insights remains. Overall, I will maintain my positive assessment of the paper.

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

This work focuses on addressing the gaps in predictive theory for scaling of test-time compute. The authors model verifier-guided inference as adaptive hypothesis testing and provide a theoretical framework for TTS. The framework tries to provide an explanation as to why, even when massive inference compute is spent, it can hit a performance plateau, termed ``the verifier capacity bottleneck", even when solution is contained within the candidate generation space. The authors provide theoretical analysis as well as empirical observations.

Critical strengths
  1. I think the theoretical framework is formulated well. Treating the verifier as a channel that is capacity-limited and analyzing its effect on TTS is interesting, though this framing may be an oversimplification that does not model other limitations or scenarios of TTS.

  2. I also like how Fano's inequality is applied by treating TTS as adaptive hypothesis testing over this verifier channel. I think this is a nice perspective and angle to study TTS.

  3. I also appreciate the empirical analysis, though it could be presented more clearly.

Critical weaknesses
  1. The theory does not deal with some practical or real-world limitations of TTS, like long reasoning traces due to overthinking that are already been studied extensively, such as [2]. In that study performance degrades sharply and is caused by token-level entropy spikes and variance growth in long chains of thought, rather than a precision bottleneck in the verifier. The current theoretical framework proposed in this work does not account for the sharp drops in performance in such cases. I feel current framework does not also account for self-correcting feedback loops in tree based scaling where based on feedback the generator output distribution may shift through self-refinement for sampling consequent steps in reasoning [3,4]. Will current framework break in cases of self-correcting feedback loops ?

  2. I think some additional relevant works like [1] have already studied the impact of an imperfect/noisy verifier on test-time scaling and how it can cause a bottleneck despite coverage. I think it is essential to discuss and compare how current theoretical framework differs and offers a different eprspective from this work. Also the related work in current version of paper is very thin. I would recommend discussing other related works for test-time scaling like [2] and also related works discussing limitations of the generation policy and verifiers. Current related work is dense and is just many papers cited in a paragraph with little discussion of limitations of those works and how later works build upon the earlier ones. It would be very difficult for readers of this paper to understand the background of this topic with current version.

  3. The paper is not very clear to read. To give some context, this work is very closely aligned with my research interests. Though AI use policy claims to have been used only for polishing, I feel some parts have been heavily polished or rewritten by AI, making the text very dense and hard to parse. For instance, lines 129-134 are very dense, and statements like " The contribution is the abstraction and its consequence" beat around the bush a bit, making it hard to get the core contribution. Also, M is not introduced the first time and it is not apparent what it refers to. From the figure and later Section 4, it is the packing number. it gets better from Section 3 a bit with some more exposition. I would recommend the authors rewrite the abstract and introduction a bit to give a clear overall view of the core motivation, contribution and insights. Right now I get very little information from the abstract and intro when it is supposed to introduce any reader (familiar or unfamiliar with this problem) to the problem and core contributions in an intuitive way.

[1] ROC-N-REROLL: HOW VERIFIER IMPERFECTION AFFECTS TEST-TIME SCALING ICLR 2026

[2] Does Thinking More Always Help? Mirage of Test-Time Scaling in Reasoning Models

[3] SETS: Leveraging Self-Verification and Self-Correction for Improved Test-Time Scaling Jiefeng Chen, Jie Ren, Xinyun Chen, Chengrun Yang, Ruoxi Sun, Jinsung Yoon, Sercan Ö Arık

[4] Refining Over Resampling: Test-Time Self-Correction for LLM Reasoning Ahsan Bilal, Muhammad Ahmed Mohsin, Muhammad Umer, Lena Trigg, Ali Subhan, Muhammad Ali, Dean F. Hougen

Questions for authors
  1. In Definition 1, you mention noisy rewards. Would you need any guarantees on the structure of the noise, such as a sub-Gaussian property, which would enable bounds on the noise, or do you assume no such structure?

  2. `` All source code, seeds, and rollout evaluation artifacts are archived to support exact reproduction." in Section 7 is not clear. I was unable to find code neither in the paper nor in the supplementary material.

  3. Can you please provide additional hyperparameter details on the temperature values used for the generator & verifier? And also max output seq length configured for both?

  4. Can this framework also work for latent reasoning models. Would it not break the assumptions on policy made here?

2 comments
AuthorsOpenReview ↗

Response to Reviewer xohC: Clarity & M Notation, Related Work, Limitations/Scope, and Reproducibility

We thank Reviewer xohC for recognizing the value of our verifier-channel perspective and Fano-based adaptive hypothesis testing formulation, and for providing clear, actionable feedback on presentation, related work, scope, and reproducibility. All points have been addressed in the revised PDF and supplementary code archive:

  1. Clarity, Abstract, Introduction, and Notation (MM):
    • We rewrote the Abstract and Section 1 for direct clarity, removing dense phrasing (such as the previous lines 129–134) and stating the core question and post-prompt channel model up front.
    • We explicitly define M=∣Hx∣M = |\mathcal{H}_x| (number of distinguishable post-prompt candidate hypotheses, or ε\varepsilon-packing number MεM_\varepsilon) at its very first appearance in Section 1 before referencing log⁡M/CV\log M/C_V.
  2. Expanded Related Work & Missing Citations:
    • Section 2 now discusses and contrasts all four references you suggested:
      • Dorner et al. (ICLR 2026) (ROC-n-reroll: How Verifier Imperfection Affects Test-Time Scaling), contrasting their fixed-sampler ROC geometry analysis with our policy-independent channel capacity lower bounds and realized MI diagnostics.
      • Ghosal et al. (2025) (Mirage of Test-Time Scaling), Chen et al. (TMLR 2025) (SETS), and Bilal et al. (2026) (Refining Over Resampling), explicitly contrasting token-level overthinking and closed-loop distribution-shifting self-correction against our fixed-rollout selection setting.
  3. Scope & Limitations (Overthinking, Closed-Loop Self-Correction, Latent Reasoning):
    • We added an explicit Limitations and Scope paragraph in Section 7 acknowledging that our fixed-rollout channel model does not capture: (i) token-level entropy spikes / overthinking degradation in long reasoning chains, (ii) closed-loop self-correction / tree search where feedback shifts the generator's candidate distribution across steps (which breaks the fixed-distribution assumption unless generator drift is tracked per step), or (iii) latent continuous-state reasoning models whose internal states are not discrete candidate queries Y^t\hat Y_t.
  4. Q1 (Noise structure in Definition 1):
    • Clarified directly in Definition 1: no parametric or tail assumptions (such as sub-Gaussianity) on OO are required; our bounds hold for any measurable Markov kernel PV(⋅∣y^,y⋆)P_V(\cdot \mid \hat y, y^\star).
  5. Q2 & Q3 (Reproducibility, Code Archive, and Hyperparameters):
    • Appendix B now opens with a dedicated Hyperparameters and generation settings paragraph listing exact values across every task: generator Tgen=0.7T_{\mathrm{gen}}=0.7 (plus Tgen=1.0T_{\mathrm{gen}}=1.0 GSM8K ablation), top_p =0.95=0.95, max_new_tokens =512=512 (GSM8K/MBPP), 768768 (MATH), and 192192 (13 MC tasks), deterministic Tver=0T_{\mathrm{ver}}=0 forward-pass logit scoring for the LLM judge, and deterministic single-pass step-boundary scoring (max_len =1024=1024) for Qwen2.5-Math-PRM-7B.
    • We have uploaded the anonymized source code, YAML configs, seeds, and rollout evaluation artifacts as Supplementary Material on OpenReview.
Reviewer_xohCOpenReview ↗

Response to authors

Thanks. I think this work is interesting. However, I still feel that the clarity of the manuscript can be improved. Please introduce core research questions, structure ur analysis around them, and also synthesize core insights in the results more clearly. The abstract and intro are a bit clearer after revision during rebuttal. I would recommend authors also rewrite rest of the paper and I am willing to adjust my score to 3 conditional on authors revising and making the paper clear.

Reviewer_iwq7OpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

The paper models verifier-guided inference as adaptive hypothesis testing and defines the verifier capacity CV=sup⁡I(Y⋆;O∣Y^)C_V = \sup I(Y^\star; O \mid \hat Y). It uses Fano’s inequality and an adaptive chain rule to prove E[τ]≥((1−δ)log⁡M−log⁡2)/CV\mathbb{E}[\tau] \ge ((1-\delta)\log M - \log 2)/C_V for any adaptive policy. It adds a posterior-splitting achievability result and a two-point collapse result. The experiments fix the rollouts on GSM8K, MATH, MBPP and 13 multiple-choice sets and change only the selector. Noisy oracles with CV=1−h2(η)C_V = 1-h_2(\eta) give a calibration curve that maps the PRM, majority vote, an LLM judge and log-probability to capacity-equivalent scores of 0.30, 0.21, 0.10 and 0.03.

Critical strengths
  1. The fixed-rollout diagnostic separates generator coverage from selector quality, because only the selection channel changes across rows. Other researchers can apply this protocol to any new verifier.

  2. The paper separates worst-case capacity, realized MI and the calibrated score CeqC_{eq}. The judge example (capacity 0.078 bits, realized MI 0.036 bits at a 0.89 correct base rate) shows why these values differ. This gives the field a clear vocabulary for verifier quality.

Critical weaknesses

The model removes the information that the generator gets from the task. In Definition 2 the policy sees only past queries, past outputs and private randomness U⊥HU \perp H, so Lemma 1 sets the candidate contribution to zero. A generator at 90.6% pass@1 on GSM8K gets most of its information from the prompt, so the bound does not describe the systems that the paper tests. The experiments do not test Theorem 1. No experiment compares the measured number of queries with log⁡M/CV\log M/C_V. Appendix A.3 states that the Figure 2 curve does not follow from Fano. The bound is negative for the 394 of 500 GSM8K problems with log⁡2M^eff≤0.5\log_2 \hat M_{\text{eff}} \le 0.5. A binomial selection model predicts the ordering of noisy oracles by η\eta without the theory. Table 4 follows from answer agreement, because no selector can change the output when all candidates agree. The authors state that the proofs use the standard active sequential testing toolkit, so the contribution depends on this link to the experiments, and the link stays ordinal. CVC_V does not determine the best-of-N gain. Two channels with equal capacity and different TPR and FPR give different gains at a skewed base rate, and majority vote queries no verifier. The CeqC_{eq} scores thus project different signals onto one BSC curve, and the PRM score (0.30) does not match its soft MI (0.12). Proposition 1 needs C-rich queries, but an equality verifier gives at most h2(1/M)h_2(1/M) bits per query, so the tightness claim does not cover best-of-N. Most GSM8K comparisons have no intervals (PRM 94.2 against majority 93.0 on 500 problems), and the majority minus η=0.2\eta=0.2 interval on Llama MATH includes zero.

Questions for authors
  1. Does Lemma 1 hold when the generator conditions on the task xx, so that its samples depend on HH? The answer decides if the bound applies to LLM sampling.
  2. Which rule selects a candidate under the noisy oracle? Does a closed-form binomial model of per-problem correct fraction and η\eta reproduce Table 1 without capacity?
  3. Do two channels with equal CVC_V and different TPR and FPR give equal gains on the same rollouts? Equal gains would support CVC_V as the controlling quantity.
  4. What does Ceq=0.21C_{eq} = 0.21 mean for majority vote, which uses agreement between candidates and no verifier channel?
  5. Why does the log-probability selector give the same value of 90.6 at N = 1, 8 and 32? Does it select the first sample?
  6. On which problems is Theorem 1 non-vacuous, and how close is the measured number of queries to the bound on those problems?
4 comments
AuthorsOpenReview ↗

Response to Reviewer iwq7 (1/2): Log-prob Bug Fix (Q5), Post-Prompt Lemma 1 (Q1), and Sequential Stopping (Q6)

We thank Reviewer iwq7 for an exceptionally thorough and technically sharp review. Every mathematical and empirical question you raised directly improved the paper. In the revised PDF (trackable via OpenReview pdfdiff) and supplementary code archive, we fixed the implementation bug you spotted, added the missing post-prompt conditioning and empirical tests, and clarified each metric's scope. (Because OpenReview comments are capped at 5,000 characters, we split our response into two consecutive comments: Part 1 covers Q5, Q1, and Q6; Part 2 covers Q2, Q3, Q4, and confidence intervals.)

Q5 (Bug caught & fixed): Why did log-probability give 90.6 at N=1,8,32N=1, 8, 32?

You were completely right. In experiments/core/policy.py (line 120), the generation script stored placeholder logprobs = [0.0] to avoid VRAM OOM when caching full-vocabulary logits during batched generate(), so max() in verifier_logprob broke ties by index and selected candidate 0 (pass@1 = 90.6%).

We have now computed exact offline token log-probabilities log⁡p(completion∣prompt)\log p(\text{completion}\mid \text{prompt}) under Qwen2.5-7B-Instruct on the exact same 500×32500 \times 32 GSM8K rollouts (see experiments/scripts/score_gsm8k_logprob.py, results in experiments/outputs/rebuttal_iclr2027/gsm8k_logprob_summary.csv):

  • Token-normalized (1∣tok∣log⁡p(y∣x)\frac{1}{|\text{tok}|}\log p(y\mid x)): Acc.@1 / @8 / @32 = 90.6% / 88.8% / 89.4% (95% CI at N=32N=32: [86.6%, 92.0%]), capturing -15.8% of oracle gain (slightly below pass@1 due to length/brevity bias; Ceq≤0.03C_{\mathrm{eq}} \le 0.03, 10-bin soft MI =0.025= 0.025 bits).
  • Word-normalized gives 90.6% / 89.2% / 90.2% ([87.4%, 92.8%], soft MI =0.041= 0.041 bits); unnormalized sum gives 90.6% / 89.8% / 90.8% ([88.2%, 93.2%], +2.6+2.6% captured gain, Ceq≈0.044C_{\mathrm{eq}} \approx 0.044, soft MI =0.059= 0.059 bits). Across all normalizations, generator log-probabilities carry minimal post-prompt correctness signal.
  • We updated Table 1, Figures 4–5, Section 6, and the supplementary code/CSV archive accordingly, and gratefully acknowledge your catch.

Q1: Does Lemma 1 hold when the generator conditions on the task prompt xx?

You identified a genuine notation omission in Definition 2. When Ft−1\mathcal{F}_{t-1} did not explicitly include xx, Y^1\hat Y_1 already carried substantial prompt-derived information (e.g., 90.6% pass@1 on GSM8K), violating I(H;Y~t∣F~t−1)=0I(H;\tilde Y_t \mid \tilde{\mathcal{F}}_{t-1})=0. We revised Definition 2, Lemma 1, Theorem 1, and Appendix A to explicitly condition on xx (F0=σ(x,U)\mathcal{F}_0 = \sigma(x, U)), defining Hx\mathcal{H}_x as the post-prompt residual uncertainty over Y⋆Y^\star given xx. With xx fixed, every Y^t\hat Y_t is Ft−1\mathcal{F}_{t-1}-measurable with U⊥H∣xU \perp H \mid x, so I(H;Y~t∣x,F~t−1)=0I(H;\tilde Y_t \mid x, \tilde{\mathcal{F}}_{t-1})=0 holds strictly and E[τ∣x]≥((1−δ)log⁡M−log⁡2)/CV\mathbb{E}[\tau\mid x]\ge ((1-\delta)\log M - \log 2)/C_V.

Q6: On which problems is Theorem 1 non-vacuous, and how close is measured E[τ]\mathbb{E}[\tau]?

Under the post-prompt formulation, the 394/500 GSM8K problems with log⁡2M^eff≤0.5\log_2 \hat M_{\mathrm{eff}} \le 0.5 have near-zero post-prompt entropy (pass@1 ≈98\approx 98%), so Theorem 1 rightly predicts ≤0\le 0 queries (matching Table 6, where η=0.4\eta=0.4 loses only 1.0%). Theorem 1 is strictly positive (non-vacuous) on log⁡2M^eff>1\log_2 \hat M_{\mathrm{eff}} \gt 1 (53 GSM8K items, mean 1.791.79; 98 Llama-MATH items, mean 2.472.47).

We added a direct sequential stopping experiment on these non-vacuous subsets (Appendix B, Table 2), drawing Y⋆∼p^Y^\star \sim \hat p and running posterior-guided BSC(η\eta) queries until max⁡yPt(Y⋆=y)≥1−δ\max_y P_t(Y^\star=y) \ge 1-\delta (δ=0.10\delta=0.10):

Dataset (log⁡2M^eff>1\log_2 \hat M_{\mathrm{eff}}\gt 1)η\etaCVC_V (bits)Thm. 1 LBMeasured E[τ]\mathbb{E}[\tau]Realized err.
GSM8K (n=53n=53, mean 1.791.79)0.01.0000.612.160.002
GSM8K (n=53n=53, mean 1.791.79)0.10.5311.143.590.044
GSM8K (n=53n=53, mean 1.791.79)0.20.2782.186.550.054
GSM8K (n=53n=53, mean 1.791.79)0.30.1195.1114.610.073
MATH (n=98n=98, mean 2.472.47)0.01.0001.223.250.000
MATH (n=98n=98, mean 2.472.47)0.10.5312.305.540.044
MATH (n=98n=98, mean 2.472.47)0.20.2784.3910.300.057
MATH (n=98n=98, mean 2.472.47)0.30.11910.2823.180.075

Measured E[τ]\mathbb{E}[\tau] strictly respects Theorem 1 and scales as 1/CV1/C_V, with the 2–3×2\text{--}3\times factor explained by singleton-equality query degeneracy. Section 4 and Proposition 1 (Appendix A.2) now explicitly state that CC-rich achievability applies only to structured/process queries (e.g., unit tests or step rewards), whereas unstructured singleton equality queries provide O((log⁡M)/M)O((\log M)/M) bits and require Ω(M)\Omega(M) queries.

AuthorsOpenReview ↗

Response to Reviewer iwq7 (2/2): Binomial Model (Q2), Asymmetric Channels & PRM MI (Q3), Majority Vote & CIs (Q4)

(Continuing our response to Reviewer iwq7.)

Q2: Noisy-oracle selection rule & closed-form binomial model

Our noisy-oracle implementation uses ordered first-accept selection (flipping each candidate's true binary label independently with probability η\eta, returning the first candidate flagged positive, falling back to candidate 0). We verified your conjecture directly (analyze_iclr2027_rebuttal.py): the exact first-accept expectation and the closed-form i.i.d. binomial model given per-problem correctness fraction pip_i reproduce Table 1 within ≤0.011\le 0.011 (mean ∣diff∣=0.0065|\text{diff}| = 0.0065 across all (N,η)(N,\eta)). We now document this exact rule and binomial agreement in Appendix A.3, clarifying that Theorem 1 does not aim to replace the one-parameter BSC binomial formula, but rather to lower-bound arbitrary adaptive policies and provide a calibrated reference scale for non-BSC practical selectors.

Q3: Equal-CVC_V channels with different (TPR,FPR)(\mathrm{TPR},\mathrm{FPR}) & reconciling PRM 0.30 vs soft MI 0.12

You are right on both counts.

  1. Asymmetric channels with equal CVC_V yield different best-of-NN gains under skewed priors. We added Appendix B, Table 3 comparing three channels with identical CV=0.278C_V = 0.278 bits at GSM8K's 89.089.0% base rate (N=32N=32): Symmetric BSC (FPR=0.20,TPR=0.80\mathrm{FPR}=0.20,\mathrm{TPR}=0.80) achieves 94.394.3% (49.349.3% captured gain, realized MI 0.1140.114 bits), Lenient (FPR=0.428,TPR=0.96\mathrm{FPR}=0.428,\mathrm{TPR}=0.96) achieves 92.992.9% (30.630.6%, MI 0.1410.141), and Strict (FPR=0.04,TPR=0.572\mathrm{FPR}=0.04,\mathrm{TPR}=0.572) achieves 96.496.4% (76.776.7%, MI 0.0960.096). The same pattern holds on Llama MATH. We updated Section 3.2 and Section 6 to state explicitly that worst-case CVC_V bounds general adaptive policies, whereas fixed-budget best-of-NN on a skewed pool depends on the operating point and realized MI.
  2. Why does PRM have Ceq≈0.30C_{\mathrm{eq}}\approx 0.30 yet soft MI =0.120= 0.120 bits? Because on GSM8K's skewed pool (89.089.0% correct, input entropy h2(0.890)=0.499h_2(0.890)=0.499 bits), even the symmetric noisy oracle η=0.2\eta=0.2 (CV=0.278C_V=0.278 bits) itself has realized MI of only 0.1140.114 bits (and η=0.1,CV=0.531\eta=0.1, C_V=0.531 has realized MI 0.2290.229 bits). Thus PRM's soft MI (0.1200.120 bits) closely matches the realized MI of an η≈0.19\eta\approx 0.19 symmetric oracle (CV≈0.30C_V\approx 0.30), reconciling the two numbers.

Q4 & Statistical Intervals: Majority vote and paired bootstrap CIs

  • Majority vote: In Section 3.1 we now explicitly note that majority vote aggregates inter-candidate agreement without querying an external verifier channel, so its Ceq≈0.21C_{\mathrm{eq}}\approx 0.21 is strictly an empirical coordinate on the fixed GSM8K reference curve (not a channel capacity).
  • Confidence intervals: Section 6 now reports 10,00010{,}000-resample paired bootstrap 95% CIs for GSM8K Table 1 (oracle: 98.298.2% [97.0,99.2][97.0,99.2], PRM: 94.294.2% [92.0,96.2][92.0,96.2], majority: 93.093.0% [90.6,95.2][90.6,95.2], judge: 91.691.6% [89.2,94.0][89.2,94.0], logprob: 89.489.4% [86.6,92.0][86.6,92.0]; majority - pass@1: +2.4+2.4 [0.6,4.4][0.6,4.4]; eta=0.2 - eta=0.4: +2.8+2.8 [2.1,3.4][2.1,3.4]), and we explicitly note where differences (majority - judge, majority - eta=0.2) include zero.
Reviewer_iwq7OpenReview ↗

Thankyou

Thank you for the thorough response, the log-probability fix and the added experiments. I will maintain my score, because the new test of Theorem 1 uses only simulated BSC oracles, and you now agree that capacity alone does not set best-of-N gains and that the majority-vote score is not a capacity, so it remains unclear what the capacity-equivalent scores of the real selectors measure beyond their ranking.

AuthorsOpenReview ↗

Follow-up to Reviewer iwq7: Non-Simulated Theorem 1 Test on Real Verifiers and Scope of C_eq

Thank you for reading our revision carefully and for clearly stating your two remaining concerns. We respect your decision and add two concise clarifications below for you and the Area Chair:

1. Non-simulated test of Theorem 1 on the real PRM, LLM Judge, and Log-prob trajectories

To test Theorem 1 without any simulated BSC flips, we ran adaptive posterior-guided sequential stopping directly on the saved real verifier scores (prm_mean, judge_p_yes, mean_logprob_tok) over the non-vacuous subsets (log⁡2M^eff>1\log_2 \hat M_{\mathrm{eff}} \gt 1, leave-one-problem-out 5-bin empirical likelihoods, stopping threshold 1−δ=0.651-\delta = 0.65, capped at NN rollouts; reproducible via analyze_iclr2027_rebuttal.py):

Real verifier (non-simulated)nn (log⁡2M^eff>1\log_2 \hat M_{\mathrm{eff}}\gt 1)Mean HHSubset CVC_VRealized MIMeasured E[τ]\mathbb{E}[\tau]Stop rateRealized err.Thm. 1 LB
GSM8K Judge (N=32N=32)531.790.0700.0687.620.810.3771.59
GSM8K Log-prob (N=32N=32)531.790.0070.00715.580.600.4720.00
MATH PRM (N=16N=16)982.470.2960.2667.300.680.3981.64
MATH Judge (N=16N=16)982.470.1170.1008.700.540.4692.64

Every real verifier obeys Theorem 1 (E[τ]≥\mathbb{E}[\tau] \ge Thm. 1 LB). Within both datasets, the higher-CVC_V real verifier stops in fewer queries with lower error (GSM8K Judge 7.627.62 vs. Log-prob 15.5815.58; MATH PRM 7.307.30 vs. Judge 8.708.70).

2. What CeqC_{\mathrm{eq}} measures beyond ranking (and what it does not)

We agree completely that CeqC_{\mathrm{eq}} is not a budget-invariant or prior-invariant capacity (for majority vote it is purely a non-channel baseline coordinate, and for real verifiers it depends on NN, channel asymmetry, and the GSM8K prior). Beyond ordinal ranking, CeqC_{\mathrm{eq}} serves as a nonlinear headroom unit conversion on a fixed reference testbed: near GSM8K's high pass@1 ceiling (90.6% to 98.2%), raw accuracy gaps (94.2% / 93.0% / 91.6% / 89.4%) look small and linear, whereas projecting captured oracle gain (47.4% / 31.6% / 13.2% / -15.8%) onto the symmetric-oracle curve maps them to an equivalent flip-noise level (η≈0.19,0.24,0.32,≥0.40\eta \approx 0.19, 0.24, 0.32, \ge 0.40). All intrinsic information claims about learned verifiers rest on measured CVC_V and realized MI, not on CeqC_{\mathrm{eq}}.

Thank you again for your constructive feedback—your log-probability bug catch and theoretical sharpening materially strengthened the paper.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.