Theoretical limitations of multi-layer Transformer(arxiv.org)

    This paper proves the first unconditional limitations of multi-layer decoder-only transformers, which are the dominant architecture used in large language models (LLMs) today. The key takeaways are:
    
    1. Any constant-depth L-layer decoder-only transformer requires a polynomial model dimension of at least n^(2^(-4L)) to perform sequential composition of L functions over an input of n tokens. This is an exponentially larger model size than what an (L+1)-layer transformer needs.
    
    2. There are certain tasks, like L-step sequential function composition, that are exponentially harder for L-layer transformers compared to (L+1)-layer transformers. This proves a depth-width tradeoff.
    
    3. The same sequential composition tasks used above can be solved by an exponentially shallower and smaller encoder-only transformer compared to decoder-only transformers. This unconditionally separates the computational power of encoders vs decoders.
    
    4. Sequential composition tasks that are hard for L-layer transformers become exponentially easier when allowing L steps of "chain of thought" reasoning. This provides the first provable benefit of chain of thought prompting.
    
    The results rely on a new theoretical model called the "autoregressive communication model" that abstracts the key aspects of decoder-only attention. The lower bounds are proved by analyzing the ability of this model to perform multi-step function composition.
    
    The proofs appear technically sound, relying on information-theoretic arguments without unproven assumptions. The separation between encoders and decoders was previously only known assuming unproven complexity conjectures.
    
    The key limitation is that the theoretical model makes some simplifications compared to practical transformers. But overall, this looks like an important foundational result that rigorously demonstrates limitations of the currently dominant LLM architecture and provides theoretical motivation for alternative approaches like encoder-decoder models, chain of thought, and deep but narrow models. The unconditional nature of the results makes them more definitive than prior work relying on complexity assumptions.
        The sequential function composition problem that the paper shows to be hard for constant-depth decoder-only transformers essentially requires iteratively applying a sequence of functions, where each function takes as input the output of the previous function application. 
    
    In terms of practical everyday reasoning tasks, this could potentially capture things like:
    
    1. Multi-step arithmetic: A task like "What is 5 plus 3, minus 2, times 4, divided by 8" requires sequentially applying the arithmetic operations. Each operation takes as input the result of the previous one.
    
    2. Chained logical inference: Deriving a conclusion from a sequence of logical premises, where each inference step builds on the previous conclusions. For example: "If A then B. If B then C. If C then D. A is true. Therefore D is true."  Reaching the final conclusion requires iteratively applying the logical rules.
    
    3. Complex query decomposition: Answering a complex query that requires multiple steps of information retrieval and computation. Like "How many countries have a population larger than Russia's GDP per capita?" This might involve retrieving Russia's GDP, dividing by population to get per capita, then comparing each country's population to this value and counting matches.
    
    4. Multi-hop reasoning over knowledge: Drawing inferences that require combining multiple facts from a knowledge base. E.g. "The tallest building in the city with the largest population in John's home state" would require finding John's state, its largest city, and the tallest building there, using separate knowledge lookups.
    
    5. Sequential decision making: Planning tasks that require a sequence of decisions, where each decision depends on the state resulting from previous decisions.
    
    The paper suggests that constant-depth transformers, the current architecture of choice for LLMs, may struggle with tasks like these that require longer chains of computation, despite their strong performance on many benchmarks. Exploring alternative architectures like deeper models or encoder-decoder structures may help address these limitations.
    
    Of course, the actual difficulty of any given task for an LLM depends on many factors beyond just the abstract computational structure. But this result provides a valuable lens for understanding the types of everyday reasoning that may be challenging for the current paradigm and motivates further research into more compositional and reasoning-oriented architectures.