acceptodds
Under review as a conference paper at ICLR 2027

Foveal Search: Learning Proxy Combinations for Certified Corpus Decisions

Abstract

LLMs make it possible to draw nuanced conclusions from large collections of unstructured records. But using an LLM to judge every record is costly, especially when the goal is only an overall conclusion. Cheaper signals can be obtained for the entire collection, yet relying on them alone risks drawing the wrong conclusion. Foveal Search addresses this gap by acquiring a limited number of reference judgments and making each one serve two purposes: it contributes immediately to the decision and helps determine how to combine the cheaper signals for future judgments. The method guarantees a prescribed level of decision error even when those signals are poor. We also show when the information gained from learning their combination can outweigh the judgments spent learning it, with bounds that count every acquired judgment. Across evaluated settings, Foveal Search often uses fewer judgments than methods that ignore the cheaper signals while maintaining high observed correct completion. On held-out data, learning separate weights for the signals saves 3.0% and 4.6% of judgments compared with learning one weight for their average. Source Code: https://anonymous.4open.science/r/30228

Primary area:
learning theory
Keywords:
Likelihood calibration, Certified stopping, Query complexity

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_cGtLOpenReview ↗
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
  1. 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.

  2. 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.

  3. 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
  1. 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?

  2. Under what conditions is Foveal expected to outperform the strongest prediction-powered baselines, and why is it more expensive in some favorable regimes?

  3. 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
AuthorsOpenReview ↗

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 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.

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?

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:

  • Method: a concrete learning rule whose calibration cost can be quantified. The general permission to update a predictor does not specify how quickly a particular predictor improves. Foveal uses the known full-corpus proxy covariance and estimates only proxy-label cross-moments, with a constrained quadratic fit at doubling checkpoints. For binary labels, this yields the explicit finite-population excess-risk bound \le \frac{N-k}{k(N-1)} \left(\frac r4-b^\top G^\dagger b\right)$$ for a uniform subset of size $k$ (Eq. (11), Appendix A.2). Here $G$ is the proxy covariance, $b$ the proxy-label cross-moment, $r=\operatorname{rank}(G)$, and $\sigma_*^2$ the residual variance of the best fixed coefficient in the declared constraint set. This quantifies the fitting error that an evolving-predictor growth bound would otherwise leave as an input, and remains valid with singular $G$.
  • Theorem 1: control of that fitting cost through a label-dependent stop. The additional result beyond the earlier validity guarantees and the fixed-sample growth bound of Csillag et al. (2025), which takes prediction error as given, is \le \sigma_*^2\mathbb{E}[T]+B_N, \qquad B_N\le \frac{1+r\lceil\log_2 N\rceil}{4},$$ for the exact-fit doubling learner and every observation-based stopping time $1\le T\le N$, where $v_t$ is the conditional variance of the evidence correction. Thus fitting the weights has an explicit cumulative-variance allowance that grows only logarithmically with corpus size at fixed proxy rank. This allowance is not itself a number of extra labels; Theorems 2 and 3 use it to prove explicit bounds on the labels needed for correct completion and on the expected total label cost.
AuthorsOpenReview ↗

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 Pr⁡(T0>t)≤η\Pr(T_0>t)\le\eta and Pr⁡(a^0=a, T0≤t)≥[1−δ−η]+\Pr(\widehat a_0=a,\ T_0\le t)\ge[1-\delta-\eta]_+, with separate tolerances for decision error (δ\delta) and missed deadlines (η\eta). 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 (Cs−1)Δ>Δχ,ΞN.(C_s-1)\Delta>\Delta\chi\\,\Xi_N. Here CsC_s is the scalar certificate, Δ=σs2−σ∗2\Delta=\sigma_s^2-\sigma_*^2 is the reduction in oracle residual variance, Δχ=χ−χs\Delta\chi=\chi-\chi_s is the increase in calibration factor, and ΞN\Xi_N 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 E[Dt∣Ft−1]=μ−τ\mathbb{E}[D_t\mid\mathcal F_{t-1}]=\mu-\tau 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 0\\{0\\}. 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.

AuthorsOpenReview ↗

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).

DatasetCorpus sizeUpper bound on expected labelsCertified expected savingObserved mean labelsObserved mean saving
Housing5,1602,561.32At least 50.3%1,076.5679.1%
Hypothyroid14510658/79<13510658/79<135At least 6.9%103.0628.9%
Arena, Vicuna2,4032,016.24At least 16%698.4470.9%
Arena, Koala2,273499.62At least 78%90.3896.0%
Arena, OASST1,981266.58At least 86%36.1498.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 E[T0]\mathbb{E}[T_0] 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 E[T0]≤2561.32\mathbb{E}[T_0]\le2561.32, 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 1/21/2. 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 73(145+1)/(78+1)=10658/79<13573(145+1)/(78+1)=10658/79<135. 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).

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

