acceptodds
Under review as a conference paper at ICLR 2027

Risk Identification and Evidence Complexity for Verifier-Guided Selection

Abstract

A fixed verifier-guided selector can have different risks under routing laws with identical low-order statistics. We study the cost of estimating its worst compatible risk when each paid query restores a retained state and returns a fresh bounded loss. The feasible domain contains all nonnegative routing laws with the specified moments. For top- selection and moments through order , the worst-case record count scales as while the unseen mass is bounded by , where . We construct one positive law with prescribed heavy records at every geometric scale, uniformly in the number of scales and bounded product biases. The resulting acquisition rates match away from and at critical breadth when dominates . At fixed confidence, the general critical bounds remain and ; the balanced top-two lower bound improves by a factor . The critical gap separates a scalar-output lower bound from an upper algorithm that learns a near-optimal law; a specified mean family admits cheaper scalar estimation at fixed confidence. We also characterize the full space of exactly identified losses. A supplied distance bound to this space reduces the effective query depth even when the approximating loss is unknown, under the same paid observation interface.

Primary area:
learning theory
Keywords:
learning theory, partial identification, verifier-guided selection, evidence complexity, adaptive sampling, moment constraints, minimax estimation, limited independence

Reviews

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

I am unable to summarize the paper as I have found it impossible to understand.

Critical strengths

None

Critical weaknesses

The paper reads like an LLM slop. It is impossible to understand what is going on, what is the problem the authors want to solve and more importantly WHY they want to solve it. I can imagine there is some kind of contribution there but at the current state it is not-readable and should be rejected.

Questions for authors

none

2 comments
AuthorsOpenReview ↗

Response to Reviewer vXbD (1/2): The problem we study and its relevance to LLM reasoning

We thank the reviewer for the candid assessment. We agree that the submitted version did not state clearly what problem we address or why it matters, and we take responsibility for this. Below we restate the problem through a minimal example; the revised introduction now follows the same structure.

Setting. Many LLM reasoning systems do not return the model's first answer. They sample several candidate solutions or reasoning steps, score them with a verifier (typically a reward model, often a process reward model, PRM), and keep only the highest-scoring few. Best-of-N with a trained verifier (Cobbe et al., 2021), PRM-based step selection (Lightman et al., ICLR 2024) and PRM-guided beam search for test-time compute (Snell et al., ICLR 2025) all follow this pattern. Our experiments use this pipeline: Qwen2.5-Math-1.5B-Instruct generates the steps, and Qwen2.5-Math-PRM-7B or RLHFlow Llama3.1-8B PRM scores them.

Deployed systems often have more than one verifier available, for example a cheap and an expensive one, or two versions under an A/B test. A rule, which we call the router, decides which verifier scores each candidate. Because the verifiers assign different scores, the router affects which candidates survive and, in turn, whether the final answer is correct.

Question. Consider an evaluator outside the system, such as an internal safety team, a third-party evaluator or a regulator. Such an evaluator usually receives summary statistics of the routing rather than the full log, for example: "each candidate is sent to verifier A half of the time, and the choices for any two candidates are independent." We ask two questions. What is the largest failure rate consistent with this information? And if the evaluator can pay to rerun the model, how many reruns are needed to estimate it reliably?

A minimal example (Section 2). Three candidates compete for two slots. For each candidate, one verifier assigns a higher score and the other a lower one. Consider two routers:

  • Router 1 assigns candidates 1 and 2 by independent fair coins and sets candidate 3 to the XOR of the two, so the number of "high" assignments is always even.
  • Router 2 does the same but negates the assignment of candidate 3, so the number is always odd.

Under both routers, every candidate is sent to each verifier exactly half of the time, and any two assignments are independent. The released statistics therefore cannot distinguish them; this is the standard example of three bits that are pairwise but not jointly independent. The routers differ, however, in how often all three candidates receive their low score: one quarter of the time under Router 1, and never under Router 2. If that configuration is the one that leads the search to a wrong answer, the failure rate is 25% under Router 1 and 0% under Router 2. The released information supports only the interval [0%, 25%]; pairwise statistics do not determine the risk.

