- Rating
- 3(+1)
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper presents FlashGreedy, a CUDA kernel for greedily solving facility location optimization problems that is build to reduce expensive memory transfers. The FlashGreedy method runs more than 9x faster in all settings that are tested and up to hundreds of times faster than the fastest competitor.
Critical strengths
- The low-level kernel delivers huge speedups over competitors.
- The authors prove that the algorithm is exact and the same subset is picked as in the baseline methods.
- The method can be used for all greedy optimization of facility-location objectives; not only in token pruning.
Critical weaknesses
- In the current state, the paper is more heavy engineering than scientific research. The idea of IO being a major bottleneck on modern GPUs is not new and low level, tiled kernels for specific algorithms have been around since FlashAttention. The paper also cites the newer Flash-KMeans, FLASH-MAXSIM, and TileMaxSim kernels. This paper is an application of the idea to facility location optimization.
- While the algorithm is shown to be exact, the paper is missing analysis on the runtime and complexity of this algorithm. While Section 4.3 presents the number of transfers needed for different , this is not sufficient to judge the algorithm, especially since is a dependent variable of and . Figure 3 shows that in many outer iterations, no token is added to the coreset (thus in some settings). As the scientific contribution of this paper, it would be nice to have mathematical analyses on the worst case and average case (under reasonable assumptions) depending on as well as worst case and average case runtime of the algorithm.
- The papers tables are inconsistent. For example SCOPE with and takes 1.25 ms in Table 2 and 2.18 ms in Table 3 (from what I understand both settings should use and multi-token inference). Similarly in Table 3 SCOPE with (3.43 ms) is slower than (3.10 ms) even though in the greedy solution, the subset of size is build by first building a subset of size and then growing it. If these differences come down to run-to-run variance, then this variance seems very large compared to the runtime (up to almost 100%) and all results should accurately report run-to-run variance in all tables to be able to judge the average-case speedup.
- The best baseline is an unoptimized pytorch loop. It would be nice to have the same algorithm as a low-level kernel implementation to see how much of the speedup comes from python/pytorch overhead compared to a low level kernel and how much gain the IO-awareness of the algorithm contributes.
- All experiments are run on A100 GPUs, it would be interesting to see how the results change on larger H or B-tier GPUs or consumer GPUs (like RTX 4090).
- The speedup numbers reported are for the token selection step alone. How much speedup is expected in an end-to-end pipeline setting? Is token selection actually the bottleneck there?
- The running averages in Figure 3 are very noisy and should probably be smoothed more.
Questions for authors
- What is the run-to-run variance of the method and baselines (i.e. under the exact same tokens and under same with different set of tokens from the same distribution)? What is the run-to-run difference of the number of outer iterations ?
- What is the average case and worst case number of outer iterations ? (from Remark 1) is only a termination argument, but can it actually happen, and if so under which circumstances? In the worst cases, is the algorithm still as fast or faster than a non-IO-aware GPU-based implementation of naive greedy?
2 comments
Feedback to Comments
Thank you for putting in the effort to answer all my questions. I think the new analysis should be a prominent part of the manuscript, especially the average-case runtimes and comparison to the low-level naive greedy implementation. I still think this is a bit of a judgement call, however in light of the new results I will update my recommendation to weak accept.
We thank the reviewer for the precise questions. Each is answered with new theory and measurements (revised PDF, Appendix C--J).
Q2/W2: worst- and average-case number of outer iterations r.
Lemma (Appendix C). Between two admissions, an outer iteration that admits nothing makes, in every tile, one stale bound above the next greedy gain Δ∗ exact (it falls below Δ∗). Hence the next greedy token is admitted within 1+maxtht outer iterations, where ht counts such blocking bounds in tile t.
Theorem. ⌈(k−1)/T⌉≤r≤(k−1)(⌈n/T⌉+1), i.e., O(nk/T) instead of the O(nk) termination argument; Flash Greedy never evaluates more than Naive Greedy's (k−1)n rows plus 2T per token.
It can happen: an adversarial family (targets in k levels with geometric weights; every admission leaves all stale bounds above the next gain) reaches 83--96% of the bound (Table 8), as it does for Lazy Greedy.
Average case: if the ∣H∣ blocking bounds fall into the T tiles uniformly, the expected wait is 1+E[maxload] of ∣H∣ balls in T bins, Θ(lnT/lnlnT) for ∣H∣≈T. An exact simulator, validated against the kernel (identical r and output), shows that on real matrices ∣H∣ is small, 78% of the admissions wait for no extra iteration, no wait exceeds the Lemma, and waits track the balls-into-bins prediction (Table 7). Over all 82 configurations r/(k−1) is 0.39--1.35 for images and video, and at most 10.5 for 20,000-instance pools with k=128 (6% of the bound).
Worst-case speed: on the adversarial family Flash Greedy needs ≈⌈n/T⌉ barrier-separated steps per token and is slower than an IO-aware naive kernel, but still 1.5--2.6$\times$ faster than the non-IO-aware PyTorch naive greedy (every row still comes from the fastest memory level, no temporaries).
Q1/W3: variance and inconsistent tables.
You are right. The submission mixed protocols (main table: 3 wall-clock calls including Python allocation; ablations: 5 back-to-back calls on one matrix), and its Table 3 values for the 1,296-token matrix (2.18/3.43/3.10 ms) are not reproducible. Every number is now re-measured with one protocol: CUDA events around a full call (host overhead included), warm-up of $\ge$2 calls and $\ge$0.3 s (an idle A100 needs this to reach its boost clock), 20 timed calls per sample, all samples, no concurrent CPU job. All tables report mean$\pm$std over samples. The same matrix takes 1.31/2.12/3.22 ms for k=128/256/512, monotone and consistent across tables. Run-to-run CV of Flash Greedy (same tokens) has median 0.14% and maximum 0.6%; across samples (same n,m,k) its CV is 0.1--5.4% (Table 11). r has zero run-to-run variance: the kernel is deterministic (fixed reduction order; 15 matrices × 10 runs gave one r and one output each), and across samples its std is 2--8% of the mean.
W4: the same algorithm as a low-level kernel.
We added fused Triton and CUDA naive greedy kernels replayed from CUDA graphs (no PyTorch overhead), a CUDA lazy greedy, and an IO-aware persistent naive kernel sharing everything with Flash Greedy except the candidate scheduling (Table 2). Removing PyTorch overhead and fusing gives 7.5--35$\times$; Flash Greedy is a further 3.8$\times$ (geometric mean) faster than the best fused kernel, and faster in all configurations. The scheduling adds 1.82$\times$ (L2) and 9.54$\times$ (HBM, up to 30.0$\times$) over the IO-aware naive kernel, which Section 5.3 now states.
W1: the contribution is an exact algorithm (tile-local lazy bounds, certified multi-token admission) with proofs of exactness, IO complexity and now a tight bound on r; the kernel implements it.
W5: T and the placement are read from the device and the code JIT-compiles for sm_89/sm_120; RTX 4090 GPU and RTX 5090 GPU results are shown in Table 15.
W6: with unchanged MMTok/SCOPE code in LLaVA-NeXT-7B, the released per-view solvers take 2--17% of a short-answer inference (Flash Greedy: 1.02--1.18$\times$ end to end), global selection over 2,880 tokens 32--52% (1.44--2.02$\times$) (Appendix H).
W7: the tokens-per-iteration figure (Figure 3 of the submission, Figure 2 of the revision) now shows the mean over all samples with a 25-iteration moving average and a ±1 std band.
In short, we thank you for the effort you have put into reading this paper.