🤖 AI

Certified Multi-Turn Robustness for LLM Safety via Compositional Bounds and Safety Persistence

This paper introduces Multi-Turn Certified Robustness (MTCR), a novel framework that leverages State-Adversarial MDPs and compositional bounds to provide tighter, theoretically grounded safety guarantees for large language models against multi-turn jailbreak attacks, overcoming the exponential degradation of existing single-turn certification methods.

Original authors: Yang Liu, Bin Chong, Wenkai Yang, Shuai Zhang, Yancheng Chen, Feiyu Han, GuoZhen, Cheng Zhang, Huaibing Xie, Changze Lv, Shihan Dou, Pluto Zhou

Published 2026-08-24

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yang Liu, Bin Chong, Wenkai Yang, Shuai Zhang, Yancheng Chen, Feiyu Han, GuoZhen, Cheng Zhang, Huaibing Xie, Changze Lv, Shihan Dou, Pluto Zhou

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the rapidly evolving world of artificial intelligence, large language models have become the engines behind a new generation of conversational technology. These systems can write stories, solve problems, and hold complex dialogues, but their ability to engage in back-and-forth conversation also introduces a specific vulnerability. While a single question might be easy to guard against, a clever attacker can use a series of questions, slowly shifting the context of a conversation to trick the machine into revealing harmful information or bypassing its safety rules. This is known as a multi-turn jailbreak. For years, researchers have struggled to prove that these systems are safe over a long conversation. Traditional methods could only guarantee safety for a single exchange, and when they tried to extend those guarantees to a long chat, the math suggested the safety would vanish almost instantly, leaving the system wide open to attack.

A team of researchers has now developed a new framework called Multi-Turn Certified Robustness, or MTCR, which changes how we understand safety in these long conversations. Instead of treating a chat as a simple chain of independent events where safety is lost with every turn, the researchers modeled the conversation as a journey through a structured landscape. They discovered that conversations naturally fall into distinct "modes" or patterns, much like a traveler moving through different regions of a map. By breaking the conversation down into these specific regions and studying how the system moves between them, they found that safety does not necessarily degrade as quickly as previously thought. Their work provides a formal, mathematical guarantee that a conversation can remain safe for a specific number of turns, even if an attacker is actively trying to manipulate the dialogue.

The core of this discovery lies in how the researchers analyzed the flow of conversation. They realized that if a conversation stays within a safe pattern for a while, the system's safety margin—the buffer that keeps it from generating harmful content—does not shrink as fast as simple math would predict. They defined a property they call "safety persistence," which measures how well a model holds onto its safety standards as the conversation progresses. In their experiments, they tested this framework on six different large language models, ranging from open-source systems to the most advanced commercial models available. They subjected these models to rigorous testing, including a sophisticated attack style known as Crescendo, where an adversary carefully crafts a sequence of inputs to gradually break down the model's defenses.

The results were clear and reassuring. In every test case, the actual safety of the models was significantly higher than the strict, worst-case guarantees provided by the new framework. For example, on a conversation lasting twenty turns, the theoretical guarantee might suggest a safety probability of only a few percent, yet the models actually remained safe in the vast majority of trials. This gap between the strict guarantee and the real-world performance confirms that the mathematical bounds are not violated in practice, even under intense pressure. The researchers found that the most advanced models, such as those from major technology companies, maintained their safety much longer than older or less aligned models, showing that better training leads to stronger persistence.

Crucially, this work also ruled out the idea that safety must inevitably collapse exponentially as a conversation gets longer. Previous methods assumed that if a model had a 95% chance of being safe in one turn, it would have only a tiny chance of being safe after twenty turns. The new framework shows that this assumption is too pessimistic. By accounting for the structure of the conversation and the way safety margins evolve, the researchers proved that safety can be maintained for much longer than the old math allowed. They demonstrated that for a conversation to remain safe, the system does not need to be perfect at every single step; it only needs to maintain a certain level of resilience as it moves from one topic to another.

