acceptodds
Under review as a conference paper at ICLR 2027

Interaction Collapses Safety: On the Query-Access Limits of Jailbreak-Robust Generation

Abstract

Recent theoretical work has formalized a trade-off between consistency and breadth in language generation from positive examples. Deployed language models are, in addition, queried: users choose prompts and observe outputs, and jailbreaking uses this access. We develop a query-access theory of jailbreak robustness, in which a generator is trained from positive data and accessed through black-box sampling. We show that a generator that is both broad and sufficiently robust yields, from samples on a fixed batch of prompts, a membership estimator for the target language. Our main result, the Query-Access Impossibility Theorem, follows: for any class of prefix-closed languages (violations cannot be repaired once emitted) that is not statistically identifiable from positive data, no generator is both uniformly robust and uniformly detectably broad once its worst-case error is small relative to its detectable breadth. Adaptivity is unnecessary for this impossibility, but it can substantially reduce the cost of discovering the boundary. All properties are quantified over the random training sample, and an explicit rate sequence and an explicit non-identifiable class show that the hypotheses hold simultaneously. Three consequences follow: robust generators lose detectable breadth, broad generators leak detectably in the worst case, and requiring average-case consistency adds no constraint. Exact or noisy membership feedback removes the barrier, and preference feedback does so exactly when its reward carries information about the boundary. The message is that a sufficiently broad generator reveals, through its own samples, the boundary it is meant to protect: when positive data do not identify that boundary, the tension between helpfulness and jailbreak robustness is information-theoretic and cannot be removed by better training on the same data, but can be removed by feedback that certifies the boundary.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Jailbreaking, Theory

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_3emEOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies generators trained on positive i.i.d. examples and accessed through prompt-conditioned black-box sampling. For prefix-closed target languages, it constructs a membership estimator from detectable coverage and sufficiently small worst-case generation error, then reduces their simultaneous achievement to statistical identification. Additional results address membership/preference feedback and query complexity; validation consists of proofs, an explicit non-identifiable unary class, and a synthetic estimator simulation.

Critical strengths
  1. A sampling-based refinement of the identification connection. Unlike the support-membership approach in Kalavasis et al. (2025), the main estimator requires neither deciding generator support nor inspecting model internals. This is a meaningful distinction for full-support models, and the shared, non-adaptive batch gives a clean constructive reduction.

  2. Careful treatment of training randomness. The proof explicitly separates training and probing randomness and converts fixed-string guarantees into identification using a growing deterministic test set. The direct non-SIL proof for the unary chain and the acknowledgement that robustness already implies average-case consistency improve the argument's rigor.

Critical weaknesses
  1. The substantive novelty and the source of the impossibility need sharper separation. Kalavasis et al. (2025, 2026) already establish generation/breadth-to-identification connections; the distinct contribution here is the quantitative sampling formulation. Uniformity over all distributions with support equal to the target already creates an obstruction for the identifiable class K0={ϵ}K_0=\{\epsilon\}, K1={ϵ,a}K_1=\{\epsilon,a\}: at each sufficiently large nn, let P1(a)=d>0P_1(a)=d>0 be arbitrarily small. Conditional on seeing only ϵ\epsilon, the trained generator has the same law as under K0K_0; once aa is within the horizon and γn<αn\gamma_n<\alpha_n, its breadth-success probability under K1K_1 is at most ρn+1−(1−d)n≤ρn+nd\rho_n+1-(1-d)^n\leq\rho_n+nd, contradicting 1−βn1-\beta_n for small enough dd. This is a uniform-in-distribution obstruction, not a fixed-distribution non-identifiability argument, and does not invalidate Theorem 1; it does call for a clearer account of what non-SIL and interaction add.

  2. Section 6 does not yet establish the claimed attack-discovery complexity. The proof of Corollary 2(a) explicitly allows exact-oracle query strings to depend on SnS_n, although Lemma 1's breadth guarantee is for strings fixed before SnS_n is drawn; the claimed 2qrn2q r_n bound is therefore unjustified for this extension. Fresh probe samples do not remove dependence on the training sample, whereas a deterministic exact-oracle path depending only on a fixed target is covered by the coupling argument. Separately, identifying KK does not itself locate a prompt with error comparable to Γn\Gamma_n, and no reduction connecting these tasks is supplied. Theorem 5 correctly bounds amplification of a known failure, but the claimed discovery-plus-amplification attack cost needs additional assumptions or a narrower interpretation.

