points by GuB-42 2 days ago | 0 comments
It depends on what you say is O(1). A theoretical Turing machine has an infinite tape that can be accessed in O(1), but in real life, it would require a machine of an infinite size.
Same idea for that transformer, it needs an infinite context, and it is an infinitely big machine, but with that level of abstraction, it processes a token in O(1).
In practice, there is no such thing as O(1) on arbitrarily sized data, there is no such thing as infinity either, it is just an abstraction.
It’s not the same for transformers, especially not with the theoretical infinite context. It simply doesn’t process tokens in O(1) in your given setup.
In practice, with frontier LLMs, it’s of course more complicated, and also they don’t reveal how they do lookups, but still the theoretical limit applies regardless.
Do you mind elaborating or perhaps providing some reference as to why you think transformers should be similar to a Turing machine on this specific criteria?