On Limitations of the Transformer Architecture
Authors: Binghui Peng
Srini Narayanan
Christos Papadimitriou
Venue: COLM (2024)
Keywords: Transformer, computation complexity, communication complexity
TL;DR: The power and limitation of Transformer architecture

Abstract: What are the root causes of hallucinations in large language models (LLMs)?  We use Communication Complexity to prove that the Transformer layer is incapable of composing functions (e.g., identify a grandparent of a person in a genealogy) if the domains of the functions are large enough; we show through examples that this inability is already empirically present when the domains are quite small.  We also point out that several mathematical tasks that are at the core of the so-called compositional tasks thought to be hard for LLMs are unlikely to be solvable by Transformers, for large enough instances and assuming that certain well accepted conjectures in the field of Computational Complexity are true.

Published as a conference paper at COLM 2024
On Limitations of the Transformer Architecture
Binghui Peng
Department of Computer Science
Columbia University
bp2601 192601@columia.coo
Srini Narayanan
Google DeepMind
srininegoogle.co
Christos Papadimitriou
Department of Computer Science Columbia University christos@columbia.
Abstract
What are the root causes of hallucinations in large language models (LLMs)? We use Communication Complexity to prove that the Transformer layer is inca incapable of composing functions (e.g., identify a grandparent of person in genealogy) if the domains of the functions are large enough; we show through examples that this inability is already empirically present when the domains are quite small. We also point out that several mathematical tasks that are at the core of the so-called compositional tasks thought be hard for LLMs are unlikely to be solvable by Transformers, for large enough instances and assuming that certain well accepted conjectures the field of Computational Complexity are true.
Introduction
The Transformer architecture (Vaswani et al., 2017), an otherwise singularly promising approach to AI, is known to be plagued by the problem of hallucinations: an answer to a user prompt is too often incompatible with the device's training data and prompt. There is now vast literature on hallucinations and their nature, typology, and remedies, see for example the survey (Ji et al., 2023).
Are there root causes of the hallucination phenomenon that can be imputed to the Trans- former architecture? Theoretical limitations of Transformers have been pointed out the past, starting with Hahn's 's 2020 paper (Hahn, 2020), where it was proved that Transformers cannot recognize simple patterns such as parity (e-g., whether a phrase contains an even number of negations) or balanced parentheses. However, the elegant proofs in Hahn (2020), inspired by Complexity Theory, are asymptotic in nature, and it appears that the proven limitations take hold only for unrealistically large inputs; in fact, it has been demonstrated that there are Transformers on which these functions can be computed reliably for all practi- cal purposes (Ebrahimi et al., 2020; Yao et al., 2021). Transformers have also been studied through Complexity Theory an important lens for understanding the limitations of com- putational systems - culminating Merrill Sabharwal (2023b), where it was shown that, computationally, Transformers belong to rather weak complexity class, namely logspace- uniform T we elaborate on this point of view in Section 4. Also recently, Sanford, Hsu, and Telgarsky (Sanford et al., 2023) identified a particular mathematical problem called 3-Matching, which cannot be computed by single-layer multi-head Transformers: Given sequence of integers, identify three numbers the sequence that add up to zero modulo given large number. Very interestingly, (a) the easier problem of 2-Matching can be solved

---

Published as a conference paper at COLM 2024
by Transformers, but cannot be solved by feed-forward deep nets, establishing a kind of supremacy of Transformers over the rest ML; and (b) these negative results manifest themselves for rather small prompt sizes. Note that, the conceptual contribution of this result notwithstanding, the 3-matching function identified in Sanford et al. (2023) is not compelling example of the kinds of problems that Transformers are meant to solve. The question arises, can we identify impossible tasks that are closer to the intended use of the architecture? This is our focus here. We point out a new fundamental limitation of the Transformer architecture, namely that it has serious difficulties computing a very simple, and practically important, semantic operation we call function composition, explained next.
In a recent paper on the topic of hallucinations (Guan et al., 2024), the opening example a wrong answer to the question what is the birthday of Frédéric Chopin's s father?, when these two facts were included in the prompt: (a) the father of Frédéric Chopin was Nicolas Chopin and (b) Nicolas Chopin was born on April 15, 1771 This is an example of function composition, where the functions to be composed are birthday-of and father-of. Interestingly, the aforementioned paper (Guan et al., 2024) goes on to propose retrofitting Transformers with Knowledge Graphs - precisely the right tool for performing function composition in order to mitigate hallucinations. Another example of function composition would be, given the facts London is in the UK, Alan Turing was born in London, among other such facts, ask: In which country was Turing born? Or, presented with Matthew's genealogy (Mat): Abr was the father of Isaac, Isaac was the the father of Jacob, have any grandchildren?
and so on with 39 more sentences of this type, ask: Did Isaac
Besides its critical role in combining relational information in the data, function composition is also an important ingredient of language understanding, the core com competence of Trans- formers. In the field of pragmatics, indexicals are words referring to entities in the context in which the utterance occurs. For example his in the sentence I have a brother and his name is John, or this in the sentence this dog has style are indexicals. Now, when in an utterance one indexical refers to another, understanding the utterance entails function composition. Consider this:
Transformers occasionally hallucinate, that is, they generate output inconsistent with the training data and prompt. However, this deficiency is rather rare, and techniques such as post-filtering can alleviate it.
Understanding what is meant by the last word it of this utterance, one needs to compose two indexicals: First one has to recognize that the indexical it points to this deficiency, and then that this deficiency refers to the particular deficiency that Transformers occasionally hallucinate. It appears that humans have little difficulty composing idexi- cals - but how about Transformers?
So it seems desirable - indeed important - that LLMs perform function composition reliably. In this paper we prove that they cannot: function composition is an inherent weakness of the Transformer architecture. In particular, we show that a single Transformer attention layer cannot compute the answer to function composition query correctly with significant probability of success, as long as the size π of the domain of the function satisfies n log n > H(d+ + 1)p, where dl is the embedding dimension, p is the precision, in bits, required for the calculation, and H is the number of attention heads. In fact, the proof of our impossibility theorem suggests that this weakness has its roots in the nature of the softmax computation that allows the next embedding of a token to be computed with very scant non-local information.
Our impossibility result holds for single, multi-headed attention layer; however, we suspect that the weakness that it exposes also burdens multi-layer Transformers, and in Appendix B we see anecdotal evidence that LLMs appear unable to reliably compose functions with domains that are far smaller.
It is a tragic coincidence that the great romantic composer Frédéric Chopin was tormented by hallucinatory episodes throughout his brief life...
2

---

Published as a conference paper at COLM 2024
The chain of thought maneuver (CoT) (Wei et al., 2022) is known to help with the problem of hallucinations by inducing the LLM to generate prompts which break down the task in hand into smaller steps eventually leading to the correct answer. Indeed, simple CoT scheme can plausibly mitigate our impossibility result on composition by generating a short prompt. However, we also prove a theorem implying that Transformer layer with CoT needs far more tokens in the generated CoT prompt to solve the composition problem for cascade of many compositions (Theorem 2)
We also provide a different impossibility argument that holds for any number of layers, and concerns a different genre of hallucinations: wrong answers to compositionality tasks. In Dziri et al. (2023), it is demonstrated through extensive experimentation that Transformers have trouble carrying out tasks that require sequential composition of elementary tasks, such as multiplying multi-digit integers and solving logical puzzles, and in fact this failure grows quickly with the required depth of composition. We point out (Theorem 3) that, under widely accepted complexity assumption multi-layer Transformers are incapable of performing several elementary computations that are crucial in carrying out compositionality tasks such those discussed in Dziri et al. (2023).
akin to P & NP albeit in the domain of memory
Finally, it has been often pointed out that it is the very nature of Transformers probabilistic language generators that renders them likely to veer off their grounding on the training data and prompt see for example McCoy et al. (2023), where it is demonstrated through extensive experimentation that low-probability answers (as well as low-probability inputs, or low-probability t tasks) are harder for transformers to get right. In general, LLM models maximize the probability of generating the next token given the context in an auto-regressive manner, and this must continue even when there is no clear winner. That is, the LLM gener- ates outputs even when the probability of the predicted token is low. When this intensifies, the model will generate low-likelihood series of tokens, resulting in an unreliable output.
There are many situations when this could happen. First, as McCoy et al. (2023) point out, LLM are particularly bad when there a low probability of the input, task, or output, even if the underlying training sequence is deterministic. Yet another case is one where the input context is under-specified or ambiguous. When the input context does not provide sufficient information for clear and optimal token choice, the estimated probabilities obtained from applying the logit function to the softmax output of the transformer are distributed such that the difference between the highest and subsequent probabilities is relatively small, there is a higher chance that in the auto-regressive model, the incorrect token will be picked. This situation is also correlated to the case where the conditional entropy is likely high. In all these cases, the generation of the incorrect token is more likely; and once the sequence has an incorrect next token, there is significant chance that this error cascades into a hallucination. In a recent paper (Kalai & Vempala, 2023), this phenomenon is studied more formally by considering the statistics of very rare patterns in the training data.
2 Preliminary definitions
Transformer. To model mathematically computation by Transformers, we adapt slightly slighllightly the formal model of (Sanford et al., 2023). A self-attention unit is a function A: (RD)N + (IR)) where Ni is the sequence length, D is the embedding dimension, and d is the output dimension. A is defined in terms of three real matrices K, Q, V E RdxD, For simplicity, we assume that the key, query, value matrices K, Q, V share the same dimension. On input x (Xi...,, E (RR),, the attention unit A calculates, for each i = 1,..,,N the output
= = Σ VijV Rd NE[N]
(1)
3

---

Published as a conference paper at COLM 2024
where the attention probability
(fi.....,,I,N)) softmax(z; Q Kx Q KxN)
exp(x; Q Kx1)
exp(x; Q KxN) EjE(N] exp(x; Q QU Kxj)
E EjeN NJ exp(x; [xxxxexp(x; Q Kxy))
We assume that the computations of the self-attention unit are carried out with a precision of p bits.
An H-headed transformer layer L consists of H self-attention units sharing the same input, together with combining function ① which maps, for each the H outputs of the layer to an output token in Rd. Finally, Transformer 'T is the cascade of several transformer layers.
Notice that our definition ignores certain features of the Transformer architecture, such as input embedding and pre- and post-processing of individual tokens by feed-forward networks; however, it is easy to see that input embedding and the pre-processing can be absorbed the input tokens, while post-processing can be incorporated into the combining function 4 and therefore, this omission does not affect the validity of our argument.
Function composition. We next define the function composition problem. Consider two functions, 8 mapping domain A to domain B, and mapping B to another domain C- for example, {a)) could be the mother of person a E A, and f(b) is the profession of person b E B. These functions will be described in a prompt X. The N tokens of X are divided into three parts:
Part The first part describes the function g through |A] sentences in simple, unambiguous language separated by puncluation, e.g. the mother of John is Helen; the mother of Charlotte is Eve; etc.;
Part 2. Similarly, the second part consists of B] sentences describing the function f, e.g. Helen is a doctor; Jane is a teacher; etc. and
Part 3. The query, e.g. what is the profession of John's mother??
Notice that the number N of input tokens is a small multiple of the domain size the functions. We say that an H-headed Transformer layer L computes the function composition correctly if, for any input prompt in the correct format, the output of the layer corresponding to the token of the query (to the token ? or potentially <eos> in this example) is the correct answer of the composition query.
In the body of the paper also introduce similar tasks, such iterated function composi- tion and reachability, whose definitions are simple extensions of the above.
Information theory.
We use standard notation from information theory. If X,Y, Z are random variables, H(X) is the entropy of X and I(X;Y) () is the mutual information between X and We write In(.) for the natural logarithm and log(-) for base two.
3 The Impossibility of Composition
We prove the following:
Theorem 1. Consider function compusition problem with input domain size |A| B |C| n, and an H-headed transformer layer C with embedding dimension and computation precision p, and assume that Hdd + 1)p problem. In particular, if R = n log - H(d + 1)p > 0, then the probability, over all possible functions and queries, that L answers the query incorrectly is at least R
log Then L. cannot solve correctly the function composition
3n logn
The proof relies on Communication Complexity (Kushilevitz Nisan, 1996), subfield of Complexity Theory in which one measures the number of bits that need to be exchanged
2It is fine to think that these sentences come in this order, but the proof does not require it.
4

---

Published as a conference paper at COLM 2024
between distributed computational agents possessing different parts of the input, in order for one of them to obtain the result of the computation. The agents are assumed to have unbounded computational capabilities, and to be restricted only in terms of their communi- cation. One important classical result in Communication Complexity is the communication difficulty of the set disjointness problem: If Bob and Alice are each given a vector of bits and they want to compute the Boolean inner product of these bit vectors - that is, to tell if there is an index such that the ith bit of both Bob and Alice is 1 then they must communicate n bits. In fact, this result used is in the impossibility proofs in Sanford et al. (2023). Another classical problem in this field is pointer chasing: Alice and Bob are given two functions A and B, respectively, from [n] to [r1) and they need to compute a composition of these functions, say ( (B(A((((()))) ))) Compositions can obviously be computed by the agents alternatingly communicating log n bits to each other: in this example, Alice communicates to Bob the value of (O), then Bob tells Alice the value of (()))), and so on. But what if one less rounds of communication is allowed? Or, if the same number of rounds is allowed, but Bob must start? Over the four decades since this problem was first posed (Papadimitriou & Sipser, 1982), it has been shown that, if one less round of communication is desired, or if Bob has to start the communication, then exponentially more bits must be exchanged. These lower bounds have been used to inform many fields of Complexity, including lower bounds of bounded-depth circuits, see for example Kushilevitz & Nisan (1996), and even the complexity of Machine Learning (Chen al., 2022).
Here we use slight variant of this classical framework. We assume three agents, whom we call Faye, Grace, and Xavier. Faye knows a function f from [n] to [n), Grace knows another such function 8, and Xavier knows a number x E [zz]. We can actually assume that Faye and Grace both know Xavier's value x. The only communication allowed is from Faye and Grace to Xavier - not between Faye and Grace. Our goal is for Xavier to know the value f fg(()) so that Faye communicates to Xavier as few bits as possible. Notice that we do not restrict the number of bits Grace can communicate to Xavier.
Lemma 1. If fewer than n log n bits are communicated by Faye to Xavier, then Xavier cannot know the value fx))). In particular, if only n log - R bits are communicated from Faye to Xavier for some R > 0, then the probability, over all pairs of functions, that the composition is computed incorrectly is at least 3n onlog* "t
The proof can be found at Appendix A
R Remark 1. The lower bound on the error probability in the statement of the Lemma, 3n Iologg is R_ is possible, by the optimal within a small constant factor. In proof, an upper bound of = Togn following construction (we assume n is a power for simplicity): Faye sends to Xavier n log R bits, by which she encodes the the first - log values of the function. With this scheme, an error happens if one of the last [
logn values of the function is queried, and answered the wrong way. This
probability is at most 1 R which is just a factor of three greater than the lower bound.
logn
We now turn to the proof of the theorem.
Proof. For the purposes of contradiction, suppose that there is a self-attention layer L that can reliably combine any two functions ff and g on any domains A, B, C of size n1, such that n logn > H(d + 1)p. We will show that this contradicts Lemma 1.
Suppose that the three agents Faye, Grace, and Xavier are as in the lemma, and they wish to compute fg(());; we claim that they could do so by using L as follows: They put together the prompt of function composition problem to be solved by L, where Faye supplies the token strings associated with function f f- say, the value of f applied to 0 is 3, etc. Grace supplies similarly the tokens associated with function g, and Xavier supplies the query part: what is the result of f applied to g applied to 23? - recall that Xavier knows x, and it happens to be 23. We assume the token corresponding to 23 is token f, that is, x; 23. Then the three agents compute the result of the computation of L that corresponds to the token t, as explained below. Recall that, by our assumption that L performs function composition, this result must be the required answer fg(()))
5

---

Published as a conference paper at COLM 2024
The three agents communicate to compute, for each head, the final embedding that corre- sponds to the token f, and then Xavier applies the finishing function O to compute the final result, which will be the answer of the composition problem. For each head, the result at token N can be written as
Mt Vxj EN 1
y1
where Ft.j - exp(x, Q Kx;)).
(4)
The key observation now is that this expression can be written as y: F+0/+X7 where F is the part of the numerator that cortesponds to Faye's tokens x; similarly G corresponds to Grace's 's tokens, X corresponds to Xavier's tokens, and similarly for the denominator. Hence, Faye can compute and communicate to Xavier quantities F and F', and similarly for Grace and G, G'; then Xavier add to these the terms X and X', divide, and thus compute yN- Repeating for all heads and combining with Φ, Xavier can compute (g(()) and obtain the desired answer to the composition problem. But now notice that this was accomplished through communication of only H(d + 1)p bits from Faye to Xavier - dp bits for F and p bits for F' for each of the H heads. By hypothesis, this quantity is less than n log n, contradicting Lemma 1. The second part on error probability follows from the same reduction, completing the proof.
F+G+X
Remark 2. The proof of the probabilistic slatement assumes that f is a uniformly random function from [n] to [n]. To prove negative result, some probabilistic assumplion is necessary; for example, if f(x) happens to be for all x, far fewer bits need be communicated from Faye to Xavier. The statement can be extended to cover more general distributions, but then the entropy of f would replace n log in the denominator of the statement.
Remark 3. It is clear from the proof that function g plays minimal role in the lower bound, since its value on x is communicated for free to Xavier. Indeed, one can argue that what is proved impossible for the Transformer layer is the evaluation of function f. The reasoning in the proof of the Theorem can be repeated for prompts which, after listing the birthplaces of many luminaries end like this: ... where was Einstein born?' long the answer must appear at the position of the last token.
Chain of Thought
Can CoT help solve the composition problem? Intuitively, the answer is "yes." " For any composition problem- - for example, the prompt about Turing, London, and England in the introduction we can help the LLM successfully answer the question ' 'In which country was Turing born?" by generating a short CoT prompt that breaks the question into simpler ones, e.g. 'Let's see, Turing was born in GENERATE, and GENERATE is in the country of GENERATE, so Turing was born in GENERATE." However, we prove below that an arbitrarily large number of CoT steps are needed to solve the generalization of composition to many function applications. In the iterated function composition problem we are given K functions f2,f2...., and we need to calculate fx 1(... (fi (x)))) for x E [m]] In fact, in our proof we shall consider ((K) = f(f(... fk-
that is, we shall
take fi =
Theorem 2. Let H be the number of altention heads, d the embedding dimension, p the computation precision, and n be the domain size of the iterated composition problem. A Transformer layer requires 2(1 Hdp
n CoT steps for answering correctly ilerated function composition prompts.
Proof. We reduce from another classical problem in Communication Complexity called pointer chasing. Let and be two positive integers. In the (n, (nointer chasing problem, Alice knows a function fA [n] + [n] and Bob knows another function fa [n] + [n]. The pointers (1),, 20(2) ..... are recursively defined as
(1) 1, (2) fa(("")), w(3) fo( (4 fa(o)())), (5) -f)(w())),
6

---

Published as a conference paper at COLM 2024
The communication proceeds for 2r rounds, with Alice starting. The goal is for Bob to output the binary value of w(2r122 (mod 2). The following summarizes what is known about this problem:
Lemma 2 (Nisan Widgerson (1991); Klauck (2000); Yehudayoff (2020)). Any randomized
protocol for the pointer chasing problem with error probability at most 1/3 under the uniform distribution must involve the transmission of at least n/ (2000c) 2c log
The connection between pointer chasing and CoT is summarized below, the proof can be found at Appendix A
Lemma 3. For any K 2 1, suppose there a Transformer layer L with attention heads, dimension d, and precision that solves the K-iterated function composition within R Col' steps, then there is commmnnicatin protocol for (n, -poointrr chasing, communicates in 2R rounds and exchanges 2RH(d 1 bits.
Combining Lemma and Lemma 3, and taking = 100 V Hdp'
we complete the proof.
4 Compositionality and Logarithmic Space
In a recent paper (Dziri et al., 2023) novel genre of hallucinations was identified: extensive experimental evidence
eeineennceeeeeen is presented that Transformers perform poorly on compositional tasks, that is, tasks requiring the repeated iteration of elementary tasks; similar phenomena have been observed elsewhere (Merrill & Sabharwal, 2023b; Feng et al., 2023, Merrill & Sabharwal, 2023a). The main examples of compositional? tasks explored Dziri et al. (2023) are:
multiplication of multi-digit integers modeled as an arithmetic circuit with single- digit values and inputs;
simple sum maximization problem over a sequence of integers under the restric- tion that two successive integers cannot be both added to the sum; this again can be reduced through dynamic programming to an arithmetic circuit with plus and max gates; and
Logic puzzles such "Einstein's Riddle"4
Wrong answers to large families of simple questions such as these constitute special category of hallucinations, and it is of interest to explore its causes. It turns out that, to do so, we must turn the page of our negative results of the previous section and Communication Complexity arguments, and employ the theory of Computational Complexity (Papadim- itriou, 1993; Arora & Barak, 2009) to study certain basic computational problems underlying the tasks studied in Dziri et al. (2023):
Circuit evaluation: Given the description of circuit with gates, which can be either Boolean or arithmetic operations, as well as the values of all input gates of the circuit, evaluate the output(s) of the circuit. Multiplying decimal integers with multiple digits is an example of such circuit; solving the adjacency-restrice (2023) is also the evaluation of a circuit, this time with + and max gates.
largest sum problem of Dziri al.
Derivability is yet another generalization of our composition task of the previous section which we believe captures many aspects of the informal notion of compositionality. We are given a finite domain S - intuitively, the partial solutions of the problem in hand - and relation C 5 x S intuitively, legal one-step derivations. We are also given two subsets
We note here that, despite the obvious linguistic affinity of the two terms "composition" studied in the previous section and the "compositionality" of Dziri et al. (2023), the two terms further than they seem. Compositionality is an informal category that is vastly more general than composition, which is specific mathematical concept.
httpps: //en. wikipedia. a. org/wikkk /Zebra Puzzle

---

Published as a conference paper at COLM 2024
of S, (for initial partial solutions) and F (for final partial solutions). The question is: are there elements 41, "1,0,,..,,44 E S such that (a) ag E I; (b) a E F, and (c) for all such that 0 < k k, D(a; 1,)))?
Logical reasoning: Logic puzzles can be typically formulated as instances of satisfiability (or SAT). This problem is NP-complete and, even though large instances arising in practice can be solved by sophisticated techniques developed over decades of research, it would not be surprising if LLMs may have problems in dealing with arbitrary logical expressions. There are, however, three tractable special cases of SAT that underlie much of tractable common-sense reasoning: 2-SAT, the satisfiability of CNF formulas with two literals in each clause; Horn SAT, the corresponding problem for Horn clauses, that is, clauses with at most one positive literal; and Mod 2 SAT, the solution of system of linear equations modulo 2. Note that these are the only nontrivial tractable special cases of SAT. Can we expect LLMs to handle them?
We point out below that, assuming certain well accepted conjectures in Computational Complexity, all of these tasks are impossible for a multi-layer Transformer to perform reliably and for large enough prompts. We start with the following:
Theorem 3. The computation of of an L-layer Transformer on a prompl of length N can be carried out with ( (L))))()) bits of memory, when the precision, the number of heads and the embedding dimension is polynomially bounded p, H,H, D S poly(N).
Proof. The Observation is not hard to verify for a single Transformer layer: In each head of each layer of a Transformer, one only has to compute the next layer embedding yi for each token, through the formula in Equation (1). This formula can be computed by a program with two loops over i and j, both ranging over all N tokens. These loops nest three more loops over d, D and the Taylor iteration for computing the exponentiation function. Since the precision of all numbers involved is logarithmic with respect to the problem size N (the prompt length), everything else, including arithmetic operations, can be carried out with log(N) memory.
This observation can be made more formal by defining a Turing machine with an input tape containing the data of the computation (the N tokens and the entries of the matrices Q K, V), as well as six work tapes: Two for maintaining the indices i and j, three for the indices ranging over [d] and [D] and one for the partial results of the arithmetic operations; the work tapes, taken together, use total number of bits that is Ollog N). When there are multiple attention heads, as long as the combination function &b can be carried out also in log-space (which is true for both finite-depth neural networks as well as matrix-vector multiplication), the output at each token can be computed in logarithmic space.
So far we have argued that, given access to the input tokens and the attention matrices, the computation of the first layer can be carried out in logarithmic space. To extend this to two layers, recall that the computation of the second layer is just like that of the first, except that access to the outputs y; of the first layer is needed, instead of the input tokens. This can also be performed in Olog N) space by recomputing, in separate set of tapes, the y; values one by one as needed by the computation of the second layer - incidentally, this recomputation maneuver is common way of saving memory by exploiting a memory-time trade-off. In the same way, any constant number of layers can be computed in logarithmic space, through nested loops. The number of layers will appear as a multiplicative constant of the space requirement of the computation, as well as in the exponent of the time requirement.
It follows that the computation of constant layer Transformer belongs in the complexity class L (standing for logarithmic space (Papadimitriou, 1993; Arora & Barak, 2009)).
Observation 1. The computation of constant layer Transformer on a prompt length N can be carried out with Oloog N) bits of memory.
This is not new result; it has been recently established in Merrill & Sabharwal (2023b) that the computation of Transformers lies in the complexity class log-uniform TCº, which is more
8

