acceptodds
Under review as a conference paper at ICLR 2027

TREEval: Allocating Compute for Efficient LLM Safety Evaluation

Abstract

Safety evaluation of large language models often relies on repeatedly generating and judging complete responses, making thorough evaluation computationally expensive. We introduce TREEval, a framework that formulates safety evaluation as a compute-allocation problem over response probability mass, reusing alternative continuations exposed during generation instead of repeatedly generating isolated full rollouts. A simple instantiation, TREEval-DFS, achieves over 98% correlation with repeated-sampling safety measurements with an average estimated compute gain of 69x. We find that this efficiency is enabled by broader response-space coverage and by noisy but informative partial-response judgments that preserve much of the model-level safety signal. We further characterize the tradeoff between allocating compute within versus across prompts: greater inter-prompt exploration exposes more harmful behavior, and these differences show similar trends to standard measures of response diversity.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
LLM Safety, Jailbreak

Reviews

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

TREEval formulates safety evaluation as a problem of allocating compute among prompt perturbation, response-tree expansion, node judging, and early stopping. It retains alternative next-token continuations exposed during model inference, associates them with path probabilities, and aggregates safety judgments over the probability mass they represent. By performing evaluation concurrently with generation, TREEval achieves substantial estimated compute savings while maintaining high correlation with sampling-based safety measures.

Critical strengths

S1: Effective exploitation of exposed alternative continuations.

The key insight—that alternative next-token continuations already exposed during model inference carry valuable safety information—is both intuitive and underexplored. By associating these continuations with path probabilities and aggregating safety judgments over the represented probability mass, TREEval extracts additional signal without incurring extra generation cost.

S2: Comprehensive ablations supporting the core claim.

The traversal ablations (BFS, DFS, random exploration) credibly demonstrate that the gains stem primarily from covering more of the response space rather than from a specific traversal policy, strengthening the generality of the approach and clarifying the source of its advantage.

S3: Clear presentation and honest scoping.

The algorithm is well-described and easy to follow. The authors explicitly acknowledge key limitations and the restrictions of the compute accounting under MoE and API settings, which reflects methodological transparency.

Critical weaknesses

W1: Partial-prefix coverage does not establish a reliable harmfulness estimand.

Assigning a binary judgment to a short prefix effectively labels its entire continuation region without verifying the distribution of final outcomes within that region. Moreover, thirty tokens need not constitute a complete safety-relevant response, raising concerns about whether prefix-level labels faithfully reflect the harmfulness of the full generation.

W2: Probability weighting shifts the target of the sampled baseline.

Tree-region probability weighting can be well-motivated in principle, yet applying an additional round of probability weighting to trajectories that have already been sampled is problematic. Specifically, if complete responses are drawn independently from P(y) and then re-weighted by P(y), the normalized average converges to a P(y)²-weighted quantity rather than the standard per-response harmfulness under P(y). This discrepancy calls into question whether the reported agreement truly reflects fidelity to the intended estimand.

Questions for authors

The current evaluation relies on judgments made at depth 30 rather than on independent assessments of complete responses. In practice, safety-related outputs frequently exhibit a "refuse-then-comply" pattern, where the model initially refuses but subsequently provides harmful content. Given this phenomenon, prefix-level judgments at a fixed depth may miss critical safety violations that emerge later in the generation. I would be interested to see experimental results comparing TREEval's estimates against ground-truth labels obtained from full, independently evaluated responses.

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

This paper presents TREEval, a framework for compute-efficient LLM safety evaluation. Standard Harm@K evaluation requires K complete rollouts, which can be expensive. TREEval instead estimates harmfulness using partial responses, aiming to preserve the safety signal of Harm@K without requiring complete rollouts.

The specific implementation uses the TREEval-DFS algorithm. For a given prompt X, TREEval-DFS follows the highest-probability response while retaining a few high-probability alternative tokens at each position. These alternative, unexpanded paths are also evaluated with a safety judge. For example, suppose the highest-probability response is "A quick brown fox":

Token position1234
GreedyAquickbrownfox
AlternativesTheslow, bigblack, movementbear, dog, mouse

In this example, the following strings are evaluated:

[The, A slow, A big, A quick black, A quick movement, A quick brown bear, A quick brown dog, A quick brown mouse, A quick brown fox]