Questions for authors
  1. Clarification affecting novelty: What does non-SIL contribute beyond the uniform-distribution obstruction above? Also, under γn≤αn/4\gamma_n\leq\alpha_n/4, thresholding each empirical prefix frequency at αn/2\alpha_n/2 gives false-positive and false-negative bounds of ρn+m(n)e−k(n)αn2/8\rho_n+m(n)e^{-k(n)\alpha_n^2/8} and βn+e−k(n)αn2/2\beta_n+e^{-k(n)\alpha_n^2/2}, respectively, by conditional Hoeffding bounds. Choosing k(n)αn2k(n)\alpha_n^2 sufficiently larger than log⁡m(n)\log m(n) makes both vanish without the gap's m(n)m(n) factor; although the paper acknowledges that its gap is only sufficient, how does this stronger sufficient condition affect the claimed frontier and the contribution?

  2. Proof clarification: Is Corollary 2(a) restricted to algorithms whose exact-oracle query path is independent of SnS_n? If not, please justify a bound for sample-dependent query strings. What additional assumptions connect recovered membership information to finding a high-error prompt?

  3. Scope clarification: Can the feedback results recover the same uniform detectable breadth used in Theorem 1, rather than merely positive support/asymptotic coverage? Also, are the structured-output examples intended to mean viable prefixes, rather than complete valid JSON or schema-conforming outputs, whose languages are generally not prefix-closed? These distinctions materially affect the proposed application to guardrails.

5 comments
AuthorsOpenReview ↗

Response to Reviewer 3emE

We thank the reviewer for a constructive review. The explicit obstruction and the thresholding argument both led to changes in the paper.

Source of the impossibility. The reviewer's obstruction is correct and, as the reviewer notes, does not invalidate Theorem 1. It is exactly the regime of uniform failure probabilities that Reviewer RnC1 also identified. Revised Remark 4 states it in general form (proof in App. D): if sup⁡K,Pρn\sup_{K,P}\rho_n and sup⁡K,Pβn\sup_{K,P}\beta_n must vanish, then γn≥αn\gamma_n\ge\alpha_n is forced for all large nn on every class with two distinct prefix-closed languages, identifiable or not.

The revised Definitions 4–5 keep the levels class-uniform but let ρn,βn\rho_n,\beta_n depend on (K,P)(K,P). Under them the obstruction disappears, since for a fixed distribution the distinguishing string eventually appears. By the new converse, for m(n)≥s(n)m(n)\ge s(n) both properties are then attainable below the gap iff the class is SIL. Non-SIL is therefore exactly the dividing line.

As the reviewer says, the distinctive contribution is the quantitative sampling formulation. It is not a cosmetic change: support-based characterizations say nothing about full-support generators, which every softmax model is, and the sampling formulation is what makes the result apply to them. The revision makes it an exact characterization with a sharp threshold (Remark 11). New Remark 5 states the role of prompting precisely, and Section 2 now relates the result to Kalavasis et al. (2025, 2026), Karbasi et al. (2025) and Anastasopoulos et al. (2026).

Thresholding (Q1). Adopted in general form as Lemma 1(a). It thresholds at (αn+γn)/2(\alpha_n+\gamma_n)/2, needs only γn<αn\gamma_n<\alpha_n, and uses a depth that depends only on the specification. The effect is to sharpen the frontier: the Gap Condition becomes γn<αn\gamma_n<\alpha_n, and it cannot be weakened further, since at γn=αn\gamma_n=\alpha_n both properties hold on every prefix-closed class (Remark 11). Figure 2(b) illustrates the regime this adds: at mγ/α=5m\gamma/\alpha=5 the single-match rule fails at every depth, while the threshold rule is error-free from k=1000k=1000 on.

Section 6, Corollary 2(a) (Q2). As the reviewer notes, the submitted proof covered query paths that do not depend on SnS_n, but not sample-dependent ones. The revision covers both. Breadth is now required simultaneously on the horizon, so a single breadth event covers every query within it. For the sampling step, the corollary now gives two versions:

  • a fresh batch per query, with a conditional Hoeffding bound given SnS_n and the earlier answers, failure ≤ρn+βn+2q m(n)e−k(n)(αn−γn)2/2\le\rho_n+\beta_n+2q\,m(n)e^{-k(n)(\alpha_n-\gamma_n)^2/2};
  • one shared batch, with Lemma 1(a) applied to the entire horizon, failure ≤ρn+βn+2m(n)s(n)e−k(n)(αn−γn)2/2\le\rho_n+\beta_n+2m(n)s(n)e^{-k(n)(\alpha_n-\gamma_n)^2/2}. This version is valid whatever rule selects the queries, including rules that depend on the batch.

No restriction on the query path is needed.

