Your Transformer is Secretly an EOT Solver | Elements of a Vector Space
"/>
"/>
"/>
"/>
Nine months ago, or was it ten? I've learned not to trust my sense of time when deep in a problem. Anyone faced with a major deadline or enveloped in the mire of one particular question for an extended period intuitively understands that Time becomes something else then. Not the measured progression of hours, but rather a kind of thickness, a medium through which one moves with increasing difficulty, like a swimmer who has ventured too far from shore and finds the water has become viscous, resistant.
I was doing what I had seen others do, what perhaps I had been doing all along without quite admitting it to myself: trying to invent yet another subquadratic attention mechanism. Yes, another one. As if the world needed more of these thingsThis is perhaps too cynical. If you are the future inventor of FlashAttention 4, thank you. The world does need efficient implementations, and even asymptotic improvements in memory complexity, but this is best measured in reducing constant factors rather than shaving \(\mathcal{O}(\log n + \log\log n)\) time to \(\mathcal{O}(\log n + \frac{\log\log n}{\log\log\log n})\).. There are already so many. I knew this. You know this. Anyone who works in this field knows this. And yet we persist, as men have always persisted in rebuilding Babel, each generation convinced that this time, with these new tricks, with some recherché materials, with this understanding our predecessors lacked, the tower will stand.
But mine, of course, was going to be different. Mine was going to be new and quirky. Mine was going to reflect practical considerations; real constants and implementation details rather than mere Big-O algorithmic obscurantism.
The idea involved an approximation. This was to be an approximation that became asymptotically accurate as \(n\) (sequence length) grew. This way, it's only wrong in all the ways that don't matter and right in the one way that does. There was, naturally, some unanticipated problem. There is always some unanticipated problem. It's practically a theorem in this field.
Why Asymptotically Accurate Subquadratic Attention is Impossible
Let me explain the nature of that unanticipated problem I mentioned. It is mathematically impossible for any subquadratic attention mechanism to be asymptotically accurate on all inputs.
The intuition is a \(\textit{needle in a haystack}\) construction. The softmax function requires knowing all query-key similarities in each row to compute the normalization constant correctly. If an algorithm inspects only \(o(n^2)\) query-key pairs, then by the pigeonhole principle, there must exist at least one query row \(i^*\) for which it examines only \(o(n)\) of the \(n\) possible keys. Place an arbitrarily large similarity score in one of the uninspected positions, the "needle," and the algorithm will fail catastrophically because it lacks information essential to computing the attention weights.
More formally, define a subquadratic algorithm as one computing \(o(n^2)\) query-key dot products, and asymptotically accurate as producing output that converges to the exact attention matrix in the limit as \(n \to \infty\). Assume, for contradiction, that such an algorithm \(\mathcal{A}\) exists.
By subquadraticity, the average number of keys inspected per query is \(o(n)\). Therefore, there exists a query index \(i^*\) and a corresponding uninspected key index \(j^*\). Now construct an adversarial input: let \(q_{i^*} = e_1\), let \(k_{j^*} = M_n e_1\) where \(M_n = \ln(n^2)\), and set all other queries, keys, and values to zero vectors. The exact attention output for row \(i^*\) concentrates almost entirely on position \(j^*\), converging to \(e_1\) for \(n \to \infty\). But since \(\mathcal{A}\) never inspects \((i^*, j^*)\), it has no information about this dominant contribution and must output approximately zero, yielding a non-vanishing error lower bound of \(\|e_1\|_2 = 1\) in the limit.
The contradiction arises from the global normalization inherent in softmax: computing accurate attention weights requires complete information about all query-key similarities in each row. A subquadratic algorithm cannot provide this complete information for all rows simultaneously, making asymptotic accuracy impossible.
So I walked away. I came back. I walked away again. And then, I had a thought. The thought was this: perhaps there is no way forward through brute force. Perhaps the only way through is to find some hidden mathematical structure, some symmetry or equivalence that's been sitting there all along, waiting for someone to notice it.
That thought, as it happens, was correct. Which is how I ended up writing this paperThis blog post is a companion to my arXiv paper "Scaled-Dot-Product Attention as One-Sided Entropic Optimal Transport" (arXiv:2508.08369). That paper extends this analysis to show that the backward pass gradient is...