acceptodds
Under review as a conference paper at ICLR 2027

Safety after Sharpening: Certified Risk Bounds for Autoregressive Language Models

Abstract

Global power sampling makes a language model's more likely responses more prominent by raising the probability of each complete response to a power and then renormalizing. Recent work uses this approach to improve reasoning without further training karan2026,ji2026, but it can also make incorrect responses more likely. We study how to compute guaranteed lower and upper bounds on the probability of a specified failure after this change of distribution. Our method evaluates selected partial responses with rigorous numerical error bounds and bounds the contribution of every unevaluated continuation. We prove that these intervals can be made arbitrarily narrow for autoregressive transformers that retain all earlier tokens, at any fixed generation length within their context limits, although the worst-case cost is exponential. We also bound failure probabilities when generation stops at the first end-of-sequence (EOS) token or a length limit. When verified bounds on EOS probability and the sum of powered non-EOS token probabilities hold after every reachable partial response, we bound the combined weight of all remaining responses without enumerating them. On a 17-state model with probabilities and stopping bounds checked for every state, these bounds reach interval width while avoiding 8–11 iterations of a dynamic-programming baseline, after both methods evaluate the same next-token probabilities. GPT-2 experiments reach width on 22 of 24 two-token tasks and 8 of 24 longer tasks. In an instruction-tuned model, we certify at least a 9.15-percentage-point increase in the probability of an incorrect initial verdict for one eight-token prompt. In a separate two-token control with equally long answer labels A and B, the effect reverses when we swap their meanings.

Primary area:
learning theory
Keywords:
global power sampling, autoregressive language models, risk certification, numerical verification, AI safety

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_JQvjOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The gap the authors identify is that sampling a few high probability answers and renormalizing leaks the remaining probability mass, which can affect risk, while ordinary floating point inference cannot provide strict numerical guarantees. The method explores partial generation prefixes, controls numerical error with outward rounded interval arithmetic, and keeps a probability mass bound on unexplored branches. For EOS stopping, the authors also derive a tail bound from the stopping probability and the mass of continued generation. The paper certifies the probability of specified program events. It is not a general semantic safety certificate for full responses, and it differs from standard token level temperature reduction.

Critical strengths

The paper states clearly what is certified and where the guarantee ends. Unqueried branches are neither deleted nor renormalized into a top-k answer set. The analysis separates interval width from failure probability, absolute from relative precision, and true semantics from finite precision implementation.

Table 1 reports quantifiable certification results. In the GPT-2 two token experiment, after querying 129 full vocabulary probability rows per prompt, 22 of 24 tasks reach an interval width of at most 0.01. Only 9 satisfy U/L ≤ 2, and the authors do not mistake a narrow absolute interval for an accurate estimate of rare risk.

The experiments also contain one rigorously valid risk change result. In Table 6, the initial verdict error event has an interval of about [0.1713, 0.1777] under the original distribution, and [0.2693, 0.9631] at α = 2. The latter interval is wide, but its lower bound exceeds the upper bound of the original interval, so the risk increases by at least 9.15 percentage points.

The appendix results on query complexity lower bounds and hardness under program representations help explain the scaling bottleneck. The authors state explicitly that these results do not imply computational hardness for any specific Transformer checkpoint.

Critical weaknesses

W1 The actual scale is very small. The full GPT-2 two token experiment already takes about 34.4 minutes. In Table 2, only 8 of the 24 events at four to eight tokens reach the 0.01 target width, and the eight token "France" interval still has width 1, which is uninformative.

W2 The certified events are far from real safety problems. GPT-2 mainly checks digits and newlines, and the instruction model has only 135M parameters, with events that mostly check initial labels. A mathematically reliable event does not automatically give a semantically meaningful safety guarantee.

W3 "risk amplification" may reflect answer format bias. In Table 7, swapping the correct and incorrect code between A/B encodings reverses the direction of the risk change. The error rate drops when the correct code is A and rises clearly when it is B. The effect therefore cannot be attributed directly to the model favoring dangerous answers or flawed reasoning. The authors acknowledge this as a limitation rather than hiding it.