From membership information to a high-error prompt. In the regime that breadth forces, no such reduction is needed. The proof of Theorem 1 uses robustness only at the m(n)m(n) budgeted prompts (Remark 5), so strengthened Proposition 3 shows that the forced leakage occurs on budgeted prompts: lim sup⁡nPr⁡[max⁡t≤m(n)en(p(t))>γn]>0\limsup_n\Pr[\max_{t\le m(n)}e_n(p^{(t)})>\gamma_n]>0 for some (K,P)(K,P). On that event, cycling through p(1),…,p(m(n))p^{(1)},\dots,p^{(m(n))} for ⌈ln⁡2/γn⌉\lceil\ln2/\gamma_n\rceil rounds elicits a violation with probability at least 1/21/2. This is an oblivious attack of total cost m(n)⌈ln⁡2/γn⌉m(n)\lceil\ln 2/\gamma_n\rceil, against the lower bound 1/(2Γn)1/(2\Gamma_n) of Theorem 5. For failing prompts outside the budget, we adopt the narrower reading: the model measures discovery by the cost of learning the boundary. Section 6 now states both points.

Scope (Q3). The feedback results now attain the same notion of breadth: Theorems 2(b) and 3 give envelope γn≡0\gamma_n\equiv0 and detectable breadth with floor 1/21/2, s(n)=m(n)s(n)=m(n). The copy generator fails this for every infinite KK for a suitable PP (Remark 11), so the separation from Theorem 1 is exact in the same notions. The structured-output examples are meant as viable prefixes. App. B.5 defines KK as the set of prefixes that extend to a complete valid output; this set is prefix-closed by construction, whereas the set of complete valid outputs generally is not. For guardrails, the matching membership oracle is an incremental validator, as in constrained decoding.

We hope this revision addresses the reviewer's concerns about the source of the impossibility and Section 6, and we would be grateful if the reviewer would consider these changes in their final assessment.

Dear Reviewer 3emE, as the discussion period draws to a close, we wanted to check whether the revision resolves your concerns about the source of the impossibility and Section 6, including the strengthened Proposition 3. We would be glad to discuss any remaining point, and we would be grateful if you could take these changes into account in your final assessment.

Dear Reviewer 3emE, as the discussion period draws to a close, we wanted to check whether the revision resolves your concerns about the source of the impossibility and Section 6, including the revised Corollary 2(a) and the strengthened Proposition 3. We would be glad to discuss any remaining point, and we would be grateful if you could take these changes into account in your final assessment.

Reviewer_eLYHOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies whether jailbreak-robust generation is possible for expressive language classes that cannot be statistically identified in the limit (SIL) from positive examples. It defines the uniform robustness envelope, uniform detectable breadth (a lower bound on the prefix mass of in-budget prompts), and the Gap Condition; proposes a proof framework reducing generation to identification with approximate membership queries (the non-adaptive membership estimator of Lemma 1); proves the Query-Access Impossibility Theorem (the two uniform properties cannot both hold on prefix-closed, non-SIL classes under the Gap Condition), together with positive results: an exact membership oracle removes the barrier (Theorem 2) and a noisy oracle restores approximate robustness within O(nclogn)O(n^c log n) queries (Theorem 3). It also gives Proposition 2 (Refusal: robustness forces some legitimate strings to lose detectable breadth), Proposition 3 (Vulnerability: sufficient breadth forces worst-case leakage to exist), and Theorem 5.

Critical strengths
  1. Assumptions are separated and the quantifier order is precise: Robustness is convergence in probability of the worst-case error ΓnΓ_n (Definition 4), and breadth is a lower bound on the prefix mass of in-budget prompts (Definition 5). Remark 1 makes the quantifier order explicit, avoiding formulations like "for every x∈K§nx∈K\S_n" whose scope depends on random samples, reflecting rigor.
  2. The estimator in Lemma 1 is executable, and the proof does not rely on adaptivity: The estimator only needs to fix a batch of prompts and sample repeatedly; it does not need to know whether x is legitimate and does not need to choose prompts adaptively. Remark 3 explains that Assumption 1 is only used in the analysis; the procedure itself is independent of legality judgments.
  3. The joint satisfiability of the assumptions is verified in the main text: Table 1 gives explicit rates, and Proposition 1 gives an explicit non-SIL prefix-closed class L_chain. Readers can directly check that the Gap Condition's non-empty window and the rate conditions hold simultaneously.
Critical weaknesses
  1. The connection to real LLMs is interpretive, with no experimental bridge: Section 1 and Section 4.3 interpret Proposition 2–3 as formal accounts of refusal and leakage on aligned LLMs, but the main text does not estimate prefix mass or worst-case error on real models. Appendix B.13 lists "estimating prefix mass on structured-output tasks" as future work, indicating the gap between the current results and LLM empirics.
  2. The Abstract's claim "exact or noisy membership feedback removes the barrier" needs qualification: Theorem 2 proves that the worst-case error is identically zero and that the generation probability is positive for every legitimate string, but does not provide a class-uniform prefix-mass lower bound satisfying the breadth definition. Remark 1 already shows that a class-uniform prefix-mass lower bound over all strings of an infinite language is unattainable. There is a gap between Theorem 2's "positive probability" and the "detectability" in the breadth definition.
  3. Theorem 4 and Proposition 5 are two extreme cases; the middle ground is unexplored: The reward is either completely unrelated to the target language (boundary-uninformative) or exactly equal to the target language's indicator function. Remark 7 admits that real reward models fall in between, but this paper provides no measurements or intermediate results. This leaves the question "when is preference feedback sufficient" largely unanswered.
