acceptodds
Withdrawn from ICLR 2027

Certifying LLM Safety Across Adaptive Multi-Turn Conversations

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

A large class of language-model safety certificates is local: it bounds the effect of perturbing one prompt. A multi-turn jailbreak is different. The attacker observes each response, adapts the next message, and succeeds if any turn drives the conversation into an unsafe state. We formulate certification for this sequential event and introduce Multi-Turn Certified Robustness (MTCR), a composition layer that lifts valid one-step probability bounds to adaptive conversations. MTCR partitions safe dialogue histories into abstract states and certifies the safe probability mass transferred between them. A robust dynamic program then propagates this mass over the conversation horizon, retaining reachability and state-dependent risk that a global product discards. We further refine the abstraction with safety-margin bins, recording not only whether a trajectory remains safe but how close it moves toward the decision boundary. The resulting certificate requires neither independence across turns nor a fixed attack trajectory. Across four open-weight and two hosted language models, MTCR improves the certified lower bound over global worst-case multiplication at every evaluated horizon; on LLaMA-2-7B-Chat, the improvement grows from at five turns to at twenty turns. Controlled experiments isolate the source of this gain and recover exact survival probabilities when the abstract transition model is known. These results establish state-aware composition as a practical route from single-turn robustness to certifiable conversational safety.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
Multi-Turn Conversation, Certified Robustness, Large Language Models

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 4 reviews, above 27% of the others.
Reviewer_HqCJOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

MTCR composes local one-step safety certificates into a multi-turn guarantee against an adaptive attacker. Safe dialogue histories are partitioned into M cells (k-means over dialogue embeddings, optionally refined by safety-margin bins); a local oracle provides simultaneous lower bounds on one-step transition probabilities between cells; and a robust Bellman recursion propagates the substochastic matrix, giving a k-turn certificate e^T Q^k 1 without assuming independence or a fixed attack trajectory. The unified certificate takes the max of the global product, mode-only, mode-margin, and persistence (beta^k) bounds under one calibration event. The theory covers validity, finite-sample correction, dominance over the induced scalar bound, exactness for Bellman-sufficient abstractions, and an impossibility result showing exponential decay is unavoidable without state structure. On four open-weight and two hosted LLMs (AdvBench, edit distance epsilon=5), MTCR beats global multiplication at every horizon (mean gain 1.24x at k=5, 1.64x at k=10), with ablations over M, epsilon, safety predicate, and a controlled synthetic study.

Critical strengths
  1. The composition layer is clean, correct, and well scoped. Validity by Bellman induction, a single calibration event that avoids a union bound over horizons, and an exactness result paired with an impossibility result give a complete account of when state-aware composition helps and why. Any improved local verifier plugs in unchanged.
  2. The empirical analysis is honest. Six models, sensitivity to epsilon/M/predicate, a controlled process isolating composition from oracle quality, and reported failure modes (M=8 at fixed budget; dense estimated operators). The M-granularity trade-off — finer partitions lose because confidence penalties exceed structural gain — is the right way to read these results.
Critical weaknesses
  1. The certified threat model does not cover the motivating attack. The introduction motivates with Crescendo-style semantic escalation, but the certificate covers only character-level edits around a fixed reference message; escalation is "evaluated separately" and sits outside the certified set. The defining difficulty of multi-turn jailbreaks is that the attacker changes message content adaptively, so the demonstrated certificates are substantially narrower than the framing suggests.
  2. The abstraction-to-validity link is under-demonstrated. Cells come from k-means on MiniLM embeddings; validity within a cell rests on anchor covers, with uncovered histories routed to a zero-mass fallback. The paper reports neither cover fractions nor fallback mass in the production experiments, so one cannot tell how much of the conservatism (0.36 certified vs 66% observed at k=5) comes from coverage rather than the oracle — and coverage is exactly the part a practitioner must replicate.
Questions for authors
  1. In the six-model experiments, what fraction of evaluation trajectories hit the fallback cell? How does the certificate change as anchors per cell increase?
  2. The k-means abstraction is fitted on 500 held-out safe conversations. Do attacked trajectories stay within the certified cells, or do they drift into fallback (which would silently zero the certificate)?
  3. Can MTCR compose a semantic-level local oracle (e.g., a paraphrase certificate) at non-trivial scale? Even a small demonstration would close much of the gap with the motivating threat model.
  4. What margin Delta was used for the persistence certificate in the production experiments, and how sensitive is the unified bound to that choice?