The same effect appears with real verifiers. On 512 MATH/GSM8K questions with two PRMs and three routing decisions per question, the gap between the lowest and highest compatible risk averages 5.3 percentage points per question when only per-candidate routing rates are released, and 1.5 points when pairwise statistics are added (Table 1). Under pairwise statistics the gap is zero on 482 of the 512 questions and is concentrated on the remaining 30, where the routing changes the selected answer.

(continued in 2/2)

AuthorsOpenReview ↗

Response to Reviewer vXbD (2/2): Contributions and revisions

Second difficulty: the failure rates must be estimated. The probability that a given retained state leads to a wrong final answer is generally unknown. It can only be estimated by restoring the saved reasoning state, letting the model continue, and checking the result. Each such continuation, including PRM scoring, took about 10 GPU-seconds on A100 GPUs in our runs, so the number of reruns is the natural measure of cost. The states that determine the worst case are typically rare and lie deep in the search. Each carries little probability, but there are many of them, and together they can change the risk.

Contributions.

  1. For a fixed selection rule, we characterize the exact range of failure rates consistent with the released routing statistics. Every value in this range is attained by a single valid router, not by combining incompatible ones.
  2. We determine how many paid reruns are needed to estimate the upper end of this range to accuracy ε. The answer depends on the balance between how many candidates are retained and how much routing information is released. Under pairwise statistics, retaining one candidate requires order 1/ε² reruns, retaining two adds logarithmic factors, and retaining three requires order 1/ε³ once the candidate pool is large.
  3. The main technical step, also noted by Reviewers D5j6 and i7bA, is to show that a single router can make rare states at many depths of the search important simultaneously. This is why the lower bound applies to an actual router rather than to a mixture of hypothetical ones. For pairwise and three-wise statistics, this router is a simple linear hash.
  4. We identify when the cost decreases: if the losses are close to the component already determined by the routing statistics, far fewer reruns are required.

Relevance to the ICLR community. Verifier-guided selection is now a standard way to allocate test-time compute in reasoning. Reliability figures for such systems are usually computed by parties with access to the whole pipeline. Our results show that the routing statistics actually released may not determine the risk, and that the number of costly reruns needed to resolve it can be computed in advance.

Revisions.

  • The abstract and introduction now begin with this LLM setting and the 25%-versus-0% example, before any notation is introduced.
  • Related work opens with a paragraph on verifiers and PRMs in LLM reasoning.
  • The introduction ends with the four contributions above.
  • To stay within nine pages, two technical passages in Sections 4 and 5 are now given as short summaries; their full statements already appear in Appendices D.12 and E.1.

We would be grateful to know whether the revised introduction and Section 2 make the problem clear, and which parts remain difficult to follow.

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

This paper studies auditing the downstream risk of a fixed verifier-guided selection mechanism under partial information about the routing law. Given low-order routing moments (e.g., k-wise independence) and paid access to fresh bounded continuation losses at selected retained records, the paper characterizes the worst compatible risk and the evidence (query) complexity needed to estimate it to accuracy ε with confidence 1−δ. The core contributions are: (i) a selector-specific reduction to a canonical “top-b” retained-record geometry; (ii) sharp counts and uniform tail capacity bounds for feasible records under moment constraints; (iii) a new simultaneous multiscale positive construction that places prescribed heavy records at all depth scales while matching specified moments; and (iv) matching (up to logarithms at the critical regime) lower/upper bounds on minimax query complexity for scalar risk estimation and interval identification, together with structured continuation results that reduce sample complexity when the loss lies near the fully identified class.

Critical strengths

The main technical strength is the simultaneous positive multiscale construction. Rather than combining separate single-scale witnesses—which would dilute the relevant mass—the paper constructs one globally nonnegative routing law that satisfies the prescribed low-order moments while supporting uniformly heavy records across many geometric depths. This construction enables minimax lower bounds on the complete feasible domain and leads to a clean acquisition-complexity phase transition at b=2\floorr/2b = 2\floor{r/2}, with matching rates away from the critical regime and only a logarithmic gap at criticality.

Critical weaknesses

Please refer to questions

Questions for authors

The paper states that an “acquisition-rate evaluation varies accuracy and candidate count under fresh responses,” but Appendix G mainly reports frozen-tree identification, saved-risk-table calculations, and a same-cache replay benchmark. Appendix G.4 also notes that the reported counts and tail bounds are “not measured fresh-response query budgets,” while the conclusion lists fresh-continuation scaling experiments as future work. Could you clarify what acquisition-rate experiment was actually performed? If none was run end to end, could you include a small live experiment that adaptively queries restored records, returns a faithful interval for specified (ϵ,δ)(\epsilon, \delta), and reports empirical coverage and query count as and vary?

