- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper introduces a taxonomy, grounded in computation theory, for organizing existing skeptical arguments about language models. The taxonomy has five categories: computability, complexity, learnability, representation capacity, and category error. The paper classifies formal results, including Hahn (2020) and Merrill & Sabharwal (2023), according to this taxonomy. It also provides case studies, including works by Chomsky et al. (2023), Bender et al. (2021), LeCun (2022), and Searle (1980), and organizes previous informal and empirical arguments as well. Finally, it expands on the P ≠ NP assumption that some components of the taxonomy rely on, discussing it from a physicalist point of view.
Critical strengths
-
The paper gathers previously scattered works and organizes them into a single framework. It references classic computation theory papers such as Turing (1936) and Church (1936), while also covering a wide span of recent work. Presenting each categorized component together with its epistemic status fits well with the paper’s goal of distinguishing what is formally proven from what is closer to intuition.
-
The paper contrasts the works of Gold (1967) and Kleinberg & Mullainathan (2024). In addition, drawing on the Chain-of-Thought results of Merrill & Sabharwal (2024), it shows that changes in the success criteria or in the reasoning can allow different upper bounds for specific methods. These results offer valuable insights for research on skepticism about language models.
Critical weaknesses
-
The taxonomy’s categories are not orthogonal, and a single argument can receive multiple labels depending on how it is interpreted. For example, Minsky & Papert (1969) could be classified as either REPR or COMPLEX depending on the scope of interpretation. Lin et al. (2021) is labeled REPR (via COMPLEX subcomputation), which implies dependencies among the taxonomy’s components. The discussion of Chomsky’s New York Times arguments (Section 5.1) shows that category assignment depends on how a work is interpreted, which makes the taxonomy itself fragile. Moreover, the taxonomy mirrors concepts from computation theory, so clustering existing works under it offers only a limited contribution.
-
The paper argues for formalizing these arguments, but most case studies simply assign labels without precise statements, which weakens the main contribution the paper claims. The rules for organizing arguments and assigning categories are not strictly defined. For example, Section 3 defines LEARN_C as covering cases that require excessive samples or computation. However, the LEARN_C row in Table 1 covers only the computation aspect, while the LEARN_S row describes LEARN_C as related to the sample complexity of learning grammar. These conflicting definitions make it difficult for the proposed taxonomy to serve as a reliable framework.
Questions for authors
-
Would it be possible to restructure the taxonomy, or to elaborate on the rules for assigning categories, so as to avoid the confusion described in the second weakness? If not, how could the relationships between categories, and arguments assigned to multiple categories, be handled?
-
If the definition of LEARN_C were clarified, would the main finding (that many arguments turn out to be learnability arguments) still hold?
4 comments
Hello, we were wondering whether some of you concerns have been addressed and whether you have more questions.
Thank you for your response and the clarification. However, my concern about the limited novelty remains, since the contribution is still mainly a reorganization of existing arguments and results under standard concepts from the theory of computation. In addition, if the main contribution is formulating prose arguments in the language of the theory of computation, the case studies would need to state them as precise claims rather than assign labels, which the current paper does not do. Therefore, I will keep my score, and I appreciate the authors’ efforts.
full formalizations added
Hello,
In addition, if the main contribution is formulating prose arguments in the language of the theory of computation, the case studies would need to state them as precise claims rather than assign labels
Thank you for bringing this up. We have now added full formalizations to Appendix C, which we hope will alleviate this particular concern.
Please see the comment at the top for our overall argument for why the work is broadly of interest.
Thank you for considering our arguments.
Notation. Σ∗ is the set of token strings. Prompts are denoted by z ∈ Σ∗ and continuations by x ∈ Σ∗. P(x | z) is the human-level distribution over continuations, and L(x | z) is the distribution produced by an LM L. A dot stands for the full distribution over continuations, as in P(· | z). We write d for a distance between distributions (e.g. total variation) and ε for the tolerance for “human-level.”
Where the correct response depends on the world, M ∈ ℳ denotes a world (for Pearl, a structural causal model; for LeCun and for Bender & Koller, the physical world). ℳ is the class of a priori possible worlds. We write T(M) for the distribution over training text in world M, P(x | z, M) for the human-level distribution in that world, and Q ⊆ Σ∗ for the set of test prompts.
Example 1: the world-model arguments (LeCun, 2022; Pearl, 2018; Bender & Koller, 2020) — LEARN_S
These arguments assert that LMs cannot learn to generate human-level language from text alone, because the training text does not contain enough information to determine a world model. For Pearl, Q is the set of interventional questions (“what happens to Y if we set X?”); for LeCun and Bender & Koller, Q is the set of prompts whose correct answer requires predicting how the world would respond.
Claim. Assume the world is M ∈ ℳ and the training text is drawn from T(M). For any LM L trained on samples from T(M), there exists a prompt z ∈ Q such that
d(L(· | z), P(· | z, M)) > ε.
Why it is LEARN_S. The limitation is attributed to the data, rather than to the model's capacity or to the training procedure. A sufficient condition for the claim is that there exist M₁, M₂ ∈ ℳ with T(M₁) = T(M₂) but, for some z ∈ Q,
d(P(· | z, M₁), P(· | z, M₂)) > 2ε.
The learner then sees the same data in both worlds, so by the triangle inequality any L is more than ε away from the correct distribution in at least one of them.
Epistemic status. For Pearl's version, pairs (M₁, M₂) of this kind are proven to exist: the observational and interventional layers of the causal hierarchy are distinct for almost all SCMs (Bareinboim et al., 2022). So if text depends on M only through the observational distribution, the claim is proven. That premise is contestable, since text includes reports of interventions and their outcomes. Absent such an assumption about the structure of the world and the data, the claim is a conjecture of LEARN_S form. The formalization makes explicit which premise carries the argument.
Example 2: Chomsky's argument from moral thinking (Chomsky et al., 2023) — CATEG
Chomsky et al. hold that “true intelligence is also capable of moral thinking” and that LMs are “constitutionally unable to balance creativity with constraint”: they either “overgenerate” or “undergenerate.”
Primary reading. This is a CATEG argument: moral thinking is not a computational process, so LMs cannot perform it in the relevant sense. Because the claim is not about the outputs of LMs, it cannot be stated in terms of L(· | z). This is by design: CATEG arguments can be classified but not formalized, and no capability result bears on them.
Secondary (behavioral) readings. These can be stated. Let Q_moral be the set of prompts that call for ethical judgment, and let A(z) ⊆ Σ∗ be the acceptable continuations of z. Then:
-
Overgeneration: for some z ∈ Q_moral, the following inequality holds, where Σ∗ ∖ A(z) is the set of unacceptable continuations:
L(Σ∗ ∖ A(z) | z) > P(Σ∗ ∖ A(z) | z) + ε. -
Undergeneration: for some z ∈ Q_moral, L declines to answer with probability exceeding that of P by more than ε.
What the formalization shows. The claim that no LM avoids both could be an argument of any of the other four categories (COMPUT, COMPLEX, LEARN, or REPR), and each would call for a different kind of evidence. The original text does not say which is intended. This is the sense in which the taxonomy lets us interrogate an argument rather than only classify it.
Thank you for the questions
Thank you very much for the thoughtful review.and for catching an important typo, which we will be fixing in the manuscript very soon.
W1: The taxonomy’s categories are not orthogonal
We do not quite agree here. The issue, in our opinion, is that complex prose can be ambiguous. We will be revising the manuscript to assign secondary labels to particular arguments.
W1: The taxonomy mirrors concepts from computation theory, so clustering existing works under it offers only a limited contribution.
We would like to clarify that, in our view, the contribution is not the taxonomy by itself, but rather the fact that prominent prose arguments can be formulated in the language of the theory of computation. The taxonomy is a downstream consequence of that.
W1:
LEARN_Cvs.LEARN_SYou identified a typo in Section 3. Thank you.
LEARN_Cis the computational learning complexity and does not have to do with samples. This will be fixed in the next version of the manuscript, which will be uploaded soon.LEARN_Cis meant to represent algorithmic learning complexity, whereasLEARN_Sis meant to represent sample complexity. Those are completely separate.Q1: Would it be possible to restructure the taxonomy?
This is a very easy fix which we will implement within the next day. Essentially, we will fix the typo and clarify that
LEARN_Crefers to algorithmic learning complexity only.Q2: Does the typo affect the findings?
No. The categorization is as in Table 2.
We hope that correcting the typo in the manuscript will address your concerns.