6 ms·

I would add to the list a few questions about the evolution of cost dynamics going forward, given the advent of new sequence modeling architectures. As we all

by cs702 3y ago

I would add to the list a few questions about the evolution of cost dynamics going forward, given the advent of new sequence modeling architectures. As we all know, Transformers are very expensive to train and run because their compute cost is quadratic in context length: O(N²). If newer model architectures like RWKV, Mamba, and various others, which incur cost that is linear in context length, O(N), prove as successful as Transformers, the demand for compute for a query of N tokens would decline from O(N²) to O(N). For a sequence with N = 100,000 tokens, it would mean cost dropping by a factor of 100,000×. That's not peanuts! The implications for all market participants would be significant.

nyrikki 3y ago
In the general case that would be the same as hierarchy collapse of PH, which would prove P=NP
- cs702 3y ago
  Well, it would depend on how many tokens from the vocabulary are required, in the worst case, to solve NP problems. Think of the tokens as symbols, and of the vocabulary as a finite alphabet of symbols, in a formal system. In other words, no, it would NOT necessarily prove P = NP.
  - nyrikki 3y ago
    The Singleton case is NP-complete If you consider NP second-order existential logic, meaning that given x, you will get a y, While there may be many true values that aren't y, it will help Attention, which requires feed forward networks, which approximate a DAG, you can think of attention as run time reweighing to change what y value is returned. PH is a query expressible in second-order logic, which would allow for 'for any' at the second level. The reduction in the general case to just logarithmic time: O(n log n), would cause issue, there will not be any movement from quadratic time to linear time without massive new discoveries. It is inherent from the restrictions of ANNs having binary output. Considering FP and FNP vs P and NP may help as they make that property clearer than the concept of second-order existential logic does in some contexts.
    - cs702 3y ago
      Thank you. Right now, my puny little brain is searching through what I would describe as "those distant and slightly vague memories" that make up my poor man's knowledge of computational complexity theory. > Attention, which requires feed forward networks, which approximate a DAG, you can think of attention as run time reweighing to change what y value is returned. Isn't that's true for linear RNN mechanisms too? Note that linear RNNs like RWKV and Mamba are linear in the number of tokens in the sequence, but not in the number of features per token.
      - nyrikki 3y ago
        You don't typically get to the Sigma_2^P level unless are a sadist or forced. Attention works differently in RNNs, and it may be able to find different tractable forms, and may solve different problems, but increasing generalization is a reduction of compression in the general case. A many to one reduction to a recursively enumerable set gets you to finite time, a reduction to NP gets you to quadratic time. Obviously those are upper limits and specific instances or classes of instances may do better. P being inside NP is a good example. All ANNs are binary output, which helps with that. SNN or spikey neutral networks, which better model cortical neurons and have continuous output have problems with being un-computable without much complexity as an example. That can be viewed as the problems with computable numbers in place of the reals. But there are lots of interesting and practical things to solve. It is just those solutions will be more domain specific IMHO.
        cs702 3y ago
        Hmm... You're right: It's quite possible that the new crop of linear RNNs may not be able to solve the same problems as Transformers. It could also be that we will have to increase the depth of these linear RNNs (possibly even dynamically) to enable them to perform comparably well on all problems. Right now it's hard to tell for sure. I don't know. What I do know is that recently proposed linear RNNs are performing comparably to Transformers at similar model sizes, but have not yet been evaluated at state-of-the-art scales.
- dadadad100 3y ago
  As in the case of constraint solvers there are tons of heuristics that have been applied over the years to make performance look like it scales somewhat linearly in many or most problems. This doesn’t mean p==np
  - nyrikki 3y ago
    Most of those have had practical deciders functions. If you consider NP-complete as the intersection of NP, which is a decision problem, and NP-hard which a decider function isn't possible; look at the success of heuristics between those two sets. Existential quantifiers on the second order terms in NP is the same thing. Over Parameterization can be thought as less lossy compression and attention can be thought of as improved retrieval or as additional expressiveness by not missing out on as many outputs using binary output. You can consider how LLMs tend to append, resulting in telescope reduction as one of those approximation reductions. But this is due to the combinatorial optimization, which is far more difficult. Another way to think about it is that PH is equal to the set of boolean queries on a concurent random acess machine using exponentially many processors and constant time. If your datasets have the Markovian property and are close to ergotic there are options, but you probably wouldn't need to resort to attention and over parameterization in that case. The word sense disambiguation problem is probably another lens. That is harder yet but may be a way to think about what I am trying to explain.
    - dadadad100 3y ago
      Thanks for this reply. HN paid for itself again today