1 comment
AuthorsOpenReview ↗

Response to Reviewer i7bA: Scope of the experiments, a correction, and additional checks

We thank the reviewer for checking the main text against Appendix G so carefully. The reviewer is correct. The page-9 sentence "Acquisition-rate evaluation varies accuracy and candidate count under fresh responses" describes an experiment that had not been run. The submitted experiments measure risk identification on saved losses, together with finite certificate checks and a same-cache timing comparison. In the revised PDF, the sentence now reads:

"Our finite experiments quantify risk identification using saved losses and verify finite routing constructions; the fresh-response acquisition rates in Section 4 are theoretical bounds."

We apologize for this error.

What the submitted experiment measures. Table 1 isolates the effect of missing routing information. The losses are held fixed on 512 MATH/GSM8K questions, and only the released routing statistics vary. The average per-question risk ambiguity falls from 5.273 pp with marginals only to 1.465 pp once pairwise statistics are added, and to 0.098 pp if one common router is shared across all questions.

Additional experiments. We added two experiments, both reported in the new Appendix G.6.

(a) Adaptive querying with simulated fresh responses. Each retained state was assigned a fixed failure probability, hidden from the auditor. Each query returned a new, independent pass/fail draw from the requested state. The adaptive auditor chose the next state based on its observations so far; the baseline allocated queries uniformly. Since the true probabilities were fixed by construction, every returned interval could be checked against the exact endpoints.

  • K = 8 candidate families, top-2 selection, endpoint tolerance ε = 0.10, δ = 0.05: adaptive allocation used 53,270 queries on average, against 151,552 for uniform allocation (64.9% fewer). Each method was run 120 times, and every returned interval of both methods satisfied the endpoint requirement.
  • K = 3: adaptive 16,082, uniform 14,336. With only seven retained states there is little room for prioritization, and the overhead of adaptive allocation is not recovered.

These results currently cover a single (ε, δ) setting. Since the responses are simulated, we will add a sweep over ε and δ in the final version, reporting empirical coverage and query counts, as the reviewer suggests.

(b) Adaptive querying on the actual pipeline. We repeated the K = 8 comparison with real responses. Each query restored a saved retained state, generated a fresh continuation with the actual generator, and scored it with both PRMs; the adaptive auditor chose each next state from these real outcomes. On 8× NVIDIA A100 80GB with ε = 0.10 and δ = 0.05:

AdaptiveUniform
Fresh queries57,552151,552
Wall-clock time (h)21.1251.71
GPU-seconds per query10.579.83

Adaptive allocation used 62.0% fewer queries and 59.2% less time. This run also confirms that the query interface can be implemented with the actual models.

How (a) and (b) complement each other. Verifying coverage requires the exact risk endpoints, and therefore the true failure probability of every retained state. With the actual models these probabilities are unknown, so (b) measures cost on the real system, while (a), where the probabilities are fixed by construction, checks coverage. The savings in (b) are close to those in (a) (62.0% versus 64.9% fewer queries).

Reviewer_D5j6OpenReview ↗
Rating
3
Confidence
1(−2)
Informativeness
1
Presentation
2(−1)
Soundness
2
Read review
Paper summary

The paper studies the problem of auditing verifier-guided search when the routing mechanism is only partially identified. There are kk candidate families each with a low and a high score. A routing mechanism selects one of the two scores for each family and a selector retains the top bb candidates. The auditor knows the scoring alternatives and the released routing statistics typically consisting of low-order moments and limited independence, but does not know the full joint routing distribution. The downstream loss associated with each retained record is unknown and is estimated through paid queries. Authors make use of two sources of uncertainty: (i) identification uncertainty via multiple routing laws being consistent with the released statistics. (ii) statistical uncertainty via the need to estimate unknown continuation losses.

Critical strengths

The theoretical development is ambitious and in particular the arguments in the proofs are sound and look rigorous to me. The reduction to a canonical selector geometry helps isolate the combinatorial structure underlying the acquisition problem. The construction itself is also interesting so that rather than establishing hardness separately at each scale, it seeks to construct a single feasible routing law that preserves substantial mass on rare events across multiple scales while satisfying the prescribed moment constraints.