Reviewer_QuNNOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduces Multi-Turn Certified Robustness (MTCR) as a valid certification of the adaptive multi-turn conversations. The author claim that the conventional method provides overly conservative bound by multiplying worst-case single-turn safety probabilities to get the lower bound for the multi-turn dialogue. MTCR solves this by mapping safe historical conversation to abstract sematic states and safety-margin bins. Then, the author constructs certified transition probabilities between states and applies dynamic programming to produce conversational safety bounds. The author conduct experiments in six LLMs to demonstrate that MTCR provides tighter certifier lower bounds.

Critical strengths
  1. The paper brings up a well-motivated problem and proposes state-aware certification with theoretical guarantees. The paper addresses an important limitation of existing single-turn certification methods and provides a mathematical framework for adaptive multi-turn safety without assuming independence between turns.
Critical weaknesses
  1. My first concern is the limited justification of practical safety certification. The proposed framework relies on estimated safety probabilities obtained from sampled LLM responses and automated safety predicates. Although the authors account for sampling uncertainty, the reliability of the safety labels is not sufficiently established. Furthermore, transition probabilities may be estimated from different conversation histories, while the theoretical guarantees require each bound to hold uniformly across all histories within an abstract state. The paper should better justify how the implemented certification procedure satisfies this requirement, particularly given that semantically similar histories may exhibit different safety behaviors.
  2. My second concern in the limited validity of the multi-turn evaluation. The paper motivates MTCR through adaptive multi-turn jailbreaks, but the experimental settings do not adequately reflect this threat model. The static perturbation setting does not clearly explain how single-turn AdvBench prompts are extended into multi-turn conversations. Meanwhile, the escalation setting relies on predefined five-turn templates. These settings provide limited evidence that the proposed framework is effective for realistic adaptive multi-turn jailbreaks. I suggest that the authors clarify the static conversation construction and evaluate stronger, response-adaptive attacks.
Questions for authors

Please refer to the Weaknesses section for my questions.

Reviewer_S92jOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes Multi-Turn Certified Robustness (MTCR), a framework for certifying LLM safety across adaptive multi-turn conversations. It uses state abstraction, safety margins, and robust dynamic programming to obtain tighter trajectory-level safety bounds than naive worst-case multiplication. The problem is important, and the theoretical framework is reasonable. However, I have concerns about the validity of the practical certification procedure and whether the experiments adequately support the paper's claims.

Critical strengths

1.The paper addresses a relevant problem that is not well covered by existing single-turn certification methods. Explicitly modeling history-dependent attacks is a meaningful step toward multi-turn safety guarantees.

2.The state-aware composition framework is well motivated. The theoretical results provide a reasonable foundation for propagating local safety guarantees without assuming independence across turns.

3.The evaluation covers six LLMs and shows consistent improvements over the global multiplicative baseline. The ablation studies also help explain the contributions of state abstraction and safety margins.

Critical weaknesses

1.The practical validity of the certificates remains unclear. The main theorem requires transition bounds that hold uniformly over all histories within each abstract state. The paper does not adequately explain how the local verifier and anchor coverage satisfy this requirement. Without a more rigorous justification, it is difficult to trust the reported certified bounds.

2.The experiments do not adequately evaluate adaptive attacks. The theoretical formulation considers history-dependent adversaries, but the certified evaluation is limited to character-level perturbations, while the escalation experiments rely on predefined templates. This leaves a substantial gap between the stated threat model and the experimental evidence.

3.The baseline comparison is too limited. Most results are compared against naive worst-case multiplication, which ignores state information by construction. Given the close connection to robust dynamic programming, stronger comparisons with state-aware or reachability-based methods are needed to establish the novelty and practical advantage of MTCR.

4.The safety predicates are not sufficiently validated. The evaluation relies on refusal matching and harmful-content classification, neither of which is validated against human judgments. Since the certificates are defined with respect to these predicates, their reliability directly affects how the safety guarantees should be interpreted.

5.The practical improvements are modest, and some experimental choices are questionable. At longer horizons, the absolute certified probabilities remain very low despite the reported relative gains. In addition, the two-state configuration produces a stronger certificate than the default four-state setting, but this choice is not adequately explained.

Questions for authors

See weakness

