On Limitations of the Transformer Architecture

Many thanks for your very helpful suggestions; we address your concerns below.

Theorem 1 ..single transformer layer... adding more layers could help.

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

wouldn't say that this theorem shows that an "arbitrarily large number of CoT steps are needed"!

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

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.

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

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

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

Finally, 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.

Overall, 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.

Missed citation

Thanks, we will add the citation.

are c and r the same thing?

Yes, sorry for the typo.

Many thanks for your positive feedback; we address your concerns below.

Theorem 1 and positional embeddings.

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

continuous interval [1,n]

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

more than one layer?

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

Lake, B. M., & Baroni, M. (2023).

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

Universal function approximators..

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

p3: incorrect answers are higher likelihood given the corpus

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

Thanks for the writing suggestions, we will incorporate them.

We thank the reviewer for the helpful comments/suggestions; we address your questions below.

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?

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

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?

Function 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?”).

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.

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

Thanks for the positive feedback; we address your concerns below.

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.

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

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

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

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

DNNs do not reason symbolically, but rather approximate...

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

It is known that theoretically, DNNs can represent any real-valued function (even a shallow DNN can...

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

But in general, it would be nice if you think a little on any potential implications to their practical use.

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