acceptodds
Under review as a conference paper at ICLR 2027

Taxonomizing Arguments for Language Model Skepticism in the Language of the Theory of Computation

Abstract

Alongside acknowledgement of genuine success and hype, language models (LMs), and in particular autoregressive language models (ALMs), have attracted skepticism: many believe that they are inherently limited in their capabilities. We systematically translate arguments for skepticism into the more precise language of the theory of computation. We contribute novel formalizations of several prominent arguments that were previously only described informally. We aim to enable analyses of skepticism of LMs that are more systematic and precise, and to distinguish conjecture, intuition, and formally proven results.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
language model, language model skepticism

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 3 reviews, above 27% of the others.
Reviewer_u6DaOpenReview ↗
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
  1. 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.

  2. 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
  1. 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.

  2. 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
  1. 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?

  2. 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
AuthorsOpenReview ↗

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_C vs. LEARN_S

You identified a typo in Section 3. Thank you. LEARN_C is 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_C is meant to represent algorithmic learning complexity, whereas LEARN_S is 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_C refers 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.

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.

AuthorsOpenReview ↗

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.

Reviewer_ox38OpenReview ↗
Rating
3(+1)
Confidence
1
Informativeness
2
Presentation
2
Soundness
1(−1)
Read review
Paper summary

The paper organizes arguments for language model skepticism using five categories: uncomputability, computational complexity, learnability, representational capacity, and category error. And it separates learnability into statistical identifiability, computational learnability, and optimization. Case studies of arguments associated with Chomsky, Bender, LeCun, Searle, and others illustrate the framework. The paper classifies existing capability and limitation results by their assumptions and epistemic status. Its validation consists primarily of literature comparisons and case analyses.

Critical strengths
  1. The paper provides a useful organizing framework by separating the type of limitation from its evidential status. Its classification tables and appendix identify the objects, assumptions, and status of the results. The paper also emphasizes that limitations of particular architectures on formal tasks do not directly establish the impossibility of human-level language generation.
  2. Several case studies in the paper clarify distinct targets of disagreement. These examples demonstrate the framework’s value in exposing underlying assumptions.
Critical weaknesses
  1. I find some category assignments difficult to reconcile with the distinctions introduced earlier. Table 2 places the polynomial-length CoT result under computational learnability, while Appendix A.14 discusses it as a change in representational capacity. As I understand it, the result concerns what a model can compute with additional decoding steps, rather than how efficiently training can discover the required parameters. The parsing example in Section 5.1 is less clear-cut: a mistaken interpretation could reflect limited capacity, but it could also reflect a failure to learn a representable solution. Since the paper is interpreting an informal argument, it would help to clarify what is being classified and how ambiguous cases are handled. Allowing multiple labels where appropriate might make the framework easier to apply consistently.
  2. The connection between human language emerging through evolution and the implications for P versus NP in Section 6 remains unclear to me. The authors acknowledge several limitations, but I would welcome more explanation of how this historical outcome bears on asymptotic computational difficulty. A narrower conclusion about applying hardness results to human language may be easier to support.
Questions for authors
  1. Could the author clarify why the CoT result is classified as computational learnability rather than representational capacity? For the parsing example, how does the classification distinguish a capacity limitation from a failure to learn? It would help to explain how the framework handles informal claims that allow more than one interpretation.
  2. Could the author clarify what the emergence of human language adds to the argument about P versus NP? I would find it helpful to distinguish the conclusion supported by this observation from the additional assumptions it requires.
5 comments
AuthorsOpenReview ↗

Thank you for the review

Thank you very much for the careful review.

W1: Poly-length CoT

Thank you for pointing out this issue. Table 2 contains a typo, and the category should be REPR, as discussed in the appendix. This will be corrected in the next version of the manuscript.

W1/Q1: Ambiguities

As suggested by you and another reviewer, the next version of the manuscript will identify secondary readings when the prose arguments allow multiple readings.

W2/Q2: Emergence of human language and P\mathsf{P} vs. NP\mathsf{NP}

We would welcome an interactive discussion here.

