RouteRelay: Event-Triggered Cross-Layer Route Reuse for Efficient Dynamic Sparse Attention

1 Introduction

• Dynamic sparse routing repeats across the network, although neighboring layers often preserve the same broad semantic dependencies.Reusing indices can skip rebuilding a complete score matrix without reusing attention outputs.Source: §1 · p. 1
• RouteRelay stores selected chunks, near-miss competitors, and random sentinels at anchor layers; intermediate layers rescore these candidates and fully refresh only unstable rows.Attention at every layer still uses that layer’s own queries, keys, and values.Source: §1 · p. 1
• The method combines a sufficient top-k margin condition with a bound on random sentinels missing multiple newly competitive chunks.Source: §1 · p. 2
• The evaluation measures route fidelity, refreshed-row fraction, score-pair reduction, and CPU latency across drift, sentinel-ablation, and routing-scale experiments.Source: §1 · p. 2

2.1 Dynamic Sparse Routing

• Selected chunks are expanded into token indices for sparse attention, while routing scores query–key chunk pairs and adds selection overhead.DHSA measurements show routing and chunk selection can be material components of long-context prefill time (Xiong et al.).Source: §2.1 · p. 2

2.2 Why Route Reuse Is Safer than Attention Reuse

• Cross-layer KV sharing and attention-structure reuse reduce repeated computation, but changing KV states or attention outputs changes the model’s numerical operation.Source: §2.2 · p. 2
• RouteRelay relays integer chunk IDs, so floating-point attention quantities remain layer-specific; only whether the selected index set matches the current route is approximate.Source: §2.2 · p. 2

3.1 Route Ledger

• Each row’s ledger stores selected routes and a sentinel set of near-cutoff chunks, uniformly sampled omitted chunks, and mandatory global candidates.Near-miss sentinels target local rank swaps; random sentinels hedge against low-ranked chunks becoming important after representation shifts.Source: §3.1 · p. 2

3.2 Candidate Rescoring

• Rows reuse routes when selected candidates remain above sentinels; failed tests trigger full rescoring only for unstable rows.Forced anchors can bound the lifetime of stale random sentinels, and Figure 1 distinguishes route-index reuse from layer-specific attention computation.Source: §3.2 · p. 2, Figure 1 · p. 3

3.3 Top-k Stability

• A selected–omitted margin greater than twice the maximum score perturbation preserves every selected–omitted ordering.The exact maximum perturbation requires the full score row, so the lemma is primarily an analysis tool; the sentinel trigger cheaply tests for violations near the decision boundary.Source: §3.3 · p. 3

3.4 Random-Sentinel Miss Probability

• Random sentinels are most effective when route change is broad, while near-miss sentinels target isolated rank swaps; the miss bound does not guarantee perfect recall.Source: §3.4 · p. 3

3.5 Complexity

• Routing work falls substantially when candidate width is much smaller than the key-chunk count and the refreshed-row fraction is small; sparse-attention cost is unchanged.Source: §3.5 · p. 3

4.1 Route-Maintenance Dataflow

• Anchor layers initialize selected routes, sentinels, and anchor ages; intermediate layers refresh routes and sentinel sets only for rows that fail the stability test.Stable rows keep their routes and advance their ledger ages.Source: §4.1 · p. 3

4.2 Row-Selective Routing Kernel

• A fixed-width batched dot product rescores candidates, while a prefix sum compacts unstable rows for complete score-row computation and ledger updates.If no rows are unstable, the full router is skipped.Source: §4.2 · p. 3

4.3 Interaction with Existing Routers

• RouteRelay leaves boundary construction, chunk representations, token expansion, causal masking, and the sparse-attention backend unchanged, and supports route widths chosen by the underlying policy.It can be inserted between route scoring and token expansion.Source: §4.3 · p. 4

4.4 Batching and Memory

• Ledger storage is O(nq c) indices per layer group, where c = k + m + r; with nq = 1024 and c = 64, 32-bit indices occupy 256 KB.Ledgers are bucketed by route width so compatible rows can share kernels.Source: §4.4 · p. 4

5.1 Cross-Layer Route Stability

• At drift 0.03 and 0.06, RouteRelay rerouted 55.4% and 78.2% of rows with more than 99.99% recall, versus fixed-stride recall of 94.9% and 91.2%.At drift 0.01, it rerouted 25.0% of rows with 100.0% recall; its refresh work rises with evidence of instability rather than following a fixed global stride.Source: §5.1 · pp. 4–5

5.2 Sentinel Ablation

• Twelve near-miss sentinels recovered 100.0% recall while evaluating 50.8% of full-routing score pairs; random sentinels alone reached 92.32% recall at 14.2%.Increasing near-miss width to 24 and 48 preserved 100.0% recall but raised score-pair fractions to 55.3% and 64.2%, respectively.Source: §5.2 · p. 5

5.3 Routing-Scale Study

• RouteRelay retained 100.0% route recall at every tested size while evaluated score pairs fell from 51.6% at 128 chunks to 38.5% at 1024.The fraction was 38.4% at 512 chunks and 38.5% at 1024; the plateau reflects full refreshes becoming a larger share of remaining work.Source: §5.3 · pp. 5–6

5.4 Wall-Clock Routing Cost

• Across tested CPU settings, unfused RouteRelay is 1.6–3.7× slower than full routing despite evaluating fewer score pairs.Irregular gathers, row compaction, conditional full-row routing, and ledger reconstruction add overhead; the authors identify fused GPU or equivalent compiled execution as a practical implementation need.Source: §5.4 · p. 6

• Reformer, Linformer, and Performer alter the attention operator, while Routing Transformer learns content-dependent sparse neighborhoods; RouteRelay instead amortizes route construction for an existing dynamic sparse operator.Source: §6 · p. 6
• Static-pattern methods, online structured routing, content-aware chunk routing, and query-dependent retrieval offer different sparse-attention designs; RouteRelay reduces how often an existing dynamic pattern is recomputed.Source: §6 · p. 6
• KV-cache methods select or share retained states, whereas RouteRelay preserves each layer’s Q, K, V, softmax, and output, reusing only discrete route metadata and refreshing unstable query rows.Source: §6 · pp. 6–7
• PagedAttention manages non-contiguous KV caches and FlashAttention reduces exact-attention memory traffic; both are complementary to reducing score pairs evaluated by a dynamic router.Source: §6 · p. 7
• Unlike early-exit and layer-skipping methods, RouteRelay executes every Transformer layer and adapts sparse-router cost without changing the architecture or backbone weights.Source: §6 · p. 7

• 100.0% recall while evaluating as little as 38.4% of full-routing score pairs across the tested routing scales.Source: §7 · p. 7
• Anchor layers compute complete routes, while intermediate layers rescore selected chunks and compact sentinels, rerouting unstable rows on demand.Source: §7 · p. 7
• RouteRelay preserves exact sparse attention within each selected set and is orthogonal to approaches that summarize omitted content or vary token budgets.Source: §7 · p. 7
• The slower unfused CPU path shows that arithmetic savings require a fused kernel to translate into latency gains.Source: §7 · p. 7