Limitations of multi-layer transformer


"For any constant L, we prove that any L-layer decoder-only transformer needs a polynomial model dimension (nΩ(1)) to perform sequential composition of L functions over an input of n tokens.

As a consequence, our results give: 
  1. The first depth-width trade-off for multi-layer transformers, exhibiting that the L-step composition task is exponentially harder for L-layer models compared to (L+1)-layer ones; 
  2. An unconditional separation between encoder and decoder, exhibiting a hard task for decoders that can be solved by an exponentially shallower and smaller encoder; 
  3. A provable advantage of chain-of-thought, exhibiting a task that becomes exponentially easier with chain-of-thought.
"On the technical side, we propose the multi-party autoregressive communication model that captures the computation of a decoder-only Transformer. 

"We also introduce a new proof technique that finds a certain indistinguishable decomposition of all possible inputs iteratively for proving lower bounds in this model."


Comments

Post a Comment

Empathy recommended

Popular posts from this blog

Hamza Chaudhry

"Although a nuclear confrontation based on fake intelligence may seem unlikely, the stakes during crises are high and timelines are short, creating situations where fake data could well tilt the balance toward nuclear war. "The evolution of nuclear systems has led to further ambiguity in crises and shorter timeframes for verifying intelligence. An intercontinental ballistic missile from Russia could reach the U.S. within 25 minutes. A submarine-launched ballistic missile could arrive even sooner.  "Many modern missiles carry ambiguous payloads, making it unclear whether they are nuclear-tipped. AI tools for verifying the authenticity of content are not sufficiently reliable, making this ambiguity difficult to resolve in a short window. "The likeliest nuclear hotspots are also the arenas involving actors with low levels of trust on both sides — be that the U.S. and the Chinese Communist Party or Russia, or India and Pakistan. Even if communication is established in a...
Read more

When their AI chums have Bob's data

Image
1 "How do we discuss Bob's prognosis with him?"   Ask Doctor Agent! "How to discuss our auction of Bob's home with him?"   Ask Realtor Agent! "How do we obtain a confession from Bob?"  Ask District Attorney Agent! 2 But why would Bob's data reside within AI agents? We have a fascination with androids. One part of this fascination includes the idea of ' self-repair .'  Many of us long for the ability to diagnose and cure ourselves without the need to expose ourselves to other humans, like doctors and nurses, for example.  We'd much prefer tiny sensors throughout our bodies that could signal to us when/how we might need to alter our metabolisms.  Yet who —besides a tech bro —can make the sensors and/or digital assistant? Who can program the assistant, much less afford the things to begin with?  No worries. Firms around the world are already testing various solutions! Soon all one will have to do is surrender oneself and all will be...
Read more

Swarm 🦹‍♂️

"Knowledge discovery from data typically includes solving some type of an optimization problem that can be efficiently addressed using algorithms belonging to the class of evolutionary and bio-inspired computation .  "In this chapter, we give an overview of the various kinds of evolutionary algorithms, such as genetic algorithms, evolutionary strategy, evolutionary and genetic programming, differential evolution, and coevolutionary algorithms, as well as several other bio-inspired approaches, like swarm intelligence and artificial immune systems.  "After elaborating on the methodology, we provide numerous examples of applications in astronomy and geoscience and show how these algorithms can be applied within a distributed environment, by making use of parallel computing, which is essential when dealing with Big Data."
Read more