This work considers the problem of resolving queries over a corpa of documents in a cost effective manner. Cheap verification may be erroneous and using more robust approaches may be too costly. They propose a clean theoretical model for this problem and define a δ\delta approximately correct notion for answering this query. Essentially, each document has some full verification cost (which reveals the true label) and some proxy vector which can be arbitrarily correlated with the true label. The proxies are known up front, so every time we learn a real label, we learn how the proxy mean relates to the true mean. They provide a suite of theoretical results within this framework, as well as empirical validation.

Critical strengths

I am positive about the paper. The problem is well define and the authors do a good job of defining a tractable theoretical model that captures the essence of the problem while allowing rigorous investigations. The algorithm construction is neat and given the fixed corpus, the proxy covariance is known from the full table, so labels only estimate the proxy–label cross-moment b. They also handle the fact that stopping depends on labels, so the prefixes you condition on aren’t uniform.

Critical weaknesses

My main weakness is that core justification of the work is around LLM verification of document sets. But the empirical validation is done on tabular data. The biggest improvement to the paper would be to prototype a way to port this algorithm to an LLM based workflow.

Questions for authors

See weakness above.

3 comments
AuthorsOpenReview ↗

Response to Reviewer VCfU (1/3): W1 and Q1, the LLM datasets

We thank the reviewer for the suggestion to prototype a port of the algorithm to an LLM-based workflow, which the revision now includes.

W1 and Q1: Porting Foveal Search to an LLM verification workflow

My main weakness is that core justification of the work is around LLM verification of document sets. But the empirical validation is done on tabular data. The biggest improvement to the paper would be to prototype a way to port this algorithm to an LLM based workflow.

See weakness above.

We ported Foveal Search to an LLM verification workflow and evaluated it on LLM datasets of text documents, in addition to the tabular data of the original submission. We provide pairwise comparisons of chatbot responses, step-by-step reasoning traces, solutions to math problems, and restaurant reviews. The algorithm is unchanged, and the workflow code, the scoring prompts and model versions, and the archived LLM outputs are in the anonymous repository.

The new LLM datasets (Section 5.2, Appendix M). In every dataset the items are texts, the proxies are LLM judgments of each text, and the reference label is the expensive judgment that Foveal Search acquires one at a time.

DatasetDocumentsReference labelLLM proxiesDecisionIn the paper
Chatbot Arena2,403, 2,273, and 1,981 pairwise comparisons of chatbot responses for Vicuna-13B, Koala-13B, and OASST-Pythia-12BHuman voteVerdicts of GPT-4, Claude 3 Opus, and GPT-3.5Does the model win more than half of its comparisons?Table 2
PRM800K and ProcessBenchBatches of 250, 500, or 1,000 step-by-step reasoning tracesEvery step is valid (benchmark annotation)Four open LLM judges, two prompts eachDoes the share of invalid traces exceed 2% or 5%?Figure 1, Appendix M.3
ProcessBench (workflow prototype)125 reasoning tracesThe entire trace is validOne local LLM, three promptsDoes the share of valid traces exceed 1/4, 1/2, or 3/4?Appendix M.2
MATH solutions256 solutions to 243 problemsEvery step is validFour open LLM judges, two prompts eachAre more than half of the solutions valid?Appendix M.4
Yelp restaurant reviews5,888 reviews of 30 restaurantsThe review reports a hygiene issue (votes of two LLMs)Four open LLM judges, two prompts eachDo more than 5% of a restaurant's reviews report an issue?Appendix M.6

For Chatbot Arena we follow Chatzi et al. (2024), whose public release pairs the human votes with the verdicts of the three LLM judges on the same comparisons. The reasoning traces and their step-level annotations come from PRM800K (Lightman et al., 2024) and ProcessBench (Zheng et al., 2024). The MATH solutions are the MATH subset of ProcessBench, and the restaurant reviews and their reference labels come from the Yelp portion of the review benchmark of Yeh et al. (2026). The four open judges are Qwen3-4B, Qwen3.5-2B, Qwen3.5-4B, and Llama-3.1-8B-Instruct.

AuthorsOpenReview ↗

Response to Reviewer VCfU (2/3): W1 and Q1 continued, results on the LLM datasets

W1 and Q1, continued: results on the LLM datasets

