# How the Two-Stream Paged KV Cache Works in FlashInferKVCacheManager

> Understand the two-stream paged KV cache in FlashInferKVCacheManager. Discover how it optimizes memory and enables efficient sliding-window attention for video sequences.

- Repository: [Robbyant/lingbot-map](https://github.com/Robbyant/lingbot-map)
- Tags: internals
- Published: 2026-07-25

---

**The `FlashInferKVCacheManager` implements a two-stream paged key-value cache that separates recyclable patch tokens from append-only special tokens within a unified physical memory block, enabling efficient sliding-window attention for video frame sequences.**

The `FlashInferKVCacheManager` in the LingBot-Map repository provides a high-performance memory management layer for transformer-based video understanding models. By splitting key-value tensors into two distinct logical streams—visual patch tokens and metadata special tokens—it achieves O(1) page allocation and minimal memory churn during long-form video processing.

## Architecture Overview

### Logical Stream Separation

The manager maintains two independent logical streams to handle different token lifecycles. According to the source code in [`lingbot_map/layers/flashinfer_cache.py`](https://github.com/Robbyant/lingbot-map/blob/main/lingbot_map/layers/flashinfer_cache.py) (lines [4‑11](https://github.com/Robbyant/lingbot-map/blob/main/lingbot_map/layers/flashinfer_cache.py#L4-L11)), the **patch stream** stores recyclable pages holding per-frame visual patch tokens. One page is allocated per frame, and pages are recycled as frames slide out of the attention window.

The **special stream** (lines [12‑17](https://github.com/Robbyant/lingbot-map/blob/main/lingbot_map/layers/flashinfer_cache.py#L12-L17)) functions as an append-only pool storing six special tokens per frame (camera, register, and scale tokens). These pages are never evicted; the pool simply grows to accommodate new frames, ensuring constant access to metadata for attention computation.

### Physical Memory Layout

Both streams share a single contiguous physical memory allocation per transformer block. The cache stores data in a 5-D tensor with shape:

```python
kv_caches[block_idx]: [max_num_pages, 2, page_size, H, D]

```

As implemented at lines [19‑22](https://github.com/Robbyant/lingbot-map/blob/main/lingbot_map/layers/flashinfer_cache.py#L19-L22), pages `0` through `max_patch_pages-1` belong to the patch pool, while pages `max_patch_pages` through `max_num_pages-1` belong to the special pool. This layout ensures cache-friendly access patterns while maintaining logical separation between streams.

## Memory Pool Sizing and Allocation

### Patch Page Calculation

The patch pool size accounts for the scale frames, sliding window, and headroom. The specific calculation at lines [32‑33](https://github.com/Robbyant/lingbot-map/blob/main/lingbot_map/layers/flashinfer_cache.py#L32-L33) sets:

```

patch_pages = scale_frames + sliding_window + 16

```

This guarantees sufficient pages for both the permanent scale frame buffer and the temporary sliding window, plus 16 pages of headroom to prevent allocation failures during frame transitions.

### Special Page Pre-allocation

The special stream requires different handling due to its append-only nature. Lines [34‑36](https://github.com/Robbyant/lingbot-map/blob/main/lingbot_map/layers/flashinfer_cache.py#L34-L36) show that special pages are pre-allocated for a configurable `max_total_frames` parameter plus additional headroom. Since these pages are never recycled, the pre-allocation strategy prevents runtime memory fragmentation during long video sequences.

## Frame Lifecycle Management

### Appending Frames with Token Splitting

When processing a new video frame, the `append_frame` method splits incoming K/V tensors into distinct components. At lines [24‑28](https://github.com/Robbyant/lingbot-map/blob/main/lingbot_map/layers/flashinfer_cache.py#L24-L28), the implementation separates:

- `sp_k` and `sp_v`: The six special tokens per frame
- `patch_k` and `patch_v`: The remaining patch tokens (e.g., 256 patches per frame)

This bifurcation allows each tensor type to follow its respective memory management strategy.

### Writing Patch Pages

The `_write_patch_page` method handles patch token storage with intelligent routing. As shown at lines [74‑84](https://github.com/Robbyant/lingbot-map/blob/main/lingbot_map/layers/flashinfer_cache.py#L74-L84), the method obtains a free patch page, writes the patch tokens, and routes the page to either:

- The **scale deque**: For the first `scale_frames` frames (permanent retention)
- The **live window deque**: For subsequent frames (subject to eviction)

### Writing Special Tokens

Special tokens bypass the recycling mechanism entirely. The `_write_special_tokens` method (lines [14‑25](https://github.com/Robbyant/lingbot-map/blob/main/lingbot_map/layers/flashinfer_cache.py#L14-L25)) appends the six special tokens to the special pool, automatically handling page-boundary crossings when the current page fills. This append-only design ensures that every frame's metadata remains accessible for cross-attention regardless of window position.

### Eviction Strategy

Only patch pages in the live window are eligible for recycling. Lines [29‑35](https://github.com/Robbyant/lingbot-map/blob/main/lingbot_map/layers/flashinfer_cache.py#L29-L35) implement the eviction logic: when the sliding window exceeds `sliding_window` frames, the oldest live-window patch page is returned to the free list. Special pages and scale pages are never evicted, guaranteeing that metadata and initial context frames remain available for the attention mechanism.

## Attention Computation Workflow

### Planning and Execution

The manager optimizes attention computation through a plan-once, reuse-many strategy. For the first layer of a frame (`block_idx == 0`), the system **plans** the visible page table by concatenating `scale → window → special` pages and calculates the length of the final (potentially partially-filled) page (lines [86‑94](https://github.com/Robbyant/lingbot-map/blob/main/lingbot_map/layers/flashinfer_cache.py#L86-L94)).

All subsequent layers **run** the same execution plan, reusing the cached page IDs without recomputing the table (lines [97‑104](https://github.com/Robbyant/lingbot-map/blob/main/lingbot_map/layers/flashinfer_cache.py#L97-L104)). This amortizes the planning overhead across all transformer blocks in the layer stack.

### FP32 Fallback Mode

For numerical validation, the manager supports a reference implementation. When `force_fp32` is enabled, the system gathers K/V tensors into dense memory and applies PyTorch's `scaled_dot_product_attention` (lines [72‑84](https://github.com/Robbyant/lingbot-map/blob/main/lingbot_map/layers/flashinfer_cache.py#L72-L84)). This path sacrifices performance for bit-exact accuracy comparisons against the optimized FlashInfer kernels.

## Practical Usage Example

The following pattern demonstrates the canonical workflow for managing video sequences, mirroring the sanity-check routine found in the source (lines [72‑86](https://github.com/Robbyant/lingbot-map/blob/main/lingbot_map/layers/flashinfer_cache.py#L72-L86)):

```python
import torch
from lingbot_map.layers.flashinfer_cache import FlashInferKVCacheManager

device = torch.device("cuda" if torch.cuda.is_available() else "cpu")

# Initialize manager for 2 transformer layers

mgr = FlashInferKVCacheManager(
    num_blocks=2,
    max_num_frames=88,           # scale + window + headroom

    tokens_per_frame=262,        # 256 patches + 6 specials

    num_heads=16,
    head_dim=64,
    dtype=torch.bfloat16,
    device=device,
)

# Append a new frame (K/V shape: [tokens_per_frame, H, D])

k = torch.randn(262, 16, 64, dtype=torch.bfloat16, device=device)
v = torch.randn(262, 16, 64, dtype=torch.bfloat16, device=device)
mgr.append_frame(block_idx=0, k=k, v=v)

# Evict old frames to maintain sliding window

mgr.evict_frames(block_idx=0, scale_frames=8, sliding_window=64)

# Compute attention (plan is built automatically on first call)

Q = torch.randn(262, 16, 64, dtype=torch.bfloat16, device=device)
out = mgr.compute_attention(block_idx=0, q=Q)

# Reset for new video sequence

mgr.reset()

```

## Summary

- **Two-stream architecture** separates recyclable patch tokens (visual data) from append-only special tokens (metadata) to optimize memory usage for video sequences.
- **Unified physical layout** stores both streams in a single 5-D tensor `[max_num_pages, 2, page_size, H, D]` with contiguous page ranges for each stream.
- **Intelligent eviction** recycles only live-window patch pages while preserving scale frames and all special tokens, ensuring metadata persistence.
- **Plan-once optimization** computes the page table during the first layer execution and reuses it for subsequent layers, reducing CPU overhead.
- **O(1) allocation** through pre-allocated page pools eliminates runtime memory allocation latency during video playback.

## Frequently Asked Questions

### What is the purpose of splitting the KV cache into two streams?

The split allows the cache to apply different memory management policies to different token types. Patch tokens representing visual content can be safely evicted when they slide out of the attention window, while special tokens containing camera parameters and register embeddings must remain accessible for all frames. This design reduces memory pressure without losing critical metadata.

### How does the sliding window eviction policy work?

The manager maintains two deques for patch pages: a scale deque (permanent) and a live-window deque (temporary). When the number of frames exceeds `scale_frames + sliding_window`, the oldest page from the live-window deque is returned to the free list. This operation occurs in constant time and does not affect special tokens or scale frames.

### Why are special tokens stored in an append-only pool?

Special tokens are required for cross-frame attention calculations regardless of temporal distance. By storing them in an append-only pool, the manager guarantees that metadata for any historical frame remains addressable without complex remapping logic. This simplifies the attention kernel implementation and ensures consistent performance as video length increases.

### When should I use the force_fp32 fallback mode?

Enable `force_fp32` during model validation or debugging when you need bit-exact numerical agreement with a reference PyTorch implementation. This mode bypasses the optimized FlashInfer kernels and uses standard `scaled_dot_product_attention` on gathered dense tensors, trading performance for numerical accuracy verification.