Questions for authors
  1. How can the prefix mass be estimated on real LLMs? This is the key step in connecting theory to empirics. Have the authors considered approximating the membership oracle with constrained decoding or an output classifier on structured-output tasks?
  2. How tight is the requirement in the Gap Condition that the gap parameter is smaller than the ratio of the breadth lower bound to the number of preset prompts? Is there a counterexample where both properties can be achieved when the two are of the same order? This determines how necessary the condition is.
  3. Can the results be extended to continuous prompt spaces? This paper assumes prompts form a countable set with a fixed enumeration. The actual prompt space of LLMs is continuous token sequences; do the estimator and the impossibility theorem still hold in that case?
3 comments
AuthorsOpenReview ↗

Response to Reviewer eLYH

We thank the reviewer for a careful reading and pertinent questions. Our answers refer to the revised Definitions 4–5. Following Reviewers RnC1 and 3emE, these keep the levels (γn,αn,m(n),s(n))(\gamma_n,\alpha_n,m(n),s(n)) class-uniform but let the failure probabilities depend on (K,P)(K,P), with breadth required simultaneously on a horizon fixed before SnS_n is drawn.

Connection to deployed models. We appreciate this point and agree that an empirical bridge would strengthen the work. Our aim here is theoretical, in the spirit of Kleinberg & Mullainathan (2024) and Kalavasis et al. (2025, 2026), and we have tried to keep our claims within that scope: Propositions 2–3 are statements about the model that suggest, but do not establish, an account of observed behaviour. What the theory offers empirical work is a precise target: the ratio γn/αn\gamma_n/\alpha_n of worst-case leakage to visible breadth. Following the reviewer's suggestion, App. B.13 now explains how this ratio can be estimated, with logit access or black-box sampling and on structured-output tasks (see Q1); we see this measurement as a natural next step.

Theorem 2: positivity versus detectability. The submitted Theorem 2 established positivity, as the reviewer notes. The revision closes this gap: Theorems 2(b) and 3 now give envelope γn≡0\gamma_n\equiv0 together with detectable breadth with floor 1/21/2 and s(n)=m(n)s(n)=m(n). This is consistent with Remark 1: a class-uniform floor over an infinite language is unattainable, so breadth is required on a horizon growing with nn, and the restated theorems meet it there. Theorem 2(a), deployment-time filtering, remains a positivity statement. The separation is now exact: from positive data alone, both properties are attainable below the gap iff the class is SIL (Theorem 1, m(n)≥s(n)m(n)\ge s(n)); with membership feedback, for every class.

The middle ground of preference feedback. New Proposition 6 (Section 5.3, proof in App. D) gives an intermediate result. Assume:

  • Bradley–Terry comparisons, Pr⁡[Cr(x,y)=x]=σ(r(x)−r(y))\Pr[\mathcal C_r(x,y)=x]=\sigma(r(x)-r(y));
  • a margin reward: r≥τ+Δ/2r\ge\tau+\Delta/2 on KK and r≤τ−Δ/2r\le\tau-\Delta/2 off KK;
  • a reference y0y_0 with ∣r(y0)−τ∣≤δ<Δ/2|r(y_0)-\tau|\le\delta<\Delta/2.

Then comparing against y0y_0 is a noisy membership oracle with η=σ(δ−Δ/2)<1/2\eta=\sigma(\delta-\Delta/2)<1/2, and Theorem 3 applies with O(log⁡n/(1/2−η)2)O(\log n/(1/2-\eta)^2) comparisons per string. Ordinal feedback therefore suffices when the reward's level sets track the boundary with a margin and a calibrated reference is available. A boundary-uninformative reward is the same for every KK, so no calibrated reference can be chosen without knowing KK (Theorem 4). Remark 8 states this.

Q1. Estimating prefix mass on real models. With logit access, μn(x;p,Sn)\mu_n(x;p,S_n) is the product of next-token probabilities along xx, so it can be computed exactly. With black-box access, Lemma 1(a) separates valid from invalid strings with O(log⁡(m(n)∣T∣)/(αn−γn)2)O(\log(m(n)|T|)/(\alpha_n-\gamma_n)^2) samples per prompt. The largest estimated error over the prompts tested is a lower bound on worst-case leakage. On structured-output tasks, KK is the set of viable prefixes (App. B.5). There, constrained decoding or an incremental validator supplies the exact oracle of Theorem 2, and an output classifier a noisy oracle in the sense of Theorem 3, provided its errors are independent across repeated queries; this excludes systematic errors. App. B.13 now includes this.