Results on the LLM datasets (Section 5.2).

  1. Chatbot Arena with human reference judgments (Table 2). Human votes supplied the reference labels, and judgments from GPT-4, Claude 3 Opus, and GPT-3.5 supplied the proxies. On Vicuna-13B, Koala-13B, and OASST-Pythia-12B, Foveal Search returned the correct verdict on all 64 query orders per corpus and used 39%, 23%, and 8% fewer human reference labels than EB-CS (Waudby-Smith and Ramdas, 2020), respectively. Relative to labeling every item, the refined Theorem 3 certificates guarantee expected label savings of at least 16%, 78%, and 86% under exact fitting and certified arithmetic for the prescribed no-interruption process (Appendix A.5).

  2. Held-out verification with rare errors (Figure 1, Appendix M.3). Four local LLM judges supplied proxy scores. Each run tested whether the fraction of invalid reasoning traces in a batch exceeded a specified threshold. Foveal Search returned the correct verdict in all 1,024 runs. For batches of 500 and 1,000 traces, it averaged 298.5 and 439.9 reference labels, saving 31% and 41% relative to EB-CS. The lowest-cost PPI++-CS variants (Kilian et al., 2025) incorrectly accepted 21 of 128 batches that should have been rejected in one setting and 24 of 128 in the other at τ=0.02\tau=0.02. Their lower label cost therefore came with incorrect verdicts.

  3. Held-out MATH solutions with four LLM judges (Appendix M.4). We selected two banks of three proxy columns on 705 development examples and froze both selections before evaluating them on a separate 256-item MATH corpus. With judges of uneven quality, Foveal Search averaged 121.77 reference labels versus 126.33 for matched F-Scalar. With judges selected for complementary errors, it averaged 121.70 versus 125.64. Both methods returned the correct verdict on all 64 query orders for each bank. The observed mean savings over F-Scalar were 3.6% and 3.1%, respectively. Both adjusted intervals included zero.

  4. Restaurant reviews at natural prevalence (Appendix M.6). Each batch is the set of reviews of one restaurant. Foveal Search and EB-CS returned the correct verdict in all 480 runs, and Foveal Search used fewer labels in each group of restaurants.

AuthorsOpenReview ↗

Response to Reviewer VCfU (3/3): W1 and Q1 continued, the workflow from raw text to a verdict

W1 and Q1, continued: the workflow from raw text to a verdict

The prototype shows each step of the port on 125 ProcessBench traces (Appendix M.2). It takes raw reasoning traces as input, uses an LLM to score each trace, and sequentially reveals reference labels until Foveal Search can decide whether the fraction of valid traces exceeds a specified threshold. In a prespecified ProcessBench run, Foveal Search, with no change to the algorithm, correctly concluded that at most half of the 125 traces were valid after revealing 54 reference labels (Section 5.2, Table 28).

From raw text to proxy scores. The prototype uses 125 ProcessBench problems, each with a written reasoning trace. A local Qwen3.5-4B model scores each trace under three fixed prompts. The first assesses overall correctness, the second checks whether every step is valid, and the third identifies the first erroneous step. These 375 prompt evaluations yield three proxy scores per trace. The benchmark reference label is 1 if the entire trace is valid and 0 otherwise. In the full corpus, 41 of the 125 traces are valid. We count each revealed benchmark annotation as one reference label and do not count proxy scoring as label cost.

From proxy scores to a corpus verdict. Foveal Search runs without modification. It first computes the covariance of the proxy scores, which are available for every trace before verification begins. It then reveals reference labels one at a time in uniformly random order. Each reference updates the decision evidence using weights fixed before that reference was revealed. At checkpoints where the sample size doubles, the algorithm refits the weights using the references observed so far and applies them to subsequent queries. It stops when the evidence determines the corpus verdict at the prescribed error level.

Table 27 maps each algorithm component to its step in the workflow. Table 28 excerpts the prespecified run at τ=1/2\tau=1/2, from its first calibration fit to its stopping point at label 54. The released trace includes all three proxy outputs, every revealed reference, the weights used for subsequent queries, and the final verdict. The original problem and solution text is not redistributed.

Prototype results (Appendix M.2). Foveal Search and label-only EB-CS both returned the correct verdict on all 16 query orders at each threshold. EB-CS provides the same error guarantee. The table reports the mean number of reference labels acquired.

Valid-trace thresholdFoveal SearchLabel-only EB-CSMean label savings vs. EB-CS
τ=1/4\tau=1/488.31108.6318.7%
τ=1/2\tau=1/254.4464.1915.2%
τ=3/4\tau=3/412.8122.6943.5%