W4 The efficiency gains are not yet shown on Transformers. The 8 to 11 Bellman sweeps in Table 3 come from a verified 17 state model, which is not equivalent to node level neural model queries or real runtime. Some of the foundational theorems are also fairly direct, so the incremental contribution needs more

Questions for authors

Q1. Besides combining existing bounds, what is the most critical new technique introduced in this paper? Can you provide a computational baseline with equivalent rigor?

Q2. For the approximate power sampler used in practice, how is the verification of the target distribution transformed into a guarantee of the realized distribution?

Q3. Have the efficiency gains not yet been reliably tested on Transformers? The 8–11 Bellman sweeps saved in Table 3, derived from a 17-state model with all states validated, do not equate to savings in neural model query or actual runtime.

3 comments
AuthorsOpenReview ↗

Implemented sampler, format control, and empirical scope

Thank you for the careful review and for highlighting the clear scope of the guarantees and the certified 9.15-percentage-point increase in wrong first verdicts. Your questions prompted us to clarify how the guarantee applies to an implemented sampler and to measure certification time on a Transformer.

Our position. We believe the risk certificates are sound within their stated scope. Answer format affects what the verdict experiment measures, and verification cost affects how quickly we can obtain a narrow interval. For a specified failure event and checkpoint evaluated in real arithmetic, Theorem 1 guarantees that the interval contains the true risk. We enclose queried probabilities by outward rounding and bound the contribution of every unqueried branch. For our implemented sampler, we preserve coverage by widening the interval by a certified total variation bound (Q2). On this basis, we kindly request that you reconsider the soundness rating.

W1, W4 / Q1. What is new, and how does it compare with an equally rigorous baseline? The report checker identifies transitions that every correct completion must pass through. Verifying rows at these transitions bounds the powered weight of correct completions before their ancestor rows are verified. In a controlled eight-field case with 643 accepted token sequences, this approach needs 6 rows versus 11 for grammar-aware ancestor-first search at power 2 and width 0.01. Both use exact rows, give the same deterministic guarantee, and visit 10 nonprompt prefixes. Separately, Proposition 3 avoids 8–11 Bellman sweeps using the same 17 verified rows. On the original SmolLM2 prompt without a worked example, none of the six-row schedules reaches width 0.01.

Q2. Which sampler inherits the guarantee? Our sampler draws from certified lower powered weights using an exact uniform integer draw. If these weights sum to Λ>0\Lambda>0 and the full normalizer is at most Z‾\overline Z, total variation from the target is at most η=1−Λ/Z‾\eta=1-\Lambda/\overline Z. The ideal risk interval [L,U][L,U] then transfers to [max⁡(0,L−η),min⁡(1,U+η)][\max(0,L-\eta),\min(1,U+\eta)]. With 129 rows per GPT-2 prompt, η≤0.01\eta\le0.01 in 11 of 12 two-token settings and η≤0.03919\eta\le0.03919 in the remaining setting (Table 9). Other decoders require their own bound on the difference between output distributions.

Q3. Does batching reduce Transformer certification time? During rebuttal, we implemented batched verification of candidate response prefixes and tested it on 24 new SmolLM2 records (Section 5.4 and Appendix D.10.1). At power 2, all three methods reach width 0.01 on the same 15 records within 420 seconds and 64 rows. Batching is faster on all 15, with identical verified row counts on each record. The median paired savings are 96.21 seconds (34.02%) versus verifying the same paths sequentially and 103.19 seconds (36.24%) versus best-first. All three methods miss the target on the other nine records. Timing includes candidate planning where used and record-specific prefill. Preparing the shared template cache took 135.64 seconds and was timed separately.

On one Qwen2.5-3B prompt, batched CPU verification completes eight fixed continuation rows in 16.9 minutes after shared prefill and root evaluation. The serial run completes five rows within 45 minutes. Whole-report intervals stay essentially [0,1][0,1], so this comparison measures the time to produce verified rows (Appendix D.4).

