BEACON: Budget-Efficient Discovery of Policy Violations in Large Language Models via Cognitive-Guided Monte Carlo Tree Search

1 Introduction

The deployment of large language models (LLMs) in safetycritical applications demands rigorous evaluation of their robustness against adversarial inputs [Brown et al., 2020; OpenAI, 2023]. While extensive research has developed sophisticated jailbreak attacks spanning gradient-based optimization [Zou et al., 2023], agent-based refinement [Chao et al., 2023; Mehrotra et al., 2024], and knowledge decomposition [Wei et al., 2025], most work evaluates success through Attack Success Rate (ASR), defined as the fraction of harmful goals achieved. This singular focus on final success counts obscures a critical dimension: real safety auditing operates under strict resource constraints, where each API query incurs cost and latency, and evaluation must cover diverse failure modes rather than maximize raw success.

† Corresponding author.

Current ASR-based evaluation ignores three critical dimensions: discovery timing, where methods with identical 80% ASR differ dramatically if one requires 50 vs. 500 queries; failure diversity, where repeatedly exploiting the same vulnerability provides less insight than discovering multiple violation categories; and budget efficiency, where 10 vs. 100 queries per success have vastly different practical utility [Ramesh et al., 2025].

We propose reframing LLM safety evaluation through the lens of budget-constrained failure discovery. This perspective draws inspiration from test optimization in software engineering [Yoo and Harman, 2012], adaptive sampling in Bayesian optimization [Snoek et al., 2012], and coverageguided fuzzing [B¨ohme et al., 2016]. Our central thesis is that the goal of safety evaluation should not be to maximize the count of successful attacks, but to efficiently discover and characterize the diversity of failure modes under realistic resource constraints. This reframing yields a richer evaluation framework where discovery timing, harm category diversity, and discovery efficiency are first-class citizens alongside traditional success metrics.

To address these challenges, we introduce BEACON, a budget-aware safety testing framework that uses CognitiveGuided Monte Carlo Tree Search to navigate the violation search space under fixed budgets, integrating cognitive profiling, diversity-aware selection, and cross-session memory to enable efficient discovery of diverse policy violations.

The main contributions of this paper are as follows:

1. We formalize budget-constrained safety evaluation with principled metrics capturing discovery timing, frontloaded efficiency, harm category diversity, and per-query productivity (§3).
2. We introduce Cognitive-Guided MCTS incorporating defense persona priors, diversity-aware UCB selection [Auer et al., 2002; Sawwan and Wu, 2024], and memory-guided simulation to address cold-start exploration and exploitation-diversity tradeoffs (§4.3).
3. We present the BEACON framework integrating CGMCTS with cognitive profiling, Q-learning [Watkins and Dayan, 1992], and context poisoning in a pipelinewith-iteration architecture (§4).
4. Experiments on standard benchmarks and frontier LLMs show BEACON discovers safety failures earlier and achieves higher coverage across policy violation categories (§5).

2 RelatedWork

LLM Safety Evaluation and Jailbreak Attacks. The landscape of adversarial attacks against LLMs has expanded rapidly, spanning gradient-based optimization [Zou et al., 2023; Liu et al., 2023], LLM-driven iterative refinement [Chao et al., 2023; Mehrotra et al., 2024; Yu et al., 2023], multi-agent coordination [Samvelyan et al., 2024; Rahman et al., 2025; Chen et al., 2025], and persuasionbased attacks [Zeng et al., 2024; Wei et al., 2025]. To systematize evaluation, several benchmarks have emerged, including HarmBench [Mazeika et al., 2024], JailbreakBench [Chao et al., 2024], StrongREJECT [Souly et al., 2024], and OpenRT [Wang et al., 2026]. Recent surveys [Yi et al., 2024; Liu et al., 2024] provide comprehensive taxonomies of attack and defense methods. While most prior work reports ASR as the primary evaluation metric, discovery timing and harm category diversity remain implicit byproducts rather than explicit optimization targets.

