Summary

• Replace the O(N) List[Tuple[int, int]] materialization with a bigram view over raw token_ids controlled by a new is_bigram flag on RadixKey.
• convert_to_bigram_key is no longer called on the cache_finished_req / cache_unfinished_req hot path; key construction and slicing are now O(1).

Background

• EAGLE radix keys have historically been stored as List[Tuple[int, int]] produced by convert_to_bigram_key; every insert/match allocated N−1 Python tuples.
• At 1M context in SWARadixCache.cache_unfinished_req, convert_to_bigram_key alone took ~138 ms (inside insert ~84 ms + inside the follow-up match_prefix ~54 ms), dominating the step.

Change

• RadixKey stores raw token_ids: List[int] in both plain and bigram modes. is_bigram=True makes __len__, __iter__, __getitem__, and new page_aligned expose bigram semantics over the raw list; a slice over bigrams [a, b) returns a view over raw tokens [a, b+1] so adjacent slices share one boundary token.
• _key_match_page_size1 / _key_match_paged compare raw ints position-by-position and convert matched-tokens → matched-bigrams with max(0, i - 1) (then round to page size for paged mode).
• get_child_key builds a single bigram tuple (or page_size tuples) as the dict key — unchanged in behavior, but no longer per-token allocation.
• compute_node_hash_values hashes overlapping (t_i, t_{i+1}) byte pairs directly from raw tokens, producing the same SHA256 stream as before for backwards-compatible hashes.
• page_align_keys gains an is_bigram flag to keep one extra boundary token when aligning on bigram count.
• Call sites in radix_cache.py, swa_radix_cache.py, and unified_radix_cache.py drop the tuple-materialization path; maybe_to_bigram_view becomes the O(1) entry normalizer for externally-constructed keys. hiradix_cache.py storage path keeps convert_to_bigram_key (external hash-key compatibility).

Numbers (CPU microbench, 1M tokens)

• convert step: ~47 ms → ~0 ms (> 100,000× for this sub-operation).
• match (full prefix): 113 ms → 16 ms (~7×).
• Full cache_unfinished_req-like cycle: 70 ms → 23 ms (~3×).

Test plan

• test/registered/unit/mem_cache/test_swa_unittest.py
• test/registered/unit/mem_cache/test_radix_cache_unit.py
• test/registered/unit/mem_cache/test_unified_radix_cache_unittest.py
• EAGLE + chunked prefill + long-context e2e on GPU