acceptodds
Under review as a conference paper at ICLR 2027

Structure-Preserving Visual Token Compression for Streaming Video Understanding via Bilateral Grid Splatting

Abstract

Streaming video understanding requires Video MLLMs to process incoming frames in real time, but rapidly accumulating visual tokens incur a severe computational bottleneck. Visual token compression offers a remedy, yet existing methods fall short in the streaming on two fronts: the unbounded frame stream forces aggressive compression under which their accuracy collapses, and they require a temporal boundary prior unavailable in the streaming setting. To bridge this gap, we propose BGStream, a training-free compression method based on the bilateral grid that 1) preserves the semantic structure of visual features even under aggressive retention ratios, and 2) splats each incoming frame's tokens into the grid on the fly, without accessing the full video. However, since generalizing the bilateral grid to visual tokens is non-trivial, we ground this design in a theoretical analysis based on the Johnson–Lindenstrauss lemma. On StreamingBench and OVO-Bench, BGStream outperforms prior compression methods while remaining compatible with KV cache optimization.

Primary area:
applications to computer vision, audio, language, and other modalities
Keywords:
Streaming Video Understanding, Visual Token Compression, Bilateral Grid

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_d9XXOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes BGStream, a training-free token compression method for streaming video MLLMs. Visual features are randomly projected to 4-D keys, and tokens in the same cell are averaged. Each grid covers 32 frames. A FIFO buffer keeps salient tokens from the last 5 frames, and a Johnson–Lindenstrauss analysis is given for the projection. At about 5% retention, BGStream outperforms seven compression baselines on StreamingBench and OVO-Bench. The authors claim that it preserves the structure under aggressive compression and is complementary to KV-cache methods.

Critical strengths
  1. The splatting is additive and does not need the full video, so it fits streaming. The compression step itself is also cheap, which makes the method practical.
  2. At about 5% retention, BGStream outperforms seven compression baselines on three backbones, and it still leads when the token count is matched for each query. This strong result is the main reason for my positive rating.
Critical weaknesses
  1. In Table 15, FIFO-only already outperforms every compression baseline in Tables 1 and 2. It gets 67.96 against 65.84 on StreamingBench and 53.76 against 48.84 on OVO-Bench. The grid only adds 0.64 and 0.82 points, so its own gain is small. Since the grid is the main contribution, this is an important concern.
  2. Theorem B.6 needs Δ>τ_grid+2R. Since Δ≤D+2R always holds, τ_grid must be below D. However, the only τ_grid construction in Appendix B.2 gives more than 2D at N=6272, d_s=4 and s_r=1/3. The purity guarantee is therefore not shown to hold in the actual setting. This weakens the theoretical contribution of the paper.
Questions for authors
  1. How were the baselines changed from their default configurations in Appendix D.3 to reach 5% retention, and can they be given the same FIFO buffer?
  2. Since Appendix D.3 removes spatial partitioning, the grid becomes a 4-D random projection with 3 bins per axis plus averaging. This is closer to random-projection hashing than to a bilateral grid. Can it be compared with k-means at the same cell count, and how are position ids assigned to grid tokens?
  3. In Tables 1, 2 and 14, the KV-cache combinations are slower and less accurate than BGStream alone. What is the KV memory of BGStream alone?
  4. Is the 524 ms encoder cost in Table 18 paid at query time, and what does ReKV's 13 s latency include?
4 comments
AuthorsOpenReview ↗

Response to Reviewer d9XX (1/N)

W1/Q1. The gain over FIFO-only and the baseline setup

We agree that the gain over FIFO-only in Table 15 (in the revised manuscript, Table 16) is modest, and we address this in two steps: first the baseline configuration behind Tables 1 and 2, then where the benefit of the grid shows. Regarding the configuration in Appendix D.3, the baselines follow the hyperparameters of their original papers, with only the retention ratio set to 5% to match BGStream, and they do not use a FIFO buffer.

As for whether the baselines can be given the same FIFO buffer, yes: we gave each baseline the same FIFO buffer and the same retention ratio as BGStream, so that only the compression of past frames differs. For this comparison, we use the baselines that, like BGStream, require no temporal boundary prior and are thus applicable in the streaming setting (VisionZip, ToMe, and StreamingTOM). As shown in the table below, with the FIFO buffer the baselines reach the level of FIFO-only: VisionZip and ToMe do not improve over it on OVO-Bench, StreamingTOM improves slightly, and BGStream gives the largest gain on both benchmarks. We have clarified the baseline configuration in Appendix D.3, added this comparison to Appendix D.12, and referred to it in Section 5.2.

Compression of past framesStreamingBenchOVO-Bench
VisionZip67.6953.08
ToMe68.3351.64
StreamingTOM68.2554.10
Bilateral grid (BGStream)68.6054.58

We would also like to reiterate our main contribution: a grid that operates without a temporal prior, remains effective under aggressive retention ratios, and removes temporal redundancy as a by-product of splatting (Section 4.2). Since most questions in these benchmarks concern the recent context, the grid's gain is small in overall accuracy; it is consistent, however, in the comparison above, and it is on the tasks that require past frames (Backward Tracing in Table 2, offline benchmarks in Appendix D.8) that the role of the grid becomes visible.


W2. Theorem B.6

We agree that the explicit construction at the bottom of page 26 in Appendix B.2, τgrid=srD2log⁡ ⁣(2N(N−1)dsδ),\tau_{\mathrm{grid}} = s_rD\sqrt{2\log\!\left(\frac{2N(N-1)d_s}{\delta}\right)}, satisfies the grid-width probability constraint in Eq. (23) but is too conservative to simultaneously satisfy the geometric separation condition of Theorem B.6 under our default configuration. This construction was intended to establish the existence of a deterministic bound satisfying Eq. (23), rather than the joint feasibility of all the theorem's conditions, and the proof of Theorem B.6 does not depend on it.

A sharper, realization-wise criterion follows from Lemma B.5 and Eq. (26): for a fixed projection PP, every non-empty grid cell is pure whenever ΔP>2RP+sr∥W(P)∥2,\Delta_P > 2R_P + s_r\|W(P)\|_2, where ΔP\Delta_P and RPR_P denote the minimum inter-cluster center distance and the maximum within-cluster radius after projection, respectively. Cross-cluster points are separated by at least ΔP−2RP\Delta_P - 2R_P, whereas points sharing a cell are at most sr∥W(P)∥2s_r\|W(P)\|_2 apart by Lemma B.5, so this condition rules out cross-cluster collisions. However, even this criterion does not hold on our features [ΔP−2RP=X\Delta_P - 2R_P = X vs. sr∥W(P)∥2=Ys_r\|W(P)\|_2 = Y], which is consistent with the purity below 1 in Table 5. The difficulty is therefore not specific to the construction: Theorem B.6 does not certify our default configuration, and neither does Theorem B.8, which relies on the same separation condition (Eq. 28).

We nevertheless believe the conditional results retain their theoretical value. Theorem B.6 identifies sufficient conditions linking grid width, cluster separation, and within-cluster drift to the absence of cross-cluster collisions, and Appendix B.3 characterizes how such contamination affects the aggregate SNR and representation error under its stated assumptions.

AuthorsOpenReview ↗

Response to Reviewer d9XX (N/N)

Q2. Relation to hashing, k-means, position ids