At τ=1/4\tau=1/4, Foveal Search reached the correct verdict on all 16 query orders, compared with 9 of 16 for PPI++-CS. PPI++-CS used fewer labels at τ=1/2\tau=1/2. F-Scalar, which learns one coefficient for the average of the three prompt scores, used slightly fewer labels than Foveal Search at every threshold. Thus, a shared weight was sufficient to capture the proxy benefit in this prototype.

In summary, the revised paper validates Foveal Search on LLM verification of document sets and no longer on tabular data alone, and it includes the requested prototype that ports the algorithm to an LLM-based workflow. The workflow code, the scoring prompts and model versions, the batch construction procedure, the archived LLM outputs, and the complete stopping trace are available in the anonymous repository.

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

Foveal Search makes certified threshold decisions (is the corpus mean μ above τ?) over a fixed finite corpus with expensive labels and known proxy vectors. It samples uniformly without replacement and uses each label first as evidence, then to refit proxy weights. Error control holds for any predictable proxy weights; the main result is an excess-variance bound for an exact-fit doubling-checkpoint learner with known proxy covariance, carried through data-dependent stopping to correct-completion and expected-label-cost guarantees. Experiments on a synthetic rare-evidence panel and two tabular datasets compare against label-only and prediction-powered baselines, ablate learned weights on held-out populations and evaluate cost certificates. I did not verify the appendix proofs (including the bounded-response extension) or the deferred protocols, so those parts are assessed conditionally.

Critical strengths
  1. Validity is cleanly separated from efficiency, with a plausible stopped-cost analysis. Predictable controls and safe bets give error control (Proposition 1) regardless of proxy quality, while savings depend on residual variance and decision margin. Theorem 1 avoids treating survival-conditioned prefixes as uniform subsets by charging fitting excess over a complete random permutation; the main-text arguments I checked (pp. 3–5) are consistent. Since PPE already gives anytime validity with evolving predictors (p. 9), this analysis is the core contribution.
  2. A reasonably matched learning ablation. Foveal and SCALAR share inputs, reference components and checkpoint schedules; with settings fixed before held-out outcomes were accessed, separate proxy weights reduce held-out mean labels by 3.0%/4.6% (Table 2; prespecified paired statistic, p. 8). This directly tests the method's key design choice, and the paper discloses its post-hoc choices, cheaper competitors and DEFAULT's vacuous cost bound.
Critical weaknesses
  1. The strongest cost guarantees do not cover the best-performing default policy. DEFAULT has the lowest measured cost, but its available bound is still the full census size NN. The nontrivial guarantees apply only to the CAPPED and FIXED variants, and the appendix explains that these modified-policy certificates do not transfer to the range-adaptive DEFAULT policy. Since certified label savings are a central contribution beyond error control, the current theory does not certify the savings of the policy that performs best empirically.

  2. The practical gains are modest and demonstrated in a limited setting. On the held-out comparison, Foveal improves over SCALAR by 3.0% on Housing and 4.6% on Hypothyroid. The appendix makes clear that this comparison was prespecified, which is a strength, but the absolute gains remain small and ONS is slightly cheaper on Housing. Some prediction-powered baselines are also cheaper in the main experiments. In addition, the Figure 1 delayed-stopping variant is explicitly post hoc, and the real-data evaluation uses only two tabular datasets rather than direct LLM-judgment workloads. This leaves the practical benefit for the paper's motivating LLM setting somewhat unclear.

Questions for authors
  1. Can the authors provide a nontrivial cost guarantee for the DEFAULT range-adaptive policy? The appendix explains why the current Theorem 3 bound reduces to (N) at the main real-data thresholds and why the modified-policy certificates do not transfer to DEFAULT. Is this mainly a limitation of the current analysis, or is there a deeper obstacle to certifying the deployed policy?

  2. How should the practical importance of the learned proxy combination be interpreted given the modest held-out gains? Foveal improves over SCALAR by 3.0% and 4.6%, while ONS is slightly cheaper on Housing. More discussion of when separate learned weights are expected to provide substantial gains would help.

8 comments
AuthorsOpenReview ↗

Response to Reviewer MZir (1/7): W1 and Q1, Theorem 3 covers the DEFAULT policy

We thank the reviewer for the careful reading of the theory and the experiments.

W1 and Q1: A cost guarantee for the deployed DEFAULT policy

The strongest cost guarantees do not cover the best-performing default policy. DEFAULT has the lowest measured cost, but its available bound is still the full census size (N). The nontrivial guarantees apply only to the CAPPED and FIXED variants, and the appendix explains that these modified-policy certificates do not transfer to the range-adaptive DEFAULT policy. Since certified label savings are a central contribution beyond error control, the current theory does not certify the savings of the policy that performs best empirically.