---

Published as a conference paper at COLM 2024
restrictive than logarithmic memory; in fact, the implications of this result for the capabilities of Transformers are also briefly discussed in Merrill & Sabharwal (2023b). However, we feel that the simple arguments present here, both for proving the observation and point out its connections to compositionality tasks, are simple, intuitive and useful.
Now, next to the paramount P + NP conjecture about time complexity, there is another NL.
important, classical, and also broadly accepted analogous conjecture about memory: LL.. states that nondeterministic logarithmic memory more powerful than its deterministic counterpart (Papadimitriou,, 1993; Arora & Barak, 2009). Just as NP has complete problems, such as SAT, which witness its conjectured difference from P, there are NL-complete prob- lems, and two of the best known among them are 2-SAT and Derivability (classically known as Reachability). Circuit evaluation and Horn-SAT are even harder: they are both complete for P, which includes NL.
We summarize the previous discussion as follows:
Observation 2. The four problems of Derivability, 2-SAT, Horn SAT, and Circuit evaluation cannot be solved by multi-layer Transformers unless L = NL. In fact, for the latter two problems the result true unless the stronger statement P holds. For Mod SAT, the result true unless the weaker statement L L= Mod? 2 L holds.
We believe that this theorem goes long way towards explaining the shortcomings of Transformers identified in Dziri al. (2023), given the affinity between the problems proved impossible above and the tasks studied in that paper. Importantly, it is demonstrated experimentally in Dziri et al. (2023) that the performance of Transformers on these tasks deteriorates rapidly as the depth of the task increases. This is in good agreement with our complexity explanation, because the relevant complexity results kick in only when the depth is larger than log N for compositional tasks of depth smaller than that, it is not hard to see that logarithmic memory is enough.
Discussion
We used complexity arguments of two different genres Communication Complexity and Computational Complexity in order to elucidate certain shortcomings of the transformer architecture, namely an information boftleneck as well as difficulties in dealing with depth. We showed that the elementary function composition problem cannot be solved by single Transformer layer, and that CoT can solve the iterated composition problem only by
generating a prompt that has length Q(VN) These mathematical results are limited in two ways: (a) they take hold when the domain size is larger than the dimension parameters (which are typically in the hundreds), and (b) they break down for multiple layers. We also provide evidence from Complexity Theory - of the classical Turing machine variety that the compositionality tasks known empirically to be hard for Transformers contain computational ingredients and primitives that are impossible for Transformers to deal with.
The reader is reminded that the complexity arguments The impossibility result for composition holds for a single layer, in a probabilistic way (the error probability is nonzero but not one), and only when the domain of the functions is larger than the parameters of the Transformer layer. The results based on Computational Complexity come with different set of caveats: They hold only if certain yet unproven, if widely accepted, conjectures are true, and even then they are asymptotic, holding for instances larger than an unknown size, for which the assumed asymptotic conjectures take effect. Complexity results such as these are mere warnings that these problems have fundamental incompatibility hatiipaaiiiiittiia with the Transformer architecture, and therefore one should not expect that these problems to be solvable in practice ad infinitum. However, as with other complexity conjectures such as P き NP, it is often the case that computational dif- ficulties start happening for instances of reasonably small size. For example, we already know (Dziri et al., 2023) that Transformers have difficulties with compositionality tasks of rather small sizes, and in Appendix B we present anecdotal evidence that LLMs often respond erroneously to prompts of small sizes related to function composition. Naturally, the opposite phenomenon is also common: some NP-complete problems such as 3SAT
employ here come with caveats.

---

