- Rating
- 3
- Confidence
- 1
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 3
Read review
Paper summary
I am not an expert at this area. As far as I understand, this paper shows an interesting result that OWF exists if and only if there is a family of languages with the following properties:
- One sample l∈L is sufficient to pin down the target language L
- Any PPT algorithm given access to polynomial many samples in L, has negligible probability of writing even one unseen sample from the target language.
Critical strengths
The paper gives a clean answer to a theoretical question.
I didn't find errors in the security proofs.
Critical weaknesses
I don't know how the result can be translated to real language models or ordinary classes such as regular languages.
Questions for authors
In real life, we not only believe OWF exist, but also somehow believe the ideal cipher model. In this case, your result is trivial, is my understanding correct?
Response to Reviewer g86C
Thank you for the review and for checking the security proofs. The paper makes no claim about trained language models; for ordinary classes it gives a necessary condition for regular families, and relative to an ideal cipher the hard direction is immediate, while the equivalence, in particular its converse, does not follow from that model.
W1 (real language models and regular languages).
Regular languages. For a family whose languages are recognized by automata with at most q(n)=poly(n) states, a strong gap requires that examples longer than q(n) appear only with negligible probability within polynomial horizons (Appendix L, "Regular families"). The reason is pumping: an example w with ∣w∣≥q(n) has a split w=xyz with ∣xy∣≤q(n), ∣y∣≥1 and xyiz∈LS for every i≥0. A generator that tries the O(∣w∣2) candidate splits, one per round, and outputs xyiz with i large enough that the word is longer than every example, produces a fresh valid word at the round of a correct split, in polynomial time. So in automaton families the barrier would need sources that almost never emit long words; whether natural regular or context-free families can exhibit it is open (Appendix L, Section 7).
Language models. The theorem concerns the Bayesian idealization of in-context learning as implicit posterior inference (Xie et al., 2022), not trained models, and the Ethics statement says so. What it does say about that idealization is two-sided. First, for the witness the Bayesian generator (one posterior draw, then enumeration) succeeds after a single example, while every efficient generator has negligible success, so an explanation of in-context generation that appeals to the Bayesian ideal needs a computational premise in addition to a statistical one. Second, the converse (Theorem 4.2, Remark 4.4) names that premise: such a strong gap forces the process that produced the data to be distributionally one-way. We have added a paragraph to Section 7 that states both points and the boundary.
Q1 (ideal cipher).
For the hard direction alone, largely yes; for the theorem, no. Relative to an ideal cipher or random oracle O with 2λ-bit outputs, the family Lk={(i,O(k,i))} already has the property: an example fixes k except with probability about 2−λ, since each of the other 2λ−1 keys agrees at the observed index with probability 2−2λ, and a fresh word needs an oracle value at an unqueried point. Two parts of the result do not follow from that belief.
The same new paragraph of Section 7 also covers idealized models.
Presentation. We have added a plain-language walk-through of the witness to the introduction (after Theorem 1.1) and separated the classical ingredients from the new ones there; the general response lists all changes, which are in blue in the revised PDF.
We are glad to answer further questions.