🤖 machine learning

ProtoKV: Streaming Video Understanding under Delayed Query with Summary-State Memory

ProtoKV is a streaming video understanding framework that addresses the challenge of delayed queries by maintaining a constant memory footprint through a hybrid approach of exact near-window KV caching and a fixed-capacity summary-state memory for historical content, thereby significantly improving accuracy over token-retention baselines as query delays increase.

Original authors: Le Tu Ngoc Minh (KAIST), Jinyeong Lim (KAIST), Dongsu Han (KAIST)

Published 2026-06-26

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Le Tu Ngoc Minh (KAIST), Jinyeong Lim (KAIST), Dongsu Han (KAIST)

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are watching a very long, continuous video stream, like a 24-hour security camera feed. Your job is to answer questions about what happened in that video. The problem? You have a tiny brain (limited computer memory) and you can't pause the video to rewind and re-watch everything. You have to keep watching while waiting for someone to ask you a question, which might come minutes or even hours after a specific event happened.

This is the challenge of Streaming Video Understanding.

The Problem: The "Forgetting" Brain

Most current systems try to solve this by keeping a "sliding window" of the last few minutes of video in their memory.

The Analogy: Imagine you are holding a bucket of water (your memory). As new water (video frames) flows in, you have to let old water out to keep the bucket from overflowing.
The Flaw: If a crucial event happens (like a thief stealing a wallet) and then 20 minutes of boring footage follow before someone asks, "Did you see the thief?", the old water (the thief) has already been dumped out of the bucket. The system forgets the answer.

Other systems try to keep a list of "important moments" (tokens) they saved. But if the video is long, they have to constantly decide which saved moments to throw away to make room for new ones. If they throw away the wrong moment, the answer is lost forever.

The Solution: ProtoKV (The "Summary Notebook")

The authors propose a new system called ProtoKV. Instead of trying to save every single frame or just a few specific moments, ProtoKV uses a two-part memory system that acts like a smart notebook.

1. The "Recent Past" (The Exact Window)

For the most recent part of the video (say, the last few minutes), ProtoKV keeps a perfect, high-definition copy of everything.

Analogy: This is like having a clear, high-resolution photo of what happened in the last 5 minutes. If you ask a question about right now, the answer is right there, crystal clear.

2. The "Distant Past" (The Prototype Bank)

For everything that happened before that recent window, ProtoKV stops saving individual frames. Instead, it creates summaries.

The Analogy: Imagine you are watching a parade. You don't remember every single person's face from 2 hours ago. Instead, you remember: "There was a marching band," "There was a float with a giant cat," and "There was a group of people in red shirts."
How it works: ProtoKV groups similar things together into "Prototypes."
- If a person is walking, ProtoKV creates a "Walking Person" summary.
- If that person walks for 10 minutes, the system doesn't save 10 minutes of video. It just updates the "Walking Person" summary to say, "This person has been walking for a long time."
- It also keeps a "residual" note: "Most of the time, the person was walking normally, but occasionally they waved." This captures the variety without saving every single step.

The Magic Trick: The "Ghost Token"

When a question finally arrives (e.g., "What did the person in the red shirt do 30 minutes ago?"), the system needs to feed this information to the AI model. But the model expects to see actual video frames, not just a summary.

ProtoKV uses a clever trick called Pseudo-Tokens.

The Analogy: Imagine you have a summary note that says "Giant Cat Float." To show this to the AI, ProtoKV creates a few "ghost" video frames that look like the Giant Cat Float based on the summary notes.
These ghosts aren't real frames; they are mathematical reconstructions of the summary. The AI model sees these ghosts and treats them just like real video frames.
Crucially, the system counts how many real moments went into that summary. If the "Giant Cat Float" summary was built from 500 real seconds of video, the system tells the AI, "This ghost represents 500 seconds of evidence," so the AI pays more attention to it.

Why This is Better

The paper claims that ProtoKV is much better at answering questions about things that happened a long time ago (high "delay") compared to other methods.

Old Method (Sliding Window): If the event happened 30 minutes ago, the system has already deleted it. Accuracy drops to zero.
Old Method (Token Retention): The system tried to save specific moments, but it had to delete some to make room for new ones. It might have deleted the exact moment the thief appeared.
ProtoKV: It never deletes the concept of the event. It just compresses it into a summary. Even after 30 minutes of new video, the "Thief" summary is still there, updated with new details, ready to be turned back into a "ghost" frame for the AI to answer the question.

The Results

The authors tested this on several video benchmarks. They found that:

Accuracy: ProtoKV got significantly higher scores (up to 12.5 points better) on questions about events that happened a long time ago.
Stability: As the time gap between the event and the question grew, ProtoKV's performance stayed steady, while other methods crashed.
Speed: It answers questions just as fast as the other methods because the "summary" is small and fits easily into the computer's memory, so it doesn't slow down the system.

In short, ProtoKV solves the problem of "forgetting" by stopping the attempt to remember every single detail and instead remembering the story of what happened, allowing it to answer questions about the distant past without needing a super-computer's memory.

Technical Summary: ProtoKV

Problem Statement

Streaming Video Understanding (SVU) requires systems to process continuous video streams and answer asynchronous queries in real-time under strict GPU memory and latency constraints. A critical challenge in this setting is delayed query: decisive visual cues may appear briefly and early in a stream, but the query arrives significantly later after many subsequent frames have been processed.

Under bounded memory, standard approaches face a dilemma:

