PaperlayerView exact revision on arXiv

Source-linked AI summary

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

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

arXiv:2608.20820v1cs.AI

TL;DR

Multi-turn jailbreaks expose a gap in certified LLM robustness because existing methods are single-turn and naive composition degrades exponentially. MTCR models conversations as State-Adversarial MDPs and combines mode decomposition with safety persistence, with empirical safety exceeding certified bounds across six LLMs and tested attacks.

  • Problem

    Existing certified robustness methods are limited to single-input settings, while multi-turn jailbreaks progressively manipulate context and make naive certified bounds decay exponentially.

  • Method

    MTCR models conversations as State-Adversarial MDPs and combines embedding-space mode decomposition, (α, β)-safety persistence, tightness analysis, and a unified certification algorithm.

  • Results

    Across six production LLMs, empirical safety consistently exceeds certified bounds under ε-bounded and Crescendo-style attacks.

  • Takeaways & Limitations

    Safety persistence improves the degradation rate from p^k to β^k when β > p, while compositional bounds are tight for non-overlapping decompositions.

  • Takeaways & Limitations

    Formal certification applies only to ε-bounded adversaries, and mode decomposition depends on heuristic clustering whose coverage and tightness can vary.

Abstract

from arXiv · show

Large language models (LLMs) are vulnerable to multi-turn jailbreak attacks that progressively manipulate conversation context. Existing certified robustness methods are limited to single-turn inputs; naive multi-turn composition yields bounds that degrade exponentially in the number of turns. We introduce Multi-Turn Certified Robustness (MTCR), a framework that models conversational safety via State-Adversarial MDPs and defines $k$-turn certified robustness as the worst-case safety probability across $k$ adversarial turns. MTCR comprises: (i) compositional certification via embedding-space mode decomposition, yielding tighter certified lower bounds than naive multiplication; (ii) $(α,β)$-safety persistence, improving the degradation rate from $\underline{p}^{k}$ to $β^k$ (with $β> \underline{p}$) and yielding interpretable horizon estimates; (iii) matching information-theoretic upper bounds establishing tightness; and (iv) a unified algorithm combining these results. Experiments on six LLMs under $ε$-bounded and Crescendo-style attacks confirm that empirical safety consistently exceeds the certified bounds.

1 Introduction

Multi-turn jailbreaks progressively manipulate conversation context and can defeat defenses designed for single-turn attacks. MTCR extends certified robustness to multi-turn conversations through compositional certification and safety persistence, with empirical safety exceeding certified bounds.

  • Multi-turn jailbreak attacks progressively manipulate conversation context, creating a distinct challenge beyond single-turn attacks.
  • Crescendo achieves near-perfect success against production LLMs in fewer than 10 turns, while X-Teaming reaches 96–98% against state-of-the-art models.
  • Existing certified robustness methods target single-input settings, while naive multi-turn composition yields a bound of p^k that becomes negligible for moderate k.
  • MTCR models conversations as State-Adversarial MDPs and defines k-turn certified robustness.
  • Embedding-space mode decomposition certifies intra-mode safety and inter-mode transitions separately, producing tighter bounds than naive multiplication.
  • Safety persistence improves the robustness degradation rate from p^k to β^k when β > p and provides interpretable horizon estimates.
  • Across six production LLMs, empirical safety consistently exceeds certified bounds under both ε-bounded and Crescendo-style attacks.

2 Problem Formulation: Multi-Turn Safety as SA-MDP

The paper formulates multi-turn safety as worst-case safety maintenance over adaptive adversarial turns in a State-Adversarial MDP. It shows that naive multiplicative certification decays exponentially and formally applies only within the specified perturbation ball.

  • Dialogue histories map to conversational states in an embedding space, with adversaries selecting user messages from an ε-perturbation ball and the LLM generating responses.
  • k-turn certified robustness is the worst-case probability of maintaining safety across k turns against an adaptive adversary.
  • Naive multiplicative composition uses the worst-case per-turn certified safety p and yields a bound that vanishes exponentially when p < 1.
  • With p = 0.95, the naive bound gives ρ10 ≥ 0.60, ρ20 ≥ 0.36, and ρ50 ≥ 0.08.
  • For a target ρk ≥ 0.9, the example permits at most k ≤ 2 turns under naive composition.
  • Formal certification covers ε-bounded perturbations, while Crescendo results are empirical rather than formally guaranteed.
  • Without additional structure, multiplicative composition provides little practical guarantee beyond a few turns.