W2–W3. What does the verdict experiment establish? The original result certifies an increase of at least 9.15 percentage points in wrong first verdicts at power 2. The parser scores only the leading verdict. In a post hoc control at the same eight-token cap, swapping equal-length A/B answer codes reverses the direction at powers 4 and 8 (Table 12). The swap also changes the prompt, so the cause of the original increase remains open. In a separate BF16 greedy pilot on an RTX 3090, Qwen2.5-3B-Instruct gets all eight JSON fields right in 7 of 12 cases (Appendix D.3).

Reviewer_JQvjOpenReview ↗

Thank you for the additional experiments and the candid concessions

My remaining concerns are mainly about motivation, which the rebuttal does not resolve.

I) Who needs this certificate? The paper is motivated by risk leakage in top-k sampling and the lack of strict numerical guarantees in floating-point inference. But the guarantee holds for a real-arithmetic model and a specified event, while deployed systems run in FP16/BF16 with approximate samplers. Q2 was answered for a newly designed sampler, not for the sampler used in practice. The certificate therefore does not cover the system whose risk motivated the work.

ii) The regime where certification works is the regime where it is least needed. Tight intervals are obtained only for short horizons, small models, and simple events (digits, newlines, leading labels), where the relevant mass is nearly enumerable. At 4–8 tokens or on the 3B model, intervals are mostly vacuous. The rebuttal’s new results (batching speedups on 15/24 records, one Qwen prompt) are engineering gains and do not change this.

iii) The headline use case is not supported. The motivating example is certified risk amplification, but the A/B-swap control shows the effect may come from answer-format bias, and it is not reported at power 2, where the claim is made. It is unclear what real risk question this certificate answers.

I would encourage the authors to articulate a concrete setting where such a certificate changes a deployment decision, and to reframe the contribution accordingly. I will weigh these points in my final assessment.

AuthorsOpenReview ↗

What the certificate tells us when we change the sampling rule

Thank you for reading the additional experiments and for asking us to show what deployment decision the certificate can support.

Our position. A team testing a decoding change before deployment can use a certificate to bound how often the intended decoder would trigger fallback on a fixed report input. We now certify the power target induced by a pinned BF16 base decoder and estimate the approximate sampler’s fallback rate from independent draws. Thank you for asking us to make this decision concrete.

I. Who needs the certificate, and which decoder does it cover? Inference settings can change BF16 outputs [1], and finite-budget power samplers can depart from their target [2]. We separate these effects on the same 24 SmolLM2 records. At power two, the exact-real and pinned BF16 target intervals are disjoint on 17 records. The approximate blockwise sampler's simultaneous 95% confidence intervals are disjoint from its BF16 target on three records, based on 2,048 independent runs per record and decoder. See Section 5.4 and Appendix D.10.2 of the revised manuscript.

RecordExact-real power-two targetBF16 power-two targetApproximate BF16 sampler (95% simultaneous CI)
125.90–6.79%4.74–5.60%3.33–6.48%
2215.67–15.95%20.15–20.45%5.78–9.67%

If every checker failure triggers fallback, the intervals can be compared with a fallback budget. We chose 10% after the original runs to illustrate the decision. On record 12, ordinary decoding exceeds 10%, and both power-two targets and the audited sampler clear it. On record 22, both targets exceed 10%, while the tested sampler clears it under the reported stopping rule. Its failure probability is at least 10.48 percentage points below its BF16 target at the audit confidence level. If the policy rejects early returns without EOS, counting up to 47 extra failures raises the conservative upper bound to 12.20% and leaves the decision unresolved.

The same comparison can inform a fidelity requirement. On record 14, the reference table is within 0.643 percentage points of the exact-real target in total variation. The approximate sampler differs from that target on report failure alone by at least 18.55 points at the audit confidence level. A one-point total-variation requirement would clear the reference table and reject the approximate sampler on this record.

