- 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
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.
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.
| Record | Exact-real power-two target | BF16 power-two target | Approximate BF16 sampler (95% simultaneous CI) |
|---|---|---|---|
| 12 | 5.90–6.79% | 4.74–5.60% | 3.33–6.48% |
| 22 | 15.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 . 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
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 and the full normalizer is at most Z, total variation from the target is at most η=1−Λ/Z. The ideal risk interval [L,U] then transfers to [max(0,L−η),min(1,U+η)]. With 129 rows per GPT-2 prompt, η≤0.01 in 11 of 12 two-token settings and η≤0.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], 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).