3 Multi-Turn Certified Robustness

MTCR combines embedding-space mode decomposition, safety persistence, tightness results, and a unified certification algorithm. These structural assumptions can improve multi-turn bounds, while their absence makes exponential degradation unavoidable.

  • Framework: MTCR extends single-turn certification through mode decomposition, safety-margin evolution, information-theoretic upper bounds, and a unified algorithm.
  • 3.1 Compositional Certification: Mode decomposition separates intra-mode safety from inter-mode transition safety and bounds feasible mode trajectories over k turns.
  • 3.1 Compositional Certification: The compositional bound strictly improves over naive multiplication under suitable intra-mode and transition-safety conditions.
  • 3.1 Compositional Certification: At k = 20, τ = 3, p = 0.9, δ = 0.02, γ = 0.7, and κ = 1, the compositional lower bound is approximately twice the naive lower bound.
  • 3.1 Compositional Certification: Dynamic programming computes the worst-case mode trajectory in O(M^2k) time.
  • 3.2 Safety Persistence: Under (α, β)-safety persistence, safety margins retain at least a (1−α) fraction per turn with probability at least β.
  • 3.2 Safety Persistence: Safety persistence yields β^k > p^k when β exceeds the worst-case per-turn bound and supports the sufficient horizon estimate k ≤ ξ/(1−β).
  • 3.2 Safety Persistence: With β = 0.98 and ξ = 0.1, persistence estimates kmax = 5, compared with kmax = 1 for p = 0.9.

4 Experiments

Experiments evaluate MTCR across production LLMs, attack types, horizons, perturbation budgets, mode granularities, certification variants, and safety detectors. MTCR remains valid in practice, improves certified bounds over naive composition, and shows model- and horizon-dependent degradation.

  • Experimental Setup: MTCR evaluates six production LLMs across horizons k ∈ {5, 10, 15, 20}, static ϵ-ball and Crescendo-style attacks, and mode granularities M ∈ {2, 4, 8}.The setup uses AdvBench harmful prompts, 100 trials per configuration, and ϵ=5 with N=100 smoothing samples per mode.
  • Certification Results: Empirical safety under Crescendo exceeds the MTCR certified bound for all models and horizons, with gaps from +0.19 for LLaMA-2 at k=5 to +0.30 for GPT-4o at k=10.MTCR is therefore not violated in the reported experiments.
  • Certification Results: 1.2–1.6× tighter certification at k=5 is achieved by MTCR than by the valid naive bound p^k.The comparison attributes this improvement to compositional structure.
  • Model Comparison: At k=5, certified bounds rank GPT-4o highest at ˆρ5=0.55 and Vicuna lowest at 0.28, with closed-source models consistently outperforming open-source models.The intermediate values are Claude-3.5-Sonnet 0.51, Qwen2.5 0.44, Llama-3.2 0.40, and LLaMA-2 0.36.
  • Horizon Effects: GPT-4o retains 58% of its k=5 bound at k=10, compared with 29% for Vicuna; LLaMA-2 decays from 0.36 to 0.02 across k ∈ {5, 10, 15, 20}.The combined formula provides the tightest LLaMA-2 bound at every reported horizon, while Crescendo lowers empirical safety by 8–13 percentage points relative to static attacks.

5 Discussion