II. Does certification help beyond short or simple events? Our SmolLM2 checker compares all eight JSON fields with the source record and rejects malformed or incomplete reports. This follows JSONSchemaBench's distinction between schema compliance and task accuracy [3]. Verified correct reports take 38–42 tokens under a 64-token cap. The exact-real certificate resolves the 10% decision on 23/24 records, including eight with intervals wider than 0.01. Both audited decoders fail a gate that requires all 24 records to pass. Scale remains a limitation. Evaluating and certifying the BF16 target on 1,300 previously selected prefixes took 136 seconds on CPU. The Qwen2.5-3B BF16 pilot evaluated 12 rows on one record and returned an interval essentially [0,1][0,1]. Saved outputs and replay scripts for both models are in the updated supplement.

III. What does the answer-format control establish? Answer-token preferences can contribute to option-order sensitivity [4]. Section 5.2 and Table 12 now report the equal-length A/B swap at power two and the original eight-token horizon. With B correct, wrong-code risk rises from 51.71% to at least 76.17%. With A correct, the direction remains unresolved. The swap also changes the prompt, so the cause of the original effect remains open. In the whole-report comparison, the format is fixed within each record and the checker scores the complete output.

We would appreciate your reassessment in light of these results.

References

  • [1] Yuan et al. Understanding and Mitigating Numerical Sources of Nondeterminism in LLM Inference. NeurIPS 2025. Paper
  • [2] Talwar, Nemeth, and Moss. A Critical Look at Power Sampling when Test-Time Sharpening LLMs. 2026. §3
  • [3] Geng et al. JSONSchemaBench: A Rigorous Benchmark of Structured Outputs for Language Models. 2025. §6
  • [4] Zheng et al. Large Language Models Are Not Robust Multiple Choice Selectors. ICLR 2024. Paper
Reviewer_scQmOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies deterministic certification of failure probabilities under global power sampling, which raises complete-response probabilities to a power and renormalizes over all responses. The proposed method combines outward-rounded transformer evaluation with partial exploration of the response tree, retaining bounds on the powered mass of every unexplored continuation. It establishes eventual convergence at fixed generation lengths within the model’s context limit, gives worst-case query and computational hardness results, and derives continuation bounds under uniformly verified stopping conditions.

Experiments demonstrate certificates for selected short GPT-2 and SmolLM2 outputs, including a certified increase in wrong-verdict probability after sharpening. A finite-state experiment illustrates how verified continuation bounds can avoid repeated Bellman updates.

The paper carefully distinguishes global powering from local temperature sampling, absolute from relative precision, and fixed-length from EOS-stopped generation. Its explicit discussion of assumptions and unsuccessful cases helps prevent overinterpretation of the results.

Critical strengths

The paper provides a sound framework that accounts jointly for numerical uncertainty and unexplored response mass. The method retains the full vocabulary and bounds unevaluated continuations rather than renormalizing over selected outputs. This matters under global powering because continuations affect the normalizer even after a prefix has determined the failure outcome. The convergence argument and the distinction between capped and EOS-ended responses are convincing. I did not identify a substantive technical flaw in the stated results.

The implementation and experiments demonstrate meaningful certification capabilities while reporting their limits clearly. The full-history transformer evaluations go beyond a purely abstract bounded-search formulation. In particular, the nonoverlapping ordinary and sharpened risk intervals establish at least a 9.15-percentage-point increase in wrong-verdict probability for one eight-token task. The paper also retains uninformative intervals, invalid outputs, and answer-format controls, and correctly avoids interpreting these certificates as unrestricted semantic-safety guarantees.

Critical weaknesses

The mathematical novelty is relatively modest, and the contribution is strongest as an integration of established techniques. Theorem 1 follows from monotonicity of the normalization ratio, the frontier bounds use standard bounded-search reasoning, and Corollary 2 establishes convergence through finite enumeration and increasing numerical precision. Proposition 3 uses scalar bounds preserved by a monotone continuation recursion. The hardness results add substance, but concern general autoregressive sources rather than transformer checkpoints. The paper would benefit from identifying more clearly which aspects of the combined certification procedure constitute the principal methodological advance over existing bounded weighted-search and rigorous inference approaches.

