Towards Formalizing Skepticism of Autoregressive Language Models: A Taxonomy in the Language of the Theory of Computation

Alongside acknowledgement of genuine success and hype, 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 ALMs that are more systematic and precise, and to distinguish conjecture, intuition, and formally proven results. Our framework distinguishes in-principle limitations from empirical ones, and surfaces an in-between category: arguments that appear to assert contingent limitations but, if correct, would establish fundamental ones not yet known to obtain.