- Rating
- 2
- Confidence
- 2
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper is ambitious in proposing the first ever practical LM verification framework BEAVER. It applies existing practices of branch and bound from neural networks to language models. BEAVER computes deterministic probability bounds for given data using a token trie and a frontier. Based on the results, BEAVER outperforms sampling-based verifier and shows potentials in saving computations and data.
Critical strengths
- This paper is studying a timely and useful topic, and its results show very promising effects
- This approach is simple and flexible, easy to upgrade and integrate, and also show the power in multiple tasks
Critical weaknesses
- The approach seems very limited in practical usage. Its complexity will explode as the answer length increase. And also in experiments, the answer length is 16 tokens or 32 tokens which is very short.
- Not very sure about the baselines are strong enough. Some existing NN verifiers can be flexible enough as better baselines for LM verification.
- The proof on the optimality seem not serious enough, which seems naive considering it is repeating the property of greedy decoding. Not sure about the effects of tolerance in the proof.
- This paper seems not yet completed, especially these mess contents of the statements in page 10. Also, I saw lots of grammar errors and expression issues, such as frequent “Equation equation 4”, etc.
Questions for authors
- Whether there are any methods to reduce the time cost? for example, the time cost for a short inference is around 2 minutes in H100 which seems very expensive. Any good ideas?
3 comments
Dear Reviewer xTF8,
Thank you again for your review. With the discussion period closing soon, we wanted to check whether our response addressed your concerns. We believe our responses address every point raised and we have committed to the corresponding revisions. We would also emphasize the significance of what BEAVER establishes: it is the first method to place deterministic, sound bounds on the probability mass an LLM assigns to violating responses, a guarantee no benchmark or sampling procedure can provide. Existing evaluations sample only a few responses from a model’s output distribution, so a model can appear safe while unsafe responses remain in the tail. Adversaries can reach that tail by repeated sampling [1] or by altering the decoding algorithm [2]. Sampling also makes evaluation stochastic. Researchers report reaching different conclusions about the same model across evaluation runs, which makes results hard to reproduce [3, 4]. BEAVER’s bounds do not depend on random sampling, so they are reproducible and directly comparable across models and checkpoints. This matters most for open-weight models deployed by parties who did not train them: whoever holds the weights can remove every guardrail, so the model’s own behavior is the only defense.
We see this as a first step that we intend to carry considerably further. We would be grateful to know whether our responses resolve your concerns, and are glad to run any further experiment you consider decisive while the discussion period remains open.
References [1] Huang, Yangsibo, et al. “Catastrophic jailbreak of open-source LLMs via exploiting generation.” International Conference on Learning Representations. 2024. [2] Vega, Jason, and Gagandeep Singh. “Matching ranks over probability yields truly deep safety alignment.” arXiv preprint arXiv:2512.05518 (2026). [3] Ouyang, Shuyin, et al. “An empirical study of the non-determinism of ChatGPT in code generation.” ACM Transactions on Software Engineering and Methodology 34.2 (2025): 1–28. [4] Song, Yifan, et al. “The good, the bad, and the greedy: Evaluation of LLMs should not ignore non-determinism.” arXiv preprint arXiv:2407.10457 (2024).
Dear Reviewer xTF8,
Thank you once again for your time and effort in reviewing this paper. I am grateful for your thoughtful comments and your contribution to the review process.
The authors have responded to your initial feedback. When you have a chance, could you please read their responses and participate in the discussion with them?
Thank you so much for your continued help!
Best regards,
Your AC
Response to Reviewer xTF8
We thank the reviewer for their feedback, and for finding the topic timely and the approach flexible.
Weakness 1: Complexity with answer length
Please see our response to Reviewer gpa4, Weakness 3. In short, LLM output distributions are neither concentrated enough for sampling to suffice, nor spread out enough to make verification intractable. Beaver expands the most probable unresolved prefix anywhere in the token trie, so the bounds tighten quickly. The bounds are also sound at every step, which lets a practitioner stop whenever the bounds meet their safety requirements. In addition, many safety violations happen within the first few tokens. In our experiments, the tasks set the generation lengths: On privacy, 16 tokens exceed every email address in the leaked set.
Beaver also handles longer generations. On toxicity with Qwen3-4B, raising the maximum length from 32 to 128 tokens leaves the risky count unchanged (50). Past depth 48, almost no prefix has probability above ϵ, so 64 and 128 tokens give the same certificate (see our response to Reviewer gpa4, Weakness 3).
Weakness 2: Baselines
Please see our response to Reviewer gpa4, Weakness 2 for all details. Traditional NN verifiers such as DeepPoly and α,β-CROWN [1][2] are designed for models that run a single forward pass over an input region, and are not designed to handle the probabilistic autoregressive generation of LLMs. They cannot reason about the probability distributions over responses, and bound propagation methods scale at most to small transformers [3][4]. We tried to apply α,β-CROWN on Qwen3-4B and GPT-2, and it did not run on either model. Therefore, these verifiers cannot be used as baselines for this problem.
Weakness 3: Optimality proof and greedy decoding
Beaver does not perform greedy decoding. Greedy decoding follows a single path, picking the most probable next token at each step without going back. Beaver's Max-μ strategy instead selects the most probable unresolved sequence anywhere in the token trie, which is often not a continuation of the most probable response. This is a best-first search, similar to Dijkstra's algorithm with an edge cost of −logP(t∣prefix). For example, in the walkthrough in Appendix C, greedy decoding only produces ls -la. Beaver also expands echo and rm, finds the violating response rm -rf /home, and certifies P∈[0.58,0.91] after 8 forward passes. We will revise by adding a figure of this example.
The tolerance ϵ defines which sequences must be resolved, namely all sequences with probability greater than ϵ. Every sound verifier must expand all of these sequences to reach tolerance ϵ, and Max-μ expands exactly these sequences, for every ϵ (Theorem 4.6). Therefore, no other selection strategy can verify up to tolerance ϵ in fewer forward passes. Table 8 confirms this empirically: Sample-μ and UCB-based selection need 1.3-2.4× more forward passes.
Weakness 4: Writing
We thank the reviewer for pointing this out. The repeated "Equation equation" was caused by an error in our macro definitions. The statements on page 10 are the AI use and ethics statements required by the template, together with placeholder text from the template that we failed to remove. We will revise the paper ensuring no errors are present in the final version.
Question: Methods to reduce the time cost
We would like to clarify that 2 minutes is the latency of a single prompt when Beaver verifies 32 prompts in parallel, and not the time per prompt. The actual throughput is 4.2-4.7 s per prompt on a single H100 (Table 7), and all 300 prompts of a task are verified in under 25 minutes. Beaver already uses several optimizations to reduce this cost as listed in Appendix E. A further direction is incremental verification[5], where an explored trie is reused for a related prompt or a new version of the model, making repeated verification cheaper.
Citations:
[1] Gagandeep Singh, Timon Gehr, Markus Püschel, and Martin Vechev. 2019. An abstract domain for certifying neural networks. Proc. ACM Program. Lang. 3, POPL, Article 41 (January 2019), 30 pages. https://doi.org/10.1145/3290354
[2] Xu, Kaidi, et al. "Fast and complete: Enabling complete neural network verification with rapid and massively parallel incomplete verifiers." arXiv preprint arXiv:2011.13824 (2020).
[3] Bonaert, Gregory, et al. "Fast and precise certification of transformers." Proceedings of the 42nd ACM SIGPLAN international conference on programming language design and implementation. 2021.
[4] Shi, Zhouxing, et al. "Robustness verification for transformers." arXiv preprint arXiv:2002.06622 (2020).
[5] Ugare, Shubham, et al. "Incremental verification of neural networks." Proceedings of the ACM on Programming Languages 7.PLDI (2023): 1920-1945.