Repository navigation
Routed Attention: Learning when to use O(N) conv vs O(N²) attention (75-99% compute savings) #2240
MikeyBeez
started this conversation in
Show and tell
Replies: 0 comments
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Uh oh!
There was an error while loading. Please reload this page.
I've been exploring whether we can avoid O(N²) attention entirely for positions that don't need it.
The Problem
O(N) causal convolution can match attention on language modeling perplexity, but completely fails on tasks requiring long-range retrieval. You have to choose: fast but limited, or capable but slow.
The Idea
What if each position could choose its own computation? Most tokens can be predicted from local context. Only some positions genuinely need to search the full sequence.
I built a lightweight router that examines each position and routes it to either:
The router uses Gumbel-softmax for differentiable discrete routing, trained end-to-end.
Key Finding: Curriculum Learning is Essential
Naive training fails completely. The attention cost penalty prevents the router from exploring the attention pathway, so it never learns when attention is needed.
The fix is two-phase curriculum learning:
Results (Associative Recall)
At distance 126, the router achieves full accuracy using attention on only 0.3% of positions—essentially O(N) compute with O(N²) capability.
Potential FlashAttention Integration
The routed approach could complement FlashAttention:
Links
Would love feedback on:
All reactions