2 ms·

> architectures like RWKV, Mamba, and various others, which incur cost that is linear in context length, O(N) These are actually O(N*M) where M is independent

by jxy 3y ago

> architectures like RWKV, Mamba, and various others, which incur cost that is linear in context length, O(N) These are actually O(N*M) where M is independent of inference time context length, but it controls the actual amount of information that gets retained during inference. Ignoring that factor of M is misleading.

hansvm 3y ago
All models are wrong. Some are useful. The "linear" models I'm aware of have a cost of O(N * M), where M is the amount of information retained _per token_ (with some exceptions that store less state but still have intermediate computations for some M about the same size as the others, and with less state you necessarily have forgetting issues and can't scale to unbounded sequences anyway). Contrast that with a transformer, which has a cost of O(N^2 * M), where M is still the amount of information retained _per token_. Dividing the two you still find a multiplicative speedup of O(N). For accurate cost estimates or any number of other use cases, yes, the M is critical. When comparing architectures (or when talking about a single architecture with the current implicit conversation happening that whatever you say is meant to be taken with respect to other architectures) it's conventional to note that the M term always appears as a multiplicative factor beyond the rest of the costs. You drop it because it's obviously there but it's just visual noise that doesn't help you understand where the models sit with respect to each other. You only include it if it's relevant, like if you found a way to get similar performance with a smaller M. It's kind of like how we always drop the log term on a hash table (equivalently, we work in the "word RAM" model of computation), but bignum algorithm papers carefully consider every log(log(log(N))) that crops up. It's relevant in some contexts and not in others. You can't ever include enough context to fully represent your thoughts to another person, so you truncate somewhere, hopefully capturing the essence of what matters.

by jxy 3y ago

hansvm 3y ago

All models are wrong. Some are useful. The "linear" models I'm aware of have a cost of O(N * M), where M is the amount of information retained _per token_ (with some exceptions that store less state but still have intermediate computations for some M about the same size as the others, and with less state you necessarily have forgetting issues and can't scale to unbounded sequences anyway). Contrast that with a transformer, which has a cost of O(N^2 * M), where M is still the amount of information retained _per token_. Dividing the two you still find a multiplicative speedup of O(N). For accurate cost estimates or any number of other use cases, yes, the M is critical. When comparing architectures (or when talking about a single architecture with the current implicit conversation happening that whatever you say is meant to be taken with respect to other architectures) it's conventional to note that the M term always appears as a multiplicative factor beyond the rest of the costs. You drop it because it's obviously there but it's just visual noise that doesn't help you understand where the models sit with respect to each other. You only include it if it's relevant, like if you found a way to get similar performance with a smaller M. It's kind of like how we always drop the log term on a hash table (equivalently, we work in the "word RAM" model of computation), but bignum algorithm papers carefully consider every log(log(log(N))) that crops up. It's relevant in some contexts and not in others. You can't ever include enough context to fully represent your thoughts to another person, so you truncate somewhere, hopefully capturing the essence of what matters.