acceptodds
Under review as a conference paper at ICLR 2027

Semantic Coverage for Test-Time Reasoning: The Value and Cost of Early Information

Abstract

An additional reasoning trace can be individually valuable while adding little to the work already done. We study test-time allocation through semantic coverage, an objective that values the useful support a set of outputs provides jointly. Predicting this support before completion may avoid redundant work, but consumes computation that could otherwise be spent completing another trace. In a structured overlap model, we show that optimal coordination need not require a full model of possible outputs: learning which branches share useful contributions can suffice. We characterize how many observations are needed to approach optimal coverage in the worst case. In a screening model, we determine exactly when checking whether a candidate will add something new reduces the average computation needed to obtain a useful contribution. The check need not be perfect, and we derive how much it is worth paying for its ability to distinguish new contributions from duplicates. We then show how repeated checking in a discovery model can obtain every distinct useful contribution with high probability using only one full completion for each. Duplicates still have to be encountered, but need not be fully generated; we characterize the minimum total cost of checks and completions up to constant factors. In multi-answer question answering, output format changes the benefit of coordinated generation: naming answers before explaining them increases its coverage gain. In a controlled study using the same preview-based predictions, selecting unfinished traces for their predicted joint contribution recovers more distinct correct answers on average than individual ranking. In a separate comparison of complete procedures with all online work charged, agreement-filtered answer lists achieve higher mean F1 at lower mean token cost than iterative preview selection on retrieved evidence. These results distinguish improvements in selection from improvements in the overall quality–cost tradeoff.

Primary area:
foundation or frontier models, including LLMs
Keywords:
large language models, test-time reasoning, compute allocation, semantic coverage, value of information

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_vhdFOpenReview ↗
Rating
2
Confidence
2(−1)
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper addresses the challenge of allocating a limited computational budget across multiple incomplete reasoning trajectories during test-time reasoning, with the goal of avoiding the repeated generation of identical answers or evidence. The core tension lies in the trade-off that while inspecting early previews of trajectories helps identify complementary paths, the previews themselves consume tokens and may encroach upon the budget reserved for completing the reasoning. Specifically, the study investigates three key aspects: the amount of early information required to select complementary rather than redundant trajectories; the conditions under which the informational value of a preview justifies its computational cost; and how to employ inexpensive checks to filter out duplicate candidates as more answers are discovered, thereby ensuring that costly reasoning is completed only for candidates that provide novel information.

Critical strengths
  1. The paper gives a clear definition of semantic coverage. Equation (2) separates changes in individual value from gains from fewer repeats. Theorems 1–3 study learning enough to coordinate, exact diagnostic profitability, and discovery with two operation costs.

  2. The experiments separate two settings clearly. One uses the same shared previews and candidate pool for different selection rules. The other compares complete procedures under a shared token ceiling and charges all online work. The paper reports both gains from product-union selection and cases where agreement-filtered lists have higher target F1 at lower cost.

Critical weaknesses
  1. The link between Theorem 1 and the experiments is not strong enough. The theorem requires complete contributor observations and a common circular order that makes BB an arc. However, SCPS uses entity previews and product-union selection. The paper does not show how these previews provide complete contributor observations or a consistent order.

  2. The empirical evidence is limited, and the theory alone does not establish practical usefulness. More importantly, several assumptions of the diagnostic theory are hard to verify at deployment. Theorems 2–3 assume known conditional diagnostic laws, persistent candidate labels, fresh independent reports, and, in the discovery model, uniform hidden classes. Appendix C.5 requires calibration on deployment conditional laws of novel and duplicate examples, and states that fitting and calibration costs must be charged or amortized. However, the empirical predictors are fitted using gold reference matches. The paper does not report calibration cost or calibration sample size, and it does not test distribution shift. Therefore, it remains unclear whether the required information is available in practice and whether the diagnostic provides a net benefit.

Questions for authors
  1. How are the conditional diagnostic laws estimated at deployment?

  2. How many deployment-matched labeled examples are needed to calibrate the diagnostic, and does the Eq. (5) threshold correctly predict realized cost savings after charging calibration and acquisition costs?

  3. Please add more experiments.

  4. Could the authors clarify the practical use cases of the proposed framework? In which real tasks is it necessary to acquire early information and select among unfinished attempts according to semantic coverage, rather than use direct generation or agreement-filtered lists? Please provide a concrete example in which this choice improves final utility under a shared token ceiling, and explain what the useful contribution, diagnostic, and completion correspond to in that task.

5 comments
AuthorsOpenReview ↗

Response to Reviewer vhdF (1/3): Theorem 1 and the experiments

Thank you for the detailed, technical review; your questions helped make the paper more precise. You identified the two places where it needed to be more explicit: what Theorem 1 requires and what App. C.5 asks of deployment.

