STAR-Teaming: A Strategy-Response Multiplex Network Approach to Automated LLM Red Teaming

While prior red-teaming efforts have focused on eliciting harmful text outputs from large language models (LLMs), such approaches fail to capture agent-specific vulnerabilities that emerge through multi-step tool execution, particularly in rapidly growing ecosystems such as the Model Context Protocol (MCP). To address this gap, we propose a trajectory-aware evolutionary search method, T-MAP, which leverages execution trajectories to guide the discovery of adversarial prompts. Our approach enables the automatic generation of attacks that not only bypass safety guardrails but also reliably realize harmful objectives through actual tool interactions. Empirical evaluations across diverse MCP environments demonstrate that T-MAP substantially outperforms baselines in attack realization rate (ARR) and remains effective against frontier models, including GPT-5.2, Gemini-3-Pro, Qwen3.5, and GLM-5, thereby revealing previously underexplored vulnerabilities in autonomous LLM agents. Code is available at https://github.com/pwnhyo/T-MAP.

Red-teaming is becoming a central part of large language model (LLM) safety evaluation, yet current practice still relies heavily on expert-written prompts or fixed benchmark suites. This creates a gap between what is easy to test and what deployed models can actually do: failures may be rare, context-sensitive, and distributed across many threat categories. We study automated red-teaming as a constrained adversarial search problem and introduce a learning-driven framework that couples category-aware attack generation with hierarchical vulnerability detection. The method starts from curated safety seeds, expands them through meta-prompt-guided and evolutionary search, and scores the resulting prompt--response pairs with lexical, semantic, and behavioral detectors. Across six threat categories on GPT-OSS-20B, the framework discovers 47 validated vulnerabilities, including 21 high-severity cases and 12 novel attack patterns. Under matched query budgets, it achieves a 3.9$\times$ higher discovery rate than manual expert red-teaming while maintaining 89% detection accuracy and full category coverage. Ablations show that the gains do not come from more prompts alone: diversity constraints prevent template collapse, coverage constraints prevent category blind spots, and semantic detection recovers failures missed by lexical rules. These results suggest that red-teaming can be made more scalable and reproducible when treated as adaptive search rather than as a static checklist.

Many approaches to LLM red-teaming leverage an attacker LLM to discover jailbreaks against a target. Several of them task the attacker with identifying effective strategies through trial and error, resulting in a semantically limited range of successes. Another approach discovers diverse attacks by combining crowdsourced harmful queries and tactics into instructions for the attacker, but does so at random, limiting effectiveness. This article introduces a novel framework, Adaptive Instruction Composition, that combines crowdsourced texts according to an adaptive mechanism trained to jointly optimize effectiveness with diversity. We use reinforcement learning to balance exploration with exploitation in a combinatorial space of instructions to guide the attacker toward diverse generations tailored to target vulnerabilities. We demonstrate that our approach substantially outperforms random combination on a set of effectiveness and diversity metrics, even under model transfer. Further, we show that it surpasses a host of recent adaptive approaches on Harmbench. We employ a lightweight neural contextual bandit that adapts to contrastive embedding inputs, and provide ablations suggesting that the contrastive pretraining enables the network to rapidly generalize and scale to the massive space as it learns.