We identify a routing paradox in hybrid sequence models: content-based routing - deciding which tokens deserve expensive attention - requires pairwise computation, and this requirement is inescapable. Through 20+ controlled experiments across three tasks, multiple scales (200K to 1.4B parameters), and 15+ routing mechanisms, we map the routing landscape exhaustively. Every system that achieves high routing precision does so through pairwise token comparison. Every mechanism that avoids pairwise computation fails: recurrent models (Mamba-1.4B: 29%), memory banks (12%), bandits (0.7-3.6%), contrastive pretraining (1.6%), and 12 other approaches all cluster at 1-29%. Routing needs two ingredients: (1) per-token representations with bidirectional context and (2) pairwise token comparison. Bidirectional Mamba (O(n)) + pairwise comparison achieves 99.5%; replacing the full pairwise router with rank-1 projection improves this to 99.7%. Adding one bidirectional layer to frozen Pythia-1B recovers 99.4% routing. Six different O(n) preprocessing mechanisms (bidirectional Mamba, Perceiver inducing points, causal attention with E2E training, sparse attention, bidirectional attention, rank-1 projection) all succeed; global mean pooling (1.9%) and Fourier mixing (0.9%) fail. The routing signal occupies a ~34-dimensional latent subspace, invisible to cosine similarity. Non-learned indices (Bloom filter: 90.9%; BM25: 82.7%) bypass the bottleneck for exact/keyword matching. Combining O(n) bidirectional Mamba with rank-1 pairwise projection yields 99.7% routing at linear inference cost.
Figures & tables
Figure 1: The routing paradox. (a) Hybrid architectures want cheap recurrence for most tokens and expensive attention for a few. A router decides which tokens get attention. (b) The paradox: the router needs representations with relational context to identify relevant tokens — but creating those representations requires the very pairwise computation routing aims to avoid. (c) Our experiments reveal the two-ingredient resolution: O(n) bidirectional preprocessing + pairwise comparison achieves 99.7% routing at linear inference cost.
Figure 2: Phase transition at one Transformer layer. (a) Routing precision jumps 82 × from 1.2% to 98.4% between 0 and 1 layers; additional layers provide no gain. (b) Over training, the transition occurs in a single epoch (epoch 10), a discrete regime change rather than gradual improvement.
Figure 3: The routing signal lives in a latent subspace. (a) Cosine similarity between query and answer representations is negative in the successful condition (1L Transformer) — matching tokens are not geometrically close. (b) Replacing learned routing projections with random matrices drops routing from 98.4% to 2.6%, confirming the signal requires specific learned access. (c) SVD of the combined routing matrix WqWk⊤ shows 90% of energy in just 34 of 128 dimensions.
Figure 4: The routing landscape. Twenty approaches tested across non-learned indices, learned segment routing, contextual bandits, and contrastive pretraining. Only mechanisms with pairwise token comparison succeed; everything else clusters at 1–29%.
Figure 5: Why contrastive pretraining fails. (a) Attention has three steps; contrastive loss replicates only step 1. (b) Step 3 (value aggregation) writes match results into representations — one mechanism for providing relational context (bidirectional recurrence and inducing points are others; see Section 4.6 ). (c) Contrastive pretraining achieves only 1.6–2.2%, no improvement over the 1.2% baseline.
Figure 6: Generalization beyond the synthetic task. (a) Our findings replicate on the Zoology MQAR benchmark: Transformer 1L achieves 100% routing and 55.6% accuracy; Flow and raw embeddings cluster at ∼ 25%. (b) BM25 achieves 82.7% retrieval on HotpotQA with zero learned parameters.
Task
Model / Method
Routing / Retrieval
Task Acc
MQAR [ 22 ]
Transformer 1L
100.0%
55.6%
Flow 2L
24.2%
5.6%
Raw embeddings
25.6%
7.6%
HotpotQA [ 33 ]
BM25 (non-learned)
82.7%
— †
Random retrieval
12.5%
— †
Table 1: Generalization results. The routing hierarchy replicates across tasks. MQAR routing precision = Investigator selects the correct key position. HotpotQA precision = at least one supporting sentence appears in retrieved segments.
Model
Type
Routing
Rank
Pairwise stage
Systems with pairwise computation (all succeed):
Bidir attention 1L (E2E)
Bidir attn + router
99.1%
1.6
Preproc + router
Causal attention 1L (E2E)
Causal attn + router
98.9%
1.6
Router only ⋆
Sparse bidir (w32+g16)
Sparse bidir + router
99.7%
1.5
Preproc + router
Rank-1 bidir projection
Rank-1 bidir + router
98.8%
1.6
Preproc + router
Pythia-1B + bidir bridge
Frozen + bidir layer
99.4%
3.5
Bridge + router
Table 2: The pairwise–compression divide. Every system with pairwise token comparison achieves high routing. Every system without it fails. The divide is not causal-vs-bidirectional but pairwise-vs-compressed. The Investigator’s dot-product scoring ( sij=qi⊤kj ) is itself pairwise computation — systems with attention preprocessing AND pairwise routing have pairwise computation at two stages.
Regime
Routing
Ingredient(s) present
Cost
Both ingredients present (all succeed):
Bidir Mamba + rank-1 pairwise
99.7%
Bidir preproc + pairwise
O(n)
Sparse bidir attn (w32+g16)
99.7%
Bidir preproc + pairwise
O(n⋅w)
Perceiver M=16 + pairwise
99.5%
Inducing pts + pairwise
O(16n)
Pythia-1B + bidir bridge
99.4%
Bridge + pairwise
O(n2)
Bidir attn 1L + pairwise
99.1%
Bidir attn + pairwise
O(n2)
Table 3: The routing quality hierarchy. Routing requires two ingredients: (1) per-token representations with bidirectional context, and (2) pairwise token comparison. The preprocessing can be attention, bidirectional recurrence, or inducing points — but pairwise comparison cannot be absent. Combining O(n) bidir Mamba with rank-1 pairwise yields the best routing (99.7%) at linear cost.