- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper introduces Foveal Search, a sequential method for deciding whether the mean label of a fixed finite corpus exceeds a threshold when reference labels are costly but multiple inexpensive proxy predictions are available for every item. The method uses each acquired label both to update decision evidence and to learn a variance-reducing linear combination of proxies, and refits the combination at geometrically spaced checkpoints. It combines learned and fixed proxy controls through sequential e-value processes, enabling anytime stopping while retaining a full-verification fallback. The main theoretical contributions are finite-sample decision-error control without assumptions on proxy quality, a bound showing that learning the proxy combination adds at most logarithmic cumulative-variance overhead at fixed proxy rank, and sufficient conditions for correct completion within a label budget and for expected label savings. Validation includes rare-evidence synthetic experiments, two real datasets, held-out proxy-weight ablations, and additional multi-proxy studies. Foveal often reduces label use relative to label-only controls while maintaining high observed correct completion. However, some prediction-powered baselines are cheaper in favorable regimes, empirical gains are setting-dependent.
Critical strengths
This paper is theoretically solid. By combining variance reduction with sequential betting and e-processes, it establishes finite-sample decision-error control, proves that learning the proxy combination incurs at most logarithmic cumulative-variance overhead when the proxy rank is fixed, and derives sufficient conditions for correct completion within a given label budget and for expected label savings.
Critical weaknesses
-
The paper’s novelty is not sufficiently established. Although sequential betting and e-processes are discussed in the Related Work section, the paper does not clearly explain why these tools are essential to the proposed method or precisely distinguish its theoretical contributions from existing results. Consequently, it remains unclear which results are genuinely new and which follow from combining established techniques, weakening the paper’s methodological contribution.
-
The empirical results do not demonstrate a sufficiently compelling advantage over existing methods. Foveal mainly improves upon label-only baselines, while some prediction-powered baselines require fewer labels in favorable regimes. Moreover, the gains from learning separate proxy weights are relatively modest and vary across settings.
-
Besides, the paper is not sufficiently self-contained. Several citations, including those in the Introduction, are not hyperlinked, making the relevant literature unnecessarily difficult to trace. More importantly, essential proofs and technical details are relegated to a separate supplementary appendix rather than included in the main PDF.
Questions for authors
-
What motivates the use of sequential betting and e-processes for this problem? In particular, what advantages do they provide over alternative anytime-valid or prediction-powered inference methods?
-
Under what conditions is Foveal expected to outperform the strongest prediction-powered baselines, and why is it more expensive in some favorable regimes?
-
Do the sufficient conditions for label savings hold in either real-data experiment? Connecting the theoretical guarantees to the observed costs would clarify whether the theory provides meaningful practical predictions.
7 comments
Response to Reviewer cGtL (2/6): W1 and Q1 continued, label-cost guarantees and why sequential betting
W1 and Q1, continued: label-cost guarantees and why sequential betting
- Theorems 2 and 3: sufficient budgets and expected total cost for the complete DEFAULT policy. Theorem 2 gives an explicit sufficient-budget condition, Eq. (15), under which and , with separate tolerances for decision error () and missed deadlines (). Theorem 3 gives \min\\!\left\\{N,\frac{A_j(\delta)+\lambda_j^2B_N} {\lambda_jd-\lambda_j^2(d^2+\sigma_*^2)}\right\\},$$ for an included fixed-fraction learned-control component with an admissible betting fraction and positive denominator. Here $d=|\mu-\tau|>0$, $\lambda_j$ is its betting fraction, $p_j$ its prior weight, and $A_j(\delta)=\log(2/(\delta p_j))+\log(3/2)+1$. These results go beyond controlling error at a stop or expected evidence at a fixed horizon: they bound the paid labels needed to complete verification, including all labels used for fitting. The analyzed component already belongs to DEFAULT, and the proof tracks it until DEFAULT stops, whichever component or logical rule triggers termination. $T_0$ denotes the prescribed process with exact fits, certified evidence arithmetic, and no numerical recovery; Eq. (18) separately accounts for recovery with a justified failure-probability bound. Neither the finite-population confidence sequences of Waudby-Smith and Ramdas (2020; 2024) nor the prediction-powered e-process analysis of Csillag et al. (2025) supplies the stopping-time calibration analysis required for these explicit guarantees on the full cost of learning the proxy weights and completing verification.
The revision also makes the tradeoff for separate proxy weights explicit. For a nested scalar control with positive drift, Eq. (20) shows that the vector control has a smaller uncapped cost certificate exactly when Here is the scalar certificate, is the reduction in oracle residual variance, is the increase in calibration factor, and is the checkpoint accumulation factor in Eq. (12). With the same component, prior, and fitting schedule, this compares the accumulated variance benefit with the additional cost of fitting. The conclusion compares cost certificates, not realized costs.
Why these guarantees do not follow immediately from generic online-learning results. Appendix C makes the connection explicit: a pathwise regret bound valid simultaneously over every prefix can imply a stopped-variance bound for the learner it analyzes. Online Newton Step (ONS) and Exponentially Weighted Online Optimization (EWOO) have such guarantees for their own update rules. Those results do not transfer to Foveal Search’s proxy-weight learner, which uses exact constrained quadratic fits at doubling checkpoints and can incur linear regret on an unfavorable query order. The logarithmic cumulative-variance allowance in Theorem 1 instead follows from this learner’s expected calibration error under uniform sampling without replacement. This bound on expected accumulated evidence variance through a data-dependent stop is the learner-specific result used in Theorems 2 and 3 to prove the bounds on completion budgets and expected total label cost.
Why use sequential betting? It provides a direct connection between adaptive fitting, finite-sample correctness, and label cost. Each label updates evidence with coefficients fixed before that label is revealed, then contributes to fitting the coefficients used for future queries. The finite-population correction satisfies despite these updates. Nonnegative betting factors therefore preserve error control during refitting and repeated checking, while their log growth exposes the residual-variance term controlled by Theorem 1. This is the mechanism that converts improved proxy combinations into the completion bounds above.
Unlike a fixed-time PPI guarantee alone, the sequential construction justifies checking after every acquired label without fixing the final labeling budget in advance. It also gives finite-sample protection when informative labels are rare, without requiring a nondegenerate estimated variance or an asymptotic approximation. Proposition 2 identifies a specific failure of the power-tuned asymptotic PPI-CS comparator: an initial sample containing no positive labels can produce the incorrect singleton interval . Other finite-sample anytime-valid methods, including suitable confidence sequences and prediction-powered e-processes, can also protect against optional stopping. Our contribution relative to those methods is the explicit calibration and total-cost analysis for this learner.
Response to Reviewer cGtL (3/6): Q3, certified savings on the original datasets
Q3: Do the cost bounds certify savings on the original datasets?
Do the sufficient conditions for label savings hold in either real-data experiment? Connecting the theoretical guarantees to the observed costs would clarify whether the theory provides meaningful practical predictions.
Yes. The revised analysis certifies expected label savings for the unchanged DEFAULT policy on both original real-data datasets: at least 50.3% on Housing and 6.9% on Hypothyroid. The expectation is over uniformly random verification orders of each fixed corpus. Every acquired verification label is counted, including labels used to fit the proxy weights.
Connecting the theoretical guarantees to the observed costs. The table compares the certified expected savings with the observed mean savings, each relative to labeling the entire corpus. It includes the two original datasets, whose data and predictors follow Gu et al. (2026) for Housing and Brawand et al. (2026) for Hypothyroid, and the three additional LLM-judge corpora from the Chatbot Arena release of Chatzi et al. (2024).
| Dataset | Corpus size | Upper bound on expected labels | Certified expected saving | Observed mean labels | Observed mean saving |
|---|---|---|---|---|---|
| Housing | 5,160 | 2,561.32 | At least 50.3% | 1,076.56 | 79.1% |
| Hypothyroid | 145 | At least 6.9% | 103.06 | 28.9% | |
| Arena, Vicuna | 2,403 | 2,016.24 | At least 16% | 698.44 | 70.9% |
| Arena, Koala | 2,273 | 499.62 | At least 78% | 90.38 | 96.0% |
| Arena, OASST | 1,981 | 266.58 | At least 86% | 36.14 | 98.2% |
Observed means average 16 query orders on Housing and Hypothyroid (Appendix J.3, Table 14), and 64 on each Arena corpus (Table 2). The certificates concern under the paper's exact-fitting and certified-arithmetic assumptions, without numerical recovery.
For the two original datasets, the new certificates come from stopping rules already included in DEFAULT. Theorem 3's fixed-fraction bound alone gives the census cap on both datasets; Corollaries 2 and 3 establish the expected savings above.
Housing. Even with a normalized decision margin of only about 0.0093, Corollary 3 obtains a nontrivial bound by analyzing an existing range-adaptive component with a fixed proxy control. The proof bounds its changing betting fractions over possible verification histories and establishes , guaranteeing at least 50.3% expected savings. This applies to the complete DEFAULT policy, including all labels acquired while its learned components are fitted. The observed mean is 1,076.56 labels, corresponding to 79.1% savings (Section 5.4, Appendix K.5).
Hypothyroid. Corollary 2 uses the existing logical stopping rule. The corpus contains 78 negative labels among 145 items, with threshold . Once 73 negative labels have been acquired, the remaining labels cannot change the negative verdict. Under uniform random ordering, the expected position of the 73rd negative label is . DEFAULT stops no later than this logical rule, giving at least 6.9% expected savings. Its observed mean is 103.06 labels, or 28.9% savings (Appendix A.9).
Additional LLM-judge corpora. On the three Arena corpora, Theorem 3 with the finite-population refinement in Appendix A.5 gives the certificates shown above. These certify expected savings of at least 16%, 78%, and 86%; the observed mean savings are 70.9%, 96.0%, and 98.2%, respectively. Across these five evaluated corpora, the ordering by certified saving percentage agrees with the ordering by observed mean saving percentage (Appendix A.9).
A direct comparison for the logical stopping rule. Corollary 2 also gives the analytic expected cost of using logical stopping alone, which we can compare with that rule's measured cost. In the four rare-error settings where the batch should be rejected, the expected costs are approximately 262.4, 255.4, 512.7, and 505.5 labels, averaging 384.0. The observed mean for logical stopping alone is 384.7 labels; the complete DEFAULT policy uses 260.9 labels on the same runs (Table 35). This comparison links the analytic calculation to the measured cost of the specific rule it analyzes. Across the broader 18 rejection settings, the same corollary certifies expected savings of 19% to 50% (Appendix A.9).
Response to Reviewer cGtL (1/6): W1 and Q1, what is new
We thank the reviewer for the detailed comments on novelty, the comparison with existing methods, and presentation.
W1 and Q1: What is new, and why use sequential betting?
The genuinely new results are the label-cost guarantees, and the new part of the proposed method is that the labels that decide when verification stops also fit the proxy weights. Among related approaches, finite-population betting confidence sequences (Waudby-Smith and Ramdas, 2020; 2024) give anytime-valid inference when a fixed corpus is sampled without replacement. Prediction-powered e-processes (Csillag et al., 2025) keep that validity when the predictor changes as labels arrive. Foveal Search differs from both in the new label-cost guarantees it establishes. Specifically, Foveal Search bounds the number of labels that verification needs while the proxy weights are fitted from those same labels. For fixed proxy rank, Theorem 1 bounds the fitting contribution to expected cumulative evidence variance by an allowance that grows at most logarithmically with corpus size, through any data-dependent stopping time. An explicit label budget then suffices for a correct verdict with a stated probability (Theorem 2), and the expected number of labels, counting every label used for fitting, has an explicit upper bound (Theorem 3).
Relative to these two approaches, the new contributions are: