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

Introduction

Recently, language models trained on huge datasets of raw text have pushed the limits of natural language processing (devlin-etal-2019-bert; raffel2019exploring; brown2020language, 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 (rogers2020primer; tenney-etal-2019-bert). 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 (yogatama2019learning; zhang-etal-2020-winowhy). brown2020language discuss the limitations of their GPT-3 language model compared to 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, bk-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.See blog2020 for a summary of the informal discussion around bk-2020, much of which took place on social media. Their style of argumentation largely focused on developing thought experiments, rather than making formal arguments.

One thought experiment featuring prominently in bk-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. bk-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 (blog2020; potts2020), is the existence of unit tests, with assertions encoding examples of input/output pairs for blocks of code.Unit tests are blocks of code in a software project that are designed to test whether the core code is behaving correctly. For example, systematically observing blocks like x = 3; assert x == 3 could let a system bootstrap the semantics of variable assignment, 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.Contexts like assertions can be seen as an argument in favor of the distributional hypothesis harris1954distributional. 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 (potts2020). Indeed, this is one of Grice’s Maxims (grice1975logic): 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 cat1 == cat2, where cat1 and cat2 are two Cat objects. See LABEL:sec:towards-nl for more discussion of how assertions and other formal concepts translate to natural language. We will generalize assertions to an abstract formal language context, allowing us to study how they can be used to emulate semantic relations.

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 (LABEL:sec:towards-nl). 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 bk-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.LABEL:sec:old-emulation documents and motivates conceptual changes since the original arXiv version of the paper.

Preliminaries

Let $L\subseteq\Sigma^{\star}$ denote a formal language over alphabet $\Sigma$. We will use $\lambda$ to denote the empty string.

Let $(\Sigma^{\star})^{2}$ denote the Cartesian product of $\Sigma^{\star}$ with itself; i.e., the set of all pairs of strings. Resembling clark2010three, we refer to a tuple $\langle l,r\rangle\in(\Sigma^{\star})^{2}$ as a syntactic context. We also use other symbols to refer to a context, e.g., $\kappa=\langle l,r\rangle$. We denote by $\lambda^{2}$ the empty context $\langle\lambda,\lambda\rangle$.

We will model formal languages not just as sets of strings, but as having an associated semantics.We slightly abuse notation by using $L$ to refer to both a set of strings, and a set of strings paired with a denotation function, which could be written more verbosely as $\langle L,\llbracket\cdot\rrbracket_{L}\rangle$. Specifically, we assume the existence of a denotational semantics over every substring of $L$, which we now elaborate on. Let $Y$ be a countable set of referents. First, we will say that some $e\in\Sigma^{\star}$ is a valid expression within the context $\kappa=\langle l,r\rangle$ if there exists some contextual denotation $\llbracket e\mid\kappa\rrbracket_{L}\in Y$. Intuitively, this represents the value of $e$ when it occurs in the larger context $ler\in L$. We will also use the notation $\llbracket e\mid l,r\rrbracket_{L}$ where convenient. We will reserve $\emptyset\in Y$ as a special null symbol, defining $\llbracket e\mid\kappa\rrbracket_{L}=\emptyset$ iff $e$ is not a valid expression in the context $\kappa$.Our simple model of denotations does not reflect the full range of semantic theories that have been proposed for natural language. In particular, our denotations $\llbracket e\mid\kappa\rrbracket_{L}$ depend only on the linguistic context $\kappa$ rather than any external world state. This differs substantially from how truth conditions are traditionally conceptualized in formal semantics (Heim1998-HEISIG). For example, in our framework, the referent of English $\llbracket\textit{the dog}\mid\kappa\rrbracket_{L}$ must be fixed with no regard for the extralinguistic context. LABEL:sec:towards-nl further contrasts our setup with the richer semantics of natural language.

Each context $\kappa\in(\Sigma^{\star})^{2}$ also has a support, or set of expressions that are valid within it:

2 Strong Transparency

As defined above, we make very few assumptions about denotations. They are not necessarily compositional, and expressions may take different referents in different contexts. However, we saw in the integer expression language that the meanings of an expression did not depend on its context. We now define a property formalizing this idea.

$L$ is strongly transparent iff, for all $e\in\Sigma^{\star}$, $\kappa\in(\Sigma^{\star})^{2}$, either $\llbracket e\mid\kappa\rrbracket_{L}=\llbracket e\mid\lambda^{2}\rrbracket_{L}\neq\emptyset$, or $\llbracket e\mid\kappa\rrbracket_{L}=\emptyset$.

Strong transparency resembles referential transparency (russell25), but is a stronger condition, in that it does not allow the same name to ever refer to different values. For example, for a Python program, strong transparency does not allow assigning local variables within a function, even if the function output would remain completely specified by its inputs.

3 Assertion Queries

We now define an oracle function providing assertion information about expressions in $L$, resembling assert e1 == e2 for two Python expressions e1, e2. A system is granted access to this function, and it can make assertion queries to it in order to learn about the semantics of $L$.This resembles the role of queries in classical grammar induction works (e.g., angluin1987queries). An assertion query tells us whether two expressions $e,e^{\prime}$ are equivalent within the context $\kappa$.

For $e,e^{\prime},\in\Sigma^{\star}$ and $\kappa\in(\Sigma^{\star})^{2}$, define the assertion oracle

The $\aleph_{L}$ oracle is motivated by assertion statements in programming languages, which occur naturally in environments like unit tests. The distribution of strings in a corpus of code should capture some notion of this oracle, since a programmer is more likely to assert two expressions are equal if they are expected to have the same value. Our goal is to study the limits of understanding achievable from raw text, so we consider an “upper bound” setup by assuming a system has full access to $\aleph_{L}$. Can the system use this powerful oracle to emulate the underlying semantics?

4 Turing Machines

Our notion of language understanding will be based around the idea of emulation, which in turn requires a model of computational realizability. We will use Turing machines (turing1936computable) as a model of universal computation. We write $\mu(e)$ for the output of Turing machine $\mu$ evaluated on input $e\in\Sigma^{\star}$. We will also define an oracle Turing machine as a standard Turing machine that can compute a blackbox “oracle” function $f$ as a subroutine. We imagine the machine has a special query instruction and tape. After writing $x$ to the query tape and executing the query instruction, the query tape will contain $f(x)$. We will write $\mu_{f}(e)$ for the Turing machine $\mu$ evaluated on input $e$ with oracle access to $f$. In the case where $f=\aleph_{L}$, we will simply write $\mu_{L}(e)$. Whereas, in computability theory, oracle Turing machines are generally leveraged to make reductions from uncomputable problems, here we will use them to formalize the ability of an emulator to make assertion queries about $L$. This oracle provides additional power because these queries contain additional information beyond that encoded in the input expression.

Research Question: Do Assertions Enable Emulation?

There is a long history in AI of trying to define and measure understanding. turing1950computing 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” (levesque2014). Understanding can be behaviorally diagnosed in neural models by evaluating them on benchmarks (wang-etal-2018-glue). An alternate approach is probing (adi2017fine; conneau-etal-2018-cram; ijcai2018-796; hewitt-liang-2019-designing; belinkov2019analysis), 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.

$\mu$ can be thought of as an emulator that evaluates expressions, whereas $\delta$ receives two values and decides whether they are equal. Crucially, only $\mu$ has direct access to $\aleph_{L}$. $\delta$ can only use information from the oracle to the extent that it is encoded in the representations $\mu_{L}(e)$ and $\mu_{L}(e^{\prime})$.

Definition 3 formulates emulation as a decision problem, as is typical in theoretical computer science. Equivalently, $\delta$ can be replaced by a computable function $\rho$ such that $\rho(\mu_{L}(e)\mid\kappa)$ evaluates $\mu_{L}(e)$ in context $\kappa$, i.e., its output string is isomorphic to $\llbracket e\mid\kappa\rrbracket_{L}$ under $=$. The functions $\delta$ and $\rho$ are Turing-reducible to each other, implying that if one definition is satisfied, so is the other.

With our definition of emulation in place, we can formally state the research question:

For a class of languages $\mathcal{L}$, is $\mathcal{L}$ $\aleph$-emulatable?

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 $\aleph_{L}$. Thus, $\mu_{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 $\delta$. The class $\mathcal{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 $\mathcal{L}$.

Stepping back, Question 1 bears on the role of assertions raised by bk-2020. Does observing assertions allow a Turing-complete 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 Transparent is $\aleph$-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.

Now, we move towards justifying that the emulation is correct for every $\kappa\in(\Sigma^{\star})^{2}$. We note that $\delta$ is simply the indicator function for equality over the natural numbers:

where the last step follows by strong transparency. We conclude that the conditions for emulation (Definition 3) are fully satisfied. ∎

Through a simple construction, we have shown it is possible to emulate meaning from assertion queries for languages with strongly transparent semantics. The number of bits in the emulated representation $\mu_{L}(e)$ is linear in the size of $e$. In the next section, we consider what happens without strong transparency, where, among other complexities, values can be bound to variables, complicating the construction used in Theorem 1.

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.

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 $n<m$. However, it turns out that recovering $m$ for any $L_{m}\in\textsc{Leq}$ is not possible with a fixed number of assertion queries. Formalizing this, we will show that Leq is not $\aleph$-emulatable.Another example of a non-$\aleph$-emulatable language takes M to be a finite list of integers and replaces \color[rgb]{1,0,0}n\; < M with \color[rgb]{1,0,0}n\; in M.

Without loss of generality, we focus on the contexts for leq()The only “valid” context for leq() is within print($\cdot$). The denotation of leq() when it occurs next to def is $\emptyset$. and True within print($\cdot$), each of which is parameterized by some value of $n$. Notationally, we identify each $L_{m}$ with $m$, and each context with its parameter $n$. This enables shorthand like $\llbracket e\mid n\rrbracket_{m}$ for the denotation of the expression $e$ in the context parameterized by $n$ in $L_{m}$.

for some sequence of contexts $n_{1},\cdots,n_{q}$, which we assume without loss of generality is sorted in increasing order. We can adversarially construct $m^{\prime}\neq\infty$ such that all these queries are the same, and thus $\mu_{\infty}(e)=\mu_{m^{\prime}}(e)$ for both $e$. To implement this, we simply set $m^{\prime}=n_{q}+1$. Since $\mu_{\infty}(e)=\mu_{m^{\prime}}(e)$, we conclude that, for all $n$,

On the other hand, consider $n>n_{q}$. In this case,