# How Paged KV Cache Attention Achieves Stable Inference in Ling-Bot-Map

> Discover how paged KV cache attention ensures stable inference for Ling-Bot-Map by recycling video tokens and maintaining constant memory use. Learn more.

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

---

**Paged KV cache attention achieves stable streaming inference by separating video tokens into a recyclable patch stream and an append-only special stream, maintaining constant memory usage and fixed tensor shapes regardless of video length.**

Ling-Bot-Map processes video streams frame-by-frame for LiDAR mapping, requiring a key-value (KV) cache that grows with each incoming frame. Without careful management, this leads to unbounded memory growth and numerical instability from variable attention mask shapes. The repository solves this using a **paged KV cache** implementation based on FlashInfer, which partitions the cache into two logical streams sharing a single physical page pool.

## Two-Stream Paged KV Cache Architecture

The `FlashInferKVCacheManager` in [`lingbot_map/layers/flashinfer_cache.py`](https://github.com/Robbyant/lingbot-map/blob/main/lingbot_map/layers/flashinfer_cache.py) manages memory through two distinct token streams that serve different purposes during video processing.

### Recyclable Patch Stream

The patch stream holds the 256 patch tokens generated for each video frame. These pages are allocated from a fixed-size pool and recycled when they fall outside the configured sliding window. When the window slides forward, evicted patch pages return to a free list without deallocating underlying GPU memory, ensuring **O(1) memory complexity** regardless of video duration.

### Append-Only Special Stream

The special stream preserves camera, register, and scale tokens—six per frame—that must persist across frames for geometric consistency. These pages are never evicted; new tokens append directly to the tail of the cache. This design ensures that critical camera parameters remain accessible to all future frames while the patch cache recycles obsolete visual features.

## Core Implementation Mechanics

Each transformer block owns a KV cache tensor of shape `[max_num_pages, 2, page_size, num_heads, head_dim]` in NHD layout, where dimension 1 distinguishes keys from values. Pages 0 through `max_patch_pages-1` store patch tokens, while remaining pages store special tokens.

### Frame Appending Without Dispatch Overhead

When processing a new frame, the `append_frame` method writes patch tokens to a free patch page and special tokens to the current tail special page using direct tensor slice assignment:

```python

# kv_caches[block_idx] has shape [max_num_pages, 2, page_size, num_heads, head_dim]

kv_caches[block_idx][page_id, 0] = k
kv_caches[block_idx][page_id, 1] = v

```

This approach avoids the expensive Python-to-C++/CUDA dispatch overhead of per-token appends, reducing latency jitter during streaming inference.

### Sliding-Window Eviction Strategy

After each append, the `evict_frames` method identifies patch pages outside the sliding window (default 64 frames) and moves their indices to a free list. The eviction is computationally cheap because it manipulates page metadata rather than copying or deallocating tensor data. The method optionally preserves special tokens in `kv_cache_cross_frame_special`, allowing evicted frames to retain camera and scale information for cross-frame attention.

### Cross-Frame Special Token Preservation

When `cross_frame_special=True`, the manager extracts special tokens from evicted frames into a dedicated buffer. This preserves access to historical camera parameters and scaling factors even after their associated visual patches are recycled, maintaining geometric stability for long sequences.

## Attention Computation and Numerical Stability

The `FlashInferAttention` layer in [`lingbot_map/layers/attention.py`](https://github.com/Robbyant/lingbot-map/blob/main/lingbot_map/layers/attention.py) transparently switches between batch processing and streaming modes, handling the KV cache lifecycle for each transformer block.

### Visible Page Table Construction

For streaming inference, the manager builds a **visible page table** via `build_visible_page_table` that concatenates scale pages, live window pages, and special pages in deterministic order. This guarantees that the FlashInfer kernel receives identically shaped inputs at every timestep, preventing numerical drift caused by padding variations or reallocation.

### Kernel Dispatch and Sequence Lengths

Streaming mode utilizes `BatchPrefillWithPagedKVCacheWrapper` from FlashInfer. The `compute_last_page_len` method calculates exactly how many tokens are valid in the final page, allowing the kernel to avoid out-of-bounds reads without expensive padding calculations. The last page length accounts for partial pages at the sequence tail, ensuring exact attention weights regardless of accumulated frame count.

## Eliminating Sources of Instability

Traditional dense KV caches suffer from four critical instability sources that the paged architecture resolves:

- **Unbounded Memory Growth**: Dense caches grow **O(N)** with sequence length, causing out-of-memory errors during long videos. The paged approach bounds memory to **O(1)** by recycling patch pages and maintaining a fixed pool size based on scale frames (8) plus sliding window (64) plus headroom.

- **Variable Sequence Lengths**: Standard attention requires re-padding for each new token length, introducing numerical differences between timesteps. The visible page table presents a fixed-shape layout to the kernel every frame.

- **High Dispatch Latency**: Per-token CUDA API calls create inconsistent timing and overhead. Direct tensor slice writes eliminate this dispatch cost entirely.

- **Loss of Geometric Context**: Evicting frames normally destroys camera parameter history. The special stream preservation ensures consistent geometric transforms persist across the entire video.

## Practical Implementation Examples

### Initializing the Cache Manager

Configure the manager with fixed page limits to establish memory bounds before processing begins:

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

device = torch.device("cuda" if torch.cuda.is_available() else "cpu")
mgr = FlashInferKVCacheManager(
    num_blocks=12,                # one per transformer block

    max_num_frames=88,            # scale (8) + window (64) + headroom (16)

    tokens_per_frame=262,         # 256 patches + 6 specials

    num_heads=16,
    head_dim=64,
    dtype=torch.bfloat16,
    device=device,
    num_special_tokens=6,
    scale_frames=8,
    sliding_window=64,
    max_total_frames=200,
)

```

This initialization matches the `__init__` implementation in [`flashinfer_cache.py`](https://github.com/Robbyant/lingbot-map/blob/main/flashinfer_cache.py) (lines 54-90).

### Appending Frames and Evicting Old Data

Process incoming frames while maintaining the sliding window constraint:

```python

# Generate sample KV tensors for one frame

k = torch.randn(262, 16, 64, dtype=torch.bfloat16, device=device)
v = torch.randn(262, 16, 64, dtype=torch.bfloat16, device=device)

block_idx = 0
mgr.append_frame(block_idx, k, v)

# Maintain window size and preserve special tokens

mgr.evict_frames(
    block_idx,
    scale_frames=8,
    sliding_window=64,
    cross_frame_special=True,
    include_scale_frames=True,
    camera_only=False,
)

```

The `append_frame` method (lines 102-120) handles page allocation, while `evict_frames` (lines 129-155) manages the recycling logic.

### Computing Streaming Attention

Integrate the cache manager with the attention layer for frame processing:

```python
from lingbot_map.layers.attention import FlashInferAttention

attention = FlashInferAttention(
    dim=1024,
    num_heads=16,
    rope=None,
    kv_cache_sliding_window=64,
    kv_cache_scale_frames=8,
)

# Query tensor for current frame

q = torch.randn(1, 262, 1024, dtype=torch.bfloat16, device=device)

out = attention(
    x=q,
    kv_cache=mgr,            # Pass manager as kv_cache

    num_frames=1,            # Streaming mode

    global_idx=0,
)

```

The streaming branch begins at line 68 of [`attention.py`](https://github.com/Robbyant/lingbot-map/blob/main/attention.py), invoking `build_visible_page_table` and `compute_last_page_len` before calling FlashInfer.

### Resetting for New Sequences

Clear per-block state between videos without reallocating GPU memory:

```python
mgr.reset()   # Clears free lists and frame counters

```

The `reset` method (lines 224-233) prepares the manager for a fresh sequence while preserving the allocated page buffer.

## Summary

- **Paged KV cache attention** in Ling-Bot-Map uses a two-stream architecture: recyclable patch pages for visual tokens and append-only special pages for camera parameters.
- **Constant memory usage** is achieved through sliding-window eviction that recycles patch pages without deallocation, bounding memory to the scale size plus window size regardless of video length.
- **Numerical stability** stems from fixed-shape page tables passed to FlashInfer kernels, eliminating variable-sequence-length padding and Python dispatch overhead.
- **Cross-frame consistency** is preserved by optionally retaining special tokens (camera, scale, register) even when their associated patch pages are evicted.
- **Direct tensor operations** replace per-token CUDA API calls, reducing latency jitter in streaming scenarios.

## Frequently Asked Questions

### What distinguishes patch tokens from special tokens in the KV cache?

Patch tokens represent the 256 visual features extracted from each video frame and belong to the recyclable stream. Special tokens consist of camera parameters, register embeddings, and scale factors—six per frame—that provide geometric context. According to the implementation in [`flashinfer_cache.py`](https://github.com/Robbyant/lingbot-map/blob/main/flashinfer_cache.py), special tokens reside in an append-only stream to ensure camera history remains accessible throughout the video, while patch tokens recycle through the fixed-size page pool.

### How does the sliding window prevent memory exhaustion during long videos?

The sliding window limits active patch pages to a fixed number (default 64) plus scale frames (8). When `evict_frames` detects pages outside this window, it moves their indices to a free list without deallocating underlying storage. This recycling mechanism ensures that processing a 10,000-frame video uses the same GPU memory as processing a 100-frame video, achieving true **O(1)** memory complexity.

### Why does direct tensor slicing improve stability compared to per-token KV cache updates?

Per-token appends invoke separate Python-to-C++/CUDA dispatch operations for each token, introducing variable overhead and potential timing jitter that can affect numerical consistency in streaming pipelines. The Ling-Bot-Map implementation writes entire pages via direct tensor slice assignment (`kv_caches[block_idx][page_id, ...]`), which executes as a single CUDA kernel launch. This eliminates dispatch overhead and ensures deterministic latency for each frame.

### When should I use batch mode versus streaming mode in FlashInferAttention?

Use **batch mode** (which falls back to `torch.nn.functional.scaled_dot_product_attention`) when processing complete, pre-recorded videos with known sequence lengths where the entire KV cache fits in memory simultaneously. Use **streaming mode** with the `FlashInferKVCacheManager` when processing live video streams or very long sequences where memory must remain bounded. The `FlashInferAttention.forward` method automatically selects the appropriate backend based on the `num_frames` parameter and presence of a paged cache manager.