- hansvm 3y ago
  One the one-hand, "no". On the other, that's an interesting observation. There are known Θ(N^2) problems, which a linear transformer substitute couldn't possibly solve (in a single pass), and which current transformers might be able to. It's an open question how many of the current LLM capabilities rely on quadratic compute, but linear transformers might be a pipe dream for some current use cases. Generally though, I don't think that's quite the same. Collapsing all O(N^2) problems down to O(N) would collapse the hierarchy and prove P=NP, but it's blatantly impossible and would prove a lot of falsehoods too.
  - nyrikki 3y ago
    The known lower bound for self attention is n^(2-epislon) PH, or the polynomial hierarchy is the collapse I was talking about, but note I was talking about global and not individual or families of instances. Schaefer's Dichotomy Theorem shows that HORNSAT is solvable, given those constraints. I found this paper useful as it reframes it as topology which is helpful to build it intuitions, at least me. https://arxiv.org/abs/2307.03446 https://arxiv.org/abs/2307.03446 Of the proposed linear self attention like solutions I have seen, they tend to approach it more from what can be reduced the clustering problem. A lens for that is FTA vs FMEA, being thought of as top down vs bottom up. Top down is cheaper but may miss things, bottom up doesn't miss things but can result in combinatorial explosion. This paper covers some optimization problems that are NP-hard to approximate to within a given approximation ratio. Being able to do so would show P=NP https://dl.acm.org/doi/pdf/10.1145/321958.321975 https://dl.acm.org/doi/pdf/10.1145/321958.321975 But that is under the assumption that increasing the self attention window was to improve accuracy, not to trade accuracy for efficiency. While this paper is about casual inference and not PAC learning, it is the reason most 'causal AI' is just stocastic search and event trees. https://www.cs.cornell.edu/home/halpern/papers/newcause.pdf https://www.cs.cornell.edu/home/halpern/papers/newcause.pdf
doctorpangloss 3y ago
> The implications [of a bunch of different architectures] for all market participants would be significant. I don't know, who cares. How much good training data is there that correctly exercises 100k context windows? All the costs and complexity are tied up in authoring good training data, not compute. 1 person can invent an alternative easier to train architecture. 1 person cannot author 100k context window instruct examples with the same quality as the 4k ones. It will still take thousands of people for 100k just like it took 1000s of people for 4k windows, image labeling, etc.
- famouswaffles 3y ago
  >All the costs and complexity are tied up in authoring good training data, not compute. No it's compute. Post-Training by Human reinforcement is not necessary. Anthropic employs RLAIF and it works just fine. Some don't bother with reinforcement learning at all and just leave it at fine-tuning on Instruction-response pairs. The work being done to pre or post-training data is insignificant in comparison. You don't need 100k instruct-tuning examples. The vast majority of instruct-tuning data is nowhere maxing even a 4k context. 100k pre-training runs would probably be very helpful but the thing stopping that from happening even in domains that regularly match or exceed that context (fiction, law, code, etc) is the ridiculous compute it would require to train with that much context.
  - doctorpangloss 3y ago
    > The vast majority of instruct-tuning data is nowhere maxing even a 4k context This should indicate for you how much the problem really is the training data.
    - famouswaffles 3y ago
      It shows you don't need a instruction-tuning dataset that wide to create a model that follows instructions for large contexts. I don't know how else to tell you that you're completely wrong on what costs construe the majority of LLM development/training.
araes 3y ago
With the Big O notation, are there also possibilities for either the whole process to go to O(nlogn) or possibly subportions to the O(logn) range? There's also a lot of math operations over the years that have gone to O(Nª) where 1 < a < 2.
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.
chillee 3y ago
This is extremely wrong. The attention component that's quadratic is a relatively small portion of compute.
- cochne 3y ago
  I think they are correct, do you have a source? From my knowledge the only other components are the fully connected networks which are not big contributors.
  - lumost 3y ago
    For small values of N, the linear terms of the transformer dominate. At the end of the day, a double layer of 764*2048 is still north of 3.1 MM flops/token/layer.
  - imtringued 3y ago
    It's quadratic, because of the dot product in the attention mechanism. You can use K-V Caching to get rid of a lot of the quadratic runtime that comes from redundant matrix multiplications, but after you have cached everything, you still need to calculate the dot product k_i * q_j with i,j being index of the tokens. With n tokens, you will get O(n*n). But you have to remember that this is only n^2 multiplications. It's not exactly the end of the world at context sizes of 32k, for example. It only gets nasty in the hundred thousands to millions. Here is the source I used: https://sebastianraschka.com/blog/2023/self-attention-from-scratch.html https://sebastianraschka.com/blog/2023/self-attention-from-s...
  - chillee 3y ago
    https://news.ycombinator.com/item?id=39475528 https://news.ycombinator.com/item?id=39475528 My source is me :) I work at PyTorch on ML compilers. If you don't believe me, perhaps you'll believe Karpathy's diagram (and the general discussion in the thread): https://twitter.com/karpathy/status/1658161721251602432 https://twitter.com/karpathy/status/1658161721251602432
