Iirc, there's a big difference between the computational complexity of what a transformer can solve and what it can solve in practice; what it can solve in practice tends to come from things like singular learning theory (which describes the forms of generalizations that a given ML algorithm can make), but I think (iirc) that transformers can compute a pretty broad class of O(N^2) functions?
replyFor the umpteenth time a transformer is an arbitrary turning machine due to the fact that it has a theoretically limitless tape (the context).
replyA single transformer step is simply O(1) (for a particular parameter size), but it applied a potentially infinite number of times.
Thus while a single transformer cannot solve any problem, a transformer system applied in the normal way can solve any computable problem.
The context acting as a "theoretically limitless tape" while simultaneously the step being O(1) are contradictory. You cannot have it both.
replyThe context can change each time. To implement a UTM only requires 2 states and 3 symbols or the reverse.
replySo if you use the context not as a tape in itself, but as an io channel to read/write an infinite tape, the context for any given step can remain fixed in size, and so the step itself can be O(1).
Any basic lookup table is turing complete if you bolt an external infinite tape and read/write head onto it. But then that’s moving the goal post since the context wouldn’t be the “limitless tape” and it’s not a transformer “in the normal way” because turing completeness would be coming from external io and not from auto regressive self attention. Different topic.
replyIt's not contradictory at all. The dfa at each step of the turing machine model is also o(1).
replyOf course it is. You’re conflating a turing machine with a transformer. Transformers don’t have a local read/write head. The [self] attention is over the whole context, which makes each step O(N) at best (with caching) and O(N^2) w/o.
reply