W1. The link between Theorem 1 and the experiments. We agree, and the revision now makes the link clearer. SCPS’s previews give neither complete contributor sets nor a consistent order, so SCPS does not test Theorem 1, but the coordinated-sampling experiment of Sec. 4.1 does, and coordination helps there under the output format that the theorem’s condition calls for. The experiment was in the original submission but did not state this link; the revision connects its sampler to Theorem 1 and checks the theorem’s condition:

1. The sampler is Theorem 1’s systematic sampler. In inverse-CDF decoding, one number u∈[0,1)u \in [0,1) selects one output, token by token. Each possible output ii then owns an interval of length πi\pi_i, its probability under decoding, and outputs that share an opening occupy one consecutive stretch. Independent sampling draws the kk values of uu independently. The lattice sampler used in Sec. 4.1 draws output jj at uj=(j/k+Δ) mod 1u_j = (j/k + \Delta) \bmod 1, with one shift Δ∼U[0,1)\Delta \sim U[0,1) shared by the batch, so the kk points are evenly spaced and each output keeps the model’s distribution. This is systematic sampling, with the outputs as actions, the decoding order as the circular order, and selection probabilities kπik\pi_i.

2. What the theorem predicts. Let BeB_e be the outputs that name answer ee, with total probability π(Be)\pi(B_e). If the outputs in BeB_e are adjacent, a batch never repeats ee when kπ(Be)≤1k\pi(B_e) \le 1 and never misses it when kπ(Be)≥1k\pi(B_e) \ge 1: it names ee with probability min⁡(1,kπ(Be))\min(1, k\pi(B_e)). No sampler with these output probabilities can do better. Independent sampling gives 1−(1−π(Be))k1 - (1 - \pi(B_e))^k, which is lower because its draws can repeat ee. Of course, the theorem does not say that every output format meets this condition, but it shows how much coordination can achieve with the appropriate information. If the model must state its answer first, all outputs that give the same answer begin with the same tokens, so they sit next to each other in the order (up to different names for one answer). If the model must reason first and answer last, outputs that give the same answer begin in many different ways and are scattered across the order, and the theorem then gives no guarantee.

3. What we observe. We crossed format with sampler for three models and two kinds of evidence (retrieved, and answer-bearing passages that contain the answers), six settings in all. With the answer first, coordination adds 0.04–0.20 distinct correct answers per four outputs (9–20% over independent sampling), every interval above zero; with the rationale first, no change is detected in any setting. The difference between the formats is significant in all six settings after Holm correction. Since each output keeps its distribution, the gain comes from repeats avoided (Eq. (2), Fig. 2).

We also added checks of the adjacency condition on generated outputs; the main one tests a consequence of it. If the outputs naming answer ee occupy one interval of length π(Be)\pi(B_e), the kk evenly spaced points land in it ⌊kπ(Be)⌋\lfloor k\pi(B_e) \rfloor or ⌈kπ(Be)⌉\lceil k\pi(B_e) \rceil times whatever the shift, so across batches the number of times ee is named takes at most two adjacent values. If they are scattered, the count can vary by more. Over twelve batches per question (164 questions, two models), we looked at every answer named at least twice. With the answer first, the count takes at most two adjacent values for 92% of them, against 41% under independent sampling; the exceptions are consistent with different names for one answer. With the rationale first, it does so for 41%, about the same as under independent sampling (39%). Rare answers pass under any sampler, so we also looked at answers named at least eight times: 89% pass with the answer first, against 9–17% in the other three cases. The check is necessary for adjacency, not sufficient: it is consistent with adjacency for nearly all answers under the answer-first format, and rejects it for most under the other.

Where SCPS fits. Here the order comes from decoding, so nothing has to be learned, and no contributor observations are needed. SCPS is used for the other results: it illustrates Eq. (2) in Sec. 4.2, and Sec. 4.3 applies Theorem 2 to its measured prices.

Changes in the paper. This explanation is now in the paper: Sec. 4.1 gives the sampler’s link to Theorem 1, the role of output format and the count check; App. E.1 gives the formal argument, the full check with its independent-sampling baseline, and the distance from the ceiling; new Table 1 (Sec. 4) pairs each result with its experiment.

AuthorsOpenReview ↗

Response to Reviewer vhdF (2/3): deployment requirements and labeled sample size

W2 and Q1. Can the requirements be met at deployment, and how are the laws estimated? We agree the submission should have discussed this. The decision needs the fraction pp of useful candidates and how often the diagnostic (an early look at an unfinished candidate, such as a preview) flags useful (α\alpha) and other candidates (β\beta).

How the two flag rates are measured.

  1. Run the diagnostic on a sample of candidates from the task.
  2. Complete every candidate, including those the diagnostic would reject.
  3. Record which were useful, and the flag rates α^\hat\alpha among useful and β^\hat\beta among other candidates.
  4. Buy the diagnostic only if α^−β^\hat\alpha-\hat\beta, less a confidence margin 2log⁡(4/δ)/n\sqrt{2\log(4/\delta)/n} for nn examples of each kind, exceeds c/[C(1−p)]c/[C(1-p)], the boundary of Theorem 2 (cc: the diagnostic's price; CC: a completion's cost); otherwise complete directly.