- dTal 3y ago
  To anyone doubting this, note that llama.cpp does not slow down by a factor of 16 when you pass -c 2048 instead of -c 512.

by cs702 3y ago

nyrikki 3y ago

In the general case that would be the same as hierarchy collapse of PH, which would prove P=NP

cs702 3y ago
Well, it would depend on how many tokens from the vocabulary are required, in the worst case, to solve NP problems. Think of the tokens as symbols, and of the vocabulary as a finite alphabet of symbols, in a formal system. In other words, no, it would NOT necessarily prove P = NP.
- nyrikki 3y ago
  The Singleton case is NP-complete If you consider NP second-order existential logic, meaning that given x, you will get a y, While there may be many true values that aren't y, it will help Attention, which requires feed forward networks, which approximate a DAG, you can think of attention as run time reweighing to change what y value is returned. PH is a query expressible in second-order logic, which would allow for 'for any' at the second level. The reduction in the general case to just logarithmic time: O(n log n), would cause issue, there will not be any movement from quadratic time to linear time without massive new discoveries. It is inherent from the restrictions of ANNs having binary output. Considering FP and FNP vs P and NP may help as they make that property clearer than the concept of second-order existential logic does in some contexts.
  - cs702 3y ago
    Thank you. Right now, my puny little brain is searching through what I would describe as "those distant and slightly vague memories" that make up my poor man's knowledge of computational complexity theory. > Attention, which requires feed forward networks, which approximate a DAG, you can think of attention as run time reweighing to change what y value is returned. Isn't that's true for linear RNN mechanisms too? Note that linear RNNs like RWKV and Mamba are linear in the number of tokens in the sequence, but not in the number of features per token.
    - nyrikki 3y ago
      You don't typically get to the Sigma_2^P level unless are a sadist or forced. Attention works differently in RNNs, and it may be able to find different tractable forms, and may solve different problems, but increasing generalization is a reduction of compression in the general case. A many to one reduction to a recursively enumerable set gets you to finite time, a reduction to NP gets you to quadratic time. Obviously those are upper limits and specific instances or classes of instances may do better. P being inside NP is a good example. All ANNs are binary output, which helps with that. SNN or spikey neutral networks, which better model cortical neurons and have continuous output have problems with being un-computable without much complexity as an example. That can be viewed as the problems with computable numbers in place of the reals. But there are lots of interesting and practical things to solve. It is just those solutions will be more domain specific IMHO.
      - cs702 3y ago
        Hmm... You're right: It's quite possible that the new crop of linear RNNs may not be able to solve the same problems as Transformers. It could also be that we will have to increase the depth of these linear RNNs (possibly even dynamically) to enable them to perform comparably well on all problems. Right now it's hard to tell for sure. I don't know. What I do know is that recently proposed linear RNNs are performing comparably to Transformers at similar model sizes, but have not yet been evaluated at state-of-the-art scales.
dadadad100 3y ago
As in the case of constraint solvers there are tons of heuristics that have been applied over the years to make performance look like it scales somewhat linearly in many or most problems. This doesn’t mean p==np
- nyrikki 3y ago
  Most of those have had practical deciders functions. If you consider NP-complete as the intersection of NP, which is a decision problem, and NP-hard which a decider function isn't possible; look at the success of heuristics between those two sets. Existential quantifiers on the second order terms in NP is the same thing. Over Parameterization can be thought as less lossy compression and attention can be thought of as improved retrieval or as additional expressiveness by not missing out on as many outputs using binary output. You can consider how LLMs tend to append, resulting in telescope reduction as one of those approximation reductions. But this is due to the combinatorial optimization, which is far more difficult. Another way to think about it is that PH is equal to the set of boolean queries on a concurent random acess machine using exponentially many processors and constant time. If your datasets have the Markovian property and are close to ergotic there are options, but you probably wouldn't need to resort to attention and over parameterization in that case. The word sense disambiguation problem is probably another lens. That is harder yet but may be a way to think about what I am trying to explain.
  - dadadad100 3y ago
    Thanks for this reply. HN paid for itself again today