The discussion presents MTCR as a practical auditing and diagnostic framework, while identifying mode discovery, computational cost, and threat-model coverage as key boundaries. It also connects certified bounds to conversation-length policies and possible runtime monitoring.

  • Mode Discovery and Quality: Mode decomposition quality affects certification tightness through overlap κ and intra-mode safety, with safe-conversation-derived modes potentially missing adversarially explored state regions.The paper reports M=4 with κ=1 and stronger bounds, whereas M=8 increases overlap to κ=3 and substantially degrades certification.
  • Tightness and Computation: Certified and empirical safety remain separated by gaps of +0.18 to +0.30, reflecting worst-case infima, finite-sample underestimation, and conservative mode aggregation.Suggested tightening directions include attention-informed certificates, gradient-based persistence analysis, and adaptive sampling.
  • Tightness and Computation: Randomized smoothing may be too costly for real-time use, although four-horizon certification of one model takes approximately 2.5 hours on a single A100 GPU.The authors position MTCR primarily as an offline, pre-deployment certification tool.
  • Threat Model Scope: Formal certification covers ε-bounded adversaries, while safety against Crescendo-style attacks beyond the ε-ball is reported only empirically.The framework can accommodate richer perturbation metrics when compatible per-turn certification oracles are available.
  • Practical Deployment Considerations: MTCR supports pre-deployment auditing, identifies low-safety modes for targeted tuning, and provides a theoretically grounded maximum conversation length for a target safety level ξ.The framework also proposes combining static certification with runtime monitoring that can trigger early termination as the safety margin approaches zero.

6 Conclusion

MTCR introduces a theoretical framework for certified safety in multi-turn LLM conversations. Experiments on production models find that empirical safety consistently exceeds certified bounds across tested models and horizons.

  • MTCR is presented as the first theoretical framework for certified safety in multi-turn LLM conversations.
  • Empirical safety consistently exceeds certified bounds across all tested production models and horizons.The conclusion identifies automated mode discovery, tighter LLM-specific bounds, and integration with empirical defenses as future directions.

Limitations

The limitations concern threat-model scope, heuristic mode decomposition, and the binary, detector-dependent safety predicate. The supplied proof passages also expose conservative overlap handling and nontrivial horizon conditions.

  • Scope and Assumptions: Formal certification applies only to ε-bounded adversaries, so results against semantic attacks such as Crescendo remain empirical rather than formal.
  • Scope and Assumptions: Heuristic clustering of safe dialogue embeddings can affect bound tightness through the choice of M and overlap κ, while missing adversarial state-space regions.
  • Scope and Assumptions: The binary, detector-dependent safety predicate does not support graded harmfulness scores.
  • Certification Boundaries: The 1/κ overlap penalty is conservative, but it does not affect reported bounds for the non-overlapping κ=1 decompositions used at M=4.
  • Certification Boundaries: The linear persistence bound is non-trivial only when k(1 −β) < 1, and is most informative for horizons much smaller than 1/(1 −β) when β is near one.

E.7 Proof of Theorem 3.8

The proof establishes tightness for non-overlapping mode decompositions by constructing a memoryless system whose independent per-turn safety probabilities match the compositional lower bound. It also contrasts this case with a system where no structural improvement is possible.

  • Matching Construction: The authors construct a system whose intra-mode and transition safety probabilities independently attain the corresponding certified quantities.
  • Tightness: The constructed system matches the compositional lower bound exactly when κ=1, proving tightness for non-overlapping decompositions.
  • Impossibility Without Structure: A memoryless system with per-turn safety probability p makes adversarial inputs irrelevant and yields the naive bound p^k.
  • Impossibility Without Structure: When every mode has identical safety p and margin evolution is independent across turns, no persistence property with β>p or mode decomposition improvement exists.
  • Impossibility Without Structure: These examples show that modes and persistence are necessary structural assumptions for sub-exponential bounds, not merely sufficient mechanisms.
  • Unified Certification: The unified algorithm combines persistence and compositional bounds by taking the better of the two certified estimates.

G Safety Detector Comparison