Of the assumptions you list, measured rates replace known laws; each candidate is completed once and labeled by that completion, so its label is fixed by construction. Fresh repeated reports and uniform classes are needed only for the results on repeated diagnostics and on discovery, as Sec. 3.2 now says.

Gold references, calibration cost and shift. Step 3 needs a verifier of usefulness: execution where the task has one (tests), or labeled development questions (question answering). New App. G.1.1 reports what you asked for on our question-answering predictors: sample size (91–96 questions per fit), held-out calibration (ECE 0.02–0.06), and the one-time cost of the fitting data (1.29M and 7.04M tokens, two backbones). Without refitting, on a separate 160-question population, the Qwen3.5-9B predictor’s ECE goes from 0.058 to 0.088 with retrieved evidence.

Changes in the paper. Sec. 3.2 (new paragraph "Using the boundary") gives the measurement procedure for the rule and the assumptions it needs; App. C.5 the sample sizes and repayment; new App. G.1.1 the predictors’ calibration, cost and transfer.

Q2. How many labeled examples, and does the threshold predict realized savings? We agree that the threshold should be checked against realized outcomes. The revision applies it in two settings, and in both the boundary’s verdict matches the realized comparison.

How many labeled examples? The number of labeled candidates in step 3 depends on how far the diagnostic clears its price. At 95% confidence, a diagnostic whose estimated α−β\alpha-\beta exceeds c/[C(1−p)]c/[C(1-p)] by 0.20 needs 220 independent examples of each kind; one that clears it by 0.10 needs 877. If labeling, fitting and calibration cost KK, they are repaid over HH uses only when HΔ>KH\Delta \gt K, Δ\Delta being the saving per use; if Δ≤0\Delta \le 0, nothing repays them (App. C.5).

Executable tests (new experiment). Can a look at a test’s first 128 tokens tell whether the test is worth finishing and running?

  • Sample. On 16 TestGenEvalLite tasks, we finished and executed every candidate: 240 labeled tests, 20 of them useful.
  • Measured rates. A screen on the first 128 tokens (fitted on other tasks) flags 30% of the useful tests and 24% of the others.
  • What the rule says. Do not buy the screen. With 20 useful tests, a 6-point gap cannot be distinguished from zero (95% interval: −20 to +28 points), and the rule buys only on a reliable gap. Even at face value, the prefix costs at least 14.3% of the rest of the test, nearly twice the 7.7% that such a gap could repay (App. H.4).

The whole experiment took 1.40M tokens of generation. So a sample labeled by execution alone was enough to decide against this screen before deployment, and to show what would change the decision: a cheaper prefix or a sharper screen.

Question answering. Could SCPS’s previews pay?

  • Measured price. A prefix and two previews cost 0.97–1.45 times a completion (App. G.1).
  • What the rule says. The loop finishes one candidate in four. At this price, previews save compute only if that quarter holds more than all of the useful candidates on the two Qwen models (109% and 104%), which is impossible, or 86% of them on Gemma-4-12B (App. G.3.3).
  • What happened. Under the same token ceiling, the same loop without previews finishes about twice as many traces and recovers 0.29–0.84 more distinct correct answers. It uses 4–17% more tokens and has slightly lower F1 on two models (Tab. G3).

Changes in the paper. Both analyses are now in Sec. 4.3; details are in new App. G.3.3 (Tab. G8) and new App. H.4.

AuthorsOpenReview ↗

Response to Reviewer vhdF (3/3): further experiments and practical use

Q3 (and the limited evidence noted in W2). More experiments. After the submission, we added the following experiments and connections between the experiments and our theory, which should address your concern:

  • Table 1 at the start of Sec. 4, pairing Theorems 1–2 and Eq. (2) with the experiments that test or illustrate them;
  • two checks of Theorem 1's condition, one with an independent-sampling baseline, and how far coordination is from the theorem's ceiling (App. E.1);
  • a new experiment applying the purchasing rule to executable tests, with 240 labeled candidates (Sec. 4.3, App. H.4);
  • the price analysis of previews (Sec. 4.3, App. G.3.3, Tab. G8);
  • sample sizes, held-out calibration, fitting costs and a separate question population for the predictors (App. G.1.1);
  • further test-generation experiments on 32 Django and SymPy components, scored by TestGenEval execution (App. H.5–H.6).

Q4. Practical use cases. We agree the submission should have made this concrete. In short: choosing by coverage pays whenever information about overlap is cheap enough, and the paper gives a general rule to decide, from measured prices and rates, whether acquiring early information pays in a given task.

