Provable Limitations of Acquiring Meaning from Ungrounded Form: What Will Future Language Models Understand? (2021)

Abstract: Language models trained on billions of tokens have recently led to unprecedented results on many NLP tasks. This success raises the question of whether, in principle, a system can ever “understand” raw text without access to some form of grounding. We formally investigate the abilities of ungrounded systems to acquire meaning. Our analysis focuses on the role of “assertions”: textual contexts that provide indirect clues about the underlying semantics. We study whether assertions enable a system to emulate representations preserving semantic relations like equivalence. We find that assertions enable semantic emulation of languages that satisfy a strong notion of semantic transparency. However, for classes of languages where the same expression can take different values in different contexts, we show that emulation can become uncomputable. Finally, we discuss differences between our formal model and natural language, exploring how our results generalize to a modal setting and other semantic relations. Together, our results suggest that assertions in code or language do not provide sufficient signal to fully emulate semantic representations. We formalize ways in which ungrounded language models appear to be fundamentally limited in their ability to “understand”.

## introduction recently, language models trained on huge datasets of raw text have pushed the limits of natural language processing (devlin et al., 2019; raffel et al., 2019; brown et al., 2020, among others). such systems transcend the expert system paradigm, where rules about language and meaning are hardcoded into a system, as well as the supervised learning paradigm, where a notion of meaning is provided through ground-truth labels. rather, analysis of massive language models has revealed that, to some degree, knowledge of syntactic and semantic dependencies can emerge without explicit supervision (rogers et al., 2020; tenney et al., 2019). this knowledge can then be transferred to a variety of downstream nlp tasks. yet, today's nlp systems built on large language models still fall short of human-level general understanding (yogatama et al., 2019; zhang et al., 2020). brown et al. (2020) discuss the limitations of their gpt-3 language model compared with humans, suggesting that: scaling up any lm-like model . . . may eventually run into (or could already be running into) the limits of the pretraining objective. this possibility raises an interesting theoretical question. what are the fundamental limits of learning meaning from language modeling, even assuming a perfect learner with access to unlimited data? recently, bender and koller (2020) argued that achieving true natural language understanding from text alone is impossible, and that, to really get at meaning, some type of semantic grounding is necessary. @xcite their style of argumentation largely focused on developing thought experiments, rather than making formal arguments. one thought experiment featuring prominently in bender and koller (2020) was the task of learning to understand a programming language's semantics from raw code. here, understanding was defined as fully emulating a compiler. this setup has clear parallels to learning to understand natural language, although the more well-defined nature of programming languages makes them easier to reason about. bender and koller (2020) argue that emulation is difficult in this setting, and perhaps impossible, because the source code alone contains no information about how it should be interpreted to create outputs. one counterpoint raised by the paper, as well as others (michael 2020; potts, 2020), is the existence of unit tests, with assertions encoding examples of input/output pairs for blocks of code. @xcite for example, systematically observing blocks like @xmath0; assert @xmath1, because a programmer is likely to write assertions that will pass. these assertions constitute a form of implicit grounding embedded within language modeling by the pragmatic concerns of programmers, and they could potentially be leveraged to emulate a compiler. @xcite however, it is not immediately clear if unit tests provide ''enough'' supervision to do this, even with unlimited data. viewing the debate about the power of assertions as central to the larger philosophical question, we aim to clarify it in more formal terms. in this paper, we formally study whether observing a generalized notion of assertions can allow a system to ''understand'' strings. an assertion is a query about whether two strings evaluate to the same value within a fixed context. this is motivated by the role of assertions in unit tests, where asserting two expressions are equal suggests that they have the same value within the test. while assertions are directly motivated by the compiler thought experiment, they also have analogs in natural language, where sentences make assertions about the world, and it is reasonable to expect some form of bias towards true statements (potts, 2020). indeed, this is one of grice's maxims (grice, 1975): a set of basic principles proposed to govern the pragmatics of natural language. for example, the truth conditions of this cat is the cat that mary owns verify that two cats in the world identified in distinct ways are the same entity. in general, we might expect a sentence to appear with higher frequency if its truth conditions hold within its context, similar to an assertion in code, although of course there will also be other factors governing sentence frequency besides this. in this sense, the example sentence resembles the python statement assert @xmath2, where cat1 and cat2 are two cat objects. see section 6 for more discussion of how assertions and other formal concepts translate to natural language. we will generalize assertions to an abstract formal 2 unit tests are blocks of code in a software project that are designed to test whether the core code is behaving correctly. our findings are as follows. if every expression in a language has the same value in every valid context, then the language can be emulated using a finite number of assertion queries (section 4). however, we construct a class of languages where expressions can take different values in different contexts, and where assertions do not enable emulation, i.e., infinite queries would be required (section 5). intuitively, this means that assertions do not provide enough signal for a turing-complete emulator to fully ''understand'' languages from this class. we go on to discuss differences between our formal model and the less well-defined context of natural language (section 6). these results provide a formal way to characterize upper bounds on whether it is possible to emulate the semantics of a language from distributional properties of strings. within our framework, in certain settings, we find that meaning cannot be learned from text alone. we strengthen claims made by bender and koller (2020) that assertions in code do not necessarily provide sufficient signal for a language model to emulate understanding. we do not make strong claims about how these results transfer to natural language, although we expect that the added complexity of natural language would make it, if anything, more difficult to ''understand'' than code. @xcite ## preliminaries let l ⊆ σ denote a formal language over alphabet σ. we will use λ to denote the empty string. let (σ ) 2 denote the cartesian product of σ with itself; that is, the set of all pairs of strings. resembling clark (2010), we refer to a tuple l, @xmath3. we also use other symbols to refer to a context (e.g., κ = l, r ). we denote by λ 2 the empty context λ, λ . ## research question: do assertions enable emulation? there is a long history in ai of trying to define and measure understanding. turing (1950) constitutes an early behaviorist perspective; more recent approaches tend to emphasize not just an external view of a system's behavior, but also ''how it is achieved'' (levesque, 2014). understanding can be behaviorally diagnosed in neural models by evaluating them on benchmarks (wang et al., 2018). an alternate approach is probing (adi et al., 2017; conneau et al., 2018; hupkes and zuidema, 2018; hewitt and liang, 2019; belinkov and glass 2019), which investigates how directly a model's representations encode semantic relations by measuring if they can be easily decoded from them. similarly, we take the position that systems are capable of understanding if they emulate representations that are isomorphic to underlying meaning under important semantic relations like equivalence. we will formalize this in question 1, which asks whether such emulation is possible using assertions. definition 3 (ℵ-emulation) a class of languages l over σ is ℵ-emulatable if there exists an oracle turing machine μ and standard turing machine δ such that, for all @xmath4, κ ∈ (σ ) 2 , and e, @xmath5, definition 3 formulates emulation as a decision problem, as is typical in theoretical computer science. equivalently, δ can be replaced by a computable function ρ such that ρ(μ l (e) | κ) evaluates μ l (e) in context κ, that is, its output string is isomorphic to e | κ l under =. the functions δ and ρ are turing-reducible to each other, implying that if one definition is satisfied, so is the other. figure 2 : emulate implements an emulator μ. let all strings be an iterable enumerating all strings in σ . we provide a concrete implementation of all strings in figure 5 . with our definition of emulation in place, we can formally state the research question: how does question 1 relate to understanding in large language models? we imagine that, with sufficiently large amounts of data, the frequencies of strings in l carry enough signal such that the language model objective ''supervises'' access to ℵ l . thus, μ l (e) can be thought of as the language model representation of an expression e. we then hope to recover underlying semantic relations from the representations produced by the language model via some function δ. the class l corresponds to a set of hypothesis languages over which the language model must search for the true l. we will see that whether emulation is possible will depend on the properties of l. stepping back, question 1 bears on the role of assertions raised by bender and koller (2020). does observing assertions allow a turingcomplete system to emulate a compiler? in more general terms, are assertions powerful enough implicit grounding to achieve representations that encode the denotational semantics of a language? ## strong transparency we first consider the case where the language being learned is known to be strongly transparent. let transparent denote the class of strongly transparent languages. we will show that trans-parent is ℵ-emulatable. the core idea of the proof is to construct a canonical form for each expression. the canonical form is the first expression in a lexicographic ordering that the assertion oracle deems equivalent to the target expression. for technical reasons, the emulator returns the index of this string under the lexicographic order. proof. as python is turing-complete, we write μ : σ → n as a python function emulate in figure 2 . the function receives as input an expression expr and a callback function asserteq to an oracle computing ℵ l . for each @xmath6, there exists @xmath7, e | λ 2 ) = 1. in the ''worst case'', this holds when @xmath8. by construction, all strings reaches all strings in finite time. therefore, the number of loop iterations before reaching e is finite. we can conclude that emulate halts on every @xmath9, establishing that it is computable. now, we move towards justifying that the emulation is correct for every κ ∈ (σ ) 2 . we note that δ is simply the indicator function for equality over the natural numbers: the function emulate outputs @xmath10, the index of the first string e such that e | λ 2 @xmath11. now, let e, @xmath12. because the enumeration order of the for loop is fixed across computation of μ l (e) and μ l (e ): ## general case requiring strong transparency precludes a broad class of linguistic patterns allowing an expression to refer to different values in different contexts. for example, this includes assigning variable or function names in python, or binding pronouns in natural language. these constructions can make emulation impossible to achieve from assertions. we will construct a class of languages based on python where emulation is uncomputable. definition 4 let @xmath13, where strings in l m are defined according to figure 3 . for semantics, we first define m | κ l @xmath14. for any other @xmath15.8 expression, we define e | l, r l m as the value of e assigned by the python interpreter in the context l, r . for strings that are not valid python expressions, define e | l, r l @xmath16. what does it take to emulate the expressions leq() and true in l m ? if we knew m, then we could emulate them by simply comparing @xmath17. however, it turns out that recovering m for any l @xmath18. formalizing this, we will show that leq is not ℵ-emulatable. @xcite theorem 2 leq is not ℵ-emulatable. proof. without loss of generality, we focus on the contexts for leq() 9 and true within print(•), @xcite another example of a non-ℵ-emulatable language takes m to be a finite list of integers and replaces @xmath19. @xcite the only ''valid'' context for leq() is within print(•). the denotation of leq() when it occurs next to def is ∅. when @xmath20, it holds for all n that ℵ ∞ (leq(), true | n) = 1. to satisfy emulation of @xmath21, true}, μ ∞ makes a finite number of assertion queries for some sequence of contexts n 1 , • • • , n q , which we assume without loss of generality is sorted in increasing order. we can adversarially construct @xmath22, and thus μ ∞ (e) = μ m (e) for both e. to implement this, we simply set @xmath23. since μ ∞ (e) = μ m (e), we conclude that, for all n, on the other hand, consider @xmath24. in this case, therefore, the conditions of ℵ-emulation (definition 3) cannot be satisfied for both l m and l ∞ . this implies that leq is not ℵ-emulatable. ## stepping back in this work, we formalized an argument that was raised by bender and koller (2020) as a thought experiment. bender and koller (2020) question whether unsupervised training objectives are the right goal to target for achieving natural language understanding. if meaning is defined as identifying which object in the real world, or which set of situations, a linguistic element refers to, then, in a direct sense, an ungrounded system cannot understand meaning. but bender and koller (2020) go farther than this, claiming that an ungrounded system cannot even emulate understanding because it is not clear how a system should learn to interpret strings, even if it can model their distribution. we formalize this idea of emulation as ℵ-emulation. one counterargument mentioned by bender and koller (2020) is that indirect forms of grounding do exist in programming and natural language, which we formalize as assertions. the syntactic distributions of statements like assert allow us to indirectly observe semantic relations over the denotations. assertions are one way that the distribution of strings in a corpus is not blind to their semantics. by studying them, we study whether this indirect grounding enables a computational system to emulate the underlying semantic relations. key takeaways while assertions allow a system to emulate semantic relations in simple cases where the semantics are referentially transparent, we find that linguistic constructs like variable binding bring this task in conflict with the fundamental laws of computability. in other words, under our formal model of meaning and emulation, it is not just intractable for an ungrounded system to emulate understanding of a formal language, but, in some cases, impossible. we provide constructive examples where understanding must necessarily break down. we present these results in a well-defined framework building off formal approaches in logic, linguistics, and computer science. while we do not prove anything about natural languages, we do show that ungrounded models must fail to emulate equivalence in a very simple setting. a similar result likely extends to natural language understanding as well, which among other things, requires modeling referential identity (e.g., for sentences like manny is the cat). further, we believe much of our framework can be readily adopted in other works formalizing understanding in turing-complete systems. open questions in this work, we have focused on utterances, by default, as opposed to dialogues. an exciting extension would be to formalize a dialogue between two speakers, interrupted by the ''octopus'' of bender and koller (2020). @xcite existing theories of discourse could potentially be synthesized with this framework. what linguistic properties besides referential transparency relate to emulatability? can this framework be extended to formalize multimodal setups, where multiple oracles from different domains can potentially be combined to gain additional power? finally, is there a natural way to relax our standard of emulation towards a probabilistic definition, and how would this change the results? hongming zhang, xinran zhao, and yangqiu song. 2020. winowhy: a deep diagnosis of essential commonsense knowledge for answering winograd schema challenge. in proceedings of the 58th annual meeting of the association for computational linguistics, pages 5736-5745, online. association for computational linguistics. https://doi.org/10.18653/v1/2020 .acl-main.508