The study also highlighted the importance of how these conversations are structured. The researchers used a technique to group similar conversation states together, finding that when a model stays within a consistent group of topics, it is very hard to break its safety. It is only when the conversation jumps between very different groups that the risk increases. This insight allows for a more nuanced understanding of safety, moving away from a binary view of "safe" or "unsafe" to a dynamic view of how safety persists over time. While the formal guarantees apply to specific types of text manipulation, the researchers observed that the models held up well even against more complex, semantic attacks that go beyond simple text changes.

Ultimately, this research provides a new tool for developers and auditors to assess the safety of conversational AI before it is released to the public. It offers a way to calculate exactly how long a conversation can last before the risk of a safety failure becomes too high, providing a concrete limit based on the model's specific behavior. The framework suggests that with the right structural properties, large language models can engage in long, complex dialogues without losing their guard. This does not mean the problem is solved forever, but it establishes a firm foundation for understanding and certifying safety in the multi-turn interactions that define the future of human-AI communication. The work confirms that while attackers are clever, the underlying safety mechanisms of well-aligned models are more robust and persistent than previously believed.

Technical Summary: Certified Multi-Turn Robustness for LLM Safety via Compositional Bounds and Safety Persistence

1. Problem Formulation

Large Language Models (LLMs) deployed in conversational applications are increasingly vulnerable to multi-turn jailbreak attacks. Unlike single-turn attacks, these threats (e.g., Crescendo, X-Teaming) progressively manipulate conversation context across multiple interactions, often achieving near-perfect success rates against state-of-the-art defenses.

Existing certified robustness methods (e.g., randomized smoothing, erase-and-check) are limited to single-input settings. A straightforward extension of these methods to multi-turn scenarios involves multiplying single-turn safety probabilities. However, this approach yields bounds that degrade exponentially with the number of turns ( $k$ ). If the worst-case per-turn safety probability is $p < 1$ , the $k$ -turn bound becomes $p^k$ , which becomes negligible for moderate $k$ (e.g., dropping from 0.95 to 0.08 over 50 turns). This exponential degradation fails to provide practical guarantees for safety-critical applications.

The paper models multi-turn conversations as State-Adversarial Markov Decision Processes (SA-MDPs). In this framework:

State ( $s_t$ ): The dialogue history is mapped to an embedding space via a function $\phi$ .
Adversary: Selects user messages $u_t$ from an $\epsilon$ -perturbation ball around a reference input.
Transition: The system evolves via $s_t = T(s_{t-1}, u_t, r_t)$ , where $r_t$ is the LLM response.
Safety: Defined by a predicate partitioning the state space into safe ( $S^+$ ) and unsafe ( $S^-$ ) regions.

The goal is to define and compute $k$ -turn Certified Robustness ( $\rho_k$ ), representing the worst-case probability of maintaining safety across $k$ turns against any adaptive adversary.

2. Methodology: Multi-Turn Certified Robustness (MTCR)

The authors propose MTCR, a framework that avoids exponential degradation by exploiting structural properties of the conversational state space. The framework consists of four integrated components:

2.1 Compositional Certification via Mode Decomposition

Instead of treating the conversation as a sequence of independent turns, MTCR decomposes the safe state space $S^+$ into a set of modes $\mathcal{M} = \{m_1, \dots, m_M\}$ (clusters in embedding space).

Intra-mode Safety: Certifies the probability of remaining safe within a specific mode.
Inter-mode Transitions: Certifies the probability of transitioning safely between modes.
Bound Tightness: By separating intra-mode stability from transition costs, the compositional bound is significantly tighter than the straightforward multiplicative bound ( $p^k$ ). The bound is computed as a product of intra-mode and transition probabilities, scaled by an overlap factor $\kappa$ .
Computation: The worst-case trajectory over the mode transition graph is computed efficiently using dynamic programming in $O(M^2k)$ time.

2.2 $(\alpha, \beta)$ -Safety Persistence

