- 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
-
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.
-
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
-
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 , : at each sufficiently large , let be arbitrarily small. Conditional on seeing only , the trained generator has the same law as under ; once is within the horizon and , its breadth-success probability under is at most , contradicting for small enough . 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.
-
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 , although Lemma 1's breadth guarantee is for strings fixed before is drawn; the claimed 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 does not itself locate a prompt with error comparable to , 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
-
Clarification affecting novelty: What does non-SIL contribute beyond the uniform-distribution obstruction above? Also, under , thresholding each empirical prefix frequency at gives false-positive and false-negative bounds of and , respectively, by conditional Hoeffding bounds. Choosing sufficiently larger than makes both vanish without the gap's factor; although the paper acknowledges that its gap is only sufficient, how does this stronger sufficient condition affect the claimed frontier and the contribution?
-
Proof clarification: Is Corollary 2(a) restricted to algorithms whose exact-oracle query path is independent of ? If not, please justify a bound for sample-dependent query strings. What additional assumptions connect recovered membership information to finding a high-error prompt?
-
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
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.
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 supK,Pρn and supK,Pβn must vanish, then γn≥αn is forced for all large n 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 depend on (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) 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, needs only γn<αn, and uses a depth that depends only on the specification. The effect is to sharpen the frontier: the Gap Condition becomes γn<αn, and it cannot be weakened further, since at γn=αn both properties hold on every prefix-closed class (Remark 11). Figure 2(b) illustrates the regime this adds: at mγ/α=5 the single-match rule fails at every depth, while the threshold rule is error-free from k=1000 on.
Section 6, Corollary 2(a) (Q2). As the reviewer notes, the submitted proof covered query paths that do not depend on Sn, 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:
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) budgeted prompts (Remark 5), so strengthened Proposition 3 shows that the forced leakage occurs on budgeted prompts: limsupnPr[maxt≤m(n)en(p(t))>γn]>0 for some (K,P). On that event, cycling through p(1),…,p(m(n)) for ⌈ln2/γn⌉ rounds elicits a violation with probability at least 1/2. This is an oblivious attack of total cost m(n)⌈ln2/γn⌉, against the lower bound 1/(2Γ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 and detectable breadth with floor 1/2, s(n)=m(n). The copy generator fails this for every infinite K for a suitable P (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 K 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.