Q2. Tightness of the Gap Condition. Following Reviewer 3emE's thresholding suggestion, the condition is now γn<αn\gamma_n<\alpha_n, without the factor m(n)m(n). Lemma 1(a) thresholds the empirical frequencies at (αn+γn)/2(\alpha_n+\gamma_n)/2, with a depth that depends only on the specification. The single-match rule remains as Lemma 1(b). The condition is sharp, and the requested counterexample exists at equal order: on every prefix-closed class, the generator Gn(⋅∣p(t))=αnδx(t)+(1−αn)δϵG_n(\cdot\mid p^{(t)})=\alpha_n\delta_{x^{(t)}}+(1-\alpha_n)\delta_\epsilon has envelope γn=αn\gamma_n=\alpha_n and detectable breadth with floor αn\alpha_n (Remark 11). The revised Figure 2(b) shows the threshold rule succeeding at mγ/α=5m\gamma/\alpha=5, where no single-match depth works.

Q3. Continuous prompt spaces. Prompts enter the impossibility only through the budget on which breadth is witnessed. Robustness is a supremum over all prompts, so it holds on any subset. Theorem 1 therefore applies verbatim to any prompt space, provided breadth is witnessed on a countable family fixed in advance; token-sequence prompts are such a family. For soft-prompt embeddings, where breadth may be witnessed only off such a family, the extension needs a countable dense family and continuity of prefix masses in the prompt; we leave it open. The positive results do not depend on the prompt space. App. B.13 now states this.

We thank the reviewer again; we hope the revision, in particular Proposition 6 and the restated feedback theorems, strengthens the case for the paper.

Dear Reviewer eLYH, thank you again for your questions. As the discussion period nears its end, we would welcome any further comments on the revision, in particular Proposition 6 on preference feedback and the restated Theorems 2(b) and 3, and we are happy to clarify anything that remains unclear.

Dear Reviewer eLYH, as the discussion period nears its end, we would welcome any further comments on the revision, in particular Proposition 6 on preference feedback, the restated Theorems 2(b) and 3, and the discussion of prefix-mass estimation in App. B.13. We are happy to clarify anything that remains unclear.

Reviewer_RnC1OpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

Language generation in the limit, introduced by Kleinberg and Mullainathan, asks whether a learner receiving positive examples of an unknown language can eventually generate new valid strings. Kalavasis et al. studied the additional requirement of breadth, or coverage of the target language. This formulation requires the support of the generator to eventually equal the set of unseen strings in the target language, which is unrealistic for modern language models since they assign positive probability to every string. This paper relaxes this requirement for generators trained on i.i.d. positive examples and accessed through prompts. It allows a vanishing probability of invalid outputs and, motivated by jailbreaking, requires this to hold for every prompt, which it calls jailbreak robustness. Its breadth condition, detectable breadth, asks that each valid string appear as a prefix of the output with at least a prescribed probability under some prompt within a finite search budget.

Their main result shows that, for classes of prefix-closed languages (where prefixes of valid strings are also valid), jailbreak robustness and detectable breadth are incompatible unless the class is statistically identifiable. The result requires both properties to hold at rates uniform over target languages and sampling distributions, with the worst-case error rate being small compared with the ratio of the lower bound on breadth to the prompt budget. Their next results study additional feedback: they give positive results with exact and noisy membership labels and examine when preference feedback conveys useful information about the target. Their final results analyze the query cost of finding unsafe prompts and of observing an invalid output through repeated sampling.

Critical strengths

Relaxing the exact-support validity requirement of prior work is a useful direction. This relaxation fits models that assign positive probability to invalid outputs but keep the total probability of invalid outputs small. Formulating breadth through observable samples is also natural for generators accessed through a sampling interface.

Critical weaknesses

