{"id":"235cce9d-586c-4a31-a05a-c3ca098dcd82","arxiv_id":"2505.18065","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":4,"one_line_summary":"The paper claims PRM generalization error controls test-time compute efficiency and that the proposed CATS controller improves accuracy on MATH-500 and AIME24.","lead":"This paper derives PAC-Bayes bounds that connect a process reward model's generalization error to the number of reasoning samples needed at test time, then introduces CATS, a learned actor-critic controller for adaptive search. Generalists should read it to see theory-motivated compute allocation for LLM reasoning, though the central theorem has proof errors.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4.5's per-path independence assumption is inconsistent with a single fixed reward model, so the exponential sample-complexity bound is unproven.","rationale":"The paper's central claim is that a lower PRM generalization error reduces the number of sampled reasoning paths needed to reach a target accuracy. The quantitative basis is Theorem 4.5, whose lower bound in Eq. (6) contains the misranking term (N-1) exp(-gamma^2 / 8epsilon^2). This term is obtained by a Hoeffding tail bound over path-level reward deviations, but the deviations are not independent in the actual inference setup: a single frozen PRM produces all scores, so any two errors Delta_h and Delta_h' are functions of the same parameters phi and the same question q. If randomness is intended to come from a PAC-Bayes posterior, then phi is drawn once and shared by all paths, again inducing correlation. The independence assumption is therefore internally inconsistent with the problem setting, not merely a strong condition. A concrete correlated-error model shows why this matters: if the PRM systematically over-scores one family of wrong reasoning patterns, the true-best path will be misranked with probability that does not vanish as N grows, contradicting the claimed exponential improvement. The reader's identified gap, that the PAC-Bayes bound in Eq. (5) controls expected loss and not the per-instance sup norm epsilon, is also real and supports the same conclusion: the theorem's epsilon is not connected to the theory developed earlier. There is also a smaller algebraic mismatch between the theorem statement and its proof, with delta placed inside the bracket instead of outside; this alone would require correction. The empirical CATS results are extensive but lack error bars and code release, and the sparsity proxy in Appendix G shows only a weak, non-monotonic relation across five PRMs, so they do not compensate for the unproven theoretical link. Because the core theorem is not established as stated, the paper's central theoretical claim does not stand; the reader's REJECT verdict is appropriate and no adjustment is needed.","tokens_in":18126,"tokens_out":8829,"duration_ms":83450,"concrete_test":"Run a selection simulation with a fixed PRM (e.g., Qwen2.5-Math-PRM-7B) on a labeled benchmark: for each question, sample N paths, record true rewards and PRM scores, and compute the empirical misranking rate P(h_sel != h*) for N = 4..256. Check whether this rate decays like (N-1) exp(-gamma^2 / (8 epsilon^2)) with epsilon estimated from the observed sup error. If the rate does not decay with N, or if block-bootstrapping path errors destroys the decay, the independence assumption in Theorem 4.5 is the reason; this directly tests the central claim that better PRM generalization reduces required samples.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing step is Theorem 4.5's assumption that, conditioned on H, the per-path deviations Delta_h = R_phi(q,h) - R*(q,h) are independent and mean-zero. For a fixed trained PRM, phi is a single parameter vector; conditioned on H, the Delta_h are deterministic. If instead phi is drawn from the PAC-Bayes posterior Q of Theorem 4.2, there is only one draw of phi shared by all paths, so the Delta_h are coupled through phi and are not independent. Thus the Hoeffding bound in Appendix C (line 28) has no valid target, and the exponential (N-1) exp(-gamma(q)^2 / (8 epsilon^2)) term in Eq. (6) is unsupported. Correlated errors can persist: a wrong reasoning style systematically over-scored by the PRM will keep being selected no matter how large N is. A secondary internal mismatch is that Appendix C's derivation yields p[1 - (N-1) exp(-gamma^2/8epsilon^2)] - delta, not the stated p[1 - delta - (N-1) exp(-gamma^2/8epsilon^2)], and the PAC-Bayes bound of Eq. (5) is not shown to control the per-instance sup norm epsilon used here.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies how the generalization error of a process reward model (PRM) affects test-time compute optimality in external test-time reasoning for large language models. The authors first derive a PAC-Bayes generalization bound for PRMs (Theorem 4.2), then use it to state an answer-accuracy lower bound in terms of the reward gap, coverage probability, and a uniform error bound ε (Theorem 4.5), and from this derive a target-accuracy constraint on the sampling budget (Corollary 4.6). They then propose Compute-Aware Tree Search (CATS), an actor-critic method that uses PRM parameter sparsity as a proxy for generalization error and adaptively controls search hyperparameters. Experiments on MATH-500 and AIME24 with several policies and PRMs report that CATS outperforms Best-of-N, beam search, and majority voting across budgets.","tokens_in":18296,"tokens_out":10912,"duration_ms":87915,"significance":"The question addressed is timely and important: understanding how verifier quality controls the compute-accuracy trade-off in inference-time scaling. If the theoretical results were valid, the connection between PAC-Bayes generalization bounds, reward margin, and the number of sampled paths would be a useful contribution. The empirical component is substantial: CATS is a well-motivated controller, the experiments cover multiple policy models and PRMs, and the appendices include ablations for the sparsity proxy, reward coefficients, and discount factor, as well as pseudocode. However, the load-bearing steps of the theory are not sound: the proof of Theorem 4.2 contains an incorrect optimization, the assumptions of Theorem 4.5 are incompatible with the actual random structure of a fixed PRM, and the bridge from the PAC-Bayes expected-loss bound to the per-candidate uniform error ε is not justified. These problems undermine the central claim that a smaller PRM generalization error provably reduces the number of candidate paths required for a target accuracy.","major_comments":[{"comment":"The λ optimization in the proof is incorrect. Equation (21) gives λ E_Q[L_D − L_S] ≤ λ²/(8n) + KL(Q∥P) + log(1/δ). For this inequality the optimal λ is λ* = 4n E_Q[L_D − L_S], not the claimed λ* = 4√((n−1)/2). Substituting the claimed value leaves an uncancelled term √((n−1)/2)/(2n), and the final bound with denominator 2(n−1) and log(n/δ) does not follow from the preceding algebra. The theorem may be repairable by citing a standard PAC-Bayes bound, but the derivation as written does not prove Eq. (4).","section":"Appendix B, proof of Theorem 4.2"},{"comment":"The assumption that, conditioned on H, the deviations Δ_h = R_φ(q,h) − R*(q,h) are independent and mean-zero is not justified for the setting of the paper. For a fixed trained PRM, φ is a single parameter vector, so conditioned on H the deviations are deterministic; unconditionally, the Δ_{h_i} are independent only because the h_i are independent, but they need not be mean-zero since E_{h∼π_θ}[R_φ(q,h) − R*(q,h)] is not zero in general. If φ is instead drawn from the PAC-Bayes posterior Q, all paths share the same draw of φ, so the deviations are coupled. Consequently, the Hoeffding bound in Appendix C has no valid target, and the exponential term (N−1)exp(−γ(q)²/(8ε²)) in Eq. (6) is unsupported.","section":"Section 4.2, Theorem 4.5 assumptions"},{"comment":"The sentence 'Define this upper-bound as ε' is not a valid step. Equation (5) bounds the expected absolute loss E_{φ∼Q}[L_D(φ) − L_S(φ)] averaged over the data distribution D, whereas Theorem 4.5 requires a high-probability uniform error bound ε on sup_{h∈H}|R_φ(q,h) − R*(q,h)| over a finite candidate set for a single question q. No argument is given that the PAC-Bayes bound controls this sup-norm quantity or that the event G has probability at least 1−δ. This missing bridge is load-bearing: it is precisely the link that would support the claim that smaller PRM generalization error reduces the required number of samples, and it is not established.","section":"Section 4.2, Eq. (5) to Theorem 4.5"},{"comment":"The final algebra of the proof does not match the statement. The derivation gives Pr(E1 ∪ E2) ≤ (1 − p) + p(N−1)exp(−γ²/8ε²) + δ, which yields success probability at least p − p(N−1)exp(−γ²/8ε²) − δ, i.e., p[1 − (N−1)exp(−γ²/8ε²)] − δ, not p[1 − δ − (N−1)exp(−γ²/8ε²)] as stated in Eq. (6). In addition, the intermediate statement that a competitor must overcome a gap of at least γ(q) − 2ε is not the quantity that appears in the Hoeffding exponent. The stated bound therefore does not follow from the proof as written.","section":"Appendix C, proof of Theorem 4.5"}],"minor_comments":[{"comment":"The dimension d in the term log d is never defined, and the constant c is introduced without explanation or calibration; the formal step from a sparsity-based prior to this specific bound is omitted.","section":"Section 5.1, Eq. (8)"},{"comment":"The notation is inconsistent: Assumption 4.4 states lim_{N→∞} p_N(q) = 1, but the quantity used throughout the rest of the section is p_{N,τ}(q).","section":"Section 4.2, Assumption 4.4"},{"comment":"The PRM parameters and the critic parameters are both denoted φ (R_φ and V_φ), which is confusing; the critic should use a different symbol, e.g., V_ξ as in Eq. (10).","section":"Section 5.2 and Algorithm 1"},{"comment":"The comparison with Best-of-N and Beam Search uses the number of candidate paths as the shared budget, but CATS's adaptive tree search may consume different amounts of compute per path; the paper should state how the budget is matched and ideally report token counts or wall-clock time.","section":"Section 6.2"},{"comment":"The text says 'using Qwen2.5-Math-PRM-7B as the policy model,' which appears to be a typo; the policy in the corresponding experiments is Qwen2.5-Instruct-7B, and the intended model should be clarified.","section":"Appendix H.2"},{"comment":"The empirical results are reported without error bars or significance tests; given that several ablations show differences of about one percentage point, the claim of consistent improvement would be stronger with variance estimates or multiple seeds.","section":"Figures 1–2 and Tables 3–6"},{"comment":"The Limitations section asserts that the assumptions 'do not undermine the validity of the analysis,' but in light of Major Comments 2 and 3 this assertion is not supported; the appendix should be expanded to address the independence and uniform-error assumptions rather than dismissing them.","section":"Appendix A"}],"recommendation":"reject","confidential_remarks":"The paper's advertised contribution is the theoretical framework, and the central bridge from PAC-Bayes bounds to per-candidate uniform error is not established; the proof of Theorem 4.5 also contains an unjustified independence assumption and algebraic inconsistencies. If the authors reframe the paper as an empirical study of CATS with a heuristic sparsity proxy, it could be a reasonable applied contribution, but the current manuscript does not meet the bar for acceptance in this form."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the paper aims at a real question—how PRM generalization error affects test-time compute—and the CATS method looks like it works, but the main theorem (4.5) has a load-bearing flaw that makes the theory unsound as written.\n\nWhat's new and good: the idea of linking a PAC-Bayes bound for reward models to sample complexity and then using that to motivate a learned controller is a sensible direction. CATS, an actor-critic that adjusts sampling and pruning based on reward gaps and sparsity, is a reasonable practical contribution. The experiments cover multiple policies and PRMs on MATH and AIME, and CATS consistently beats Best-of-N, Beam Search, and Majority Voting. That's a solid empirical story, modulo the issues below.\n\nWhere it falls apart: Theorem 4.5 assumes that, conditioned on H, the deviations Δ_h are independent and mean-zero. For a fixed trained PRM, φ is a single parameter vector, so the Δ_h are either deterministic (if φ is fixed) or all correlated through the same posterior draw. There is no independence. The Appendix C proof also derives p[1 - (N-1)exp(-γ²/8ε²)] - δ, not the stated p[1 - δ - (N-1)exp(...)]; the δ placement is not a cosmetic typo. On top of that, ε in the theorem needs to be a uniform per-path bound, but the PAC-Bayes bound from Eq. 5 controls expected loss over the data distribution. The bridge between those two is never established. Theorem 4.2's proof has a suspicious λ* that doesn't depend on the KL term, suggesting an optimization error there as well. These are load-bearing, not cosmetic.\n\nEmpirics: the sparsity proxy evidence is thin—five PRMs, no clear monotonic trend (Skywork is most sparse but has high error), and the main results are reported without error bars or code. The method may still work, but the current evidence doesn't let us separate CATS's contribution from noise.\n\nBottom line: this is a paper for someone interested in adaptive test-time compute who might borrow the CATS idea. The theory as written should not be relied on. I'd send it to peer review because the question matters and the method is promising, but it needs major revision—either fix the theorem and its proof, or drop the theoretical framing and present CATS as an empirical method. The current version overclaims.","headline":"The core theory doesn't hold up—Theorem 4.5's independence assumption is invalid—but CATS is a sensible method worth a serious look.","tokens_in":18925,"tokens_out":5625,"would_cite":false,"duration_ms":43322,"reading_group":"maybe","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A process reward model's generalization error dictates the test-time compute needed for reliable reasoning.","keywords":["test-time compute optimality","process reward model","PAC-Bayes generalization bound","reward gap","compute-aware tree search","actor-critic control","mathematical reasoning","LLM inference scaling"],"falsifier":"Sample candidate sets from a fixed policy model, score them with a PRM, and compute the empirical uniform deviation $\\hat\\varepsilon = \\sup_{h\\in H}|R_\\varphi(q,h) - R^*(q,h)|$ on held-out questions with known per-step labels; also measure the correlation of deviations across paths that share a prefix. If $\\hat\\varepsilon$ routinely exceeds the value used in Theorem 4.5, or if the deviations are strongly correlated, the stated accuracy floor cannot be expected to hold.","tokens_in":17811,"feed_emoji":"🧠","tokens_out":11159,"duration_ms":80147,"temperature":0.7,"pith_summary":"This paper tries to establish that the generalization error of a process reward model (PRM) is a primary driver of test-time compute optimality: under a fixed inference budget, the number of candidate reasoning paths needed to reach a target accuracy shrinks as the PRM's error bound shrinks. The proof path is a lower bound on final-answer accuracy in which the chance of selecting the correct answer is at least the coverage probability of sampling a good path times a mis-ranking penalty that depends on the reward gap divided by the PRM's error. From that bound the paper derives a compute-budget corollary: to guarantee accuracy $\\alpha$, the sampling coverage must satisfy $p_{N,\\tau}(q) \\ge \\alpha / [1 - \\delta - (N-1)\\exp(-\\gamma(q)^2/(8\\varepsilon^2))]$. Because the true error $\\varepsilon$ is unobservable, the paper proposes parameter sparsity as a proxy and builds CATS, an actor-critic search controller that widens the reward gap by adaptively choosing how many paths to sample and keep. Experiments on MATH-500 and AIME24 across several policy models and PRMs show CATS outperforming Best-of-N, beam search, and majority voting, consistent with the predicted dependence on $\\varepsilon$.","feed_headline":"Reward-model error sets how many reasoning paths you need","feed_subtitle":"A new bound ties reward-model generalization to accuracy and compute; the CATS controller exploits the reward gap","key_machinery":"The load-bearing object is the reward gap $\\gamma(q) = R^*(q,h^*) - \\max_{h \\ne h^*} R^*(q,h)$, the difference in true reward between the best candidate path and the runner-up; the argument shows that a mis-ranking happens only when the PRM's bounded errors let a competitor overcome this gap. That mis-ranking tail is carried by the exponential term $\\exp(-\\gamma(q)^2/(8\\varepsilon^2))$ in Theorem 4.5, where $\\varepsilon$ is the uniform bound on the PRM's absolute deviation. The generalization bound that supplies $\\varepsilon$ is the PAC-Bayes inequality of Theorem 4.2, which upper-bounds the expected absolute reward error by $\\sqrt{(\\mathrm{KL}(Q\\|P) + \\log(n/\\delta))/(2(n-1))}$; the paper then proposes parameter sparsity, through the bound $\\varepsilon \\le \\sqrt{(c\\|\\hat\\phi\\|_0 \\log d + \\log(n/\\delta))/(2(n-1))}$, as an observable proxy for that error. CATS is the mechanism that operationalizes the bound: an actor-critic controller whose reward function penalizes compute, rewards reward-gap widening, and rewards high PRM scores.","core_discovery":"The paper's central claim, stated as Theorem 4.5, is that for a fixed question $q$ with $N$ independently sampled reasoning paths, the probability that the PRM-selected path gives the correct answer is at least $p_{N,\\tau}(q)[1 - \\delta - (N-1)\\exp(-\\gamma(q)^2/(8\\varepsilon^2))]$, where $p_{N,\\tau}(q)$ is the probability that at least one sampled path has true reward above threshold $\\tau$, $\\gamma(q)$ is the gap between the true-best and the second-best path rewards, and $\\varepsilon$ is a uniform bound on $|R_\\varphi(q,h) - R^*(q,h)|$ over the candidate set. The argument bounds the mis-ranking event: with deviations bounded by $\\varepsilon$, a competitor must overcome a gap of roughly $\\gamma(q) - 2\\varepsilon$, and a standard tail bound for bounded independent deviations produces the exponential term. Corollary 4.6 turns this into a budget statement: guaranteeing accuracy $\\alpha$ forces the sampling coverage $p_{N,\\tau}(q)$ to be at least $\\alpha/[1 - \\delta - (N-1)\\exp(-\\gamma(q)^2/(8\\varepsilon^2))]$. The paper's conclusion is that smaller PRM generalization error and larger reward gap are the two levers that cut required test-time compute, and it builds CATS to widen the reward gap while using sparsity as a proxy for the error.","pith_inferences":["My inference: the authors could test the theory directly by artificially degrading a strong PRM (for example, adding calibrated label noise) and checking whether the required number of paths grows roughly as predicted by the $\\exp(-\\gamma(q)^2/(8\\varepsilon^2))$ term.","My inference: because the theorem assumes deviations for different candidate paths are independent, it likely understates mis-ranking risk when candidates share reasoning prefixes; an experiment on prefix-sharing candidate sets would show whether practical margins need to be wider than the formula suggests.","My inference: the reward-gap argument should transfer beyond math word problems to other verifier-guided planning settings, since the proof uses only sampled paths, true rewards, and gaps, not any language-model-specific structure."],"forward_implications":["Tightening the PRM generalization bound $\\varepsilon$ raises the accuracy floor exponentially in $1/\\varepsilon^2$ for a fixed number of sampled paths $N$.","To reach a target accuracy $\\alpha$, the required sampling coverage grows like $\\alpha/[1 - \\delta - (N-1)\\exp(-\\gamma(q)^2/(8\\varepsilon^2))]$, so better-generalizing PRMs translate directly into a smaller compute budget.","The reward gap $\\gamma(q)$ is the controllable lever at inference: adjusting sampling hyperparameters such as top-$p$, top-$k$, and temperature to separate good from bad paths improves accuracy without changing the PRM.","Parameter sparsity can serve as an observable proxy for the unobservable generalization error, enabling adaptation at test time.","CATS, as an actor-critic policy over sampling and retention actions, is reported to outperform Best-of-N, beam search, and majority voting on MATH-500 and AIME24 across the tested policy and PRM combinations."],"supporting_citations":[{"why":"Supplies the PAC-Bayes variational machinery used to prove Theorem 4.2.","marker":"[37]"},{"why":"Provides the PAC-Bayes bound form that the reward-model generalization bound adapts.","marker":"[38]"},{"why":"Defines the step-level PRM training objective and supplies the MATH-500 evaluation set.","marker":"[12]"},{"why":"Provides the automatic step-label construction used for the PRMs in the experiments.","marker":"[13]"},{"why":"Motivates Assumption 4.4 that sampling more paths makes coverage of a high-reward path approach probability one.","marker":"[28]"},{"why":"Formulates test-time compute optimality and the budget-based evaluation used in Equation 1.","marker":"[7]"},{"why":"Supports sparsity-based priors for non-vacuous PAC-Bayes bounds, justifying Equation 8.","marker":"[32]"},{"why":"Supplies compression-style PAC-Bayes bounds used to argue parameter sparsity is a proxy for the generalization error.","marker":"[33]"}],"fun_headline_variants":["Reward-model error dictates reasoning path count","Test-time compute scales with PRM generalization error","CATS: cutting test-time compute via reward-model error bounds","Generalization bound links PRM error to required samples"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument relies on treating the theoretical bound on the reward model's average error as a bound on the worst-case error for every candidate reasoning path, and on assuming those path-wise errors are independent and centered; that equivalence is asserted, not proven.","fun_headline_variants_meta":{"raw":{"variants":["Reward-model error dictates reasoning path count","Test-time compute scales with PRM generalization error","CATS: cutting test-time compute via reward-model error bounds","Generalization bound links PRM error to required samples"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000318,"raw_usage":{"total_tokens":1846,"prompt_tokens":1045,"completion_tokens":801,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":661,"completion_tokens_details":{"reasoning_tokens":751}},"tokens_in":661,"tokens_out":801,"duration_ms":5973,"temperature":1.0,"reasoning_tokens":751,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T14:36:36.223530+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Sample candidate sets from a fixed policy model, score them with a PRM, and compute the empirical uniform deviation $\\hat\\varepsilon = \\sup_{h\\in H}|R_\\varphi(q,h) - R^*(q,h)|$ on held-out questions with known per-step labels; also measure the correlation of deviations across paths that share a prefix. If $\\hat\\varepsilon$ routinely exceeds the value used in Theorem 4.5, or if the deviations are strongly correlated, the stated accuracy floor cannot be expected to hold.","supporting_citations":[{"cited_title":"Pac-bayesian generalisation error bounds for gaussian process classification","cited_arxiv_id":null,"evidence_quote":"Provides the PAC-Bayes bound form that the reward-model generalization bound adapts."},{"cited_title":"Let’s Verify Step by Step, May 2023","cited_arxiv_id":null,"evidence_quote":"Defines the step-level PRM training objective and supplies the MATH-500 evaluation set."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the automatic step-label construction used for the PRMs in the experiments."},{"cited_title":"Le, Christopher Ré, and Azalia Mirhoseini","cited_arxiv_id":null,"evidence_quote":"Motivates Assumption 4.4 that sampling more paths makes coverage of a high-reward path approach probability one."},{"cited_title":"Scaling LLM Test-Time Compute Optimally Can be More Effective than Scaling Parameters for Reasoning","cited_arxiv_id":null,"evidence_quote":"Formulates test-time compute optimality and the budget-based evaluation used in Equation 1."},{"cited_title":"Sparsity-aware generalization theory for deep neural networks","cited_arxiv_id":null,"evidence_quote":"Supports sparsity-based priors for non-vacuous PAC-Bayes bounds, justifying Equation 8."},{"cited_title":"Pac-bayes compression bounds so tight that they can explain generalization","cited_arxiv_id":null,"evidence_quote":"Supplies compression-style PAC-Bayes bounds used to argue parameter sparsity is a proxy for the generalization error."}],"review_version":1}