We agree that, with spatial partitioning removed, our routing step, a Gaussian projection followed by per-axis quantization, is closely related to random-projection hashing [1]. At the same time, we view this routing step as one component of a broader framework: the bilateral grid assigns each token to a cell, accumulates it into a homogeneous (sum, count) pair, and summarizes each cell into one representative token, so that frames are incorporated as they arrive and grids can be merged under a token budget (Appendix C.2). Within this framework, the routing step can be instantiated in several ways, such as PCA that gives comparable accuracy at about 70× the projection time (Table 18 in the revised manuscript). The k-means comparison suggested by the reviewer fits naturally into this view as another routing: at the same cell count, it is comparable on StreamingBench and 1.7 points lower on OVO-Bench, and its compression takes 2.87 s per query versus 95.4 ms for the grid, since it fits clusters iteratively over all features of a group. The framework thus accommodates different routings, and we use the random projection because it is the simplest one that keeps the framework single-pass and additive in a stream. Regarding position ids, grid tokens follow the flattened cell-index order within chronologically ordered groups, followed by the FIFO tokens, and the LLM assigns consecutive positions to this sequence; original patch indices and timestamps are not used as position ids.

[1] Locality-sensitive hashing scheme based on p-stable distributions, Datar et al., ACM’24


Q3. KV memory

BGStream alone requires 0.03 GiB of KV cache on StreamingBench and OVO-Bench, essentially the same as the combination in Table 14 (in the revised manuscript, Table 15). We would like to explain why we nevertheless report the combination. BGStream and KV-cache methods bound different things: BGStream reduces the tokens that enter the LLM, and its token budget BB caps the context, which at BB = 18,000 corresponds to about 1 GiB of KV cache. On the other hand, a KV-cache method caps memory at a chosen budget independent of BB, by offloading or evicting entries rather than merging them. The combination is intended for long streams under such a memory cap, where it keeps the KV-cache method's bound while being much faster than that method alone (Tables 1, 2 and 15). However, the benchmark videos are far shorter than the point at which either bound binds, so at these lengths BGStream alone and the combination use the same memory and the combination only pays the overhead of the KV-cache method, as the reviewer observed.

We have revised the paper accordingly: Sections 2 and 5.2 and Appendix A.1 now describe KV-cache optimization as compatible with BGStream rather than as complementary in general, and Appendix D.11 reports the KV memory of BGStream alone in Table 15 together with a short explanation of why it matches the combination at these stream lengths.


Q4. Latency

Yes. In our measurement protocol, all frames up to the query are encoded when the query is issued, so the 524 ms in Table 18 (in the revised manuscript, Table 21) is the visual encoder and adaptor cost over the full prefix, and it is included in the per-query latency of every method (in deployment, this cost is paid as frames arrive). Similarly, ReKV's 13 s includes the same encoder and adaptor cost. The remaining time comes from two sources. First, all visual tokens pass through the LLM to build the KV cache, so the attention cost grows quadratically with the number of visual tokens. Second, the past KV entries are offloaded, and the query-relevant ones are loaded back to GPU memory at query time. BGStream avoids both by reducing the visual tokens before they enter the LLM, which is where its latency advantage comes from.

We have clarified the measurement protocol and this breakdown in Appendix D.14.

Thank you for the response and new experiments. Although the margin over baselines with the same FIFO buffer is modest and Theorem B.6 does not certify the default setting, BGStream remains fast and still leads in the controlled comparisons, so I will keep my score of 3.

We sincerely appreciate your valuable feedback and your engagement in the discussion, both of which have helped us further improve our paper.

Reviewer_7TmLOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes BGStream, a training-free visual token compression method for streaming video understanding. It uses low-dimensional random projections to route visual tokens into a bilateral grid, merges tokens within each cell, and retains recent-frame tokens through a FIFO buffer. The method is supported by a JL-based theoretical analysis and evaluated across multiple video-understanding benchmarks and model backbones. Experimental results on a series of streaming video understanding benchmarks show its advantage in comparison to existing methods.

Critical strengths
  • The paper addresses a valuable problem: reducing the computational cost of continuously accumulating visual tokens in streaming video understanding.
  • The method has a theoretical foundation, with explicit assumptions connecting random projection, grid-cell purity, and aggregation error.
  • The evaluation is extensive, using widely adopted benchmarks, multiple backbones, efficiency measurements, and ablations covering key design choices.