Reviewer_TrfeOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes Multi-Turn Certified Robustness (MTCR), a framework for certifying LLM safety across adaptive multi-turn conversations. It represents dialogue histories as abstract states and uses robust dynamic programming to combine local safety bounds into a trajectory-level certificate. Experiments on six LLMs report tighter lower bounds than the conventional global product baseline.

Critical strengths

A single-turn safety certificate does not fully capture what happens over a multi-turn conversation, where an attacker can adapt subsequent messages based on the model's previous responses. Extending safety certification to this setting is a meaningful direction, and I think the paper makes an interesting contribution in this regard. One of the interesting aspects of the paper is its state-aware composition. Rather than repeatedly applying the weakest one-step bound, MTCR tracks how safe probability mass moves between different states. The reported results show tighter lower bounds than the global product baseline across six models at the evaluated horizons. The controlled experiments also provide evidence for the contribution of the proposed composition mechanism.

Critical weaknesses

(1) The practical implementation of the certification procedure could be explained in more detail. The theoretical guarantee requires each transition lower bound to hold uniformly over all histories within a source state and all admissible perturbations. Appendix E explains that the robust verifier and certified anchor cover provide this uniformity, while Clopper–Pearson bounds account for finite response sampling. I may have missed some implementation details, but I could not find a clear explanation of which specific robust verifier is used in the LLM experiments. Appendix G mentions randomized smoothing as an illustrative example, but it is not clear whether this is the procedure actually used in the experiments. The construction of anchor neighborhoods and how their coverage is verified could also be described more explicitly. This is worth clarifying because finite-sample confidence intervals alone cannot establish uniform guarantees over unseen histories and admissible inputs. The guarantees also depend on the validity of the robust transformation and the coverage of the anchor neighborhoods. A more concrete description of how these steps are implemented would help readers understand how the theoretical requirements are satisfied in practice. (2) The relationship between the adaptive threat model and the experimental attacks could be clarified. The theoretical framework allows the attacker to choose subsequent inputs based on the full conversation history. In the experiments, however, the attacks mainly use static edit-distance perturbations and template-based multi-turn escalation. It is not entirely clear whether the escalation attack adjusts its next message based on the model's previous response, or simply follows a predefined sequence. Since adaptivity is one of the main motivations of this work, I think it would be useful to explain how the experimental attacks relate to the theoretical threat model, particularly which results are covered by the current certification guarantee.

Questions for authors

(1) Could the authors provide an end-to-end example of how a local transition bound is obtained in practice? For a representative abstract state, it would be useful to see the anchor set, the corresponding robust verification results, the finite-sample correction, and the resulting lower bound. I am also curious how sensitive the certificate is to the granularity of the anchor cover (e.g., the number and size of anchor neighborhoods). (2) Have the authors compared fixed-sequence escalation with genuinely feedback-dependent attacks under the same perturbation budget and conversation length? Such a comparison would help isolate the effect of adaptivity itself. I am also interested in whether the reported certificate holds uniformly over the attacker's choice of adaptive policy, rather than only over individual admissible inputs. (3) The gap between certified lower bounds and observed safety rates is noticeable. For example, on LLaMA-2-7B-Chat, the MTCR certificate is 0.36 at 5 turns, while the observed static trajectory safety is 66%. At 10 turns, these values are 0.13 and 49%, respectively. At 20 turns, the certificate drops to 0.02, while the observed safety rate remains at 30%. GPT-4o also shows a considerable gap (0.32 vs. 73% at 10 turns). I understand that these are different quantities: observed safety on a finite set of attacks is not the same as worst-case safety probability. The Discussion already mentions several possible sources of this gap, including local-oracle conservatism, within-state worst-case estimation, and finite-sample correction. It would be interesting to understand the relative contributions of these factors in more detail. I also want to know how such low absolute certificate values should be interpreted in practical safety assessment. (4) I also noticed a few reporting and presentation points. Section 5.2 and Appendix I.2 state that all six models are evaluated at the same horizons (5, 10, 15, and 20 turns), but Table 1 only reports the 15- and 20-turn results for LLaMA-2-7B-Chat. It would be helpful to include the missing results or clarify the actual experimental scope. The Conclusion is also rather brief and overlaps somewhat with the Abstract. It could do more to summarize the main findings, explain the scope of the certification guarantees, and discuss their practical implications. Finally, Figure 1 is quite crowded, with some overlapping elements and text boxes. A cleaner layout with better spacing would make the framework easier to follow.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.