The evidence for practical scalability remains limited. GPT-2 certificates attain width 0.01 on 22/24 two-token tasks but only 8/24 longer tasks; eight-token France-prompt intervals remain essentially uninformative. Useful uniform continuation bounds are not established for the tested transformers: the reported GPT-2 bound has (1-\rho) on the order of (10^{-707}). The continuation-saving experiment instead uses a 17-state family constructed with nearly constant continuation-ratio values, after both methods have evaluated the same probability rows. Avoiding 8–11 Bellman sweeps is a valid result, but does not establish fewer neural evaluations or practical runtime savings. These limitations constrain the demonstrated scope, although the paper acknowledges them appropriately.

Questions for authors

Clarification of novelty: Which component of the method requires a substantive extension of existing bounded weighted-search or rigorous numerical-inference techniques? A more explicit distinction between the new methodological contribution and the application of established bounds would help assess the paper’s significance.

Clarification of the continuation benchmark: How sensitive are the formula widths and avoided Bellman sweeps to greater variation in (\theta(h)=e(h)/(1-c(h)))? The current family preserves this quantity exactly or perturbs it slightly. Can the authors provide evidence or analysis identifying when the continuation bounds remain informative outside this favorable setting?

2 comments
AuthorsOpenReview ↗

Technical contribution and sensitivity of the continuation bounds

Thank you for the detailed review. We appreciate your recognition that the framework accounts for numerical error and unexplored continuations, and that the experiments report where the bounds are loose. Your questions helped us sharpen the statement of novelty and test how sensitive the EOS bound is to variation within a subtree.

Our position. We agree that the paper uses standard bounded search and rigorous arithmetic. The main addition is an upper bound on the powered weight of correct reports that uses verified mandatory transitions without first verifying their ancestor rows. The EOS formula gives a separate gain when continuation bounds are tight within a subtree.

W1 / Q1. What is specific to global-power certification? Proposition 4 uses the checker to find a mandatory transition, such as EOS after a completed valid object. A prefix-free cover of successful responses bounds their powered weight using only the rows at those prefixes, even when ancestor rows are unavailable. In the late-bottleneck case of a controlled fixture with 643 accepted token sequences, this takes 6 rows versus 11 for a grammar-aware ancestor-first baseline at width 0.01 and power 2. Both use exact rows and the same risk guarantee. Proposition 3 also bounds an EOS-stopped subtree when verified stopping and continuation bounds hold throughout it. Appendix A.2 gives the complementary worst-case result of exponentially many row queries for a first-bit event at power two.

Q2. What happens as the continuation ratio varies within a subtree? Greater variation can make the formula miss the target width even when bounded Bellman iteration still reaches it. Let e(h)e(h) be the powered EOS weight and c(h)c(h) the sum of the powered non-EOS weights. If θ(h)=e(h)/(1−c(h))\theta(h)=e(h)/(1-c(h)) lies in [ℓ,u][\ell,u] and c(h)≤ρc(h)\le\rho throughout the subtree, Proposition 3 bounds the continuation interval width by (u−ℓ)+(1−u)ρr(u-\ell)+(1-u)\rho^r with rr tokens remaining. Appendix B.6 tests 21 cases using exact arithmetic and the same verified rows for both methods. Table 5 shows three perturbation levels.

Perturbation at cap 32Formula reaches risk width 0.01Bounded Bellman sweeps at powers 2 / 4 / 8
1/40961/4096Powers 2, 4, and 811 / 9 / 8
8/40968/4096Power 8 only11 / 9 / 8
32/409632/4096No powers11 / 9 / 8

At power 2, the formula’s risk interval widens from about 0.00765 to 0.06114 and then to 0.24179. The perturbation changes both EOS and non-EOS weights, so this measures sensitivity to the joint change. The spread term explains why certifying tighter regions can help.

W2. What work does the formula save? It saves continuation updates on the 17-state model. Both methods verify the same 17 rows, and the formula avoids 8–11 Bellman sweeps (Section 5.3). On GPT-2, the weight-derived continuation bound is too loose to improve the intervals. At the reported row budgets, 22/24 two-token and 8/24 four- or eight-token tasks reach width 0.01. The separate timing comparison on 24 new SmolLM2 records tests batching at power 2. All three arms reach width 0.01 on the same 15 records under a 420-second and 64-row budget. Each such record uses the same number of verified rows across methods. Batching reduces the paired request-to-certificate time by a median of 103.19 seconds versus best-first and 96.21 seconds versus the same targeted search run serially. The shared fixed-example cache is prepared before timing.