Critical weaknesses
  • The benefit specific to bilateral grid compression is not fully isolated. Appendix D.12, Table 15 shows that the full method improves over FIFO-only by 0.64 and 0.82 percentage points. However, this comparison does not distinguish the benefit of the specific bilateral grid design from the more general benefit of allocating part of the budget to historical information.

  • The connection between structural preservation metrics and task-relevant semantics remains insufficiently established. Semantic purity in Table 5 relies on pseudo-labels obtained by clustering the original token features and therefore primarily measures consistency with feature-space groupings. The correspondence between this consistency and the semantic information required by downstream tasks remains insufficiently validated.

  • Coordinate correspondence across independently normalized grids requires clarification. Appendix D.13 states that min–max normalization statistics are computed independently for each temporal group, whereas Appendix C.2 merges cells with identical indices across grids. Because the normalization ranges may differ, identical indices do not necessarily correspond to the same regions in the original projected space.

  • The evaluation benchmarks may not adequately reflect the long-horizon demands motivating the method. Table 15 shows that FIFO-only achieves performance close to the full method under a matched token budget. This raises uncertainty about whether the benchmarks adequately test the ability to preserve and retrieve task-relevant information from distant history. The authors could consider additional benchmarks with stronger historical dependencies or construct targeted evaluations aligned with the intended capabilities.

Questions for authors
  1. How does bilateral grid compression compare with alternative historical-token compressors when both the FIFO branch and recent/history budget allocation are fixed?
  2. Do improvements in distortion and semantic purity correlate with downstream QA gains?
  3. How are cells aligned across independently normalized grids before cross-grid merging, and how does repeated merging affect long-sequence performance?
  4. Given the strong FIFO-only results, can you evaluate tasks that explicitly require distant-history recall or reasoning across temporally separated events?
4 comments
AuthorsOpenReview ↗

Response to Reviewer 7TmL (1/N)

Thank you for the valuable feedback. We carefully address each concern below.

W1/Q1. Isolating the grid's benefit

To isolate the benefit of the grid, we fix the FIFO branch and the history budget and swap only the historical-token compressor, replacing the bilateral grid with the baselines that, like the grid, require no temporal boundary prior and are thus applicable to the streaming setting (VisionZip, ToMe, and StreamingTOM). The table below reports the results, and two observations follow. First, allocating the budget to history is not sufficient by itself: with VisionZip or ToMe, the historical tokens do not improve over FIFO-only (53.76 in Table 16) on OVO-Bench, so the outcome depends on how the history is compressed. Second, under the same FIFO branch and budget, the bilateral grid outperforms all baselines, indicating that the benefit of the grid is attributable to its compression of the historical tokens rather than to the budget allocation alone. The margins are small on StreamingBench because most of its questions concern the recent frames, where every method relies on the same FIFO branch (see also our response to W4). In the revised manuscript, we have added this comparison to Appendix D.12 and referred to it in Section 5.2.

Historical-token compressorStreamingBenchOVO-Bench
VisionZip67.6953.08
ToMe68.3351.64
StreamingTOM68.2554.10
BGStream68.6054.58

W2/Q2. Purity/distortion and downstream QA

As the reviewer notes, purity relies on k-means pseudo-labels and thus mainly measures consistency with feature-space groupings. To check how far this consistency relates to the downstream task, we computed both metrics for BGStream, VisionZip, ToMe, and StreamingTOM and correlated their averages with QA accuracy on 1,000 randomly sampled questions. Both correlations are in the expected direction (Spearman ρ\rho = 0.40 for purity and −0.60 for distortion, where lower distortion is better), indicating a trend rather than a close relationship. In other words, better structural preservation is associated with higher accuracy but does not by itself determine it.

This result helps clarify the scope of our motivation: we designed BGStream on the view that the loss of structure among visual tokens is a key cause of the degradation of existing methods at low retention ratios, and the trend above suggests that it is indeed a cause, but not the only one. Other causes include cases where distinct instances of the same category are merged into one group, losing the information needed for counting, and cases where a small object that a question asks about does not survive compression even though the overall structure is preserved. Accordingly, Section 5.6 is meant to show that BGStream addresses the structural cause, preserving the feature-space structure, rather than to account for all of its QA gains. Addressing the other causes is a natural direction for future work.

