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

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 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 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) 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.

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:

# 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,
)

# 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

# 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 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, lingbot_map/layers/attention.py, and 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 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 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.

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