# How Paged KV Cache Attention Enables ~20 FPS Streaming Inference in LingBot-Map

> Discover how paged KV cache attention in LingBot-Map delivers ~20 FPS streaming inference by optimizing attention cost for longer videos.

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

---

**Paged KV cache attention achieves ~20 FPS in LingBot-Map by using a two-stream cache with sliding-window eviction and FlashInfer's paged kernel to maintain constant-time attention cost regardless of video length.**

LingBot-Map processes continuous video streams through a Vision Transformer architecture, where standard self-attention creates a computational bottleneck by requiring full key/value matrix recomputation for every frame. The repository solves this challenge by implementing **paged KV cache attention**, a memory-efficient mechanism that bounds per-frame cost to achieve real-time streaming performance.

## Core Architecture Components

The `FlashInferAttention` and `FlashInferKVCacheManager` classes in [`lingbot_map/layers/flashinfer_cache.py`](https://github.com/Robbyant/lingbot-map/blob/main/lingbot_map/layers/flashinfer_cache.py) implement three key innovations that together deliver the ~20 FPS throughput.

### Two-Stream KV Cache Design

The cache separates tokens into two distinct streams to optimize memory usage. In `FlashInferKVCacheManager.__init__`, the system allocates separate page pools for **patch tokens** (spatial visual features that can be recycled) and **special tokens** (camera embeddings, register tokens, and scale indicators that must persist indefinitely).

This design ensures that non-essential visual data can be evicted while critical metadata remains resident. The patch stream uses dynamic page allocation, while the special stream receives static slots that never participate in eviction cycles.

### Sliding-Window Eviction Strategy

To prevent unbounded memory growth during streaming, the system implements aggressive eviction in `FlashInferKVCacheManager.evict_frames`. Only the most recent `sliding_window` frames (default 64) plus a fixed set of `scale_frames` (default 8) remain in the patch cache.

The `_apply_kv_cache_eviction_causal` method in [`lingbot_map/layers/attention.py`](https://github.com/Robbyant/lingbot-map/blob/main/lingbot_map/layers/attention.py) coordinates this process by identifying pages outside the temporal window and marking them for recycling. This maintains a constant upper bound on KV cache size, ensuring that attention computation never scales with total video duration.

### FlashInfer Paged-Kernel Integration

The `BatchPrefillWithPagedKVCacheWrapper` kernel from FlashInfer enables direct reading from paged storage without materializing dense KV matrices. In `FlashInferKVCacheManager.compute_attention`, the system builds a **visible page table** once per frame step, then launches a single kernel via `prefill_wrapper.run`.

This eliminates the O(N²) memory traffic of classic attention implementations. The kernel operates directly on FP16/BF16 data in the page pool, fusing attention softmax and dropout operations into a single GPU dispatch.

## Step-by-Step Streaming Inference

The streaming pipeline in `FlashInferBlock.forward` ([`lingbot_map/layers/block.py`](https://github.com/Robbyant/lingbot-map/blob/main/lingbot_map/layers/block.py)) orchestrates the inference process. The following sequence maintains constant computational cost to achieve the ~20 FPS throughput:

1. **First Frame Initialization**: During the initial forward pass with `num_frames > 1`, `FlashInferAttention.prepare_qkv` extracts query, key, and value tensors, applies optional RoPE, and formats them as `[tokens_per_frame, heads, dim]`. The manager stores these via `append_frame` in separate patch and special pages.

2. **Frame Appending**: For streaming steps (`num_frames == 1`), the current frame's K/V tensors are appended to the cache through `manager.append_frame`. The system writes patch tokens to recyclable pages and special tokens to protected slots.

3. **Eviction Execution**: Immediately after appending, `manager.evict_frames` recycles pages outside the sliding window. This keeps the total page count fixed at approximately 72 patch pages plus special pages, regardless of stream duration.

4. **Paged Attention Computation**: The query from the current frame is processed by `manager.compute_attention`, which assembles the visible page table (scale pages + window pages + special pages) and invokes the FlashInfer kernel. This attends over all relevant history without copying data to contiguous memory.

5. **Constant-Time Guarantee**: Because the page table size is fixed, memory bandwidth and compute remain constant per frame, enabling the ~20 FPS sustained throughput reported in [`benchmark/lingbot_map.py`](https://github.com/Robbyant/lingbot-map/blob/main/benchmark/lingbot_map.py).

## Performance vs. Naïve Dense Caching

The paged approach fundamentally differs from traditional dense KV caching. Key distinctions include memory allocation patterns and computational complexity:

- **Memory Allocation**: Dense caches reallocate full KV matrices each frame, causing size to grow linearly with video length. The paged cache reuses pre-allocated pages, writing only new patch tokens.
- **Bandwidth Utilization**: Standard implementations suffer linearly increasing memory traffic and GPU pressure. The paged system maintains constant traffic by reading only the fixed window of pages.
- **Synchronization Overhead**: Dense approaches require CPU-GPU synchronization for each frame. The FlashInfer kernel executes entirely on the GPU without host synchronization.
- **Latency Characteristics**: Traditional methods are dominated by copy and softmax operations. The fused kernel reduces latency by approximately 2×, achieving the target ~20 FPS throughput.

## Implementation Examples

The following code examples demonstrate how to initialize the paged KV cache manager and execute streaming inference steps. These patterns mirror the implementation found in [`lingbot_map/aggregator/stream.py`](https://github.com/Robbyant/lingbot-map/blob/main/lingbot_map/aggregator/stream.py):

```python

# Initialize the paged KV manager (once per model)

from lingbot_map.layers.flashinfer_cache import FlashInferKVCacheManager
import torch

device = torch.device("cuda")
kv_manager = FlashInferKVCacheManager(
    num_blocks=12,
    max_num_frames=88,
    tokens_per_frame=262,  # 256 patches + 6 specials

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

```

```python

# First pass: populate cache with multiple frames

def first_pass(x, pos):
    attn = FlashInferAttention(
        dim=768, num_heads=8, rope=None,
        kv_cache_sliding_window=64,
        kv_cache_scale_frames=8,
    )
    # x shape: [B, N, C] where N = tokens_per_frame

    out = attn(x, pos=pos, num_frames=5, kv_cache=kv_manager, global_idx=0)
    return out

```

```python

# Streaming inference: single-frame mode with constant cost

def streaming_step(x, pos):
    attn = FlashInferAttention(
        dim=768, num_heads=8, rope=None,
        kv_cache_sliding_window=64,
        kv_cache_scale_frames=8,
    )
    # Reuses existing kv_manager; appends, evicts, and computes

    out = attn(x, pos=pos, num_frames=1, kv_cache=kv_manager, global_idx=0)
    return out

```

The `FlashInferBlock` class in [`lingbot_map/layers/block.py`](https://github.com/Robbyant/lingbot-map/blob/main/lingbot_map/layers/block.py) compiles these operations into CUDA graphs for additional optimization, handling the `skip-append` path for non-key frames to minimize redundant writes.

## Summary

- **Paged KV cache attention** in LingBot-Map uses separate streams for patch and special tokens, with sliding-window eviction to bound memory usage.
- The `FlashInferKVCacheManager` class maintains fixed-size page pools, recycling old frames while preserving critical scale and special tokens.
- FlashInfer's `BatchPrefillWithPagedKVCacheWrapper` kernel reads directly from paged storage, eliminating O(N²) memory materialization and CPU-GPU synchronization.
- This architecture keeps per-frame attention cost constant at O(patch_pages × heads × dim), enabling sustained **~20 FPS streaming inference** regardless of video length.
- Key implementation files include [`lingbot_map/layers/flashinfer_cache.py`](https://github.com/Robbyant/lingbot-map/blob/main/lingbot_map/layers/flashinfer_cache.py), [`lingbot_map/layers/attention.py`](https://github.com/Robbyant/lingbot-map/blob/main/lingbot_map/layers/attention.py), and [`lingbot_map/layers/block.py`](https://github.com/Robbyant/lingbot-map/blob/main/lingbot_map/layers/block.py).

## Frequently Asked Questions

### How does the sliding window eviction affect model accuracy?

The sliding window retains the most recent 64 frames plus 8 fixed scale frames, which provides sufficient temporal context for video understanding tasks. According to the implementation in `FlashInferKVCacheManager.evict_frames`, special tokens (camera embeddings, registers) are never evicted, preserving critical metadata. The design assumes that visual information beyond the 64-frame window contributes diminishing returns for real-time navigation tasks.

### What hardware requirements are needed to achieve 20 FPS?

The benchmark in [`benchmark/lingbot_map.py`](https://github.com/Robbyant/lingbot-map/blob/main/benchmark/lingbot_map.py) targets modern NVIDIA GPUs with FlashInfer support. The system uses **FP16/BF16** precision to maximize tensor throughput. While the code runs on any CUDA-capable device, the ~20 FPS figure assumes sufficient GPU memory to hold the page pools (approximately 12 transformer blocks with 88 max frames) and compute capacity to execute the fused attention kernel efficiently.

### Can the cache size parameters be tuned for different latency requirements?

Yes. The `sliding_window` (default 64) and `scale_frames` (default 8) parameters in `FlashInferKVCacheManager.__init__` control the memory-computation trade-off. Reducing `sliding_window` decreases the attention context and memory bandwidth, potentially increasing FPS at the cost of temporal coherence. Conversely, increasing these values expands context but requires more GPU memory and compute per frame.

### How does paged attention differ from standard transformer KV caching?

Standard caching materializes dense KV matrices that grow linearly with sequence length, requiring O(N²) memory traffic for attention computation. The paged approach in [`lingbot_map/layers/flashinfer_cache.py`](https://github.com/Robbyant/lingbot-map/blob/main/lingbot_map/layers/flashinfer_cache.py) stores K/V tensors in fixed-size pages and uses the FlashInfer kernel to index them sparsely. This yields constant-time per-frame cost regardless of stream duration, whereas naïve implementations slow down as videos grow longer.