My main concerns are the strength of the assumptions behind the main result and the contribution beyond prior work.

  1. The paper relaxes validity, but in exchange it imposes strong uniformity requirements. After nn training samples, robustness and breadth must hold with the same guarantees for every target language in the class and every training distribution over it. For breadth, this means that each valid string must appear under some prompt with at least a minimum probability that depends only on nn, even when the training distribution almost never shows the strings that distinguish the target from the other languages in the class. Prior work allows such guarantees to depend on the target language and the distribution, and the paper notes that its argument does not extend to that case (Remark 4). It is unclear to me why uniform guarantees are reasonable for current LLMs, or what new conceptual conclusion this formulation yields beyond the validity-breadth trade-off established in prior work.

    Unless I am missing something, the uniformity requirements already make the problem impossible for trivial classes. Consider the class of the two prefix-closed languages {ε}\{\varepsilon\} and {ε,a}\{\varepsilon, a\}. Since the guarantees must hold for every training distribution, take the target {ε,a}\{\varepsilon, a\} with a distribution that puts almost all of its mass on ε\varepsilon. With high probability, the training data then contain only ε\varepsilon, exactly as when the target is {ε}\{\varepsilon\}, so the generator behaves the same in both cases. Breadth for {ε,a}\{\varepsilon, a\} requires some prompt to produce outputs starting with aa with at least the minimum probability, while robustness for {ε}\{\varepsilon\}, at the rates assumed in Theorem 1, requires every prompt to produce such outputs with smaller probability. Hence no generator has both properties, although this class is trivially identifiable. The same argument applies to any class containing two different prefix-closed languages, since any two such languages share the empty string. Thus, under the rate condition of Theorem 1, uniformity already implies impossibility without requiring statistical non-identifiability or query access. What role, then, do interaction and statistical non-identifiability play in the obstruction?

  2. The technical contribution also appears limited. The main proof estimates, from the generator's samples, whether each string belongs to the target language, and then eliminates candidate languages that disagree with these estimates. Both steps use elementary arguments, and the uniform rates let the paper avoid the harder questions about statistical identification and rates studied by Kalavasis et al. (2025). The feedback and query-complexity results also rely on standard filtering, majority-vote, and query-learning arguments. Moreover, Kalavasis et al. (2025) already show that, in their setting, negative examples make generation with breadth possible for every countable class, and the paper does not compare its feedback results with this. I would welcome a clearer explanation of the main technical difficulty and how the paper overcomes it.

  3. I found the paper quite difficult to follow, even as a reader familiar with prior work on language generation and breadth. The introduction does not clearly isolate the changes to the model or explain why each is needed, and the ordering of the definitions makes the setup hard to parse. For example, Assumption 1 is stated as prefix-separability, and Remark 2 then shows that it is equivalent to prefix-closedness. A direct comparison with the earlier formulations and a simple example before the full definitions would help.

  4. I may be missing something, but the following points seem to need clarification:

    • Theorems 2(b) and 3 use a much weaker notion of coverage than detectable breadth: each valid string only needs to receive positive probability. This weaker goal is achievable without feedback. Sampling uniformly from the training data already meets the guarantees of Theorem 2(b), since every valid string eventually appears in the training data, and mixing this generator with a vanishing fraction of a full-support distribution meets those of Theorem 3. As stated, these results therefore do not establish a benefit from training-time or noisy feedback for the detectable-breadth requirement used in Theorem 1.

    • Corollary 2(a) answers the queries of a membership-query algorithm with the estimator of Lemma 1. For valid strings, the guarantee of Lemma 1 relies on breadth, which holds only for strings fixed before the training sample is drawn (Remark 1). The proof, however, allows the queries to depend on the training sample, as they do for algorithms that use the training data, such as those in Proposition 4. I do not see why the error bound applies to such queries. Could the authors clarify this step?

    • After Corollary 2, the paper claims that adaptive probing needs exponentially fewer probe samples than any fixed test set. However, the proof of Theorem 1 answers all its membership questions from a single shared batch of samples. Could an oblivious procedure do the same, and if so, what remains of the exponential saving?

Questions for authors

Please see comments in weaknesses.

7 comments
AuthorsOpenReview ↗

Response to Reviewer RnC1 (Part 1/2)

We thank the reviewer for a careful review. The two-language example is correct and has sharpened the paper. It does not contradict the submitted Theorem 1, and the revision completes an extension that the submission had already flagged.

On uniformity and the counterexample. Under the submitted Definitions 4–5, uniformity bound both the levels (γn,αn,m(n),s(n))(\gamma_n,\alpha_n,m(n),s(n)) and the failure probabilities (ρn,βn)(\rho_n,\beta_n). As the reviewer showed, the second requirement already forces γn≥αn\gamma_n\ge\alpha_n on any class with two prefix-closed languages. The submitted theorem therefore remains correct, but under those definitions its conclusion holds without the non-SIL hypothesis. Revised Remark 4 states this in general form (proof in App. D).

We now separate the two. A deployed model can commit in advance to a leakage level and a coverage target; it cannot commit to how fast training succeeds on an unknown distribution, just as a statistical identifier's success probability depends on (K,P)(K,P). The revised definitions therefore keep the levels class-uniform but require only ρn(K,P),βn(K,P)→0\rho_n(K,P),\beta_n(K,P)\to 0 for each (K,P)(K,P). Breadth must hold simultaneously on a horizon fixed before SnS_n is drawn. The submitted Remark 4 had identified such (K,P)(K,P)-dependent rates as the case the argument did not cover; the revision covers it. Floors that depend on xx or PP remain open. Your example no longer applies: for a fixed PP, the distinguishing string eventually appears.

Under these definitions:

  • Theorem 1 holds under γn<αn\gamma_n<\alpha_n, and has a converse: for prefix-closed classes with m(n)≥s(n)m(n)\ge s(n), both properties are attainable below the gap iff the class is SIL.
  • The gap is sharp (Remark 11).
  • Each choice is necessary: uniform failure probabilities make the barrier hold for every class (Remark 4); per-string breadth makes the theorem false (Remark 1).