hansvm 3y ago
One the one-hand, "no". On the other, that's an interesting observation. There are known Θ(N^2) problems, which a linear transformer substitute couldn't possibly solve (in a single pass), and which current transformers might be able to. It's an open question how many of the current LLM capabilities rely on quadratic compute, but linear transformers might be a pipe dream for some current use cases. Generally though, I don't think that's quite the same. Collapsing all O(N^2) problems down to O(N) would collapse the hierarchy and prove P=NP, but it's blatantly impossible and would prove a lot of falsehoods too.
- nyrikki 3y ago
  The known lower bound for self attention is n^(2-epislon) PH, or the polynomial hierarchy is the collapse I was talking about, but note I was talking about global and not individual or families of instances. Schaefer's Dichotomy Theorem shows that HORNSAT is solvable, given those constraints. I found this paper useful as it reframes it as topology which is helpful to build it intuitions, at least me. https://arxiv.org/abs/2307.03446 https://arxiv.org/abs/2307.03446 Of the proposed linear self attention like solutions I have seen, they tend to approach it more from what can be reduced the clustering problem. A lens for that is FTA vs FMEA, being thought of as top down vs bottom up. Top down is cheaper but may miss things, bottom up doesn't miss things but can result in combinatorial explosion. This paper covers some optimization problems that are NP-hard to approximate to within a given approximation ratio. Being able to do so would show P=NP https://dl.acm.org/doi/pdf/10.1145/321958.321975 https://dl.acm.org/doi/pdf/10.1145/321958.321975 But that is under the assumption that increasing the self attention window was to improve accuracy, not to trade accuracy for efficiency. While this paper is about casual inference and not PAC learning, it is the reason most 'causal AI' is just stocastic search and event trees. https://www.cs.cornell.edu/home/halpern/papers/newcause.pdf https://www.cs.cornell.edu/home/halpern/papers/newcause.pdf

doctorpangloss 3y ago

> The implications [of a bunch of different architectures] for all market participants would be significant. I don't know, who cares. How much good training data is there that correctly exercises 100k context windows? All the costs and complexity are tied up in authoring good training data, not compute. 1 person can invent an alternative easier to train architecture. 1 person cannot author 100k context window instruct examples with the same quality as the 4k ones. It will still take thousands of people for 100k just like it took 1000s of people for 4k windows, image labeling, etc.

famouswaffles 3y ago
>All the costs and complexity are tied up in authoring good training data, not compute. No it's compute. Post-Training by Human reinforcement is not necessary. Anthropic employs RLAIF and it works just fine. Some don't bother with reinforcement learning at all and just leave it at fine-tuning on Instruction-response pairs. The work being done to pre or post-training data is insignificant in comparison. You don't need 100k instruct-tuning examples. The vast majority of instruct-tuning data is nowhere maxing even a 4k context. 100k pre-training runs would probably be very helpful but the thing stopping that from happening even in domains that regularly match or exceed that context (fiction, law, code, etc) is the ridiculous compute it would require to train with that much context.
- doctorpangloss 3y ago
  > The vast majority of instruct-tuning data is nowhere maxing even a 4k context This should indicate for you how much the problem really is the training data.
  - famouswaffles 3y ago
    It shows you don't need a instruction-tuning dataset that wide to create a model that follows instructions for large contexts. I don't know how else to tell you that you're completely wrong on what costs construe the majority of LLM development/training.

araes 3y ago

With the Big O notation, are there also possibilities for either the whole process to go to O(nlogn) or possibly subportions to the O(logn) range? There's also a lot of math operations over the years that have gone to O(Nª) where 1 < a < 2.

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.

chillee 3y ago

This is extremely wrong. The attention component that's quadratic is a relatively small portion of compute.

cochne 3y ago
I think they are correct, do you have a source? From my knowledge the only other components are the fully connected networks which are not big contributors.
- lumost 3y ago
  For small values of N, the linear terms of the transformer dominate. At the end of the day, a double layer of 764*2048 is still north of 3.1 MM flops/token/layer.
- imtringued 3y ago
  It's quadratic, because of the dot product in the attention mechanism. You can use K-V Caching to get rid of a lot of the quadratic runtime that comes from redundant matrix multiplications, but after you have cached everything, you still need to calculate the dot product k_i * q_j with i,j being index of the tokens. With n tokens, you will get O(n*n). But you have to remember that this is only n^2 multiplications. It's not exactly the end of the world at context sizes of 32k, for example. It only gets nasty in the hundred thousands to millions. Here is the source I used: https://sebastianraschka.com/blog/2023/self-attention-from-scratch.html https://sebastianraschka.com/blog/2023/self-attention-from-s...
- chillee 3y ago
  https://news.ycombinator.com/item?id=39475528 https://news.ycombinator.com/item?id=39475528 My source is me :) I work at PyTorch on ML compilers. If you don't believe me, perhaps you'll believe Karpathy's diagram (and the general discussion in the thread): https://twitter.com/karpathy/status/1658161721251602432 https://twitter.com/karpathy/status/1658161721251602432
dTal 3y ago
To anyone doubting this, note that llama.cpp does not slow down by a factor of 16 when you pass -c 2048 instead of -c 512.