Critical weaknesses

My main concern is the model access assumed for continuation queries. The auditor can request any legal retained record directly and obtain bounded response with conditional mean θt\theta_t. This is a strong assumption particularly when records correspond to rare events or internal states of a search procedure that may be expensive to reproduce. As I understand the model, the acquisition complexity counts the cost of the downstream response but does not account for the cost of generating, restoring or otherwise accessing the requested record. This is reasonable for an abstract oracle access, but it limits the direct interpretation of the resulting query complexity bounds in real-world auditing settings.

On the other hand, the analysis relies on released routing moments being known exactly. This is a natural starting point for characterizing the identified set, and the paper appropriately notes that estimated population moments require their own confidence set and error allowance. However, uncertainty in the released moments is not incorporated into the main acquisition complexity results. In practical applications, routing statistics may be estimated from finite logs, rounded, or released with additional noise.

Furthermore, the experiments provide a useful "unrealistic" illustration of partial identification by fixing the continuation loss and optimizing over routing laws compatible with different levels of released response. The main experiment uses three routing bits, yielding only eight assignments per question. This setting is well suited to exact optimization and illustrates the identification mechanism clearly but it doesn't directly test the principal asymptotic claims on the number of candidates, dept -dependent record masses, or the accumulation of difficulty across multiple scales.

Questions for authors
  • The paper constructs valid probability distributions satisfying the moment constraints. But can they be generated by finite hash families, pseudorandom functions, or realistic verifier-routing procedures with comparable complexity? If not, the minimax lower bound may be substantially more adversarial than the applications warrant.

  • What happens when the released moments themselves are noisy? Suppose the auditor receives estimates m^\hat m rather than exact mm with nn routing observations behind them. What is the joint minimax cost in routing log samples and continuation queries? I would expect an interesting interaction between statistical uncertainty in mm and continuation uncertainty in θ\theta.

  • What if the auditor cannot directly request a rare record? This assumption seems crucial. If the auditor can only observe records generated naturally by the router, the rare-record problem becomes an importance sampling problem.

  • What changes when bb depends on KK? The theory treats bb and rr as fixed. But in many search systems the number of retained candidates could grow. The entire phase diagram might change when bb is a function of KK

2 comments
AuthorsOpenReview ↗

Response to Reviewer D5j6: Access, Noisy Moments, Hash Realizability, and Scope

We thank the reviewer for the careful reading and for checking the proofs. Most of the questions concern whether the model is too favorable to the auditor. We address them in turn and state explicitly where the answer lies outside what we prove.

1. Direct access to rare records and its cost (W1, Q3). We agree that Theorem 2 counts only fresh continuations, not the cost of creating or storing a search state. In an LLM pipeline, requesting a record means reloading the saved prompt and partial reasoning and letting the model continue. We measured this cost. On 8× NVIDIA A100 80GB, with Qwen2.5-Math-1.5B-Instruct generating and both PRMs scoring, one fresh response cost about 10 GPU-seconds on average (10.57 and 9.83 GPU-seconds in the adaptive and uniform runs described in our reply to Reviewer i7bA). Building and storing the tree is a separate, one-time cost. Section 2 of the revision now states this distinction, and Appendix G.6 reports the measurement.

On passive logs: we agree that the problem becomes one of importance sampling, but here it can fail entirely rather than merely become expensive. Router A places probability 1/4 on each of 100, 010, 001, 111; Router B places 1/4 on each of 000, 011, 101, 110. Their one- and two-bit statistics coincide, yet A never produces 000. If the failure is concentrated at that record, no number of logs from A carries information about it, while B assigns it mass 1/4. Importance weighting requires positive logging probability wherever the estimand has support. Direct access is therefore a strong assumption, as the reviewer notes, but without it the worst compatible risk is not identifiable. This example is now included in Section 2.

2. Realizability by hash families (Q1). For moment orders two and three, the hard laws are realizable. Appendix C.5 constructs the multiscale law as a linear hash over GF(2): each routing bit is a fixed linear function of a uniform seed, with one additional seed bit for order three. This is the standard pairwise / 3-wise independent hash, with a seed of log₂K + O(1) bits. A single seed distribution matches the prescribed moments and makes the chosen rare records heavy at every scale simultaneously. For r ≥ 4, Theorem 1 provides a valid probability law, but we do not have a short-seed hash realization, and a particular deployed router may be more restricted. In that case the lower bound should be read as a statement about the full moment-compatible family, as the reviewer suggests.