The first thing to emphasize is that our argument is conditional: if one believes that the worst-case hardness of learning human language transfers to the case of actual human language, then one needs to accept that either language emergence is an extremely unlikely event (in light of ETH being tentatively shown to not hold, perhaps merely near-exponentially unlikely) or that standard assumptions like P≠NP\mathsf{P} \neq \mathsf{NP} and NP⊈BPP\mathsf{NP} \not\subseteq \mathsf{BPP} do not hold. A prominent example where this argument applies is Van Rooij et al. (2024), who do appear to argue that the worst-case hardness of learning human language transfers to the actual case.

A second part of the argument is the connection between the problem of learning human language and the outcome of the physical process of evolution. We argue that something like human language must be learned by evolution, since a language that must somehow encode something like Turing machines is necessary to describe physical phenomena. We would be more than happy to interactively refine this argument if it doesn't make sense!

Thank you very much for your time and careful review and we look forward to a dialogue.

Reviewer_ox38OpenReview ↗

Thank you for your responses

Thank you for your further response. I now broadly understand why the paper discusses the link between language emergence and the P versus NP problem, and that the argument is conditional.

Overall, I understand the point the authors are trying to make. I acknowledge that my understanding of the relevant theory may be limited. However, I am still concerned about whether the classification criteria are sufficiently clear and consistent, and about what new insights the work provides.

As you noted in your response to another reviewer, “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.” How does the paper evaluate whether this reformulation or shift can make the debate clearer and easier to analyze? And, as a theoretical analysis, how does the paper ensure that this transcription faithfully and adequately conveys the meaning of the original argument? Or is this just proposing a “possible” interpretation?

I would also appreciate the opportunity to further discuss the paper’s positioning and its specific contribution.

Thank you for the questions!

How does the paper evaluate whether this reformulation or shift can make the debate clearer and easier to analyze?

In our view, formulating claims in the language of the theory of computation makes clear their epistemic status as possibly

  1. claims known to be correct,
  2. claims known to be incorrect, or
  3. unproven conjectures.

Here are examples:

In van Rooij et al. (2024), the mathematical formalization was made in the original paper, and so it was possible to check the proof (Guerzhoy (2026)). The issue in van Rooij et al. (2024) is actually precisely the transfer from worst-case to the human language issue, so the epistemic status of the claim is either “disproven as stated” or “downgraded to an unproven conjecture about transfer from worst-case algorithmic learnability to the human language instance pending reformulation, conditional on NP⊈BPP\mathrm{NP} \nsubseteq \mathrm{BPP}.”

If Bender and Koller (2020) are also understood as a LEARNS\mathrm{LEARN}_{S} argument, the epistemic status is “conjecture.” Similarly for LeCun (2022) interpreted as a LEARNS\mathrm{LEARN}_{S} argument.

We believe that clarifying the epistemic status of claims and showing that they are actually (usually) mathematical and empirical conjectures about learnability advances the understanding of the debate, because people advancing the claims often present them as unconditionally true/proven and self-evident, and likewise people contesting the claims often offer only competing intuitions.

And, as a theoretical analysis, how does the paper ensure that this transcription faithfully and adequately conveys the meaning of the original argument? Or is this just proposing a “possible” interpretation?

What we think we have are the best interpretations of the texts as written that we can offer. At the end of the day, as long as claims are in the domain of complex prose, it is possible to imagine that the author, and indeed every different reader, holds their own private interpretation of the text, or that the author expressed their private interpretation incorrectly in the text. We offer what we think advances the conversation in a useful way. In response, authors or any other readers of the authors’ texts might accept the formalization, or might offer a different one, might revise the text so that the text says something else, or might, once they see the formalization, change their beliefs about the claims and/or the world.

An example of this kind of conversation is the one we had the other day. You challenged Section 6, we clarified, and now the epistemic status is clearer.

To summarize

  1. We offer interpretations of texts, not of the authors’ private beliefs, or the private beliefs of the readers of the texts.
  2. We might be simply mistaken about what the best interpretation is in the same way that any claim/proof in an ICLR paper is mistaken. We don't think there can be a procedure for obtaining the definitive interpretation of complex prose. Authors often offer multiple contradictory interpretations of their own prose.
  3. In a situation like this, the goal is more to advance the conversation. The usual way those kinds of conversations go is with multiple rounds of reformulation and refinement by someone advancing a claim like the ones we analyze. Our paper is merely a first step in those kinds of conversations, but it is a necessary step.
Reviewer_sym2OpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
3
Soundness
1
Read review
Paper summary

