- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper studies reliability certification for randomized generation systems with ordering-dependent performance. For a fixed evidence state and ordering , let $ Q=q_\pi=\Pr{g(Y)=1\mid \pi} $ denote the conditional probability that a sampled output passes a binary verifier. The primary service target is the fresh-draw success probability $ \mathbb{E}[Q]>p_\star. $ The paper first characterizes when thresholding a nonlinear surrogate mean can certify this target. It shows that the largest distribution-free safe cutoff is the lower convex envelope of evaluated at , and that the exact equivalence $ \mathbb{E}[\phi(Q)]<c \quad\Longleftrightarrow\quad \mathbb{E}[Q]>p_\star $ for every ordering distribution is possible if and only if is strictly decreasing and affine.
The paper then considers finite verifier depth, where $ S_j\mid Q_j\sim \operatorname{Binomial}(n,Q_j). $ It proves that, at fixed , the count distribution identifies over arbitrary mixing distributions if and only if is a polynomial of degree at most . The paper supplements these results with restricted-family calibrations, sequential tests, variance decomposition, jackknife bias correction, controlled simulations, and a Qwen/EvalPlus audit.
Critical strengths
-
The paper cleanly separates target mismatch from measurement error: a surrogate may target the wrong population functional even with infinite data, while finite verifier depth creates an additional identifiability problem.
-
The main results are sharp and interpretable. In particular, the affine-score characterization gives a strong necessary-and-sufficient condition rather than only a conservative sufficient condition.
-
The fixed-depth identifiability theorem provides useful guidance for clustered evaluation design: increasing the number of orderings cannot recover a general nonlinear functional when the within-ordering depth remains fixed.
-
The paper is appropriately careful about the scope of its experiments and does not interpret controlled probability laws or a single-checkpoint audit as evidence of broad prevalence.
-
Critical weaknesses
see questions
Questions for authors
-
Validation of restricted-family assumptions. The restricted-support and fixed-shape results recover substantially stronger, and sometimes lossless, nonlinear calibration. However, their practical value depends on validating assumptions such as $ Q\in[a,b] $ or , where is the latent ordering-specific success probability rather than an observed bounded score. Could the authors provide a concrete statistically valid protocol---such as sample splitting, simultaneous guarantees across tasks, or sensitivity analysis under support violations---for learning or validating these assumptions? In the Appendix~N audit, how often would such restrictions be accepted, and how much completeness gain would remain after accounting for calibration uncertainty?
-
Constructive estimation after Theorem 3.
Theorem~3 establishes non-identifiability of nonpolynomial functionals at fixed verifier depth, but practitioners still need an actionable approximation strategy. Could the authors characterize at least one regime in which increases with the number of orderings , together with a sieve or Bernstein-polynomial estimator whose approximation and sampling errors are both controlled? Under a fixed verifier budget $ B=Kn, $ how should one allocate between and , and how should misspecification risk be audited when using a parametric mixing family?
-
End-to-end experimental validation.
Could the authors include a minimal end-to-end RAG or agent experiment using the direct Bernoulli e-process, rather than only probability-law simulations and the code-generation audit? It would be useful to report certificate coverage, verifier-call cost, and decision latency at realistic thresholds such as $ p_\star\in{0.8,0.9,0.95}, $ and to compare the direct certificate with a nonlinear-score gate under the same ordering law and evaluation budget. Such an experiment would clarify when ordering heterogeneity is operationally meaningful and how large the target-induced efficiency gap is in a realistic workflow.
Response to Reviewer tAQm: Qualification, Completeness, Misspecification, and End-to-End Certificate Evaluation
Response to Reviewer tAQm
We thank the reviewer.
1. Qualification and completeness
Appendix E (Eqs. 32–35) replaces hard support with simultaneous tail-mass and mean-success bounds. Binomial detection controls out-of-interval mass in nonlinear calibration. Qualification meets tolerances, not exact support. Fixed-shape compatibility is diagnostic; lossless calibration needs an independently justified exact family or a conservative misspecification adjustment.
For clipped log, fix δ≤a<p⋆<b≤1−δ, protecting selection. Equation (35) gives
Uμ<cu⋆(p⋆)⟹mL>p⋆.
Here mL uses one fresh verifier bit per ordering. The secant obeys Sa,b(p⋆)≥u(p⋆)≥cu⋆(p⋆); tail penalties are nonnegative and the cap exceeds the cutoff. Therefore, the tail-corrected gate is contained in the affine gate using the same mL. Its gain is over unrestricted nonlinear, not affine calibration. Shared data require joint error allocation; completions are not ordering draws.
The Qwen audit uses 50 tasks × 100 orderings × 200 generations, original targets and common budgets including qualification/calibration. Interval, detection and family selection are independent or protected on a finite grid; confidence allocation spans all comparisons. The nonlinear baseline remains unrestricted. Identity pooling alters the model, outside Theorem 3's count-only obstruction.
At targets 0.5/0.7/0.9, counts (of 50) are: tail-qualified 34/25/12; fixed-shape-compatible (diagnostic) 37/33/28; affine certificates 31/18/6; unrestricted nonlinear 18/8/1; tail-corrected 26/14/4. Reference-qualified safe subsets contain 35/22/8 tasks. Within these, tail-corrected completeness exceeds unrestricted nonlinear by 22.9/27.3/37.5 percentage points, but trails affine by 14.3/18.2/25.0. Issued sets lie within these subsets; only containment in affine is theoretical. Reference qualification is incomplete and separately budgeted.
2. Increasing-depth estimation
Proposition 7 (Appendix P): For independent Qk∈[0,1], Sk∣Qk∼Bin(n,Qk), and μ=K−1∑kϕ(Sk/n), a bounded Lϕ-Lipschitz score of range Rϕ satisfies, with probability 1−δ,
∣μ−Eϕ(Q)∣≤2nLϕ+Rϕ2Klog(2/δ).
Binomial variance bounds bias and concentration bounds sampling error; both vanish as n,K→∞. For B=Kn, balancing this bound gives n=Θ(B), not optimality. Clipped log qualifies, unlike unclipped log near zero. Appendices H–J concern adaptive inverse-binomial sampling. Fixed-depth fits need misspecification analysis; counts cannot identify nonpolynomial scores.
3. Fixed-depth misspecification
At depth 200, a frozen parametric gate was evaluated in 200 independent repetitions per law, all with EQ≤p⋆. Compatibility / mean absolute nonlinear-score error / false certificates on unsafe laws:
Compatibility/error use all repetitions; false certificates concern only the parametric gate. Theorem 3 allows identical fixed-depth counts yet different nonlinear-score means, with equal mean success. Not every family member has such an alternative; mean certification remains possible. Neither nonrejection nor these tests establish arbitrary-misspecification robustness.
4. End-to-end certificates
The Qwen audit is not an end-to-end RAG/agent study. New Table O.1 (Appendix O) compares 100 paired programming tasks at p⋆=0.90, under 2,000 calls/task including calibration/decision. 0.05/300 per gate–task, split across components, gives union-bound control. Latency includes generation and verification.
Cohort: 50 HumanEval+ and 50 MBPP+ tasks, SHA-256 ranks 32–81; disjoint from audit ranks 1–25 and cards 26–31. Appendix N's model, tokenizer, EvalPlus, cards, ordering law, decoding and verifier are fixed; BF16 generation uses one A100-80GB.
Certificates / mean calls/task / mean latency: fresh-bit direct e-process 62% / 1,010 / 11.8 s; tail-corrected nonlinear 46% / 1,440 / 17.6 s; identity-pooled nonlinear 49% / 1,570 / 19.2 s. Nonissuance does not imply failure.