a day ago
- The author attempted to invent a subquadratic attention mechanism but proved that asymptotically accurate subquadratic attention is impossible via a needle-in-a-haystack argument, as softmax requires complete row information.
- This impossibility led to the discovery of an exact equivalence between scaled dot-product attention and a one-sided entropic optimal transport (EOT) problem.
- In the EOT formulation, source measures are fixed (each query emits unit mass), the target marginal is free, costs are negative query-key dot products, and the entropy regularization parameter equals the temperature sqrt(d_k).
- The unique minimizer of this EOT problem is exactly the softmax attention matrix, as proven using Lagrange multipliers.
- The paper further shows that the backward pass gradient is equivalent to an advantage-based policy gradient and that the EOT formulation induces a specific information geometry.