Can the authors provide a nontrivial cost guarantee for the DEFAULT range-adaptive policy? The appendix explains why the current Theorem 3 bound reduces to (N) at the main real-data thresholds and why the modified-policy certificates do not transfer to DEFAULT. Is this mainly a limitation of the current analysis, or is there a deeper obstacle to certifying the deployed policy?

On the evaluated corpora, the census bound was a limitation of the analysis. By tracking components and stopping rules already present in DEFAULT, as suggested, we derive nontrivial expected-cost bounds for the original policy on both tabular datasets and three direct LLM-judgment workloads. These certificates apply to the prescribed no-interruption process under exact fitting and certified arithmetic. On Vicuna-13B, for example, the upper bound falls from the census size of 2,403 to 2,016.24 expected labels.

Theorem 3 holds for the unchanged DEFAULT policy. The proof follows one component that DEFAULT already contains and uses only the fact that DEFAULT has not stopped yet (Section 4.4, proof in Appendix A.10). The argument has four steps.

  1. One component is followed. DEFAULT keeps a mixture of evidence components. One of them learns the proxy weights and bets a fixed fraction λ\lambda on each label. The proof follows the log evidence of this single component and leaves the policy as it is.
  2. The conditional expected log increment is bounded below. At each acquired label, the component’s conditional expected log increment is at least λd−λ2(d2+vt)\lambda d-\lambda^2(d^2+v_t), where dd is the margin and vtv_t is the conditional variance of the proxy-corrected label at step tt. Theorem 1 bounds the expected cumulative variance up to the stopping time T0T_0 of DEFAULT by σ∗2E[T0]+BN\sigma_*^2\mathbb{E}[T_0]+B_N, where BNB_N is the cumulative variance allowance for fitting the weights.
  3. The followed evidence stays below a fixed level while DEFAULT is running. DEFAULT stops when its mixture crosses the decision threshold. Before the last label the mixture is below the threshold, so the weighted share of the followed component is below the threshold as well. Accounting for the final multiplicative update, which is at most 3/23/2, and the certified-arithmetic allowance, the log evidence of the component at the stop is at most a constant AA on every run. The step uses no assumption on what ends the run, so the step covers runs ended by another component, by a logical rule, or at the full census.
  4. The two facts bound the stopping time. Combining the lower bound on expected log evidence at T0T_0 with its terminal upper bound AA gives the expected-label bound below when the coefficient of E[T0]\mathbb{E}[T_0] is positive.

Let T0T_0 be the number of reference labels DEFAULT acquires before stopping. For a tracked fixed-fraction component with positive denominator, Theorem 3 gives

\min\left\\{N,\frac{A+\lambda^2 B_N} {\lambda d-\lambda^2(d^2+\sigma_*^2)}\right\\}.$$ Here $N$ is the corpus size, $d$ is the distance between the corpus mean and the threshold, $\sigma_*^2$ is the residual variance under the best fixed proxy weights, $B_N$ is the calibration allowance from Theorem 1, and $\lambda$ is the component’s betting fraction. At error level $\delta=.05$ and prior weight $1/24$, $A=\log 1440+1$. The bound holds for each existing fixed-fraction component. On all three corpora, $\lambda=1/8$ gives the smallest bound. The bound is a guarantee for DEFAULT itself and does not involve CAPPED or FIXED.
AuthorsOpenReview ↗

Response to Reviewer MZir (2/7): W1 and Q1 continued, certified savings on the evaluated corpora

W1 and Q1, continued: certified savings on the evaluated corpora

Appendix A.5 accounts for the shrinking number of unlabeled items in both terms of the bound. The residual-variance term is weighted by the unread fraction, and the calibration allowance becomes 6.64, 6.64, and 6.57 on the three corpora (Table 26). On Vicuna, the formula above gives the census bound, while the refined bound gives 2,016.24. The table reports the refined certificates for all three corpora (Section 5.2, Table 2). We compute dd and σ∗2\sigma_*^2 from the full corpus after evaluation. DEFAULT receives neither quantity, and no setting of DEFAULT was tuned to the margin or to the residual variance. Lemma 5 in Appendix M.1 establishes T=T0T=T_0 for the guarded implementation on every query order of these three corpora under the stated execution assumptions, so the certificates apply to the evaluated policy.

CorpusSize NNMargin ddResidual variance σ∗2\sigma_*^2Upper bound on expected labelsGuaranteed expected savings vs. census
Vicuna-13B2,403.0489.21172,016.24At least 16%
Koala-13B2,273.1590.1955499.62At least 78%
OASST-Pythia-12B1,981.2789.1530266.58At least 86%