As the original text did not make this scope clear, we have revised Section 5.6 accordingly and added this discussion to Appendix D.7. We thank the reviewer for prompting this clarification.

AuthorsOpenReview ↗

Response to Reviewer 7TmL (N/N)

W3/Q3. Cell alignment across grids and repeated merging.

We thank the reviewer for this careful reading. We agree that, with per-group normalization, identical cell indices do not necessarily correspond to the same region of the projected space. We first note that cross-grid merging is a practical safeguard for keeping the context within a token budget on arbitrarily long streams, rather than a core step of the compression. It is invoked only when the context exceeds BB = 18,000 tokens, which the videos in StreamingBench and OVO-Bench never reach, so the results in Tables 1 and 2 do not involve merging.

Nevertheless, to address the concern for the case where merging does occur, we implemented an aligned variant and compared it with the original merging. The original (index-based) merging combines the cells that share the same index in the two grids. The aligned variant instead keeps each cell's mean key in the un-normalized projected space, re-quantizes both grids over their common range, and merges the cells that land in the same new cell, so that cells are merged by location in the projected space rather than by index; the mismatch described by the reviewer cannot occur in this variant. Since merging never triggers at the default budget, we evaluated on a subset of 611 OVO-Bench questions with long videos (7.5 min on average) and reduced BB so that merging actually occurs: at BB = 2,000 only a few merges take place, and at BB = 1,000 merging occurs repeatedly. As shown in the table below, the two variants give the same accuracy at BB = 2,000 and differ by a single question at BB = 1,000, while repeated merging itself lowers accuracy by 0.3 points. The mismatch in normalization ranges therefore has little effect, which is consistent with Appendix D.13, where per-frame and per-group normalization also perform on par. We keep the index-based merging for its simplicity, and have added this discussion to Appendix C.2.

Budget BBIndex-based merging (original)Aligned merging
18,000 (default)45.5045.50
2,00045.5045.50
1,00045.1745.01

W4/Q4. Evaluation of distant-history recall

We agree that the aggregate scores of both benchmarks are dominated by questions about the recent context, which explains the strong FIFO-only result in Table 15 (in the revised manuscript, Table 16). Two of our evaluations, however, directly test distant history. The Backward Tracing tasks of OVO-Bench (Table 2) require recalling past events and ordering temporally separated actions, and the offline long-video benchmarks in Appendix D.8 pose the question at the end of a long video, where the FIFO buffer holds only the last few frames. In both settings, BGStream achieves the best score among compression methods or remains competitive with offline methods that see the entire video, indicating that the grid tokens retain the information needed for distant-history recall. Finally, we would like to reiterate that BGStream targets streaming video understanding, where frames must be compressed on the fly without access to the full video. The streaming benchmarks are therefore our primary evaluation, and the results above show that this constraint does not come at the cost of long-horizon recall.

We have revised the paper accordingly: Section 5.2 now presents the Backward Tracing and offline results together under "Distant-history recall" and Appendix D.12 explains that the strength of FIFO-only in Table 16 reflects the recency of the benchmark questions.

Thank you for the response and additional experiments. The clarifications and controlled comparisons address some of my concerns. However, W4 remains insufficiently resolved given the limitated evidence in existing benchmarks. This limitation also affects the mimimal performance improvement in W1. I will maintain my original rating.

We sincerely appreciate your valuable feedback, which has helped us further improve our work.

We'd like to address your remaining concern regarding W4, and we believe the following three points do so. 1) in our response to W1, we replaced the historical-token compressor with other baselines while keeping the FIFO branch and the budget fixed, and BGStream still outperformed all of them. Since the FIFO branch is identical across these methods, the difference comes from how the history beyond the FIFO window is retained. 2) In this comparison, the margin is larger on OVO-Bench, which includes Backward Tracing tasks that require recalling distant history. 3) as noted in our earlier response, BGStream outperforms the baselines applicable to the streaming setting (e.g., VisionZip, ToMe) on the offline long-video benchmarks (Appendix D.8), which also require understanding distant history.