3. Noisy released moments (W2, Q2). Proposition 27 (Appendix F.1) handles the composition. Given a confidence set M for the moments with coverage 1−δ_m, one optimizes over routing laws compatible with any moment vector in M and runs the fresh-response audit on this enlarged domain. If the audit is (ε_v, δ_v)-faithful there, its output is (ε_v + γ_rep + γ_m, δ_v + δ_m)-faithful for the true moments, where γ_m measures how much the moment uncertainty enlarges the set of record distributions. We do not have the joint minimax cost in the number of log samples n and continuation queries. We agree that this interaction is of interest. We expect noisy moments to give deep records more feasible mass and hence a heavier effective tail, but we have not established a rate. The revised conclusion lists this as an open question.

4. Experiments and the asymptotic claims (W3). We agree. Table 1 tests identification only: losses fixed, routing information varied, three bits. It is not a test of the rates, and we have corrected the page-9 sentence that suggested otherwise. During the rebuttal we added finite experiments with fresh responses (details in our reply to Reviewer i7bA). At K = 8, top-2, ε = 0.10 and δ = 0.05, adaptive allocation used 64.9% fewer queries than uniform allocation in simulation, where all 120 runs of each method met the target, and 62.0% fewer on the actual pipeline (57,552 vs 151,552 fresh responses on 8× A100). At K = 3 adaptive allocation was slightly worse in simulation. This illustrates the allocation effect at small K. It does not verify the dependence on K or the multiscale accumulation; for these, the lower-bound construction remains the evidence.

5. Growing b (Q4). Theorem 2 fixes b and r, and its constants depend on b. The finite-K formulation remains valid for any (K, b), but the fixed-b phase diagram does not give a rate for b = b(K). Heuristically, the record-count exponent grows with b while the tail exponent ⌊r/2⌋ is fixed by the release, so a growing b with fixed r eventually enters the b > 2⌊r/2⌋ regime. Making this precise requires tracking the dependence of the constants on b, which we have not done. The revised conclusion states this as an open question.

I thank the authors for their rebuttal.

My first concern remains unanswered: How is realizability defined? I couldn’t find a formal definition in the main paper despite its relevance to the statements made in Theorem 2 which is important for understanding the assumptions under which the theoretical results hold.

My second question was also not addressed. Records may be generated from different distributions, potentially with different regions of concentrated probability mass. What assumptions, if any are made about these underlying generative distributions? In particular, line 131 refers to an "unconstrained distribution", but this notion was not formally introduced.

Regarding the table provided in response to Reviewer i7bA, reporting only the number of queries does not show the effectiveness of the proposed approach. In particular, the table does not show how the estimation error evolves as a function of the query budget. Without this information, it is difficult to assess whether increasing the number of queries is equivalent to a good estimation accuracy. The conclusions drawn from these results seem rather premature. Uniform sampling is a relatively weak baseline, and comparing against it alone does not provide particularly convincing evidence of the advantages of the proposed weighted sampling strategy.

I would also like to clarify something about my initial assessment to the authors. My weak accept score may have been overly generous and I apologize if it conveyed a positive evaluation of the current draft than I intended. I genuinely struggled to follow several parts of the paper, particularly because important definitions, assumptions, and explanations were missing. In several passages, understanding the mathematical statements required me to infer assumptions that were not explicitly stated by the authors. For example, in Section 2 notations in the problem formulation are not properly introduced, I had to assume that RR referred to expected regret and that θt\theta_t represented risk rather than loss. The sum exchange in equation (1) is also wrong. Similarly, equations in lines 301 and 450 among other passages are presented without sufficient explanation or mathematical context, making it difficult to understand their purpose.

Despite these concerns, I did have a positive perspective in the proposed setting of weighted sampling for verification under regret-based objectives. I found this direction interesting particularly from the perspective of theoretical sample complexity. although I am less convinced about the experimental novelty. However, I believe the draft requires substantial revision before it so I maintain a weak positive recommendation but with lower confidence given the unresolved questions.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.