Corollary 2 covers binary labels at small margins (Appendix A.9). DEFAULT stops as soon as the observed labels logically determine the verdict. If the corpus mean exceeds τ\tau, observing r=⌊Nτ⌋+1r=\lfloor N\tau\rfloor+1 positive labels suffices. With MM positives among NN items queried in uniformly random order, the expected position of the rrth positive is r(N+1)/(M+1)r(N+1)/(M+1). DEFAULT may stop earlier, so this quantity bounds its expected cost. The analogous argument counts negative labels when the mean is below the threshold.

On Hypothyroid, the bound is 10658/79<13510658/79<135 labels out of 145. In the rare-error LLM study, a positive label denotes an invalid trace. Across the evaluated settings where the invalid-trace rate exceeds the threshold, Corollary 2 guarantees expected label savings of 19% to 50% relative to a census (Tables 29 and 30).

Corollary 3 gives a nontrivial bound for the unchanged DEFAULT policy on Housing, where Theorem 3 returns the census size (Appendix K.5). The margin on Housing is small, so the fixed-fraction component of Theorem 3 does not help there. Corollary 3 follows a fixed-proxy, range-adaptive component already included in DEFAULT. Let S=T0∧HS=T_0\wedge H and Φ(s)=∑t=1sct\Phi(s)=\sum_{t=1}^{s}c_t, where ctc_t is a lower bound on this component’s conditional expected log increment. The mixture threshold before stopping and the bound on the final update give E[Φ(S)]≤K\mathbb{E}[\Phi(S)]\le K, including runs stopped by another component or a logical rule. The pointwise bound T0≤A+BΦ(S)T_0\le A+B\Phi(S), with B≥0B\ge0, then gives E[T0]≤A+B E[Φ(S)]≤A+BK\mathbb{E}[T_0]\le A+B\,\mathbb{E}[\Phi(S)]\le A+BK. Thus Proposition 9 bounds the stopping time of the unchanged DEFAULT policy itself.

On the Housing development table, N=5160N=5160, τ=1/3\tau=1/3, and d=59953/6450000≈0.0093d=59953/6450000\approx0.0093. For the original DEFAULT policy without numerical recovery,

\qquad \frac{\mathbb{E}[N-T_0]}{N}\ge0.5036.$$ The guarantee is for DEFAULT itself and certifies expected savings of at least 50.3%.
AuthorsOpenReview ↗

Response to Reviewer MZir (3/7): W1 and Q1 continued, the general argument and summary

W1 and Q1, continued: the general argument and summary

Proposition 9 gives the general argument (Appendix K.5). Fix the table and choose an existing component of DEFAULT’s evidence mixture on the correct side. Let pp be its prior weight, 1/α1/\alpha the mixture threshold, and ζ\zeta a bound on the log deficit of the certified evidence arithmetic. At label tt, let λt\lambda_t be the component’s betting fraction and XtX_t its correction. For a deterministic horizon H≤NH\le N, suppose that on every history where the policy is still running at label t≤Ht\le H,

\lambda_tX_t\ge-\rho,\qquad X_t\le u_t,\qquad \mathbb{E}[X_t\mid\mathcal{F}_{t-1}]=d>0,\qquad \mathrm{Var}(X_t\mid\mathcal{F}_{t-1})\le v_t^+.$$ Here $L_t\ge0$, $U_t$, $u_t\ge0$, and $v_t^+$ are deterministic, and $0<\rho<1$. Define $$C_\rho=\frac{-\rho-\log(1-\rho)}{\rho^2}, \qquad c_t=\min_{a\in\\{L_t,U_t\\}} \\{ad-C_\rho a^2(d^2+v_t^+)\\},$$ $$\Phi(s)=\sum_{t=1}^{s}c_t,\qquad K=\log\frac{1}{\alpha p}+\zeta+ \log\max_{1\le t\le H}(1+U_tu_t).$$ If $A\in\mathbb{R}$ and $B\ge0$ satisfy $A+B\Phi(s)\ge s$ for $0\le s<H$ and $A+B\Phi(H)\ge N$, then $\mathbb{E}[T_0]\le\min\\{N,A+BK\\}$. **Proposition 9 therefore bounds the expected cost of the unchanged DEFAULT policy.** The envelopes $L_t$, $U_t$, $u_t$, and $v_t^+$ bound the behavior of the component in the analysis only. DEFAULT continues to choose its betting fraction adaptively, and no cap is imposed on the policy. For Housing, we track the range-adaptive component that corrects each label using the first proxy with coefficient one. It has $p=1/192$, $\alpha=1/40$, $\zeta=1$, and $\rho=2/5$. Taking $H=4200$, exact rational arithmetic gives $\Phi(4200)\ge24.7976$ and $K\le10.22398$. The choices $A=721$ and $B=180$ satisfy all 4,201 inequalities, giving $\mathbb{E}[T_0]\le721+180K<2561.32$. This is the bound of Corollary 3. **In summary, nontrivial cost guarantees now cover the best-performing DEFAULT policy itself, without CAPPED or FIXED. Theorem 3 certifies expected savings of at least 16%, 78%, and 86% on the three LLM corpora, Corollary 2 bounds the expected cost on Hypothyroid below 135 of 145 labels, and Corollary 3 certifies at least 50.3% on Housing.**

