On Limitations of the Transformer Architecture

Summary

This paper presents three theoretical results: Theorem 1. Given a string encoding of two functions f and g, and a point x, a single transformer layer cannot compute f(g(x)). Theorem 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). Observation 1. Transformer encoders are in L (log-space).

Rating

4

Confidence

4

Ethics flag

1

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. Theorem 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"! Observation 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. However, 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. Minor complaints: I 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. Missed 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? I'd suggest changing the title to reveal more of the contents of the paper; for example, mentioning function composition or communication complexity. The 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?

Summary

This paper applies theories from Communication and Computational Complexity to analyze the limitations of transformers architecture. The 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. The 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.

Rating

6

Confidence

3

Ethics flag

1

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. I 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. 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? 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? 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. I 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.

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$. The 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.

Rating

6

Confidence

2

Ethics flag

1

Reasons to accept

- Very interesting topic - Very important topic - Likely to form a good basis for further theory in the area - 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. - 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. A 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. More general observations and questions are as follows. 1) 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? 2) 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. 3) 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. 4) 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. Minor comments/typos - p2: the the father - p2: idexicals -> indexicals - 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. - p4: Why is the token of the query `John`? why isn't it `?`? - 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. - p4: Does the notation $[n]$ mean a set of cardinality $n$? Please add this in. - 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? - p9: CoT [needs a] prompt of length $\Omega(\sqrt{N})$ - is this correct? is it the same $N$ as on p4?

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).

Rating

7

Confidence

2

Ethics flag

1

Reasons to accept

- Interesting mathematical paper. - 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. - 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. - 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). - 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. But in general, it would be nice if you think a little on any potential implications to their practical use.