Since the revised hypotheses are weaker on both counts, the submitted impossibility is a special case of the revised one.

What is new beyond the validity–breadth trade-off. The identification barrier itself is classical. The new elements are its scope and what it constrains. (i) Earlier characterizations are stated through the support; a full-support model is always broad and never valid in that sense, so they say nothing about it, whereas Theorem 1 does. (ii) It constrains a deployment specification, not a training algorithm, at the sharp threshold γn<αn\gamma_n<\alpha_n, using only black-box samples. (iii) The leakage it forces lies on budgeted prompts that an oblivious prober finds (Proposition 3). The converse is asymptotic: its rates depend on (K,P)(K,P), so it gives no finite-sample certificate for a deployed model, whereas the impossibility holds whatever the rates (Appendix B.6).

Role of non-SIL and of interaction. Non-identifiability is the source of the hardness and, by the converse, exactly the dividing line. New Remark 5 is explicit about interaction: the impossibility does not use m(n)→∞m(n)\to\infty, and with one prompt it is a statement about unconditional generation. Prompting enters in two places: (i) safety is a supremum over prompts, the jailbreak notion; (ii) breadth may be witnessed across a budget of prompts. The reduction needs only sampling access, and no adaptivity. Interaction also gives a new consequence. The proof uses robustness only at the m(n)m(n) budgeted prompts, so the leakage that breadth forces occurs there. An oblivious prober therefore finds a violation in m(n)⌈ln⁡2/γn⌉m(n)\lceil\ln 2/\gamma_n\rceil queries (strengthened Proposition 3).

AuthorsOpenReview ↗

Response to Reviewer RnC1 (Part 2/2)

Technical contribution. The individual estimates are elementary by design, so that the reduction is transparent. The difficulty lies in the formulation: with (K,P)(K,P)-dependent rates the argument now meets statistical identification directly rather than avoiding it, and the contribution is a formulation in which the characterization is exact, together with three results showing that it cannot be relaxed: per-string breadth makes the theorem false (Remark 1), uniform failure probabilities make it trivial (Remark 4), and the gap cannot be closed (Remark 11). The converse inherits the identifier's rate, which is (almost) exponential under Angluin's condition (Kalavasis et al., 2025). The feedback and query-complexity results use standard constructions, as the reviewer says. Their role is to make the separation exact in the same notions: from positive data, both properties are attainable below the gap iff the class is SIL; with membership feedback, for every class.

Relation to the negative-example result of Kalavasis et al. (2025). Their result is the support-based analogue of Theorems 2–3. Section 2 now says so, and also discusses Kalavasis et al. (2026), Karbasi et al. (2025) and Anastasopoulos et al. (2026). Our additions are quantitative: detectable breadth with a constant floor and zero worst-case error; noisy membership feedback at logarithmic overhead per string (Theorem 3); the teaching-dimension lower bound and the effect of positive data on query count (Proposition 4); and when preference feedback suffices (Theorem 4, Propositions 5–6).

Presentation. These changes are in the current revision. The introduction now has a paragraph stating the three changes to the model and why each is needed, a comparison table with the support-based formulations (Table 1), and a short example on the chain class. Assumption 1 is now stated directly as prefix-closedness, with separability as an equivalent form (Remark 2).

Clarifications.

(i) Theorems 2(b) and 3. The submitted statements concerned positivity, which the copy generator also meets, so they did not yet show a benefit for detectable breadth. Both theorems now give envelope γn≡0\gamma_n\equiv 0 and detectable breadth with floor 1/21/2 and s(n)=m(n)s(n)=m(n). The construction mixes the filtered generator with the point mass on each prompt's string inside the identified language. The copy generator fails this on every infinite KK for a suitable PP (Remark 11).

(ii) Corollary 2(a). The submitted argument applies as stated to query paths that do not depend on SnS_n; for sample-dependent queries it needed breadth beyond strings fixed before SnS_n. Breadth now holds simultaneously on the horizon, so one breadth event covers every query within it, however the query depends on SnS_n. The Hoeffding step is handled in either of two ways:

  • with a fresh batch per query, conditionally on SnS_n and earlier answers (failure ≤ρn+βn+2q m(n)e−k(n)(αn−γn)2/2\le\rho_n+\beta_n+2q\,m(n)e^{-k(n)(\alpha_n-\gamma_n)^2/2});
  • with one shared batch, by applying Lemma 1(a) to the whole horizon (failure ≤ρn+βn+2m(n)s(n)e−k(n)(αn−γn)2/2\le\rho_n+\beta_n+2m(n)s(n)e^{-k(n)(\alpha_n-\gamma_n)^2/2}). This version holds whatever rule selects the queries, including rules that depend on the batch itself.