Thanks for the response and the additional details. It addresses my questions, and I am maintaining my weak-accept recommendation.

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

Global power sampling works by "sharpening a distribution", making likely responses even more likely. As a consequence, it can also exacerbate incorrect, or unwanted, responses by making them more likely. The authors study an interesting problem: how do you compute certified bounds on the probability of a specified failure under a sharpened distribution. The authors bound unexplored responses explicitly, evaluating selected partial responses with numerical error bounds, summing the powered weights of responses with known outcomes, and bounding the rest. This gives a guaranteed interval for failure probability that can be made arbitrarily small, although often at exponential cost. When the authors are able to verify uniform bounds on EOS probability and the sum of powered non-EOS token probabilities, the authors are able to bound the combined weights of all remaining responses without enumerating them.

Critical strengths
  • I think the studied problem is a very timely, and very ambitious technical problem.

  • The authors offer a principled anytime framework for bounding failure probability under sharpened autoregressive distributions: the framework maintains valid bounds that are progressively refined as the trajectory space is being explored.

  • I quite liked section 4, which offers an interesting theoretical contribution by which, having established uniform bounds on the stopping and continuation probabilities for any arbitrary prefix, allows us to bound the aggregate probability of the entire continuation subtree without explicitly enumerating its sequences.

Critical weaknesses

My main concern is that, as it currently stands, their is limited evidence that this framework is of practical use. More precisely, to achieve the arbitrary tight intervals promised by the authors, one might need to explore exponentially many prefixes. Furthermore, while quite elegant, section 4 rests upon the assumption that we are able to certify a uniform bound on the stopping and continuation probabilities in the prefix tree, which is infeasible for LLMs.

Questions for authors
  • Could the approach in section 4 benefit from maintaining different local uniform bounds for different prefix subtrees, rather than relying on globally applicable bounds?

  • Do the authors know how the proposed certificate procedure compares with Monte Carlo estimates of the failure probability under a similar computational budget?

1 comment
AuthorsOpenReview ↗

Search cost, local continuation bounds, and comparison with sampling

Thank you for the careful review and for highlighting the timeliness of the problem and the value of refining valid bounds as search progresses. Your questions about subtree bounds and comparison with sampling helped us clarify where the method is practical.

Our position. We agree that exact certification can require exponentially many queries in the worst case. In our GPT‑2 experiments, heuristic prefix search reached the target interval width of 0.01 on 22 of 24 two-token tasks using 129 probability rows per prompt. In a matched-query comparison, deterministic search reached the same target in 312 of 480 runs, compared with 304 for importance sampling. The heuristic determines which prefixes we explore first. Every interval we return is guaranteed to contain the true risk, regardless of the search order.

We disagree that Proposition 3 requires a single uniform bound over the entire prefix tree. The stopping and continuation bounds must hold throughout the subtree to which they are applied, and different subtrees can use different bounds. We agree that efficiently verifying tight bounds within Transformer subtrees remains an open problem.

W1. Can certification take exponentially many queries? Yes, in the worst case. Appendix A.2 proves this for deterministic methods that access general autoregressive models through exact next-token queries. On GPT-2, 22/24 two-token tasks reached interval width 0.01 with 129 full-vocabulary rows per prompt. At four or eight tokens, 8/24 reached that width with 128 rows per prompt and length (Section 5.1). On 24 new eight-field SmolLM2 records with a worked example, the three schedules reach width 0.01 on the same 15 records at power 2, within 420 seconds and 64 verified rows. These records use 42–59 rows each, with the same count for all three schedules on each record. Batching lowers the median paired time by 103.19 seconds against best-first and 96.21 seconds against targeted serial, measured from the request to certificate writing with a shared fixed-example cache already prepared. The other nine records miss the target for all three schedules.