The harmfulness judgments are aggregated using a probability-weighted average, where each string is weighted by its cumulative token probability. This produces TREEval's harmfulness estimate for prompt X. In practice, the authors skip continuations shorter than 7 tokens.

Across 10 instruction-tuned models, TREEval-DFS achieves a Pearson correlation of 0.9828 with Best-of-N harmfulness measurements at an average estimated 69.4× lower compute cost.

Critical strengths
  1. Useful empirical analysis of partial-response judging. The authors investigate how safety judgments change with response depth and show that partial responses can preserve meaningful safety information even before generation is complete.

  2. Explores the tradeoff between in-prompt and inter-prompt evaluation. The authors find that allocating more compute across semantically related prompt perturbations generally exposes more harmful behavior than exploring individual response trees more deeply.

Critical weaknesses
  1. Pearson correlation overstates the usefulness of TREEval. Safety evaluation metrics are often used to compare models, but TREEval-DFS does not consistently preserve model rankings. Despite a Pearson correlation of 0.9828 with Harm@K, the metrics rank the 10 models in Table 1 differently. Furthermore, when comparing all 45 possible pairs of the 10 models, TREEval-DFS identifies a different model as safer in 5 comparisons.

  2. TREEval is poorly calibrated against Harm@K. TREEval's harmfulness estimates are consistently higher than Harm@K, ranging from 1.39× to 4.23× the corresponding Harm@K scores in Table 1.

  3. Missing important baselines in Table 2, such as best-first search and Distinct Leaf Enumeration [1].

  4. The practical usefulness of many-rollout safety evaluation itself is unclear. Even Harm@1 achieves a relatively high Pearson correlation (0.896) with Average Attack Success@100, raising questions about the incremental value of more elaborate evaluation methods.

  5. Requires access to token-level probabilities, which are unavailable through most closed-source model APIs. This limits TREEval's utility for researchers outside organizations that train or host their own models.

[1] Xueyan Li et al. (2026). Efficient Test-Time Inference via Deterministic Exploration of Truncated Decoding Trees. arXiv:2604.20500.

Questions for authors

Please see the weaknesses section. Also, could you please check whether my interpretation of the algorithm and the example in the summary are correct?

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

This paper proposes TREEval, which treats generation as a probability-weighted token-level response tree instead of naively generating N rollouts (capped at 30 tokens) and evaluating each. The authors provide a TREEval-DFS instantiation, which achieves high correlation with repeated-sampling safety measurements, while requiring significantly less compute. The authors also conduct ablations to attribute the efficiency and study allocation of compute.

Critical strengths
  • Significant reduction in compute compared to standard BoN sampling with full sequence length.
  • The ranking agreement is strong with high correlation.
  • Clean general framing and writing. The ablation also provides useful knowledge.
Critical weaknesses
  • The main paper discusses only one kind of perturbation (character-level noise from BoN Jailbreak) and evaluate using only one dataset. To show generalization, more methods/ datasets should be included.
  • The perturbation is free here, but would the results change if the perturbation is more distinct from the tested setup/ more costly? Eg. Perturbation can also take up compute, especially when using LLM-based attacks like PAIR. It is unclear whether the method is generalizable to more perturbation settings. This can also affect the general recommendation for compute budget allocation.
  • Parameter ratio is a very rough estimate. Using some more standard compute estimate with raw counts would be more accurate. Eg. report tokens processed/ count of judge calls and forward passes, FLOPs estimate based on active parameters, or measured GPU time. Does the compute reduction ratio change if this metric is adjusted?
  • Lack of statistical significance. The sample size is often small in the experiments, but there is no confidence intervals or multi-seed runs for the main result numbers
  • This method relies on previous work suggesting that first few tokens of the response reveal safety behavior already. However, it is possible that models “revert” their responses later in the sequence by recognizing that they should comply/ deny instead. The conclusion would likely also be different if the model first performs reasoning/ thinking.
Questions for authors
  • Does the judge cost account for how many tokens each call reads? Is there a formula for the judge cost computation?
  • In Figure 5, we see a consistent flip rate as response depth increases by every single token. How much is judge noise versus the model actually changing its answer?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.