Comments on the paper

2 comments
AuthorsOpenReview ↗

Comment 1 of 2:Summary of the revision

Summary of the revision

We thank all three reviewers. The revised PDF now includes the full appendix, and all citations are now hyperlinked. The main changes are listed below with the reviewers who raised each point. Section and appendix numbers refer to the revised PDF. A second comment, "How to read the experiments", explains the terms and the run counts in the new experiments and lists the sources of the datasets and the baselines.

  1. Positioning (cGtL, MZir). The abstract and the introduction keep the finite-sample error guarantee and the label savings over label-only methods as the main claims, and now present separate proxy weights as a conditional benefit. The fourth paragraph of Section 1 now separates the anytime-valid error guarantee, which follows from existing tools, from the label-cost guarantees, which are our contribution.
  2. Cost guarantees for the unchanged default policy (MZir, cGtL). Theorem 3 already bounds the expected cost of the default policy of Foveal Search (DEFAULT), and Section 4.4 now states this fact. On the three new LLM-judge corpora (Table 2), Theorem 3 (tighter form in Appendix A.5) guarantees that DEFAULT saves at least 16%, 78% and 86% of the labels in expectation. The new Corollary 2 (Appendix A.9) covers binary labels at small margins. On Hypothyroid, Corollary 2 bounds the expected cost of DEFAULT below 135 labels for 145 items. In the new rare-error study, Corollary 2 guarantees that DEFAULT saves 19% to 50% of the labels in expectation in every setting where the batch should be rejected. The new Corollary 3 (Appendix K.5) guarantees that DEFAULT saves at least 50.3% of the labels in expectation on Housing, where the original bound was the full corpus size.
  3. LLM workloads (VCfU, MZir). The new Section 5.2 reports three studies with LLM judges. The first study uses three corpora from Chatbot Arena with human votes as reference labels (Table 2). The second study is a workflow from raw text to a verdict on 125 ProcessBench reasoning traces (Appendix M.2). The third study is a held-out study with rare errors in batches of 500 and 1000 reasoning traces, scored by four local LLM judges (Figure 1, Appendix M.3). In the rare-error study, Foveal Search reaches the correct verdict in all 1024 runs and uses 31% and 41% fewer labels than EB-CS, the label-only method with the same error guarantee.
  4. Prediction-powered baselines (cGtL, MZir). The new Proposition 2 (Section 4.1) concerns PPI++-CS, the power-tuned form of PPI-CS. PPI++-CS accepts a batch that should be rejected with probability at least (1−k/N)b(1-k/N)^b, the probability that an initial sample of bb draws contains none of the kk invalid items among the NN items. In the rare-error study, the cheapest PPI++-CS variants use fewer labels than Foveal Search but accept 24 and 21 of 128 batches that should be rejected at a threshold of τ=.02\tau=.02. A longer initial sample removes these wrong verdicts but ends 29% of the runs without a verdict. Close to the threshold, the observed error rate of PPI++-CS with the longer initial sample again exceeds the allowed error level δ\delta in 9 of the 72 combinations of variant and setting (Appendix M.3). A new study on restaurant reviews, in which the share of positive labels is not set by us, shows the same pattern (Appendix M.6).
  5. When separate weights help (MZir, cGtL). The new condition (20) in Section 4.4 states when separate proxy weights repay the cost of learning them. Section 5.3 keeps the original held-out comparison, in which Foveal Search uses 3.0% and 4.6% fewer labels than the variant with a single shared weight, and now adds a synthetic study and a held-out study on MATH problems (Appendix M.4). The controls that replace only the weight learner of Foveal Search and keep the same error guarantee are now named F-Scalar, F-ONS, F-Single and F-Zero. Tables 2 and 3, the result tables of Appendix M and Figure 1 group these variants with Foveal Search.
  6. Post hoc variant (MZir). Section 5.1 already reported the original policy first. The revision moves the old Figure 1, which features the delayed-stopping variant, to Appendix H (now Figure 2), and the new Figure 1 shows the held-out study with LLM judges.

