Long-Context Engineering at Million-Token Scale: Sparse Attention and Index Reuse

    A practical engineering walkthrough for making million-token context windows usable rather than merely advertised. It covers why headline context limits say nothing about real cost, how sparse MoE and dynamic sparse attention (DSA) reshape the compute curve, and why cross-layer index reuse plus training-time alignment are needed to make DSA deployable. It also covers multi-token prediction and speculative decoding, KV cache capacity math and layered serving architecture (paged KV, prefix reuse, tiered storage, chunked prefill with prefill/decode disaggregation), a cost estimation framework, reinforcement learning for long-horizon agents including context compaction and reward hacking defenses, a tiered acceptance test plan with position-depth sweeps, and the cases where retrieval is the better answer than long context.

    1. Why “1M Context Support” Is Just Marketing Talk

    Over the past two years, nearly every model release has come with a context length number attached: 128K, 200K, 1M. But what engineering teams actually care about is not the nominal ceiling. It is four other things along that curve:

    1. The compute curve. Attention cost in the prefill phase grows quadratically with sequence length. For a single request with 1M input tokens, the attention portion alone can exceed the business’s total daily compute consumption.
    2. The memory curve. KV cache grows linearly with length, which determines how many concurrent sessions a single node can hold — and that converts directly into unit cost.
    3. The latency curve. Time to first token (TTFT) is dominated by prefill, and long requests stretch the queueing time of short requests on the same node.
    4. Effective utilization. Can the model accurately retrieve a fact located at position 12K while reading at position 800K? This one is both the worst and the least visible: benchmark scores don’t drop, business results do.

    Engineering the first four while making the fourth solid is what “long context is actually usable” means. Let’s take it layer by layer.

    2. Base Model Choice: Sparse MoE Plus Dynamic Sparse Attention

    2.1 Sparse MoE Only Solves Half the Problem

    Sparse mixture-of-experts (MoE) decouples capacity from compute through “large total parameters, few active parameters per token.” A configuration with roughly 700B total parameters and about 40B active per token has an FFN compute cost close to that of a dense 40B model. This is a necessary precondition for long context, but MoE only compresses the per-token feed-forward cost. The quadratic term in attention is untouched. For long context, the cost bottleneck is usually attention, not FFN.

    2.2 How Dynamic Sparse Attention Works, and What It Costs

    Dynamic sparse attention (DSA) lets each query attend only to the most relevant subset of keys. A lightweight indexer is trained to score every position and select the top-K; attention is then computed only over the selected positions.

    If full attention has complexity O(S²·d), top-K sparse attention is O(S·k·d), where S is sequence length, k is the number of keys retained per query, and d is the head dimension. With S=1M and k=2048, the multiply-accumulate count for the attention portion drops to roughly 1/512 — an order-of-magnitude gain.

    But the cost is widely underestimated: the indexer itself has to be computed. Each Transformer layer independently computes a Q·Kᵀ scoring pass plus top-K selection, which means the indexing overhead is also O(L·S²·d_idx). When d_idx is only a quarter of the head dimension, the indexing term accounts for roughly 20%–30% of total attention cost; on very long sequences, the memory-access overhead of top-K sorting and gather amplifies it further. The result: naive DSA makes long context “affordable to compute,” but the indexing layer makes it “slow to run and expensive to deploy.”

    3. Cross-Layer Index Reuse: Turning Per-Layer Selection into Periodic Sharing

    3.1 The Core Observation

    Adjacent layers agree closely on which positions matter. That correlation creates room to compress how often index computation runs: instead of recomputing at every layer, indices can be shared over a fixed window.

    A typical implementation is “reuse every four layers”: each group of 4 consecutive layers forms a reuse group, the first layer in the group runs the indexer and produces the top-K indices, and the remaining three reuse that result directly, skipping scoring and selection.

    1. # Illustrative pseudocode: cross-layer index reuse
    2. REUSE_WINDOW = 4
    3. def attn_layer(layer, hidden, kv_cache, idx_store):
    4. q = q_proj(hidden)
    5. k, v = kv_proj(hidden)
    6. kv_cache.append(layer, k, v) # append this layer's KV for later decoding reuse
    7. head = layer % REUSE_WINDOW
    8. if head == 0:
    9. idx = topk(indexer(q, k), k=K) # only the group's first layer scores and selects
    10. idx_store.save(layer, idx)
    11. else:
    12. idx = idx_store.load(layer - head) # remaining layers in the group reuse directly
    13. return sparse_attn(q, kv_cache.get(layer), idx) # compute only over selected positions

    3.2 Design Trade-Off Checklist

    Index reuse is not a free lunch. Each item below needs to be settled before shipping:

    • Value of the reuse window N. Larger N amortizes indexing cost more thinly, but “important positions” drift further. In practice N lands between 3 and 8, and deeper networks generally tolerate longer windows than shallow ones.
    • Sharing granularity. Do you share the full top-K index set, or the indexer’s score ordering? The former is simpler to implement and friendlier to memory access; the latter lets each layer do a small re-rank, which is slightly more accurate but reduces the benefit.
    • Dimension alignment. When the indexer’s output dimension differs from the attention head dimension, a projection adapter is required — and that projection must participate in training. It cannot be stitched together ad hoc at inference time.
    • Fallback behavior. When reuse causes attention entropy to rise abnormally (the distribution flattens, indicating the selected positions are not relevant enough), fall back to full attention or enlarge K. In production, a moving average of attention entropy works well as an online monitoring signal.

    3.3 The Critical Prerequisite: Index Reuse Must Be Introduced During Training

    This is the most frequently overlooked point. If index reuse is added only at inference time, the model sees sparse patterns it never encountered during training and quality degrades noticeably. The correct approach is to introduce the reuse mechanism into the computation graph in the mid-to-late pretraining phase, while sequence length is being gradually extended, so the model adapts during training to the idea that “attention positions in some layers are decided on their behalf by upstream layers.”

    Companion long-document pretraining practices:

    • Positional extrapolation. The base model extrapolates via RoPE base frequency scaling (NTK-aware / YaRN-style schemes). The scaling factor must match the target length and the training buckets; it cannot be changed ad hoc at inference time.
    • Length curriculum. Sample progressively across buckets of 8K → 32K → 128K → 1M, gradually increasing the share of long samples. Dumping in full long sequences at once leads to unstable convergence.
    • Data composition. Long documents must cover real long-range structures: code repositories, legal contracts, logs and call traces, multi-turn tool-calling trajectories. Simply concatenating short documents only teaches a “position-independent” pseudo-long context.
    • Sparse pattern consistency. The K, the index reuse window, and the indexer temperature used during training must match the inference configuration, otherwise the gains don’t transfer.

    4. Multi-Token Prediction and Speculative Decoding: Turning a Training Objective into Inference Speedup

    Multi-token prediction (MTP) adds several prediction heads during training so the model predicts multiple future tokens at once. At inference, these heads act as a draft model, and the main trunk verifies them round by round; accepted tokens are committed directly. This is speculative decoding.

    Its benefit is determined entirely by the mean acceptance length: with acceptance length τ, a single forward pass yields roughly τ tokens, for a theoretical speedup approaching τ×. In practice this is discounted by verification overhead and batching effects. In long-context settings, where the bulk of computation is dominated by prefill and KV memory access, the marginal cost of single-step decoding is relatively low, so speculative decoding actually offers better value. Empirically, moving mean acceptance length from just above 4 to above 5 typically improves end-to-end decode throughput by 15%–25%; but this range depends heavily on task distribution — gains are clear for highly predictable tasks like code completion, while open-ended creative tasks see acceptance rates drop significantly.

    Two engineering constraints:

    • KV consistency. When a token produced by a draft head is rejected, the corresponding positions in the KV cache must be rolled back precisely, otherwise subsequent generation is polluted. Paged KV management reduces rollback to moving page pointers, keeping the cost under control.
    • Multi-step vs. single-step drafting. A draft chain of around 7 steps often outperforms longer chains on long sequences, because every additional step costs another KV memory access while acceptance probability decays with position.

    5. Serving Side: Building a System for 1M Context

    5.1 First, Do the KV Cache Capacity Math

    KV cache size in bytes can be estimated as:

    1. bytes ≈ 2 × L × H_kv × d_h × S × b

    where L is the number of layers, H_kv is the number of KV heads (far smaller than the number of attention heads under GQA/MQA), d_h is the head dimension, S is sequence length, and b is bytes per element.

    Take an example configuration: L=60, H_kv=8, d_h=128, bf16 (b=2). That is roughly 0.23 MiB per token, so a single session with a 1M context consumes about 240 GiB of GPU memory. The conclusion is straightforward: a pure-GPU-memory approach does not hold at million-token context. You must go tiered.

    5.2 Four Required Capabilities

    1. Paged KV management and prefix reuse. KV is managed in fixed-size pages, and identical prefixes (system prompt, long documents, repository context) are shared across requests. In multi-turn conversation and document QA scenarios, prefix hit rates often exceed 60% — this is the first lever for long-context cost optimization.
    2. Tiered storage and KV offloading. Hot pages live in GPU memory, warm pages on local high-speed SSD, and cold sessions in object storage. When a cold session resumes, its KV is streamed back in and overlapped with computation to avoid serial waiting. Cloud implementations typically rely on a combination of object storage, elastic block storage, and a container platform; lifecycle and hot/cold tiering policies need separate tuning based on business session length.
    3. Chunked prefill and prefill/decode separation. Split long prompts into fixed-size chunks (e.g., 8K–32K) computed in batches, and insert scheduling points between chunks so short requests can jump the queue and tail latency stays bounded. You can go further and place prefill and decoding in separate resource pools, scaling each against its own bottleneck: the prefill pool is compute-bound, the decode pool is memory-bandwidth-bound, and co-locating them wastes both directions.
    4. Isolation and quotas. Route by input length tier; very long requests go to a dedicated queue with dedicated quota, with maximum context and timeout limits, so a single pathological request cannot drag down the whole pool. Logging, services, and alerting need to cover TTFT percentiles as a function of input length, KV hit rate, memory watermark, and rejection rate. These metrics are far more useful than average latency.

    5.3 A Rough Cost Estimation Framework

    1. per-request cost ≈ (S² · c_attn / k_eff + S · c_ffn) · unit_price
    2. + S · kv_bytes · price_mem · T_hold

    The first term is compute, where k_eff is the effective key count after sparsification (including the amortization effect of index reuse). The second term is the duration of memory occupancy. The optimization levers are usually raising k_eff and lowering T_hold — that is, sparsify harder and release session memory faster.

    6. The Reinforcement Learning Loop for Long-Horizon Agents

    The value of long context ultimately materializes in agents: a coding agent running 50 steps accumulates context linearly with each step, and by step 30 the window is packed with early logs and failed attempts.

    6.1 Context Compaction

    Trigger rolling compaction as you approach the token budget ceiling (an empirical threshold of 70%–80%): fold early steps into a structured summary (goal, completed actions, key conclusions, open questions), trim raw tool output down to paths and summaries, and externalize full detail to files or a retrieval system for on-demand recall. The point of compaction is not saving tokens, it is preserving the decision chain — the summary must retain “why this option was ruled out,” otherwise the agent will repeatedly walk down already-disproven paths.

    6.2 Critic + PPO: Addressing Sparse Rewards

    Rewards in long-horizon tasks are extremely sparse — only final success or failure. The usual approach is to introduce a value model (Critic) that estimates remaining success probability at the step level, propagating the sparse terminal reward along the trajectory for credit assignment, with PPO’s clipped objective controlling the size of policy updates and a KL penalty constraining drift from the base model. Trajectory lengths vary widely, so advantage estimation needs length normalization; otherwise long trajectories are naturally down-weighted.

    6.3 Anti-Reward-Hacking

    If a reward can be gamed, the model will game it. Common defenses:

    • Verifiable rewards: replace subjective scoring with objective signals such as unit tests, compile results, schema validation, and state hashes;
    • Process constraints: detect cheating patterns like modifying test files, hardcoding return values, or skipping validation branches, and score them as failures outright;
    • Length penalties: prevent farming process rewards by adding steps;
    • Sandbox isolation: network-isolate the training and evaluation environments so the model cannot obtain answers through external calls;
    • Human spot checks: periodically review high-reward trajectories by hand to confirm the reward function has not been gamed.

    7. Acceptance Checklist: How to Tell Whether Long Context “Actually Works”

    Don’t use needle-in-a-haystack as the sole standard — it has been optimized against too thoroughly. Instead, run a five-tier progression, each evaluated at multiple length points: 8K, 32K, 128K, 512K, and 1M.

    Tier What it tests Typical failure mode
    Single-needle retrieval Locating one fact Position sensitivity, loss in the middle section
    Multi-needle aggregation Collecting and summarizing N clues Incomplete recall, failed deduplication
    Cross-section multi-hop Reasoning that combines two or more pieces of information Only the most recent piece is used
    Long code repository tasks Locating and modifying across files Hallucinating non-existent symbols
    Distractor robustness Injecting similar but irrelevant content Being misled by similar text

    Also run a position sweep that places the answer at 5%, 25%, 50%, 75%, and 95% depth, and plot the accuracy-versus-position curve. If the middle collapses noticeably, long-sample position coverage during training was insufficient.

    On the engineering side, watch for: whether TTFT scales sublinearly with input length (the signal that sparsification is working), the throughput inflection point as concurrency rises, KV prefix hit rate, and the ratio of P99 to P50 (a measure of tail-latency control quality).

    8. When Not to Use Long Context

    Set clear boundaries: a million-token context is not the optimal answer to every problem.

    • Stable, reusable knowledge is more economical through retrieval — write once, reuse many places, at a unit cost far below stuffing the full text in every time.
    • For tasks that only need to locate a few facts, retrieval plus short context can cost on the order of one percent of stuffing everything in.
    • Long context is genuinely irreplaceable when you need global structural understanding (refactoring an entire repository), consistency reasoning across large spans (comparing contract terms against code), or agent trajectories that require the complete decision history.

    The pragmatic architecture is hybrid: retrieval handles coarse filtering and knowledge reuse, long context performs global reasoning over the candidate set, and the two are bridged by a structured intermediate representation.

    9. Summary

    Long-context engineering compresses into a single through-line: first shrink the numerator of sparsification (cross-layer index reuse amortizes indexing cost), then enlarge the denominator (larger K and steadier training-time alignment), and finally control the cost terms with tiered storage and prefix reuse on the serving side. Miss any one of the three, and 1M context remains a number on a spec sheet rather than a deliverable capability.