i see in the linked post they mention O(n) not O(1). O(1) would basically be impossible and instant. Something like no compute required, constant results...
The name subquadratic is actually good and makes sense to me. Because today's models are usually O(n^2) or worse. Anything equals or less than O(n^1) is basically sub-quadratic.
Meanwhile O(log n) would be logarithmic as the log name indicates. But we have a long way to go there. Maybe with double tokenizer plus extensive caching it may be possible...
What I mean here is tokenizing the user input; then capturing intent; caching intent -> response. So that next time once you get the intent, you don't need to do full transformer inference compute. This can be logarithmic complexity in terms of time complexity.
Comments
i see in the linked post they mention O(n) not O(1). O(1) would basically be impossible and instant. Something like no compute required, constant results...
The name subquadratic is actually good and makes sense to me. Because today's models are usually O(n^2) or worse. Anything equals or less than O(n^1) is basically sub-quadratic.
Meanwhile O(log n) would be logarithmic as the log name indicates. But we have a long way to go there. Maybe with double tokenizer plus extensive caching it may be possible...
What I mean here is tokenizing the user input; then capturing intent; caching intent -> response. So that next time once you get the intent, you don't need to do full transformer inference compute. This can be logarithmic complexity in terms of time complexity.