This paper proposes a taxonomy for analyzing arguments about the limitations of language models using the theory of computation. It distinguishes five categories: computability, computational complexity, learnability, representation capacity, and category errors. The authors apply the taxonomy to arguments from the literature, including those concerning stochastic parrots, grounding, world models, and the Chinese Room argument. They also discuss theoretical results on neural architectures and argue that many skeptical claims ultimately concern learnability. The paper emphasizes that formalizing an argument does not establish its correctness and that theoretical results about specific architectures or tasks do not automatically generalize to human-level language generation.

Critical strengths
  • The taxonomy distinguishes different kinds of limitations that are often conflated in discussions of language models. This can help researchers formulate clearer claims and identify what evidence is required to support them.
  • The paper connects computational complexity, learnability, formal-language theory, and philosophical arguments about intelligence and understanding. The analysis of existing arguments demonstrates how the framework can expose hidden assumptions and clarify the scope of claims. The paper encourages readers to examine the assumptions behind a claim rather than treating every mathematical result as evidence of a general limitation of AI.
Critical weaknesses

The authors claim to introduce the first systematic taxonomy of (A)LM skepticism based on computational limitations. However, this claim is not sufficiently supported by a comparison with existing literature. In particular, Lin (2026), also systematically examines claims about LLM capabilities. Although the two frameworks differ, the authors should clarify how their taxonomy advances beyond existing work.

  • Several arguments can plausibly belong to multiple categories. The paper does not provide sufficiently explicit operational criteria for deciding between learnability, representation capacity, and computational complexity, which may limit reproducibility. Whether other researchers would consistently assign the same categories. That weakens the reproducibility and explanatory power of the framework.
  • The argument connecting physicalism, the emergence of human language-generating organisms, and computational complexity assumptions requires a more precise statement of its assumptions. In particular, the relationship between worst-case hardness and the probability of a physical process producing a capability is not sufficiently established.
  • The case studies are illustrative, but the paper does not establish whether the taxonomy produces more consistent or informative analyses than existing approaches. A proof about a restricted architecture and formal task does not automatically prove that all language models cannot achieve human-level language generation.

Lin, Z. (2026). Six misconceptions about large language models: A minimal model and diagnostic taxonomy. PNAS Nexus, 5(7). https://doi.org/10.1093/pnasnexus/pgag236

Questions for authors
  1. What systematic principles guided the selection of the five top categories? How do the authors justify their completeness and choice over plausible alternative classifications?
  2. Why are these categories the appropriate organizing principles, rather than alternative classifications or a hierarchy of necessary and sufficient conditions?
  3. How do the case studies demonstrate that the taxonomy improves the analysis of LM skepticism, rather than simply assigning existing arguments to predefined categories? Is there evidence that it reveals assumptions, inconsistencies, or limitations that would otherwise be missed?
  4. Is the taxonomy specifically designed for language models, or is it intended to apply more broadly to computational learning systems? How do the authors justify its scope, and what evidence supports its generalizability?
  5. Do the examples and theoretical discussions sufficiently support the paper’s broader claims about computational limits on language models? How are formal results under specific assumptions distinguished from conclusions about practical, real-world language capabilities?
  6. How do the authors ensure that their formalizations preserve the intended meaning of the original skeptical arguments?
3 comments
AuthorsOpenReview ↗

Thanks and Responses to W1 – W4

We thank the reviewer for the feedback.

We would like to reiterate what we see as the primary contribution of the paper. The contribution is expressing common prose arguments about the capabilities of (A)LMs in the language of the theory of computation. The taxonomy is the natural consequence of the translation into the language of the theory of computation and is not by itself the point of the paper. We believe we are the first to systematically translate very common prose arguments into precise mathematical language, and to point out that a taxonomy of prose arguments arises as a result.

Please see below for specific answers regarding your feedback.

W1: "The authors claim to introduce the first systematic taxonomy of (A)LM skepticism based on computational limitations. However, this claim is not sufficiently supported by a comparison with existing literature. In particular, Lin (2026), also systematically examines claims about LLM capabilities. Although the two frameworks differ, the authors should clarify how their taxonomy advances beyond existing work."