Which real tasks, and what the contribution, diagnostic and completion are in each. The setting arises wherever a set of attempts is valued for what it supplies together.

  • Questions with many answers (QAMPARI; also retrieving all relevant evidence, or proposing candidate hypotheses). In our experiment, the contribution is a distinct correct answer, the diagnostic is a short preview (at most 24 tokens) that forecasts an unfinished trace's answer, and completion is the rest of the trace.
  • Test generation. The contribution is a newly covered line from a test that passes and preserves the suite, the diagnostic scores a candidate test's first 128 tokens, and completion writes up to 896 more tokens and runs the test.
  • Tasks with a verifier, such as code generation or theorem proving scored by pass@k. The contribution is the first output that gets verified.

When acquiring early information is the right choice. Theorem 2 gives the condition: the diagnostic’s price must be below C(1−p)(α−β)C(1-p)(\alpha-\beta), a fraction of a completion. This is the regime of long completions and cheap, discriminating diagnostics: in the worked example of Sec. 3.2, a diagnostic priced at a fifth of a completion lowers the cost of a useful result from 5C5C to 3.75C3.75C. A labeled sample shows which side of the boundary a task is on (Q2). In our runs, the two measured diagnostics do not clear it: one because a forecast, bought with its prefix, costs about as much as a completion even with prompt caching, and the other because its screen separates candidates weakly; there, direct generation or agreement filtering is the better choice. The same calculation shows what would change this: if a preview cost only its output tokens, the share of useful candidates that the loop's completions must contain would fall from 86–109% to at most 56–65% (App. G.3.3). Where overlap information is free, as with the decoding order in Part 1, answer-first coordination adds 0.04–0.20 distinct correct answers per four outputs (9–20%) at no extra generation.

Changes in the paper. The rewritten first paragraph of the introduction names tasks scored by what attempts supply together and reports that one answer list is not enough; Table 1 and Sec. 4.3 show where our measured diagnostics stand against the boundary; the rewritten Discussion states the practical conclusion and the limitation for reasoning-first traces.

Thank you again. Your questions on Theorem 1 and on what the rule needs in practice led to the new checks, the price analysis, and the test experiment, and we consider the paper stronger with them.

Reviewer_2twGOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies how to allocate test-time computation to maximize semantic coverage while accounting for the cost of acquiring early information about unfinished reasoning traces. The authors develop three theoretical models to characterize the information needed for optimal joint selection, the conditions under which early screening is cost-effective, and the computational cost of discovering distinct useful contributions. They also propose Semantic-Coverage Portfolio Search (SCPS), which uses short previews and estimated answer correctness to select complementary reasoning prefixes for completion. Experiments on multi-answer question answering show that coverage-aware selection improves distinct correct-answer coverage over individual ranking under shared preview information, while simpler agreement-filtered generation achieves better F1–cost tradeoffs in the full-budget comparisons.

Critical strengths
  1. This paper provides a theoretical framework for understanding the trade-off between semantic coverage and the cost of acquiring early information.

  2. This paper provides honest results compared with the proposed method and the simple baseline Agreement-filtered lists.

Critical weaknesses
  1. The motivation of this paper seems confusing to me. When I read the introduction, I do not understand why we should care about semantic coverage, since Self-Consistency asks for the most confident answer. Even though the authors mention the multi-answer setting, it does not make sense to me because we can simply ask the LLM to output every answer. Therefore, the proposed method, which asks LLMs to generate one answer at a time for the multi-answer setting, also cannot convince me. The current setting is not reasonable enough for me to think the problem is indeed important.

  2. The proposed method seems over complex and lack of pratical usage. The proposed method only generates one answer in a multi-answer setting and then predicts the answer with a prefix, judges the answer using another LLM or another logistic regression, and then regenerates the full answer using the selected prefix. However, nearly none of each part's motivation is well-supported. For example, I do not understand why the prediction using a prefix can be successful, or why using another run of an LLM or logistic regression is reliable for judging the answer. The experiments compared with Agreement-filtered lists, which is a simple Self-Consistency-based method, show that this overly complex design cannot perform well.

Questions for authors
  1. I notice the analysis of coverage only considers the final answer. Is it possible to do the analysis over the reasoning trace and apply it to the GRPO training setting to increase reward diversity?

  2. Could the authors explain the motivation for each part of the proposed SCPS?

  3. Could the authors explain how to predict the answers using the prefix in detail and evaluate the effectiveness of it?

4 comments
AuthorsOpenReview ↗

Response to Reviewer 2twG (1/2): what the paper studies and why coverage matters

Thank you for the frank and useful review. It showed us that the introduction did not make clear what problem the paper studies or why it matters. We have changed it accordingly.

Where the problem arises. Many valuable tasks are not finished by one confident answer; they need a set of distinct useful results. A literature or evidence search must surface every relevant source. A system that proposes hypotheses or candidate solutions is valued for the distinct ones it finds. A test suite is worth the code it covers, so language-model test generators such as CoverUp and CodaMosa are guided by coverage. A question can have many correct answers (QAMPARI). A code or proof search succeeds as soon as one of many attempts is verified (pass@k).