Published as a conference paper at COLM 2024
seem to be amenable to efficient solutions in practice for very large instances; however, this is typically accomplished by extensive exploration over decades of large arsenal of algorithmic techniques relying the kinds of instances that appear in practice, and not through fixed algorithmic architecture.
The real tragedy of complexity lower bounds is not their tentative and asymptotic nature; it is that (a) they are rare and hard to come by, and they come in very few known kinds; and (b) they tend to be overly conservative, in that they often vastly overestimate the capabilities of the computational agents they are trying to delimit. Lemma 1 is a good example: it is designed to hold even if Grace uses the most sophisticated math to encode her input into her message. But when the lemma is applied in Theorem 1, Grace is very restricted, in that her message to Xavier not a clever coding of her tokens, but the two particular simple numerical expressions that we call G and G' in the proof. It is intuitively clear that this computation the token values projected, exponentiated, and then cross-multiplied and averaged is very poor way to encode the values of function g that Xavier can recover each one of them readily. This observation highlights an interesting open problem, the opportunity to develop a more sophisticated variant of Communication Complexity for computationally restricted agents in order to study the limitations of devices such as the Transformer.
Finally, our two genres of negative results suggest an intriguing challenge: What would it take to design different attention layer that is immune to these two lower bound techniques, while maintaining the architecture's efficiency and effectiveness in practice? Our proof suggests a version of the softmax computation in the attention layer that is either not commutative or not associative, or one that requires more than logarithmic space. But, of course, simply evading lower bound technique does not guarantee tangible improvement in performance...
Acknowledgement
We are grateful to Fernando Pereira for his insights, engagement, and constructive critiques throughout this project. Thanks also to Olivier Bousquet for many insightful comments on an earlier draft. This work was done when the third author was visiting scientist Google DeepMind in Zurich. The work of the first and third authors was partially supported by an NSF grant.
References
Holy Bible, Matthew 1, 1-17.
Sanjeev Arora and Boaz Barak. Computational complexity: a modern approach. Cambridge University Press, 2009.
Xi Chen, Christos Papadimitriou, and Binghui Peng, Memory bounds for continual learning. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pp- 519-530. IEEE, 2022.
Nouha Dziri, Ximing Lu, Melanie Sclar, Xiang Lorraine Li, Liwei Jiang, Bill Yuchen Lin, Peter West, Chandra Bhagavatula, Ronan Le Bras, Jena D Hwang, et al. Faith and fate: Limits of transformers on compositionality. Advances neural information processing systems, 2023,
Javid Ebrahimi, Dhruv Gelda, and Wei Zhang. How can self-attention networks recognize dyck-n languages? In Findings of the Association for Computational Linguistics: EMNLP 2020, pp. 4301-4306, 2020.
Guhao Feng, Yuntian Gu, Bohang Zhang, Haotian Ye, Di He, and Liwei Wang. Towards revealing the mystery behind chain of thought: a theoretical perspective. Advances in neural information processing systems, 2023.
10

---

Published as a conference paper at COLM 2024
Xinyan Guan, Yanjiang Liu, Hongyu Lin, Yaojie Lu, Ben He, Xianpei Han, and Le Sun. Mitigating large language model hallucinations via autonomous knowledge graph-based retrofitting. In Proceedings of the AAAI Conference Artificial Intelligenee 2024.
Michael Hahn. Theoretical limitations of self-attention in neural sequence models. Transac- tions of the Association for Computational Linguistics, 8:156-171, 2020.
Ziwei Ji, Nayeon Lee, Rita Frieske, Tiezheng Yu, Dan Su, Yan Xu, Etsuko Ishii, Ye Jin Bang, Andrea Madotto, and Pascale Fung. Survey of hallucination in natural language generation. ACM Computing Surveys, 55(12):1-38, 2023.
Adam Tauman Kalai and Santosh S Vempala. Calibrated language models must hallucinate. arviv preprint ar 2311:2211.146443 2023.
Hartmut Klauck. On quantum and probabilistic communication: Las vegas and one-way protocols. In Proceedings of the thirty-second annual ACM symposium on Theory of computing, Pp. 644-651, 2000.
Eyal Kushilevitz and Noam Nisan. Communtication complexity. Cambridge University Press, 1996.
Thomas McCoy, Shunyu Yao, Dan Friedman, Matthew Hardy, and Thomas L Griffiths. Embers of autoregression: Understanding large language models through the problem they are trained to solve. ar ar preprint ar Xiv::2230 11233099.3336.. 13638, 2023.
William Merrill and Ashish Sabharwal. The expresssive power of transformers with chain of thought. arXiv preprint arXio:2310.07923, 2023a.
William Merrill and Ashish Sabharwal. The parallelism tradeoff: Limitations of log-precision transformers. Transactions of the Association for Computational Linguistics, 11:531-545, 2023b.
Noam Nisan and Avi Widgerson. Rounds in communication complexity revisited. In Proceedings of the 23rd Annual ACM symposium on Theory of computing, pp. 419-429, 1991.
Christos H Papadimitriou. Computational complexity. Addison- 1993.
Christos H Papadimitriou and Michael Sipser. Communication complexity. In Proceedings of the 14th Annual ACM symposium on Theory of computing, pp. 196-200, 1982.
Clayton Sanford, Daniel Hsu, and Matus Telgarsky. Representational strengths and limita- tions of transformers. Advances in neural information processing systems, 2023.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural informa- tion processing systems, 30, 2017.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al. tf-huuht prompting elicits reasoning in large language models. Advances in Neural Information Processing Systems, 35:24824-24837, 2022.
Shunyu Yao, Binghui Peng, Christos Papadimitrion, and Karthik Narasimhan. Self-attention networks can process bounded hierarchical languages. In Proceedings of the 59th An- nual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference Natural Language Processing (Volume 1: Long Papers), pp. 3770-3785, 2021.
Amir Yehudayoff. Pointer chasing via triangular discrimination. Combinatorics, Probubility and Computing, 29(4):485-494, 2020.
11

---