You are right to point to Lin's (2026) July 2026 paper, which we will cite. The key distinction between our contribution and Lin is that while Lin offers competing intuitions about language model capabilities, we offer precise mathematical formulations. We also note that we offer a true taxonomy, in the sense that arguments that on their face sound very different end up in the same category. On the other hand, Lin offers what is better described as a list of 6 common arguments (what Lin calls "misconceptions"). Lin offers no mathematical formulations, and does not connect arguments to the theory of computation. Lin's contribution is therefore fundamentally distinct from ours despite superficial similarities in the titles. Lin's valuable contribution is in offering competing intuitions. Our contribution is in translating intuitions into the language of mathematics.

W2: Several arguments can plausibly belong to multiple categories. The paper does not provide sufficiently explicit operational criteria for deciding between learnability, representation capacity, and computational complexity, which may limit reproducibility."

We agree that some prose arguments could be categorized in multiple ways, and that this is a limitation. If your advice is to assign to multiple categories rather than choose the best one, we are happy to consider it.

We strongly disagree with the framework on requiring explicit operational criteria for understanding complex prose. Learnability, representation capacity and computational complexity are of course completely conceptually distinct; the genuine difficulty in classifying complex prose arguments is in understanding authorial intent in complex prose. In our opinion, "explicit operational criteria" is not the right framework here, as shown by many decades of attempts in GOFAI to produce those.

In other words, in our view, the taxonomy is clear. The inherent ambiguity is in interpreting complex prose.

We welcome feedback on this point if the reviewer has concrete suggestions.

W3: "The argument connecting physicalism, the emergence of human language-generating organisms, and computational complexity assumptions requires a more precise statement of its assumptions. In particular, the relationship between worst-case hardness and the probability of a physical process producing a capability is not sufficiently established."

You are correct to say that worst-case hardness does not transfer to actual-world probability. However, our argument does not rely on this. Rather, we point out in the paper that if someone's argument (exemplified most strongly by van Rooij et al. (2024)) relies on worst-case hardness and the transfer of the worst-case hardness to actual-world probability as a premise, then they might like to revise they credence in assumptions like P!=NP. Our argument is conditional.

We recognize the argument is compressed. We believe it is correct as stated. We welcome discussion here and will expand in the appendix as necessary.

W4: "The case studies are illustrative, but the paper does not establish whether the taxonomy produces more consistent or informative analyses than existing approaches"

We would like to emphasize that our goal is not to analyze and categorize a corpus of arguments. Rather, the contribution is in translating commonly-cited prose arguments into a mathematical framework, and contributing to the mathematical understanding of the discourse. The goal is understanding rather than collecting statistics. We believe your argument would apply more strongly if the goal were to compute statistics of a corpus of arguments.

AuthorsOpenReview ↗

Responses to Q1 – Q6

Q1: “What systematic principles guided the selection of the five top categories? How do the authors justify their completeness and choice over plausible alternative classifications?”

Representation capacity, computational complexity, learnability, and computability are the main four frameworks for analyzing problems in the language of the theory of computation. A "category error" refers to the claim that language capacity is not computational, and therefore by definition not amenable to computation-theoretic analysis. Therefore, completeness follows by design, and alternative classifications can only be finer-grained categories.

Q2: “Why are these categories the appropriate organizing principles, rather than alternative classifications or a hierarchy of necessary and sufficient conditions?”

The categories are the organizing principles of the theory of computation rather than of a taxonomy that we propose. We argue that they are appropriate because the theory of computation is the appropriate framework for analyzing claims about the capabilities of computational models. In our opinion, this is the key contribution of the paper.

Q3: “How do the case studies demonstrate that the taxonomy improves the analysis of LM skepticism, rather than simply assigning existing arguments to predefined categories? Is there evidence that it reveals assumptions, inconsistencies, or limitations that would otherwise be missed?”

We would put it differently. The main benefit is from explicitly thinking of objection in precise computation-theoretic terms. The best example of the process being productive is in Sections 5.4 and and 6, where we discuss an existing analysis and present a new one that would not have been possible without putting prose arguments in precise terms.

Q4: “Is the taxonomy specifically designed for language models, or is it intended to apply more broadly to computational learning systems? How do the authors justify its scope, and what evidence supports its generalizability?”

