2 ms·

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 possibl

by 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

by hansvm 3y ago

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