acceptodds
Under review as a conference paper at ICLR 2027

Facility Location Submodular Optimization on GPU for Token Subset Selection

Abstract

Token subset selection for vision-language model and in-context learning is often modeled as facility location maximization: choose of source tokens that best cover target tokens under a similarity matrix. Its objective function is monotone submodular, so the greedy is near-optimal. However, every existing solver is slow. CPU libraries submodlib and apricot run the lazy greedy as a serial chain of row reads. Moreover, PyTorch loops recompute all marginal gains on the GPU at every iteration, moving the whole similarity matrix through HBM times. To improve the execution speed, we present Flash Greedy, an IO-aware persistent CUDA kernel that runs the entire selection in one launch. The similarity matrix is tiled over the streaming multiprocessors (SM) and placed in SRAM, L2 cache or HBM by its size. Every SM keeps a private copy of the coverage vector and evaluates exactly one candidate token per iteration. In addition, a replicated selection loop admits several tokens per grid barrier. A bool position vector is used to certify which candidate gains are still exact, thereby selecting the multiple tokens. Most importantly, our method returns exactly the naive greedy solution, and we give its IO complexity per placement regime. In the evaluation, we use three similarity matrices from MMTok, SCOPE, and Selective Annotation; whose token features are extracted from image, video, and text. Flash Greedy returns the same subset as the submodlib, apricot and original PyTorch implementation. However, Flash Greedy is faster than the PyTorch loops, and faster than the best CPU library.