Sliding Window (SWA): Retains only recent tokens, guaranteeing constant memory but irretrievably losing evidence once it exits the window.
Token Retention/Compression: Attempts to keep a subset of historical tokens. However, as the delay ( $\Delta$ ) between evidence and query grows, these methods suffer from "post-evidence update pressure." Decisive cues are often evicted or diluted because the system must make query-agnostic retention decisions without knowing which future tokens will be relevant. Once a specific token instance is dropped, its associated fine-grained cue is lost.

The paper argues that representing far history as a set of retained token instances is brittle under long delays. Instead, the system needs a mechanism that preserves the evidence of past events rather than the specific token instances, allowing for graceful degradation as the delay increases.

Methodology: ProtoKV

ProtoKV is a constant-footprint memory mechanism designed for streaming video LLMs. It shifts the representation of far history from token retention to a summary-state approach using a two-tier online state:

1. Two-Tier Architecture

Near Window (Exact): A ring buffer ( $B_{near}$ ) storing the exact Key-Value (KV) pairs for the most recent $W$ frames. This preserves fine-grained, temporally local evidence without approximation.
Far Memory (Summary State): A fixed-capacity prototype bank ( $B_{far}$ ) of size $K_{max}$ that aggregates older, evicted history. Instead of storing token instances, it stores object-centric prototypes.

2. Online Update Mechanism

As the video stream progresses, tokens are evicted from the near window and absorbed into the far memory via a continuity-aware assignment:

Assignment: Evicted tokens are assigned to a prototype $k$ $k$ by minimizing an online cost function that combines:
- Key-space similarity (clustering tokens with similar keys).
- Spatial continuity (enforcing track-consistent association using spatial coordinates).
- Staleness control (discouraging assignment to prototypes that have not been updated recently).
Prototype Update: Once assigned, the prototype is updated as a persistent summary state:
- Centers: Key and value centers ( $c_k, p_k$ ) are updated via Exponential Moving Average (EMA).
- Mass: A counter ( $n_k$ ) tracks the number of absorbed tokens.
- Residual Statistics: To prevent the loss of distinctive cues through simple averaging, ProtoKV maintains Product Quantization (PQ)-based histograms of the residuals ( $r_K = K - c_k$ , $r_V = V - p_k$ ). This captures intra-prototype diversity without storing individual token codes.
- Maintenance: The bank undergoes lightweight maintenance, including mass decay for idle prototypes, merging of redundant prototypes, and recycling of empty slots.

3. Query-Time Interface: Pseudo-Token Synthesis

At query time, ProtoKV exposes the far memory to the standard attention mechanism without architectural changes:

Pseudo-Tokens: Each prototype is synthesized into $S$ pseudo-KV tokens. These are constructed by combining the prototype's center with representative residual patterns decoded from the stored PQ histograms.
Mass-Aware Bias: To account for the multiplicity of tokens summarized by a prototype, a log-mass bias ( $b_k = \log n_k$ ) is added to the attention logits. This ensures that prototypes representing more evidence exert a proportionally stronger influence.
Fixed Context: The final context consists of the exact near-window tokens plus the bounded number of pseudo-tokens ( $L_{context} = W + K_{max} \cdot S$ ), ensuring constant query-time latency and memory usage regardless of stream length.

Key Contributions

Far-Memory Mechanism: Introduction of a fixed-capacity, spatiotemporally consistent prototype bank augmented with residual statistics to summarize distant history, moving away from token-instance retention.
Pseudo-Token Synthesis: A training-free method to synthesize bounded pseudo-KV tokens with mass-aware weighting, enabling standard attention to access far-history evidence under a constant query-time footprint.
Delayed-Query Protocol: A retrospective-query filtering protocol to evaluate SVU robustness against increasing query delays while maintaining invariant ground truth.

Experimental Results

ProtoKV was evaluated on four streaming video benchmarks (RVS-Ego, RVS-Movie, OVO-Bench, StreamingBench) using LLaVA-OV-7B and Qwen2.5-VL-7B backbones.

Performance: Under matched memory budgets, ProtoKV outperforms sliding-window baselines and token-retention methods (e.g., InfiniPot-V). It achieves up to 12.5 percentage points higher accuracy than token-retention baselines in long-delay regimes.
Robustness to Delay: While all methods degrade as query delay ( $\Delta$ ) increases, ProtoKV exhibits significantly flatter degradation curves. The performance gap widens as $\Delta$ grows, demonstrating that the summary-state approach better preserves decisive cues under sustained post-evidence update pressure.
Efficiency: ProtoKV maintains competitive query-time Time-To-First-Token (TTFT) and lower end-to-end latency compared to offloading/retrieval-based baselines (e.g., ReKV), which suffer from retrieval overhead.
Offline Performance: When applied to offline video understanding benchmarks (VideoMME, MLVU), ProtoKV remains competitive with state-of-the-art compression methods, suggesting its utility extends beyond streaming scenarios.

Significance and Claims

The paper claims that ProtoKV addresses a fundamental limitation in streaming video understanding: the brittleness of token-retention strategies under long delays. By shifting from retaining specific token instances to maintaining a summary-state of far history, ProtoKV allows sparse, decisive cues to survive many subsequent updates without being overwritten or diluted.

The authors emphasize that this design is tailored for delayed queries where answers depend on past event occurrences rather than instantaneous visual content. The results suggest that for interactive systems requiring always-on, query-agnostic maintenance with fixed on-device footprints, representing far history as a compact, object-centric summary state is a more effective operating point than sliding windows or token selection. The work highlights the value of summary-state memory for stable streaming systems under sustained update pressure.