In these tasks, one attempt is rarely enough, so systems run many. For example, a single answer list finds on average only 22–29% of a question’s answers from retrieved evidence, and further attempts find more. Attempts can also run in parallel, so more attempts need not mean a longer wait. But parallel attempts repeat one another: in recent work, over 80% of parallel reasoning traces ended in the same final answer (Tu et al., 2026), and every repeat costs a full generation. So the practical question is how to get the most distinct useful results from a given amount of compute. The paper studies two decisions that answer it: when to coordinate attempts so that they do not repeat, and when an early look at unfinished attempts is worth its price. It gives theory for both and experiments that test them (new Table 1); SCPS is one of the procedures used in two of these tests.

W1. Why care about coverage, when Self-Consistency asks for the most confident answer? The two answer different questions. Self-Consistency asks which single answer to trust. Coverage asks what a set of attempts supplies together, counting each useful result once. They are complementary, and the revised Sec. 2 now clarifies this.

“We can simply ask the LLM to output every answer.” We agree this is the natural first thing to try; the paper does it, and one list is not enough. Three of the five procedures in Table 2 (formerly Table 1) ask for the whole list: one list; sixteen lists filtered by agreement; and repeated lists told the answers found so far. As the rewritten introduction puts it: “Requesting the whole collection at once does not remove the problem. In our experiments a single answer list recovers, on average, 22–29% of a question’s answers from retrieved evidence (Sec. 4.3), so further attempts are needed, and they overlap.” Given that several attempts are needed, the paper studies how to decide what each should add.

Why does each SCPS trace name one answer? This is a choice for a clean experiment. With one answer per trace, we can see exactly what each trace contributes. Two traces then overlap exactly when they name the same answer, so we can measure and control overlap. It is not a limit of the framework: Sec. 2 states that “One action can supply several contributions, as when a single generated list supplies many answers”.

Changes in the paper. The rewritten first paragraph of the introduction discusses tasks of this kind (pass@k, test suites, many-answer questions), the contrast with Self-Consistency, and why one list is not enough. Sec. 2 adds the sentence quoted above and states how agreement and coverage work together; new Table 1 (Sec. 4) pairs each result with its experiment.

Q1. Reasoning traces and GRPO. Yes, both fit. Coverage counts whatever the task’s evaluator treats as useful, not only final answers. Our test-generation experiment counts newly covered lines, and a reasoning trace’s useful contributions could be its verified intermediate steps.

For GRPO, coverage has been shown to matter. QuasiMoTTo (Li et al., 2026) samples a group of outputs jointly so that they repeat less, and reports that this matches independent sampling with half the GRPO training steps on maze and Sudoku tasks, attributing the gain to higher coverage. Our work is complementary. Theorem 1 says when such coordination is optimal; in language-model outputs, with the answer first, it finds 0.04–0.20 more distinct correct answers per four outputs (9–20%) at no extra generation (Sec. 4.1). The rest of the paper studies selection that needs paid information, and counts its cost in compute, not in number of samples (Sec. 4.3). Eq. (2) also suggests a way to get the reward diversity you describe: credit each trajectory with what it adds to the group’s verified coverage, so that it is not rewarded again for what another already supplied.

Changes in the paper. The Discussion now states that useful contributions “can also be verified intermediate claims or executed behaviors”, and proposes the group credit above for reinforcement learning.

AuthorsOpenReview ↗

Response to Reviewer 2twG (2/2): the parts of SCPS, prefix forecasts, and agreement-filtered lists

W2 and Q2. Is the method too complex, and what motivates each part? We agree the submission did not make it clear what SCPS is for or why each part is there. SCPS is the experimental procedure we use to study the question, a way to measure what early information can gain and what it costs; the paper’s contribution is the characterization of that tradeoff. The rewritten opening of Sec. 4.2 gives the reason for each step:

  1. Prefix. Finishing an attempt is the costly step. A prefix is an unfinished attempt, so we can still decide whether to finish it.
  2. Preview. To decide, we need a cheap forecast of the answer the prefix will reach. A preview is that forecast (Q3).
  3. Correctness estimate. A previewed answer can be wrong, so a logistic model fitted on separate development questions estimates the chance that it is correct.
  4. Joint selection. Finishing two prefixes that give the same answer wastes one completion. SCPS picks prefixes for what they add together: a prefix whose likely answer is already covered adds little, so a weaker prefix with a missing answer can take its place.
  5. Completion. A selected prefix is continued without the preview text, so the preview forecasts the answer without fixing it.

SCPS is compared with simpler alternatives: ranking prefixes one at a time, removing duplicate predicted answers, taking the first four prefixes, and the same loop run without previews.

Why agreement-filtered lists can do better. You are right: on retrieved evidence, they reach higher mean F1 at lower cost than SCPS. The F1 advantage comes from filtering: keeping only names found in at least two of sixteen lists removes many that match no reference answer and keeps most correct ones (Tab. G4). The cost comes from the previews, and Theorem 2 says why they do not repay it: an early look at an unfinished attempt is worth buying only if it costs a fraction of finishing it. We measured the price: a prefix and two previews cost 0.97–1.45 times as many tokens as finishing (Sec. 4.3, Tab. G8). At that price, in a loop that completes one candidate in four, no selector could make previews pay on two of three models, and under the same ceiling the same loop without previews recovers 0.29–0.84 more distinct correct answers, for 4–17% more tokens and slightly lower F1 on two.

