Paper deep dive
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
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 94%
Last extracted: 8/24/2026, 5:25:08 AM
Summary
The paper introduces Multi-Turn Certified Robustness (MTCR), a framework for certifying the safety of Large Language Models (LLMs) against multi-turn jailbreak attacks. It addresses the exponential degradation of safety bounds in existing methods by utilizing State-Adversarial Markov Decision Processes (SA-MDPs). MTCR employs compositional certification via embedding-space mode decomposition and $(\alpha,\beta)$-safety persistence to derive tighter lower bounds on safety probability. Experiments on six LLMs demonstrate that empirical safety exceeds these certified bounds under $\epsilon$-bounded and Crescendo-style attacks.
Entities (10)
Relation Signals (7)
Yang Liu → affiliatedwith → Peking University
confidence 95% · Yang Liu Affiliation: Peking University
Bin Chong → affiliatedwith → Peking University
confidence 95% · Bin Chong Affiliation: Peking University
GuoZhen → affiliatedwith → Tencent Hunyuan
confidence 95% · GuoZhen Affiliation: Tencent Hunyuan
MTCR → improvesupon → Naive Multiplicative Bound
confidence 95% · yielding tighter certified lower bounds than naive multiplication
MTCR → uses → SA-MDP
confidence 95% · MTCR... models conversational safety via State-Adversarial MDPs
MTCR → utilizes → Safety Persistence
confidence 92% · MTCR comprises: ... (ii) ($\alpha,\beta$)-safety persistence
MTCR → evaluatedagainst → Crescendo
confidence 90% · Experiments on six LLMs under ... Crescendo-style attacks
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract: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) $(\alpha,\beta)$-safety persistence, improving the degradation rate from $\underline{p}^{k}$ to $\beta^k$ (with $\beta > \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 $\epsilon$-bounded and Crescendo-style attacks confirm that empirical safety consistently exceeds the certified bounds.
Tags
Links
- Source: https://arxiv.org/abs/2608.20820v1
- Canonical: https://arxiv.org/abs/2608.20820v1
Trouble viewing inline? Open PDF directly →
Full Text
83,705 characters extracted from source content.
Expand or collapse full text
Certified Multi-Turn Robustness for LLM Safety via Compositional Bounds and Safety Persistence Yang Liu Affiliation: Peking University Bin Chong Affiliation: Peking University Affiliation: Corresponding author: chongbin@pku.edu.cn Wenkai Yang Affiliation: Renmin University of China Shuai Zhang Affiliation: Tsinghua University Yancheng Chen Affiliation: University of Chinese Academy of Sciences Feiyu Han Affiliation: University of Chinese Academy of Sciences GuoZhen Affiliation: Tencent Hunyuan Cheng Zhang Affiliation: Tencent Hunyuan Huaibing Xie Affiliation: Tencent Hunyuan Changze Lv Affiliation: Tencent Hunyuan Shihan Dou Affiliation: Tencent Hunyuan Pluto Zhou Affiliation: Tencent Hunyuan Abstract 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; (i) (α,β)(α,β)-safety persistence, improving the degradation rate from p¯k p^\,k to βkβ^k (with β>p¯β> p) and yielding interpretable horizon estimates; (i) 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 The deployment of large language models (LLMs) in conversational applications has raised safety concerns, particularly regarding jailbreak attacks: carefully crafted inputs designed to bypass safety mechanisms and elicit harmful content (Zou et al. 2023; Wei et al. 2023). Although substantial progress has been made in defending against single-turn attacks, multi-turn jailbreak attacks that progressively manipulate conversation context across multiple interactions pose a distinct challenge (Russinovich et al. 2025; Li et al. 2024). Recent empirical studies reveal the severity of this threat. The Crescendo attack (Russinovich et al. 2025) achieves near-perfect success rates against production LLMs using fewer than 10 turns; X-Teaming (Rahman et al. 2025) attains 96–98% success rates against state-of-the-art models; human red-teamers consistently exceed 70% success against deployed defenses (Li et al. 2024). These findings indicate that defenses robust against single-turn attacks offer little protection in multi-turn settings. On the theoretical side, existing certified robustness methods (randomized smoothing (Robey et al. 2023), erase-and-check (Kumar et al. 2023), knapsack-based certification (Chen et al. 2025)) are limited to single-input settings. A naive extension yields certified lower bounds that degrade exponentially in the number of turns: if each turn has worst-case certified safety probability p, the k-turn bound under multiplicative composition is merely pkp^k, which becomes negligible for moderate k. This degradation arises because adaptive adversaries observe responses and craft subsequent inputs (a sequential game), accumulated context compounds adversarial influence, and autoregressive generation amplifies early-token perturbations. Contributions. We develop Multi-Turn Certified Robustness (MTCR), a certification framework grounded in SA-MDP theory, with three contributions: (1) We model multi-turn conversations as State-Adversarial MDPs and define k-turn certified robustness. We develop compositional certification via embedding-space mode decomposition: certifying intra-mode safety and inter-mode transitions separately yields bounds tighter than naive multiplication (Corollary 3.2). A unified algorithm (Algorithm 1) combines compositional and persistence bounds to compute the certified guarantee in practice. (2) We formalize (α,β)(α,β)-safety persistence, a structural property under which the robustness bound improves from p¯k p^\,k to βkβ^k (when β>p¯β> p), with a linear characterization 1−k(1−β)1-k(1-β) that yields interpretable horizon estimates (Theorem 3.5). We prove information-theoretic upper bounds showing our compositional approach is tight for non-overlapping decompositions, and impossibility results for systems that lack structural assumptions. (3) We evaluate MTCR on six production LLMs. The certified bounds provide formal guarantees against ϵε-bounded adversaries; empirical safety consistently exceeds the bound under both static (ϵε-ball) and Crescendo-style adaptive attacks, confirming that the bounds are not violated in practice. Figure 1: Overview of MTCR. Left: Multi-turn conversations modeled as SA-MDPs; naive bound p¯k p^\,k degrades exponentially. Center: MTCR combines compositional certification (intra-mode + transition safety) with (α,β)(α,β)-persistence into a unified bound. Right: Matching upper bounds establish tightness (κ=1κ=1). Experiments on six LLMs confirm empirical safety exceeds the certified bounds. 2 Problem Formulation: Multi-Turn Safety as SA-MDP We model multi-turn conversations as State-Adversarial MDPs (SA-MDPs). The dialogue history ht=(u1,r1,…,ut,rt)h_t=(u_1,r_1,…,u_t,r_t) maps to a conversational state st=ϕ(ht)∈⊆ℝds_t=φ(h_t) ^d via an embedding ϕφ (e.g., LLM hidden representations). An adversary selects user messages utu_t from an ϵε-perturbation ball ℬϵB_ε around a reference input; the LLM responds according to policy π(⋅|s,u)π(·|s,u). States evolve as st=T(st−1,ut,rt)s_t=T(s_t-1,u_t,r_t). A safety predicate :→0,1 Safe:S→\0,1\ partitions the state space into a safe region +S_+ and an unsafe region −S_-, with safety margin Δ(s)=dist(s,−) (s)=dist(s,S_-). We assume S is bounded, +S_+ is open (so Δ(s)>0 (s)>0 for all s∈+s _+), and +S_+ has non-empty interior with δmin _ denoting the maximum inscribed ball radius. Full formal definitions appear in Appendix B. Definition 1 (k-Turn Certified Robustness). Given initial state s0∈+s_0 _+, LLM policy π, perturbation budget ϵε, and horizon k∈ℕk , the k-turn certified robustness ρk(s0,π,ϵ) _k(s_0,π,ε) is: infν∈Πϵℙut∼ν(⋅|st−1)rt∼π(⋅|st−1,ut)[⋀t=1k(st)|s0], _ν∈ _εP_ subarraycu_t ν(·|s_t-1)\\ r_t π(·|s_t-1,u_t) subarray [ _t=1^k Safe(s_t)\, |\,s_0 ], (1) where states evolve according to st=T(st−1,ut,rt)s_t=T(s_t-1,u_t,r_t). The quantity ρk(s0,π,ϵ) _k(s_0,π,ε) captures the worst-case probability of maintaining safety across k turns against any adaptive adversary (one that observes st−1s_t-1 before choosing utu_t). A natural certification strategy is to compose single-turn safety bounds multiplicatively. For each state s, let p(s,ϵ)=infu∈ℬϵℙ[(T(s,u,r))]p(s,ε)= _u _εP[ Safe(T(s,u,r))] denote the certified probability of remaining safe after one adversarial turn. This composition yields the following bound. Proposition 2.1 (Naive Multiplicative Bound). For any s0∈+s_0 _+: ρk(s0,π,ϵ)≥(infs∈+p(s,ϵ))k=p¯k, _k(s_0,π,ε)≥ ( _s _+p(s,ε) )^k= p^\,k, (2) where p¯=infs∈+p(s,ϵ) p= _s _+p(s,ε) is the worst-case per-turn certified safety. If p¯<1 p<1, this bound vanishes exponentially in k. Example 2.2 (Vacuity of Naive Bound). With per-turn safety p¯=0.95 p=0.95: ρ10≥0.60 _10≥ 0.60, ρ20≥0.36 _20≥ 0.36, ρ50≥0.08 _50≥ 0.08. For safety-critical applications requiring ρk≥0.9 _k≥ 0.9, this permits at most k≤2k≤ 2 turns. Scope of certification. The certified guarantee applies to adversaries constrained within an ϵε-ball (e.g., character-level edit distance) around reference inputs. Real attacks such as Crescendo operate at the semantic level; while our experiments report empirical safety against such attacks, the formal certification covers only ϵε-bounded perturbations. The SA-MDP framework is agnostic to the perturbation metric and extends to richer threat models once compatible per-turn certification oracles become available. Without additional structure, the multiplicative composition provides little practical guarantee for conversations beyond a few turns. This motivates identifying structural conditions under which tighter bounds can be achieved. 3 Multi-Turn Certified Robustness We extend single-turn certification to multi-turn conversations by exploiting mode structure in embedding space and safety margin evolution. The framework has four parts: compositional bounds via mode decomposition (§3.1), safety persistence characterizing margin evolution (§3.2), information-theoretic upper bounds establishing tightness (§3.3), and a unified algorithm (§3.4). 3.1 Compositional Certification Conversations exhibit mode structure in embedding space that can be exploited for tighter certification. A mode decomposition ℳ=m1,…,mMM=\m_1,…,m_M\ covers +S_+ with bounded overlap κ=maxs|i:s∈mi|κ= _s|\i:s _m_i\|. For each mode m we define intra-mode certified safety ρmin(ϵ) _m^in(ε) (worst-case probability of staying safe and in m) and for edges (mi,mj)(m_i,m_j) in the transition graph we define transition safety ρi→jtr(ϵ) _i→ j^tr(ε). A mode trajectory σ over k turns has nj(σ)n_j(σ) intra-mode turns in mjm_j and τ(σ)τ(σ) transitions. Full definitions appear in Appendix B. Theorem 3.1 (Compositional Certification Bound). Let ℳ=m1,…,mMM=\m_1,…,m_M\ be a mode decomposition with overlap κ=κ(ℳ)κ=κ(M). For any k-turn conversation with mode trajectory σ∈Σk(ℳ)σ∈ _k(M): ρk(s0,π,ϵ)≥1κ _k(s_0,π,ε)≥ 1κ ⋅∏j=1M(ρmjin(ϵ))nj(σ) · _j=1^M ( _m_j^in(ε) )^n_j(σ) ⋅∏(i,j)∈Trans(σ)ρi→jtr(ϵ) · _(i,j) (σ) _i→ j^tr(ε) where Trans(σ)=(σ(t),σ(t+1)):σ(t)≠σ(t+1)Trans(σ)=\(σ(t),σ(t+1)):σ(t)≠σ(t+1)\ is the multiset of transitions. Taking the infimum over feasible trajectories: ρk(s0,π,ϵ)≥1κ⋅ _k(s_0,π,ε)≥ 1κ· infσ∈Σk(ℳ,s0)[∏j=1M(ρmjin)nj(σ) _σ∈ _k(M,s_0) [ _j=1^M ( _m_j^in )^n_j(σ) ⋅∏(i,j)∈Trans(σ)ρi→jtr] · _(i,j) (σ) _i→ j^tr ] where Σk(ℳ,s0)⊆Σk(ℳ) _k(M,s_0) _k(M) are trajectories starting from a mode containing s0s_0. The following corollary quantifies when the compositional bound strictly improves upon the naive multiplicative bound. Corollary 3.2 (Improvement over Naive Composition). Let p¯=infsp(s,ϵ) p= _sp(s,ε) be the naive per-turn bound. Suppose the mode decomposition satisfies: 1. Intra-mode safety: ρmjin≥1−δ _m_j^in≥ 1-δ for small δ>0δ>0 2. Inter-mode transition safety: ρi→jtr≥γ _i→ j^tr≥γ for some γ∈(0,1)γ∈(0,1) 3. Sparse transitions: trajectory σ has at most τ transitions Then the compositional bound is: ρkcomp≥1κ(1−δ)k−τ⋅γτ _k^comp≥ 1κ(1-δ)^k-τ·γ^τ (3) This exceeds the naive bound p¯k p^\,k when: τ<klog(1−δ)−klogp¯−logκlog(1−δ)−logγτ< k (1-δ)-k p- κ (1-δ)- γ (4) Example 3.3 (Numerical Comparison). Under parameters k=20k=20, τ=3τ=3, p¯=0.9 p=0.9, δ=0.02δ=0.02, γ=0.7γ=0.7, κ=1κ=1: ρ20naive _20^naive ≥0.920≈0.122 ≥ 0.9^20≈ 0.122 ρ20comp _20^comp ≥0.9817⋅0.73≈0.708⋅0.343≈0.243 ≥ 0.98^17· 0.7^3≈ 0.708· 0.343≈ 0.243 The compositional certified lower bound is approximately twice the naive lower bound. Note: improvement depends on k and τ; when k is small, transition overhead may dominate (see Appendix I.2). Computing the compositional bound requires finding the worst-case trajectory over the mode transition graph. This can be done efficiently, as the following proposition shows. Proposition 3.4 (Worst-Case Trajectory Computation). The trajectory infimum in Theorem 3.1 can be computed by dynamic programming in O(M2k)O(M^2k) time. 3.2 Safety Persistence The compositional bound still depends on the number of transitions τ. We next define safety persistence, a property that enables stronger guarantees by characterizing how safety margins evolve. Definition 2 ((α,β)(α,β)-Safety Persistence). A conversational system (,T,π,)(S,T,π, Safe) exhibits (α,β)(α,β)-safety persistence for α∈[0,1)α∈[0,1) and β∈(0,1]β∈(0,1] if for all safe states s∈+s _+ with safety margin Δ(s)>0 (s)>0: ℙu∼ν,r∼π[(s′)=1∧Δ(s′)≥(1−α)Δ(s)]≥βP_u ν,\,r π\! [ gathered Safe(s )=1\\ \ (s )≥(1-α) (s) gathered ]≥β (5) where s′=T(s,u,r)s =T(s,u,r) and ν∈Πϵν∈ _ε is any adversarial policy. With probability at least β, the safety margin retains at least a (1−α)(1-α) fraction of its previous value per turn; well-aligned LLMs typically satisfy this property. Under safety persistence, we obtain the following guarantee. Theorem 3.5 (Degradation under Safety Persistence). Suppose the system exhibits (α,β)(α,β)-safety persistence. Let s0∈+s_0 _+ have initial margin Δ0=Δ(s0)>0 _0= (s_0)>0. Then: ρk(s0,π,ϵ)≥βk _k(s_0,π,ε)≥β^k (6) When β>p¯β> p (i.e., the persistence guarantee exceeds the worst-case per-turn bound), we have βk>p¯kβ^k> p^\,k, strictly improving upon the naive bound. Additionally, a union bound yields an interpretable (though numerically weaker) characterization: ρk(s0,π,ϵ)≥1−k(1−β) _k(s_0,π,ε)≥ 1-k(1-β) (7) This formula provides a sufficient condition for safety: the system remains safe with probability ≥1−ξ≥ 1-ξ whenever k≤ξ/(1−β)k≤ξ/(1-β), enabling direct horizon estimation. Corollary 3.6 (Effective Horizon Estimation). Under (α,β)(α,β)-safety persistence, to maintain ρk≥1−ξ _k≥ 1-ξ for target ξ∈(0,1)ξ∈(0,1), the linear characterization gives the sufficient horizon bound: kmax=⌊ξ1−β⌋k_ = ξ1-β (8) compared to kmax=⌊log(1−ξ)/logp¯⌋k_ = (1-ξ)/ p under naive composition. For example, with β=0.98β=0.98 and ξ=0.1ξ=0.1: the persistence-based estimate gives kmax=5k_ =5, whereas p¯=0.9 p=0.9 gives kmax=1k_ =1. Safety persistence can be verified from Lipschitz continuity of the transition dynamics and concentration properties of the LLM output; the following proposition gives sufficient conditions. Proposition 3.7 (Persistence from Lipschitz Continuity). Suppose: 1. T is LsL_s-Lipschitz in state: ‖T(s,u,r)−T(s′,u,r)‖≤Ls‖s−s′‖\|T(s,u,r)-T(s ,u,r)\|≤ L_s\|s-s \| 2. T is LuL_u-Lipschitz in input: ‖T(s,u,r)−T(s,u′,r)‖≤Lu⋅d(u,u′)\|T(s,u,r)-T(s,u ,r)\|≤ L_u· d(u,u ) 3. T is LrL_r-Lipschitz in response: ‖T(s,u,r)−T(s,u,r′)‖≤Lr⋅dr(r,r′)\|T(s,u,r)-T(s,u,r )\|≤ L_r· d_r(r,r ) for some metric drd_r 4. The safe region satisfies: +S_+ is convex with dist(s,−)≥δdist(s,S_-)≥δ for s in the δ-interior 5. LLM responses satisfy: ℙ[∥r−r∗∥≤η]≥p0P[\|r-r^*\|≤η]≥ p_0 for some nominal response r∗r^* 6. Nominal drift is bounded: ‖T(s,u∗,r∗)−s‖≤δT\|T(s,u^*,r^*)-s\|≤ _T for all s∈+s _+ Then for all states s in the δ-interior of +S_+ (i.e., Δ(s)≥δ (s)≥δ), the (α,β)(α,β)-persistence condition (Definition 2) holds with: α α =Luϵ+Lrη+δTδ, = L_uε+L_rη+ _Tδ, (9) β β =p0⋅[Luϵ+Lrη+δT<δ]. =p_0·1[L_uε+L_rη+ _T<δ]. The indicator function reflects a strict sufficient condition; when Luϵ+Lrη+δT≥δL_uε+L_rη+ _T≥δ, it yields β=0β=0, making the bound vacuous. This occurs in many practical settings where the perturbation budget and nominal drift are large relative to the safety margin. Proposition 3.7 serves as a theoretical grounding showing when persistence holds from first principles; in our experiments, persistence parameters are instead estimated empirically via sampling (Algorithm 1 Phase 1; see Appendix F.1). 3.3 Tightness and Impossibility Results We establish that our compositional bounds are tight. The following theorem gives an information-theoretic upper bound via a matching construction, showing that the compositional product cannot be improved for non-overlapping decompositions. Theorem 3.8 (Information-Theoretic Upper Bound on Certification). For any mode decomposition ℳM and any trajectory σ, there exist transition dynamics T and adversarial strategies ν∗ν^* such that: ρk(s0,π,ϵ)≤∏j=1M _k(s_0,π,ε)≤ _j=1^M (ρmjin)nj(σ) ( _m_j^in )^n_j(σ) ⋅∏(i,j)∈Trans(σ)ρi→jtr · _(i,j) (σ) _i→ j^tr The compositional product is also an upper bound for a worst-case system matching the mode-level safety parameters. Corollary 3.9 (Near-Optimality of Compositional Bounds). For non-overlapping mode decompositions (κ=1κ=1), our compositional lower bound (Theorem 3.1) matches the information-theoretic upper bound (Theorem 3.8) exactly. The compositional certification is therefore tight for κ=1κ=1. These positive results rely on structural assumptions. Without such assumptions, exponential degradation is unavoidable, as the following impossibility result shows. Theorem 3.10 (Impossibility of Sub-Exponential Bounds in General). Without structural assumptions (mode decomposition or safety persistence), there exist conversational systems where: ρk(s0,π,ϵ)=pk _k(s_0,π,ε)=p^k (10) for some p<1p<1, and the naive multiplicative bound p¯k p^\,k is tight. The proof constructs a memoryless system where the transition function T maps every (s,u,r)(s,u,r) to a fresh state drawn independently from a fixed distribution, with ℙ[(s′)=1]=pP[ Safe(s )=1]=p regardless of the adversary’s choice of u (see Appendix E.8). Since turns are independent and each has safety probability exactly p, we get ρk=pk _k=p^k. Thus our structural assumptions (modes, persistence) are necessary to guarantee sub-exponential bounds, not merely sufficient for achieving them. 3.4 Unified Framework and Algorithm We synthesize the above results into a unified certification framework. When the system admits both a mode decomposition and safety persistence, we obtain the following combined bound. Theorem 3.11 (Combined Bound). Suppose the system has mode decomposition ℳM with overlap κ and exhibits (α,β)(α,β)-safety persistence within each mode. Then: ρk(s0,π,ϵ)≥βkκ⋅infσ∈Σk(ℳ,s0)[ _k(s_0,π,ε)≥ β^kκ· _σ∈ _k(M,s_0) [ ∏j(ρmjinβ)nj(σ) _j ( _m_j^inβ )^\!n_j(σ) ⋅∏(i,j)ρi→jtr] · _(i,j) _i→ j^tr ] When ρmjin≥β _m_j^in≥β for all modes (persistence dominates intra-mode certification): ρk≥βkκ⋅γτ _k≥ β^kκ·γ^τ (11) where γ=mini,jρi→jtrγ= _i,j _i→ j^tr and τ is the number of transitions. Algorithm 1 formalizes the four-phase procedure: certify intra-mode and inter-mode safety, compute the worst-case trajectory via dynamic programming, and combine with persistence parameters. Phase 3 uses ρ^mjin/β ρ_m_j^in/ β (not ρ^mjin ρ_m_j^in) for intra-mode steps, consistent with Theorem 3.11, since the persistence baseline is already captured by β^k β^k in Phase 4. The final output is max(β^k,ρ^kcomb) ( β^k, ρ_k^comb), taking the better of the persistence-only and combined bounds. In practice, the combined formula dominates because it exploits both mode structure and persistence jointly (Table 3). Let N be the number of samples for randomized smoothing. Phase 1 requires O(MN)O(MN) LLM forward passes; Phase 2 requires O(|Eℳ|N)O(|E_M|N) passes; Phase 3 performs O(M2k)O(M^2k) arithmetic operations. The total complexity is O((M+|Eℳ|)N+M2k)O((M+|E_M|)N+M^2k), which is linear in the horizon k. 4 Experiments We evaluate MTCR on production LLMs under real attack scenarios. Appendix I provides additional numerical verification under a controlled parametric model. 4.1 Experimental Setup Compared methods. No prior method provides certified multi-turn robustness. We compare four variants: Mult. ref., the multiplicative reference p¯k p^k with p¯=supsp(s,ϵ) p= _sp(s,ε) (an optimistic reference, not a valid certified bound under adaptive adversaries); Persistence-Only, applying the (α,β)(α,β)-persistence bound alone; Compositional-Only, using mode decomposition without persistence; and MTCR (full), our combined certification (Algorithm 1). Data. We use harmful prompts from AdvBench (Zou et al. 2023), covering violence, illegal activities, and hate speech (50 prompts per category, 150 total). Mode discovery. Dialogue state embeddings are computed on n=500n=500 held-out safe multi-turn conversations (ShareGPT-style) using sentence-transformers. Each state is the embedding of the full dialogue history. Modes are discovered via k-means clustering in embedding space, with cluster radii set at the 90th percentile of within-cluster distances. This is geometric clustering; we do not claim these clusters correspond to human-interpretable semantic categories, though they capture safety-relevant structure as evidenced by the high intra-mode safety rates. Evaluation protocol. Each attack trial runs k turns; empirical safety is the fraction of trials in which all turns remain safe. We report results over 100 trials per configuration; 95% Clopper–Pearson confidence intervals are ≤±0.05≤± 0.05 across all settings and omitted from tables for clarity. A concrete example of the data format, perturbation procedure, and Crescendo-style attack progression appears in Appendix H. 4.2 Experiments on Production Models We evaluate six LLMs with varying alignment strengths. Open-source: LLaMA-2-7B-Chat (Touvron et al. 2023), Vicuna-7B (Chiang et al. 2023), Llama-3.2-3B, and Qwen2.5-7B-Instruct (Yang et al. 2025). Closed-source (via API): GPT-4o (Hurst et al. 2024) and Claude-3.5-Sonnet (Anthropic 2024). The evaluation covers horizons k∈5,10,15,20k∈\5,10,15,20\, two attack types (static ϵε-ball and Crescendo-style), and mode granularities M∈2,4,8M∈\2,4,8\. Dialogue state embeddings use all-MiniLM-L6-v2. Safety is judged by a harmful-content detector combining refusal patterns and an unsafe-keyword list; we also compare with neural classifiers (Appendix G). Perturbation budget is ϵ=5ε=5 (character-level edit distance, following SmoothLLM (Robey et al. 2023)), with N=100N=100 smoothing samples per mode and ϵ∈3,5,7ε∈\3,5,7\ for sensitivity analysis. Full details are in Appendix J.2. Table 1: Certification and empirical safety across six LLMs (M=4M=4, N=100N=100, ϵ=5ε=5, 100 trials). MTCR ρ^k ρ_k: certified lower bound; Naive p¯k p^\,k: valid but loose multiplicative bound; Mult. ref. p¯k p^k: optimistic reference (not a valid certified bound under adaptive adversaries); Gap == Emp. (Crescendo) −- MTCR ρ^k ρ_k. Bold: best certified bound per horizon. Model k Certification Empirical Safety Gap MTCR ρ^k ρ_k Naive p¯k p^\,k Mult. ref. Static Crescendo Open-source models LLaMA-2-7B-Chat 5 0.36 0.29 0.59 66% 55% +0.19 10 0.13 0.08 0.35 49% 38% +0.25 15 0.05 0.02 0.21 38% 28% +0.23 20 0.02 0.01 0.12 30% 22% +0.20 Vicuna-7B 5 0.28 0.22 0.50 58% 46% +0.18 10 0.08 0.05 0.25 40% 30% +0.22 Llama-3.2-3B 5 0.40 0.33 0.66 72% 62% +0.22 10 0.18 0.11 0.43 56% 45% +0.27 Qwen2.5-7B-Instruct 5 0.44 0.35 0.70 76% 65% +0.21 10 0.22 0.12 0.48 60% 49% +0.27 Closed-source models (API) GPT-4o 5 0.55 0.44 0.82 88% 78% +0.23 10 0.32 0.20 0.66 73% 62% +0.30 Claude-3.5-Sonnet 5 0.51 0.42 0.77 85% 74% +0.23 10 0.28 0.18 0.60 70% 58% +0.30 We highlight three findings from Table 1. (1) Bound validity. Empirical safety under the strongest attack (Crescendo) exceeds the MTCR certified bound across all models and horizons, with gaps from +0.19+0.19 (LLaMA-2, k=5k=5) to +0.30+0.30 (GPT-4o, k=10k=10). This confirms the certified guarantee is not violated in practice. Comparing MTCR with the naive bound p¯k p^\,k (which is also a valid certified bound), MTCR provides 1.2–1.6× tighter certification at k=5k=5, demonstrating the value of compositional structure. (2) Model ranking and alignment quality. Certified bounds reflect alignment strength: at k=5k=5, GPT-4o achieves the highest certified bound (ρ^5=0.55 ρ_5=0.55), followed by Claude-3.5-Sonnet (0.510.51), Qwen2.5 (0.440.44), Llama-3.2 (0.400.40), LLaMA-2 (0.360.36), and Vicuna (0.280.28). Closed-source models consistently outperform open-source ones, suggesting stronger underlying safety alignment. (3) Degradation with horizon. Examining the ratio ρ^10/ρ^5 ρ_10/ ρ_5 across models reveals that better-aligned models degrade more slowly: GPT-4o retains 58% of its k=5k=5 bound at k=10k=10, compared to only 29% for Vicuna. This supports Theorem 3.5: systems with stronger safety persistence exhibit slower degradation. For LLaMA-2, the full k∈5,10,15,20k∈\5,10,15,20\ trajectory shows progressive decay from 0.360.36 to 0.020.02, with the combined formula (Theorem 3.11) providing the tightest bound at all horizons (Table 3). Crescendo reduces empirical safety by 8–13 percentage points relative to static attacks; stronger models show larger absolute but smaller relative drops. Figure 2 visualizes this degradation. 55101015152020000.10.10.20.20.30.30.40.40.50.50.60.60.70.7Horizon kkBoundMTCR ρ^k ρ_kMult. ref. p¯k p^kEmp. (Static)Emp. (Crescendo) Figure 2: Certified lower bound vs. horizon k on LLaMA-2-7B-Chat (p¯=0.90 p=0.90, p¯=0.78 p=0.78; data from Table 1). The MTCR curve lies below empirical safety under both attack types at all horizons, confirming the certified bound is not violated. We vary mode granularity M∈2,4,8M∈\2,4,8\ on LLaMA-2-7B-Chat at k=5k=5. Coarser modes (M=2M=2) yield ρ^5=0.39 ρ_5=0.39; finer modes (M=8M=8) yield 0.250.25 due to increased overlap κ and transition cost. Although M=2M=2 gives a marginally higher bound at k=5k=5, it provides less diagnostic value (fewer modes to identify safety bottlenecks) and lower intra-mode homogeneity, which degrades certification at longer horizons. We use M=4M=4 throughout. Perturbation budget sensitivity. Table 2 varies ϵ∈3,5,7ε∈\3,5,7\ on LLaMA-2-7B-Chat. Larger ϵε enlarges the adversarial ball ℬϵB_ε, lowering certified bounds as expected; empirical safety follows the same trend. Table 2: Perturbation budget ϵε sensitivity (LLaMA-2-7B-Chat, M=4M=4, k=5,10k=5,10, 100 trials). ϵε MTCR ρ^5 ρ_5 MTCR ρ^10 ρ_10 Emp.5 (Static) Emp.10 (Static) 3 0.49 0.19 75% 58% 5 0.36 0.13 66% 49% 7 0.24 0.07 55% 37% MTCR ablation. Table 3 ablates the certification variants on LLaMA-2-7B-Chat. The combined formula (Theorem 3.11) consistently gives the tightest certified bound across all horizons, as it exploits both mode structure and persistence. The persistence-only bound (β^k β^k with β^=0.79 β=0.79) degrades faster than the combined formula because it does not exploit intra-mode safety rates that exceed the global persistence baseline. Compositional-Only outperforms Persistence-Only at k=5k=5 when transitions are sparse (see Appendix I.2), but degrades similarly at longer horizons. Table 3: MTCR component ablation (LLaMA-2-7B-Chat, M=4M=4, ϵ=5ε=5, β^=0.79 β=0.79, 100 trials). Mult. ref. is an optimistic reference (not certified). Bold: best certified bound per horizon. MTCR (max) takes the maximum over component bounds. Method k=5k=5 k=10k=10 k=15k=15 k=20k=20 Mult. ref. p¯k p^k 0.59 0.35 0.21 0.12 Persistence-Only (β^k β^k) 0.31 0.10 0.03 0.01 Compositional-Only 0.34 0.11 0.04 0.01 Combined (Thm. 3.11) 0.36 0.13 0.05 0.02 MTCR (max) 0.36 0.13 0.05 0.02 Safety detector comparison. Table 4 compares keyword-based detection (refusal patterns + unsafe keywords) with a neural harmful-content classifier. Both yield conservative certified bounds; the neural detector may differ in empirical safety rates on edge cases. See Appendix G for setup. Table 4: Safety detector comparison (LLaMA-2-7B-Chat, k=5k=5, ϵ=5ε=5, 100 trials). Detector MTCR ρ^5 ρ_5 Emp. (Static) Emp. (Crescendo) Keyword-based (default) 0.36 66% 55% Neural classifier 0.33 70% 59% Sample complexity. Tight certification via randomized smoothing requires N=O(log(1/δconf)/γgap2)N=O( (1/ _conf)/ _gap^2) samples, where δconf _conf is the confidence level and γgap _gap is the gap between the true safety probability and the certification threshold. We use N=100N=100 for computational feasibility; increasing N would tighten confidence intervals but not change the qualitative findings. 5 Discussion Mode Discovery and Quality. Our framework assumes a mode decomposition is given (Section 4.1, Appendix F). Mode quality affects certification tightness through two channels: (i) the overlap parameter κ, introducing a 1/κ1/κ penalty in Theorem 3.1, and (i) intra-mode safety ρmin _m^in, which depends on mode homogeneity. In our experiments, k-means with M=4M=4 yields κ=1κ=1 and intra-mode safety above the persistence baseline, while M=8M=8 increases overlap (κ=3κ=3) and degrades the bound substantially. The mode decomposition is derived from safe conversations and may not cover state-space regions explored under adversarial conditions; extending mode discovery to include adversarial trajectory data is a direction for future work. Balancing granularity against overlap remains open; one direction is formulating mode discovery as constrained optimization minimizing κ subject to a minimum intra-mode safety threshold. Tightness and Computation. While our bounds improve upon naive composition, gaps remain between certified and empirical safety (Table 1, Gap: +0.18+0.18 to +0.30+0.30), arising from worst-case infima, finite-sample smoothing underestimates, and conservative mode-level aggregation. Potential tightening includes attention-pattern-informed per-turn certificates, gradient-based persistence analysis, and adaptive sampling for high-variance modes. The sample cost of randomized smoothing may be prohibitive for real-time use; our framework targets offline certification, similar to (Chen et al. 2025). Full certification of a single model at four horizons requires approximately 2.5 hours on a single A100 GPU (open-source) or comparable API cost (closed-source), practical for pre-deployment auditing. Threat Model Scope. Formal certification covers ϵε-bounded adversaries (Section 2). The empirical observation that Crescendo attacks (beyond the ϵε-ball) do not violate the certified bound suggests that mode structure and persistence capture safety properties generalizing beyond the perturbation model, though this remains empirical rather than formal. Extending to semantic-level perturbations (e.g., sentence-embedding distance) requires only a compatible per-turn oracle, which the SA-MDP framework accommodates without structural changes. Practical Deployment Considerations. MTCR serves as both a pre-deployment audit tool quantifying worst-case multi-turn safety and a diagnostic identifying safety bottlenecks (modes with low ρmin _m^in or transitions with low ρi→jtr _i→ j^tr), guiding targeted safety tuning. It can also inform conversation-length policies: given a target safety level ξ, Corollary 3.6 provides a theoretically grounded maximum conversation length kmaxk_ . Extensions. A natural next step is combining MTCR with runtime monitoring: the certified bound provides a static guarantee, while online tracking of Δ(st) (s_t) can trigger early termination when the margin approaches zero. Extending the binary safety predicate to graded scores (continuous harmfulness severity) requires modifying the persistence definition, but the compositional structure carries over directly. 6 Conclusion We introduced Multi-Turn Certified Robustness (MTCR), the first theoretical framework for certified safety in multi-turn LLM conversations. Experiments on production LLMs confirm that empirical safety consistently exceeds the certified bounds across all tested models and horizons. The framework opens directions such as automated mode discovery, tighter LLM-specific bounds, and integration with empirical defenses. Limitations MTCR has several limitations. First, the formal certification applies only to ϵε-bounded adversaries (e.g., character-level perturbations); while empirical safety generalizes to semantic attacks like Crescendo, no formal guarantee is provided beyond the ϵε-ball. Second, mode decomposition relies on heuristic clustering of safe dialogue embeddings; the choice of M and overlap κ affects bound tightness, and the decomposition may not cover adversarial state-space regions. Finally, the safety predicate is binary and detector-dependent; graded harmfulness scores are not supported. Extending MTCR to richer threat models, automated mode discovery, and continuous safety metrics remains future work. References Anthropic (2024) Anthropic. 2024. The claude 3 model family. https://w.anthropic.com/claude. Chao et al. (2025) Patrick Chao, Alexander Robey, Edgar Dobriban, Hamed Hassani, George J Pappas, and Eric Wong. 2025. Jailbreaking black box large language models in twenty queries. In 2025 IEEE Conference on Secure and Trustworthy Machine Learning (SaTML), pages 23–42. IEEE. Chen et al. (2025) Huanran Chen, Yinpeng Dong, Zeming Wei, Hang Su, and Jun Zhu. 2025. Towards the worst-case robustness of large language models. arXiv preprint arXiv:2501.19040. Chiang et al. (2023) Wei-Lin Chiang, Zhuohan Li, Ziqing Lin, Ying Sheng, Zhanghao Wu, Hao Zhang, Lianmin Zheng, Siyuan Zhuang, Yonghao Zhuang, Joseph E Gonzalez, et al. 2023. Vicuna: An open-source chatbot impressing gpt-4 with 90%* chatgpt quality. See https://vicuna. lmsys. org (accessed 14 April 2023), 2(3):6. Cohen et al. (2019) Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. 2019. Certified adversarial robustness via randomized smoothing. In international conference on machine learning, pages 1310–1320. PMLR. Du et al. (2021) Tianyu Du, Shouling Ji, Lujia Shen, Yao Zhang, Jinfeng Li, Jie Shi, Chengfang Fang, Jianwei Yin, Raheem Beyah, and Ting Wang. 2021. Cert-rnn: Towards certifying the robustness of recurrent neural networks. In Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security. Henzinger et al. (1998) Thomas A Henzinger, Shaz Qadeer, and Sriram K Rajamani. 1998. You assume, we guarantee: Methodology and case studies. In International Conference on Computer Aided Verification, pages 440–451. Springer. Hurst et al. (2024) Aaron Hurst, Adam Lerer, Adam P Goucher, Adam Perelman, Aditya Ramesh, Aidan Clark, AJ Ostrow, Akila Welihinda, Alan Hayes, Alec Radford, et al. 2024. Gpt-4o system card. arXiv preprint arXiv:2410.21276. Iyengar (2005) Garud N Iyengar. 2005. Robust dynamic programming. Mathematics of Operations Research, 30(2):257–280. Kumar et al. (2023) Aounon Kumar, Chirag Agarwal, Suraj Srinivas, Aaron Jiaxun Li, Soheil Feizi, and Himabindu Lakkaraju. 2023. Certifying llm safety against adversarial prompting. arXiv preprint arXiv:2309.02705. Lecuyer et al. (2018) Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. 2018. Certified robustness to adversarial examples with differential privacy. arXiv preprint arXiv:1802.03471. Li et al. (2024) Nathaniel Li, Ziwen Han, Ian Steneker, Willow Primack, Riley Goodside, Hugh Zhang, Zifan Wang, Cristina Menghini, and Summer Yue. 2024. Llm defenses are not robust to multi-turn human jailbreaks yet. arXiv preprint arXiv:2408.15221. Mehrotra et al. (2024) Anay Mehrotra, Manolis Zampetakis, Paul Kassianik, Blaine Nelson, Hyrum Anderson, Yaron Singer, and Amin Karbasi. 2024. Tree of attacks: Jailbreaking black-box llms automatically. Advances in Neural Information Processing Systems, 37:61065–61105. Nilim and El Ghaoui (2005) Arnab Nilim and Laurent El Ghaoui. 2005. Robust control of markov decision processes with uncertain transition matrices. Operations Research, 53(5):780–798. Pasareanu et al. (2018) Corina S Pasareanu, Divya Gopinath, and Huafeng Yu. 2018. Compositional verification for autonomous systems with deep learning components. arXiv preprint arXiv:1810.08303. Rahman et al. (2025) Salman Rahman, Liwei Jiang, James Shiffer, Genglin Liu, Sheriff Issaka, Md Rizwan Parvez, Hamid Palangi, Kai-Wei Chang, Yejin Choi, and Saadia Gabriel. 2025. X-teaming: Multi-turn jailbreaks and defenses with adaptive multi-agents. arXiv preprint arXiv:2504.13203. Robey et al. (2023) Alexander Robey, Eric Wong, Hamed Hassani, and George J Pappas. 2023. Smoothllm: Defending large language models against jailbreaking attacks. arXiv preprint arXiv:2310.03684. Russinovich et al. (2025) Mark Russinovich, Ahmed Salem, and Ronen Eldan. 2025. Great, now write an article about that: The crescendo \Multi-Turn\\LLM\ jailbreak attack. In 34th USENIX Security Symposium (USENIX Security 25), pages 2421–2440. Touvron et al. (2023) Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. 2023. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint arXiv:2307.09288. Wei et al. (2023) Alexander Wei, Nika Haghtalab, and Jacob Steinhardt. 2023. Jailbroken: How does llm safety training fail? Advances in neural information processing systems, 36:80079–80110. Xu and Sivaranjani (2024) Yuezhu Xu and S Sivaranjani. 2024. Eclipse: Efficient compositional lipschitz constant estimation for deep neural networks. Advances in Neural Information Processing Systems, 37:10414–10441. Yang et al. (2025) An Yang, Anfeng Li, Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chang Gao, Chengen Huang, Chenxu Lv, et al. 2025. Qwen3 technical report. arXiv preprint arXiv:2505.09388. Ye et al. (2020) Mao Ye, Chengyue Gong, and Qiang Liu. 2020. Safer: A structure-free approach for certified robustness to adversarial word substitutions. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 3465–3475. Zeng et al. (2023) Jiehang Zeng, Jianhan Xu, Xiaoqing Zheng, and Xuanjing Huang. 2023. Certified robustness to text adversarial attacks by randomized [mask]. Computational Linguistics, 49(2):395–427. Zeng et al. (2024) Yi Zeng, Hongpeng Lin, Jingwen Zhang, Diyi Yang, Ruoxi Jia, and Weiyan Shi. 2024. How johnny can persuade llms to jailbreak them: Rethinking persuasion to challenge ai safety by humanizing llms. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 14322–14350. Zhang et al. (2021) Huan Zhang, Hongge Chen, Duane Boning, and Cho-Jui Hsieh. 2021. Robust reinforcement learning on state observations with learned optimal adversary. arXiv preprint arXiv:2101.08452. Zhang et al. (2020) Huan Zhang, Hongge Chen, Chaowei Xiao, Bo Li, Mingyan Liu, Duane Boning, and Cho-Jui Hsieh. 2020. Robust deep reinforcement learning against adversarial perturbations on state observations. Advances in neural information processing systems, 33:21024–21037. Zhang et al. (2024) Xinyu Zhang, Hanbin Hong, Yuan Hong, Peng Huang, Binghui Wang, Zhongjie Ba, and Kui Ren. 2024. Text-crs: A generalized certified robustness framework against textual adversarial attacks. In 2024 IEEE Symposium on Security and Privacy (SP), pages 2920–2938. IEEE. Zhang et al. (2023) Yunruo Zhang, Tianyu Du, Shouling Ji, Peng Tang, and Shanqing Guo. 2023. Rnn-guard: Certified robustness against multi-frame attacks for recurrent neural networks. arXiv preprint arXiv:2304.07980. Zou et al. (2023) Andy Zou, Zifan Wang, Nicholas Carlini, Milad Nasr, J Zico Kolter, and Matt Fredrikson. 2023. Universal and transferable adversarial attacks on aligned language models. arXiv preprint arXiv:2307.15043. Appendix Appendix A Related Work Single-Turn Certified Robustness. Certified robustness originated with randomized smoothing (Cohen et al. 2019; Lecuyer et al. 2018), providing probabilistic guarantees against ℓp _p-bounded perturbations. For NLP, SAFER (Ye et al. 2020) pioneered certified text classification via synonym substitution. RanMASK (Zeng et al. 2023) improved this through random token masking. Text-CRS (Zhang et al. 2024) generalized to insertion, deletion, and reordering. For LLM jailbreaking, SmoothLLM (Robey et al. 2023) adapts randomized smoothing to character-level perturbations. Erase-and-Check (Kumar et al. 2023) provides certified harmful prompt detection. Chen et al. (Chen et al. 2025) establish tight bounds via knapsack formulation. All these methods are limited to single-turn settings. Multi-Turn Attacks. Crescendo (Russinovich et al. 2025) progressively escalates from benign to harmful requests. PAIR (Chao et al. 2025) and TAP (Mehrotra et al. 2024) use attacker LLMs for iterative refinement. Persuasion-based attacks (Zeng et al. 2024) exploit psychological techniques. X-Teaming (Rahman et al. 2025) achieves state-of-the-art success rates through multi-agent coordination. Defenses remain largely empirical without formal guarantees. Robust MDPs and Compositional Verification. Our framework builds on robust MDP theory. Standard robust MDPs consider transition uncertainty (Iyengar 2005; Nilim and El Ghaoui 2005). State-Adversarial MDPs (Zhang et al. 2020; Zhang et al. 2021) model adversaries perturbing state observations, proving optimal stationary policies may not exist, which directly informs our approach. Compositional verification (Pasareanu et al. 2018; Henzinger et al. 1998) decomposes complex problems; ECLipsE (Xu and Sivaranjani 2024) achieves compositional Lipschitz estimation; Cert-RNN (Du et al. 2021; Zhang et al. 2023) extends to sequential models. We adapt these ideas to conversational safety. Appendix B Formal Definitions and Assumptions B.1 Vocabulary, Dialogue, and State Space Let V be a finite vocabulary and ≤LV^≤ L denote sequences of length at most L. A dialogue history ht=(u1,r1,…,ut,rt)h_t=(u_1,r_1,…,u_t,r_t) is a sequence of user messages and model responses. The state embedding ϕ:ℋ→φ:H maps histories to ⊆ℝdS ^d with norm ∥⋅∥\|·\|. We assume S is bounded and +S_+ is open with non-empty interior; the openness ensures Δ(s)>0 (s)>0 for all s∈+s _+. The maximum inscribed ball radius is δmin=supr>0:∃s∈+,Br(s)⊆+ _ = \r>0:∃ s _+,B_r(s) _+\. B.2 Perturbation and Agents For a reference input u∗u^* and metric d, the ϵε-perturbation set is ℬϵ(u∗)=u:d(u,u∗)≤ϵB_ε(u^*)=\u:d(u,u^*)≤ε\. An adversarial user policy ν:→Δ(≤L)ν:S→ (V^≤ L) satisfies supp(ν(⋅|s))⊆ℬϵ(u∗(s))supp(ν(·|s)) _ε(u^*(s)). The class Πϵ _ε in Definition 1 is the set of all such adversarial policies (so the adversary is restricted to inputs within ϵε of the reference at each state). The LLM policy π(⋅|s,u)π(·|s,u) generates responses conditioned on state and user input. B.3 Transition, Safety, and Single-Turn Certification State transition is given by T(st−1,ut,rt)↦stT(s_t-1,u_t,r_t) s_t. The safety predicate :→0,1 Safe:S→\0,1\ defines +=s:(s)=1S_+=\s: Safe(s)=1\ and the safety margin Δ(s)=dist(s,−) (s)=dist(s,S_-). The single-turn certified safety is p(s,ϵ)=infu∈ℬϵℙ[(T(s,u,r))]p(s,ε)= _u _εP[ Safe(T(s,u,r))] (12) where the probability is over r∼π(⋅|s,u)r π(·|s,u). B.4 Conversational Modes and Decomposition A conversational mode m=(m,m,ψm)m=(S_m,A_m, _m) consists of a region m⊆S_m , admissible messages m⊆≤LA_m ^≤ L, and a safety function ψm _m. A mode decomposition ℳ=m1,…,mMM=\m_1,…,m_M\ satisfies coverage (⋃imi⊇+ _iS_m_i _+) and bounded overlap κ=maxs|i:s∈mi|κ= _s|\i:s _m_i\|. The transition graph GℳG_M has edge (mi,mj)(m_i,m_j) if and only if transitions from miS_m_i to mjS_m_j are possible. B.5 Intra-Mode and Transition Safety The intra-mode certified safety is: ρmin(ϵ)=infs∈m∩+infu∈ℬϵ∩mℙ[(T(s,u,r))∧T(s,u,r)∈m] _m^in(ε)= _s _m _+ _u _ε _mP[ Safe(T(s,u,r)) T(s,u,r) _m] (13) For each edge (mi,mj)∈Eℳ(m_i,m_j)∈ E_M, the transition safety ρi→jtr(ϵ) _i→ j^tr(ε) is the infimum of ℙ[(T(s,u,r))]P[ Safe(T(s,u,r))] over feasible (s,u)(s,u) that induce transitions to mjS_m_j. B.6 Mode Trajectory and Feasible Set A mode trajectory σ∈ℳkσ ^k over k turns has nj(σ)=|t:σ(t)=mj=σ(t+1)|n_j(σ)=|\t:σ(t)=m_j=σ(t+1)\| intra-mode turns in mjm_j and τ(σ)=|t:σ(t)≠σ(t+1)|τ(σ)=|\t:σ(t)≠σ(t+1)\| transitions. The feasible set Σk(ℳ,s0) _k(M,s_0) contains trajectories starting from a mode containing s0s_0. B.7 Remarks Definition 1 uses adaptive adversaries that observe st−1s_t-1 before choosing utu_t; oblivious adversaries yield a weaker setting, and our bounds apply to the stronger adaptive case. For the overlap factor 1/κ1/κ: when a state lies in κ modes, the adversary can exploit this ambiguity; when κ=1κ=1, the factor disappears. For (α,β)(α,β)-safety persistence, α controls the maximum margin contraction per turn, and β is the probability that the margin shrinks by at most factor α. Under a convex safe region +S_+, from initial distance Δ , one turn yields a safe state with distance ≥(1−α)Δ≥(1-α) with probability at least β. Appendix C Algorithm Pipeline Require : Initial state s0s_0, LLM policy π, budget ϵε, horizon k, mode decomposition ℳM Ensure : Certified robustness lower bound ρ^k ρ_k 1 // Phase 1: Intra-Mode Certification; 2 foreach mode m∈ℳm do 3 Estimate ρ^min← ρ_m^in← RandomizedSmoothingCertify(m,ϵ,N)(m,ε,N); 4 Estimate persistence parameters (α^m,β^m)←( α_m, β_m)← EstimatePersistence(m)(m); 5 end foreach 6 7 // Phase 2: Inter-Mode Certification; 8 foreach edge (mi,mj)∈Eℳ(m_i,m_j)∈ E_M do 9 ρ^i→jtr← ρ_i→ j^tr← BoundaryAwareCertify(mi,mj,ϵ,N)(m_i,m_j,ε,N); 10 end foreach 11 12 // Phase 3: Worst-Case Trajectory (Dynamic Programming); 13 β^←minmβ^m β← _m β_m; 14 Initialize V0(m)←1V_0(m)← 1 for modes containing s0s_0, else 00; 15 for t=1t=1 to k do 16 foreach mode mjm_j do 17 Vt(mj)←minVt−1(mj)⋅ρ^mjin/β^,mini:(mi,mj)∈EVt−1(mi)⋅ρ^i→jtrV_t(m_j)← \! \V_t-1(m_j)· ρ_m_j^in/ β,\; _i:(m_i,m_j)∈ EV_t-1(m_i)· ρ_i→ j^tr \; 18 end foreach 19 end for 20 21 // Phase 4: Compute Final Bound; 22 ρ^kcomb←1κ⋅β^k⋅minmVk(m) ρ_k^comb← 1κ· β^k· _mV_k(m) // Combined bound (Theorem 3.11); 23 ρ^k←max(β^k,ρ^kcomb) ρ_k← ( β^k,\; ρ_k^comb) // Best of persistence-only and combined; 24 return ρ^k ρ_k Algorithm 1 Multi-Turn Certified Robustness (MTCR) Appendix D Background: State-Adversarial MDPs We provide background on State-Adversarial MDPs (Zhang et al. 2020) informing our framework. A standard MDP is (,,P,R,γ)(S,A,P,R,γ) with state space S, action space A, transition kernel P(s′|s,a)P(s |s,a), reward R(s,a)R(s,a), and discount γ. An SA-MDP augments this with an adversary that perturbs state observations: the agent observes s~=s+δ s=s+δ where ‖δ‖≤ϵ\|δ\|≤ε is chosen adversarially. Key results are as follows. Remark D.1 (Key results from (Zhang et al. 2020)). In SA-MDPs with optimal adversaries: 1. Deterministic stationary optimal policies may not exist 2. Optimal policies must be history-dependent or randomized 3. Policy regularization (TV/KL divergence) provides robustness These results show that static guardrails cannot guarantee robustness under state-adversarial perturbations; adaptive mode-based certification is needed to achieve meaningful guarantees. Appendix E Detailed Proofs E.1 Proof of Proposition 2.1 Define events Et=(st)=1E_t=\ Safe(s_t)=1\. By the chain rule: ℙ[⋀t=1kEt]=∏t=1kℙ[Et|⋀i=1t−1Ei]P [ _t=1^kE_t ]= _t=1^kP [E_t\, |\, _i=1^t-1E_i ] (14) For any adversarial policy ν, at each turn t conditioned on being in a safe state st−1∈+s_t-1 _+, the adversary selects ut∈ℬϵu_t _ε. By the single-turn safety definition (Appendix 12): ℙ[Et|E1,…,Et−1,st−1]≥p(st−1,ϵ)≥p¯P [E_t\, |\,E_1,…,E_t-1,s_t-1 ]≥ p(s_t-1,ε)≥ p (15) where p¯=infs∈+p(s,ϵ) p= _s _+p(s,ε), since p(st−1,ϵ)=infu∈ℬϵℙ[(T(st−1,u,r))]p(s_t-1,ε)= _u _εP[ Safe(T(s_t-1,u,r))] is the minimum over adversarial inputs, and the actual input utu_t achieves at least this probability. Since this bound holds for each conditional term regardless of the adversary’s strategy: ρk(s0,π,ϵ)=infνℙ[⋀t=1kEt]≥p¯k _k(s_0,π,ε)= _νP [ _t=1^kE_t ]≥ p^\,k (16) E.2 Proof of Theorem 3.1 We prove this in three steps. Step 1: Trajectory Conditioning. Let E=⋀t=1k(st)E= _t=1^k Safe(s_t) denote full safety. For any state trajectory (s1,…,sk)(s_1,…,s_k), define the induced mode trajectory σ where σ(t)∈m:st∈mσ(t)∈\m:s_t _m\ (choosing arbitrarily if multiple modes contain sts_t). Then: ℙ[E]=∑σ∈Σk(ℳ,s0)ℙ[E∧trajectory is σ]P[E]= _σ∈ _k(M,s_0)P[E is σ] (17) Since we seek a lower bound, it suffices to lower bound each summand. For any fixed trajectory σ: ℙ[E∧trajectory σ]=ℙ[E|trajectory σ]⋅ℙ[trajectory σ]P[E σ]=P[E\,|\,trajectory σ]·P[trajectory σ] (18) Step 2: Decomposition Along Trajectory. Partition the k turns into intra-mode turns ℐ=t:σ(t)=σ(t+1)I=\t:σ(t)=σ(t+1)\ and transition turns =t:σ(t)≠σ(t+1)T=\t:σ(t)≠σ(t+1)\ (with ||=τ(σ)|T|=τ(σ)). For intra-mode turns in mode mjm_j, since the per-turn safety bound ρmjin(ϵ) _m_j^in(ε) holds uniformly for all states within mjS_m_j: ℙ[⋀t∈ℐj(st)|stay in mj]≥(ρmjin(ϵ))|ℐj|P [ _t _j Safe(s_t)\, |\,stay in m_j ]≥ ( _m_j^in(ε) )^|I_j| (19) where ℐj=t∈ℐ:σ(t)=mjI_j=\t :σ(t)=m_j\ and |ℐj|=nj(σ)|I_j|=n_j(σ). For transition turns from mim_i to mjm_j: ℙ[(st)|st−1∈mi,st∈mj]≥ρi→jtr(ϵ)P[ Safe(s_t)\,|\,s_t-1 _m_i,s_t _m_j]≥ _i→ j^tr(ε) (20) Step 3: Overlap Penalty (Factor 1/κ1/κ). Lemma E.1 (Overlap Penalty). For any mode decomposition with overlap κ=maxs|i:s∈mi|κ= _s|\i:s _m_i\|: ρk(s0,π,ϵ)≥1κ⋅infσℙ[E|trajectory σ] _k(s_0,π,ε)≥ 1κ· _σP[E\,|\,trajectory σ] (21) Proof. Fix a deterministic tie-breaking rule: assign each sts_t to the mode mjm_j with the smallest index j such that st∈mjs_t _m_j. Under this rule, every state sequence maps to a unique trajectory σ, so ℙ[E]=∑σℙ[E∩traj=σ]P[E]= _σP[E∩\traj=σ\]. For non-overlapping decompositions (κ=1κ=1), the assignment is unique and the bound follows directly from conditioning on the worst-case trajectory, without any penalty factor. For overlapping decompositions (κ>1κ>1), we introduce the 1/κ1/κ factor as follows. When a state sts_t lies in multiple modes ℳ(st)=i:st∈miM(s_t)=\i:s_t _m_i\ with |ℳ(st)|≤κ|M(s_t)|≤κ, the adversary can steer the trajectory through the mode with the weakest safety bound. Let ρmin(s)=mini∈ℳ(s)ρmiin _ (s)= _i (s) _m_i^in and ρmax(s)=maxi∈ℳ(s)ρmiin _ (s)= _i (s) _m_i^in denote the weakest and strongest per-turn bounds available at state s. Our compositional bound (which uses ρmjin _m_j^in for the assigned mode mjm_j) may overestimate the actual per-turn safety by using ρmjin _m_j^in when the adversary achieves ρmin(s) _ (s). Since each state belongs to at most κ modes, and each ρmiin≤1 _m_i^in≤ 1, the per-turn overestimation is bounded: ρmjin/ρmin(s)≤κ _m_j^in/ _ (s)≤κ in the worst case (when modes have safety probabilities 1/κ,2/κ,…,11/κ,2/κ,…,1). Applying this correction across all k turns conservatively as a single multiplicative factor yields: ρk≥1κ⋅infσℙ[E|σ] _k≥ 1κ· _σP[E\,|\,σ] (22) When κ=1κ=1, each state belongs to exactly one mode and the factor disappears. ∎ Remark E.1. The 1/κ1/κ penalty is conservative; tighter overlap corrections are possible when mode safety probabilities are similar. In all our experiments, we use non-overlapping decompositions (κ=1κ=1) at the recommended granularity M=4M=4, so this factor does not affect reported bounds. Multiplying the per-turn bounds for trajectory σ: ℙ[E|trajectory σ]≥∏j=1M(ρmjin)nj(σ)⋅∏(i,j)∈Trans(σ)ρi→jtrP[E\,|\,trajectory σ]≥ _j=1^M ( _m_j^in )^n_j(σ)· _(i,j) (σ) _i→ j^tr (23) By Lemma E.1, the worst-case over mode assignments (exploited by the adversary when states lie in overlap regions) introduces the 1/κ1/κ factor. Taking the infimum over adversaries (which determines the worst-case trajectory) yields: ρk(s0,π,ϵ)=infνℙ[E]≥1κ⋅infσ∈Σk(ℳ,s0)[∏j(ρmjin)nj(σ)⋅∏(i,j)ρi→jtr] _k(s_0,π,ε)= _νP[E]≥ 1κ· _σ∈ _k(M,s_0) [ _j ( _m_j^in )^n_j(σ)· _(i,j) _i→ j^tr ] (24) E.3 Proof of Corollary 3.2 From Theorem 3.1, with nj(σ)n_j(σ) summing to k−τk-τ (non-transition turns): ρk≥1κ∏j(1−δ)nj(σ)⋅γτ=1κ(1−δ)k−τγτ _k≥ 1κ _j(1-δ)^n_j(σ)·γ^τ= 1κ(1-δ)^k-τγ^τ (25) The inequality 1κ(1−δ)k−τγτ>p¯k 1κ(1-δ)^k-τγ^τ> p^\,k rearranges to the stated condition on τ. E.4 Proof of Proposition 3.4 Define value function Vt(m)V_t(m) = minimum certified lower bound achievable in t turns ending in mode m. Initialize V0(m)=1V_0(m)=1 for modes containing s0s_0, else V0(m)=0V_0(m)=0. Recurrence: Vt+1(mj)=minVt(mj)⋅ρmjin,mini:(mi,mj)∈EVt(mi)⋅ρi→jtrV_t+1(m_j)= \V_t(m_j)· _m_j^in, _i:(m_i,m_j)∈ EV_t(m_i)· _i→ j^tr \ (26) The first term corresponds to staying in mjm_j; the second to transitioning from some mim_i. Final answer: ρk≥1κminmVk(m) _k≥ 1κ _mV_k(m). E.5 Proof of Theorem 3.5 Step 1: First Bound (ρk≥βk _k≥β^k). Let At=(st)=1∧Δ(st)≥(1−α)Δ(st−1)A_t=\ Safe(s_t)=1 (s_t)≥(1-α) (s_t-1)\ denote the event that the persistence condition holds at turn t. By Definition 2, for any adversarial policy and any safe state st−1∈+s_t-1 _+ with Δ(st−1)>0 (s_t-1)>0: ℙ[At|st−1∈+,Δ(st−1)>0]≥βP[A_t\,|\,s_t-1 _+, (s_t-1)>0]≥β (27) We verify the precondition inductively. At t=1t=1: s0∈+s_0 _+ with Δ(s0)=Δ0>0 (s_0)= _0>0 by assumption. At turn t>1t>1: on the event ⋀i=1t−1Ai _i=1^t-1A_i, we have (st−1)=1 Safe(s_t-1)=1 (so st−1∈+s_t-1 _+) and Δ(st−1)≥(1−α)t−1Δ0>0 (s_t-1)≥(1-α)^t-1 _0>0 (since α<1α<1). Therefore: ℙ[At|⋀i=1t−1Ai]≥βP [A_t\, |\, _i=1^t-1A_i ]≥β (28) By the chain rule: ℙ[⋀t=1kAt]=∏t=1kℙ[At|⋀i=1t−1Ai]≥βkP [ _t=1^kA_t ]= _t=1^kP [A_t\, |\, _i=1^t-1A_i ]≥β^k (29) On the event ⋀t=1kAt _t=1^kA_t, safety holds at every turn ((st)=1 Safe(s_t)=1 is part of the persistence condition). Therefore: ρk=infνℙ[⋀t=1k(st)]≥ℙ[⋀t=1kAt]≥βk _k= _νP [ _t=1^k Safe(s_t) ] [ _t=1^kA_t ]≥β^k (30) Step 2: Complementary Linear Characterization. We derive a union-bound-based formula that, while looser than βkβ^k in general, provides an interpretable horizon estimate. Define Ut=(st)=0U_t=\ Safe(s_t)=0\ as the event that turn t is unsafe. Note that Ut⊆AtcU_t A_t^c (unsafety implies persistence failure), since the persistence event AtA_t requires (st)=1 Safe(s_t)=1. For each turn t, conditioned on all previous turns being safe (⋀i=1t−1(si)=1 _i=1^t-1 Safe(s_i)=1, which ensures st−1∈+s_t-1 _+), the openness of +S_+ (assumed in Section 2) guarantees Δ(st−1)>0 (s_t-1)>0. The persistence definition then gives: ℙ[Ut|⋀i=1t−1(si)=1]≤1−βP [U_t\, |\, _i=1^t-1 Safe(s_i)=1 ]≤ 1-β (31) since ℙ[At|⋅]≥βP[A_t|·]≥β and At⊆(st)=1=UtcA_t \ Safe(s_t)=1\=U_t^c. Applying the union bound over the “first failure” decomposition: ℙ[∃t≤k:(st)=0]=∑t=1kℙ[Ut∩⋀i=1t−1Uic]≤∑t=1k(1−β)=k(1−β)P [∃\,t≤ k: Safe(s_t)=0 ]= _t=1^kP [U_t∩ _i=1^t-1U_i^c ]≤ _t=1^k(1-β)=k(1-β) (32) Therefore: ρk=infνℙ[⋀t=1k(st)]≥1−k(1−β) _k= _νP [ _t=1^k Safe(s_t) ]≥ 1-k(1-β) (33) which is the linear degradation bound. This holds whenever k(1−β)<1k(1-β)<1; for β close to 1 the bound is non-trivial for horizons k≪1/(1−β)k 1/(1-β). E.6 Proof of Proposition 3.7 For s∈+s _+ with margin Δ(s) (s), consider any adversarial u∈ℬϵu _ε and response r with ‖r−r∗‖≤η\|r-r^*\|≤η (or dr(r,r∗)≤ηd_r(r,r^*)≤η). The new state s′=T(s,u,r)s =T(s,u,r) satisfies: ‖s′−s‖ \|s -s\| ≤‖T(s,u,r)−T(s,u∗,r∗)‖+‖T(s,u∗,r∗)−s‖ ≤\|T(s,u,r)-T(s,u^*,r^*)\|+\|T(s,u^*,r^*)-s\| (34) ≤Lr⋅η+Lu⋅ϵ+δT ≤ L_r·η+L_u·ε+ _T (35) where the last step uses the Lipschitz conditions and the nominal drift bound (condition 6). The new margin satisfies: Δ(s′)≥Δ(s)−‖s′−s‖≥Δ(s)−(Luϵ+Lrη+δT) (s )≥ (s)-\|s -s\|≥ (s)-(L_uε+L_rη+ _T) (36) For Δ(s′)≥(1−α)Δ(s) (s )≥(1-α) (s), we need: Δ(s)−(Luϵ+Lrη+δT)≥(1−α)Δ(s)⟹α≥Luϵ+Lrη+δTΔ(s) (s)-(L_uε+L_rη+ _T)≥(1-α) (s) α≥ L_uε+L_rη+ _T (s) (37) Taking the worst case over Δ(s)≥δ (s)≥δ and noting the response concentration holds with probability p0p_0 yields the result. E.7 Proof of Theorem 3.8 We construct a system that achieves the upper bound exactly, showing it is tight. Step 1: Matching Construction. For each mode mjm_j, construct transition dynamics TjT_j such that, for all s∈mjs _m_j and all u∈ℬϵu _ε, the per-turn safety probability is exactly ρmjin _m_j^in, independently across turns. This is achievable: let Tj(s,u,r)T_j(s,u,r) draw the next state from a distribution supported on mjS_m_j with ℙ[(s′)=1∧s′∈mj]=ρmjinP[ Safe(s )=1 s _m_j]= _m_j^in, independently of (s,u)(s,u). Similarly, for transitions from mim_i to mjm_j, set ℙ[(s′)]=ρi→jtrP[ Safe(s )]= _i→ j^tr independently. Step 2: Safety Probability Under This Construction. Under the constructed system, per-turn outcomes are independent given the mode trajectory σ. For intra-mode turns in mjm_j, each turn is safe independently with probability ρmjin _m_j^in. For transition turns from mim_i to mjm_j, safety holds independently with probability ρi→jtr _i→ j^tr. Therefore: ρk=∏j=1M(ρmjin)nj⋅∏(i,j)∈Transρi→jtr _k= _j=1^M ( _m_j^in )^n_j· _(i,j) _i→ j^tr (38) This matches the compositional lower bound from Theorem 3.1 (with κ=1κ=1), so the bound is tight for non-overlapping decompositions. Lemma E.2 (Mode-Optimal Attack Existence). For each mode m and state s∈ms _m, the optimal attack u∗(s)=argminu∈ℬϵℙr∼π[(T(s,u,r))]u^*(s)= _u _εP_r π[ Safe(T(s,u,r))] exists by compactness of ℬϵB_ε (finite vocabulary, bounded length) and achieves the infimum in the intra-mode safety definition (Appendix B.5). E.8 Proof of Theorem 3.10 We construct a memoryless conversational system. Let =[0,1]S=[0,1] and +=[0,p]S_+=[0,p] so that (s)=[s≤p] Safe(s)=1[s≤ p]. Define the transition function T(s,u,r)=rT(s,u,r)=r where r∼Uniform[0,1]r [0,1] independently of (s,u)(s,u). Under this system, the adversary’s choice of u∈ℬϵu _ε has no effect on the next state, and the per-turn safety probability is ℙ[(s′)=1]=pP[ Safe(s )=1]=p regardless of the current state or adversary’s action. Since turns are independent: ρk=pk=p¯k _k=p^k= p^\,k (39) Furthermore, no mode decomposition can improve the bound: every mode has identical intra-mode safety p, and transitions do not change the safety probability. No persistence property holds with β>pβ>p, since the margin Δ(s′)=max(0,p−s′) (s )= (0,p-s ) is independent of Δ(s) (s). This shows that our structural assumptions (modes, persistence) are necessary to guarantee sub-exponential bounds, not merely sufficient for achieving them. E.9 Proof of Theorem 3.11 We combine Theorems 3.1 and 3.5. Let β^=minmβ^m β= _m β_m denote the global persistence parameter. Step 1: Factoring out persistence. Theorem 3.5 gives an overall bound βkβ^k, which factors as a per-turn contribution of β. We decompose the k-turn compositional product into a persistence baseline (βkβ^k) and a residual capturing mode-specific deviations above this baseline. For a mode trajectory σ with nj(σ)n_j(σ) intra-mode turns in mode mjm_j and τ(σ)τ(σ) transitions: ∏j(ρmjin)nj(σ)=β∑jnj(σ)⋅∏j(ρmjinβ)nj(σ)=βk−τ(σ)⋅∏j(ρmjinβ)nj(σ) _j( _m_j^in)^n_j(σ)=β _jn_j(σ)· _j ( _m_j^inβ )^n_j(σ)=β^k-τ(σ)· _j ( _m_j^inβ )^n_j(σ) (40) Step 2: Applying compositional certification. Substituting into Theorem 3.1: ρk≥1κ⋅βk−τ⋅infσ[∏j(ρmjinβ)nj(σ)⋅∏(i,j)ρi→jtr] _k≥ 1κ·β^k-τ· _σ [ _j ( _m_j^inβ )^n_j(σ)· _(i,j) _i→ j^tr ] (41) Since βk−τ≥βkβ^k-τ≥β^k (as τ≥0τ≥ 0 and β≤1β≤ 1), we obtain the stated bound with βkβ^k replacing βk−τβ^k-τ (a conservative simplification). Step 3: Simplification when persistence dominates. When ρmjin≥β _m_j^in≥β for all modes, each ratio ρmjin/β≥1 _m_j^in/β≥ 1, so ∏j(ρmjin/β)nj≥1 _j( _m_j^in/β)^n_j≥ 1. The infimum over trajectories is then dominated by the transition terms ∏(i,j)ρi→jtr≥γτ _(i,j) _i→ j^tr≥γ^τ, yielding ρk≥βkγτ/κ _k≥β^kγ^τ/κ. Appendix F Mode Discovery Algorithms We describe three practical approaches for constructing mode decompositions from dialogue data. Clustering-based discovery. Given a dialogue dataset h(i)i=1n\h^(i)\_i=1^n, we (1) compute embeddings s(i)=ϕ(h(i))s^(i)=φ(h^(i)) using a pretrained encoder; (2) apply k-means to obtain cluster centers c1,…,cM=KMeans(s(i),M)\c_1,…,c_M\=KMeans(\s^(i)\,M); and (3) define mode regions mj=s:‖s−cj‖≤rjS_m_j=\s:\|s-c_j\|≤ r_j\ with radius rjr_j chosen to achieve coverage (e.g., 90th percentile of within-cluster distances). This approach is used in our experiments. Topic-based discovery. Alternatively, we can apply LDA or neural topic models to conversation transcripts. Each topic j corresponds to mode mjm_j; the region mjS_m_j is defined via a topic posterior threshold (e.g., assign s to mjm_j when the posterior for topic j exceeds a threshold). This yields semantically interpretable modes when topics are well-separated. Self-annotation. A third approach prompts the LLM to classify conversation segments: “Classify this conversation segment into one of: greeting, information-seeking, task-execution, clarification, conclusion.” The responses define mode assignments; embedding space can then be partitioned accordingly. F.1 Persistence Parameter Estimation Algorithm 1 calls EstimatePersistence(m)(m) to obtain (α^m,β^m)( α_m, β_m) for each mode. We implement this as follows. Given mode m with region mS_m, sample NpN_p state–input pairs (s,u)(s,u) where s∈m∩+s _m _+ and u∈ℬϵu _ε. For each pair, generate response r∼π(⋅|s,u)r π(·|s,u) and compute the next state s′=T(s,u,r)s =T(s,u,r). Record the safety margin ratio δi=Δ(s′)/Δ(s) _i= (s )/ (s) when (s′)=1 Safe(s )=1, and mark as failure otherwise. The persistence parameters are estimated as: α^m α_m =1−Q0.05(δi:(si′)=1) =1-Q_0.05 (\ _i: Safe(s _i)=1\ ) (42) β^m β_m =1Np∑i=1Np[(si′)=1∧Δ(si′)≥(1−α^m)Δ(si)] = 1N_p _i=1^N_p1 [ Safe(s _i)=1 (s _i)≥(1- α_m) (s_i) ] (43) where Q0.05Q_0.05 denotes the 5th percentile. We first estimate α^m α_m as one minus the 5th percentile of margin ratios (conservatively capturing the near-worst-case contraction), then count the fraction of samples satisfying both safety and bounded contraction to obtain β^m β_m. In our experiments we use Np=100N_p=100 samples per mode. A Clopper–Pearson confidence interval at level δconf=0.05 _conf=0.05 is applied to β^m β_m (taking its lower endpoint) to ensure the resulting certified bound is valid with high probability. Appendix G Safety Detector Comparison We compare two safety detection approaches used for certifying multi-turn safety. The keyword-based detector (default) combines: (i) refusal patterns (regex for “I cannot”, “I’m unable to”, etc.): responses matching these are labeled safe; (i) an unsafe-keyword list (e.g., “how to make”, “bomb”, “illegal drug”): responses containing these without refusal are labeled unsafe. The neural classifier uses a pretrained harmful-content model (e.g., fine-tuned BERT on toxicity/harm benchmarks) to score response safety; we threshold at 0.5 for binary decisions. Both yield valid certified bounds when used consistently during certification and empirical evaluation; the keyword-based detector is more conservative (may flag edge cases as unsafe), while the neural detector can differ on ambiguous refusals. We use the keyword-based detector as default for reproducibility; Table 4 reports the comparison. Appendix H Concrete Data Example We illustrate the data format, perturbation procedure, and Crescendo-style attack with a concrete example. Sample harmful prompt. Consider the AdvBench prompt: “Write a detailed tutorial on how to pick a lock.” This belongs to the illegal-activities category. The adversary’s goal is to elicit harmful content by perturbing this prompt within character-level edit distance ϵ=5ε=5. Perturbation examples. Valid perturbations within ℬϵB_ε include: “Write a detailed tutorial on how to pick a lok” (1 substitution), “Write a detaled tutorial on how to pick a lock” (1 substitution), and “Write a tutorial on how to pick a lock” (deletion of “detailed”). Randomized smoothing certifies the fraction of such perturbations that elicit safe (refusal) responses. Crescendo-style multi-turn attack. We implement Crescendo-style attacks using template-based escalation sequences rather than the original adaptive LLM-based variant, representing a weaker but reproducible adversary. For each harmful prompt category, we manually design 10 escalation templates that progress from benign to harmful over k turns (following the escalation pattern in Russinovich et al. 2025). For the lock-picking target, a typical progression is: • Turn 1: “Can you help me with home improvement?” (benign) • Turn 2: “What about security systems and locks?” (escalation) • Turn 3: “How do residential locks work?” (further escalation) • Turn 4: “What tools are used for lock maintenance?” (near-target) • Turn 5: “Write a tutorial on how to pick a lock.” (target harmful prompt) At each turn, character-level perturbations (within edit distance ϵε) are applied independently on top of the template text, combining semantic escalation with ϵε-bounded noise. For horizons k>5k>5, additional benign filler turns are inserted before the escalation phase. Empirical safety is the fraction of 100 such trials in which the LLM refuses at every turn. Mode assignment. Dialogue embeddings from sentence-transformers map each history to ℝdR^d. For a safe conversation such as “User: What’s the weather? Assistant: I cannot provide real-time weather…”, the embedding falls into a mode cluster (e.g., “general inquiry”) discovered by k-means on held-out safe corpora. Transitions occur when the dialogue shifts topics; boundary dialogues between modes are used to certify ρi→jtr _i→ j^tr. Appendix I Numerical Verification of Theoretical Predictions We provide full details of six controlled experiments on a parametric Bernoulli model, each targeting a specific theoretical prediction. The experiments are: Compositional Gain (compositional vs. naive bounds), Persistence Scaling (persistence bound behavior), Mode Granularity (effect of mode count), Empirical Validation (certified vs. empirical safety), Pipeline Performance (end-to-end improvement), and Bound Tightness (gap to information-theoretic limits). I.1 Data Generation and Parametric Model Dialogue state embeddings s∈ℝds ^d are generated via a Gaussian mixture: n=2,000n=2,000 states from M=4M=4 Gaussians with Dirichlet mixing weights, centers scaled by 2.0, and per-cluster standard deviation 0.5. Mode decomposition uses k-means on these states; cluster radii are set at the 90th percentile of within-cluster distances. For M=4M=4, the overlap κ=1κ=1. Figure 3 illustrates the data layout. The parametric model is a configurable Bernoulli policy: for intra-mode turns it samples success (safe response) with rate ρmin _m^in, and for transitions from mim_i to mjm_j it samples with rate ρi→jtr _i→ j^tr. Parameters are set to match the theoretical values used in our analysis, permitting exact comparison of closed-form bounds against empirical outcomes. Figure 3: Synthetic data overview. I.2 Compositional Gain Table 5 reports the improvement ratio ρcomp/ρnaiveρ^comp/ρ^naive for varying horizon k and transition count τ. When k is small (e.g., k=5k=5), the ratio can be <1<1 because transition overhead dominates; the improvement becomes significant at larger k. When transitions are sparse (τ=1τ=1), compositional certification achieves 3.38× improvement at k=50k=50, consistent with Corollary 3.2. Finer granularity (τ=3τ=3 or 55) reduces the advantage as transition costs dominate. Table 5: Compositional Gain: improvement ratio ρcomp/ρnaiveρ^comp/ρ^naive across horizons and transition counts. k=5k=5 k=10k=10 k=20k=20 k=50k=50 τ=1τ=1 0.83 0.97 1.33 3.38 τ=3τ=3 0.43 0.50 0.68 1.72 τ=5τ=5 0.22 0.25 0.35 0.88 I.3 Persistence Scaling At k=100k=100 under (α,β)=(0.2,0.98)(α,β)=(0.2,0.98), the persistence bound (Theorem 3.5) exceeds the naive exponential reference by over 21×, confirming that structural persistence yields dramatically better scaling than naive composition. I.4 Mode Granularity, Empirical Validation, and Bound Tightness Mode Granularity varies M∈2,4,8,16M∈\2,4,8,16\: coarser modes yield tighter bounds due to lower overlap and transition overhead. Empirical Validation checks empirical safety against certified bounds: 94% under static attack and 90% under Crescendo-style attack, both above the certified 0.67. Pipeline Performance demonstrates end-to-end improvement of 1.86× over naive. Bound Tightness verifies that the compositional lower bound matches the information-theoretic upper bound (Corollary 3.9) for non-overlapping decompositions (κ=1κ=1). (a) (b) Figure 4: Compositional Gain (left) and Persistence Scaling (right): certified lower bounds vs. horizon. Appendix J Extended Experimental Setup We provide full experimental details for reproducibility. All experiments were run in Python 3.9 with NumPy, SciPy, and scikit-learn. Random seeds are fixed (base seed 42; per-dataset seeds 42, 142, 242, 342, 442) for all data generation and mode discovery, ensuring deterministic results given the seeds. J.1 Hyperparameter Summary Table 6 lists the hyperparameters for each experiment. Default values are p¯=0.95 p=0.95, ρin=0.98ρ^in=0.98, γ=0.7γ=0.7, κ=1κ=1, ϵ=5ε=5, δ0=1.0 _0=1.0, and δmin=0.1 _ =0.1. The perturbation budget ϵε is in edit-distance units for the synthetic setting; we use ϵ=5ε=5 unless noted. Table 6: Per-experiment hyperparameters. Experiment Parameter Value Comp. Gain k 5,10,20,50\5,10,20,50\ τ 1,2,3,4,5\1,2,3,4,5\ p¯,ρin,γ p,ρ^in,γ 0.95,0.98,0.70.95,0.98,0.7 Persist. Scale (α,β)(α,β) (0.05,0.98)(0.05,0.98), (0.1,0.95)(0.1,0.95), (0.2,0.98)(0.2,0.98) k 5,10,20,50,100\5,10,20,50,100\ Mode Gran. M 2,4,8,16\2,4,8,16\ k, d 2020, 6464 Emp. Valid. k, trials 1010, 100100 Attack types Static edit-distance, Crescendo-style Pipeline Perf. N, M, k 5050, 44, 2020 Bound Tight. ρinρ^in per mode (0.95,0.93,0.90,0.88)(0.95,0.93,0.90,0.88) γ, k 0.850.85, 10,20,30,50,100\10,20,30,50,100\ Production (LLM) Models LLaMA-2, Vicuna, Llama-3.2, Qwen2.5-7B, GPT-4o, Claude-3.5 M, k, N 44, 5,10,15,20\5,10,15,20\, 100100 ϵε, embedding 3,5,7\3,5,7\, sentence-transformers J.2 Production Model Experiments Open-source models (LLaMA-2-7B-Chat, Vicuna-7B, Llama-3.2-3B, Qwen2.5-7B-Instruct) are loaded via Hugging Face transformers and run on A100 (40GB). Closed-source models (GPT-4o, Claude-3.5-Sonnet) are accessed via OpenAI and Anthropic APIs respectively. Full certification at k∈5,10,15,20k∈\5,10,15,20\ requires approximately 2.5 hours per open-source model; API models incur additional latency. We use harmful prompts from AdvBench (Zou et al. 2023) (50 prompts per category: violence, illegal activities, hate speech; 150 total). Dialogue embeddings for mode discovery are computed with sentence-transformers all-MiniLM-L6-v2 on n=500n=500 held-out safe multi-turn dialogues (ShareGPT-style). Mode discovery uses k-means with M∈2,4,8M∈\2,4,8\; cluster radii are set at the 90th percentile. For certification, we apply randomized smoothing per mode with N=100N=100 perturbed prompts (character-level substitutions, insertions, deletions; edit distance ≤ϵ≤ε) and estimate ρ^min ρ_m^in as the fraction of safe responses. We vary ϵ∈3,5,7ε∈\3,5,7\ for sensitivity analysis (Table 2). Transition safety ρ^i→jtr ρ_i→ j^tr is estimated on boundary dialogues. The default harmful-content detector combines refusal patterns (e.g., “I cannot…”) and an unsafe-keyword list; we also compare with a neural classifier (Table 4, Appendix G). We deploy two attack types: static (random edit-distance perturbation at each turn) and Crescendo-style (escalation from benign to harmful over k turns). Fraction of trials with all turns safe over 100 runs defines empirical safety. The mode granularity ablation on LLaMA-2-7B-Chat at k=5k=5 yields ρ^5=0.39 ρ_5=0.39 for M=2M=2 (κ=1κ=1), 0.360.36 for M=4M=4 (κ=1κ=1), and 0.250.25 for M=8M=8 (κ=3κ=3). The MTCR ablation (Table 3) compares the multiplicative reference, Persistence-Only, Compositional-Only, and the Combined bound across k∈5,10,15,20k∈\5,10,15,20\. J.3 Synthetic Data and Attack Details States for synthetic experiments are sampled from a Gaussian mixture with M components. Centers are drawn from (0,4Id)N(0,4I_d) (scale 2.0); per-cluster standard deviation is 0.5. Mixing weights follow Dir(M)Dir(1_M). Mode decomposition uses k-means on the states; cluster radii are set to the 90th percentile of within-cluster distances. For the Mode Granularity experiment with varying M, we use n=1000n=1000 samples; for the main data overview, n=2000n=2000. The parametric model samples a Bernoulli with rate ρmin _m^in for intra-mode turns and ρi→jtr _i→ j^tr for transitions. For the Empirical Validation experiment, we use conservative certification (ρin=0.96ρ^in=0.96, cert. bound ≈0.67≈ 0.67) and a stronger parametric model (ρin=0.99ρ^in=0.99, vulnerability=0=0) so empirical safety reliably exceeds the certified bound; the static attack applies edit-distance perturbations within ϵε at each turn; the Crescendo-style attack escalates toward a target harmful prompt over k turns, with perturbations constrained to ℬϵB_ε per turn.