Primary area:
infrastructure, software libraries, hardware, systems, etc.
Keywords:
Facility Location, Submodular Optimization, Token Subset Selection

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_QCLKOpenReview ↗
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 n,m,T,r,kn,m,T,r,k, this is not sufficient to judge the algorithm, especially since rr is a dependent variable of n,mn, m and kk. Figure 3 shows that in many outer iterations, no token is added to the coreset (thus r>kr > k 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) rr depending on n,m,kn, m, k as well as worst case and average case runtime of the algorithm.
  • The papers tables are inconsistent. For example SCOPE with n=1296n=1296 and k=128k=128 takes 1.25 ms in Table 2 and 2.18 ms in Table 3 (from what I understand both settings should use t=108t=108 and multi-token inference). Similarly in Table 3 SCOPE with k=256k=256 (3.43 ms) is slower than k=512k=512 (3.10 ms) even though in the greedy solution, the subset of size 512512 is build by first building a subset of size 256256 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 n,m,kn,m,k with different set of tokens from the same distribution)? What is the run-to-run difference of the number of outer iterations rr?
  • What is the average case and worst case number of outer iterations rr? r=O(nk)r = O(nk) (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

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 rr.

Lemma (Appendix C). Between two admissions, an outer iteration that admits nothing makes, in every tile, one stale bound above the next greedy gain Δ∗\Delta^{*} exact (it falls below Δ∗\Delta^*). Hence the next greedy token is admitted within 1+max⁡tht1+\max_t h_t outer iterations, where hth_t counts such blocking bounds in tile tt.

Theorem. ⌈(k−1)/T⌉≤r≤(k−1)(⌈n/T⌉+1)\lceil (k-1)/T\rceil \le r \le (k-1)(\lceil n/T\rceil+1), i.e., O(nk/T)O(nk/T) instead of the O(nk)O(nk) termination argument; Flash Greedy never evaluates more than Naive Greedy's (k−1)n(k-1)n rows plus 2T2T per token.

It can happen: an adversarial family (targets in kk 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∣|H| blocking bounds fall into the TT tiles uniformly, the expected wait is 1+E[max⁡load]1+\mathbb{E}[\max\text{load}] of ∣H∣|H| balls in TT bins, Θ(ln⁡T/ln⁡ln⁡T)\Theta(\ln T/\ln\ln T) for ∣H∣≈T|H|\approx T. An exact simulator, validated against the kernel (identical rr and output), shows that on real matrices ∣H∣|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)r/(k-1) is 0.39--1.35 for images and video, and at most 10.5 for 20,000-instance pools with k=128k=128 (6% of the bound).

Worst-case speed: on the adversarial family Flash Greedy needs ≈⌈n/T⌉\approx\lceil n/T\rceil 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/512k=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,kn,m,k) its CV is 0.1--5.4% (Table 11). rr has zero run-to-run variance: the kernel is deterministic (fixed reduction order; 15 matrices ×\times 10 runs gave one rr 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 rr; the kernel implements it.

W5: TT 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\pm1 std band.

In short, we thank you for the effort you have put into reading this paper.

Reviewer_QCLKOpenReview ↗

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.

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

This paper proposes Flash Greedy, an IO-aware persistent CUDA implementation of greedy facility-location maximization for token subset selection. The method partitions the similarity matrix across GPU streaming multiprocessors, exploits the memory hierarchy, and uses cached marginal-gain bounds and bit-vector checks to admit multiple candidates while preserving the exact greedy selection sequence. Experiments on similarity matrices from MMTok, SCOPE, and Selective Annotation report substantial speedups over CPU greedy implementations and original PyTorch baselines, while returning identical selected subsets. The paper also provides an exactness argument, IO complexity analysis, and component-level ablations.

Critical strengths
  1. The paper addresses a practical computational bottleneck in facility-location-based token selection. The combination of persistent execution, parallel candidate evaluation, and memory-aware tiling provides an effective approach to accelerating the greedy procedure.

  2. Unlike approximate submodular optimization methods, Flash Greedy aims to preserve the original greedy sequence. The reported speedups are substantial across different matrix sizes and selection budgets, without changing the resulting subsets.

  3. The experiments cover multiple application settings and memory-placement regimes. Ablations on tile count and multi-token admission, together with runtime breakdowns, help explain the performance improvements.

Critical weaknesses
  1. The principal GPU baseline consists of the original PyTorch greedy loops. Comparisons against fused CUDA, Triton, or other optimized GPU implementations would help establish how much of the improvement comes from the proposed algorithmic techniques rather than kernel fusion and implementation differences.

  2. The benchmarks measure selection latency with precomputed similarity matrices. The paper does not quantify overall inference improvements in complete vision-language pipelines, where feature extraction, similarity computation, and model execution may dominate runtime.

  3. Experiments are conducted on an NVIDIA A100. Since performance depends on SM count, shared-memory capacity, cache size, and synchronization overhead, evaluation on additional GPU architectures would strengthen the generality of the results.

  4. The supplementary CUDA implementation appears to permit additional candidate refreshes during multi-token admission, beyond the simplified procedure in Algorithm 2. The authors should clarify how these operations affect the stated row-read and IO complexity bounds.

  5. The experiments focus on unweighted facility-location selection. In particular, the SCOPE comparison sets saliency weights to unity, rather than evaluating its complete weighted selection objective. Extending the implementation or evaluation to commonly used weighted variants would strengthen the practical applicability claims.

Questions for authors
  1. How does Flash Greedy compare against an optimized fused CUDA or Triton implementation of greedy facility-location selection?

  2. What speedups are obtained when integrating Flash Greedy into complete MMTok or SCOPE inference pipelines, including similarity construction and model execution?

  3. How are additional candidate refreshes during multi-token admission accounted for in the IO analysis, and do they affect the stated complexity bounds?

  4. How does performance change across GPUs with different SM counts, cache capacities, and synchronization characteristics?

  5. Can the proposed multi-token admission mechanism support weighted facility-location objectives while preserving exact greedy selection?

2 comments

We thank the reviewer for the constructive and precise review. Every point is addressed with new results in the revised PDF.

Q1/W1: optimized fused CUDA/Triton baselines.

We added (i) a fused Triton naive greedy and (ii) a fused CUDA naive greedy (one gain+argmax kernel over all rows plus one update kernel per token, no temporaries), both replayed from a CUDA graph; (iii) a CUDA lazy greedy; and (iv) an IO-aware persistent naive kernel that shares all of Flash Greedy's design (tiles, SRAM/L2/HBM placement, exact float64 gains) except the candidate scheduling (Section 5.3, Table 2, Appendix E). Over the 82 configurations Flash Greedy is 3.8$\times$ faster (geometric mean) than the best of (i)--(iii) and faster in all configurations. The scheduling itself contributes 1.82$\times$ (L2 regime) and 9.54$\times$ (HBM regime, up to 30.0$\times$) over (iv).

Q3/W4: refreshes and the IO bound.

You are right: the kernel refreshes a candidate whose bool vector overlaps the admitted token's (one row read against the updated yy), which Algorithm 2 omitted. We (a) rewrote Algorithm 2 to the implemented inner loop and the exactness proof as an invariant (after every admission, all live candidate gains are exact); (b) corrected the HBM bound to 8nm+4m(E+F+k−1)8nm+4m(E+F+k-1) with E≤TrE\le Tr candidate rows and F≤(T−1)(k−1)F\le(T-1)(k-1) refreshed rows, where the measured F/EF/E is 2.7--18.6% (Table 9); (c) evaluated the literal Algorithm 2 (stop at the first overlap, F=0F=0, exactly 8nm+4m(Tr+k)8nm+4m(Tr+k)): same output, slightly more outer iterations, and −5-5% to +3+3% time relative to the default. Refreshes do not change the complexity: in the SRAM/L2 regimes the HBM traffic stays independent of kk. We also prove r≤(k−1)(⌈n/T⌉+1)r\le(k-1)(\lceil n/T\rceil+1) (Appendix C, an adversarial family reaches 83--96% of it), so even in the worst case E≤TrE\le Tr is at most Naive Greedy's (k−1)n(k-1)n rows plus 2T2T per token; on real data $r/(k-1)=$0.39--1.35 for images and video.

Q2/W2: complete pipelines.

With LLaVA-NeXT-7B and the verbatim MMTok/SCOPE similarity construction and greedy loops (only the solver replaced; 24 images; Appendix H): in the released per-view pipelines the solver is 2--17% of a short-answer inference and Flash Greedy reduces the end-to-end latency by 1.02--1.18$\times$; for global selection over 2,880 tokens the solver is 32--52% and the end-to-end speedup is 1.44--2.02$\times$. Vision encoding and prefill are unchanged; similarity construction costs 0.3--3 ms; for 64-token answers decoding dominates (solver $\le$12%).

Q5/W5: weighted objectives, exactly.

(a) Target-weighted FL ∑jwjmax⁡i∈Ssij\sum_j w_j\max_{i\in S}s_{ij} is FL on wjsijw_j s_{ij}, so the kernel applies unchanged; MMTok's [P;αQ][P;\alpha Q] is already of this form. (b) For SCOPE's rule arg⁡max⁡iaiΔ(i∣S)\arg\max_i a_i\Delta(i\mid S) with saliency ai≥0a_i\ge0, a cached aiΔa_i\Delta remains an upper bound by submodularity, and it is unchanged when the bool vectors do not overlap, so certified multi-token admission stays exact (Proposition, Appendix I). The kernel now takes aa as input. With SCOPE's real [CLS] saliency it matches a float64 implementation of the rule on all 336 problems (per view and global) and is 3.6--8.2$\times$ (per view) and 43--82$\times$ (global) faster than SCOPE's loop.

Q4/W3: other GPUs.

Nothing is hard-coded: TT is the SM count, the placement uses the device's shared memory and L2 size, and the CUDA code is JIT-compiled for the GPU (sm_80/89/120). Measured proxies on the A100: with half the tiles (as on a GPU with half the SMs) Flash Greedy needs 1.5--1.7$\times$ more outer iterations and 1.1--1.4$\times$ more time (Table 3); moving the SRAM tiles to L2 costs only about 1% (Appendix D), since the kernel is synchronization-bound on chip. So more SMs and a larger L2 (72 MB on RTX 4090: more matrices in the L2 regime) should help, and less per-block SRAM (99 KB) should matter little. The performance on RTX 4090 and RTX 5090 is shown in Table 15.

In short, we thank you for the effort you have put into reading this paper.

Thank you for the detailed rebuttal and substantial additional experiments.

My initial assessment was a marginal weak accept, with reservations regarding the optimized GPU baselines, end-to-end benefits, and implementation details. The additional experiments and clarifications have satisfactorily addressed my concerns and significantly strengthened the paper.

I am now more confident in my weak accept recommendation.

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

The paper presents FLASH GREEDY, a GPU solver for facility-location-based token subset selection. It combines parallel candidate evaluation, cached marginal-gain upper bounds, and a Boolean-support test that allows multiple candidates to be admitted without recomputing their gains. The selection process is implemented in a persistent CUDA kernel with memory-aware data placement. Experiments across 73 configurations using similarity matrices from MMTok, a coverage-only version of SCOPE, and the facility-location baseline of Selective Annotation report substantial speedups over existing CPU libraries and original GPU PyTorch implementations while claiming identical greedy outputs.

Critical strengths
  1. A useful GPU design for accelerating greedy selection. Parallel candidate refresh and upper-bound certification address the sequential nature of traditional lazy greedy. The Boolean-support test further enables multiple candidates to be safely admitted without redundant gain computation. These mechanisms provide a meaningful algorithm–system design for accelerating an existing optimization procedure.

  2. Substantial reported speedups with informative ablations. The evaluation covers various matrix sizes and selection budgets. The multi-token admission ablation reports an additional 1.10–1.57× speedup over the authors' single-token variant, providing evidence that this mechanism contributes beyond the underlying parallel implementation.

Critical weaknesses
  1. The GPU comparisons do not sufficiently establish the incremental contribution of the proposed design. Facility-location maximization and lazy greedy are established techniques already employed in related work, including FLoC (ICLR 2026). The novelty of this paper therefore lies primarily in GPU parallelization and execution optimization. However, the external GPU baselines are original PyTorch naive-greedy implementations, including the torch.jit implementation used by MMTok. Although the paper includes tile-count and multi-token admission ablations, it lacks a separately optimized fused GPU naive-greedy baseline. The reported speedups combine several improvements, including parallel candidate scheduling, kernel fusion, and memory-aware execution. Without a comparably optimized GPU greedy baseline, it remains unclear how much additional benefit is attributable to the proposed scheduling strategy. This limits the assessment of the paper's incremental technical contribution.

  2. End-to-end benefits and application-level significance remain unclear. The evaluation measures selection latency after the similarity matrix is available, without demonstrating the benefit of replacing an existing solver in an unchanged application pipeline, such as MMTok or FLoC. Moreover, the SCOPE benchmark uses unit saliency rather than the original saliency-weighted selection rule, so equivalence with the full SCOPE method is not established. Repeating downstream accuracy evaluations may be unnecessary if identical model inputs are guaranteed, but the current experiments establish isolated solver speedups rather than meaningful end-to-end VLM inference gains.

Questions for authors
  1. How does FLASH GREEDY compare with a separately optimized fused GPU naive-greedy implementation under the same hardware and numerical precision? How much additional speedup comes specifically from parallel candidate scheduling?

  2. In an unchanged MMTok or FLoC pipeline, what fraction of the total runtime is spent on greedy selection, and how much does replacing the original solver reduce end-to-end inference latency, including similarity-matrix construction?

1 comment

We thank the reviewer for pinpointing the two questions that decide the contribution. Both are now answered with new experiments in the revised PDF (Section 5.3, Table 2, Appendix E, H, I).

Q1: fused GPU naive greedy at the same hardware and precision; contribution of the candidate scheduling.

We implemented four optimized GPU baselines: (i) naive greedy as a fused Triton kernel and (ii) as fused CUDA kernels (one gain+argmax kernel over all rows and one update kernel per token, no n×mn\times m temporaries), both replayed from a CUDA graph with capture excluded; (iii) a CUDA lazy greedy (parallel initialization, single-block pop/re-evaluate chain); (iv) an IO-aware persistent naive kernel: one cooperative launch with exactly Flash Greedy's tiles, SRAM/L2/HBM placement, replicated coverage vector and exact float64 gain arithmetic, re-evaluating all rows per token, i.e., Flash Greedy without the candidate scheduling. All CUDA solvers return identical sequences. On the A100, over all configurations (mean over all samples):

(1) PyTorch overhead and fusion: the best fused kernel is 7.5--35$\times$ faster than the PyTorch loops; Flash Greedy is a further 3.8$\times$ faster (geometric mean) than the best of (i)--(iii), and faster in all configurations.

(2) Candidate scheduling ((iv) →\to Flash Greedy): 1.82$\times$ in the L2 regime (n≈3n\approx3k; up to 2.6$\times$) and 9.54$\times$ in the HBM regime (n≥4.6n\ge4.6k; up to 30.0$\times$), growing with nn, mm, kk because (iv) still moves 4nm4nm bytes per token (e.g., 363 vs.\ 18.9 ms for 1,024 of 10,816 video tokens).

Lazy evaluation alone does not transfer to the GPU: the lazy chain re-evaluates 12--849 rows per admitted token one at a time and is 6.9--32$\times$ slower than Flash Greedy.

Q2: end-to-end benefit in an unchanged pipeline, including similarity construction. We ran LLaVA-NeXT-7B end to end on 24 TextVQA/POPE images with the verbatim similarity construction and greedy loops of MMTok and SCOPE, replacing only the solver (Appendix H):

(1) Released per-view selection (5 problems of 576 tokens): the greedy solver is 2--17% of a short-answer inference; Flash Greedy reduces end-to-end latency by 1.02--1.18$\times$.

(2) Global selection over all 2,880 tokens (our kernel benchmark): the solver is 32--52% of the inference and Flash Greedy gives 1.44--2.02$\times$ end to end; with SCOPE's loop at K=640K=640, pruning is slower than not pruning (435 vs.\ 421 ms), with Flash Greedy it takes 216 ms.

(3) Similarity construction costs 0.3--3 ms; with 64-token answers decoding dominates (solver $\le$12%).

MMTok's selections, hence model inputs and answers, are identical on every sample. Greedy selection is thus a moderate cost of the released per-view pipelines, and the largest single stage of the inference for global selection (short answers). We evaluated MMTok and SCOPE, the two pipelines whose selection code we could run unchanged.

SCOPE saliency. Flash Greedy now accepts per-token score weights ai≥0a_i\ge0: aiΔ(i∣S)a_i\Delta(i\mid S) keeps the upper-bound property and the bool-vector certificate, so it reproduces SCOPE's full rule exactly (Proposition, Appendix I). With SCOPE's real [CLS]-attention saliency on max⁡(cos⁡,0)\max(\cos,0) it matches a float64 implementation of the rule on all 336 problems and is 3.6--8.2$\times$ (per view) and 43--82$\times$ (global) faster than SCOPE's loop.

Contribution beyond parallelization. The paper contributes an exact algorithm (tile-local lazy bounds with certified multi-token admission) with proofs of exactness and IO complexity and, new, the bound r≤(k−1)(⌈n/T⌉+1)r\le(k-1)(\lceil n/T\rceil+1) on the outer iterations, which an adversarial family attains to 83--96% (Appendix C).

In short, we thank you for the effort you have put into reading this paper.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.