(iii) Exponential saving. This point is correct, and the claim is withdrawn. One shared batch serves any oblivious test set, so adaptivity gives no comparable saving in probe samples. Its advantage is in the number of membership queries, NN versus ⌈log⁡2(N+1)⌉\lceil\log_2(N+1)\rceil (Corollary 2(c)), which matters when answers are costly. Section 6, the abstract and the contributions now say this.

We believe the revision addresses the concerns raised, in particular the counterexample, the feedback results, and Corollary 2(a), and we would be grateful if the reviewer would consider whether the assessment should be updated in light of these changes. We would be glad to discuss any remaining point.

Dear Reviewer RnC1, as the discussion period draws to a close, we wanted to check whether our response and the revised definitions address your concerns about uniformity, the two-language example and Corollary 2(a). We would be glad to clarify any remaining point, and we would be grateful if you could take the revision into account in your final assessment.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General comments (to all reviewers and the AC)

Summary of revisions

We thank the reviewers for careful and technically precise reviews. Reviewers RnC1 and 3emE independently observed that, if the failure probabilities must vanish uniformly over training distributions, the impossibility already holds for identifiable classes. The submitted Theorem 1 remains true (as Reviewer 3emE notes, the observation "does not invalidate Theorem 1"), but this makes its non-identifiability hypothesis redundant. The submitted Remark 4 had named distribution-dependent rates as the case the argument did not cover; the revision covers it, and the result becomes a two-sided characterization. All changes are in blue in the revised PDF.

1. Main result (Definitions 4–5, Theorem 1, Remarks 1, 4, 5, 11). The levels (γn,αn,m(n),s(n))(\gamma_n,\alpha_n,m(n),s(n)) stay fixed in advance and class-uniform, as a deployment specification is; the failure probabilities ρn(K,P),βn(K,P)\rho_n(K,P),\beta_n(K,P) may now vanish at (K,P)(K,P)-dependent rates, as the success probability of statistical identification does; breadth must hold simultaneously on a horizon fixed before SnS_n is drawn. Then:

  • Theorem 1 holds under the weaker Gap Condition γn<αn\gamma_n<\alpha_n (Lemma 1(a), thresholding at (αn+γn)/2(\alpha_n+\gamma_n)/2, as Reviewer 3emE suggested), and has a converse: for prefix-closed classes with m(n)≥s(n)m(n)\ge s(n), both properties are attainable below the gap iff the class is SIL.
  • The gap is sharp: at γn=αn\gamma_n=\alpha_n both properties hold on every prefix-closed class (Remark 11).
  • Each modelling choice is necessary: with uniform failure probabilities the barrier holds for every class with two languages (Remark 4, proof in App. D); with per-string breadth the theorem is false (Remark 1).
  • The revised hypotheses are weaker than the submitted ones on both counts, so the submitted impossibility is a special case. What changes is the interpretation: non-identifiability is now exactly the dividing line.

2. Feedback results (Theorems 2(b), 3; new Proposition 6). As all three reviewers noted, the submitted Theorems 2(b) and 3 proved only positivity, which the copy generator meets. Both now give envelope γn≡0\gamma_n\equiv 0 and detectable breadth with floor 1/21/2, so the contrast with Theorem 1 is exact. New Proposition 6 covers the middle ground of preference feedback (Bradley–Terry comparisons with a margin reward and a calibrated reference give a noisy membership oracle).

3. Section 6. Corollary 2(a) now covers sample-dependent queries (fresh batch per query, or one shared batch over the whole horizon). The claim of an exponential saving in probe samples is withdrawn: adaptivity saves membership queries only. Proposition 3 is strengthened: the leakage that breadth forces occurs on budgeted prompts, so an oblivious prober finds a violation in m(n)⌈ln⁡2/γn⌉m(n)\lceil\ln 2/\gamma_n\rceil queries.

4. Presentation and positioning. The introduction now states the three changes to the model and why each is needed, with a comparison table (Table 1) and a worked example. Assumption 1 is stated directly as prefix-closedness. Related work now covers Kalavasis et al. (2025, 2026), Karbasi et al. (2025) and Anastasopoulos et al. (2026). App. B.13 discusses continuous prompts and estimating prefix mass on real models. Figure 2 now shows the threshold rule of Lemma 1(a) working where the single-match window is empty.

5. Scope of the claims. The introduction now states that "interaction" means query access, not adaptivity, and that the hardness comes from non-identifiability (Remark 5). Appendix B.6 explains how to read the asymptotic characterization for deployed models: the converse gives no finite-sample certificate, while the impossibility does not depend on rates. Propositions 2–3 and 6 are presented as statements about the model, not as explanations of deployed RLHF systems. Section 4.1 states that KK is a formal, prefix-closed boundary; semantic notions of harm enter only through prefix-closed proxies.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.