- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 2
Read review
Paper summary
This paper proposes EWiM, a training-free method for accelerating the prefill stage of Video LLMs on long videos. EWiM first approximates most visual attention blocks cheaply by pooling, and then selectively recomputes exact attention for a small set of blocks. Blocks are chosen by how much correcting them changes the representation of the question’s final token, and are selected under a latency budget using a hardware-aware cost model. Across four video benchmarks and multiple Video LLMs, EWiM retains nearly all of dense accuracy at a moderate time-to-first-token speedup, and it can be combined with token compression.
Critical strengths
-
A well-posed question within approximate attention. The paper argues that attention interactions should be prioritized by their effect on the answer rather than by local approximation error, and controlled comparisons against local-error and text-aware signals support this choice. This offers a useful principle for deciding where exact computation matters in sparse attention.
-
Realistic and broad evaluation. All overheads (probing, selection, and refinement) are included in the reported latency, and the cost model accounts for computation shared among blocks. The evaluation covers four benchmarks on full splits, a wide range of token-compression and sparse-attention baselines, and multiple backbones. Together, these make the reported accuracy–latency trade-off credible.
Critical weaknesses
-
The writing makes the method very hard to understand. Section 3 relies heavily on undefined, implementation-level terminology and compressed notation. The underlying idea is simple: approximate most attention blocks by pooling, then recompute exactly the few blocks that most affect the question’s final token. Yet it could be conveyed far more clearly with a standard attention formulation, a notation table, and a step-by-step description. This is consequential to my assessment because the presentation makes it difficult to verify the method and to judge its contribution.
-
The practical motivation relative to existing efficiency strategies is unclear. FlashAttention already removes the memory bottleneck of exact attention, and token compression reduces attention, feed-forward, and KV-cache costs together while remaining compatible with such kernels. EWiM, by contrast, reduces only attention computation, increases peak memory, and leaves the KV cache unchanged, while yielding a speedup comparable to token compression. It also requires many components and hyperparameters, and much of its latency budget is spent repairing a lossy coarse approximation. This is the main reason for my rating: the paper does not show when its added complexity provides benefits that simpler existing strategies cannot.
Questions for authors
- In which settings does EWiM offer benefits that token compression combined with efficient exact attention (e.g., FlashAttention) cannot? Can you provide a latency breakdown (vision encoding, attention, feed-forward) across context lengths?
6 comments
Reply 2: Refinement overhead, calibration, composition, and deployment limits
Net benefit of refinement. Four measured Qwen2.5-VL/Video-MME operating points quantify the cost of refinement:
| Configuration | Accuracy (%) | Mean TTFT (s) |
|---|---|---|
| Dense | 61.3 | 3.20 |
| Coarse | 54.3 | 1.88 |
| Denser Single Pass | 60.1 | 2.17 |
| EWiM | 61.0 | 2.16 |
Relative to Coarse, EWiM gains 6.7 percentage points (pp) with a 0.28 s increase in TTFT. Relative to Dense, it saves 1.04 s with a 0.3-pp accuracy reduction. Compared with Denser Single Pass, its observed accuracy is 0.9 pp higher at comparable measured TTFT.
The 0.28 s is a net difference between independent complete runs; component costs are measured separately. Denser Single Pass enlarges the base exact set, retains other pooled contributions, and performs no DGP. It tests spending additional computation directly on base exact attention rather than feedback-guided refinement. Its 132 additional full blocks, versus EWiM’s 84, are block counts. EWiM also incurs sampled probing, readout, and refresh work, so this ratio is not a total-compute or FLOP ratio.
Composition with compression. With the same fixed 50% FlashVID-compressed input on this model–benchmark pair:
| Attention policy | Accuracy (%) | Mean TTFT (s) |
|---|---|---|
| Dense | 58.8 | 1.95 |
| EWiM | 60.0 | 2.15 |
EWiM gains 1.2 pp at an additional 0.20 s. This fixed-input operating point improves accuracy at higher latency; it does not demonstrate acceleration over Dense on those tokens. Nor does it establish recovery of information removed by merging or greater similarity to uncompressed Dense outputs.
The separate joint-selection results report retention, accuracy, actual TTFT, and the configuration-selection protocol for each policy. Combination speedups are measured directly. In this setting, EWiM preserves the compressed sequence it receives, rather than the original pre-compression token sequence.
Configuration and calibration. Training-free does not imply calibration-free. The revised configuration table separates fixed design settings, development-selected operating points, host adapters, and hardware profiles. The reference uses , , , a 50:50 ranked/coverage mixture, and probing microbatch size 32. The selected reference operating point uses and ; both are included in the disclosed development search.
The layer budget is
where the profile is Dense attention time for that layer and input shape, not full-model TTFT. Host-specific layer indices and execution settings are listed in the configuration table.
Calibration uses 220 replay configurations per host–backend–GPU combination without answer labels. The primary H800 calibration takes 41 minutes, including preparation, compilation, warm-up, and repeated measurements. This is an offline cost for the identified combination, separate from per-request TTFT. On A100, coefficients are recalibrated and budgets recomputed; accuracy and TTFT are re-evaluated because accepted sets can change.
Memory and deployment limits. In the reported H800 setting at 64K, allocated GPU memory is 41.6 GiB for EWiM and 38.2 GiB for Dense. The 3.4-GiB difference is a total allocated-memory difference, not an isolated temporary-workspace measurement.
EWiM retains ordinary token-indexed KV storage and the ordinary FFN work associated with retained tokens. Refinement changes intermediate states and potentially KV contents, and adds row-update work. KV capacity, contents, and cross-question reusability are distinct properties.
For three and eight independent questions about the same video, EWiM’s cumulative TTFT exceeds Dense’s, while VecAttention remains faster. This measured limitation rules out extending the single-request speedup to those cached workloads.
The evaluated settings are batch-one prefilling on H800 and the recalibrated A100 configuration. Primary single-request timing uses no cross-request visual-feature or KV reuse. TTFT runs from decoded frames in host memory to first-token logits and includes visual encoding and all online method overhead. Larger batches, concurrent serving, multi-GPU execution, and decoding acceleration remain outside the evaluated scope.
Reply 3: A clearer formulation and execution sequence for Section 3
Section 3 now follows the attention computation and execution order: a provisional mixed-attention pass, isolated sampled probes, cost-aware selection, and joint full-block refinement. A compact notation table defines the symbols before use. The revised algorithm gives this sequence explicitly; detailed state lifecycles and kernels remain in the appendix.
1. Shared normalization. For one layer and query head, let . A KV tile contributes
where contains keys visible to query under the host mask. Tildes denote the corresponding pooled proxy contributions. With exact tiles and proxy tiles ,
Refinement replaces a block’s numerator and denominator contributions under this shared normalization. Selected contributions are computed exactly, but remaining proxies still affect the denominator; the resulting row is not a fully Dense output.
A candidate block comprises a query head, a query tile, and a KV tile. Approximation is restricted to entirely visual blocks whose entries are all visible under the host mask. Visible text-related and causal-boundary interactions remain exact; masked entries contribute zero. Pooling retains its multiplicity correction and the native positional and query-to-KV-head conventions.
2. Incremental downstream probing. Each candidate trial starts from the same provisional state and changes only sampled visual rows. The terminal nonvisual prompt position is unchanged, so its next-layer query is fixed. EWiM refreshes the changed rows’ native next-layer KV projections, updates the terminal attention row from shared baseline statistics, and evaluates that row’s output projection and feed-forward operations. It does not rerun the remaining decoder for each candidate.
The terminal query is shared; the changed keys and values are not frozen. DGP uses the normalized response magnitude defined in Eq. (5), without answer labels. Its scoring definition is unchanged by the presentation rewrite.
3. Allocation by conditional execution cost. Let be the accepted set and the newly affected query-row work, deduplicated across heads. The fitted marginal cost is
A block reusing already affected rows avoids additional row-update work; new rows and startup incur the corresponding costs. ECA selects the feasible candidate with the largest sensitivity-to-marginal-cost ratio, keeps sensitivity scores fixed, and updates costs after each acceptance. It stops when no remaining candidate fits the profiled budget, which includes probing and allocation overhead. This models execution sharing, not additive answer utility.
4. Joint full-block refinement. Probe states are discarded rather than accumulated. Once selection ends, every accepted block is recomputed over its full query tile, including sampled rows. Numerator and denominator corrections are accumulated within each head. EWiM then assembles head outputs, performs one shared native update per affected row, refreshes dependent projections, and commits the state before ordinary next-layer execution. Shared row updates therefore do not mix the softmax statistics of different heads.
5. Offline routing and reuse. Attention contributions obey the host mask, while routing uses the observed full video–question prompt. Question-dependent selection can change visual-prefix states, so mask compliance does not imply prefix invariance or unrestricted cross-question reuse.
The overview distinguishes unchanged model weights, decoding procedure, and supplied token sequence from the attention computation and intermediate states that refinement changes. The formulation, algorithm, and execution description now use the same notation and state sequence.
Reply 1: Measured trade-offs against token compression and runtime across context lengths
EWiM preserves the sequence supplied to it and approximates selected visual-attention interactions. It allocates additional computation to corrections with stronger sampled effects on the current question’s next-layer readout. Its target is attention computation during prefilling, rather than reducing token count or KV storage.
Comparison with optimized baselines. Dense and FlashVID use the same optimized exact-attention backend for retained-token computation. EWiM uses kernels suited to mixed proxy attention, sampled probing, and block refinement. The revised implementation table identifies the kernels, compilation settings, and fallback behavior. Any auxiliary computation required by a method remains included in its measured cost.
Accuracy uses the full benchmark split. Mean TTFT uses the same fixed 200-request timing panel across methods within each model–benchmark pair, with common repeat and aggregation procedures. Development videos are source-disjoint from evaluation videos.
On Qwen2.5-VL/Video-MME, the highest-accuracy observed configuration of each baseline within ±2% of EWiM’s mean TTFT is:
The observed differences are +1.0 and +1.4 percentage points (pp) at comparable TTFT. These are evaluation-selected descriptive comparisons. Conditional on the displayed configurations, source-video-clustered paired 95% intervals are [0.5, 1.5] and [0.8, 2.0] pp; these pointwise intervals are not adjusted for operating-point selection.
The development-frozen primary comparisons and actual latencies are reported separately for all eight main model–benchmark pairs. Searches include 15 EWiM configurations, 12 VecAttention configurations, and FlashVID visual-token retention of 40–100%, with native parameter values and fixed settings disclosed. This is a specified search range, not FlashVID’s complete native range. The curves retain points outside the matching window, including VecAttention’s faster 58.6% / 1.65 s configuration. The evidence supports the reported high-fidelity trade-offs, not uniform dominance over compression or sparse attention.
Runtime across context lengths. Revised Figures 6–7 provide numerical profiles over 8K, 16K, 32K, and 64K alongside independently measured deployment-path TTFT. The cross-method functional view compares Dense, FlashVID, and EWiM through vision encoding, decoder attention, FFN, projection/normalization, and other work. The EWiM stage view separately reports Coarse, Probe, Select, Exact refinement, and Refresh.
These are alternative classifications, not additive categories. For example, probing’s FFN work appears under FFN in the functional view and Probe in the stage view. Row updates are counted once, reused projections are not charged twice, and kernels that cannot be reliably decomposed are identified separately.
Length groups are defined by the common pre-compression host-formatted request length, Norig. Methods use the same requests within each timing group; FlashVID’s retained length is reported separately. Total tokens, visual tokens, retained visual tokens, and video duration are distinguished.
Component profiles explain computational work; independent TTFT measures request latency. Asynchronous execution, overlap, fusion, and profiling boundaries can prevent component times from summing to TTFT. Residual or unattributed wall time is disclosed where applicable rather than assigned arbitrarily to attention. Real requests support task-quality conclusions; fixed-shape replay isolates execution effects.
The decomposition explains the execution conditions behind the measurements. A large Dense attention fraction alone does not establish superiority over compression, and the aggregate high-fidelity comparison is not presented as evidence of dominance at every context length.