How Paged KV Cache Attention Enables Efficient Long-Sequence Processing in LingBot-Map

Paged KV cache attention bounds memory usage to a configured sliding window rather than growing quadratically with sequence length, enabling LingBot-Map to process arbitrarily long video streams with constant GPU memory consumption.

LingBot-Map processes video streams frame-by-frame using a transformer architecture. A naive implementation would cache key-value tensors for every token of every past frame, causing memory usage that grows quadratically with sequence length. The repository solves this through a paged KV cache attention system tightly coupled to the FlashInfer attention kernel, as implemented in lingbot_map/layers/flashinfer_cache.py.

Two-Stream Page Architecture

The system partitions KV cache memory into two distinct streams with different lifecycles. This design separates recyclable visual data from persistent metadata.

Patch Stream (Recyclable)

The patch stream holds dense visual patches extracted from each video frame. One patch page is allocated per frame, where the page size equals the number of patches per frame. Only the most recent scale frames plus a configurable sliding window of frames remain alive in memory. Older patch pages return to a free list and undergo reuse for subsequent frames, preventing unbounded memory growth.

Special Stream (Append-Only)

The special stream stores a small, fixed set of tokens that must persist across the entire video duration. These include camera pose embeddings, register tokens, and scale indicators. Special tokens pack continuously into special pages that are never evicted, ensuring constant access to global video metadata regardless of frame position.

Physical Memory Layout

The physical storage per transformer block uses a 5-D tensor with shape [max_num_pages, 2, page_size, H, D]. The second dimension (size 2) indexes both patch and special pages, while the remaining dimensions represent the maximum number of pages, tokens per page, attention heads, and head dimension respectively.

Runtime Execution Flow

The FlashInferKVCacheManager class orchestrates the paged attention through a four-stage pipeline that executes for every frame.

Appending Frames

When a new frame arrives, kv_cache.append_frame(block_idx, k, v) splits the incoming K/V tensors into special and patch components. It writes these tensors into the appropriate page slots in the physical cache buffer, handling page allocation from the free list when necessary.

Evicting Old Frames

The kv_cache.evict_frames method identifies patch pages that exceed the sliding window size. It recycles only the live_window_patch_pages while leaving special pages untouched. This operation maintains constant memory by reclaiming pages from frames that fall outside the attention window.

Building the Visible Page Table

For each attention step, kv_cache.build_visible_page_table constructs a list of page IDs currently visible to the model. This includes active patch pages (scale frames plus sliding window), all special pages, and handles partially filled final pages via the paged_kv_last_page_len parameter. This table generation occurs inside compute_attention in lingbot_map/layers/attention.py.

FlashInfer Kernel Integration

The FlashInferAttention.compute_attention method invokes flashinfer.BatchPrefillWithPagedKVCacheWrapper. The kernel receives the visible page table and operates only on those pages, making computational cost proportional to the window size rather than the total frame count. The first transformer block builds the execution plan, while subsequent blocks reuse it across all layers.

Why Paged KV Cache Is Efficient

Aspect	Traditional KV Cache	Paged KV Cache (LingBot-Map)
Memory growth	O(L²) where L is total tokens processed	O(window × patches + special) — constant w.r.t. total frames
Data movement	Entire KV matrix must reside on GPU	Only newly-written pages are copied; evicted pages are reused
Kernel launch	One large kernel per layer	One small kernel per step, reusing the same plan across blocks
Token flexibility	Fixed token layout required	Supports arbitrary token counts per frame (non-power-of-2 pages)
Precision modes	FP16/BF16 only	Optional force_fp32 path gathers K/V into dense tensors and runs PyTorch’s scaled_dot_product_attention for validation

Implementation Example

Initialize the paged KV cache manager once per model, then process streaming frames:

# Initialize cache manager for all transformer blocks

kv_cache = FlashInferKVCacheManager(
    num_blocks=12,               # number of transformer layers

    max_num_frames=2000,         # upper bound for pre-allocation

    tokens_per_frame=262,        # 256 patches + 6 special tokens

    num_heads=8,
    head_dim=64,
    dtype=torch.bfloat16,
    device=torch.device("cuda"),
    num_special_tokens=6,
    scale_frames=8,
    sliding_window=64,
)

Process frames in a streaming loop:

# Inside the streaming loop

q, k, v = flash_infer_attention.prepare_qkv(frame_tensor)  # shape: [tp_f, H, D]

# Store key-value tensors for current frame

kv_cache.append_frame(block_idx=layer_id, k=k, v=v)

# Evict frames outside the sliding window

kv_cache.evict_frames(
    block_idx=layer_id,
    scale_frames=8,
    sliding_window=64,
    cross_frame_special=True,
    include_scale_frames=True,
)

# Compute attention using only visible pages

attn_out = flash_infer_attention.compute_attention(block_idx=layer_id, q=q)

Full model integration:

class StreamingModel(nn.Module):
    def __init__(self):
        super().__init__()
        self.attn = FlashInferAttention(dim=256, num_heads=8)
        self.kv_cache = FlashInferKVCacheManager(
            num_blocks=12, max_num_frames=4096, tokens_per_frame=262,
            num_heads=8, head_dim=64, dtype=torch.bfloat16,
            device=torch.device("cuda")
        )

    def forward(self, frame):
        q, k, v = self.attn.prepare_qkv(frame)
        self.kv_cache.append_frame(0, k, v)       # block 0 example

        self.kv_cache.evict_frames(0, 8, 64)     # slide window

        out = self.attn.compute_attention(0, q)  # compute cross-frame attention

        return out

Key Source Files

The paged KV cache attention system spans the following modules in the Robbyant/lingbot-map repository:

• lingbot_map/layers/flashinfer_cache.py — Implements FlashInferKVCacheManager with page allocation, eviction logic, and visible page table construction.
• lingbot_map/layers/attention.py — Defines FlashInferAttention and integrates with flashinfer.BatchPrefillWithPagedKVCacheWrapper.
• lingbot_map/layers/block.py — Demonstrates plan reuse across transformer blocks during compute_attention calls.
• lingbot_map/models/gct_stream.py — High-level streaming model that orchestrates frame-wise inference using the paged cache.

Summary

• Paged KV cache attention eliminates quadratic memory growth by recycling patch pages outside a fixed sliding window.
• The two-stream architecture separates ephemeral visual patches from persistent special tokens, optimizing both memory reuse and information retention.
• FlashInfer integration ensures computational efficiency by operating only on visible pages, with plan reuse across transformer blocks.
• Memory usage remains constant regardless of video length, bounded by O(window × patches + special) rather than total sequence length.

Frequently Asked Questions

How does the two-stream design prevent memory exhaustion?

The two-stream design isolates recyclable visual patches from permanent metadata. By evicting only patch pages while preserving special pages, the system caps memory usage at the sliding window size plus a small constant for special tokens, preventing the unbounded growth that would occur if all historical tokens remained cached.

What distinguishes patch pages from special pages in the KV cache?

Patch pages store dense visual feature tokens extracted from video frames and follow a recycling policy where frames outside the sliding window are evicted. Special pages contain camera poses, registers, and scale tokens that must persist for the entire video duration and are never evicted, ensuring global context remains accessible.

How does FlashInfer integrate with the paged KV cache?

The FlashInferAttention class passes the visible page table generated by build_visible_page_table to flashinfer.BatchPrefillWithPagedKVCacheWrapper. This kernel performs attention only over the specified pages, eliminating the need to process or store evicted tokens while maintaining computational efficiency proportional to the active window size.

Can the sliding window size be adjusted dynamically?

The sliding window size is configured during FlashInferKVCacheManager initialization via the sliding_window parameter. While typically fixed for a given inference session, the evict_frames method accepts runtime parameters for scale_frames and sliding_window, allowing different blocks to maintain different window sizes if the model architecture requires variable attention spans.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}