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 glo

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