We do not claim generalizability beyond the context of language models (i.e., models of human language). The extended Church-Turing thesis (see Aaronson and Chen https://dl.acm.org/doi/abs/10.5555/3135595.3135617 ) would appear to imply generalizability beyond language, but that is not in the scope of the paper.

Q5: “Do the examples and theoretical discussions sufficiently support the paper’s broader claims about computational limits on language models? How are formal results under specific assumptions distinguished from conclusions about practical, real-world language capabilities?”

The paper does not make broad claims about computational limits of language models. Rather, we analyze others' arguments. If we misunderstood your concern, we are happy to elaborate.

Q6: “How do the authors ensure that their formalizations preserve the intended meaning of the original skeptical arguments?”

Translating complex prose into formal arguments is inherently subjective. For that reason, as we say in the paper, the formalizations should be viewed as a best attempt at reconstructing each author's intent. The paper's contribution is not in producing an authoritative interpretation of each author, but rather in pointing out the connection between prose and the best attempt at a mathematical formalization.

Hello, we were wondering whether some of you concerns have been addressed and whether you have more questions.

Comments on the paper

2 comments

Dear Reviewers and AC,

We have submitted a revised version of the manuscript which address the concerns of the individual reviewers, as promised in our previous responses.

We have also slightly updated Section 6 in light of the news that OpenAI claims to have refuted the Exponential Time Hypothesis (ETH). This, if true, illustrates that epistemic doubt about P!=NP is a live possibility ("If true, their claim implies a variety of other NP problems now all have faster algorithms as well. Since 3SAT is NP complete, this should make every computer scientist put at least a little more weight on the possibility of P = NP." -- Ryan Williams https://people.csail.mit.edu/rrw/ https://x.com/rrwilliams/status/2114891837265834264 ). Note that our paper makes no unconditional claims about P vs NP. We merely point to the news to make the argument that Section 6 is interesting.

Two of the reviewers raised a similar concern regarding Section 6: that worst-case hardness does not translate to a specific instance of human language. We agree. That is why our original text specified that the premise is that the worst-case hardness DOES transfer to the specific instance; this is not a premise we agree with, but rather a premise that is implicitly relied on by learnability arguments.

We have added an appendix by the request of u6Da to address their concern about the lack of full formalization of claims.

We look forward to discussing things with you! Although the time remaining is short, we would be happy for the opportunity to address your concerns, and will respond as promptly as possible.

AuthorsOpenReview ↗

case for general public and ML interest in this paper

Dear Reviewers and AC,

We believe we have addressed the technical questions below. We would also like to explain why we think this paper will interest many readers. The range of reviews suggests that the paper may not appeal to everyone, and the discussion here shows the kinds of questions it can bring into focus.

As we emphasize in the comments, the value comes from making a first step towards making the intuitions precise, not in taxonomizing the arguments by itself.

  1. There is broad public interest in AGI, but little of the debate goes beyond competing intuitions and extrapolations. This paper offers computer scientists a way to ground and qualify their views on the possibility of AGI.

  2. Many researchers in machine learning follow the AGI debate closely and participate in it. Debating LeCun, Bender and Koller, etc on those topics is very common in ML social spaces. We show that prominent arguments by LeCun, by Bender and Koller, by Pearl, and by van Rooij et al. fit within a common framework and, in many cases, reduce to the same form. We believe this finding is of interest in its own right. The framework also accommodates Lovelace’s nineteenth-century argument and later arguments by Fodor and Chomsky.

  3. We find the connection between the AGI debate in machine learning and the theory of computation intellectually exciting. We think many ICLR attendees would share our interest in the connection developed in Section 6. Recent discussion of how much weight to give the possibility that P = NP makes this question especially timely [1] (again, we do not take a position on P vs NP -- we are just pointing out that this topic is more prominent due to OpenAI's claimed refutation of the ETH).

In summary, the discussion here gives us reason to believe the paper would interest many ICLR attendees. Its contribution is to show how tools from computer science can advance the broader debate about AGI.

We will be online for part of the next 12 hours to answer any last-minute questions. Thank you for engaging with our paper.

[1] Ryan Williams wrote:

If true, their claim implies a variety of other NP problems now all have faster algorithms as well. Since 3SAT is NP complete, this should make every computer scientist put at least a little more weight on the possibility of P = NP.

Ryan Williams’s homepage: https://people.csail.mit.edu/rrw/

Original post: https://x.com/rrwilliams/status/2114891837265834264

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.