4 ms·

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.
        nyrikki 3y ago
        My hunch is it will be horses for courses.
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

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.
      - nyrikki 3y ago
        My hunch is it will be horses for courses.

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