Last but not least, we'd like to emphasize that BGStream is designed for the streaming setting, where no temporal prior is available and a low retention ratio is required. In this regard, the bilateral grid allows tokens from incoming frames to be merged at low cost. Although distant-history recall is not the primary target of this design, we believe the three results above show that BGStream is also effective at it. We truly appreciate your feedback on this point, which helped us further examine this aspect of our method. We hope these points address your remaining concern, and we would be grateful if you could reconsider your score in light of them.

Reviewer_QViHOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes BGStream, a training-free visual token compression framework for streaming video understanding. BGStream projects high-dimensional visual features into a low-dimensional guidance space using a Gaussian random projection and splats tokens into a bilateral grid, where tokens assigned to the same cell are aggregated. It additionally maintains a FIFO buffer of recent frames and hierarchically merges older grids when the token budget is exceeded. Experiments on streaming video benchmarks show that BGStream outperforms existing visual token compression methods while maintaining competitive inference latency.

Critical strengths
  • This paper is clearly written, and the streaming-specific motivation is important and well presented.
  • Applying bilateral-grid splatting to visual token compression is an interesting idea. Also, this paper provides the solid theoretical analysis.
  • The paper provides extensive experiments across multiple streaming benchmarks, model backbones, and various analysis.
Critical weaknesses
  • While the experimental results are strong, further analysis of long-term information preservation, failure cases, and sensitivity to random projection would strengthen the paper.
Questions for authors
  1. Although Tables 2 (and Table 15 in Appendix) partly cover long-term memory, testing questions whose answers lie beyond the five-frame FIFO buffer would better show the benefit of the proposed grid splatting.
  2. A visualization of example failures and the token merging process would be helpful to understand the behavior of the proposed algorithm.
  3. Since BGStream uses a random Gaussian projection, how sensitive is its performance to the random seed? The variance across different projections would help demonstrate its stability.
3 comments
AuthorsOpenReview ↗

Response to Reviewer QViH

Q1. Questions beyond the five-frame FIFO

Table 12 (in the revised manuscript, Table 13) covers this case. In the offline benchmarks (EgoSchema, LongVideoBench, MLVU), the FIFO buffer holds only the last few frames of a long video, while the questions require understanding the whole video. BGStream remains competitive with offline methods that see the entire video at compression time and outperforms the streaming baseline, which shows that the grid tokens carry the long-term content. The Backward Tracing results in Table 2, where BGStream achieves the best score among compression methods on recalling past events, point in the same direction. We now present these results together in Section 5.2 (Distant-history recall).


Q2. Failure cases and the merging process

We have added a failure case to Appendix D.15 (Figure 7). The example is a Counting question from StreamingBench: the annotated answer is three buses, whereas BGStream predicts two. We chose this task because counting requires observations of different instances to remain distinct over time, which directly tests how tokens are grouped. Nine tokens on one bus and 23 on a different bus that appears later are assigned to the same cell together with other history tokens, so parts of both buses are summarized by a single mean token.

This example shows that BGStream can pool observations of different instances into one cell when their guidance keys are similar, regardless of when they were observed. As the cell assignment is reconstructed for illustration, we do not claim that this pooling alone causes the error. Preserving instance- and event-level distinctions, for example through adaptive token allocation, is a direction for future work.


Q3. Sensitivity to the random projection

We ran BGStream with three random seeds for the Gaussian projection on StreamingBench and obtained 68.89 ± 0.39. The variation across seeds is far smaller than the margin over the baselines, and the ranking is unchanged for every seed, which shows that the performance of BGStream is stable with respect to the projection. We have added the seed statistics to Appendix D.12.

I appreciate the authors' response and will maintain my original positive rating

We sincerely appreciate your valuable feedback, especially analysis of the failure cases, which helps us clearly understand the limitations of our method. We would like to address these limitations in our future work.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.