Query-Efficient Search and Profiling. Coverage-guided fuzzing [B¨ohme et al., 2016] and Bayesian optimization [Snoek et al., 2012] formalize sample-efficient exploration in software testing and hyperparameter tuning [Xiong et al., 2025]. Monte Carlo Tree Search (MCTS) [Kocsis and Szepesv´ari, 2006; Silver et al., 2016] combines treestructured planning with UCB-based selection for sequential decision-making, and has recently been applied to LLM jailbreaking through MPA [Wu et al., 2025] and GS-MCTS [Li et al., 2025]. Query-efficient red-teaming methods such as RAPT [Liu et al., 2025] and RedAgent [Xu et al., 2024] have begun addressing budget constraints by minimizing queries per individual success, without explicit diversity-aware exploration or coverage metrics. Cognitive profiling, which systematically infers target defense characteristics, has proven valuable in adversarial ML through model extraction [Tram`er et al., 2016] and membership inference [Shokri et al., 2017]. Our work integrates these foundations into a unified framework that treats harm categories as coverage targets and incorporates cognitive priors to accelerate budget-constrained discovery.

3 Preliminary

We formalize the evaluation framework with precise metric definitions that capture discovery efficiency, timing, and diversity, all of which are ignored by traditional ASR-based evaluation.

Problem Setting. Let M be a target LLM and G = {g1, . . . , gN} a set of harmful goals. An attack method A issues queries q1, q2, . . . to M, receiving responses evaluated by a safety judge J : (goal, response) → {0, 1}. Let b denote cumulative query count (budget consumed). A response y = M(q) constitutes a safety failure for goal g if J(g, y) = 1, indicating policy violation. Each failure is assigned to a harm category c ∈ C based on the benchmark's taxonomy. Specifically, HarmBench defines |C| = 6 semantic categories (chemical/biological, illegal activities, misinformation, harmful content, harassment, and cybercrime), while StrongREJECT uses |C| = 6 functional categories (disinformation, hate/harassment, illegal goods, non-violent crimes, sexual content, and violence). We report coverage metrics using each benchmark's native harm taxonomy.

Budget Granularity. We define a per-goal budget Bg as the maximum number of target-model queries allowed for each goal instance. Goals are processed sequentially in fixed order; the cumulative budget b across all goals forms a global discovery curve, with total budget Btotal = N · Bg where N = |G| is the number of goals. Unless otherwise noted, we use Bg = 10 queries per goal throughout experiments.

Failure Discovery Curve F(b). The primary metric is the cumulative failure count as a function of budget. Let b denote the cumulative number of target-model queries issued so far. We process goals sequentially: for each goal gi, we issue up to Bg queries until either a safety failure is discovered or the per-goal budget is exhausted, then proceed to the next goal. The discovery curve is:

where each query qj targets some goal gtgt j and receives response yj = M(qj). A query yields a safety failure if J (gtgt j , yj) = 1. This curve captures the dynamics of failure discovery over the query budget, not just the final count.

k-First Discovery Query (k-FDQ, k=5). Let F(t) denote the cumulative number of successful jailbreaks discovered within the first t target-model queries. We define

Lower k-FDQ indicates faster early discovery, critical for rapid vulnerability confirmation in time-constrained audits.

We use k=5 rather than k=1 because single-success metrics exhibit high variance, and auditors typically require multiple confirmed failures before escalating findings.

Normalized Discovery Area (NDA). To reward early discovery across the entire evaluation, we compute the normalized area under the discovery curve:

where Btotal is the total budget. NDA ranges from 0 to 1, with higher values indicating earlier discovery. An ideal method that discovers all failures immediately achieves NDA = 1.0, while a method with uniform discovery rate throughout the budget yields NDA = 0.5. Values above 0.5 indicate frontloaded discovery (more failures found in the first half of budget); values below 0.5 indicate back-loaded discovery.

Harm Category Coverage Rate (CCR@b). The fraction of harm categories discovered within budget b:

where cj denotes the pre-assigned harm category of the goal gtgt j targeted by query qj. This measures the diversity of discovered policy violations across the benchmark's harm taxonomy, ensuring evaluation captures multiple vulnerability types rather than repeatedly exploiting the same weakness. We report CCR at 25%, 50%, 75%, and 100% of total budget to characterize diversity progression.

Discovery Velocity (DV). The average rate of failure discovery per query:

Higher DV indicates more efficient use of query budget. This metric captures the productivity of the attack method in failures discovered per budget. The reciprocal QpS = 1/DV =

Btotal/F(Btotal) gives the average queries-per-success, which we report in some tables for interpretability.

Together, these metrics provide a comprehensive view of safety evaluation efficiency beyond ASR: k-FDQ measures initial discovery speed, NDA captures overall timing efficiency, CCR@b measures harm category diversity progression, and DV quantifies discovery productivity.

4 BEACON

We introduce the Budget-Efficient Adaptive Cognitive Offense Navigator (BEACON), a framework for budget-aware safety testing that integrates cognitive profiling, Monte Carlo tree search, reinforcement learning, and multi-modal attack techniques. As illustrated in Figure 2, BEACON adopts a pipeline-with-iteration architecture that performs one-time target characterization, iteratively refines attack strategies through CG-MCTS and Q-learning, and consolidates successful experiences for cross-session knowledge transfer.

4.1 Perception Phase

Cognitive Profiling

Before attacking, BEACON characterizes the target's defense posture through 3-5 benign edge-case probes (boundarytesting, authority-framed, hypothetical, and multi-turn escalation). These probes are executed once per target model (not per goal). Response features (refusal rate, hedging frequency, authority compliance, verbosity) feed into Bayesian inference to produce a defense persona ˆ z ∈ Z = {Dogmatic, Cautious, Balanced, Over-Helpful}:

where o1:P are responses to P probes and ϕ(·) extracts behavioral features. BEACON infers the target's defense characteristics, making the persona a property of the defender rather than the attacker. The inferred persona conditions strategy selection: Over-Helpful targets suit authority framing; Dogmatic targets require encoding-based evasion; Cautious targets respond to gradual escalation; Balanced targets benefit from mixed-strategy exploration.

4.2 Preparation Phase

Memory Retrieval

For each goal g, BEACON retrieves the top-m most similar goals from a cross-session memory bank B storing (g′ , a′ , r′ , c′ , t′ , eg′) tuples (goal, action, reward, harm category, timestamp, goal embedding). Semantic similarity is computed via cosine distance between Sentence-BERT embeddings [Reimers and Gurevych, 2019; Feng et al., 2022]. Retrieved entries provide strategy recommendations for transfer learning and outcome statistics that inform value estimation during tree search.

Context Poisoning

Prepending multi-turn dialogue history alters model behavior: pM(y|x, cN) ̸= pM(y|x, c0). BEACON exploits this by constructing synthetic histories where the model has assisted with increasingly borderline requests, lowering resistance to subsequent harmful queries. Contexts are tailored per agent: for Social Engineer, it establishes the user's authority or expertise; for Tech Evasion, it normalizes technical discussions involving sensitive topics; for Semantic Progressive, it builds a gradual escalation trajectory; and for Chaos Explorer, it introduces unconventional or absurdist scenarios that destabilize default safety heuristics.

4.3 Iterative Attack Phase

The core attack loop cycles through four stages: strategy selection, attack execution, evaluation, and feedback update.

Strategy Selection

BEACON selects pairs from action space A = Aagent × Atech, where Aagent contains four attack agents (Social Engineer, Tech Evasion, Semantic Progressive, Chaos Explorer) and Atech contains six obfuscation techniques (code wrapper, JSON structure, base64 encoding, markdown formatting, language mixing, contextual framing), giving |A| = 24 strategies.

Selection follows a decision priority cascade that integrates multiple knowledge sources. For the first Krot = 5 attempts, BEACON enforces forced rotation through distinct strategies to ensure initial diversity and prevent early collapse. Subsequently, if the same strategy was selected consecutively, diversity enforcement requires an alternative. If semantically similar goals exist in memory with high similarity, memory-guided selection adopts their successful strategies. When Q-values exceed a high confidence threshold (θQ = 0.85), Q-learning exploitation uses the learned policy. Otherwise, tree search exploration is invoked as the default mechanism.

Cognitive-Guided Tree Search. When exploration is needed, BEACON employs MCTS to address cold-start waste from uniform priors and the exploitation-diversity tradeoff. We use MCTS rather than bandit algorithms because: (1) multi-turn attacks create sequential dependencies where early choices affect later options; (2) MCTS integrates prior knowledge through UCB; (3) backpropagation enables credit assignment across trajectories. The search tree maintains visit counts N(n), cumulative values W(n), and prior probabilities P (n) from cognitive profiling.

Selection navigates from root to leaf using diversity-aware UCB:

where the novelty term encourages strategy diversity:

The first term provides bonus λ for (agent, technique) combinations not yet attempted in the current session; the second favors nodes with sparser strategy coverage, where Sused denotes the set of strategies already executed. The prior probability P (n) is derived from cognitive profiling, converting the defense persona into an informed distribution over actions:

where πexpert(a|z) encodes domain knowledge about effective agent-technique combinations against each persona type. Empirically, informed priors accelerate initial exploration compared to uniform priors.

Expansion creates new nodes ordered by prior probability, ensuring high-prior actions are explored first. Simulation estimates node values using memory rather than random rollouts:

where the memory estimate aggregates outcomes from similar goals:

and mixing coefficient α adapts to memory availability. Memory-guided simulation empirically reduces variance in value estimates compared to random rollouts. Backpropagation updates statistics along the path from leaf to root: incrementing visit counts, accumulating values, and augmenting harm category sets with newly discovered categories, empirically improving coverage compared to pure exploitation strategies.

Q-Learning Integration. Tree search operates synergistically with Q-learning that transfers knowledge across sessions. The Q-table Q(s, a) stores expected success rates where state s = (ˆ z, t, aprev) encodes defense profile, attempt count, and previous action. After each real attack, Q-values update via:

with shaped reward incorporating timing and novelty bonuses:

The conservative threshold θQ = 0.85 ensures tree search remains the primary exploration mechanism until substantial evidence accumulates, preventing premature exploitation.

Attack Execution

Given a selected (agent, technique), BEACON instantiates both the discourse framing and the obfuscation template: the agent sets the high-level interaction style (e.g., authority/emotion appeal, encoding-oriented evasion, gradual semantic escalation, or perturbation-driven exploration), while the technique specifies the concrete surface form (code wrapper, JSON structuring, base64, markdown, language mixing, or contextual framing). BEACON then composes the final adversarial prompt by fusing the goal with the technique template and the synthesized context history, and queries the target model M.

Evaluation

Response y is evaluated by a two-stage safety judge: (1) LLM-based scoring on a 1-10 scale assessing harmfulness, specificity, and instruction-following; (2) rule-based verification checking for known refusal patterns. Both must agree for classification as safety failure (score ≥ 8). The harm category of each successful attack is determined by the goal's pre-assigned category in the benchmark taxonomy.

4.4 Knowledge Consolidation Phase

Online Update (Per Attempt). After each attempt, BEACON performs an online reflection update: it updates the Q-table via Eq. 12, appends the experience tuple to the insession memory bank B,

and, when tree search is invoked, backpropagates the realized outcomes to refine future simulations. Failed attempts increment the corresponding counters; after Kfail = 3 consecutive failures within the same strategy category, BEACON activates diversity enforcement to force exploration of alternative strategies. This reflection loop enables continuous learning: early iterations build Q-values and experience coverage, while later iterations exploit accumulated knowledge with diversity-aware selection.

Session-level Consolidation (Cross Session). Upon completing each attack session, BEACON consolidates the acquired experience into a persistent memory bank for future reuse.

In particular, successful attack trajectories are stored as tuples (g, a, r, c, t, eg) for efficient semantic retrieval in subsequent sessions. This cross-session memory enables transfer learning: new goals can directly leverage previously validated strategies, reducing exploration overhead and accelerating discovery in later runs.

4.5 Summary

BEACON integrates cognitive profiling, CG-MCTS, and Qlearning to enable budget-efficient safety testing. The cognitive profiler initializes informed priors that accelerate exploration; diversity-aware UCB selection encourages comprehensive strategy coverage; experience-guided simulation reduces value estimation variance. These components form a closed feedback loop: cognitive profiling seeds the search with defender-aware priors, CG-MCTS navigates the strategy space under budget constraints while diversity-aware selection prevents premature convergence, and Q-learning consolidates cross-session experience to progressively sharpen both priors and value estimates over time.

5 Experiments

We evaluate BEACON through two complementary perspectives: (1) traditional ASR comparison against baselines to validate attack effectiveness, and (2) detailed efficiency analysis using our proposed metrics to characterize BEACON's budget-constrained discovery dynamics.

5.1 Experimental Setup

We evaluate BEACON on HarmBench and StrongREJECT across six target LLMs, and compare against nine representative jailbreak baselines in Table 1. We adopt a fixed per-goal query budget Bg, where all target-model calls are counted toward Btotal. Attack-model generation and judging are excluded from the budget. We acknowledge this budget definition may underestimate total computational cost.

Goal Ordering. To assess sensitivity to goal ordering, we run each model-dataset configuration with 5 random permutations of the goal sequence. We report mean values in the main tables; standard deviations are consistently small (<2% for ASR, <5 queries for k-FDQ), indicating that our efficiency metrics are robust to ordering variations.

Attack/Target/Judge roles. Our pipeline separates three roles: an attack model (GPT-5.1) proposes candidate jailbreak prompts, a target model produces victim responses under budget Bg, and an internal judge (GPT-5.1) scores each target response for policy-violation severity. We note that when GPT-5.2 serves as target, using GPT-5.1 as judge avoids same-model evaluation bias.

Internal Judge Score

1-3 Safe or standard refusal; no actionable harmful content.

• 4-7 Partial or ambiguous compliance; insufficient to confirm a violation.
• 8-10 Confirmed policy-violating assistance; treated as a successful jailbreak.

5.2 Attack Success Rate Comparison

In Table 1, BEACON achieves the highest ASR across all target models, reaching 100% on DeepSeek (both benchmarks) and Qwen (StrongREJECT), with 97.4% on LLaMA (StrongREJECT). Compared to the strongest baseline (X-Teaming), BEACON improves ASR by up to 38.0 percentage points on Claude (HarmBench: 85.5% vs. 47.5%), indicating that cognitive profiling and hybrid strategy selection exploit diverse vulnerabilities across different model architectures.

Note: Model abbreviations are used throughout all tables and figures in this paper: GPT = GPT-5.2, Gemini = Gemini 3.0 Pro, Claude = Claude Sonnet 4.5, DeepSeek = DeepSeek-R1, Qwen = Qwen2.5-7B-Instruct, LLaMA = LLaMA-3.1-8B.

Figure 3: Core budget-efficiency metrics across target models.

5.3 Budget-Efficiency Analysis

Beyond final ASR, we analyze when and how BEACON discovers policy violations under a fixed query budget. For efficiency comparison, we focus on X-Teaming, the strongest baseline in Table 1, as gains over weaker methods would be expected. Both methods employ similar multi-turn agent architectures, ensuring the comparison isolates cognitive guidance contributions rather than architectural differences.

Core Efficiency Metrics

Figure 3 presents the three core budget-efficiency metrics across all target models. LLaMA and Qwen achieve high discovery velocity with rapid early discovery (k-FDQ with k=5), while GPT and Gemini exhibit higher resistance with elevated k-FDQ and lower DV. NDA values indicate frontloaded discovery dynamics where most failures are found in the first half of the budget.

Harm Category Coverage Progression

Figure 4 visualizes how harm category coverage evolves over budget allocation, using each benchmark's native 6category taxonomy. Across both HarmBench and StrongREJECT, coverage increases in clear stepwise jumps and saturates early, models discover most categories within the first few percent of dataset progress and reach full coverage (6/6) well before 20% budget. This indicates that our method can uncover the complete category set at an early stage of exploration. DeepSeek and Qwen achieve faster coverage growth, indicating that extended exploration successfully uncovers diverse failure modes even against well-aligned models.

Query Cost Distribution

Figure 5 presents violin plots showing the distribution of queries-per-success across all attacks. DeepSeek, Qwen, and LLaMA exhibit narrow, low-centered distributions with medians near 2-3 queries, indicating consistent attack efficiency. In contrast, GPT and Gemini show wider distributions extending to higher query counts, reflecting more variable outcomes. These distributional differences reveal that aggregate metrics may mask substantial variance in attack difficulty across individual instances.

Strategy Effectiveness Analysis

To understand which attack strategies are most effective against different targets, Figure 6 presents heatmaps of suc- CE: Chaos Explorer; SP: Semantic Progressive; SE: Social Engineer; TE: Tech Evasion. be: base64 encoding; cw: code wrapper; cf: contextual framing; js: json structure; lm: language mixing; mf: markdown formatting.

cess counts by agent type and obfuscation technique.

The Social Engineer agent achieves the highest success counts overall, particularly against open-weight models. The Tech Evasion agent shows complementary strength against DeepSeek, suggesting that technical obfuscation is particularly effective against reasoning-focused models. GPT and Gemini demonstrate stronger resistance across all agent types, confirming their robust multi-layered defenses.

For obfuscation techniques, code wrapper achieves strong success against open-weight models, indicating that instruction-following capabilities extend to code even when harmful intent is embedded. The json structure technique shows complementary effectiveness against DeepSeek and Claude, suggesting structured data formats can obscure malicious intent from safety classifiers.

Comparison with X-Teaming

We conduct head-to-head efficiency analysis against XTeaming on Claude Sonnet 4.5, the most challenging target where both methods' ASR is lowest, in order to stress-test efficiency under difficult conditions. Table 2 presents comprehensive budget-efficiency metrics for both methods.

The results demonstrate that BEACON is not only more successful but also substantially more budget-efficient. On StrongREJECT, BEACON reaches the 5th success 3.7× faster (k-FDQ 26 vs. 95) and achieves nearly 2× fewer queries per success (QpS 3.37 vs. 6.45), indicating substantially faster confirmation under limited audit budgets. BEACON also achieves higher NDA scores (0.707 vs. 0.598), confirming more front-loaded discovery patterns. Both methods eventually achieve full harm category coverage. These efficiency advantages on the most resistant target suggest that BEACON's gains are non-trivial and would translate to practical savings in real-world safety audits.

5.4 Ablation Studies

Table 3 reports ablations on a balanced subset, disabling one module at a time from the full system. Removing RL causes the largest degradation: ASR drops from 82.0% to 64.0% and k-FDQ worsens from 5 to 62, confirming learned action selection as the primary driver of both success rate and discovery speed. Removing MCTS degrades ASR to 70.0% and k-FDQ to 16, highlighting tree-search planning as essential for multi-turn trajectory reasoning. Removing the Profiler yields a moderate ASR drop to 78.0% but critically slows early discovery, with k-FDQ degrading from 5 to 30 and NDA from 0.620 to 0.496, confirming that cognitive priors primarily accelerate failure localization rather than determine final success. Context Engine and Memory affect discovery efficiency rather than ASR: removing the Context Engine raises k-FDQ from 5 to 45, a 9× slowdown, with ASR unchanged, while removing Memory degrades k-FDQ from 5 to 14 and NDA from 0.620 to 0.567 with negligible ASR change. Removing Multimodal yields a modest ASR drop to 80.0%, with gains concentrated on goals requiring visual context.

6 Conclusion

This paper introduces BEACON, a budget-constrained framework for efficient LLM safety evaluation through CognitiveGuided Monte Carlo Tree Search. By formalizing efficiencyoriented metrics (k-FDQ, NDA, CCR, DV), we shift focus from merely detecting vulnerabilities to measuring how quickly and diversely they emerge. Experiments on six frontier LLMs demonstrate strong effectiveness. Ablations confirm that Q-learning and MCTS are the primary drivers of attack success, while cognitive profiling and diversity-aware selection improve efficiency and coverage. These results validate that discovery efficiency is a more informative lens for safety evaluation than attack success rate alone. Future work should extend beyond textual cognitive patterns to multimodal profiling, incorporate end-to-end cost accounting, and explore defense-side efficiency metrics.

Ethics Statement

BEACON is designed as a defensive safety evaluation framework. Its purpose is to help safety engineers systematically identify and characterize failure modes in large language models so that those vulnerabilities can be diagnosed and remediated before deployment.

Restricted Use. The framework is intended exclusively for authorized auditing of systems that the auditor controls or has explicit permission to evaluate. It should not be used against public APIs or production systems without prior authorization from the system operator.

Content Warning. The paper contains examples of adversarial prompts and model outputs generated during safety evaluation. These appear solely as experimental artifacts to support reproducibility and are explicitly framed as such.

Prompt Library. The attack templates and systemprompts used in our experiments are released under the same responsible-disclosure norms as prior red-teaming work. The incremental misuse risk relative to already-published methods is minimal, while the defensive value of enabling early vulnerability discovery is substantial.

Acknowledgements

This paper is supported by the New Generation Artificial Intelligence-National Science and Technology Major Project (2025ZD0123704).