The framework introduces Safety Persistence, a structural property characterizing how safety margins evolve.

Definition: A system exhibits $(\alpha, \beta)$ -safety persistence if, with probability at least $\beta$ , the safety margin $\Delta(s)$ retains at least a $(1-\alpha)$ fraction of its previous value after an adversarial turn.
Impact: Under this property, the robustness bound degrades as $\beta^k$ rather than $p^k$ . If $\beta > p$ , the bound is strictly improved.
Horizon Estimation: This allows for interpretable estimates of the maximum conversation length ( $k_{max}$ ) required to maintain a target safety level, derived via a linear characterization ( $1 - k(1-\beta)$ ).

2.3 Tightness and Impossibility Results

The paper establishes theoretical limits on certification:

Tightness: For non-overlapping mode decompositions ( $\kappa=1$ ), the compositional lower bound matches an information-theoretic upper bound, proving the approach is tight for such systems.
Impossibility: Without structural assumptions (like mode decomposition or persistence), exponential degradation ( $p^k$ ) is unavoidable. The authors prove that for memoryless systems without these structures, the straightforward bound is tight.

2.4 Unified Algorithm

A unified algorithm (Algorithm 1) combines compositional bounds and persistence parameters. It computes the final certified guarantee as the maximum of the persistence-only bound and the combined compositional-persistence bound, leveraging both structural stability and margin evolution.

3. Experimental Results

The authors evaluated MTCR on six production LLMs (including LLaMA-2, Vicuna, Llama-3.2, Qwen2.5, GPT-4o, and Claude-3.5-Sonnet) under two attack types: static $\epsilon$ -bounded perturbations and adaptive Crescendo-style attacks.

Bound Validity: Empirical safety consistently exceeded the certified MTCR bounds across all models and horizons ( $k \in \{5, 10, 15, 20\}$ ). The gap between empirical safety and the certified bound ranged from +0.19 to +0.30, confirming the bounds are not violated in practice.
Improvement over Straightforward Bounds: MTCR provided certified bounds 1.2–1.6 times tighter than the straightforward multiplicative bound ( $p^k$ ) at $k=5$ .
Model Alignment: Certified bounds correlated with model alignment strength. Closed-source models (GPT-4o, Claude-3.5) achieved higher bounds and slower degradation rates compared to open-source models, suggesting stronger underlying safety persistence.
Ablation Studies: The combined formula (Theorem 3.11) consistently outperformed "Persistence-Only" and "Compositional-Only" variants, demonstrating the value of jointly exploiting mode structure and persistence.
Sensitivity: The framework showed expected sensitivity to perturbation budgets ( $\epsilon$ ) and mode granularity ( $M$ ), with finer modes increasing overlap and potentially degrading bounds.

4. Significance and Claims

The paper claims to introduce the first theoretical framework for certified safety in multi-turn LLM conversations. Its primary contributions are:

Breaking Exponential Degradation: By moving from straightforward multiplication to compositional bounds and safety persistence, MTCR provides non-vacuous guarantees for multi-turn interactions where previous methods failed.
Formal Guarantees: It offers formal, worst-case probabilistic guarantees against $\epsilon$ -bounded adversaries, validated empirically against stronger semantic attacks (Crescendo).
Diagnostic Utility: The framework serves as a pre-deployment audit tool, identifying specific "safety bottlenecks" (modes with low intra-mode safety or risky transitions) to guide targeted safety tuning.
Theoretical Grounding: It establishes the necessity of structural assumptions (modes, persistence) for achieving sub-exponential robustness bounds, proving that without them, exponential degradation is inevitable.

The authors maintain a modest stance, acknowledging that formal certification is currently limited to $\epsilon$ -bounded perturbations (character-level) and relies on heuristic mode discovery. They note that while empirical safety generalizes to semantic attacks like Crescendo, formal guarantees beyond the $\epsilon$ -ball remain an open challenge. The framework is designed for offline certification (auditing) rather than real-time inference due to the computational cost of randomized smoothing.