So before building a procedure like SCPS, one can check measured prices and flag rates to see whether early information is worth buying. The paper reported this comparison openly, as you noted, and the revision now explains it more clearly.

Changes in the paper. The rewritten opening of Sec. 4.2 gives the reason for each step and names the alternatives; a new paragraph in Sec. 4.3 applies Theorem 2 to the measured price of previews (new App. G.3.3, Tab. G8).

Q3. How is the answer predicted from a prefix, and how well does it work?

How. A preview is the model’s own short continuation of the prefix, at most 24 tokens, prompted to state the answer. Because it starts from the same prefix as the completion, it samples where that prefix is heading; we draw two per prefix. The logistic model of step 3 then estimates whether a previewed answer is correct. Theorem 2 applies to any such forecast, because it needs only its price, how common useful candidates are, and how well it separates them from the rest.

How well. A preview tracks its prefix’s answer, the forecasts used jointly beat individual ranking, and the predictors are calibrated:

  • When both name an answer, a preview and a completion of its prefix agree 39.7% of the time, close to the 43.1% for two completions of that prefix and above the 26.5% for a different prefix (160 development questions, App. F.2.2).
  • Given the same forecasts, choosing prefixes for what they add together recovers 2.418 distinct correct answers per batch, against 2.139 for ranking them one at a time (Sec. 4.2, Tab. F2).
  • On 78 separate questions and two further backbones, a simpler joint score that subtracts predicted pairwise overlap gains 0.248 and 0.299 over the same ranking, both significant after Holm correction.
  • If we scramble which prefixes share a predicted answer while keeping each prefix’s own score, joint selection loses coverage on two of three backbones (when the passages contain the answers). So there the gain depends on knowing which prefixes would repeat each other.
  • On held-out questions, the stated probabilities of the complete procedures’ predictors are on average within 0.02–0.06 of the observed rates of correct answers (App. G.1.1, Tab. G1).

Changes in the paper. Sec. 4.2 explains how previews are made and why a selected prefix is continued without them. New App. G.1.1 reports the predictors’ sample sizes, held-out calibration (Tab. G1), and a separate question population; App. F.2.2 reports the preview agreement; App. F.1 and F.2.1 report the selection results.

I thank the reviewer for the clarification. However, my two concerns remain:

  1. The motivation for studying the particular setting in the paper is still insufficient. For example, one could use multi-turn prompting, providing previously generated answers and asking for additional answers not already included. The limited recall of a single list does not explain why we should study the proposed setting rather than such alternatives. I still do not see a sufficient justification for this choice.

  2. Framing the contribution as analysis does not resolve this motivation concern. Without a stronger justification for the setting, it remains unclear whether the mathematical models meaningfully capture the practical problem. Furthermore, what actionable insights do these analyses provide? I currently do not see how the results guide practical decisions beyond a straightforward comparison of prediction and completion costs.

Thank you.

Multi-turn prompting with previously found answers is in the paper: "memory-conditioned lists" (Table 2) conditions each batch on the answers found so far. It recovers the most answers (2.13–3.79 vs. 1.64–2.47 for agreement-filtered lists), but at much lower F1 on the Qwen models (.071–.081 vs. .207–.239) and 2.6–5.8× the tokens. Neither strategy dominates the other: knowing what was already found raises coverage but costs prompt tokens and sequential calls. When such information pays is the question the paper studies.

Actionable insights beyond a cost comparison:

  1. For parallel sampling, name the entity first and use coordinated sampling: 9–20% more distinct correct answers at no extra generation (Sec. 4.1).
  2. Whether a check pays depends not on its price alone but on price relative to C(1−p)·TV: a cheap check that discriminates weakly does not pay, and repeated checks cannot extend the profitable range (Thm. 2).
  3. Measured on our tasks, previews and test screens fall outside that range, consistent with agreement-filtered lists performing best (Sec. 4.3).
Reviewer_s5MXOpenReview ↗
Rating
2
Confidence
2
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

In this paper, the authors study the allocation of test-time computation through semantic coverage: Particularly, the expected amount of distinct useful content supplied by a collection of outputs. It distinguishes individual output quality from redundancy between outputs, and separates the benefit of selecting with early information from the net benefit of purchasing that information. In essence, the authors demonstrate several scientific findings, e.g., when contributor sets are contiguous in an unknown common circular order, systematic sampling achieves optimal coverage at prescribed action-selection probabilities. The authors conducts extensive experiments to back up the scientific claims/findings.

