- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper proposes Triceps, a training-free prefill acceleration method for long-context LLMs that approximates the interior attention matrix (outside the exact sink and sliding-window -shape) as an elementwise product of three rank-1/Toeplitz matrices: , capturing query normalization, relative-position slash diagonals, and key-wise vertical columns. At runtime, the authors fit and in the log-domain via ridge-regularized least squares on uniformly sampled pre-softmax logits, calibrate , and evaluate the approximation on the last query rows to route each head to either an FFT convolution kernel, a multiplicative block-sparse Triton kernel, or a delegated sparse method (FlexPrefill). Experiments on Qwen3-30B-A3B and Nemotron-8B across RULER and LongReason (64k to 256k ctx) demonstrate end-to-end TTFT speedups at 128k--256k.
Critical strengths
Factorizing the interior vertical-slash pattern as by fitting a row-centered linear model in the log-score domain (Eq. 5) is a clean alternative to taking a rigid union of dominant columns and diagonals. In block-sparse mode, adding the fitted log-components () induces a smooth multiplicative threshold where strong key importance can compensate for weaker positional weight, yielding low deployed densities (11%--25% across paths, Tab. 2).
The systems integration in vLLM (w/ TP=2 up to 256k ctx) and the transparent FLOP/pseudocode breakdown in App. C (Tab. 6, Alg. 1--10) are also well executed. In addition, the exponential-family covariance identity in App. B.2 () gives a nice theoretical explanation for why gating the convolution mode on output error is much more reliable than using score-level .
Critical weaknesses
My biggest concern is that the claim of a superior speed-accuracy trade-off over existing sparse methods is hard to reconcile w/ the accuracy drops in Tab. 1 and Tab. 4. On LongReason w/ Qwen3-30B-A3B (Tab. 1a), Triceps () drops by 8.95 points below Dense at 64k (67.62% vs. 76.57%) and 5.79 points at 256k (67.51% vs. 73.30%), whereas FlexPrefill, PBS-Attn, and PRISM stay within ~1 point of Dense. Similarly, on RULER (Tab. 1b, Tab. 4), Triceps posts the lowest average accuracy among all online baselines in nearly every setting, w/ sharp drops on subtasks like Qwen3 cwe at 128k/256k (31.60% and 8.40% vs. PRISM's 64.10% and 26.90%) and Nemotron niah-multikey-1 at 64k (73.00% vs. Dense 86.00%). Because Tab. 1 only reports a single operating point () without a Pareto curve, it is unclear if any TTFT speedup over FlexPrefill remains once is tightened to match FlexPrefill's accuracy.
Second, although the FFT convolution mode is pitched as a headline contribution, Tab. 2 shows it is selected for only 1.7%--4.4% of heads on Nemotron and 4.6%--13.5% on Qwen3, and its share actually shrinks as ctx length grows from 64k to 256k (e.g., from 13.5% down to 6.1% on Qwen3 LongReason). Meanwhile, the decomposition, row-variance calibration, and routing pass incur substantial upfront overhead (39% of prefill GPU time at 64k, Fig. 2), making Triceps slower than FlexPrefill and PRISM at 64k across most settings in Tab. 5.
Third, Triceps relies heavily on FlexPrefill as its delegation backend for 10.5%--31.8% of heads (Sec. 5.1), which includes the retrieval heads where the rank-1/Toeplitz fit breaks down. Those delegated heads pay Triceps' full fitting and tail-row measurement overhead (), and then run FlexPrefill's own selection pass from scratch (line 426). There are also a couple of mismatches between the main text and App. C: Alg. 1 calls convolution calibration (Alg. 7, line 7) only after routing measurement (Alg. 5, line 4), meaning in Alg. 5 is evaluated using the statistics-calibrated from Alg. 4 rather than the convolution-calibrated used at execution; and Alg. 6 introduces an undocumented cost model that does not appear in Eq. 13.
Questions for authors
-
Why does Qwen3-30B-A3B suffer such a steep accuracy drop on LongReason at 64k (67.62% vs. 76.01% for FlexPrefill) and 256k (67.51% vs. 72.29%), as well as on RULER cwe? If you lower so that Triceps matches FlexPrefill's accuracy on Qwen3 LongReason and RULER, what is the resulting TTFT speedup?
-
Given that the convolution mode is only triggered on 1.7%--6.1% of heads at 256k (Tab. 2), what are the end-to-end TTFT and accuracy if you disable the convolution path entirely and only route between Triceps' block-sparse mode and delegation?
-
For the 20%--32% of heads delegated to FlexPrefill, why not reuse the exact tail-row attention scores already computed during
ROUTINGMEASUREMENT(on the last rows) instead of running FlexPrefill's selection pass again? Also, how does Triceps compare if delegation falls back to dense FlashAttention-2 rather than FlexPrefill? -
Can you clarify the ordering in Alg. 1 (lines 3--7)? Is inside
ROUTINGMEASUREMENT(Alg. 5, line 4) computed using the statistics-calibrated from Alg. 4, and if so, why not use the exact row mass from Alg. 7 when measuring ? Also, how is the cost model in Alg. 6 defined?
3 comments
Thank you for the detailed response and additional experiments. I have two remaining questions: i). Table A varies Triceps’ configuration while keeping the baselines at fixed operating points. Could you also sweep FlexPrefill’s budget on Qwen3 LongReason to show whether Triceps remains faster at matched accuracy? ii). Table B shows that disabling convolution can improve accuracy, while replacing delegation with exact attention can reduce it. Could you explain these changes and clarify how they support attributing the accuracy loss mainly to block selection? Varying while holding fixed would help isolate this effect.
We thank Reviewer xvCE for the follow-up questions and for suggesting the fixed- ablation over .
i) Matched-Accuracy Comparison with FlexPrefill on Qwen3 LongReason
On Qwen3-30B-A3B LongReason, Table A already provides a direct comparison at similar or higher accuracy against FlexPrefill ():
-
128k: Triceps () achieves higher accuracy ( vs. , matching Dense FA2) and lower TTFT ( vs. , faster).
-
256k: Triceps () closely matches FlexPrefill ( vs. ) while reducing TTFT from to ( faster).
Because each full LongReason evaluation on Qwen3-30B-A3B is computationally expensive, we focused our remaining GPU time before the discussion deadline on completing the fixed- ablation over below.
ii) Isolating Block Selection ( Sweep at Fixed ) & Table B Variations
Following your suggestion, we evaluated Qwen3-30B-A3B on the full LongReason benchmark (794 prompts) holding fixed ( unchanged) and varying only , so only the block-sparse retained mass is affected:
| Configuration ( fixed) | Max | LR Acc (%) 64k / 128k / 256k | LR TTFT (s) 64k / 128k / 256k |
|---|---|---|---|
| Triceps () | / / | / / | |
| Triceps () | / / | / / | |
| Triceps () (Table A/B) | / / | / / |
Holding the convolution threshold fixed (), tightening from reduces the maximum allowed dropped attention mass from to , monotonically improving accuracy by pts (64k), pts (128k), and pts (256k). In contrast, at fixed in Table B, disabling the convolution heads (No-Conv vs. Full, redirecting heads with to block-sparse) produces a mean absolute difference of only percentage points across all 12 model/length columns, and replacing FlexPrefill delegation with exact dense attention (FA2-Delegation vs. Full, which only modifies the delegated heads that already retain mass under FlexPrefill while leaving the remaining block-sparse and convolution heads unchanged) yields a mean absolute difference of only percentage points. Both variations are an order of magnitude smaller than the point effect of , confirming that the accuracy drop in our initial configuration came from not retaining sufficient attention mass during block selection rather than from the convolution or delegation approximations.
We thank Reviewer xvCE for the insightful technical review and for highlighting the exponential-family covariance identity in Appendix B.2.
Q1 — Accuracy on Qwen3 LongReason / RULER
cwe& Matched-Accuracy TTFT:RULER
cweand LongReason on the initial configuration (kc=0.5,τ=0.4, 18.1 dropped mass) were over-pruned. As detailed in Global Comment 1 (Table A, Table 5), setting kc=0.2 and τ=0.5 bounds dropped mass to 9.5. On Qwen3 LongReason, accuracy increases to 74.56%, 73.43%, and 72.04% at 64k, 128k, and 256k (matching Dense at 128k) while running faster than FlexPrefill at 128k (9.68s vs. 10.77s) and 256k (25.02s vs. 28.98s). On RULER, Triceps achieves the highest average accuracy among sparse baselines in 5 of 6 settings: Nemotronniah_multikey_1(64k) improves from 73.00% to 87.00% (vs. Dense 86.00%), and Qwen3cweimproves to 46.40% at 128k (vs. FlexPrefill 21.30%) and 13.60% at 256k (vs. FlexPrefill 10.19%). While PRISM achieves higher scores oncwe(64.10% / 26.90%), it comes at a higher computational cost (52.86s vs. 41.55s) and still underperforms Triceps (τ=0.5) on the overall RULER average across all context lengths (Table A).Q2 — 64k Overhead, Convolution Share vs. Context Length & Disabling Convolution:
Kernel optimizations reduced upfront overhead from 39 to 22 at 64k and 5 at 256k (Global Comment 1, Figure 4), making Triceps faster than FlexPrefill and PRISM at 64k on Nemotron and faster than PRISM on Qwen3 (Table A). With the updated configuration, while we reduced the number of dropped blocks (Table 2), the convolution share rises to 9.8 on LongReason and 4.8 on RULER (decreasing mildly with N as a single global Toeplitz operator spans a longer prefix). As shown in Global Comment 3 and Table B (Table 4), each convolution head executes ∼4× faster than block-sparse at 256k (2.7 ms vs. 9.7—12.6 ms, Figure 4), and disabling convolution (
Triceps No-Conv) increases 256k TTFT across all benchmarks (up to +6.2) at comparable accuracy.Q3 — Reusing the k=64 Tail-Row Scores in FlexPrefill & Dense FA2 Fallback:
Triceps FA2-Delegationin Global Comment 3 and Table B (Table 4): even when every delegated head runs exact dense FlashAttention-2, Triceps achieves 2.06× to 2.36× speedup over Dense on LongReason at 256k and 1.74× to 1.85× on RULER.Q4 — Ordering in Algorithm 1/5 for Econv & Cost Model C in Algorithm 6:
ROUTINGMEASUREMENT(Alg. 5), Econv is evaluated with the exact convolution row-mass normalization of Equation 10 (Alg. 7), not the statistics-calibrated h from Alg. 4: on the k=64 tail rows, our fused Triton kernel accumulates both the unnormalized interior output and the exact row sum (d∗c)i directly in O(kNd) time and normalizes by AΛ′1i+gi(d∗c)i. Full-sequenceCALIBRATEHORIZONTAL_CONVOLUTION(Alg. 7, which costs 3 full-length FFTs across all N rows) is called afterDECIDEHEADin Alg. 1 so that full-sequence FFTs are only paid on heads actually routed toconv.ConstantCostModel), Cconv=0, Csparse(ρ)=ρ, and Cdeleg=Cdense=ρ0=0.60, making argminmV[m] in Algorithm 6 identical to Equation 13. We simplified Algorithm 6 in Appendix C to match Equation 13 directly.