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

# Certified Multi-Turn Robustness for LLM Safety via Compositional Bounds and Safety Persistence
Source: [https://arxiv.org/html/2608.20820](https://arxiv.org/html/2608.20820)
Bin ChongAffiliation:Peking UniversityAffiliation:Corresponding author:chongbin@pku\.edu\.cnWenkai YangAffiliation:Renmin University of ChinaShuai ZhangAffiliation:Tsinghua UniversityYancheng ChenAffiliation:University of Chinese Academy of SciencesFeiyu HanAffiliation:University of Chinese Academy of SciencesGuoZhenAffiliation:Tencent HunyuanCheng ZhangAffiliation:Tencent HunyuanHuaibing XieAffiliation:Tencent HunyuanChangze LvAffiliation:Tencent HunyuanShihan DouAffiliation:Tencent HunyuanPluto ZhouAffiliation: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 introduceMulti\-Turn Certified Robustness \(MTCR\), a framework that models conversational safety via State\-Adversarial MDPs and defines*kk\-turn certified robustness*as the worst\-case safety probability acrosskkadversarial 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 fromp¯k\\underline\{p\}^\{\\,k\}toβk\\beta^\{k\}\(withβ\>p¯\\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\.

## 1Introduction

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](https://arxiv.org/html/2608.20820#bib.bib30);[Wei et al\. 2023](https://arxiv.org/html/2608.20820#bib.bib20)\)\. Although substantial progress has been made in defending against single\-turn attacks,multi\-turn jailbreak attacksthat progressively manipulate conversation context across multiple interactions pose a distinct challenge\([Russinovich et al\. 2025](https://arxiv.org/html/2608.20820#bib.bib18);[Li et al\. 2024](https://arxiv.org/html/2608.20820#bib.bib12)\)\.

Recent empirical studies reveal the severity of this threat\. The Crescendo attack\([Russinovich et al\. 2025](https://arxiv.org/html/2608.20820#bib.bib18)\)achieves near\-perfect success rates against production LLMs using fewer than 10 turns; X\-Teaming\([Rahman et al\. 2025](https://arxiv.org/html/2608.20820#bib.bib16)\)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](https://arxiv.org/html/2608.20820#bib.bib12)\)\. 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](https://arxiv.org/html/2608.20820#bib.bib17)\), erase\-and\-check\([Kumar et al\. 2023](https://arxiv.org/html/2608.20820#bib.bib10)\), knapsack\-based certification\([Chen et al\. 2025](https://arxiv.org/html/2608.20820#bib.bib3)\)\) 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 probabilitypp, thekk\-turn bound under multiplicative composition is merelypkp^\{k\}, which becomes negligible for moderatekk\. 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 developMulti\-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 definekk\-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](https://arxiv.org/html/2608.20820#S3.Thmtheorem2)\)\. A unified algorithm \(Algorithm[1](https://arxiv.org/html/2608.20820#algorithm1)\) combines compositional and persistence bounds to compute the certified guarantee in practice\.

\(2\)We formalize\(α,β\)\(\\alpha,\\beta\)\-safety persistence, a structural property under which the robustness bound improves fromp¯k\\underline\{p\}^\{\\,k\}toβk\\beta^\{k\}\(whenβ\>p¯\\beta\>\\underline\{p\}\), with a linear characterization1−k⁡\(1−β\)1\-k\(1\-\\beta\)that yields interpretable horizon estimates \(Theorem[3\.5](https://arxiv.org/html/2608.20820#S3.Thmtheorem5)\)\. 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ϵ\\epsilon\-bounded adversaries; empirical safety consistently exceeds the bound under both static \(ϵ\\epsilon\-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 boundp¯k\\underline\{p\}^\{\\,k\}degrades exponentially\.Center: MTCR combines compositional certification \(intra\-mode \+ transition safety\) with\(α,β\)\(\\alpha,\\beta\)\-persistence into a unified bound\.Right: Matching upper bounds establish tightness \(κ=1\\kappa\{=\}1\)\. Experiments on six LLMs confirm empirical safety exceeds the certified bounds\.

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

We model multi\-turn conversations as State\-Adversarial MDPs \(SA\-MDPs\)\. The dialogue historyht=\(u1,r1,…,ut,rt\)h\_\{t\}=\(u\_\{1\},r\_\{1\},\\ldots,u\_\{t\},r\_\{t\}\)maps to a conversational statest=ϕ⁡\(ht\)∈𝒮⊆ℝds\_\{t\}=\\phi\(h\_\{t\}\)\\in\\mathcal\{S\}\\subseteq\\mathbb\{R\}^\{d\}via an embeddingϕ\\phi\(e\.g\., LLM hidden representations\)\. An adversary selects user messagesutu\_\{t\}from anϵ\\epsilon\-perturbation ballℬϵ\\mathcal\{B\}\_\{\\epsilon\}around a reference input; the LLM responds according to policyπ\(⋅\|s,u\)\\pi\(\\cdot\|s,u\)\. States evolve asst=T⁡\(st−1,ut,rt\)s\_\{t\}=T\(s\_\{t\-1\},u\_\{t\},r\_\{t\}\)\. A safety predicate𝖲𝖺𝖿𝖾:𝒮→\{0,1\}\\mathsf\{Safe\}:\\mathcal\{S\}\\to\\\{0,1\\\}partitions the state space into a safe region𝒮\+\\mathcal\{S\}\_\{\+\}and an unsafe region𝒮−\\mathcal\{S\}\_\{\-\}, with safety marginΔ⁡\(s\)=dist⁡\(s,𝒮−\)\\Delta\(s\)=\\mathrm\{dist\}\(s,\\mathcal\{S\}\_\{\-\}\)\. We assume𝒮\\mathcal\{S\}is bounded,𝒮\+\\mathcal\{S\}\_\{\+\}is open \(soΔ⁡\(s\)\>0\\Delta\(s\)\>0for alls∈𝒮\+s\\in\\mathcal\{S\}\_\{\+\}\), and𝒮\+\\mathcal\{S\}\_\{\+\}has non\-empty interior withδmin\\delta\_\{\\min\}denoting the maximum inscribed ball radius\. Full formal definitions appear in Appendix[B](https://arxiv.org/html/2608.20820#A2)\.

###### Definition 1\(kk\-Turn Certified Robustness\)\.

Given initial states0∈𝒮\+s\_\{0\}\\in\\mathcal\{S\}\_\{\+\}, LLM policyπ\\pi, perturbation budgetϵ\\epsilon, and horizonk∈ℕk\\in\\mathbb\{N\}, thekk\-turn certified robustnessρk​\(s0,π,ϵ\)\\rho\_\{k\}\(s\_\{0\},\\pi,\\epsilon\)is:

infν∈Πϵℙut∼ν\(⋅\|st−1\)rt∼π\(⋅\|st−1,ut\)​\[⋀t=1k𝖲𝖺𝖿𝖾⁡\(st\)\|s0\],\\inf\_\{\\nu\\in\\Pi\_\{\\epsilon\}\}\\mathbb\{P\}\_\{\\begin\{subarray\}\{c\}u\_\{t\}\\sim\\nu\(\\cdot\|s\_\{t\-1\}\)\\\\ r\_\{t\}\\sim\\pi\(\\cdot\|s\_\{t\-1\},u\_\{t\}\)\\end\{subarray\}\}\\left\[\\bigwedge\_\{t=1\}^\{k\}\\mathsf\{Safe\}\(s\_\{t\}\)\\,\\bigg\|\\,s\_\{0\}\\right\],\(1\)where states evolve according tost=T⁡\(st−1,ut,rt\)s\_\{t\}=T\(s\_\{t\-1\},u\_\{t\},r\_\{t\}\)\.

The quantityρk​\(s0,π,ϵ\)\\rho\_\{k\}\(s\_\{0\},\\pi,\\epsilon\)captures the worst\-case probability of maintaining safety acrosskkturns against any adaptive adversary \(one that observesst−1s\_\{t\-1\}before choosingutu\_\{t\}\)\. A natural certification strategy is to compose single\-turn safety bounds multiplicatively\. For each statess, letp⁡\(s,ϵ\)=infu∈ℬϵℙ⁡\[𝖲𝖺𝖿𝖾⁡\(T⁡\(s,u,r\)\)\]p\(s,\\epsilon\)=\\inf\_\{u\\in\\mathcal\{B\}\_\{\\epsilon\}\}\\mathbb\{P\}\[\\mathsf\{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 anys0∈𝒮\+s\_\{0\}\\in\\mathcal\{S\}\_\{\+\}:

ρk​\(s0,π,ϵ\)≥\(infs∈𝒮\+p⁡\(s,ϵ\)\)k=p¯k,\\rho\_\{k\}\(s\_\{0\},\\pi,\\epsilon\)\\geq\\left\(\\inf\_\{s\\in\\mathcal\{S\}\_\{\+\}\}p\(s,\\epsilon\)\\right\)^\{k\}=\\underline\{p\}^\{\\,k\},\(2\)wherep¯=infs∈𝒮\+p⁡\(s,ϵ\)\\underline\{p\}=\\inf\_\{s\\in\\mathcal\{S\}\_\{\+\}\}p\(s,\\epsilon\)is the worst\-case per\-turn certified safety\. Ifp¯<1\\underline\{p\}<1, this bound vanishes exponentially inkk\.

###### Example 2\.2\(Vacuity of Naive Bound\)\.

With per\-turn safetyp¯=0\.95\\underline\{p\}=0\.95:ρ10≥0\.60\\rho\_\{10\}\\geq 0\.60,ρ20≥0\.36\\rho\_\{20\}\\geq 0\.36,ρ50≥0\.08\\rho\_\{50\}\\geq 0\.08\. For safety\-critical applications requiringρk≥0\.9\\rho\_\{k\}\\geq 0\.9, this permits at mostk≤2k\\leq 2turns\.

#### Scope of certification\.

The certified guarantee applies to adversaries constrained within anϵ\\epsilon\-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ϵ\\epsilon\-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\.

## 3Multi\-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](https://arxiv.org/html/2608.20820#S3.SS1)\), safety persistence characterizing margin evolution \(§[3\.2](https://arxiv.org/html/2608.20820#S3.SS2)\), information\-theoretic upper bounds establishing tightness \(§[3\.3](https://arxiv.org/html/2608.20820#S3.SS3)\), and a unified algorithm \(§[3\.4](https://arxiv.org/html/2608.20820#S3.SS4)\)\.

### 3\.1Compositional Certification

Conversations exhibit*mode structure*in embedding space that can be exploited for tighter certification\. A mode decompositionℳ=\{m1,…,mM\}\\mathcal\{M\}=\\\{m\_\{1\},\\ldots,m\_\{M\}\\\}covers𝒮\+\\mathcal\{S\}\_\{\+\}with bounded overlapκ=maxs⁡\|\{i:s∈𝒮mi\}\|\\kappa=\\max\_\{s\}\|\\\{i:s\\in\\mathcal\{S\}\_\{m\_\{i\}\}\\\}\|\. For each modemmwe define intra\-mode certified safetyρmin​\(ϵ\)\\rho\_\{m\}^\{\\mathrm\{in\}\}\(\\epsilon\)\(worst\-case probability of staying safe and inmm\) and for edges\(mi,mj\)\(m\_\{i\},m\_\{j\}\)in the transition graph we define transition safetyρi→jtr​\(ϵ\)\\rho\_\{i\\to j\}^\{\\mathrm\{tr\}\}\(\\epsilon\)\. A mode trajectoryσ\\sigmaoverkkturns hasnj​\(σ\)n\_\{j\}\(\\sigma\)intra\-mode turns inmjm\_\{j\}andτ⁡\(σ\)\\tau\(\\sigma\)transitions\. Full definitions appear in Appendix[B](https://arxiv.org/html/2608.20820#A2)\.

###### Theorem 3\.1\(Compositional Certification Bound\)\.

Letℳ=\{m1,…,mM\}\\mathcal\{M\}=\\\{m\_\{1\},\\ldots,m\_\{M\}\\\}be a mode decomposition with overlapκ=κ⁡\(ℳ\)\\kappa=\\kappa\(\\mathcal\{M\}\)\. For anykk\-turn conversation with mode trajectoryσ∈Σk​\(ℳ\)\\sigma\\in\\Sigma\_\{k\}\(\\mathcal\{M\}\):

ρk​\(s0,π,ϵ\)≥1κ\\displaystyle\\rho\_\{k\}\(s\_\{0\},\\pi,\\epsilon\)\\geq\\frac\{1\}\{\\kappa\}⋅∏j=1M\(ρmjin​\(ϵ\)\)nj​\(σ\)\\displaystyle\\cdot\\prod\_\{j=1\}^\{M\}\\left\(\\rho\_\{m\_\{j\}\}^\{\\mathrm\{in\}\}\(\\epsilon\)\\right\)^\{n\_\{j\}\(\\sigma\)\}⋅∏\(i,j\)∈Trans⁡\(σ\)ρi→jtr​\(ϵ\)\\displaystyle\\cdot\\prod\_\{\(i,j\)\\in\\mathrm\{Trans\}\(\\sigma\)\}\\rho\_\{i\\to j\}^\{\\mathrm\{tr\}\}\(\\epsilon\)whereTrans⁡\(σ\)=\{\(σ⁡\(t\),σ⁡\(t\+1\)\):σ⁡\(t\)≠σ⁡\(t\+1\)\}\\mathrm\{Trans\}\(\\sigma\)=\\\{\(\\sigma\(t\),\\sigma\(t\+1\)\):\\sigma\(t\)\\neq\\sigma\(t\+1\)\\\}is the multiset of transitions\. Taking the infimum over feasible trajectories:

ρk\(s0,π,ϵ\)≥1κ⋅\\displaystyle\\rho\_\{k\}\(s\_\{0\},\\pi,\\epsilon\)\\geq\\frac\{1\}\{\\kappa\}\\cdotinfσ∈Σk​\(ℳ,s0\)\[∏j=1M\(ρmjin\)nj​\(σ\)\\displaystyle\\inf\_\{\\sigma\\in\\Sigma\_\{k\}\(\\mathcal\{M\},s\_\{0\}\)\}\\bigg\[\\prod\_\{j=1\}^\{M\}\\left\(\\rho\_\{m\_\{j\}\}^\{\\mathrm\{in\}\}\\right\)^\{n\_\{j\}\(\\sigma\)\}⋅∏\(i,j\)∈Trans⁡\(σ\)ρi→jtr\]\\displaystyle\\cdot\\prod\_\{\(i,j\)\\in\\mathrm\{Trans\}\(\\sigma\)\}\\rho\_\{i\\to j\}^\{\\mathrm\{tr\}\}\\bigg\]whereΣk​\(ℳ,s0\)⊆Σk​\(ℳ\)\\Sigma\_\{k\}\(\\mathcal\{M\},s\_\{0\}\)\\subseteq\\Sigma\_\{k\}\(\\mathcal\{M\}\)are trajectories starting from a mode containings0s\_\{0\}\.

The following corollary quantifies when the compositional bound strictly improves upon the naive multiplicative bound\.

###### Corollary 3\.2\(Improvement over Naive Composition\)\.

Letp¯=infsp⁡\(s,ϵ\)\\underline\{p\}=\\inf\_\{s\}p\(s,\\epsilon\)be the naive per\-turn bound\. Suppose the mode decomposition satisfies:

1. 1\.Intra\-mode safety:ρmjin≥1−δ\\rho\_\{m\_\{j\}\}^\{\\mathrm\{in\}\}\\geq 1\-\\deltafor smallδ\>0\\delta\>0
2. 2\.Inter\-mode transition safety:ρi→jtr≥γ\\rho\_\{i\\to j\}^\{\\mathrm\{tr\}\}\\geq\\gammafor someγ∈\(0,1\)\\gamma\\in\(0,1\)
3. 3\.Sparse transitions: trajectoryσ\\sigmahas at mostτ\\tautransitions

Then the compositional bound is:

ρkcomp≥1κ​\(1−δ\)k−τ⋅γτ\\rho\_\{k\}^\{\\mathrm\{comp\}\}\\geq\\frac\{1\}\{\\kappa\}\(1\-\\delta\)^\{k\-\\tau\}\\cdot\\gamma^\{\\tau\}\(3\)This exceeds the naive boundp¯k\\underline\{p\}^\{\\,k\}when:

τ<k​log⁡\(1−δ\)−k​log⁡p¯−log⁡κlog⁡\(1−δ\)−log⁡γ\\tau<\\frac\{k\\log\(1\-\\delta\)\-k\\log\\underline\{p\}\-\\log\\kappa\}\{\\log\(1\-\\delta\)\-\\log\\gamma\}\(4\)

###### Example 3\.3\(Numerical Comparison\)\.

Under parametersk=20k\{=\}20,τ=3\\tau\{=\}3,p¯=0\.9\\underline\{p\}\{=\}0\.9,δ=0\.02\\delta\{=\}0\.02,γ=0\.7\\gamma\{=\}0\.7,κ=1\\kappa\{=\}1:

ρ20naive\\displaystyle\\rho\_\{20\}^\{\\mathrm\{naive\}\}≥0\.920≈0\.122\\displaystyle\\geq 0\.9^\{20\}\\approx 0\.122ρ20comp\\displaystyle\\rho\_\{20\}^\{\\mathrm\{comp\}\}≥0\.9817⋅0\.73≈0\.708⋅0\.343≈0\.243\\displaystyle\\geq 0\.98^\{17\}\\cdot 0\.7^\{3\}\\approx 0\.708\\cdot 0\.343\\approx 0\.243The compositional certified lower bound is approximatelytwicethe naive lower bound\. Note: improvement depends onkkandτ\\tau; whenkkis small, transition overhead may dominate \(see Appendix[I\.2](https://arxiv.org/html/2608.20820#A9.SS2)\)\.

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](https://arxiv.org/html/2608.20820#S3.Thmtheorem1)can be computed by dynamic programming inO⁡\(M2​k\)O\(M^\{2\}k\)time\.

### 3\.2Safety Persistence

The compositional bound still depends on the number of transitionsτ\\tau\. We next define*safety persistence*, a property that enables stronger guarantees by characterizing how safety margins evolve\.

###### Definition 2\(\(α,β\)\(\\alpha,\\beta\)\-Safety Persistence\)\.

A conversational system\(𝒮,T,π,𝖲𝖺𝖿𝖾\)\(\\mathcal\{S\},T,\\pi,\\mathsf\{Safe\}\)exhibits\(α,β\)\(\\alpha,\\beta\)\-safety persistenceforα∈\[0,1\)\\alpha\\in\[0,1\)andβ∈\(0,1\]\\beta\\in\(0,1\]if for all safe statess∈𝒮\+s\\in\\mathcal\{S\}\_\{\+\}with safety marginΔ⁡\(s\)\>0\\Delta\(s\)\>0:

ℙu∼ν,r∼π​\[𝖲𝖺𝖿𝖾⁡\(s′\)=1∧Δ⁡\(s′\)≥\(1−α\)​Δ​\(s\)\]≥β\\mathbb\{P\}\_\{u\\sim\\nu,\\,r\\sim\\pi\}\\\!\\left\[\\begin\{gathered\}\\mathsf\{Safe\}\(s^\{\\prime\}\)=1\\\\ \{\}\\land\\ \\Delta\(s^\{\\prime\}\)\\geq\(1\-\\alpha\)\\Delta\(s\)\\end\{gathered\}\\right\]\\geq\\beta\(5\)wheres′=T⁡\(s,u,r\)s^\{\\prime\}=T\(s,u,r\)andν∈Πϵ\\nu\\in\\Pi\_\{\\epsilon\}is any adversarial policy\.

With probability at leastβ\\beta, the safety margin retains at least a\(1−α\)\(1\{\-\}\\alpha\)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\(α,β\)\(\\alpha,\\beta\)\-safety persistence\. Lets0∈𝒮\+s\_\{0\}\\in\\mathcal\{S\}\_\{\+\}have initial marginΔ0=Δ⁡\(s0\)\>0\\Delta\_\{0\}=\\Delta\(s\_\{0\}\)\>0\. Then:

ρk​\(s0,π,ϵ\)≥βk\\rho\_\{k\}\(s\_\{0\},\\pi,\\epsilon\)\\geq\\beta^\{k\}\(6\)Whenβ\>p¯\\beta\>\\underline\{p\}\(i\.e\., the persistence guarantee exceeds the worst\-case per\-turn bound\), we haveβk\>p¯k\\beta^\{k\}\>\\underline\{p\}^\{\\,k\}, strictly improving upon the naive bound\.

Additionally, a union bound yields an interpretable \(though numerically weaker\) characterization:

ρk​\(s0,π,ϵ\)≥1−k⁡\(1−β\)\\rho\_\{k\}\(s\_\{0\},\\pi,\\epsilon\)\\geq 1\-k\(1\-\\beta\)\(7\)This formula provides a sufficient condition for safety: the system remains safe with probability≥1−ξ\\geq 1\-\\xiwheneverk≤ξ/\(1−β\)k\\leq\\xi/\(1\-\\beta\), enabling direct horizon estimation\.

###### Corollary 3\.6\(Effective Horizon Estimation\)\.

Under\(α,β\)\(\\alpha,\\beta\)\-safety persistence, to maintainρk≥1−ξ\\rho\_\{k\}\\geq 1\-\\xifor targetξ∈\(0,1\)\\xi\\in\(0,1\), the linear characterization gives the sufficient horizon bound:

kmax=⌊ξ1−β⌋k\_\{\\max\}=\\left\\lfloor\\frac\{\\xi\}\{1\-\\beta\}\\right\\rfloor\(8\)compared tokmax=⌊log⁡\(1−ξ\)/log⁡p¯⌋k\_\{\\max\}=\\lfloor\\log\(1\-\\xi\)/\\log\\underline\{p\}\\rfloorunder naive composition\. For example, withβ=0\.98\\beta\{=\}0\.98andξ=0\.1\\xi\{=\}0\.1: the persistence\-based estimate giveskmax=5k\_\{\\max\}=5, whereasp¯=0\.9\\underline\{p\}\{=\}0\.9giveskmax=1k\_\{\\max\}=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. 1\.TTisLsL\_\{s\}\-Lipschitz in state:‖T⁡\(s,u,r\)−T⁡\(s′,u,r\)‖≤Ls​‖s−s′‖\\\|T\(s,u,r\)\-T\(s^\{\\prime\},u,r\)\\\|\\leq L\_\{s\}\\\|s\-s^\{\\prime\}\\\|
2. 2\.TTisLuL\_\{u\}\-Lipschitz in input:‖T⁡\(s,u,r\)−T⁡\(s,u′,r\)‖≤Lu⋅d⁡\(u,u′\)\\\|T\(s,u,r\)\-T\(s,u^\{\\prime\},r\)\\\|\\leq L\_\{u\}\\cdot d\(u,u^\{\\prime\}\)
3. 3\.TTisLrL\_\{r\}\-Lipschitz in response:‖T⁡\(s,u,r\)−T⁡\(s,u,r′\)‖≤Lr⋅dr​\(r,r′\)\\\|T\(s,u,r\)\-T\(s,u,r^\{\\prime\}\)\\\|\\leq L\_\{r\}\\cdot d\_\{r\}\(r,r^\{\\prime\}\)for some metricdrd\_\{r\}
4. 4\.The safe region satisfies:𝒮\+\\mathcal\{S\}\_\{\+\}is convex withdist⁡\(s,𝒮−\)≥δ\\mathrm\{dist\}\(s,\\mathcal\{S\}\_\{\-\}\)\\geq\\deltaforssin theδ\\delta\-interior
5. 5\.LLM responses satisfy:ℙ\[∥r−r∗∥≤η\]≥p0\\mathbb\{P\}\[\\\|r\-r^\{\*\}\\\|\\leq\\eta\]\\geq p\_\{0\}for some nominal responser∗r^\{\*\}
6. 6\.Nominal drift is bounded:‖T⁡\(s,u∗,r∗\)−s‖≤δT\\\|T\(s,u^\{\*\},r^\{\*\}\)\-s\\\|\\leq\\delta\_\{T\}for alls∈𝒮\+s\\in\\mathcal\{S\}\_\{\+\}

Then for all statesssin theδ\\delta\-interior of𝒮\+\\mathcal\{S\}\_\{\+\}\(i\.e\.,Δ⁡\(s\)≥δ\\Delta\(s\)\\geq\\delta\), the\(α,β\)\(\\alpha,\\beta\)\-persistence condition \(Definition[2](https://arxiv.org/html/2608.20820#Thmdefinition2)\) holds with:

α\\displaystyle\\alpha=Lu​ϵ\+Lr​η\+δTδ,\\displaystyle=\\frac\{L\_\{u\}\\epsilon\+L\_\{r\}\\eta\+\\delta\_\{T\}\}\{\\delta\},\(9\)β\\displaystyle\\beta=p0⋅𝟏\[Luϵ\+Lrη\+δT<δ\]\.\\displaystyle=p\_\{0\}\\cdot\\mathbf\{1\}\[L\_\{u\}\\epsilon\+L\_\{r\}\\eta\+\\delta\_\{T\}<\\delta\]\.The indicator function reflects a strict sufficient condition; whenLu​ϵ\+Lr​η\+δT≥δL\_\{u\}\\epsilon\+L\_\{r\}\\eta\+\\delta\_\{T\}\\geq\\delta, it yieldsβ=0\\beta=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](https://arxiv.org/html/2608.20820#S3.Thmtheorem7)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](https://arxiv.org/html/2608.20820#algorithm1)Phase 1; see Appendix[F\.1](https://arxiv.org/html/2608.20820#A6.SS1)\)\.

### 3\.3Tightness 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ℳ\\mathcal\{M\}and any trajectoryσ\\sigma, there exist transition dynamicsTTand adversarial strategiesν∗\\nu^\{\*\}such that:

ρk\(s0,π,ϵ\)≤∏j=1M\\displaystyle\\rho\_\{k\}\(s\_\{0\},\\pi,\\epsilon\)\\leq\\prod\_\{j=1\}^\{M\}\(ρmjin\)nj​\(σ\)\\displaystyle\\left\(\\rho\_\{m\_\{j\}\}^\{\\mathrm\{in\}\}\\right\)^\{n\_\{j\}\(\\sigma\)\}⋅∏\(i,j\)∈Trans⁡\(σ\)ρi→jtr\\displaystyle\\cdot\\prod\_\{\(i,j\)\\in\\mathrm\{Trans\}\(\\sigma\)\}\\rho\_\{i\\to j\}^\{\\mathrm\{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\\kappa=1\), our compositional lower bound \(Theorem[3\.1](https://arxiv.org/html/2608.20820#S3.Thmtheorem1)\) matches the information\-theoretic upper bound \(Theorem[3\.8](https://arxiv.org/html/2608.20820#S3.Thmtheorem8)\) exactly\. The compositional certification is therefore tight forκ=1\\kappa=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\\rho\_\{k\}\(s\_\{0\},\\pi,\\epsilon\)=p^\{k\}\(10\)for somep<1p<1, and the naive multiplicative boundp¯k\\underline\{p\}^\{\\,k\}is tight\.

The proof constructs a memoryless system where the transition functionTTmaps every\(s,u,r\)\(s,u,r\)to a fresh state drawn independently from a fixed distribution, withℙ\[𝖲𝖺𝖿𝖾\(s′\)=1\]=p\\mathbb\{P\}\[\\mathsf\{Safe\}\(s^\{\\prime\}\)=1\]=pregardless of the adversary’s choice ofuu\(see Appendix[E\.8](https://arxiv.org/html/2608.20820#A5.SS8)\)\. Since turns are independent and each has safety probability exactlypp, we getρk=pk\\rho\_\{k\}=p^\{k\}\. Thus our structural assumptions \(modes, persistence\) are necessary to*guarantee*sub\-exponential bounds, not merely sufficient for achieving them\.

### 3\.4Unified 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ℳ\\mathcal\{M\}with overlapκ\\kappaand exhibits\(α,β\)\(\\alpha,\\beta\)\-safety persistence within each mode\. Then:

ρk\(s0,π,ϵ\)≥βkκ⋅infσ∈Σk​\(ℳ,s0\)\[\\displaystyle\\rho\_\{k\}\(s\_\{0\},\\pi,\\epsilon\)\\geq\\frac\{\\beta^\{k\}\}\{\\kappa\}\\cdot\\inf\_\{\\sigma\\in\\Sigma\_\{k\}\(\\mathcal\{M\},s\_\{0\}\)\}\\bigg\[∏j\(ρmjinβ\)nj​\(σ\)\\displaystyle\\prod\_\{j\}\\left\(\\frac\{\\rho\_\{m\_\{j\}\}^\{\\mathrm\{in\}\}\}\{\\beta\}\\right\)^\{\\\!n\_\{j\}\(\\sigma\)\}⋅∏\(i,j\)ρi→jtr\]\\displaystyle\\cdot\\prod\_\{\(i,j\)\}\\rho\_\{i\\to j\}^\{\\mathrm\{tr\}\}\\bigg\]Whenρmjin≥β\\rho\_\{m\_\{j\}\}^\{\\mathrm\{in\}\}\\geq\\betafor all modes \(persistence dominates intra\-mode certification\):

ρk≥βkκ⋅γτ\\rho\_\{k\}\\geq\\frac\{\\beta^\{k\}\}\{\\kappa\}\\cdot\\gamma^\{\\tau\}\(11\)whereγ=mini,j⁡ρi→jtr\\gamma=\\min\_\{i,j\}\\rho\_\{i\\to j\}^\{\\mathrm\{tr\}\}andτ\\tauis the number of transitions\.

Algorithm[1](https://arxiv.org/html/2608.20820#algorithm1)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/β^\\hat\{\\rho\}\_\{m\_\{j\}\}^\{\\mathrm\{in\}\}/\\hat\{\\beta\}\(notρ^mjin\\hat\{\\rho\}\_\{m\_\{j\}\}^\{\\mathrm\{in\}\}\) for intra\-mode steps, consistent with Theorem[3\.11](https://arxiv.org/html/2608.20820#S3.Thmtheorem11), since the persistence baseline is already captured byβ^k\\hat\{\\beta\}^\{k\}in Phase 4\. The final output ismax⁡\(β^k,ρ^kcomb\)\\max\(\\hat\{\\beta\}^\{k\},\\hat\{\\rho\}\_\{k\}^\{\\mathrm\{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](https://arxiv.org/html/2608.20820#S4.T3)\)\.

LetNNbe the number of samples for randomized smoothing\. Phase 1 requiresO⁡\(M​N\)O\(MN\)LLM forward passes; Phase 2 requiresO⁡\(\|Eℳ\|​N\)O\(\|E\_\{\\mathcal\{M\}\}\|N\)passes; Phase 3 performsO⁡\(M2​k\)O\(M^\{2\}k\)arithmetic operations\. The total complexity isO⁡\(\(M\+\|Eℳ\|\)​N\+M2​k\)O\(\(M\+\|E\_\{\\mathcal\{M\}\}\|\)N\+M^\{2\}k\), which is linear in the horizonkk\.

## 4Experiments

We evaluate MTCR on production LLMs under real attack scenarios\. Appendix[I](https://arxiv.org/html/2608.20820#A9)provides additional numerical verification under a controlled parametric model\.

### 4\.1Experimental Setup

#### Compared methods\.

No prior method provides certified multi\-turn robustness\. We compare four variants:Mult\. ref\., the multiplicative referencep¯k\\bar\{p\}^\{k\}withp¯=supsp⁡\(s,ϵ\)\\bar\{p\}=\\sup\_\{s\}p\(s,\\epsilon\)\(an optimistic reference, not a valid certified bound under adaptive adversaries\);Persistence\-Only, applying the\(α,β\)\(\\alpha,\\beta\)\-persistence bound alone;Compositional\-Only, using mode decomposition without persistence; andMTCR \(full\), our combined certification \(Algorithm[1](https://arxiv.org/html/2608.20820#algorithm1)\)\.

#### Data\.

We use harmful prompts from AdvBench\([Zou et al\. 2023](https://arxiv.org/html/2608.20820#bib.bib30)\), covering violence, illegal activities, and hate speech \(50 prompts per category, 150 total\)\.

#### Mode discovery\.

Dialogue state embeddings are computed onn=500n\{=\}500held\-out safe multi\-turn conversations \(ShareGPT\-style\) using sentence\-transformers\. Each state is the embedding of the full dialogue history\. Modes are discovered viakk\-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 runskkturns; 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\{\\leq\}\\pm 0\.05across 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](https://arxiv.org/html/2608.20820#A8)\.

### 4\.2Experiments on Production Models

We evaluate six LLMs with varying alignment strengths\.Open\-source:LLaMA\-2\-7B\-Chat\([Touvron et al\. 2023](https://arxiv.org/html/2608.20820#bib.bib19)\), Vicuna\-7B\([Chiang et al\. 2023](https://arxiv.org/html/2608.20820#bib.bib4)\), Llama\-3\.2\-3B, and Qwen2\.5\-7B\-Instruct\([Yang et al\. 2025](https://arxiv.org/html/2608.20820#bib.bib22)\)\.Closed\-source \(via API\):GPT\-4o\([Hurst et al\. 2024](https://arxiv.org/html/2608.20820#bib.bib8)\)and Claude\-3\.5\-Sonnet\([Anthropic 2024](https://arxiv.org/html/2608.20820#bib.bib1)\)\.

The evaluation covers horizonsk∈\{5,10,15,20\}k\\in\\\{5,10,15,20\\\}, two attack types \(staticϵ\\epsilon\-ball and Crescendo\-style\), and mode granularitiesM∈\{2,4,8\}M\\in\\\{2,4,8\\\}\. Dialogue state embeddings useall\-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](https://arxiv.org/html/2608.20820#A7)\)\. Perturbation budget isϵ=5\\epsilon\{=\}5\(character\-level edit distance, following SmoothLLM\([Robey et al\. 2023](https://arxiv.org/html/2608.20820#bib.bib17)\)\), withN=100N\{=\}100smoothing samples per mode andϵ∈\{3,5,7\}\\epsilon\\in\\\{3,5,7\\\}for sensitivity analysis\. Full details are in Appendix[J\.2](https://arxiv.org/html/2608.20820#A10.SS2)\.

Table 1:Certification and empirical safety across six LLMs \(M=4M\{=\}4,N=100N\{=\}100,ϵ=5\\epsilon\{=\}5, 100 trials\)\. MTCRρ^k\\hat\{\\rho\}\_\{k\}: certified lower bound; Naivep¯k\\underline\{p\}^\{\\,k\}: valid but loose multiplicative bound; Mult\. ref\.p¯k\\bar\{p\}^\{k\}: optimistic reference \(*not*a valid certified bound under adaptive adversaries\); Gap==Emp\. \(Crescendo\)−\-MTCRρ^k\\hat\{\\rho\}\_\{k\}\.Bold: best certified bound per horizon\.ModelkkCertificationEmpirical SafetyGapMTCRρ^k\\hat\{\\rho\}\_\{k\}Naivep¯k\\underline\{p\}^\{\\,k\}Mult\. ref\.StaticCrescendo*Open\-source models*LLaMA\-2\-7B\-Chat50\.360\.290\.5966%55%\+0\.19100\.130\.080\.3549%38%\+0\.25150\.050\.020\.2138%28%\+0\.23200\.020\.010\.1230%22%\+0\.20Vicuna\-7B50\.280\.220\.5058%46%\+0\.18100\.080\.050\.2540%30%\+0\.22Llama\-3\.2\-3B50\.400\.330\.6672%62%\+0\.22100\.180\.110\.4356%45%\+0\.27Qwen2\.5\-7B\-Instruct50\.440\.350\.7076%65%\+0\.21100\.220\.120\.4860%49%\+0\.27*Closed\-source models \(API\)*GPT\-4o50\.550\.440\.8288%78%\+0\.23100\.320\.200\.6673%62%\+0\.30Claude\-3\.5\-Sonnet50\.510\.420\.7785%74%\+0\.23100\.280\.180\.6070%58%\+0\.30We highlight three findings from Table[1](https://arxiv.org/html/2608.20820#S4.T1)\.

\(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 boundp¯k\\underline\{p\}^\{\\,k\}\(which is also a valid certified bound\), MTCR provides 1\.2–1\.6×\\timestighter certification atk=5k\{=\}5, demonstrating the value of compositional structure\.

\(2\) Model ranking and alignment quality\.Certified bounds reflect alignment strength: atk=5k\{=\}5, GPT\-4o achieves the highest certified bound \(ρ^5=0\.55\\hat\{\\rho\}\_\{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\\hat\{\\rho\}\_\{10\}/\\hat\{\\rho\}\_\{5\}across models reveals that better\-aligned models degrade more slowly: GPT\-4o retains 58% of itsk=5k\{=\}5bound atk=10k\{=\}10, compared to only 29% for Vicuna\. This supports Theorem[3\.5](https://arxiv.org/html/2608.20820#S3.Thmtheorem5): systems with stronger safety persistence exhibit slower degradation\. For LLaMA\-2, the fullk∈\{5,10,15,20\}k\\in\\\{5,10,15,20\\\}trajectory shows progressive decay from0\.360\.36to0\.020\.02, with the combined formula \(Theorem[3\.11](https://arxiv.org/html/2608.20820#S3.Thmtheorem11)\) providing the tightest bound at all horizons \(Table[3](https://arxiv.org/html/2608.20820#S4.T3)\)\. Crescendo reduces empirical safety by 8–13 percentage points relative to static attacks; stronger models show larger absolute but smaller relative drops\. Figure[2](https://arxiv.org/html/2608.20820#S4.F2)visualizes this degradation\.

55101015152020000\.10\.10\.20\.20\.30\.30\.40\.40\.50\.50\.60\.60\.70\.7HorizonkkBoundMTCRρ^k\\hat\{\\rho\}\_\{k\}Mult\. ref\.p¯k\\bar\{p\}^\{k\}Emp\. \(Static\)Emp\. \(Crescendo\)Figure 2:Certified lower bound vs\. horizonkkon LLaMA\-2\-7B\-Chat \(p¯=0\.90\\bar\{p\}\{=\}0\.90,p¯=0\.78\\underline\{p\}\{=\}0\.78; data from Table[1](https://arxiv.org/html/2608.20820#S4.T1)\)\. The MTCR curve lies below empirical safety under both attack types at all horizons, confirming the certified bound is not violated\.We vary mode granularityM∈\{2,4,8\}M\\in\\\{2,4,8\\\}on LLaMA\-2\-7B\-Chat atk=5k\{=\}5\. Coarser modes \(M=2M\{=\}2\) yieldρ^5=0\.39\\hat\{\\rho\}\_\{5\}\{=\}0\.39; finer modes \(M=8M\{=\}8\) yield0\.250\.25due to increased overlapκ\\kappaand transition cost\. AlthoughM=2M\{=\}2gives a marginally higher bound atk=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 useM=4M\{=\}4throughout\.

#### Perturbation budget sensitivity\.

Table[2](https://arxiv.org/html/2608.20820#S4.T2)variesϵ∈\{3,5,7\}\\epsilon\\in\\\{3,5,7\\\}on LLaMA\-2\-7B\-Chat\. Largerϵ\\epsilonenlarges the adversarial ballℬϵ\\mathcal\{B\}\_\{\\epsilon\}, lowering certified bounds as expected; empirical safety follows the same trend\.

Table 2:Perturbation budgetϵ\\epsilonsensitivity \(LLaMA\-2\-7B\-Chat,M=4M\{=\}4,k=5,10k\{=\}5,10, 100 trials\)\.ϵ\\epsilonMTCRρ^5\\hat\{\\rho\}\_\{5\}MTCRρ^10\\hat\{\\rho\}\_\{10\}Emp\.5\(Static\)Emp\.10\(Static\)30\.490\.1975%58%50\.360\.1366%49%70\.240\.0755%37%

#### MTCR ablation\.

Table[3](https://arxiv.org/html/2608.20820#S4.T3)ablates the certification variants on LLaMA\-2\-7B\-Chat\. The combined formula \(Theorem[3\.11](https://arxiv.org/html/2608.20820#S3.Thmtheorem11)\) consistently gives the tightest certified bound across all horizons, as it exploits both mode structure and persistence\. The persistence\-only bound \(β^k\\hat\{\\beta\}^\{k\}withβ^=0\.79\\hat\{\\beta\}\{=\}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 atk=5k\{=\}5when transitions are sparse \(see Appendix[I\.2](https://arxiv.org/html/2608.20820#A9.SS2)\), but degrades similarly at longer horizons\.

Table 3:MTCR component ablation \(LLaMA\-2\-7B\-Chat,M=4M\{=\}4,ϵ=5\\epsilon\{=\}5,β^=0\.79\\hat\{\\beta\}\{=\}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\.Methodk=5k\{=\}5k=10k\{=\}10k=15k\{=\}15k=20k\{=\}20Mult\. ref\.p¯k\\bar\{p\}^\{k\}0\.590\.350\.210\.12Persistence\-Only \(β^k\\hat\{\\beta\}^\{k\}\)0\.310\.100\.030\.01Compositional\-Only0\.340\.110\.040\.01Combined \(Thm\.[3\.11](https://arxiv.org/html/2608.20820#S3.Thmtheorem11)\)0\.360\.130\.050\.02MTCR \(max\)0\.360\.130\.050\.02

#### Safety detector comparison\.

Table[4](https://arxiv.org/html/2608.20820#S4.T4)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](https://arxiv.org/html/2608.20820#A7)for setup\.

Table 4:Safety detector comparison \(LLaMA\-2\-7B\-Chat,k=5k\{=\}5,ϵ=5\\epsilon\{=\}5, 100 trials\)\.DetectorMTCRρ^5\\hat\{\\rho\}\_\{5\}Emp\. \(Static\)Emp\. \(Crescendo\)Keyword\-based \(default\)0\.3666%55%Neural classifier0\.3370%59%

#### Sample complexity\.

Tight certification via randomized smoothing requiresN=O⁡\(log⁡\(1/δconf\)/γgap2\)N=O\(\\log\(1/\\delta\_\{\\mathrm\{conf\}\}\)/\\gamma\_\{\\mathrm\{gap\}\}^\{2\}\)samples, whereδconf\\delta\_\{\\mathrm\{conf\}\}is the confidence level andγgap\\gamma\_\{\\mathrm\{gap\}\}is the gap between the true safety probability and the certification threshold\. We useN=100N\{=\}100for computational feasibility; increasingNNwould tighten confidence intervals but not change the qualitative findings\.

## 5Discussion

#### Mode Discovery and Quality\.

Our framework assumes a mode decomposition is given \(Section[4\.1](https://arxiv.org/html/2608.20820#S4.SS1), Appendix[F](https://arxiv.org/html/2608.20820#A6)\)\. Mode quality affects certification tightness through two channels: \(i\) the overlap parameterκ\\kappa, introducing a1/κ1/\\kappapenalty in Theorem[3\.1](https://arxiv.org/html/2608.20820#S3.Thmtheorem1), and \(ii\) intra\-mode safetyρmin\\rho\_\{m\}^\{\\mathrm\{in\}\}, which depends on mode homogeneity\. In our experiments,kk\-means withM=4M\{=\}4yieldsκ=1\\kappa\{=\}1and intra\-mode safety above the persistence baseline, whileM=8M\{=\}8increases overlap \(κ=3\\kappa\{=\}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κ\\kappasubject 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](https://arxiv.org/html/2608.20820#S4.T1), Gap:\+0\.18\+0\.18to\+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](https://arxiv.org/html/2608.20820#bib.bib3)\)\. 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ϵ\\epsilon\-bounded adversaries \(Section[2](https://arxiv.org/html/2608.20820#S2)\)\. The empirical observation that Crescendo attacks \(beyond theϵ\\epsilon\-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\\rho\_\{m\}^\{\\mathrm\{in\}\}or transitions with lowρi→jtr\\rho\_\{i\\to j\}^\{\\mathrm\{tr\}\}\), guiding targeted safety tuning\. It can also inform conversation\-length policies: given a target safety levelξ\\xi, Corollary[3\.6](https://arxiv.org/html/2608.20820#S3.Thmtheorem6)provides a theoretically grounded maximum conversation lengthkmaxk\_\{\\max\}\.

#### Extensions\.

A natural next step is combining MTCR with runtime monitoring: the certified bound provides a static guarantee, while online tracking ofΔ⁡\(st\)\\Delta\(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\.

## 6Conclusion

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ϵ\\epsilon\-bounded adversaries \(e\.g\., character\-level perturbations\); while empirical safety generalizes to semantic attacks like Crescendo, no formal guarantee is provided beyond theϵ\\epsilon\-ball\. Second, mode decomposition relies on heuristic clustering of safe dialogue embeddings; the choice ofMMand overlapκ\\kappaaffects 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://www\.anthropic\.com/claude](https://www.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 ARelated Work

#### Single\-Turn Certified Robustness\.

Certified robustness originated with randomized smoothing\([Cohen et al\. 2019](https://arxiv.org/html/2608.20820#bib.bib5);[Lecuyer et al\. 2018](https://arxiv.org/html/2608.20820#bib.bib11)\), providing probabilistic guarantees againstℓp\\ell\_\{p\}\-bounded perturbations\. For NLP, SAFER\([Ye et al\. 2020](https://arxiv.org/html/2608.20820#bib.bib23)\)pioneered certified text classification via synonym substitution\. RanMASK\([Zeng et al\. 2023](https://arxiv.org/html/2608.20820#bib.bib24)\)improved this through random token masking\. Text\-CRS\([Zhang et al\. 2024](https://arxiv.org/html/2608.20820#bib.bib28)\)generalized to insertion, deletion, and reordering\.

For LLM jailbreaking, SmoothLLM\([Robey et al\. 2023](https://arxiv.org/html/2608.20820#bib.bib17)\)adapts randomized smoothing to character\-level perturbations\. Erase\-and\-Check\([Kumar et al\. 2023](https://arxiv.org/html/2608.20820#bib.bib10)\)provides certified harmful prompt detection\. Chen et al\.\([Chen et al\. 2025](https://arxiv.org/html/2608.20820#bib.bib3)\)establish tight bounds via knapsack formulation\. All these methods are limited to single\-turn settings\.

#### Multi\-Turn Attacks\.

Crescendo\([Russinovich et al\. 2025](https://arxiv.org/html/2608.20820#bib.bib18)\)progressively escalates from benign to harmful requests\. PAIR\([Chao et al\. 2025](https://arxiv.org/html/2608.20820#bib.bib2)\)and TAP\([Mehrotra et al\. 2024](https://arxiv.org/html/2608.20820#bib.bib13)\)use attacker LLMs for iterative refinement\. Persuasion\-based attacks\([Zeng et al\. 2024](https://arxiv.org/html/2608.20820#bib.bib25)\)exploit psychological techniques\. X\-Teaming\([Rahman et al\. 2025](https://arxiv.org/html/2608.20820#bib.bib16)\)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](https://arxiv.org/html/2608.20820#bib.bib9);[Nilim and El Ghaoui 2005](https://arxiv.org/html/2608.20820#bib.bib14)\)\. State\-Adversarial MDPs\([Zhang et al\. 2020](https://arxiv.org/html/2608.20820#bib.bib27);[Zhang et al\. 2021](https://arxiv.org/html/2608.20820#bib.bib26)\)model adversaries perturbing state observations, proving optimal stationary policies may not exist, which directly informs our approach\. Compositional verification\([Pasareanu et al\. 2018](https://arxiv.org/html/2608.20820#bib.bib15);[Henzinger et al\. 1998](https://arxiv.org/html/2608.20820#bib.bib7)\)decomposes complex problems; ECLipsE\([Xu and Sivaranjani 2024](https://arxiv.org/html/2608.20820#bib.bib21)\)achieves compositional Lipschitz estimation; Cert\-RNN\([Du et al\. 2021](https://arxiv.org/html/2608.20820#bib.bib6);[Zhang et al\. 2023](https://arxiv.org/html/2608.20820#bib.bib29)\)extends to sequential models\. We adapt these ideas to conversational safety\.

## Appendix BFormal Definitions and Assumptions

### B\.1Vocabulary, Dialogue, and State Space

Let𝒱\\mathcal\{V\}be a finite vocabulary and𝒱≤L\\mathcal\{V\}^\{\\leq L\}denote sequences of length at mostLL\. A dialogue historyht=\(u1,r1,…,ut,rt\)h\_\{t\}=\(u\_\{1\},r\_\{1\},\\ldots,u\_\{t\},r\_\{t\}\)is a sequence of user messages and model responses\. The state embeddingϕ:ℋ→𝒮\\phi:\\mathcal\{H\}\\to\\mathcal\{S\}maps histories to𝒮⊆ℝd\\mathcal\{S\}\\subseteq\\mathbb\{R\}^\{d\}with norm∥⋅∥\\\|\\cdot\\\|\. We assume𝒮\\mathcal\{S\}is bounded and𝒮\+\\mathcal\{S\}\_\{\+\}is open with non\-empty interior; the openness ensuresΔ⁡\(s\)\>0\\Delta\(s\)\>0for alls∈𝒮\+s\\in\\mathcal\{S\}\_\{\+\}\. The maximum inscribed ball radius isδmin=sup\{r\>0:∃s∈𝒮\+,Br\(s\)⊆𝒮\+\}\\delta\_\{\\min\}=\\sup\\\{r\>0:\\exists s\\in\\mathcal\{S\}\_\{\+\},B\_\{r\}\(s\)\\subseteq\\mathcal\{S\}\_\{\+\}\\\}\.

### B\.2Perturbation and Agents

For a reference inputu∗u^\{\*\}and metricdd, theϵ\\epsilon\-perturbation set isℬϵ​\(u∗\)=\{u:d⁡\(u,u∗\)≤ϵ\}\\mathcal\{B\}\_\{\\epsilon\}\(u^\{\*\}\)=\\\{u:d\(u,u^\{\*\}\)\\leq\\epsilon\\\}\. An adversarial user policyν:𝒮→Δ⁡\(𝒱≤L\)\\nu:\\mathcal\{S\}\\to\\Delta\(\\mathcal\{V\}^\{\\leq L\}\)satisfiessupp\(ν\(⋅\|s\)\)⊆ℬϵ\(u∗\(s\)\)\\mathrm\{supp\}\(\\nu\(\\cdot\|s\)\)\\subseteq\\mathcal\{B\}\_\{\\epsilon\}\(u^\{\*\}\(s\)\)\. The classΠϵ\\Pi\_\{\\epsilon\}in Definition[1](https://arxiv.org/html/2608.20820#Thmdefinition1)is the set of all such adversarial policies \(so the adversary is restricted to inputs withinϵ\\epsilonof the reference at each state\)\. The LLM policyπ\(⋅\|s,u\)\\pi\(\\cdot\|s,u\)generates responses conditioned on state and user input\.

### B\.3Transition, Safety, and Single\-Turn Certification

State transition is given byT⁡\(st−1,ut,rt\)↦stT\(s\_\{t\-1\},u\_\{t\},r\_\{t\}\)\\mapsto s\_\{t\}\. The safety predicate𝖲𝖺𝖿𝖾:𝒮→\{0,1\}\\mathsf\{Safe\}:\\mathcal\{S\}\\to\\\{0,1\\\}defines𝒮\+=\{s:𝖲𝖺𝖿𝖾⁡\(s\)=1\}\\mathcal\{S\}\_\{\+\}=\\\{s:\\mathsf\{Safe\}\(s\)=1\\\}and the safety marginΔ⁡\(s\)=dist⁡\(s,𝒮−\)\\Delta\(s\)=\\mathrm\{dist\}\(s,\\mathcal\{S\}\_\{\-\}\)\. The single\-turn certified safety is

p⁡\(s,ϵ\)=infu∈ℬϵℙ⁡\[𝖲𝖺𝖿𝖾⁡\(T⁡\(s,u,r\)\)\]p\(s,\\epsilon\)=\\inf\_\{u\\in\\mathcal\{B\}\_\{\\epsilon\}\}\\mathbb\{P\}\[\\mathsf\{Safe\}\(T\(s,u,r\)\)\]\(12\)where the probability is overr∼π\(⋅\|s,u\)r\\sim\\pi\(\\cdot\|s,u\)\.

### B\.4Conversational Modes and Decomposition

A conversational modem=\(𝒮m,𝒜m,ψm\)m=\(\\mathcal\{S\}\_\{m\},\\mathcal\{A\}\_\{m\},\\psi\_\{m\}\)consists of a region𝒮m⊆𝒮\\mathcal\{S\}\_\{m\}\\subseteq\\mathcal\{S\}, admissible messages𝒜m⊆𝒱≤L\\mathcal\{A\}\_\{m\}\\subseteq\\mathcal\{V\}^\{\\leq L\}, and a safety functionψm\\psi\_\{m\}\. A mode decompositionℳ=\{m1,…,mM\}\\mathcal\{M\}=\\\{m\_\{1\},\\ldots,m\_\{M\}\\\}satisfies coverage \(⋃i𝒮mi⊇𝒮\+\\bigcup\_\{i\}\\mathcal\{S\}\_\{m\_\{i\}\}\\supseteq\\mathcal\{S\}\_\{\+\}\) and bounded overlapκ=maxs⁡\|\{i:s∈𝒮mi\}\|\\kappa=\\max\_\{s\}\|\\\{i:s\\in\\mathcal\{S\}\_\{m\_\{i\}\}\\\}\|\. The transition graphGℳG\_\{\\mathcal\{M\}\}has edge\(mi,mj\)\(m\_\{i\},m\_\{j\}\)if and only if transitions from𝒮mi\\mathcal\{S\}\_\{m\_\{i\}\}to𝒮mj\\mathcal\{S\}\_\{m\_\{j\}\}are possible\.

### B\.5Intra\-Mode and Transition Safety

The intra\-mode certified safety is:

ρmin\(ϵ\)=infs∈𝒮m∩𝒮\+infu∈ℬϵ∩𝒜mℙ\[𝖲𝖺𝖿𝖾\(T\(s,u,r\)\)∧T\(s,u,r\)∈𝒮m\]\\rho\_\{m\}^\{\\mathrm\{in\}\}\(\\epsilon\)=\\inf\_\{s\\in\\mathcal\{S\}\_\{m\}\\cap\\mathcal\{S\}\_\{\+\}\}\\inf\_\{u\\in\\mathcal\{B\}\_\{\\epsilon\}\\cap\\mathcal\{A\}\_\{m\}\}\\mathbb\{P\}\[\\mathsf\{Safe\}\(T\(s,u,r\)\)\\land T\(s,u,r\)\\in\\mathcal\{S\}\_\{m\}\]\(13\)For each edge\(mi,mj\)∈Eℳ\(m\_\{i\},m\_\{j\}\)\\in E\_\{\\mathcal\{M\}\}, the transition safetyρi→jtr​\(ϵ\)\\rho\_\{i\\to j\}^\{\\mathrm\{tr\}\}\(\\epsilon\)is the infimum ofℙ⁡\[𝖲𝖺𝖿𝖾⁡\(T⁡\(s,u,r\)\)\]\\mathbb\{P\}\[\\mathsf\{Safe\}\(T\(s,u,r\)\)\]over feasible\(s,u\)\(s,u\)that induce transitions to𝒮mj\\mathcal\{S\}\_\{m\_\{j\}\}\.

### B\.6Mode Trajectory and Feasible Set

A mode trajectoryσ∈ℳk\\sigma\\in\\mathcal\{M\}^\{k\}overkkturns hasnj​\(σ\)=\|\{t:σ⁡\(t\)=mj=σ⁡\(t\+1\)\}\|n\_\{j\}\(\\sigma\)=\|\\\{t:\\sigma\(t\)=m\_\{j\}=\\sigma\(t\+1\)\\\}\|intra\-mode turns inmjm\_\{j\}andτ⁡\(σ\)=\|\{t:σ⁡\(t\)≠σ⁡\(t\+1\)\}\|\\tau\(\\sigma\)=\|\\\{t:\\sigma\(t\)\\neq\\sigma\(t\+1\)\\\}\|transitions\. The feasible setΣk​\(ℳ,s0\)\\Sigma\_\{k\}\(\\mathcal\{M\},s\_\{0\}\)contains trajectories starting from a mode containings0s\_\{0\}\.

### B\.7Remarks

Definition[1](https://arxiv.org/html/2608.20820#Thmdefinition1)uses*adaptive*adversaries that observest−1s\_\{t\-1\}before choosingutu\_\{t\}; oblivious adversaries yield a weaker setting, and our bounds apply to the stronger adaptive case\. For the overlap factor1/κ1/\\kappa: when a state lies inκ\\kappamodes, the adversary can exploit this ambiguity; whenκ=1\\kappa=1, the factor disappears\. For\(α,β\)\(\\alpha,\\beta\)\-safety persistence,α\\alphacontrols the maximum margin contraction per turn, andβ\\betais the probability that the margin shrinks by at most factorα\\alpha\. Under a convex safe region𝒮\+\\mathcal\{S\}\_\{\+\}, from initial distanceΔ\\Delta, one turn yields a safe state with distance≥\(1−α\)​Δ\\geq\(1\-\\alpha\)\\Deltawith probability at leastβ\\beta\.

## Appendix CAlgorithm Pipeline

Require :Initial state

s0s\_\{0\}, LLM policy

π\\pi, budget

ϵ\\epsilon, horizon

kk, mode decomposition

ℳ\\mathcal\{M\}
Ensure :Certified robustness lower bound

ρ^k\\hat\{\\rho\}\_\{k\}
1

// Phase 1: Intra\-Mode Certification;2

foreach*modem∈ℳm\\in\\mathcal\{M\}*do3

Estimate

ρ^min←\\hat\{\\rho\}\_\{m\}^\{\\mathrm\{in\}\}\\leftarrowRandomizedSmoothingCertify

\(m,ϵ,N\)\(m,\\epsilon,N\);4

Estimate persistence parameters

\(α^m,β^m\)←\(\\hat\{\\alpha\}\_\{m\},\\hat\{\\beta\}\_\{m\}\)\\leftarrowEstimatePersistence

\(m\)\(m\);5

end foreach6

7

// Phase 2: Inter\-Mode Certification;8

foreach*edge\(mi,mj\)∈Eℳ\(m\_\{i\},m\_\{j\}\)\\in E\_\{\\mathcal\{M\}\}*do9

ρ^i→jtr←\\hat\{\\rho\}\_\{i\\to j\}^\{\\mathrm\{tr\}\}\\leftarrowBoundaryAwareCertify

\(mi,mj,ϵ,N\)\(m\_\{i\},m\_\{j\},\\epsilon,N\);10

end foreach11

12

// Phase 3: Worst\-Case Trajectory \(Dynamic Programming\);13

β^←minm⁡β^m\\hat\{\\beta\}\\leftarrow\\min\_\{m\}\\hat\{\\beta\}\_\{m\};14

Initialize

V0​\(m\)←1V\_\{0\}\(m\)\\leftarrow 1for modes containing

s0s\_\{0\}, else

00;15

for*t=1t=1tokk*do16

foreach*modemjm\_\{j\}*do17

Vt\(mj\)←min\{Vt−1\(mj\)⋅ρ^mjin/β^,mini:\(mi,mj\)∈EVt−1\(mi\)⋅ρ^i→jtr\}V\_\{t\}\(m\_\{j\}\)\\leftarrow\\min\\\!\\big\\\{V\_\{t\-1\}\(m\_\{j\}\)\\cdot\\hat\{\\rho\}\_\{m\_\{j\}\}^\{\\mathrm\{in\}\}/\\hat\{\\beta\},\\;\\min\_\{i:\(m\_\{i\},m\_\{j\}\)\\in E\}V\_\{t\-1\}\(m\_\{i\}\)\\cdot\\hat\{\\rho\}\_\{i\\to j\}^\{\\mathrm\{tr\}\}\\big\\\};18

end foreach19

end for20

21

// Phase 4: Compute Final Bound;22

ρ^kcomb←1κ⋅β^k⋅minm⁡Vk​\(m\)\\hat\{\\rho\}\_\{k\}^\{\\mathrm\{comb\}\}\\leftarrow\\frac\{1\}\{\\kappa\}\\cdot\\hat\{\\beta\}^\{k\}\\cdot\\min\_\{m\}V\_\{k\}\(m\)// Combined bound \(Theorem[3\.11](https://arxiv.org/html/2608.20820#S3.Thmtheorem11)\);23

ρ^k←max⁡\(β^k,ρ^kcomb\)\\hat\{\\rho\}\_\{k\}\\leftarrow\\max\(\\hat\{\\beta\}^\{k\},\\;\\hat\{\\rho\}\_\{k\}^\{\\mathrm\{comb\}\}\)// Best of persistence\-only and combined;24

return*ρ^k\\hat\{\\rho\}\_\{k\}*

Algorithm 1Multi\-Turn Certified Robustness \(MTCR\)
## Appendix DBackground: State\-Adversarial MDPs

We provide background on State\-Adversarial MDPs\([Zhang et al\. 2020](https://arxiv.org/html/2608.20820#bib.bib27)\)informing our framework\. A standard MDP is\(𝒮,𝒜,P,R,γ\)\(\\mathcal\{S\},\\mathcal\{A\},P,R,\\gamma\)with state space𝒮\\mathcal\{S\}, action space𝒜\\mathcal\{A\}, transition kernelP⁡\(s′\|s,a\)P\(s^\{\\prime\}\|s,a\), rewardR⁡\(s,a\)R\(s,a\), and discountγ\\gamma\. An SA\-MDP augments this with an adversary that perturbs state observations: the agent observess~=s\+δ\\tilde\{s\}=s\+\\deltawhere‖δ‖≤ϵ\\\|\\delta\\\|\\leq\\epsilonis chosen adversarially\. Key results are as follows\.

These results show that static guardrails cannot guarantee robustness under state\-adversarial perturbations; adaptive mode\-based certification is needed to achieve meaningful guarantees\.

## Appendix EDetailed Proofs

### E\.1Proof of Proposition[2\.1](https://arxiv.org/html/2608.20820#S2.Thmtheorem1)

Define eventsEt=\{𝖲𝖺𝖿𝖾\(st\)=1\}E\_\{t\}=\\\{\\mathsf\{Safe\}\(s\_\{t\}\)=1\\\}\. By the chain rule:

ℙ⁡\[⋀t=1kEt\]=∏t=1kℙ⁡\[Et\|⋀i=1t−1Ei\]\\mathbb\{P\}\\left\[\\bigwedge\_\{t=1\}^\{k\}E\_\{t\}\\right\]=\\prod\_\{t=1\}^\{k\}\\mathbb\{P\}\\left\[E\_\{t\}\\,\\bigg\|\\,\\bigwedge\_\{i=1\}^\{t\-1\}E\_\{i\}\\right\]\(14\)
For any adversarial policyν\\nu, at each turnttconditioned on being in a safe statest−1∈𝒮\+s\_\{t\-1\}\\in\\mathcal\{S\}\_\{\+\}, the adversary selectsut∈ℬϵu\_\{t\}\\in\\mathcal\{B\}\_\{\\epsilon\}\. By the single\-turn safety definition \(Appendix[12](https://arxiv.org/html/2608.20820#A2.E12)\):

ℙ\[Et\|E1,…,Et−1,st−1\]≥p\(st−1,ϵ\)≥p¯\\mathbb\{P\}\\left\[E\_\{t\}\\,\\bigg\|\\,E\_\{1\},\\ldots,E\_\{t\-1\},s\_\{t\-1\}\\right\]\\geq p\(s\_\{t\-1\},\\epsilon\)\\geq\\underline\{p\}\(15\)wherep¯=infs∈𝒮\+p⁡\(s,ϵ\)\\underline\{p\}=\\inf\_\{s\\in\\mathcal\{S\}\_\{\+\}\}p\(s,\\epsilon\), sincep⁡\(st−1,ϵ\)=infu∈ℬϵℙ⁡\[𝖲𝖺𝖿𝖾⁡\(T⁡\(st−1,u,r\)\)\]p\(s\_\{t\-1\},\\epsilon\)=\\inf\_\{u\\in\\mathcal\{B\}\_\{\\epsilon\}\}\\mathbb\{P\}\[\\mathsf\{Safe\}\(T\(s\_\{t\-1\},u,r\)\)\]is the minimum over adversarial inputs, and the actual inpututu\_\{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\\rho\_\{k\}\(s\_\{0\},\\pi,\\epsilon\)=\\inf\_\{\\nu\}\\mathbb\{P\}\\left\[\\bigwedge\_\{t=1\}^\{k\}E\_\{t\}\\right\]\\geq\\underline\{p\}^\{\\,k\}\(16\)

### E\.2Proof of Theorem[3\.1](https://arxiv.org/html/2608.20820#S3.Thmtheorem1)

We prove this in three steps\.

Step 1: Trajectory Conditioning\.LetE=⋀t=1k𝖲𝖺𝖿𝖾⁡\(st\)E=\\bigwedge\_\{t=1\}^\{k\}\\mathsf\{Safe\}\(s\_\{t\}\)denote full safety\. For any state trajectory\(s1,…,sk\)\(s\_\{1\},\\ldots,s\_\{k\}\), define the induced mode trajectoryσ\\sigmawhereσ⁡\(t\)∈\{m:st∈𝒮m\}\\sigma\(t\)\\in\\\{m:s\_\{t\}\\in\\mathcal\{S\}\_\{m\}\\\}\(choosing arbitrarily if multiple modes containsts\_\{t\}\)\. Then:

ℙ⁡\[E\]=∑σ∈Σk​\(ℳ,s0\)ℙ⁡\[E∧trajectory is​σ\]\\mathbb\{P\}\[E\]=\\sum\_\{\\sigma\\in\\Sigma\_\{k\}\(\\mathcal\{M\},s\_\{0\}\)\}\\mathbb\{P\}\[E\\land\\text\{trajectory is \}\\sigma\]\(17\)
Since we seek a lower bound, it suffices to lower bound each summand\. For any fixed trajectoryσ\\sigma:

ℙ⁡\[E∧trajectory​σ\]=ℙ⁡\[E\|trajectory​σ\]⋅ℙ⁡\[trajectory​σ\]\\mathbb\{P\}\[E\\land\\text\{trajectory \}\\sigma\]=\\mathbb\{P\}\[E\\,\|\\,\\text\{trajectory \}\\sigma\]\\cdot\\mathbb\{P\}\[\\text\{trajectory \}\\sigma\]\(18\)
Step 2: Decomposition Along Trajectory\.Partition thekkturns into intra\-mode turnsℐ=\{t:σ⁡\(t\)=σ⁡\(t\+1\)\}\\mathcal\{I\}=\\\{t:\\sigma\(t\)=\\sigma\(t\+1\)\\\}and transition turns𝒯=\{t:σ⁡\(t\)≠σ⁡\(t\+1\)\}\\mathcal\{T\}=\\\{t:\\sigma\(t\)\\neq\\sigma\(t\+1\)\\\}\(with\|𝒯\|=τ⁡\(σ\)\|\\mathcal\{T\}\|=\\tau\(\\sigma\)\)\.

For intra\-mode turns in modemjm\_\{j\}, since the per\-turn safety boundρmjin​\(ϵ\)\\rho\_\{m\_\{j\}\}^\{\\mathrm\{in\}\}\(\\epsilon\)holds uniformly for all states within𝒮mj\\mathcal\{S\}\_\{m\_\{j\}\}:

ℙ⁡\[⋀t∈ℐj𝖲𝖺𝖿𝖾⁡\(st\)\|stay in​mj\]≥\(ρmjin​\(ϵ\)\)\|ℐj\|\\mathbb\{P\}\\left\[\\bigwedge\_\{t\\in\\mathcal\{I\}\_\{j\}\}\\mathsf\{Safe\}\(s\_\{t\}\)\\,\\bigg\|\\,\\text\{stay in \}m\_\{j\}\\right\]\\geq\\left\(\\rho\_\{m\_\{j\}\}^\{\\mathrm\{in\}\}\(\\epsilon\)\\right\)^\{\|\\mathcal\{I\}\_\{j\}\|\}\(19\)whereℐj=\{t∈ℐ:σ⁡\(t\)=mj\}\\mathcal\{I\}\_\{j\}=\\\{t\\in\\mathcal\{I\}:\\sigma\(t\)=m\_\{j\}\\\}and\|ℐj\|=nj​\(σ\)\|\\mathcal\{I\}\_\{j\}\|=n\_\{j\}\(\\sigma\)\.

For transition turns frommim\_\{i\}tomjm\_\{j\}:

ℙ\[𝖲𝖺𝖿𝖾\(st\)\|st−1∈𝒮mi,st∈𝒮mj\]≥ρi→jtr\(ϵ\)\\mathbb\{P\}\[\\mathsf\{Safe\}\(s\_\{t\}\)\\,\|\\,s\_\{t\-1\}\\in\\mathcal\{S\}\_\{m\_\{i\}\},s\_\{t\}\\in\\mathcal\{S\}\_\{m\_\{j\}\}\]\\geq\\rho\_\{i\\to j\}^\{\\mathrm\{tr\}\}\(\\epsilon\)\(20\)
Step 3: Overlap Penalty \(Factor1/κ1/\\kappa\)\.

###### Lemma E\.1\(Overlap Penalty\)\.

For any mode decomposition with overlapκ=maxs⁡\|\{i:s∈𝒮mi\}\|\\kappa=\\max\_\{s\}\|\\\{i:s\\in\\mathcal\{S\}\_\{m\_\{i\}\}\\\}\|:

ρk​\(s0,π,ϵ\)≥1κ⋅infσℙ⁡\[E\|trajectory​σ\]\\rho\_\{k\}\(s\_\{0\},\\pi,\\epsilon\)\\geq\\frac\{1\}\{\\kappa\}\\cdot\\inf\_\{\\sigma\}\\mathbb\{P\}\[E\\,\|\\,\\text\{trajectory \}\\sigma\]\(21\)

###### Proof\.

Fix a deterministic tie\-breaking rule: assign eachsts\_\{t\}to the modemjm\_\{j\}with the smallest indexjjsuch thatst∈𝒮mjs\_\{t\}\\in\\mathcal\{S\}\_\{m\_\{j\}\}\. Under this rule, every state sequence maps to a unique trajectoryσ\\sigma, soℙ\[E\]=∑σℙ\[E∩\{traj=σ\}\]\\mathbb\{P\}\[E\]=\\sum\_\{\\sigma\}\\mathbb\{P\}\[E\\cap\\\{\\text\{traj\}=\\sigma\\\}\]\.

For non\-overlapping decompositions \(κ=1\\kappa=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\\kappa\>1\), we introduce the1/κ1/\\kappafactor as follows\. When a statests\_\{t\}lies in multiple modesℳ⁡\(st\)=\{i:st∈𝒮mi\}\\mathcal\{M\}\(s\_\{t\}\)=\\\{i:s\_\{t\}\\in\\mathcal\{S\}\_\{m\_\{i\}\}\\\}with\|ℳ⁡\(st\)\|≤κ\|\\mathcal\{M\}\(s\_\{t\}\)\|\\leq\\kappa, the adversary can steer the trajectory through the mode with the weakest safety bound\. Letρmin​\(s\)=mini∈ℳ⁡\(s\)⁡ρmiin\\rho\_\{\\min\}\(s\)=\\min\_\{i\\in\\mathcal\{M\}\(s\)\}\\rho\_\{m\_\{i\}\}^\{\\mathrm\{in\}\}andρmax​\(s\)=maxi∈ℳ⁡\(s\)⁡ρmiin\\rho\_\{\\max\}\(s\)=\\max\_\{i\\in\\mathcal\{M\}\(s\)\}\\rho\_\{m\_\{i\}\}^\{\\mathrm\{in\}\}denote the weakest and strongest per\-turn bounds available at statess\. Our compositional bound \(which usesρmjin\\rho\_\{m\_\{j\}\}^\{\\mathrm\{in\}\}for the assigned modemjm\_\{j\}\) may overestimate the actual per\-turn safety by usingρmjin\\rho\_\{m\_\{j\}\}^\{\\mathrm\{in\}\}when the adversary achievesρmin​\(s\)\\rho\_\{\\min\}\(s\)\. Since each state belongs to at mostκ\\kappamodes, and eachρmiin≤1\\rho\_\{m\_\{i\}\}^\{\\mathrm\{in\}\}\\leq 1, the per\-turn overestimation is bounded:ρmjin/ρmin​\(s\)≤κ\\rho\_\{m\_\{j\}\}^\{\\mathrm\{in\}\}/\\rho\_\{\\min\}\(s\)\\leq\\kappain the worst case \(when modes have safety probabilities1/κ,2/κ,…,11/\\kappa,2/\\kappa,\\ldots,1\)\. Applying this correction across allkkturns conservatively as a single multiplicative factor yields:

ρk≥1κ⋅infσℙ⁡\[E\|σ\]\\rho\_\{k\}\\geq\\frac\{1\}\{\\kappa\}\\cdot\\inf\_\{\\sigma\}\\mathbb\{P\}\[E\\,\|\\,\\sigma\]\(22\)Whenκ=1\\kappa=1, each state belongs to exactly one mode and the factor disappears\. ∎

Multiplying the per\-turn bounds for trajectoryσ\\sigma:

ℙ⁡\[E\|trajectory​σ\]≥∏j=1M\(ρmjin\)nj​\(σ\)⋅∏\(i,j\)∈Trans⁡\(σ\)ρi→jtr\\mathbb\{P\}\[E\\,\|\\,\\text\{trajectory \}\\sigma\]\\geq\\prod\_\{j=1\}^\{M\}\\left\(\\rho\_\{m\_\{j\}\}^\{\\mathrm\{in\}\}\\right\)^\{n\_\{j\}\(\\sigma\)\}\\cdot\\prod\_\{\(i,j\)\\in\\mathrm\{Trans\}\(\\sigma\)\}\\rho\_\{i\\to j\}^\{\\mathrm\{tr\}\}\(23\)By Lemma[E\.1](https://arxiv.org/html/2608.20820#A5.Thmtheorem1), the worst\-case over mode assignments \(exploited by the adversary when states lie in overlap regions\) introduces the1/κ1/\\kappafactor\.

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\]\\rho\_\{k\}\(s\_\{0\},\\pi,\\epsilon\)=\\inf\_\{\\nu\}\\mathbb\{P\}\[E\]\\geq\\frac\{1\}\{\\kappa\}\\cdot\\inf\_\{\\sigma\\in\\Sigma\_\{k\}\(\\mathcal\{M\},s\_\{0\}\)\}\\left\[\\prod\_\{j\}\\left\(\\rho\_\{m\_\{j\}\}^\{\\mathrm\{in\}\}\\right\)^\{n\_\{j\}\(\\sigma\)\}\\cdot\\prod\_\{\(i,j\)\}\\rho\_\{i\\to j\}^\{\\mathrm\{tr\}\}\\right\]\(24\)

### E\.3Proof of Corollary[3\.2](https://arxiv.org/html/2608.20820#S3.Thmtheorem2)

From Theorem[3\.1](https://arxiv.org/html/2608.20820#S3.Thmtheorem1), withnj​\(σ\)n\_\{j\}\(\\sigma\)summing tok−τk\-\\tau\(non\-transition turns\):

ρk≥1κ​∏j\(1−δ\)nj​\(σ\)⋅γτ=1κ​\(1−δ\)k−τ​γτ\\rho\_\{k\}\\geq\\frac\{1\}\{\\kappa\}\\prod\_\{j\}\(1\-\\delta\)^\{n\_\{j\}\(\\sigma\)\}\\cdot\\gamma^\{\\tau\}=\\frac\{1\}\{\\kappa\}\(1\-\\delta\)^\{k\-\\tau\}\\gamma^\{\\tau\}\(25\)
The inequality1κ​\(1−δ\)k−τ​γτ\>p¯k\\frac\{1\}\{\\kappa\}\(1\-\\delta\)^\{k\-\\tau\}\\gamma^\{\\tau\}\>\\underline\{p\}^\{\\,k\}rearranges to the stated condition onτ\\tau\.

### E\.4Proof of Proposition[3\.4](https://arxiv.org/html/2608.20820#S3.Thmtheorem4)

Define value functionVt​\(m\)V\_\{t\}\(m\)= minimum certified lower bound achievable inttturns ending in modemm\. InitializeV0​\(m\)=1V\_\{0\}\(m\)=1for modes containings0s\_\{0\}, elseV0​\(m\)=0V\_\{0\}\(m\)=0\. Recurrence:

Vt\+1\(mj\)=min\{Vt\(mj\)⋅ρmjin,mini:\(mi,mj\)∈EVt\(mi\)⋅ρi→jtr\}V\_\{t\+1\}\(m\_\{j\}\)=\\min\\left\\\{V\_\{t\}\(m\_\{j\}\)\\cdot\\rho\_\{m\_\{j\}\}^\{\\mathrm\{in\}\},\\min\_\{i:\(m\_\{i\},m\_\{j\}\)\\in E\}V\_\{t\}\(m\_\{i\}\)\\cdot\\rho\_\{i\\to j\}^\{\\mathrm\{tr\}\}\\right\\\}\(26\)The first term corresponds to staying inmjm\_\{j\}; the second to transitioning from somemim\_\{i\}\. Final answer:ρk≥1κ​minm​Vk​\(m\)\\rho\_\{k\}\\geq\\frac\{1\}\{\\kappa\}\\min\_\{m\}V\_\{k\}\(m\)\.

### E\.5Proof of Theorem[3\.5](https://arxiv.org/html/2608.20820#S3.Thmtheorem5)

Step 1: First Bound \(ρk≥βk\\rho\_\{k\}\\geq\\beta^\{k\}\)\.LetAt=\{𝖲𝖺𝖿𝖾\(st\)=1∧Δ\(st\)≥\(1−α\)Δ\(st−1\)\}A\_\{t\}=\\\{\\mathsf\{Safe\}\(s\_\{t\}\)=1\\land\\Delta\(s\_\{t\}\)\\geq\(1\-\\alpha\)\\Delta\(s\_\{t\-1\}\)\\\}denote the event that the persistence condition holds at turntt\. By Definition[2](https://arxiv.org/html/2608.20820#Thmdefinition2), for any adversarial policy and any safe statest−1∈𝒮\+s\_\{t\-1\}\\in\\mathcal\{S\}\_\{\+\}withΔ⁡\(st−1\)\>0\\Delta\(s\_\{t\-1\}\)\>0:

ℙ\[At\|st−1∈𝒮\+,Δ\(st−1\)\>0\]≥β\\mathbb\{P\}\[A\_\{t\}\\,\|\\,s\_\{t\-1\}\\in\\mathcal\{S\}\_\{\+\},\\Delta\(s\_\{t\-1\}\)\>0\]\\geq\\beta\(27\)
We verify the precondition inductively\. Att=1t=1:s0∈𝒮\+s\_\{0\}\\in\\mathcal\{S\}\_\{\+\}withΔ⁡\(s0\)=Δ0\>0\\Delta\(s\_\{0\}\)=\\Delta\_\{0\}\>0by assumption\. At turnt\>1t\>1: on the event⋀i=1t−1Ai\\bigwedge\_\{i=1\}^\{t\-1\}A\_\{i\}, we have𝖲𝖺𝖿𝖾⁡\(st−1\)=1\\mathsf\{Safe\}\(s\_\{t\-1\}\)=1\(sost−1∈𝒮\+s\_\{t\-1\}\\in\\mathcal\{S\}\_\{\+\}\) andΔ⁡\(st−1\)≥\(1−α\)t−1​Δ0\>0\\Delta\(s\_\{t\-1\}\)\\geq\(1\-\\alpha\)^\{t\-1\}\\Delta\_\{0\}\>0\(sinceα<1\\alpha<1\)\. Therefore:

ℙ⁡\[At\|⋀i=1t−1Ai\]≥β\\mathbb\{P\}\\left\[A\_\{t\}\\,\\bigg\|\\,\\bigwedge\_\{i=1\}^\{t\-1\}A\_\{i\}\\right\]\\geq\\beta\(28\)
By the chain rule:

ℙ⁡\[⋀t=1kAt\]=∏t=1kℙ⁡\[At\|⋀i=1t−1Ai\]≥βk\\mathbb\{P\}\\left\[\\bigwedge\_\{t=1\}^\{k\}A\_\{t\}\\right\]=\\prod\_\{t=1\}^\{k\}\\mathbb\{P\}\\left\[A\_\{t\}\\,\\bigg\|\\,\\bigwedge\_\{i=1\}^\{t\-1\}A\_\{i\}\\right\]\\geq\\beta^\{k\}\(29\)
On the event⋀t=1kAt\\bigwedge\_\{t=1\}^\{k\}A\_\{t\}, safety holds at every turn \(𝖲𝖺𝖿𝖾⁡\(st\)=1\\mathsf\{Safe\}\(s\_\{t\}\)=1is part of the persistence condition\)\. Therefore:

ρk=infνℙ⁡\[⋀t=1k𝖲𝖺𝖿𝖾⁡\(st\)\]≥ℙ⁡\[⋀t=1kAt\]≥βk\\rho\_\{k\}=\\inf\_\{\\nu\}\\mathbb\{P\}\\left\[\\bigwedge\_\{t=1\}^\{k\}\\mathsf\{Safe\}\(s\_\{t\}\)\\right\]\\geq\\mathbb\{P\}\\left\[\\bigwedge\_\{t=1\}^\{k\}A\_\{t\}\\right\]\\geq\\beta^\{k\}\(30\)
Step 2: Complementary Linear Characterization\.We derive a union\-bound\-based formula that, while looser thanβk\\beta^\{k\}in general, provides an interpretable horizon estimate\. DefineUt=\{𝖲𝖺𝖿𝖾\(st\)=0\}U\_\{t\}=\\\{\\mathsf\{Safe\}\(s\_\{t\}\)=0\\\}as the event that turnttis unsafe\. Note thatUt⊆AtcU\_\{t\}\\subseteq A\_\{t\}^\{c\}\(unsafety implies persistence failure\), since the persistence eventAtA\_\{t\}requires𝖲𝖺𝖿𝖾⁡\(st\)=1\\mathsf\{Safe\}\(s\_\{t\}\)=1\.

For each turntt, conditioned on all previous turns being safe \(⋀i=1t−1𝖲𝖺𝖿𝖾⁡\(si\)=1\\bigwedge\_\{i=1\}^\{t\-1\}\\mathsf\{Safe\}\(s\_\{i\}\)=1, which ensuresst−1∈𝒮\+s\_\{t\-1\}\\in\\mathcal\{S\}\_\{\+\}\), the openness of𝒮\+\\mathcal\{S\}\_\{\+\}\(assumed in Section[2](https://arxiv.org/html/2608.20820#S2)\) guaranteesΔ⁡\(st−1\)\>0\\Delta\(s\_\{t\-1\}\)\>0\. The persistence definition then gives:

ℙ⁡\[Ut\|⋀i=1t−1𝖲𝖺𝖿𝖾⁡\(si\)=1\]≤1−β\\mathbb\{P\}\\left\[U\_\{t\}\\,\\bigg\|\\,\\bigwedge\_\{i=1\}^\{t\-1\}\\mathsf\{Safe\}\(s\_\{i\}\)=1\\right\]\\leq 1\-\\beta\(31\)sinceℙ\[At\|⋅\]≥β\\mathbb\{P\}\[A\_\{t\}\|\\cdot\]\\geq\\betaandAt⊆\{𝖲𝖺𝖿𝖾\(st\)=1\}=UtcA\_\{t\}\\subseteq\\\{\\mathsf\{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−β\)\\mathbb\{P\}\\left\[\\exists\\,t\\leq k:\\mathsf\{Safe\}\(s\_\{t\}\)=0\\right\]=\\sum\_\{t=1\}^\{k\}\\mathbb\{P\}\\left\[U\_\{t\}\\cap\\bigwedge\_\{i=1\}^\{t\-1\}U\_\{i\}^\{c\}\\right\]\\leq\\sum\_\{t=1\}^\{k\}\(1\-\\beta\)=k\(1\-\\beta\)\(32\)
Therefore:

ρk=infνℙ⁡\[⋀t=1k𝖲𝖺𝖿𝖾⁡\(st\)\]≥1−k⁡\(1−β\)\\rho\_\{k\}=\\inf\_\{\\nu\}\\mathbb\{P\}\\left\[\\bigwedge\_\{t=1\}^\{k\}\\mathsf\{Safe\}\(s\_\{t\}\)\\right\]\\geq 1\-k\(1\-\\beta\)\(33\)which is the linear degradation bound\. This holds wheneverk⁡\(1−β\)<1k\(1\-\\beta\)<1; forβ\\betaclose to 1 the bound is non\-trivial for horizonsk≪1/\(1−β\)k\\ll 1/\(1\-\\beta\)\.

### E\.6Proof of Proposition[3\.7](https://arxiv.org/html/2608.20820#S3.Thmtheorem7)

Fors∈𝒮\+s\\in\\mathcal\{S\}\_\{\+\}with marginΔ⁡\(s\)\\Delta\(s\), consider any adversarialu∈ℬϵu\\in\\mathcal\{B\}\_\{\\epsilon\}and responserrwith‖r−r∗‖≤η\\\|r\-r^\{\*\}\\\|\\leq\\eta\(ordr​\(r,r∗\)≤ηd\_\{r\}\(r,r^\{\*\}\)\\leq\\eta\)\. The new states′=T⁡\(s,u,r\)s^\{\\prime\}=T\(s,u,r\)satisfies:

‖s′−s‖\\displaystyle\\\|s^\{\\prime\}\-s\\\|≤‖T⁡\(s,u,r\)−T⁡\(s,u∗,r∗\)‖\+‖T⁡\(s,u∗,r∗\)−s‖\\displaystyle\\leq\\\|T\(s,u,r\)\-T\(s,u^\{\*\},r^\{\*\}\)\\\|\+\\\|T\(s,u^\{\*\},r^\{\*\}\)\-s\\\|\(34\)≤Lr⋅η\+Lu⋅ϵ\+δT\\displaystyle\\leq L\_\{r\}\\cdot\\eta\+L\_\{u\}\\cdot\\epsilon\+\\delta\_\{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\)\\Delta\(s^\{\\prime\}\)\\geq\\Delta\(s\)\-\\\|s^\{\\prime\}\-s\\\|\\geq\\Delta\(s\)\-\(L\_\{u\}\\epsilon\+L\_\{r\}\\eta\+\\delta\_\{T\}\)\(36\)
ForΔ⁡\(s′\)≥\(1−α\)​Δ​\(s\)\\Delta\(s^\{\\prime\}\)\\geq\(1\-\\alpha\)\\Delta\(s\), we need:

Δ⁡\(s\)−\(Lu​ϵ\+Lr​η\+δT\)≥\(1−α\)​Δ​\(s\)⟹α≥Lu​ϵ\+Lr​η\+δTΔ⁡\(s\)\\Delta\(s\)\-\(L\_\{u\}\\epsilon\+L\_\{r\}\\eta\+\\delta\_\{T\}\)\\geq\(1\-\\alpha\)\\Delta\(s\)\\implies\\alpha\\geq\\frac\{L\_\{u\}\\epsilon\+L\_\{r\}\\eta\+\\delta\_\{T\}\}\{\\Delta\(s\)\}\(37\)
Taking the worst case overΔ⁡\(s\)≥δ\\Delta\(s\)\\geq\\deltaand noting the response concentration holds with probabilityp0p\_\{0\}yields the result\.

### E\.7Proof of Theorem[3\.8](https://arxiv.org/html/2608.20820#S3.Thmtheorem8)

We construct a system that achieves the upper bound exactly, showing it is tight\.

Step 1: Matching Construction\.For each modemjm\_\{j\}, construct transition dynamicsTjT\_\{j\}such that, for alls∈𝒮mjs\\in\\mathcal\{S\}\_\{m\_\{j\}\}and allu∈ℬϵu\\in\\mathcal\{B\}\_\{\\epsilon\}, the per\-turn safety probability is exactlyρmjin\\rho\_\{m\_\{j\}\}^\{\\mathrm\{in\}\}, independently across turns\. This is achievable: letTj​\(s,u,r\)T\_\{j\}\(s,u,r\)draw the next state from a distribution supported on𝒮mj\\mathcal\{S\}\_\{m\_\{j\}\}withℙ\[𝖲𝖺𝖿𝖾\(s′\)=1∧s′∈𝒮mj\]=ρmjin\\mathbb\{P\}\[\\mathsf\{Safe\}\(s^\{\\prime\}\)=1\\land s^\{\\prime\}\\in\\mathcal\{S\}\_\{m\_\{j\}\}\]=\\rho\_\{m\_\{j\}\}^\{\\mathrm\{in\}\}, independently of\(s,u\)\(s,u\)\. Similarly, for transitions frommim\_\{i\}tomjm\_\{j\}, setℙ⁡\[𝖲𝖺𝖿𝖾⁡\(s′\)\]=ρi→jtr\\mathbb\{P\}\[\\mathsf\{Safe\}\(s^\{\\prime\}\)\]=\\rho\_\{i\\to j\}^\{\\mathrm\{tr\}\}independently\.

Step 2: Safety Probability Under This Construction\.Under the constructed system, per\-turn outcomes are independent given the mode trajectoryσ\\sigma\. For intra\-mode turns inmjm\_\{j\}, each turn is safe independently with probabilityρmjin\\rho\_\{m\_\{j\}\}^\{\\mathrm\{in\}\}\. For transition turns frommim\_\{i\}tomjm\_\{j\}, safety holds independently with probabilityρi→jtr\\rho\_\{i\\to j\}^\{\\mathrm\{tr\}\}\. Therefore:

ρk=∏j=1M\(ρmjin\)nj⋅∏\(i,j\)∈Transρi→jtr\\rho\_\{k\}=\\prod\_\{j=1\}^\{M\}\\left\(\\rho\_\{m\_\{j\}\}^\{\\mathrm\{in\}\}\\right\)^\{n\_\{j\}\}\\cdot\\prod\_\{\(i,j\)\\in\\mathrm\{Trans\}\}\\rho\_\{i\\to j\}^\{\\mathrm\{tr\}\}\(38\)
This matches the compositional lower bound from Theorem[3\.1](https://arxiv.org/html/2608.20820#S3.Thmtheorem1)\(withκ=1\\kappa=1\), so the bound is tight for non\-overlapping decompositions\.

###### Lemma E\.2\(Mode\-Optimal Attack Existence\)\.

For each modemmand states∈𝒮ms\\in\\mathcal\{S\}\_\{m\}, the optimal attacku∗​\(s\)=arg​minu∈ℬϵ⁡ℙr∼π​\[𝖲𝖺𝖿𝖾⁡\(T⁡\(s,u,r\)\)\]u^\{\*\}\(s\)=\\argmin\_\{u\\in\\mathcal\{B\}\_\{\\epsilon\}\}\\mathbb\{P\}\_\{r\\sim\\pi\}\[\\mathsf\{Safe\}\(T\(s,u,r\)\)\]exists by compactness ofℬϵ\\mathcal\{B\}\_\{\\epsilon\}\(finite vocabulary, bounded length\) and achieves the infimum in the intra\-mode safety definition \(Appendix[B\.5](https://arxiv.org/html/2608.20820#A2.SS5)\)\.

### E\.8Proof of Theorem[3\.10](https://arxiv.org/html/2608.20820#S3.Thmtheorem10)

We construct a memoryless conversational system\. Let𝒮=\[0,1\]\\mathcal\{S\}=\[0,1\]and𝒮\+=\[0,p\]\\mathcal\{S\}\_\{\+\}=\[0,p\]so that𝖲𝖺𝖿𝖾\(s\)=𝟏\[s≤p\]\\mathsf\{Safe\}\(s\)=\\mathbf\{1\}\[s\\leq p\]\. Define the transition functionT⁡\(s,u,r\)=rT\(s,u,r\)=rwherer∼Uniform⁡\[0,1\]r\\sim\\mathrm\{Uniform\}\[0,1\]independently of\(s,u\)\(s,u\)\. Under this system, the adversary’s choice ofu∈ℬϵu\\in\\mathcal\{B\}\_\{\\epsilon\}has no effect on the next state, and the per\-turn safety probability isℙ\[𝖲𝖺𝖿𝖾\(s′\)=1\]=p\\mathbb\{P\}\[\\mathsf\{Safe\}\(s^\{\\prime\}\)=1\]=pregardless of the current state or adversary’s action\. Since turns are independent:

ρk=pk=p¯k\\rho\_\{k\}=p^\{k\}=\\underline\{p\}^\{\\,k\}\(39\)Furthermore, no mode decomposition can improve the bound: every mode has identical intra\-mode safetypp, and transitions do not change the safety probability\. No persistence property holds withβ\>p\\beta\>p, since the marginΔ⁡\(s′\)=max⁡\(0,p−s′\)\\Delta\(s^\{\\prime\}\)=\\max\(0,p\-s^\{\\prime\}\)is independent ofΔ⁡\(s\)\\Delta\(s\)\.

This shows that our structural assumptions \(modes, persistence\) are necessary to*guarantee*sub\-exponential bounds, not merely sufficient for achieving them\.

### E\.9Proof of Theorem[3\.11](https://arxiv.org/html/2608.20820#S3.Thmtheorem11)

We combine Theorems[3\.1](https://arxiv.org/html/2608.20820#S3.Thmtheorem1)and[3\.5](https://arxiv.org/html/2608.20820#S3.Thmtheorem5)\. Letβ^=minm⁡β^m\\hat\{\\beta\}=\\min\_\{m\}\\hat\{\\beta\}\_\{m\}denote the global persistence parameter\.

Step 1: Factoring out persistence\.Theorem[3\.5](https://arxiv.org/html/2608.20820#S3.Thmtheorem5)gives an overall boundβk\\beta^\{k\}, which factors as a per\-turn contribution ofβ\\beta\. We decompose thekk\-turn compositional product into a persistence baseline \(βk\\beta^\{k\}\) and a residual capturing mode\-specific deviations above this baseline\.

For a mode trajectoryσ\\sigmawithnj​\(σ\)n\_\{j\}\(\\sigma\)intra\-mode turns in modemjm\_\{j\}andτ⁡\(σ\)\\tau\(\\sigma\)transitions:

∏j\(ρmjin\)nj​\(σ\)=β∑jnj​\(σ\)⋅∏j\(ρmjinβ\)nj​\(σ\)=βk−τ⁡\(σ\)⋅∏j\(ρmjinβ\)nj​\(σ\)\\prod\_\{j\}\(\\rho\_\{m\_\{j\}\}^\{\\mathrm\{in\}\}\)^\{n\_\{j\}\(\\sigma\)\}=\\beta^\{\\sum\_\{j\}n\_\{j\}\(\\sigma\)\}\\cdot\\prod\_\{j\}\\left\(\\frac\{\\rho\_\{m\_\{j\}\}^\{\\mathrm\{in\}\}\}\{\\beta\}\\right\)^\{n\_\{j\}\(\\sigma\)\}=\\beta^\{k\-\\tau\(\\sigma\)\}\\cdot\\prod\_\{j\}\\left\(\\frac\{\\rho\_\{m\_\{j\}\}^\{\\mathrm\{in\}\}\}\{\\beta\}\\right\)^\{n\_\{j\}\(\\sigma\)\}\(40\)
Step 2: Applying compositional certification\.Substituting into Theorem[3\.1](https://arxiv.org/html/2608.20820#S3.Thmtheorem1):

ρk≥1κ⋅βk−τ⋅infσ\[∏j\(ρmjinβ\)nj​\(σ\)⋅∏\(i,j\)ρi→jtr\]\\rho\_\{k\}\\geq\\frac\{1\}\{\\kappa\}\\cdot\\beta^\{k\-\\tau\}\\cdot\\inf\_\{\\sigma\}\\left\[\\prod\_\{j\}\\left\(\\frac\{\\rho\_\{m\_\{j\}\}^\{\\mathrm\{in\}\}\}\{\\beta\}\\right\)^\{n\_\{j\}\(\\sigma\)\}\\cdot\\prod\_\{\(i,j\)\}\\rho\_\{i\\to j\}^\{\\mathrm\{tr\}\}\\right\]\(41\)Sinceβk−τ≥βk\\beta^\{k\-\\tau\}\\geq\\beta^\{k\}\(asτ≥0\\tau\\geq 0andβ≤1\\beta\\leq 1\), we obtain the stated bound withβk\\beta^\{k\}replacingβk−τ\\beta^\{k\-\\tau\}\(a conservative simplification\)\.

Step 3: Simplification when persistence dominates\.Whenρmjin≥β\\rho\_\{m\_\{j\}\}^\{\\mathrm\{in\}\}\\geq\\betafor all modes, each ratioρmjin/β≥1\\rho\_\{m\_\{j\}\}^\{\\mathrm\{in\}\}/\\beta\\geq 1, so∏j\(ρmjin/β\)nj≥1\\prod\_\{j\}\(\\rho\_\{m\_\{j\}\}^\{\\mathrm\{in\}\}/\\beta\)^\{n\_\{j\}\}\\geq 1\. The infimum over trajectories is then dominated by the transition terms∏\(i,j\)ρi→jtr≥γτ\\prod\_\{\(i,j\)\}\\rho\_\{i\\to j\}^\{\\mathrm\{tr\}\}\\geq\\gamma^\{\\tau\}, yieldingρk≥βk​γτ/κ\\rho\_\{k\}\\geq\\beta^\{k\}\\gamma^\{\\tau\}/\\kappa\.

## Appendix FMode 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 embeddingss\(i\)=ϕ⁡\(h\(i\)\)s^\{\(i\)\}=\\phi\(h^\{\(i\)\}\)using a pretrained encoder; \(2\) applykk\-means to obtain cluster centers\{c1,…,cM\}=KMeans​\(\{s\(i\)\},M\)\\\{c\_\{1\},\\ldots,c\_\{M\}\\\}=\\text\{KMeans\}\(\\\{s^\{\(i\)\}\\\},M\); and \(3\) define mode regions𝒮mj=\{s:‖s−cj‖≤rj\}\\mathcal\{S\}\_\{m\_\{j\}\}=\\\{s:\\\|s\-c\_\{j\}\\\|\\leq r\_\{j\}\\\}with radiusrjr\_\{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 topicjjcorresponds to modemjm\_\{j\}; the region𝒮mj\\mathcal\{S\}\_\{m\_\{j\}\}is defined via a topic posterior threshold \(e\.g\., assignsstomjm\_\{j\}when the posterior for topicjjexceeds 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\.1Persistence Parameter Estimation

Algorithm[1](https://arxiv.org/html/2608.20820#algorithm1)callsEstimatePersistence\(m\)\(m\)to obtain\(α^m,β^m\)\(\\hat\{\\alpha\}\_\{m\},\\hat\{\\beta\}\_\{m\}\)for each mode\. We implement this as follows\.

Given modemmwith region𝒮m\\mathcal\{S\}\_\{m\}, sampleNpN\_\{p\}state–input pairs\(s,u\)\(s,u\)wheres∈𝒮m∩𝒮\+s\\in\\mathcal\{S\}\_\{m\}\\cap\\mathcal\{S\}\_\{\+\}andu∈ℬϵu\\in\\mathcal\{B\}\_\{\\epsilon\}\. For each pair, generate responser∼π\(⋅\|s,u\)r\\sim\\pi\(\\cdot\|s,u\)and compute the next states′=T⁡\(s,u,r\)s^\{\\prime\}=T\(s,u,r\)\. Record the safety margin ratioδi=Δ⁡\(s′\)/Δ⁡\(s\)\\delta\_\{i\}=\\Delta\(s^\{\\prime\}\)/\\Delta\(s\)when𝖲𝖺𝖿𝖾⁡\(s′\)=1\\mathsf\{Safe\}\(s^\{\\prime\}\)=1, and mark as failure otherwise\. The persistence parameters are estimated as:

α^m\\displaystyle\\hat\{\\alpha\}\_\{m\}=1−Q0\.05​\(\{δi:𝖲𝖺𝖿𝖾⁡\(si′\)=1\}\)\\displaystyle=1\-Q\_\{0\.05\}\\left\(\\\{\\delta\_\{i\}:\\mathsf\{Safe\}\(s^\{\\prime\}\_\{i\}\)=1\\\}\\right\)\(42\)β^m\\displaystyle\\hat\{\\beta\}\_\{m\}=1Np∑i=1Np𝟏\[𝖲𝖺𝖿𝖾\(si′\)=1∧Δ\(si′\)≥\(1−α^m\)Δ\(si\)\]\\displaystyle=\\frac\{1\}\{N\_\{p\}\}\\sum\_\{i=1\}^\{N\_\{p\}\}\\mathbf\{1\}\\left\[\\mathsf\{Safe\}\(s^\{\\prime\}\_\{i\}\)=1\\land\\Delta\(s^\{\\prime\}\_\{i\}\)\\geq\(1\-\\hat\{\\alpha\}\_\{m\}\)\\Delta\(s\_\{i\}\)\\right\]\(43\)whereQ0\.05Q\_\{0\.05\}denotes the 5th percentile\. We first estimateα^m\\hat\{\\alpha\}\_\{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\\hat\{\\beta\}\_\{m\}\. In our experiments we useNp=100N\_\{p\}=100samples per mode\. A Clopper–Pearson confidence interval at levelδconf=0\.05\\delta\_\{\\mathrm\{conf\}\}=0\.05is applied toβ^m\\hat\{\\beta\}\_\{m\}\(taking its lower endpoint\) to ensure the resulting certified bound is valid with high probability\.

## Appendix GSafety Detector Comparison

We compare two safety detection approaches used for certifying multi\-turn safety\. Thekeyword\-baseddetector \(default\) combines: \(i\) refusal patterns \(regex for “I cannot”, “I’m unable to”, etc\.\): responses matching these are labeled safe; \(ii\) an unsafe\-keyword list \(e\.g\., “how to make”, “bomb”, “illegal drug”\): responses containing these without refusal are labeled unsafe\. Theneural classifieruses 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](https://arxiv.org/html/2608.20820#S4.T4)reports the comparison\.

## Appendix HConcrete 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\\epsilon\{=\}5\.

Perturbation examples\.Valid perturbations withinℬϵ\\mathcal\{B\}\_\{\\epsilon\}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 overkkturns \(following the escalation pattern in[Russinovich et al\. 2025](https://arxiv.org/html/2608.20820#bib.bib18)\)\. 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ϵ\\epsilon\) are applied independently on top of the template text, combining semantic escalation withϵ\\epsilon\-bounded noise\. For horizonsk\>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ℝd\\mathbb\{R\}^\{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 bykk\-means on held\-out safe corpora\. Transitions occur when the dialogue shifts topics; boundary dialogues between modes are used to certifyρi→jtr\\rho\_\{i\\to j\}^\{\\mathrm\{tr\}\}\.

## Appendix INumerical 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\.1Data Generation and Parametric Model

Dialogue state embeddingss∈ℝds\\in\\mathbb\{R\}^\{d\}are generated via a Gaussian mixture:n=2,000n=2\{,\}000states fromM=4M=4Gaussians with Dirichlet mixing weights, centers scaled by 2\.0, and per\-cluster standard deviation 0\.5\. Mode decomposition useskk\-means on these states; cluster radii are set at the 90th percentile of within\-cluster distances\. ForM=4M\{=\}4, the overlapκ=1\\kappa\{=\}1\. Figure[3](https://arxiv.org/html/2608.20820#A9.F3)illustrates the data layout\.

The parametric model is a configurable Bernoulli policy: for intra\-mode turns it samples success \(safe response\) with rateρmin\\rho\_\{m\}^\{\\mathrm\{in\}\}, and for transitions frommim\_\{i\}tomjm\_\{j\}it samples with rateρi→jtr\\rho\_\{i\\to j\}^\{\\mathrm\{tr\}\}\. Parameters are set to match the theoretical values used in our analysis, permitting exact comparison of closed\-form bounds against empirical outcomes\.

![Refer to caption](https://arxiv.org/html/2608.20820v1/results/data_overview.png)Figure 3:Synthetic data overview\.
### I\.2Compositional Gain

Table[5](https://arxiv.org/html/2608.20820#A9.T5)reports the improvement ratioρcomp/ρnaive\\rho^\{\\mathrm\{comp\}\}/\\rho^\{\\mathrm\{naive\}\}for varying horizonkkand transition countτ\\tau\. Whenkkis small \(e\.g\.,k=5k\{=\}5\), the ratio can be<1<1because transition overhead dominates; the improvement becomes significant at largerkk\. When transitions are sparse \(τ=1\\tau\{=\}1\), compositional certification achieves 3\.38×\\timesimprovement atk=50k\{=\}50, consistent with Corollary[3\.2](https://arxiv.org/html/2608.20820#S3.Thmtheorem2)\. Finer granularity \(τ=3\\tau\{=\}3or55\) reduces the advantage as transition costs dominate\.

Table 5:Compositional Gain: improvement ratioρcomp/ρnaive\\rho^\{\\mathrm\{comp\}\}/\\rho^\{\\mathrm\{naive\}\}across horizons and transition counts\.k=5k\{=\}5k=10k\{=\}10k=20k\{=\}20k=50k\{=\}50τ=1\\tau\{=\}10\.830\.971\.333\.38τ=3\\tau\{=\}30\.430\.500\.681\.72τ=5\\tau\{=\}50\.220\.250\.350\.88
### I\.3Persistence Scaling

Atk=100k\{=\}100under\(α,β\)=\(0\.2,0\.98\)\(\\alpha,\\beta\)\{=\}\(0\.2,0\.98\), the persistence bound \(Theorem[3\.5](https://arxiv.org/html/2608.20820#S3.Thmtheorem5)\) exceeds the naive exponential reference by over 21×\\times, confirming that structural persistence yields dramatically better scaling than naive composition\.

### I\.4Mode Granularity, Empirical Validation, and Bound Tightness

Mode GranularityvariesM∈\{2,4,8,16\}M\\in\\\{2,4,8,16\\\}: coarser modes yield tighter bounds due to lower overlap and transition overhead\.Empirical Validationchecks empirical safety against certified bounds: 94% under static attack and 90% under Crescendo\-style attack, both above the certified 0\.67\.Pipeline Performancedemonstrates end\-to\-end improvement of 1\.86×\\timesover naive\.Bound Tightnessverifies that the compositional lower bound matches the information\-theoretic upper bound \(Corollary[3\.9](https://arxiv.org/html/2608.20820#S3.Thmtheorem9)\) for non\-overlapping decompositions \(κ=1\\kappa\{=\}1\)\.

![Refer to caption](https://arxiv.org/html/2608.20820v1/results/certification_bounds.png)\(a\)
![Refer to caption](https://arxiv.org/html/2608.20820v1/results/persistence_bounds.png)\(b\)

Figure 4:Compositional Gain \(left\) and Persistence Scaling \(right\): certified lower bounds vs\. horizon\.

## Appendix JExtended 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\.1Hyperparameter Summary

Table[6](https://arxiv.org/html/2608.20820#A10.T6)lists the hyperparameters for each experiment\. Default values arep¯=0\.95\\bar\{p\}=0\.95,ρin=0\.98\\rho^\{\\mathrm\{in\}\}=0\.98,γ=0\.7\\gamma=0\.7,κ=1\\kappa=1,ϵ=5\\epsilon=5,δ0=1\.0\\delta\_\{0\}=1\.0, andδmin=0\.1\\delta\_\{\\min\}=0\.1\. The perturbation budgetϵ\\epsilonis in edit\-distance units for the synthetic setting; we useϵ=5\\epsilon=5unless noted\.

Table 6:Per\-experiment hyperparameters\.ExperimentParameterValueComp\. Gainkk\{5,10,20,50\}\\\{5,10,20,50\\\}τ\\tau\{1,2,3,4,5\}\\\{1,2,3,4,5\\\}p¯,ρin,γ\\bar\{p\},\\rho^\{\\mathrm\{in\}\},\\gamma0\.95,0\.98,0\.70\.95,0\.98,0\.7Persist\. Scale\(α,β\)\(\\alpha,\\beta\)\(0\.05,0\.98\)\(0\.05,0\.98\),\(0\.1,0\.95\)\(0\.1,0\.95\),\(0\.2,0\.98\)\(0\.2,0\.98\)kk\{5,10,20,50,100\}\\\{5,10,20,50,100\\\}Mode Gran\.MM\{2,4,8,16\}\\\{2,4,8,16\\\}kk,dd2020,6464Emp\. Valid\.kk, trials1010,100100Attack typesStatic edit\-distance, Crescendo\-stylePipeline Perf\.NN,MM,kk5050,44,2020Bound Tight\.ρin\\rho^\{\\mathrm\{in\}\}per mode\(0\.95,0\.93,0\.90,0\.88\)\(0\.95,0\.93,0\.90,0\.88\)γ\\gamma,kk0\.850\.85,\{10,20,30,50,100\}\\\{10,20,30,50,100\\\}Production \(LLM\)ModelsLLaMA\-2, Vicuna, Llama\-3\.2, Qwen2\.5\-7B, GPT\-4o, Claude\-3\.5MM,kk,NN44,\{5,10,15,20\}\\\{5,10,15,20\\\},100100ϵ\\epsilon, embedding\{3,5,7\}\\\{3,5,7\\\}, sentence\-transformers
### J\.2Production Model Experiments

Open\-source models\(LLaMA\-2\-7B\-Chat, Vicuna\-7B, Llama\-3\.2\-3B, Qwen2\.5\-7B\-Instruct\) are loaded via Hugging Facetransformersand run on A100 \(40GB\)\.Closed\-source models\(GPT\-4o, Claude\-3\.5\-Sonnet\) are accessed via OpenAI and Anthropic APIs respectively\. Full certification atk∈\{5,10,15,20\}k\\in\\\{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](https://arxiv.org/html/2608.20820#bib.bib30)\)\(50 prompts per category: violence, illegal activities, hate speech; 150 total\)\. Dialogue embeddings for mode discovery are computed with sentence\-transformersall\-MiniLM\-L6\-v2onn=500n\{=\}500held\-out safe multi\-turn dialogues \(ShareGPT\-style\)\. Mode discovery useskk\-means withM∈\{2,4,8\}M\\in\\\{2,4,8\\\}; cluster radii are set at the 90th percentile\. For certification, we apply randomized smoothing per mode withN=100N\{=\}100perturbed prompts \(character\-level substitutions, insertions, deletions; edit distance≤ϵ\\leq\\epsilon\) and estimateρ^min\\hat\{\\rho\}\_\{m\}^\{\\mathrm\{in\}\}as the fraction of safe responses\. We varyϵ∈\{3,5,7\}\\epsilon\\in\\\{3,5,7\\\}for sensitivity analysis \(Table[2](https://arxiv.org/html/2608.20820#S4.T2)\)\. Transition safetyρ^i→jtr\\hat\{\\rho\}\_\{i\\to j\}^\{\\mathrm\{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](https://arxiv.org/html/2608.20820#S4.T4), Appendix[G](https://arxiv.org/html/2608.20820#A7)\)\. We deploy two attack types: static \(random edit\-distance perturbation at each turn\) and Crescendo\-style \(escalation from benign to harmful overkkturns\)\. Fraction of trials with all turns safe over 100 runs defines empirical safety\. The mode granularity ablation on LLaMA\-2\-7B\-Chat atk=5k\{=\}5yieldsρ^5=0\.39\\hat\{\\rho\}\_\{5\}\{=\}0\.39forM=2M\{=\}2\(κ=1\\kappa\{=\}1\),0\.360\.36forM=4M\{=\}4\(κ=1\\kappa\{=\}1\), and0\.250\.25forM=8M\{=\}8\(κ=3\\kappa\{=\}3\)\. The MTCR ablation \(Table[3](https://arxiv.org/html/2608.20820#S4.T3)\) compares the multiplicative reference, Persistence\-Only, Compositional\-Only, and the Combined bound acrossk∈\{5,10,15,20\}k\\in\\\{5,10,15,20\\\}\.

### J\.3Synthetic Data and Attack Details

States for synthetic experiments are sampled from a Gaussian mixture withMMcomponents\. Centers are drawn from𝒩⁡\(0,4​Id\)\\mathcal\{N\}\(0,4I\_\{d\}\)\(scale 2\.0\); per\-cluster standard deviation is 0\.5\. Mixing weights followDir⁡\(𝟏M\)\\mathrm\{Dir\}\(\\mathbf\{1\}\_\{M\}\)\. Mode decomposition useskk\-means on the states; cluster radii are set to the 90th percentile of within\-cluster distances\. For the Mode Granularity experiment with varyingMM, we usen=1000n=1000samples; for the main data overview,n=2000n=2000\.

The parametric model samples a Bernoulli with rateρmin\\rho\_\{m\}^\{\\mathrm\{in\}\}for intra\-mode turns andρi→jtr\\rho\_\{i\\to j\}^\{\\mathrm\{tr\}\}for transitions\. For the Empirical Validation experiment, we use conservative certification \(ρin=0\.96\\rho^\{\\mathrm\{in\}\}\{=\}0\.96, cert\. bound≈0\.67\\approx 0\.67\) and a stronger parametric model \(ρin=0\.99\\rho^\{\\mathrm\{in\}\}\{=\}0\.99, vulnerability=0\{=\}0\) so empirical safety reliably exceeds the certified bound; the static attack applies edit\-distance perturbations withinϵ\\epsilonat each turn; the Crescendo\-style attack escalates toward a target harmful prompt overkkturns, with perturbations constrained toℬϵ\\mathcal\{B\}\_\{\\epsilon\}per turn\.