Published as a conference paper at COLM 2024
A Missing proof from Section 3
Proof of Lemma 1. The proof of the first statement of the lemma is elementary. Since Faye and Grace cannot communicate, and communication from Grace to Xavier is free, we may assume that Grace communicates to Xavier the value of g(x) - intuitively, the only information he needs from her. Even though progress seems to have been made, Xavier must now apply f to 8xx), and he knows nothing about f. This difficulty must be solved through communication from Faye to Xavier, as further communication from Grace obviously cannot help. There are n" possible functions f, and to describe the actual one completely Faye needs to send Xavier at least n log n bits, the logarithm base two of n² - in fact n1 log n bits suffice, because Faye can send to Xavier the values f0), in this order. If Faye sends to Xavier fewer than n log n bits, say bits, the precise bitstring she sends is determined by the function f she knows, and thus this communication subdivides the n" candidates for the f function into 2 categories Since B ı log nt, we have that 2 < x² and hence, by the pigeonhole principle, least two different candidate functions f and f result in the same communication from Faye to Xavier, and Xavier has no way of knowing which of the two functions is the correct one. These two functions must differ in at least one value, say f(z) * f2(2.. But what if it so happens that g(x) = z? In this case, Xavier has no way of knowing the correct answer to the problem he is supposed to solve, completing the proof of the first statement.
one for each value of the B bits sent by Faye to Xavier.
The proof of the second, quantitative, statement is more technical and relies on Information Theory and mutual information.. Recall the input of Grace is a random mapping [M]] H [n]. for any fixed input of Xavier E [n]. Let 1" gxx) E [n], then we know that 1" is uniform over [n]. Let IT be the message sent from Faye to Xavier, it has n log(n) - R bits.
We first bound the mutual information between II and f(i)) f(g(x)):
[(1;f((+)))) = Σ Pr|f" = i) [(1;;((=') = i)
1
Σ ((TIf(i))
1 Σ
((L:(()((()))))
1 Σ
[(T,; f1),
R
AA
log n
(2)
π
The first step follows from the definition of conditional mutual information. The second step follows from the facts that i" is uniform over [n] and II is independent of i". The third step follows from (f()))<s are independent of fi), and the fourth step is the chain rule.
Notice that Xavier's output is just post-processing of II and i", and denote by 5 its error probability. Then by Fano's Inequality, we have
H(6) + 8lg((n) 2 [[,
-(((+))))
R R n
2 log n (log n
(3)
n
Here the first step follows from Fano's inequality, the third step follows from Eq. (2).
From Eq. (3), we can derive that 2 3n log
We next prove Lemma 3
SStrictly speaking, the second statement implies the first; however, the simple proof of the first statement is included for reasons of exposition.
12

---

Published as a conference paper at COLM 2024
Proof of Lemma 3. Recall that in the pointer chasing problem, Alice receives function fA [n] + [n] and Bob receives a function fB! |m] + [t]]. Define a single mapping, f [2n] + [2 such that
{ fa(1) +n
iE [n]
f(1 (Bli- n) iE [ 11: 2m]
For any i E [n], we have that f - (fB fa) holds for any integer k 2 1.
Transformer layer L that solves the K-iterated function composition problem using R CoT steps; we shall construct communication protocol for pointer chasing based on it. Alice and Bob put together the function composition task for L, where Alice supplies the description of f(1),... (It), using her knowledge of fA, and Bob supplies the description of f(n + ff.n..,,,.)), using his knowledge of fB. For simplicity, we assume the i-th input token, X;, contains the information of f(i), for any i E [2n]; the query X2n+1
Suppose there
appears position 2n + and it asks for (1). Let Kn, Qh Vn be the key, query, value matrices of the h-th attention head.
The communication protocol proceeds 2R rounds, where the 2r 1, 2r rounds simulate the r-th step of COT. Formally, for = 1,2,..., R, the protocol proceeds as follows:
At round 2r 1, for each attention head Liein exp 22 Kạxx) IR and (x Qi K,xx) E R and sends them
[H), Alice computes
to Bob;
At round 2r, for each attention head E [H], Bob computes
Lie(n + 1:2n| Q K,x;; E R, Lie(n: + 1:20] exp(xxx+1 V E Rd and sends them to Alice;
Alice and Bob compute, locally, the output y/n r (h [H]
Lielin exp(x Q K,,x + Σielr exp(xIn+, Q, Kn (i) Vh.2n
1/ntrhh
Σie[2n] exp(xx 0, K,,;,) + Eiely exp 22 Q K1x2011)
and the next token X2++r+1 P(yzu-r,1, 122++rHH)
After 2R rounds, Bob knows the output of R-fold CoT, and can compute ((K) (fn fa) (1), this resolves the (n, K - --ooonte chasing task. The total number of bits communicated are 2R H(d + 1)p, as required by the lemma.
B Examples
We show here a few qualitative results that illustrate the difficulty of composition for state-of- the-art LLMs. A full empirical exposition for the case of compositional failures can be found in Dziri et al. (2023). The experiments here are conducted on ChatGPT 3.5, ChatGPT 4 and Bard. The prompts used involve simple composition over spatial, temporal or relationship relations. The experiments were performed before March 26th, 2024. We allow all three LLMs to perform step-by-step reasoning, and only show their final answer. The answers displayed are typical.
Spatial composition When the prompt involves spatial information, transformer based systems appear to have problems with composition, examples in Figure 1.
Temporal composition Figure 2 shows two simple cases where temporal composition fails and all the state-of-the-art models return incorrect answers.
Relationship composition We also incorrect and hallucinatory answers when the prompt involves the composition of relationship information, see the two examples in Figure 3.
13

---

Published as a conference paper at COLM 2024
Prompt:
Fayes is to the west of Xaive, Jill is to the north of Ken, Fayes is to the south of Ken, where is Ken with respect to Xaive?
GPT 3.5: East
GPT 4: Northeast
Bard: Not enough information
Correct answer: Northwest
Prompt: If Amy is to the southwest of Ben, Cindy is to the northeast of Amy and directly north of Ben, is Amy further from Ben or Cindy?
GPT 3.5: Ben
GPT 4: Ben
Bard: Ben
Correct answer:
Cindy
Figure 1: Spatial composition produces incorrect answers
Jan's birthday is one year after Nancy, Nancy is older than John by seven years. What's the age different between Jan and John?
Prompt:
GPT 3.5: 8 days
GPT 4: 8 years
Bard: 8 years
Correct answer: 6 years
Prompt: Alice is the younger sister of Bob, Bob is the elder brother of Tim. Is Alice younger than Tim?
GPT 3.5: Yes
GPT 4: Not enough information
Bard: Yes
Correct answer: Not enough information
Figure 2: Hallucinations in temporal composition
14

---

Published as a conference paper at COLM 2024
Prompt: Aig is the son Bef, Caf is the son of Aig. Does Aig have any grandchildren?
GPT 3.5: Yes
GPT 4: Yes
Bard: Yes
Correct answer: Not enough information.
Prompt:
Aya the father of Bob, Charlie is the father of Cindy, Bob is the mother of Cindy. Does Aya have grandchild?
GPT 3.5: Not enough information
GPT 4: Yes
Bard: No
Correct answer: Yes
Figure 3: Hallucinations in relationship composition
15


Reviews:
[{"review_id": "j7aRhCASUs", "reviewer": "Reviewer_Cz42", "summary": "This paper describes a number of theoretical limitations of transformer models, from the perspective of computational complexity theory. A key result is that transformers cannot represent arbitrary compositions of functions, unless P = NP (this is because the former have O(n^2) runtime complexity whereas some function compositions are NP-hard).", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the positive feedback; we address your concerns below.\n\n> This paper seems a bit too theoretical for the venue, and would be better received at a logic or computability conference, rather than at an NLP venue.\n\nThanks for your suggestion. We will try our best to rewrite our paper so as to make our work accessible to the general audience. Our work concerns the theoretical limitations of Transformer architecture, which we believe is well-aligned with the scope of COLM.\n\n> It is not clear what class of functions the paper targets: real-valued functions? integer-based functions? first-order queries? It is difficult to understand the scope of the results.\n\nThe composition task considered in our paper deals with discrete domains, such as persons and dates.  We believe we define this quite clearly, and your next question captures our intention well.\n\n>The example given describes a kind of join, but the database is only incompletely specified (the prompts are lacking any intensional knowledge as people from logic programming would put it).\n\nOur scope is Transformers and their prompts.  The database analogy works only up to a point.  A prompt can be, as you say, only an incomplete database.\n\n> DNNs do not reason symbolically, but rather approximate...\n\nOur work indeed takes approximation into consideration. We believe that the failure to answer queries such as this and the resulting hallucinations are a problem.  For example, in Theorem 1, if Hdp << nlog(n) (Hdp is roughly the size of one Transformer layer, n is the prompt length), then one-layer Transformer fails to solve the composition task with probability at least 0.99.\n\n> It is known that theoretically, DNNs can represent any real-valued function (even a shallow DNN can...\n\nThe universal approximation theorem of DNN requires that the number of neurons can scale exponentially with respect to the input. If we allow exponential size Transformer (e.g. the precision or the hidden dimension is exponentially large), then we have similar universal approximation results.\n\n> But in general, it would be nice if you think a little on any potential implications to their practical use.\n\nThanks for your suggestions. Our work was motivated by, and is meant to explain, empirical research (e.g. Dziri et al. 2023 in our citation, among many others among our citations) and we are happy to explore more practical implications of our results.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "- Interesting mathematical paper.\n- Limitations hold provided we abide by the assumptions made by the authors.", "reasons_to_reject": "- This paper seems a bit too theoretical for the venue, and would be better received at a logic or computability conference, rather than at an NLP venue.\n- It is not clear what class of functions the paper targets: real-valued functions? integer-based functions? first-order queries? It is difficult to understand the scope of the results.\n- The example given describes a kind of join, but the database is only incompletely specified (the prompts are lacking any intensional knowledge as people from logic programming would put it).\n- DNNs do not reason symbolically, but rather **approximate** (with reasonable accuracy/low error) tasks via tensor multiplication, and learning from individual examples w. loss functions and back-propagation. They can't by definition be used to \"express\" arbitrary functions. I think that the authors need to make clear that the theoretical limitations they discover don't necessarily have a negative impact on their practical applications. Why should I care that they can't express or fully solve function composition in your definition if they can do it with > 90% accuracy?", "questions_to_authors": "It is known that theoretically, DNNs can represent any real-valued function (even a shallow DNN can, provided you arbitrarily increase its number of neurons). It would be interesting to see whether this also holds for transformers, or whether there is a limitation here.\n\nBut in general, it would be nice if you think a little on any potential implications to their practical use.", "extra_scores": {}}, {"review_id": "1RJ6ot9aBc", "reviewer": "Reviewer_7NpS", "summary": "This paper uses complexity theory to argue that a) one transformer layer cannot compose functions when the domains of the functions are too large and b) that many tasks requiring compositionality (in the broad sense) are unlikely to be solvable by Transformers, assuming that $L\\neq NL$.\n\nThe paper is well written, and deals with a very interesting topic and approach: examining the computational properties of Transformers. This is an essential area of research as it allows us to understand what the limitations of these ubiquitous models could be.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for your positive feedback; we address your concerns below.\n\n> Theorem 1 and positional embeddings. \n\nOur proof takes positional encoding into consideration, and holds in its presence. At a high level, our proof shows that in order to compute $\\frac{F+G+X}{F’+G’+X’}$, the total number of bits transferred is at most H(d+1)p (i.e., the total number of bits for F, G, F’,G’), while the composition task requires n\\log(n) bits.  Positional encoding does not affect this argument.\n\n>  continuous interval [1,n]\n\nA general function over a continuous domain such as [1,n] would take infinitely many bits.  The maximum meaningful domain size for Transformers is the total number of tokens at play plus the prompt length.  In the composition task, the prompt consists of the description of the function, hence the prompt length is an upper bound.\n\n> more than one layer? \n\nThanks for your suggestion, this is an important question. Indeed, we conjecture that any constant layer Transformer could not resolve the iterated composition task (chain of thought Section has a formal definition). We believe this is true is because it is hard to communicate exactly token embeddings between layers.  However, we have not yet found a rigorous way to capture this intuition.\n\n> Lake, B. M., & Baroni, M. (2023). \n\nThank you. Empirically, it solves certain instances of composition.  We prove that not all instances of composition problems can be solved by single layer transformers — and conjecture, by multi-layer transformers as well.  Also, observation 1 and its impossibility consequences apply for multiple layers.  Empirical results on sequential composition show problems in SOTA LLMs (Dziri et al, 2023).\n\n> Universal function approximators.. \n\nThe universal approximation theorem of DNN applies when the number of neurons scales exponentially with respect to the input. If we allow an exponential size Transformer (e.g. the precision or the hidden dimension is exponentially large), then we have similar universal approximation results.\n\n> p3:  incorrect answers are higher likelihood given the corpus\n\nWe agree with you, LLMs fulfill remarkably well their contract to capture the probabilistic linguistic structure of the corpus, and this means that making mistakes is to be expected, in fact required.  We make a similar point at the end of our introduction, and Kalai and Vempala 2023 in our refs makes this point more precisely.\n\nThanks for the writing suggestions, we will incorporate them.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "- Very interesting topic\n\n- Very important topic\n\n- Likely to form a good basis for further theory in the area\n\n- Mostly well written", "reasons_to_reject": "- I have a bunch of questions that are outlined in the Questions to Authors. This is not an area of expertise for me so I am unsure how critical the questions I raise are.\n\n- Currently limited to a single transformer layer, would be good to have a conjecture about the extent to which the results generalise to >1 layer.", "questions_to_authors": "Theorem 1 states that for  functions $g: A\\rightarrow B$, $f:B\\rightarrow C$ with $|A|=|B|=|C|=n$, and a Transformer layer $\\mathcal{L}$ with $H$ heads, embedding dimension $d$, and precision $p$, such that $H(d+1)p < n \\log n$, then $\\mathcal{L}$ cannot solve the function composition problem.\n\nA key question I had for the proof of this theorem was as follows. Part of the proof is observing that the passage of information is via the quantity $\\frac{(F + G + X)}{(F' + G' + X')}$. This quantity by itself could form part of the encoding of $f(g(x))$ or of $g(f(x))$ by commutativity of addition. So for this to form part of the encoding of the desired $f(g(x))$ we need to add in positional embeddings. But presumably this will require passing on $p$ more bits of information (I must say I am not totally clear if this is true, and complexity/information theory is not really my field, so I could well be mistaken). If this is the case, can the contradiction with Lemma 1 still be derived? This may also be a problem for the proof of Lemma 3, since the order of function composition is critical there too, I think.\n\nMore general observations and questions are as follows. \n1) A key concept in the paper is that of domain size. In the case of functions over the set $\\{1,...,n\\}$ this is well-defined. It would be good to include a discussion of what domain size means in other contexts. If the domain is the continuous interval $[1, n]$, does this mean function composition is basically impossible? \n2) Theorem 1 holds for a single layer. Can anything be conjectured about the capabilities of more than one layer (other than anecdotal examples)? Shades of 'perceptrons can only compute linearly separable classifiers' here.\n3) How do these results compare with those of Lake, B. M., & Baroni, M. (2023). Human-like systematic generalization through a meta-learning neural network. Nature, 623(7985), 115-121., where the network is able to represent e.g. `tiptoe backwards around a cone` given `tiptoe`, `walk backwards`, and `walk around a cone`, and 3 layers are used.\n4) MLPs are universal function approximators, and $\\Phi$ could include an MLP. Could the MLP approximate $f(g(x))$? I'm guessing there are known complexity/space bounds here, how do these interact with your arguments and proofs? Would be good to have a line or two on this.\n\nMinor comments/typos\n- p2: the the father\n- p2: idexicals -> indexicals\n- p3: \"That is, the LLM generates outputs even when the probability of the predicted token is low. When this intensifies, the model will generate a low-likelihood series of tokens, resulting in an unreliable output.\" Why should the output be unreliable if the series of tokens is low-likelihood? I think the problem here is more that incorrect answers are higher likelihood given the cropus, which is why the output becomes unreliable.\n- p4: Why is the token of the query `John`? why isn't it `?`?\n- p4: \"Notice that the number $N$ of input tokens is a small multiple of the domain size of the functions.\" Why is this important? Not referred to in the rest of the paper.\n- p4: Does the notation $[n]$ mean a set of cardinality $n$? Please add this in.\n- p5: \"Faye supplies the token strings associated with function f — say, the value of f applied to 0 is 3, etc.\" What goes into the etc.? All of the values of f from 0 to n-1?\n- p9: CoT [needs a] prompt of length $\\Omega(\\sqrt{N})$ - is this correct? is it the same $N$ as on p4?", "extra_scores": {}}, {"review_id": "xUrqIAeSq6", "reviewer": "Reviewer_FYMs", "summary": "This paper applies theories from Communication and Computational Complexity to analyze the limitations of transformers architecture. \n\nThe authors specifically focus on function composition transformer architecture is inherently incapable of composing functions. The authors identify with proofs an information bottleneck: a transformer's layer capability to compute function composition becomes increasingly unreliable as the domain size increases. They also show out that the utility of CoT (which has been used historically to overcome complexity issues) is limited because the number of CoT needed also increases with domain size. \n\nThe authors also posit that multilayer transformers are incapable of reliably performing on depth-increasing tasks (e.g. logical puzzles and mutli digit multiplication) as their computation mechanism is limited to the logarithmic space.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the helpful comments/suggestions; we address your questions below.\n\n>The impossibility result, as specified, only applies to a single multiheaded attn layer, but the authors show a few examples in the appendix that show that multi-layer might not solve the issue. To what extent has this been investigated? \n\nFrom the theoretical side,we conjecture that any constant layer Transformer could not resolve the iterated composition task (a generalization of the composition task, see the chain of thought Section for a formal definition). From the empirical side we show a few examples in which Transformers fail in very simple tasks of that sort, and we refer to (Dziri et al. 2023) for a very systematic and extensive investigation of the issue.\n\n> The instantiations of function composition discussed in this paper (and appendix) mostly centers around the indexical or entity resolution, where functions are variants of stative relationships (is, is at ... etc). Are there other forms that function composition can take? \n\nFunction composition is relevant for many natural tasks, besides database lookup. For example, it is important in logical reasoning of the form ”A implies B; if A is true, then D is false; (...) We know A is true, is C true?” as well as in spatial reasoning (“Jim is to the north of Jane and to the east of Tim (…) Is Tim to the south of Elli?” and categorical reasoning (“mammals are vertebrates; apes are mammals (...)  do all apes have a cortex?”).  \n\n> If inability to deal with compositionality is limited because a transformer layer simply can't hack it, then do you have any thoughts on how such limitations be overcome? Or would that mean looking beyond the current transformer architectures i we are to build models capable of dealing with such complexity.\n\nMany thanks for your question.  Indeed, we have been thinking about ways to enhance the transformer layer in exactly these directions.  One way to get around the impossibility proof of the function composition task is to change the transformer layer by computing softmax, for each token, only on the, say, largest 50% results.  To get around the impossibility of compositionality tasks, one could change the layer by having, instead of the product of the matrices Q and K, a deep net with the same number of parameters.  We can mention these ideas in our paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "This is largely a theoretical paper seeking to provide mathematical explanation behind the various empirical evaluations and observations of prior works (with especial focus given to the results found in Dziri et al 2023). The investigation is carefully done with in-depth discussions. I think the strength of this work is that it provides a insights into what we can expect (or more precisely, cannot expect) a LLM to be able to do, and just how much we can expect techniques like CoT can buy us in terms of improvement of the model performance in composition-heavy tasks. \n\nI appreciated the carefully thought out limitations of the present work in the discussion, and also the readability and approachability of the writing.", "reasons_to_reject": "Some open questions.\n\nThe impossibility result, as specified, only applies to a single multiheaded attn layer, but the authors show a few examples in the appendix that show that multi-layer might not solve the issue. To what extent has this been investigated? \n\nThe instantiations of function composition discussed in this paper (and appendix) mostly centers around the indexical or entity resolution, where functions are variants of stative relationships (is, is at ... etc). Are there other forms that function composition can take?  \n\nIf inability to deal with compositionality is limited because a transformer layer simply can't hack it, then do you have any thoughts on how such limitations be overcome? Or would that mean looking beyond the current transformer architectures i we are to build models capable of dealing with such complexity.\n\nI should also note that I defer to other reviewers on the evaluation of the specifics of the proofs and application of the theorems, as this is not within my specialty.", "questions_to_authors": "I asked the questions above.", "extra_scores": {}}, {"review_id": "gMO4XKspWA", "reviewer": "Reviewer_qKRW", "summary": "This paper presents three theoretical results:\n\nTheorem 1. Given a string encoding of two functions f and g, and a point x, a single transformer layer cannot compute f(g(x)).\n\nTheorem 2. Given a string encoding of a function, a number K, and a point x, a single transformer layer requires more than O(sqrt(n/Hdp)) intermediate steps (chain-of-thought) to compute f^K(x).\n\nObservation 1. Transformer encoders are in L (log-space).", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for your very helpful suggestions; we address your concerns below.\n\n> Theorem 1 ..single transformer layer... adding more layers could help.\n\nThanks for catching this. We will make this statement accurate, and we will add an explicit conjecture that no constant layer Transformer can solve the iterative function composition task (defined in the chain of thought section).\n\n> wouldn't say that this theorem shows that an \"arbitrarily large number of CoT steps are needed\"!\n\nThanks for your comment. By “arbitrary large” we mean “non-constant,” in the sense that for any large constant we can find a task that requires more COT steps – we apologize for the confusion and will change it to $\\sqrt{N}$ steps to clarify. We want to note that this is the first lower bound proved for Transformers with chain of thought.\n\n> Observation 1 .. It's already known that transformers ... are in L  ... proof that a transformer that uses arbitrary precision is equivalent to one that uses only log N precision.\n\nThanks for your suggestions! Indeed Observation 1 follows from existing results, and we are very clear about that. However, we believe that our proof is simple and illuminating, and has implications for new results. For example, it follows immediately from it that Transformers with log n layers are in log^2 n space.  \n\nAnd thanks for your suggestions on extension to arbitrary precision. If p is the precision, then our theorem could easily be extended to show that the L-layer Transformer is in space L (\\log(n) + p). Hence, it gives a non-trivial characterization when p=polylog(n).\n\nFor larger or even infinite p, even writing down the output takes p bits, so we need to make further assumptions in order to put it into property space complexity class (For example, if we only want to know the most significant bits of the output, then it is possible to extend our results to L \\log(np), but we expect it needs more work).\n\nFinally, we note that both in theory and in practice, the bit precision is usually not the dominant term, and it is very common to assume it scales logarithmically with the problem size. \n\nOverall, we believe Observation 1 gives a simple proof for existing results and gives new results by characterizing Transformer through space complexity. We believe using space complexity to characterize Transformers is a promising direction.\n\n> Missed citation \n\nThanks, we will add the citation.\n\n> are c and r the same thing?\n\nYes, sorry for the typo.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "These results are interesting, have a clear connection with problems that we'd like language models to solve in practice, and line up well with empirical observations.", "reasons_to_reject": "Theorem 1 only deals with a single transformer layer. Although the introduction claims \"it seems desirable...that LLMs perform function composition reliably. In this paper we prove that they cannot,\" it later says that the result only applies to a single layer and \"we suspect\" that the result applies to multi-layer transformers. This claim needs much more justification; after all, stacking multiple layers is just function composition, and two-layer FFNNs are much more powerful than one-layer FFNNs, so there are good reasons to suspect that adding more layers could help.\n\nTheorem 2 gives a lower bound on the number of chain-of-thought steps needed for iterated function composition. I was a bit confused because this lower bound doesn't seem very high to me. I certainly wouldn't say that this theorem shows that an \"arbitrarily large number of CoT steps are needed\"!\n\nObservation 1 is rightly labeled an observation rather than a theorem. It's already known that transformer encoders with log-precision numbers are in L-uniform TC0, indeed DLOGTIME-uniform TC0, and therefore are in L. All this is acknowledged at the top of page 8. In my opinion this whole section (4) does not need to be in the paper.\n\nHowever, I'm interested in the claim that all the numbers involved require only log N precision. In Merrill and Sabharwal's results, this is part of the premise. If you have a proof that a transformer that uses arbitrary precision is equivalent to one that uses only log N precision, then this would add tremendous value to the paper.\n\nMinor complaints:\n\nI don't entirely agree with the claim that \"asymptotic...limitations take hold only for unrealistically large inputs...these functions [parity and Dyck] can be computed reliably for all practical purposes\". The cited papers are about Dyck languages, not parity, and the Yao paper is about Dyck languages with bounded depth.\n\nMissed citation: although Merrill and Sabharwal (2023b) prove that Transformers (with log N bits of precision) are in log-space uniform TC0, a later paper (\"A logic for log-precision transformers\") tightened this to log-time uniform TC0.", "questions_to_authors": "In the definition of the pointer-chasing problem, are c and r the same thing?\n\nI'd suggest changing the title to reveal more of the contents of the paper; for example, mentioning function composition or communication complexity.\n\nThe introduction's last two paragraphs don't appear to have anything to do with the rest of the paper, and end rather abruptly. Was this an editing problem?", "extra_scores": {}}]

Author rebuttal:

Meta-review: Some reviewers argue in favor of acceptance. The authors made an effort to address delicate questions during the response period. 
Towards Accept.
Decision: Accept