In 17 of the 18 settings in which the batch should be rejected, no prediction-powered variant that reaches the correct verdict in at least 95% of its runs uses fewer labels than Foveal Search, and Foveal Search reaches the correct verdict in every run of these settings (Appendix M.7). Some prediction-powered baselines still use fewer labels than Foveal Search, for example PPI++-CS on two of the three LLM-judge corpora, where errors are common and asymptotic intervals are accurate. Foveal Search uses more labels there because Foveal Search keeps a finite-sample error guarantee. Sections 5.1 and 5.2 report these cases.

Code is at https://anonymous.4open.science/r/30228.

AuthorsOpenReview ↗

Comment 2 of 2:How to read the experiments

How to read the experiments

This comment explains the terms and the run counts in the revised paper and in our replies, and lists the sources of the datasets and the baselines.

Terms

  • Batch or corpus. The fixed set of NN items to verify. Every item has proxy scores, and the reference label of an item is acquired only when a method queries the item.
  • Run. One execution of one method on one batch with one random query order. A run ends with a verdict on whether the batch mean exceeds the threshold τ\tau, or with no verdict.
  • C/W/U. The numbers of runs with a correct verdict, a wrong verdict, and no verdict.
  • Labels. The mean number of distinct reference labels acquired per run. The mean includes wrong and undecided runs and the labels used to fit the proxy weights.
  • Paired query orders. All methods run on the same batches with the same random seeds, so two methods are compared run by run.
  • Setting. One combination of batch size NN, threshold τ\tau, and share of invalid items. A share of 2τ2\tau means twice the threshold.
  • Certified and observed savings. A certified saving comes from a theorem that bounds the expected number of labels, so a bound such as 2,016.24 is not an integer. An observed saving is a mean over runs.

The error level is δ=0.05\delta=0.05 unless stated otherwise.

Run counts

CountHow the count is formed
64Query orders per corpus on Chatbot Arena, MATH, and held-out Housing and Hypothyroid
16Query orders per threshold in the ProcessBench prototype, per restaurant, and on the Housing and Hypothyroid development tables
128Runs of one setting in the rare-error study, from 16 batches with 8 query orders each
5124 settings, as for one batch size in Table 29 or for Figure 1(a) or 1(c)
1,024The 8 settings of Table 29 (2 batch sizes, 2 thresholds, 2 shares)
1,536The 12 settings with a share of 1.25τ1.25\tau or 1.5τ1.5\tau (Figure 1(b))
2,304The 18 settings in which the batch should be rejected (3 batch sizes, 2 thresholds, 3 shares, Table 36)
4,096 and 9,216The 4 variants of PPI++-CS together, on 1,024 runs and on 2,304 runs
192 and 4803 Arena corpora with 64 orders each, and 30 restaurants with 16 orders each
13Prediction-powered variants (4 of PPI-CS, 4 of PPI++-CS, the same 4 with a longer initial sample, 1 of PPE)

Datasets and their sources

DatasetSourceIn the paper
Chatbot Arena comparisons with human votes and the verdicts of three LLM judgesPublic release of Chatzi et al. (2024)Table 2, Appendix M.5
Reasoning traces with step-level annotationsPRM800K (Lightman et al., 2024) and ProcessBench (Zheng et al., 2024)Figure 1, Appendices M.2 and M.3
MATH solutionsMATH subset of ProcessBench (Zheng et al., 2024)Appendix M.4
Restaurant reviewsYelp portion of the review benchmark of Yeh et al. (2026)Appendix M.6
Housing and HypothyroidData and predictors as in Gu et al. (2026) and Brawand et al. (2026)Sections 5.1 and 5.3

Methods and their sources

  • EB-CS. A label-only confidence sequence for sampling without replacement (Waudby-Smith and Ramdas, 2020). EB-CS has the same finite-sample error guarantee as Foveal Search and uses no proxies.
  • PPI-CS and PPI++-CS. Asymptotic confidence sequences for prediction-powered inference (Kilian et al., 2025). PPI++-CS adds the power tuning of PPI++ (Angelopoulos et al., 2026). The labels 1N and 4N give the observation horizon. A dagger marks an initial sample extended from 40 draws to 149 draws at τ=0.02\tau=0.02 or 59 draws at τ=0.05\tau=0.05.
  • PPE. Prediction-powered e-values (Csillag et al., 2025), with a finite-sample guarantee.
  • F-Scalar, F-ONS, F-Single, and F-Zero. Ablations of Foveal Search that change only how the proxy weights are set. They are not baselines. F-NoProxy, added after the other results, replaces every proxy by a constant.

In the new LLM studies, every baseline configuration was fixed before the reported runs.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.