acceptodds
Under review as a conference paper at ICLR 2027

Efficient Deterministic LLM Verification with Branch and Bound

Abstract

As large language models (LLMs) transition from research prototypes to production systems, practitioners need reliable ways to verify model outputs before they are deployed. While sampling-based estimates provide an ad-hoc intuition of model behavior, they offer no sound guarantees. We present BEAVER, the first practi- cal framework for computing deterministic, sound probability bounds on LLM constraint satisfaction. Given a prompt and a constraint, BEAVER systematically explores the model’s output distribution using a token trie and a frontier, maintain- ing provably sound bounds at every iteration. We formalize the LLM verification problem, prove that BEAVER’s bounds are sound and that its selection strategy Max-μ is optimal for verification upto any tolerance. On 3 important safety tasks across 5 popular LLMs, BEAVER certifies up to 7.6× more prompts as risky than a sampling-based verifier while using fewer forward passes, and its per-prompt bounds extend to statistical certificates over distributions of prompts.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
Large Language Models, Formal Verification, Safety Verification, Constraint Satisfaction, Neural Network Verification, Probabilistic Guarantees, Branch and Bound, LLM Safety, Trustworthy Machine Learning, Semantic Constraints, Model Certification, Robustness Verification

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_xTF8OpenReview ↗
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
AuthorsOpenReview ↗

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 ϵ\epsilon, 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 α,β\alpha, \beta-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 α,β\alpha, \beta-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-μ\mu 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 −log⁡P(t∣prefix)-\log P(t \mid \text{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]P \in [0.58, 0.91] after 8 forward passes. We will revise by adding a figure of this example.

The tolerance ϵ\epsilon defines which sequences must be resolved, namely all sequences with probability greater than ϵ\epsilon. Every sound verifier must expand all of these sequences to reach tolerance ϵ\epsilon, and Max-μ\mu expands exactly these sequences, for every ϵ\epsilon (Theorem 4.6). Therefore, no other selection strategy can verify up to tolerance ϵ\epsilon in fewer forward passes. Table 8 confirms this empirically: Sample-μ\mu 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.

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

Reviewer_sMoFOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper presents BEAVER, a framework for computing deterministic, sound probability bounds on whether an LLM’s response to a given prompt satisfies a constraint. BEAVER explores the model’s output distribution with a token trie and a frontier, expanding sequences in decreasing order of probability, and maintains sound lower and upper bounds after every iteration. Unlike runtime guardrails, which the authors argue can be removed in the open-weight setting, BEAVER is positioned as a pre-deployment verification method. Experiments on privacy leakage, insecure code generation, and toxicity across five open-weight models show that, compared with a sound sampling-based verifier, BEAVER certifies up to 7.6× more prompts as risky while using fewer forward passes.

Critical strengths

Broad empirical evaluation showing that sound verification is practical

The experiments cover three safety-relevant tasks (privacy leakage, insecure code generation, and toxicity) and five open-weight models from three families, ranging from 4B to 70B parameters, with 300 prompts per task. Across all settings, BEAVER reaches the same or better categorization than the sampling-based verifier at a lower cost. The number of certified risky prompts increases by 7.6× on toxicity and 1.2× on secure code, and on privacy BEAVER reaches nearly identical categorizations with about 13× fewer forward passes.

Low verification cost, lowering the barrier to adoption

Verifying a single prompt takes about two minutes on secure code and toxicity (and a few seconds on privacy), and all 300 prompts of a task can be verified in under 25 minutes on a single GPU (two for Llama-3.3-70B). This efficiency makes it practical to verify a model repeatedly during development, for example at every new checkpoint, rather than only once before release. As a result, safety verification can be easily integrated into the regular model development process, in the same way that unit tests are run on every code change in software development.

Critical weaknesses

The scope of the guarantees is limited by the predefined constraint Φ

BEAVER’s guarantees hold only with respect to a constraint Φ that must be defined in advance for each task. Behaviors that Φ does not capture, such as unanticipated or unintended harmful behaviors, fall outside the guarantee. In contrast, LLM-based safety judges are trained on large-scale data and can generalize beyond explicitly enumerated patterns, which allows them to judge a broad range of harmful behaviors. With predefined rules, it seems difficult to achieve comparable coverage, especially for unanticipated or unintended harmful behaviors that cannot be predicted in advance. I believe the authors should clarify how diverse the harmful behaviors of models are in real-world workloads, and to what extent predefined constraints can cover them.

Limited role of BEAVER as a deployment safety guarantee

The paper motivates BEAVER as a pre-deployment verifier that is “most needed when the weights are public and no guardrail can be enforced”, arguing that post-deployment guardrails are insufficient because an adversary can simply remove them in the open-weight setting. However, this argument applies equally to BEAVER itself. Users who intend to deploy a model safely can, and typically will, add runtime guardrails, which address safety at the point of use. Conversely, an adversary with access to open weights can go beyond removing guardrails and fine-tune the model to undo its safety training. Since BEAVER’s certificates hold only for the specific weights that were verified, they provide no guarantee once the weights are modified. For these reasons, the role of BEAVER in providing safety guarantees appears limited. I would like the authors to clarify who is expected to use BEAVER and for what purpose, what risks remain uncovered in the situations described above, and how these risks can be mitigated or what complementary measures would be needed.

Questions for authors
  • How can BEAVER handle unexpected harmful behaviors that are difficult for humans to define in advance?
  • How much do the verification results change after the weights are modified, for example by fine-tuning or quantization?
6 comments
AuthorsOpenReview ↗

Response to Reviewer sMoF

We thank the reviewer for their feedback, and for the note that Beaver is cheap enough to run on every checkpoint.

Weakness 1 / Question 1. Predefined Φ\Phi and unexpected harms:

Beaver is task-independent as Φ\Phi can be any deterministic oracle. Current LLM evaluation also relies on oracles, from fixed predicates to LLM judges, to decide whether a response is harmful. Beaver uses the same oracles, and it bounds the probability that a response satisfies them over the output distribution.

Beaver does not compete with LLM judges. An LLM safety judge with greedy decoding is deterministic, so Beaver can use it as Φ\Phi. Our toxicity constraint is already a learned classifier (Detoxify [1]). Beaver then bounds the probability that the model gives a response that the judge flags.

Many properties, such as harmfulness, sycophancy, and deception, have no provably sound and complete oracle. Benchmarks, red-teaming, and LLM judges cover only the harms that they define. Harms that no one can define are outside every evaluation method, not only Beaver. If these oracles are not reliable or useful, widely-used benchmarks such as DecodingTrust [4], HarmBench [5], and JailbreakBench [6] are not reliable or useful either.

Weakness 2. Limited role of Beaver as a deployment safety guarantee

Beaver provides pre-deployment stage guarantees, where a developer has a model and wants to check whether it is fit for deployment. Currently, this decision is made by evaluating the model on benchmarks and through red-teaming, both of which rely on a few sampled responses. Beaver replaces this ad hoc evaluation with tail-risk estimation over the output distribution, using the same oracles. Model developers, of open or closed models, can use it before releasing a checkpoint, and deployers can use it to choose between open-weight models for their use case.

Beaver does not replace runtime guardrails. Guardrails and constrained decoding enforce a constraint at inference time by modifying the output distribution, while Beaver characterizes the intrinsic behavior of the model without modifying it. These are guarantees that are provided in different phases of model deployment and can be used together. For example, if Beaver certifies that a large portion of expected prompts are safe, the deployer can use lighter guardrails during deployment, reducing inference overhead and unnecessary refusals. In contrast, if Beaver certifies relatively more risky prompts, the deployer knows that stronger guardrails are needed.

On fine-tuning attacks, Beaver's certificates hold only for the weights that were verified. However, this is true for most evaluation and defense methods, which focus on a single threat model. For example, tamper-resistant training [2] protects against fine-tuning attacks but gives no protection against jailbreaks on the fine-tuned model. Similarly, benchmarks cannot prevent fine-tuning attacks, but they are used to measure the safety of fine-tuned models[3]. Beaver can be used in the same way, with the added benefit that it captures changes in the output distribution rather than in a few sampled responses. For example:

  1. Before releasing an open-weight model, a developer can run a fine-tuning attack on it and use Beaver to check whether the fine-tuned model is still safe.
  2. While fine-tuning a model, a developer can compute Beaver bounds before and after fine-tuning, and stop the training if the bounds shift towards being less safe.

Our fine-tuning experiment below shows that Beaver detects this shift after a few toxic examples. We will revise the paper by adding the threat model to Section 1.

AuthorsOpenReview ↗

Continued response

Question 2: How much do the verification results change after the weights are modified?

We ran two experiments on Qwen3-4B. Each is compared with a bf16 baseline on the same inference backend. 

Quantization: We apply round-to-nearest weight quantization to all linear layers: 8-bit per channel, and 4-bit with group size 128. 8-bit quantization stays similar, only affecting verdicts of a few instances, but 4-bit quantization changes the verdicts of 118 of the 300 toxicity prompts, increasing the toxicity risky count from 50 to 141. For 44 of the 91 newly risky prompts, the most probable response is still safe, so a greedy evaluation of the quantized model would miss about half of its new risk. On secure code, the risky count changes little (103 to 93).

ModelToxicity R/S/OSecure code R/S/O
bf16 (baseline)50/136/114103/46/151
8-bit50/147/103102/49/149
4-bit141/82/7793/39/168

Harmful fine-tuning: We fine-tune Qwen3-4B with LoRA on Alpaca instructions mixed with toxic RealToxicityPrompts continuations (excluding our evaluation prompts) at 5% mix at learning rate 2e-4. We verify the 300 toxicity prompts at each checkpoint.

Model CheckpointToxic ExamplesR/S/Ofp
Base model050/136/114540
Step 10816/0/284572
Step 2520184/0/116263
Step 5040214/0/86233
Step 10080259/0/41214

Beaver detects the shift after only 8 toxic examples (step 10): it can no longer certify any prompt as safe (136 to 0). After 20 toxic examples the risky count rises from 50 to 184, and it keeps growing with more toxic data. Since Beaver takes 4.2-4.7 s per prompt (Table 7), this check can run on every checkpoint.

Citations

[1] https://github.com/unitaryai/detoxify

[2] Tamirisa, Rishub, et al. "Tamper-resistant safeguards for open-weight llms." International Conference on Learning Representations. Vol. 2025. 2025.

[3] Qi, Xiangyu, et al. "Fine-tuning aligned language models compromises safety, even when users do not intend to!." International Conference on Learning Representations. Vol. 2024. 2024.

[4] Wang, Boxin, et al. "Decodingtrust: A comprehensive assessment of trustworthiness in gpt models." Advances in neural information processing systems 36 (2023): 31232-31339.

[5] Mazeika, Mantas, et al. "Harmbench: A standardized evaluation framework for automated red teaming and robust refusal." International Conference on Machine Learning. PMLR, 2024.

[6] Chao, Patrick, et al. "Jailbreakbench: An open robustness benchmark for jailbreaking large language models." Advances in neural information processing systems 37 (2024): 55005-55029.

Dear Reviewer sMoF,

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

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

This paper proposes BEAVER, a branch-and-bound framework for deterministic verification of LLM output distributions. Given a prompt and a semantic constraint, BEAVER constructs a token trie to explore possible outputs and computes sound probability bounds on constraint satisfaction. The framework employs a maximum-probability-first strategy, which the authors prove minimizes the number of forward passes required to verify all sequences above a given probability tolerance. The approach is evaluated on three safety tasks across five open-weight LLMs. Experimental results show that BEAVER certifies up to more risky prompts than a sampling-based verifier while using fewer forward passes.

Critical strengths
  • The paper proposes a novel formal verification method for LLMs.

  • The paper gives a clear formulation and theoretical guarantees

  • The evaluation covers multiple LLM families and safety tasks, demonstrating improved certification effectiveness and computational efficiency compared with sampling-based verification.

Critical weaknesses
  • My main concern is whether deterministic verification provides real, meaningful guarantees for LLMs (in addition to the given examples in exp.). Unlike traditional neural networks with relatively clear input-output specifications, LLMs generate open-ended responses whose safety and correctness are difficult to define through fixed predicates. It remains unclear how such verification guarantees translate into practical safety assurance for real-world LLM applications.

  • The framework largely follows traditional formal verification techniques, combining predefined specifications, B&B search, and soundness guarantees. For a venue like ICLR, I would expect a stronger justification of why this approach is needed for LLMs and what new insights it brings, rather than simply extending existing verification techniques to a new setting.

  • Although BEAVER improves search efficiency, it still relies on exploring token sequences, making scalability a major concern as the output space grows exponentially with generation length.

Questions for authors
  1. What concrete real-world LLM safety scenarios require deterministic probability bounds rather than statistical or empirical guarantees? How would BEAVER's certificates inform practical deployment decisions?

  2. Why do the authors believe deterministic verification is necessary for generative AI, and what practical advantages does it offer over existing safety evaluation methods, especially given the inherent scalability challenges of exploring the exponentially large output space?

4 comments
AuthorsOpenReview ↗

Response to Reviewer gpa4

We thank the reviewer for their feedback.

Weakness 1: Deterministic verification provides real, meaningful guarantees for LLMs

Traditional NN verification methods provide robustness guarantees on local specifications, which are commonly used to compare models that have similar accuracy, selecting the most robust model to deploy[1]. In LLMs, current evaluation methods use various oracles, ranging from fixed deterministic predicates to LLM judges, to evaluate models on desired properties. For example, GCG [4] counts an attack as successful when the response contains none of a fixed list of refusal phrases. Many properties of current interest, such as harmfulness, sycophancy, and deception, have no provably sound and complete oracles. Still, these imperfect oracles underpin current evaluation, including over 300 LLM safety papers accepted at ICLR, ICML, and NeurIPS in 2025 alone (based on results on OpenReview). If these oracles are not reliable or useful, current benchmarks are not reliable or useful either.

Our goal with Beaver is to bound the probability of a violation over the output distribution of a prompt, instead of estimating it from a few samples. Beaver expands the most probable prefixes across the whole token trie and counts all unexplored probability mass in its bounds. Beaver provides anytime guarantees: it keeps sound bounds at each step. Beaver considers the probability mass that sampling-based evaluation misses, which resurfaces as tail risk in deployed models. Beaver requires only that the oracle is deterministic. An LLM judge with greedy decoding, a BERT-style classifier, and a fixed predicate all satisfy this condition. Our toxicity constraint is already a learned classifier (Detoxify[6]). On secure code and privacy, our constraints are sound and complete.

This matters because a single prompt can have a small but non-negligible probability of a harmful response. Repeatedly sampling the same prompt can elicit undesired behaviors that have a low but non-zero probability, and such behaviors appear during deployment when evaluation misses them [5]. Evaluation that only looks at a few responses per prompt, greedy decoding in particular, misses this mass. In our experiments on Qwen3-4B, the greedy-decoding response is safe for 24 of the 54 risky toxicity prompts and 18 of the 103 secure-code risky prompts, where a risky prompt is one with an upper-bound probability of a safe response < 90%. In the open-source setting, an unsophisticated attacker can easily exploit this by repeated sampling. (See Question 1 for follow-up)

Weakness 2: What is new, and why use formal methods

Traditional NN verification methods [2][3] are designed for classifiers that run one forward pass over an input region. They are not designed to handle the probabilistic autoregressive generation of LLMs, and they cannot reason about the probability distributions over LLM responses. We also tried to apply α,β\alpha, \beta-CROWN directly to Qwen3-4B and to GPT-2, and it did not run on either model.

Beaver is the first framework that gives sound deterministic bounds on the output probability distribution of autoregressive LLMs. As discussed in response to Weakness 1, we use formal methods, as sampling-based evaluation gives no guarantee on the probability mass that it does not sample. Beaver explores the output distribution by repeatedly expanding the most probable unresolved prefix in the token trie. It enumerates all responses with probability greater than tolerance ϵ\epsilon (within the fewest possible forward passes, Theorem 4.6) and bounds the remaining unexplored probability mass to give sound bounds at every step. The resulting bounds play a similar role for LLMs to the one certified robustness plays for classifiers: a sound, model-specific measure that can be used to compare models and decide which one to deploy.

AuthorsOpenReview ↗

Continued response

Question 1: Where deterministic bounds are necessary

Beaver bounds give a direct account of the safe and unsafe probability masses generated by a model for a prompt. For example, on the toxicity task, Beaver certifies 54 of 300 prompts (18%) as risky for Qwen3-4B, i.e., prompts for which Beaver certifies at least 10% of the probability mass is toxic. Sampling can only give an unsound estimate of this probability. On one of the secure-code prompts (continuing a C++ filesystem test, under an adversarial system prompt from our distribution), the six most probable continuations are all safe. But the 40 variants of unsafe unbounded ‘sprintf’ together hold a probability of 0.172, making the prompt risky. Beaver resolves these low-probability violations, certifying that the probability of a violation is at least 17%, so the prompt is risky. We will add this example to the revised version.

ProbContinuationΦsec∗∗∗∗\Phi_sec****
0.077char buf[256]; snprintf(buf, sizeof(buf), "hello/%03d", i);safe
0.063char buffer[256]; snprintf(buffer, sizeof(buffer), "hello/%03d", i);safe
0.035char buf[128]; snprintf(buf, sizeof(buf), "hello/%03d", i);safe
0.032char buf[256]; size = fs.read("hello", buf, sizeof(buf));safe
0.025char buf[256]; size = fs.readdir("hello", buf, sizeof(buf));safe
0.013char buf[128]; snprintf(buf, sizeof(buf), "file_%03d", i);safe
0.011char buf[256]; sprintf(buf, "hello/%03d", i);violates CWE-120
0.161 (total)39 other unbounded sprintf variantsviolate CWE-120

Additionally, please see our response to Weaknesses 1 and 2 above.

Question 2: Why deterministic verification

Please see our response to Weaknesses 1, 2 and 3 above. 

Citations:

[1] Chakravarthy, Arnav, et al. "Property-driven evaluation of rl-controllers in self-driving datacenters." Workshop on Challenges in Deploying and Monitoring Machine Learning Systems (DMML). 2022.

[2] Li, Haoyu, et al. "Bridging Control with Neural Network Verifier alpha-beta-CROWN: A Tutorial." arXiv preprint arXiv:2605.26577 (2026).

[3] 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

[4] Zou, Andy, et al. "Universal and transferable adversarial attacks on aligned language models." arXiv preprint arXiv:2307.15043 (2023).

[5] Jones, Erik, et al. "Forecasting rare language model behaviors." arXiv preprint arXiv:2502.16797 (2025).

[6] https://github.com/unitaryai/detoxify

[7] https://github.com/Verified-Intelligence/alpha-beta-CROWN

[8] Huang, Jie, Hanyin Shao, and Kevin Chen-Chuan Chang. "Are large pre-trained language models leaking your personal information?." Findings of the Association for Computational Linguistics: EMNLP 2022. 2022.

[9] Debenedetti, Edoardo, et al. "Agentdojo: A dynamic environment to evaluate prompt injection attacks and defenses for llm agents." Advances in neural information processing systems 37 (2024): 82895-82920.

[10] Wang, Boxin, et al. "Decodingtrust: A comprehensive assessment of trustworthiness in gpt models." Advances in neural information processing systems 36 (2023): 31232-31339.

[11] Mazeika, Mantas, et al. "Harmbench: A standardized evaluation framework for automated red teaming and robust refusal." International Conference on Machine Learning. PMLR, 2024.

[12] Chao, Patrick, et al. "Jailbreakbench: An open robustness benchmark for jailbreaking large language models." Advances in neural information processing systems 37 (2024): 55005-55029.

[13] Zou, Andy, et al. "Representation engineering: A top-down approach to ai transparency." arXiv preprint arXiv:2310.01405 (2023).

[14] Goldowsky-Dill, Nicholas, et al. "Detecting strategic deception with linear probes." International Conference on Machine Learning. PMLR, 2025.

Dear Reviewer gpa4,

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 gpa4,

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

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Response

We thank all reviewers for their feedback. This response covers the points shared across the reviews, and we answer each reviewer individually below. 

1. Existing evaluations have no guarantees. Benchmarks and red-teaming check a few sampled responses with an oracle, such as a classifier, a regular expression, or an LLM judge, and give no guarantee about the rest of the output distribution. Beaver uses the same oracles, but bounds the probability that a response satisfies the oracle over the output distribution of a prompt. It is the first method that gives deterministic, sound bounds on this quantity.

This matters in practice as evaluation that looks only at the most likely response gives a false sense of security. On Qwen3-4B, the greedy-decoding response is safe for 24 of the 54 risky toxicity prompts and 18 of the 103 secure-code risky prompts, where a risky prompt is one with an upper-bound probability of a safe response < 90%. On one of the secure-code prompts, the six most probable continuations of the prompt are safe even when Beaver certifies that at least 17% of the probability mass violates the constraint, making the LLM response distribution for the prompt risky (even if few likely samples are safe). Please see our response to Reviewer gpa4, Question 1 for more details.

2. Traditional NN verifiers cannot be applied to this problem. Verifiers such as DeepPoly and α,β\alpha,\beta-CROWN [3][4] are designed for a single forward pass of a classifier over an input region. They cannot handle autoregressive generation or reason about the probability distributions over responses. Further, bound propagation scales at most to small transformers[1][2]. We also tried to apply the state-of-the-art verifier α,β\alpha, \beta-CROWN[4] directly to Qwen3-4B and GPT-2, and it did not run on either model. Please see our response to Reviewer gpa4, Weakness 2, for more details.

3. Scalability and output length. The verification difficulty depends on the spread of the output distribution. If the distribution were concentrated on a handful of responses, a few samples would cover the full probability mass, and the verification problem would be easy. If it were spread uniformly over all possible sequences, verification would be exponentially expensive. LLM output distributions lie between these two extremes, making verification challenging but tractable. In our experiments, the tasks set the generation lengths. We also ran toxicity with maximum lengths of 64 and 128 tokens, and in both, the risky count remained unchanged. Please see our response to Reviewer gpa4, Weakness 3.

Note: We 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. Despite the emphasis on rigorous evaluation in the literature (over 300 LLM safety papers accepted at ICLR, ICML and NeurIPS in 2025 alone), no benchmark or sampling procedure provides this guarantee, even though stochasticity has been identified as a major issue [5][6][7]. It matters for open-weight models deployed by parties who did not train them. We see this as a first step that we intend to carry considerably further in scaling deterministic verification of LLMs.

References: 

[1] 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.

[2] Shi, Zhouxing, et al. "Robustness verification for transformers." arXiv preprint arXiv:2002.06622 (2020).

[3] Singh, Gagandeep, et al. "An abstract domain for certifying neural networks." Proceedings of the ACM on Programming Languages 3.POPL (2019): 1-30.

[4] https://github.com/Verified-Intelligence/alpha-beta-CROWN

[5] Scholten, Yan, Stephan Günnemann, and Leo Schwinn. "A probabilistic perspective on unlearning and alignment for large language models." International Conference on Learning Representations. 2025.

[6] Huang, Yangsibo, et al. "Catastrophic jailbreak of open-source LLMs via exploiting generation." International Conference on Learning Representations. 2024.

[7] Jones, Erik, et al. "Forecasting rare language model behaviors." arXiv preprint arXiv:2502.16797 (2025).

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.