routing transformer

**Routing Transformer** is an **efficient transformer that uses online k-means clustering to route tokens into clusters** — computing attention only within each cluster, reducing complexity from $O(N^2)$ to $O(N^{1.5})$ while maintaining content-dependent sparsity. **How Does Routing Transformer Work?** - **Cluster Centroids**: Maintain $k$ learnable centroid vectors. - **Route**: Assign each token to its nearest centroid (online k-means). - **Attend**: Compute full attention only within each cluster. - **Update Centroids**: Update centroids using exponential moving average of assigned tokens. - **Paper**: Roy et al. (2021). **Why It Matters** - **Content-Aware**: Tokens that are semantically similar get clustered together and can attend to each other. - **Learned Routing**: The routing is learned end-to-end, unlike LSH (Reformer) which uses random projections. - **Flexible**: The number and size of clusters adapt to the input distribution. **Routing Transformer** is **attention with learned traffic control** — routing semantically similar tokens together for efficient, content-aware sparse attention.