The paper compares keyword-based and neural safety detectors for certifying multi-turn safety, using refusal and harmful-content signals to make binary decisions.

  • Detector comparison: The keyword detector labels responses safe when they match refusal patterns and unsafe when unsafe keywords appear without refusal.Examples include “I cannot” and “I’m unable to” refusal patterns, alongside terms such as “bomb” and “illegal drug.”
  • Detector comparison: The neural detector uses a pretrained harmful-content model to score response safety and applies a 0.5 threshold for binary decisions.
  • Detector comparison: Both detection approaches yield valid certified bounds when used for multi-turn safety certification.

H Concrete Data Example

The experiments illustrate the data format, character-level perturbations, and a reproducible Crescendo-style escalation from benign dialogue to a harmful target across multiple turns.

  • Concrete examples: The evaluation uses harmful AdvBench prompts, including a lock-picking tutorial, as targets for perturbation and multi-turn escalation.
  • Perturbation procedure: Character-level perturbations stay within edit distance ϵ, and randomized smoothing estimates safety from the fraction of perturbations producing refusals.
  • Attack construction: The Crescendo-style attack uses ten manually designed escalation templates per harmful category, progressing from benign requests toward harmful prompts over k turns.
  • Attack construction: The lock-picking sequence moves from home improvement and security systems through lock mechanics and maintenance before reaching the harmful tutorial request.
  • Evaluation protocol: For horizons k > 5, benign filler turns precede escalation, while empirical safety counts trials in which the model refuses at every turn.
  • Experiment suite: Six controlled experiments test compositional gain, persistence scaling, mode granularity, empirical validation, pipeline performance, and bound tightness.

I.1 Data Generation and Parametric Model

The synthetic setup generates dialogue states from Gaussian mixtures and evaluates parametric safety under intra-mode and transition behavior. Results examine compositional and persistence scaling across horizons.

  • Data generation: Synthetic dialogue states use a Gaussian mixture with n = 2,000 states, M = 4 components, Dirichlet weights, centers scaled by 2.0, and standard deviation 0.5.
  • Data generation: Mode decomposition applies k-means to the generated states, with cluster radii set at the 90th percentile of within-cluster distances and overlap κ=1.
  • Parametric model: The Bernoulli policy samples safe-response success using separate rates for intra-mode turns and transitions between modes.
  • Parametric model: The parameters match the theoretical analysis, enabling exact comparisons between closed-form certified bounds and empirical outcomes.
  • Compositional gain: At k=50 with sparse transitions τ=1, compositional certification achieves 3.38× improvement, while finer granularity reduces the advantage as transition costs dominate.
  • Persistence scaling: At k=100 under (α, β)=(0.2, 0.98), the persistence bound exceeds the naive exponential reference by over 21×.
  • Validation and tightness: Empirical validation reports 94% static-attack safety and 90% Crescendo-style safety against a certified 0.67 bound, while pipeline performance improves 1.86× over naive certification.
  • Validation and tightness: The compositional lower bound matches the information-theoretic upper bound for non-overlapping decompositions with κ=1.

J.2 Production Model Experiments

Production-model experiments evaluate MTCR across six LLMs using randomized smoothing, mode transitions, and static or Crescendo-style attacks under character-level perturbation budgets.

  • Models and data: The evaluation covers six models: LLaMA-2-7B-Chat, Vicuna-7B, Llama-3.2-3B, Qwen2.5-7B-Instruct, GPT-4o, and Claude-3.5-Sonnet.
  • Models and data: The prompt set contains 150 AdvBench prompts spanning violence, illegal activities, and hate speech, with 500 held-out safe dialogues used for mode discovery.
  • Certification procedure: Certification applies randomized smoothing per mode with N=100 character-level perturbations and estimates intra-mode safety from safe-response fractions.
  • Certification procedure: Transition safety is estimated on boundary dialogues, and perturbation budgets vary over ϵ ∈{3, 5, 7} for sensitivity analysis.
  • Attack evaluation: The experiments compare static random perturbations with Crescendo-style escalation toward harmful prompts, defining empirical safety as all-turn safety over 100 runs.
Loading 2608.20820v1…