Critical strengths
  1. This paper is very unique by providing substantive theoretical results that distinguish sufficient information, profitable information, and resource savings.
  2. Extensive experiments are conducted to back up the scientific findings, e.g., careful empirical separation of selection gains from complete-procedure value, including informative negative results.
Critical weaknesses
  1. Even if some theoretical analysis has been provided, these theoretical guarantees have a limited demonstrated connection to practical reasoning traces.
  2. Some parts of the paper are hard to follow, e.g., some clarification text about differences between the controlled and complete-procedure studies
Questions for authors
  1. As mentioned in the critical weakness point #1, some demonstration experiments are missing. Have the authors previously explored them?
  2. The authors can improve some sections regarding the weakness point #2 by providing more details such that the readers can have a better understanding.
3 comments
AuthorsOpenReview ↗

Response to Reviewer s5MX

Thank you for your careful review and positive assessment of the theory and the experiments. Your first point led us to state more precisely what the experiments support.

W1 and Q1. Connecting the guarantees to practical reasoning traces. We agree that this connection needed to be demonstrated. On Q1: yes, the demonstration (coordination and selection) experiments were in the submission, but without explicit links to the theorems. We also added two new checks of Theorem 1’s condition, a price analysis of the previews, and a new experiment with executable tests. Overall, to make this explicit, we added a new Table 1, pairing Theorems 1–2 and Eq. (2) with the experiments that test or illustrate them. Next we detail this pairing between theory and experiments:

  1. Theorem 1 and coordinated sampling (Sec. 4.1). Line up a model’s possible outputs by their tokens. The lattice sampler used there spreads a batch’s kk draws evenly along this line, which App. E.1 shows is Theorem 1’s systematic sampler, optimal when the outputs naming each answer are adjacent. If the model states its answer first, outputs giving the same answer begin with the same tokens and sit together, up to different names for one answer; if it reasons first, they are scattered. The results follow this condition:

    • Answer first: coordination adds 0.04–0.20 distinct correct answers per four outputs (9–20% over independent sampling) in all six model-and-evidence settings, every interval above zero.
    • Reasoning first: no change is detected in any setting; the difference between the formats is significant in all six after Holm correction.
    • A necessary condition for adjacency holds on generated batches for 92% of repeated answers with the answer first, against 39–41% in the other cases.

    For practical reasoning traces, the role of Theorem 1 is to show how little information coordination needs: no model of how attempts overlap, only an order in which outputs with the same final answer are adjacent. Answer-first decoding supplies that order for free. Reasoning-first decoding does not, so there the theorem gives no guarantee, and we observe no gain; such traces need the order from another source (Discussion). The rate at which an order can be learned, and the bounds of Theorem 3, are illustrated numerically (Apps. B.6, D.5).

  2. Eq. (2) and selection from shared forecasts (Sec. 4.2). Eq. (2) splits a batch’s gain into two parts: better individual outputs and fewer repeats. Given the same previews of eight unfinished traces, choosing four for what they add together picks less reliable outputs individually, with per-output precision 1.91 points lower, yet recovers 0.279 more distinct correct answers per batch than ranking them one at a time. So the gain comes from fewer repeats. A simpler joint score also beats ranking on two further backbones (by 0.248 and 0.299, both significant).

  3. Theorem 2 and the price of early information (Secs. 3.2, 4.3). A diagnostic (an early look at an unfinished candidate, such as a preview) pays only if its price is below C(1−p)(α−β)C(1-p)(\alpha-\beta): the cost CC of a completion, times the share 1−p1-p of candidates that are not useful, times how much more often it flags useful candidates than others. We applied this twice. In question answering, the preview we chose is costly: a prefix and two previews cost 0.97–1.45 times a completion, leaving little or no room for them to pay (none on two of three models). That is the price of this preview, not of early information in general: a cheaper preview would face a much lower bar (App. G.3.3). For executable tests (new experiment), Sec. 3.2 gives a practical recipe: finish a sample of candidates, measure how often the diagnostic flags useful and other ones, and buy it only if the gap reliably exceeds what its price requires. A screen on a test’s first 128 tokens flags 30% of useful tests and 24% of the others, too small a gap to justify its price; a direct comparison agrees (first useful test in 4 of 32 episodes, against 9 of 32 for direct generation; App. H.4).

Changes in the paper. New Table 1 and the opening of Sec. 4 set out this pairing; Sec. 4.1 is rewritten around Theorem 1 (App. E.1); Sec. 3.2 shows how to apply the purchasing rule and Sec. 4.3 applies it (Apps. G.3.3, H.4); the Discussion states the limitation.

W2 and Q2. The controlled and complete-procedure studies. We agree that the submission did not make this difference easy to see. The controlled study (Sec. 4.2) gives every selection rule the same candidates and previews at no charge, so it measures only how well each rule uses that information. The complete procedures (Sec. 4.3) pay for every preview and completion, so they measure whether better selection repays the generation it displaces.

Changes in the paper. Sec. 4.3 opens with this distinction, and new Table F1 (App. F.1) sets the two protocols side by side.