W2. Is it hard to verify useful bounds on transformer continuations? Yes. We verified a bound that holds for all histories within GPT-2’s context limit, and it was too loose to improve the tested intervals (Appendix C.1). The transformer results above use bounds from selected prefixes and account for all unqueried branches.

Q1. Can different subtrees use different bounds? Yes. Proposition 3 requires each set of constants to hold only throughout its own subtree. On the same 17 verified probability rows at cap 32, using separate bounds instead of one shared bound reduced the risk interval widths from 0.573 to 0.00765 at power 2, from 0.881 to 0.00543 at power 4, and from 0.993 to 0.000740 at power 8 (Table 4).

Q2. How does the method compare with Monte Carlo at similar cost? Deterministic search reached the target more often in our matched-cost test. On 24 two-token GPT-2 tasks with 20 seeds each, the importance-sampling method reached width 0.01 in 304/480 runs at 95% confidence. Deterministic search reached it in 312/480 with the same number of distinct full-vocabulary rows per run (Table 8). On the one task where sampling helped, it saved about 2.2% of rows on average. We sampled branches with importance weights. Direct Monte Carlo draws from the globally sharpened distribution and wall-clock time were outside this comparison.

Comments on the paper

2 comments
AuthorsOpenReview ↗

Summary of the revision

Thank you for the careful reviews. The revision shows how a checker identifies prefixes that every correct report must pass through. Verifying a mandatory transition can bound the weight of correct reports without first querying all ancestor rows. In a controlled eight-field fixture, this reduces the rows needed for width 0.01 from 11 to 6 against a deterministic, grammar-aware ancestor-first baseline. We also state the worst-case query barrier and the conditions under which the EOS formula bounds a whole subtree at once.

We revised the paper in response to three questions raised across the reviews:

  1. When do continuation bounds save work? Using the same 17 verified rows, separate subtree bounds give much tighter intervals than a single global bound. A perturbation sweep shows when the formula stops meeting the target width (Tables 4–5).
  2. How does search compare at a matched query budget, and what does an implemented sampler inherit? At matched distinct-row cost, the importance-sampling baseline reaches the target width in 304/480 replays, compared with 312/480 for deterministic prefix expansion (Table 8). Separately, an explicit two-token GPT-2 sampler has a certified total-variation bound of at most 0.01 in 11/12 prompt–power settings (Table 9).
  3. What does the failure test score? Swapping equal-length answer codes reverses the certified change in wrong-first-verdict probability at powers 4 and 8 (Table 12). The whole-report checker scores all eight JSON fields and counts invalid and incomplete responses as failures.

The revised experiments state the query budget with each transformer result and identify what the finite-state comparison measures: continuation updates after both methods verify the same 17 rows.

The revised manuscript reports the new timing comparison on 24 eight-field SmolLM2 records with a worked example in Section 5.4 and Appendix D.10.1. At power 2, the same 15/24 records reach width 0.01 within 420 seconds and 64 verified probability rows under best-first, targeted serial, and targeted batch search. The three methods verify the same number of rows on every jointly successful record. Batching is faster on all 15, with median paired savings of 103.19 seconds (36.24% median per-record savings) versus best-first and 96.21 seconds (34.02%) versus targeted serial. Timing includes path nomination where used, request-specific prefill, verification, and certificate writing. The shared fixed-example cache takes 135.64 seconds to prepare once and is timed separately. Independent replay checks all 3,877 interval checkpoints. The remaining nine records miss the target in all three arms.

Appendix D.4 of the revised manuscript reports the separate Qwen2.5-3B diagnostic. Batching verifies eight fixed continuation rows in 16.9 minutes after a 42.7-minute shared prefill and a shared root evaluation. Serial verification completes five within 45 minutes and a sixth at about 51 minutes. Common rows match exactly, and the whole-report intervals remain essentially [0,1][0,1].

Dear all reviewers,

The authors have responded to your concerns for a while. Please go through the response below and the revised submission to check whether your concerns have been adequately addressed, and if there are any follow-up questions where applicable. Thank you!

Best, AC

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.