{"id":"fea35462-0bd6-4278-a014-17f3af0e1e39","arxiv_id":"2506.19651","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A fine-tuning-free parallel encoding scheme for VLMs that partitions video frames into context blocks with a shared sink block and sequential position embeddings, reducing prefill attention from quadratic to linear while preserving accuracy.","lead":"PEVLM is a fine-tuning-free method that speeds up long-video question answering in vision-language models by splitting the video into parallel chunks with a shared prefix. If its results hold, it makes long-video understanding several times faster at near full-attention accuracy, which matters for robots, vehicles, and video analytics.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Central complexity claim is unsupported: Eq. 4 implies cumulative KV prefixes (Θ(L²)), while Eq. 8 assumes sink+current block; even the intended mask gives Θ(T·N²), not Θ(T·N).","rationale":"The reader's CONDITIONAL verdict is sound. The fixed-sink worry is real but secondary: because the question block attends to the full key/value sequence, later-frame information is not entirely inaccessible; the risk is limited to video tokens whose representations need cross-block context. The complexity claim is more immediately load-bearing because it is the paper's headline and is contradicted by its own equations. The reader noted Eq. 4 vs Eq. 8 but did not make this the weakest assumption; I make it primary. If Eq. 4 is literal, the mask serializes context blocks and the speedup figures in Fig. 4/5 are unexplained; if Eq. 8 is literal, the O(TN) statement is still wrong because S and B are frame-based and therefore scale with N. Either way the central claim needs correction. Since the method may still be practical after re-derivation, I keep the verdict CONDITIONAL rather than REJECT.","tokens_in":12876,"tokens_out":17100,"duration_ms":184422,"concrete_test":"Implement the exact attention mask described in Figure 2 and count FLOPs for Qwen2.5-VL at T=768 frames with N tokens per frame, S=B=16 frames, and M=T/16 context blocks. If c_i keys are S∪c_0...c_{i-1}, the count is Σ_i 2HB(S+iB)=Θ(L²), not Eq. 10; if c_i keys are S∪c_i, the count is 2H[S²+M·B(S+B)+Q·L]=Θ(TN²+QTN). Then double N at fixed T and measure wall-clock attention time: Θ(TN) predicts ~2× growth, while the frame-based construction predicts ~4× growth. This settles whether the abstract's O(TN) is the correct scaling law.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing problem is inside the complexity claim. Eq. (4) defines Attn_ci = f(Q_ci, K_{s+c0+...+c_{i-1}}, V_{s+c0+...+c_{i-1}}), i.e. the i-th context-block query attends to the sink plus every earlier context block. Summing Eq. (4) over i gives Σ_i 2HB(S+iB) = Θ(L²), which is full-attention-like and contradicts Eq. (8)'s O(L) total. Eq. (8) uses 2HB(S+B) per block, the sink+current-block mask described in the Partitioning Strategy. The paper never reconciles this, and no code is released, so the actual mask cannot be checked. Even if Eq. (8) is the intended mask, the asymptotic claim still fails: the method fixes sink and context block sizes at 16 frames, so S,B = Θ(N) tokens; total prefill cost is Θ(M·B·(S+B)+Q·L) = Θ(TN²+QTN), not Θ(TN). The real reduction is by a factor Θ(T) relative to full attention, not the advertised Θ(TN).","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes PEVLM, a fine-tuning-free parallel encoding scheme for vision-language models that targets the prefilling stage of long-video inference. The video is partitioned into a shared sink block, frame-aligned context blocks, and a question block, while sequential position embeddings are preserved. The authors report that PEVLM reaches 99.57%–104.80% of Full-Attention accuracy across Qwen2.5-VL, LongVILA, and LLaVA-Video on MVBench, EgoSchema, VideoMME, and LongVideoBench, with up to 7.47x attention speedup and a 40% end-to-end latency reduction over Full-Attention.","tokens_in":13069,"tokens_out":7166,"duration_ms":83636,"significance":"If the efficiency and accuracy claims are made precise, PEVLM is a practically attractive contribution: it is training-free, architecture-agnostic, and addresses a real VLM-specific issue, namely that attention sinks extend into early video frames and that reusing position embeddings disrupts temporal reasoning. The evaluation across three backbones and four benchmarks is broad, and the attention-distribution analysis provides a plausible motivation for the design. However, the central advertised complexity reduction is currently not stated consistently with the method's own hyperparameters, and the empirical accuracy claims are weakened by tuning on the test benchmarks. The core idea is worth publishing after the complexity claim is corrected and the evaluation protocol is clarified.","major_comments":[{"comment":"Equation (4) is inconsistent with the rest of the paper. As written, Attn_ci = f(Q_ci, K_{s+c0+...+c_{i-1}}, V_{s+c0+...+c_{i-1}}) makes the i-th context block attend to the sink and all earlier context blocks, which yields cumulative KV prefixes and a Θ(L^2) cost when summed over i. This contradicts Equation (8), the mask shown in Figure 2, and the claimed O(L) complexity. The key-value subscript should presumably be the sink plus the current context block only. Since no code is released, this equation is the only precise specification of the mask, so it must be fixed or the measured implementation must be described exactly.","section":"Formulations, Eq. (4)"},{"comment":"The claimed reduction from O((T×N)^2) to O(T×N) is not supported by the stated hyperparameters. Equation (8) gives O(L) only if S and B are fixed token counts independent of L. In the experiments, S and B are set to 16 frames, i.e., S = Θ(N) and B = Θ(N) tokens when N is the tokens-per-frame count. With M = T/16 blocks, the total prefill cost is Θ(T·N^2), not Θ(T·N). The actual saving relative to Full-Attention is a factor Θ(T), not Θ(T·N). If the authors intend N to be a model-specific constant and only T to grow, then the complexity statement should be written in terms of T alone, or in terms of L with the per-frame token count fixed; the current abstract-level statement is misleading.","section":"Parallel Encoding / Experimental Setup (block size by frames)"},{"comment":"The sink-block and context-block sizes are selected using the same benchmarks that produce the headline accuracy numbers, and Table 2 further selects the sink configuration for each latency budget. No held-out validation or tuning protocol is reported, so the 99.57%–104.80% accuracy ratios may partly reflect selection on the test set. The authors should report a validation-based tuning procedure or, failing that, show that the accuracy conclusions are stable across a range of sink/block sizes rather than only at the selected configuration.","section":"Experiments, Figures 6–7 and Table 2"}],"minor_comments":[{"comment":"The symbol N is used both for tokens per frame in the abstract and for the number of context blocks in Equations (6) and (10). Using M for the block count would remove an avoidable source of confusion, especially given the complexity discussion.","section":"Notation, Eq. (6)"},{"comment":"The runtime measurements are reported without error bars or the number of repeated runs, and absolute attention times are not given. Since some reported accuracy differences are small, the paper should also state whether the benchmark evaluations use a single pass per example and whether multiple runs were averaged.","section":"Performance Evaluation, Figures 4–5"},{"comment":"The attention-weight distributions are described only qualitatively and the moving-average window is not specified. Reporting the window length and the aggregation procedure would make the observations reproducible.","section":"Observations, Figure 1"},{"comment":"There are several typos and clarity issues, including 'Quesion Block' in the Partitioning Strategy and Figure 2, 'promots' in the contributions list, and 'resuing' in the observations section. These should be corrected in a revision.","section":"General presentation"}],"recommendation":"major_revision","confidential_remarks":"The manuscript has a useful, practical idea and a broad empirical evaluation, but the central complexity claim needs to be corrected and the tuning protocol clarified. I do not see the issues as unfixable: the authors can revise the asymptotic statement, align Eq. (4) with the actual mask, and add a validation-based hyperparameter analysis. If code were released, it would also resolve the ambiguity in Eq. (4)."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe short version: PEVLM is a useful VLM-specific recipe for cutting prefill attention cost without fine-tuning, with a broad empirical sweep. But the complexity claim is misstated, and the paper needs a careful rewrite of that section before it's solid.\n\nWhat's actually new: the observation that reusing position embeddings across context blocks disrupts 3D-MROPE temporal encoding, and that putting early video frames in the shared sink block recovers most of the accuracy. The frame-level block partition is a sensible VLM-specific adaptation of Block-Attention/Star Attention. The experiments cover three VLMs and four benchmarks with the relevant baselines, and the accuracy results — 99.57% to 104.80% of full attention — are plausible and practically interesting. The latency-constrained results are genuinely striking.\n\nSoft spots: The complexity analysis is inconsistent. Eq. 4 as written makes each context block attend to all previous blocks, which is quadratic and contradicts Eq. 8's sink-plus-current-block mask; presumably a typo, but it needs to be fixed. More importantly, the advertised reduction from O((T·N)^2) to O(T·N) doesn't hold if N is treated as a variable, because sink and context block sizes are defined in frames (16 each) and therefore scale with N. That gives Θ(T·N^2), not Θ(T·N). For a fixed model, N is constant and the speedup is real, but the abstract's claim is off by a factor of N. The abstract also says 7.47x attention speedup and 40% end-to-end latency reduction, while the body reports 7.79–33.81x attention and 2.58–3.14x LLM speedup; these don't match. No code is released, sink/context sizes are tuned on the evaluation benchmarks, and there are no error bars. These are fixable, but a reviewer can't independently verify the numbers.\n\nWho it's for: people working on efficient long-video inference for VLMs. The VLM-specific diagnosis is the real contribution; the method itself is a combination of known pieces.\n\nRecommendation: it deserves peer review. A serious referee should ask for a corrected complexity analysis, reconciliation of Eqs. 4 and 8, and code or detailed per-sample outputs before accepting the asymptotic claims.","headline":"Useful VLM-specific parallel encoding recipe with a broad empirical sweep, but the complexity claims are overstated and the paper needs revision.","tokens_in":13661,"tokens_out":6252,"would_cite":false,"duration_ms":53784,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"PEVLM cuts long-video VLM attention from quadratic to linear cost without fine-tuning, keeping 99.57% to 104.80% of full-attention accuracy across three models and four benchmarks.","keywords":["parallel encoding","vision-language models","long video understanding","prefill acceleration","attention sink","sequential position embeddings","fine-tuning-free inference","linear attention complexity"],"falsifier":"Inspect attention maps of long videos and identify cases where the highest-attention visual tokens occur after frame 16, such as a video with a long static introduction followed by sudden salient action; run PEVLM on those videos and compare accuracy to full attention. If accuracy drops sharply and grows with sink size, the fixed-sink assumption fails.","tokens_in":1857,"feed_emoji":"🎥","tokens_out":1720,"duration_ms":65822,"temperature":0.7,"pith_summary":"The paper claims that vision-language models can process long videos at near-linear prefilling cost without retraining, by partitioning the video into frame-aligned context blocks that all share a small sink block containing the system prompt and the first 16 frames, while preserving the model's original sequential position embeddings. On Qwen2.5-VL, LongVILA, and LLaVA-Video, this recovers 99.57% to 104.80% of full-attention accuracy across four benchmarks, compared with large drops for prior parallel-encoding methods, and cuts attention computation by up to 7.47x and end-to-end latency by roughly 40%. Under a fixed 20-second latency budget it raises LongVideoBench accuracy from 23.26% to 61.03%. The core insight is that VLM attention sinks live in early video frames as well as in the text prefix, so a shared sink helps, and that reusing position embeddings across blocks destroys temporal structure.","feed_headline":"Video LLMs get near-full accuracy at linear attention cost","feed_subtitle":"Frame-aligned sink blocks plus true order keep 99.57–104.80 percent of full-attention accuracy.","key_machinery":"The central mechanism is the PEVLM attention mask combined with a position-embedding scheme. The video is split by frame boundaries into a Sink Block (system prompt plus the first 16 frames), multiple Context Blocks covering the remaining frames, and an unsegmented Question Block containing the trailing text. Each context block attends to its own tokens plus the sink block, and the question block attends to all tokens; sequential position embeddings are kept exactly as in full attention. This keeps softmax denominators small while preserving temporal position signals, and the shared sink captures the early-frame attention sinks. The total operation count is 2H($S^{2}$ + $Q^{2}$ + N $B^{2}$ + QS + N QB + N SB), which simplifies to O(L) for fixed block sizes.","core_discovery":"PEVLM's central claim is that parallel encoding can be made to match full attention for VLMs by aligning three things: block boundaries with video frame boundaries, a shared sink block that includes both the system prompt and initial frames, and sequential position embeddings rather than reused positions. The paper argues that prior LLM parallel-encoding methods fail on VLMs because they reuse position IDs, which breaks temporal and spatial position information, especially in models like Qwen2.5-VL with 3D rotary position embeddings, and because their sink blocks omit early visual tokens that act as attention sinks. With these fixes, attention complexity drops from O((T × N)^2) to O(T × N)$, and the experiments show accuracy at or above full attention in several long-context settings.","pith_inferences":["The fixed choice of 16 frames for the sink block is not content-adaptive; a dynamic sink that grows when early attention is diffuse or shrinks for short videos would likely improve the accuracy-efficiency frontier beyond the tested configurations.","The same frame-aligned sink with sequential positions should transfer to streaming video: if each new sliding window reuses the sink and only processes new frames, inference cost could scale with newly arrived frames rather than the full history, a direction the paper lists as future work.","The paper's explanation that shorter softmax horizons can beat full attention suggests PEVLM-style parallelism may combine with retrieval or chunked reasoning to improve long-video QA, not merely accelerate it, but this remains an inference from the paper's preliminary analysis."],"forward_implications":["PEVLM can be applied to already-trained VLMs at inference time with no fine-tuning, so deploying it requires only a change to the attention mask and position-embedding handling.","At roughly 100k-token video prefill, the attention layer reaches up to 7.47x speedup and the end-to-end LLM speedup is about 2.58x, with larger sink or context blocks trading speed for accuracy.","Under fixed latency budgets, PEVLM keeps accuracy high where full attention collapses, making long-video question answering feasible on resource-limited hardware.","Because PEVLM preserves full-attention position embeddings, it inherits the model's trained context-length limit and does not extend context capacity, as the paper notes for LongVILA-256f.","In some long-context configurations PEVLM exceeds full-attention accuracy, which the paper attributes to shorter softmax horizons producing sharper, more reliable attention distributions."],"supporting_citations":[{"why":"Establishes that visual attention sinks appear in early video frames, motivating the sink block to include initial frames.","marker":"Kang et al. 2025"},{"why":"Introduces the attention-sink phenomenon and the need to retain initial tokens, the theoretical basis for the shared sink block.","marker":"Lab and AI 2023"},{"why":"Qwen2.5-VL technical report, supplying the 3D rotary position embeddings whose temporal information PEVLM preserves.","marker":"Bai et al. 2025"},{"why":"APE is the strongest prior parallel-encoding baseline, providing the shared-prefix sink idea and attention temperature that PEVLM compares against.","marker":"Yang, Chen, and Chen 2025"},{"why":"Star Attention is a sink-based parallel-encoding baseline whose anchor size and accuracy PEVLM is measured against.","marker":"Liu et al. 2024"},{"why":"Block-Attention supplies the block-partition and position re-encoding approach that PEVLM builds on and improves.","marker":"Ma, Wang, and Tian 2025"},{"why":"TurboRAG is the source of the sequential-position-embedding inspiration that PEVLM adopts for video blocks.","marker":"Lu et al. 2024"},{"why":"LongVideoBench is the long-video benchmark central to the accuracy and latency-constrained evaluations.","marker":"Zhang and Wang 2024"},{"why":"VideoMME provides the short- and long-video benchmark data used in the accuracy comparison.","marker":"Fu et al. 2024"},{"why":"EgoSchema supplies the egocentric long-video reasoning benchmark used in the evaluation.","marker":"Mangalam, Akshulakov, and Malik 2023"}],"fun_headline_variants":["Video LLMs get linear attention without fine-tuning","PEVLM: linear attention, full accuracy for video LLMs","Sink-block parallel encoding makes video LLMs 7x faster","Frame-aligned sinks keep video LLM accuracy at linear cost","Up to 7.47x faster attention for video LLMs, no accuracy loss"],"cache_read_input_tokens":15744,"weakest_assumption_plain":"The method assumes that the system prompt plus the first 16 video frames always contain the tokens that dominate attention for every video and model; if a video's high-attention tokens appear in later frames, PEVLM removes all cross-block attention and cannot recover that information.","fun_headline_variants_meta":{"raw":{"variants":["Video LLMs get linear attention without fine-tuning","PEVLM: linear attention, full accuracy for video LLMs","Sink-block parallel encoding makes video LLMs 7x faster","Frame-aligned sinks keep video LLM accuracy at linear cost","Up to 7.47x faster attention for video LLMs, no accuracy loss"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000341,"raw_usage":{"total_tokens":1888,"prompt_tokens":962,"completion_tokens":926,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":578,"completion_tokens_details":{"reasoning_tokens":836}},"tokens_in":578,"tokens_out":926,"duration_ms":8644,"temperature":1.0,"reasoning_tokens":836,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T18:30:06.690253+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Inspect attention maps of long videos and identify cases where the highest-attention visual tokens occur after frame 16, such as a video with a long static introduction followed by sudden salient action; run PEVLM on those videos and compare accuracy to full attention. If accuracy drops sharply and grows with sink size, the fixed-sink assumption fails.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"APE is the strongest prior parallel-encoding baseline, providing the shared-prefix sink idea and attention temperature that PEVLM compares against."}],"review_version":1}