Reviewer_s5MXOpenReview ↗

Respond to author's comments

Thanks the reviewers for answering some issues in the comment. However, there are still some issue (e.g., lack of experiments to justify the points, the novelty is still limited from certain view)

Thank you.

Could you specify which claim you feel lacks experimental support, or which prior work limits novelty? Table 1 pairs each result with its test: Theorem 1 with the entity-first vs. rationale-first coordination experiment (six settings, Holm-corrected), Eq. (2) with the controlled selection study (three backbones), and Theorem 2 with measured preview prices and the new test-generation experiment. On novelty, Theorem 1 gives the condition under which coordinated samplers such as QuasiMoTTo are optimal. Theorem 2 extends the one-check calculation of Aouad et al. (2026) by showing that repeated or buffered checks cannot widen the profitable price range.

We would be glad to address any specific gap before the discussion closes and, if our answers resolve your concerns, would appreciate your considering an updated score.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of the revision

We thank the area chair and the three reviewers for their careful and constructive reviews, which led to new analyses, experiments, and a clearer paper. Reviewer s5MX finds the paper “very unique by providing substantive theoretical results”; Reviewer vhdF notes “a clear definition of semantic coverage”; Reviewer 2twG values the “honest results”. The concerns are specific: the link between the theorems and the experiments (vhdF, s5MX); whether what the purchasing rule needs can be measured, and where the framework is useful (vhdF, 2twG); the motivation and role of each part of the method (2twG); and the difference between the two studies (s5MX).

How the revision resolves each concern. New Table 1 pairs Theorems 1–2 and Eq. (2) with the experiments that test or illustrate them.

  1. Theorem 1’s condition is now tested in language-model outputs (vhdF, s5MX). Theorem 1 shows how little information coordination might need: no model of how attempts overlap, only an order in which outputs that give the same answer sit next to each other. Sampling evenly along such an order is then optimal. Decoding supplies this order for free when the model states its answer first, because outputs with the same answer then begin with the same tokens (up to different names for one answer). The sampler of our coordination experiment is the theorem’s sampler (Sec. 4.1, App. E.1), and the results follow the theorem’s condition:

    • Answer first: coordination adds 0.04–0.20 distinct correct answers per four outputs (9–20% over independent sampling) in all six settings, at no extra generation.
    • Reasoning first: outputs with the same answer are scattered, so the theorem gives no guarantee, and we observe no gain; such traces need the order from another source (Discussion). The rate at which an order can be learned is illustrated numerically.
    • New check of the condition: a consequence of adjacency holds for 92% of answers named at least twice with the answer first, against 41% under independent sampling.
  2. The gain of joint selection comes from avoiding repeats (s5MX). Eq. (2) splits a batch’s gain into two parts: better individual outputs and fewer repeats. In the controlled study, every rule sees the same previews of the same unfinished traces. Choosing traces for what they add together recovers 0.24–0.32 more distinct correct answers per batch than ranking them one at a time (two joint scores, three backbones). In the main comparison, the chosen outputs are individually less reliable, so the gain comes from fewer repeats.

  3. Theorem 2 is now applied to measured prices (vhdF, 2twG, s5MX). Theorem 2 gives the price below which an early look at an unfinished attempt pays: a fraction of the cost of finishing it, set by how common useless attempts are and how well the look separates useful ones from the rest. The preview we chose for SCPS is costly: a prefix and two previews cost 0.97–1.45 times a completion, which leaves little or no room for them to pay (none on two of three models; Sec. 4.3, App. G.3.3). The realized runs agree in direction: under the same ceiling, the same loop without previews recovers 0.29–0.84 more distinct correct answers, for 4–17% more tokens and slightly lower F1 on two models. This is the price of the preview we chose, not of early information in general: one that cost only its output tokens would face a much lower bar.

  4. What the purchasing rule needs can be measured on a labeled sample (vhdF). Sec. 3.2 now gives a recipe: finish a sample of candidates, measure how often the early look flags useful candidates and how often it flags the others, and buy it only if the gap reliably exceeds what its price requires (sample sizes in App. C.5). A new experiment on executable tests follows it: a screen on a test’s first 128 tokens flags 30% of useful tests and 24% of the others, too small a gap for its price, so the rule declines it (App. H.4).

Motivation and clarity. Following Reviewer 2twG, the introduction’s first paragraph now separates our problem from Self-Consistency’s, names tasks where it arises naturally, and reports that requesting the whole list in one prompt recovers on average only 22–29% of a question’s answers. The opening of Sec. 4.2 now explains each part of SCPS. Following Reviewer s5MX, Sec. 4.3 opens by stating that the controlled study gives every rule the same information for free, while the complete procedures pay for it.

What the revised paper offers. As models get more attempts per task, how to spend them becomes a practical question. The revised paper now ties its theory more closely to the experiments and gives practitioners a rule they can apply: buy early information only when a labeled sample from their own task shows that its price is low enough.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.