acceptodds
Under review as a conference paper at ICLR 2027

SANTA++: Sampling Attention through Representative Keys

Abstract

Attention often concentrates on a small subset of tokens in the context, but which subset matters changes from one query to the next. To exploit this changing structure, we introduce SANTA++, a training-free stochastic attention method that uses representative keys for memory-efficient selection without scanning the entire key-value (KV) cache. Cached keys are organized into teams, and the query scores one representative from each team to decide which teams to sample. We compute exact attention scores within the sampled teams and reweight each team's contribution by the inverse of its inclusion probability. This importance sampling correction estimates attention over the full cache, with a sampling budget that lets us trade memory reads for accuracy. Remarkably, with 32 or 64 sampled teams, SANTA++ uses 16% to 22% of dense attention's KV reads and retains 94% to 99% of the dense-attention baseline's scores on LongBench v2 and HELMET's retrieval-augmented generation subset, and 85% to 91% on RULER, with Qwen2.5-7B-Instruct at 32K context. With 31 sampled teams, our GPU implementation delivers a attention speedup over the dense FlashAttention baseline at 32K context. By reducing the number of cache entries read, SANTA++ in principle complements architectures with compressed KV representations, such as multi-head latent attention. Our kernels are available at: https://anonymous.4open.science/r/santapp-triton-demo-020D.

Primary area:
foundation or frontier models, including LLMs
Keywords:
sparse attention, stochastic attention, long-context LLM inference, KV cache, importance sampling, memory bandwidth, training-free inference, representative keys

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_ZxsUOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper introduces SANTA++, which is a training-free stochastic sparse-attention method for reducing KV Cache reads during long context autoregressive decoding. Prompt keys are divided into parent groups and then teams. It reads all original keys and values within selected teams by their inclusion probabilities. Results show promising accuracy-efficiency trade-offs and a 1.69x attention-kernel speedup, though benefits are task-dependent and exclude prefill, preparation overhead, and end-to-end latency.

Critical strengths
  1. It can be applied to existing transformers without retraining or modifying model weights.

  2. It scores only one representative key per team before deciding which parts of the prompt cache to read

  3. The sampling budget directly controls how many teams are evaluated

  4. It preserves near-dense performance on LongBench v2 and HELMET RAG while reporting lower logical KV access.

  5. Well-motivated representative design

Critical weaknesses
  1. The reported 1.69x gain only covers one attention-operator, not full-model generation latency or throughput

  2. Most results report logical KV-vector accesses rather than measured bandwidth or hardware memory behavior

  3. The GPU implementation maintains packed KV copies and metadata, adding about 71.98 MB per layer in the tested configuration.

  4. Dense prefill, clustering, team construction, cache packing, temporary allocation, and related latency are excluded from the timing results

  5. Increasing the sampling budget does not consistently improve accuracy, making budget selection less predictable

Questions for authors
  1. Can you report end-to-end decoding latency and throughput, including team construction, k-means, KV packing, and workspace allocation?

  2. Can you measure actual peak memory usage, rather than only logical KV accesses?

  3. How does performance generalize beyond Qwen2.5-7B, 32K contexts, batch size one?

  4. What explains the substantial degradation on specific tasks such as JSON KV retrieval and harder RULER variants

  5. How sensitive are results to parent size P, representative count R, and grouping method.

3 comments

Thank you for the encouraging assessment and concrete requests. We now measure up to 1.23× whole-model decoding speedup (INT4 weights, FP16 KV, batch eight), and report full-request latency, physical traffic, and memory use. References below are to the revised paper.

W1, W4, Q1 — Full-model latency and preparation.

Since submission, we have extended and optimized the kernels and integrated them into batched full-model generation. We now run contiguous S=1024 in all 28 Qwen2.5-7B layers, with approximately 32K inputs, 512 outputs, and exact attention to newly generated tokens. On the RTX 5090 Laptop GPU, matched dense Flash SDPA → SANTA++ measurements (replicated prompts; sequential prefill) are:

Weights / batchDecode ms/stepDecode tokens/sFull request s
FP16 / 329.33 → 28.11102.3 → 106.741.92 → 41.43
INT4 / 830.44 → 24.71262.9 → 323.985.11 → 82.49

We measure 1.044×/1.232× whole-model decoding speedups and full-request ratios of 1.012×/1.032× (Tables 8, 36–38). FP16 full requests are roughly break-even; see Appendix G.9 for timing uncertainty. Full requests include dense prefill and all cache preparation. Preparation takes 118/284 ms; contiguous grouping avoids k-means. Prefill accounts for 65%/84% of request time, explaining the smaller total gains. INT4 weights enable batch eight within the GPU's 24 GB memory; both methods use the same quantized checkpoint and FP16 KV cache. With INT4 weights, SANTA++ decoding is slower than dense at batch one (0.81×), but faster at batch four (1.13×) and eight (1.23×; Table 8). Section 4 and Appendix G give the implementation and timing details.

Separately, FP16 contiguous S=1024 retains 95.1% of dense RULER aggregate score at 28.2% access and gives 1.38× attention-operator speedup (Table 7).

W2 — Physical memory traffic.

Nsight Compute measurements cover the complete attention operator, including routing and intermediate buffers. On the profiled 32K CWE input, S=1024 reduces total DRAM read/write traffic from 62.55 to 18.42 MiB, a 70.6% reduction. S=128 uses 9.44 MiB (Appendix G.7, Table 44).

W3, Q2 — Cache storage and measured memory.

Our updated implementation stores the prompt KV cache only once, reordered by team. At FP16 batch three, peak allocated memory is 22.134 GiB for both methods, with 0.755 GiB of additional routing data and workspace for SANTA++. At INT4 batch eight, peak allocated memory is 21.810 GiB for both, with 2.012 GiB of additional storage for SANTA++. Prefill determines the peak in these runs. The extra storage at batch one is 0.252 GiB for the full model (Table 9; Appendix G.4).

Q3 — Generalization.

The main timing sweep covers FP16 batches 1–3 and INT4-weight batches 1, 4, and 8. Accuracy evaluations cover 8K and 32K. Beyond Qwen, DeepSeek-V2-Lite-Chat retains 98.1% of the dense aggregate on three RULER-8K tasks at 86.2% logical access to its shared latent cache (Appendix H).

Q4 — Hard retrieval failures.

The revised paper makes the remaining task-level losses explicit: contiguous S=1024 scores 60.2% on MK-NIAH-3 versus 89.6% dense, despite retaining 95.1% of the aggregate (§3). To investigate the failure, matched 50-prompt diagnostics at 32K with k-means parents and S=128 give:

ControlJSON-KVMK-NIAH-3
Instrumented baseline46%16%
Force answer-containing teams92%66%
Exact team-mass oracle96%94%
Dense98%88%

All sparse controls select 32 teams. Both interventions recover substantial accuracy, pointing to team selection as a promising improvement target. Appendix C.1 gives the intervention details.

W5, Q5 — Budget and grouping sensitivity.

Increasing the budget changes which teams are sampled and can change subsequent generation, so individual task scores need not improve monotonically. However, aggregate RULER-32K scores increase across both grouping sweeps (Tables 4–5).

We now evaluate sensitivity to parent size PP and representative count RR on two RULER-8K tasks at S=128S=128 (Appendix C.3):

PRScore (%)Access (%)
32492.6220.40
16290.3818.22
164 (ours)96.0025.68
8497.8836.08
16897.3836.32

Our default P=16,R=4P=16, R=4 provides a favorable accuracy–access trade-off: finer teams improve accuracy by only 1.4–1.9 points while increasing access by over 10 percentage points. Coarser teams reduce access but incur larger accuracy losses.

For grouping policy, contiguous S=1024S=1024 achieves 79.40% on RULER-32K at 28.16% access, versus 80.40% at 34.44% for k-means. Contiguous grouping also avoids k-means preparation, making it our preferred GPU implementation.

Thanks for the answers. I will maintain my positive score.

Thank you for your continued support and for taking the time to consider our revised results. We appreciate your constructive questions, which helped us improve both the experimental evaluation and the clarity of the paper.

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

SANTA++ is a training-free method for sparse attention during decoding. It partitions prompt keys into teams, samples teams using actual-key representatives, and evaluates their members with inverse-inclusion correction. Experiments show an accuracy–access trade-off on long-context benchmarks.

Critical strengths
  1. The paper addresses a practical bottleneck: selecting relevant tokens can itself require expensive key-cache reads.
  2. The estimator derivation carefully distinguishes unbiased unnormalized sums from the generally biased normalized output.
  3. Evaluation reports full budget sweeps and task-level results, making the accuracy–access trade-offs visible.
Critical weaknesses
  1. The main comparisons are against SDPA and SANTA. Direct comparisons with representative-based retrieval and importance-sampling methods, such as InfLLM, Squeezed Attention, and MagicPIG, are missing.
  2. The central representative-key claim is not isolated experimentally. The centroid comparisons change both the grouping and the routing representatives. They also incur different KV access costs, making the source of the improvement difficult to identify.
  3. Aggregate scores hide substantial failures. At 32K with S=128S=128, the k-means variant reduces MK-NIAH-3 accuracy from 89.60% to 16.80% and JSON KV accuracy from 96.80% to 45.60%. These losses limit the practical appeal of the lowest-access settings.
  4. The efficiency evidence is too narrow. The reported speedup uses one fixed layer-level workload and excludes preparation costs. The implementation also adds 71.98 MiB of persistent storage per layer beyond the original KV cache. End-to-end benefits remain unverified.
Questions for authors
  1. With identical team memberships, how do actual-key representatives compare with team centroids and randomly selected representatives?
  2. How much does inverse-inclusion correction improve accuracy over the same sampler without correction?
  3. How does SANTA++ compare with closely related methods at matched KV access or matched accuracy?
  4. What are the end-to-end latency and peak-memory costs, including clustering, packing, and a growing generated suffix? Do higher-accuracy budgets still provide a speedup?
  5. How were the LongBench v2 scores and confidence intervals computed from 503 distinct prompts? Please clarify the number of runs and the bootstrap resampling unit.
4 comments

Thank you for the controlled-comparison suggestions. They helped us separate the effects of team construction and representative choice. References below are to the revised paper.

W2 / Q1 — Representative choice with identical teams.

You are right that the original comparison confounded grouping and representatives. We now hold team memberships fixed and vary only the representative. Centroids have lower routing KL than leaders on all three diagnostic tasks; random members are worse (Table 1). On all 13 RULER-8K tasks, with 100 prompts per task:

Representative, S=128Score (%)Access (%)
Selected leader84.1624.97
Team centroid83.0224.02
Random member77.2824.56

These results support representative-guided team sampling. Leaders and centroids both route effectively; leaders remain our default because they are already available from team construction and give competitive downstream accuracy. Their slightly higher scores across three budgets also use slightly more KV access. We revised §2.4 accordingly (Appendix B.2).

W1 / Q3 — Direct comparisons.

We evaluated our adaptations of Quest and MagicPIG in the same harness on all 13 RULER-32K tasks, with 500 prompts per task (Figure 2, Table 6, Appendix E):

MethodLogical access (%)Score (%)
SANTA++ contiguous, S=102428.1679.40
Quest, B=204826.8868.70
Quest, B=819254.8878.89
MagicPIG, (K_h=10, L=235)25.7778.91

SANTA++ uses 48.7% fewer logical KV reads than Quest at comparable accuracy. Every tested Quest setting has a higher-scoring, lower-access SANTA++ point. Access includes routing reads for SANTA++ and Quest. MagicPIG's sampling policy is simulated on GPU; its KV access is 25.77%, or 27.83% including estimated hash lookups. SANTA++ is stronger at low access and competitive near S=1024; MagicPIG is stronger at higher budgets.

Q2 — Removing inclusion correction.

With k-means parents, the same routing rule, and S=128, corrected/uncorrected scores are 85.21/83.97 at 8K and 68.88/71.11 at 32K, each on all 13 RULER tasks with 50 matched prompts per task. The uncorrected variant scores 2.23 points higher at 32K. Correction makes the unnormalized attention sums unbiased, but does not guarantee higher downstream task accuracy (Appendix C.2).

W3 — Hard retrieval failures.

We now make these failures explicit in §3. Contiguous S=1024 retains 95.1% of dense RULER aggregate score, but MK-NIAH-3 remains at 60.20% versus 89.60% dense. Higher budgets help: k-means JSON-KV rises from 45.60% at S=128 to 87.00% at S=512; k-means MK-NIAH-3 reaches 86.60% at S=2048. This recovery costs more access.

New 50-prompt diagnostics help explain the losses: at S=128, an exact team-mass oracle raises the instrumented baseline from 46% to 96% on JSON-KV and 16% to 94% on MK-NIAH-3. This points to better team selection as a promising improvement. Appendix C.1 describes the oracle and intervention settings.

W4 / Q4 — Full generation, preparation, and memory.

Since submission, we have optimized the kernels for higher budgets and added batched full-model generation. At S=1024, the FP16 attention operator is 1.38× faster while retaining 95.1% of dense RULER aggregate score. On an RTX 5090 Laptop GPU, full-model timing covers all 28 layers, approximately 32K inputs, and 512 outputs per sequence with a growing exact suffix (replicated prompts; sequential prefill):

Weights / batchDecode speedupFull-request seconds: dense → ours
FP16 / 31.044×41.921 → 41.427
INT4 / 81.232×85.109 → 82.493

FP16 full requests are roughly break-even; see Appendix G.9 for timing uncertainty. Full-request timing includes dense prefill and all preparation. Prefill accounts for 65%/84% of request time in these two settings, explaining the smaller total gains. INT4 weights enable batch eight within the GPU's 24 GB memory; both methods use the same quantized checkpoint and FP16 KV cache. The RULER accuracy sweep uses FP16 weights. Full timing details are in §4 and Appendix G.

Contiguous grouping avoids k-means, and cache preparation takes 118/284 ms. We now store the prompt KV cache only once, reordered by team. Additional routing data and workspace use 0.755/2.012 GiB. Both methods have the same peak memory: 22.134 GiB at FP16/batch three and 21.810 GiB at INT4/batch eight, because prefill sets the peak (Table 9; Appendix G.4).

Q5 — LongBench runs and intervals.

Each setting has four runs of the same 503 prompts. We average four binary outcomes per prompt, then average across prompts; invalid answers score zero. The 95% intervals use 10,000 prompt-bootstrap resamples, keeping each prompt's four outcomes together. Normalized intervals use paired prompt indices with SDPA.

AuthorsOpenReview ↗

Follow-up on revised results

Thank you again for your helpful suggestions. We have added the requested controlled ablations, direct baseline comparisons, and full-model measurements. Before discussion closes, would you consider updating your assessment in light of these results? We would be happy to clarify any remaining questions.

Thank you for the thorough rebuttal and new experiments. The Quest/MagicPIG comparison is useful addition. However, new results conflict with paper’s claims in three ways:

  1. Benefit of actual-key representatives remains unsubstantiated. On identical teams, centroids give lower routing KL than leaders on all three tasks, and downstream scores are within 1 point with overlapping CIs (Table 10 and 11). A flat k-means centroid baseline also performs close to SANTA++ in Table 11. The gains seem to come from fine-grained routing summaries.

  2. The inclusion correction does not improve accuracy. It gives +1.24 at 8K but −2.23 at 32K (CWE: −17.0) (Appendix C.2). Since normalized output is biased, it is unclear what correction contributes.

  3. Fewer KV reads do not brings practical speedup. End-to-end gains are 1.01–1.04× in FP16, and INT4 is slower at batch 1–2 (Table 8). These gains are within the reported timing uncertainty (Appendix G.9). Meanwhile, hard retrieval tasks (e.g., MK-NIAH-3) only recover at budgets near SANTA’s full-key-scan cost, and these budgets are not timed.

Given these points, I keep my current rating.

Thank you for the detailed follow-up. As reflected in the revised paper, team centroids have lower routing KL than leaders on identical teams, while inclusion correction has task-dependent effects on downstream accuracy (§2.4, Appendix C.2).

On practical speedup, the FP16 gains at batches 1–3 are modest, and INT4 decoding is slower at batches 1–2. At larger batches, however, matched INT4 weights and FP16 KV caches give 1.13× whole-model decoding speedup at batch four and 1.23× at batch eight (Table 8). The batch-eight gain is substantially larger than the 2.0–2.35% difference between timing sources noted in Appendix G.9. Full-request speedup is 1.032×, since dense prefill accounts for 81.7% of baseline runtime, consistent with Amdahl's law (Appendix G.3).

We have also added matched INT4 accuracy results across all 13 RULER tasks (Appendix I). On 641 batch-one prompts, SANTA++ scores 80.77% versus 84.09% dense (−3.33 pp, 95% CI [−5.14, −1.57]). On the 93-prompt batch-eight subset, it scores 85.64% versus 86.87% dense (−1.22 pp, 95% CI [−6.05, +3.61]).

Reviewer_7G4yOpenReview ↗
Rating
2(+1)
Confidence
3
Informativeness
1
Presentation
3
Soundness
2
Read review
Paper summary

SANTA++ is a training-free, query-dependent sparse attention mechanism for decoding that avoids scoring every cached key. At a high level, SANTA++ aims to reach the same kind of efficiency gains that KV eviction or compaction methods achieve by discarding entries, but instead by keeping the full cache resident and selecting which entries to read per query. After prefill, keys within each layer/KV-head are split into parent groups (via k-means or contiguous token spans), and within each group a small number of "representatives" (not based on a simple mean) are chosen. Every other member is assigned to its nearest representative's "team." At each decoding step, the query scores only the representatives (one key read per team), then samples the top-K teams based on a predetermined budget. Only the sampled teams' keys and values are read and used in attention computations. This generalizes SANTA (Lee et al., 2026), which samples from the exact per-key distribution after scoring every key; SANTA++ instead routes with a cheap per-team proxy, trading some approximation error for far fewer KV reads.

Evaluated with Qwen2.5-7B-Instruct on three long-context benchmarks, i.e., LongBench v2, HELMET, and RULER, SANTA++ retains most of dense SDPA's score at a fraction of its logical KV access — e.g., 91.07%–98.54% of RULER's aggregate score across a 19.95%–63.65% access sweep (Tables 2–4). A Triton kernel implementation gives a proof-of-concept 1.69× attention-operator latency speedup over FlashAttention SDPA on a single-layer, single-token decode experiment.

Critical strengths
  1. KV selection as a training-free alternative to KV eviction, validated across three long-context benchmarks. Rather than permanently discarding entries, SANTA++ keeps the full cache resident and selects which entries to read per query via a team-based routing scheme. A direct KL-divergence comparison (Table 1) favors this actual-key routing over the previously used centroid approximation. The method is validated across LongBench v2, HELMET, and RULER.
  2. A real GPU kernel implementation with hardware-measured speedup, not simulated FLOPs savings. The latency claim is backed by an actual Triton implementation benchmarked against a real FlashAttention baseline, with bootstrap confidence intervals, NCU occupancy/DRAM-throughput breakdowns per kernel (Table 14), and a sampled-reference correctness check (<4.30×10⁻⁶ max absolute output error vs. an independent reference implementation).
Critical weaknesses
  1. Insufficient data to support the main claim on inference speed-up. Since SANTA++ keeps the entire KV cache resident and only reduces how many entries are read per step, the inference speed-up is this method's whole value proposition, not a secondary benefit on top of memory saving — yet it rests on a single measurement that leaves three questions unanswered:

    • Representative operating point? The benchmark uses nominal budget S=124 (K=31 teams), which lands at essentially the lowest budget on the accuracy sweep (S=128) — exactly where Table 4 reports the weakest normalized scores of the entire RULER sweep (more than 10% abs accuracy loss). At minimum, a speedup-vs-S curve should be included so that readers can tell at what budget routing/selection overhead starts eroding or reversing the gain — a real concern given the MLA extension (Appendix F) already shows this crossover at S=1024 in a related setting (logical access reaching 101.89% of dense, while still trailing dense SDPA's own accuracy).
    • Does the gain hold over a real generation, not just one step? The measurement captures a single decode step (one query token, Appendix E), not an end-to-end multi-token generation, so it's unclear whether the per-step routing/selection overhead amortizes or compounds as decoding continues.
    • Does an attention-only speedup translate to a whole-model speedup? The benchmark replays one isolated attention layer (layer 14 of 28) and excludes the untouched MLP/FFN cost, so the relative gain on the attention operator alone may not reflect the end-to-end, whole-layer or whole-model decode-time speedup.
  2. No empirical comparison against other named KV-selection methods, including a learned alternative to its heuristic routing score. Related Work (Section 5) cites several conceptually adjacent approaches, e.g. InfLLM, Quest-style retrieval, and multiple centroid-based grouping methods, but the only baseline method benchmarked in Tables 2–4 is SANTA. There is also a design alternative the paper never considers: rather than SANTA++'s training-free, heuristic per-team routing score, other KV eviction methods use a small trained importance predictor — the same kind of lightweight gate Fast KVzip (Kim et al., 2026a) uses to predict per-token eviction importance directly from hidden states — which could plausibly be repurposed as a per-team/per-group selector here, at the cost of requiring offline training. More broadly, the paper never discusses how its selection-based approach itself — keeping the full cache resident and reading selectively, rather than permanently discarding entries — trades off against the dominant, more commonly used eviction or compaction paradigm (e.g., memory footprint, accuracy at matched budget, or applicability when memory rather than bandwidth is the bottleneck).

  3. Quantization composability is asserted, but never tested. Every headline KV% number (16.68% on LongBench v2, 38.49% on HELMET RAG, the 19.95%–63.65% RULER sweep, etc.) is a ratio of counts at a single, fixed cache precision (BF16/FP16) — not a memory/byte ratio. Related Work (§5) asserts quantization is "complementary" and that SANTA++ "can save memory traffic even when the cache already uses compact representations," but this claim is never tested: no experiment runs SANTA++ on top of a quantized cache (e.g., FP8/INT4, as in KIVI) to check whether the reported access savings actually compose with it.

Questions for authors

please see Weaknesses above

4 comments

Thank you for your engagement and thoughtful comments. We now measure 1.38× attention operator speedup at S=1024 and up to 1.23× whole-model decoding speedup (INT4 weights, FP16 KV, batch eight), alongside adapted selection baselines. References below are to the revised paper.

W1 — Higher-accuracy operating point and budget curve.

Since submission, we have extended and optimized the GPU implementation for higher sampling budgets and batched full-model generation. Table 7 reports the requested budget sweep, including routing and selection, for contiguous SANTA++ in FP16:

Nominal SRULER score (%)KV access (%)Attention speedup
12864.7215.031.80×
25670.5417.311.57×
51275.3721.371.44×
102479.4028.161.38×

Dense RULER scores 83.51%. We now emphasize S=1024, retaining 95.1% of the dense aggregate. This configuration scores 31.46% versus 32.11% dense on LongBench v2 and retains 97.6% of the dense HELMET RAG score, at 28–31% access (Table 2). Hard retrieval remains challenging: MK-NIAH-3 scores 60.2% versus 89.6% dense (Table 30). Attention speedup remains positive through S=1024.

Complete-operator profiling also reduces DRAM read/write traffic from 62.55 to 18.42 MiB at S=1024 on the profiled 32K CWE input—a 70.6% reduction (Table 44).

W1 — Whole-model generation and preparation.

We now integrate S=1024 into all 28 layers and generate 512 tokens per sequence from approximately 32K inputs, with a growing exact-attention suffix. Against matched dense Flash SDPA on an RTX 5090 Laptop GPU (replicated prompts; sequential prefill):

Weights / batchDecode speedupFull-request speedup
FP16 / 11.016×1.007×
FP16 / 31.044×1.012×
INT4 / 81.232×1.032×

At batch eight, decode throughput rises from 262.9 to 323.9 tokens/s. Dense prefill accounts for 84% of the request, so the full-request gain is smaller: 85.11 → 82.49 s. Full-request timing includes prefill and all cache preparation. Contiguous grouping avoids k-means; preparation takes 118 ms at FP16 batch three and 284 ms at INT4 batch eight (Tables 8–9).

INT4 weights let us evaluate batch eight within the GPU's 24 GB memory; dense and sparse runs use the same quantized checkpoint and FP16 KV cache. With INT4 weights, SANTA++ decoding is slower than dense at batch one (0.81×), but faster at batch four (1.13×) and eight (1.23×; Table 8). The accuracy sweep uses FP16 weights.

W2 — Direct baselines, learned routing, and cache retention.

We evaluated our adaptations of Quest (five budgets) and MagicPIG (twelve settings) in the same harness on all 13 RULER-32K tasks, with 500 prompts per task (§3, Figure 2, Appendix E):

Method / settingRULER score (%)Logical access (%)
SANTA++ contiguous / S=102479.4028.16
Quest / B=204868.7026.88
Quest / B=819278.8954.88
MagicPIG / (K_h=10, L=235)78.9125.77

SANTA++ uses 48.7% fewer logical KV reads than Quest at comparable accuracy. Every tested Quest setting has a higher-scoring, lower-access SANTA++ point. Access includes routing reads for SANTA++ and Quest. MagicPIG's sampling policy is simulated on GPU; its KV access is 25.77%, or 27.83% including estimated hash lookups.

At low access, SANTA++ scores 64.72% at 15.03%, versus MagicPIG's 54.12% at 16.33%. MagicPIG is stronger at higher budgets. SANTA++ offers a strong low-to-medium-access trade-off with compact representative routing.

Section 5 now discusses your proposed Fast KVzip-style learned team selector as future work. Our current method requires no auxiliary training.

SANTA++ keeps all prompt tokens available for later queries. Our updated implementation stores the prompt KV cache only once, reordered by team, with 0.252 GiB of additional routing data and workspace at batch one (Appendix G.4). Eviction reduces the cache's memory footprint; SANTA++ reduces the cost of reading it.

W3 — KV-cache quantization.

We appreciate the reviewer's point, and we revise our wording so we do not assert composability with quantized KV caches. Combining SANTA++ with a quantized KV cache is future work.

Thank you for the new measurements. The budget sweep and whole-model results confirm our concern: the 1.69× operator speedup was measured at S≈128, where RULER retention is 77–85%. At S=1024 (95% retention) the operator speedup falls to 1.38×, and decode-only whole-model gains are 1.016× at FP16/batch 1 and 1.044× at batch 3, so the quality-preserving operating point yields essentially no decoding speedup in the standard FP16 setting. The 1.23× figure requires INT4 weights at batch 8, a configuration whose accuracy is not evaluated (the accuracy sweep uses FP16 weights), and INT4/batch 1 is slower than dense (0.81×). The added Quest comparison is favorable, but MagicPIG is roughly at parity at 26–28% access, and baselines are compared only by the number of KV entries read, not by measured latency or memory traffic. Since the method keeps the full cache resident and its practical value rests solely on speed, we would raise our score from 1 to 2.

Thank you for the thoughtful follow-up and for engaging so closely with our new results. Your comments led directly to the budget sweep, whole-model measurements, and new baselines, and the paper is substantially stronger for it.

Additional INT4 accuracy results and performance context

We have added INT4 accuracy results and a full-request timing analysis to the revised manuscript.

INT4 accuracy. We evaluated the INT4-weight, FP16-KV configuration used for the 1.232× whole-model decoding speedup, with SANTA++ at S=1024S=1024 against matched dense Flash SDPA across all 13 RULER tasks:

BatchMatched promptsDense (%)SANTA++ (%)Difference (pp) [95% CI]
164184.0980.77−3.33 [−5.14, −1.57]
89386.8785.64−1.22 [−6.05, +3.61]

The table quantifies the accuracy trade-off directly at INT4, including the batch-eight speedup setting. Details are in Appendix I.

Larger-batch decoding. We agree that low-batch FP16 gains are modest. With INT4 weights, however, decoding improves from 0.81× at batch one to 1.13× at batch four and 1.23× at batch eight. Quantized weights reduce model-weight traffic, and batching amortizes weight reads, making KV-cache traffic relatively more important. This suggests larger-batch, long-context decoding as a promising regime, particularly on GPUs with greater memory capacity. Our full-request gain is 1.032× because sequential prefill accounts for 81.7% of the dense request; the breakdown agrees with Amdahl's law (Appendix G.3). Longer generations or more efficient prefill could expose more of the decoding benefit.

MagicPIG trade-off. Near our preferred operating point, SANTA++ and MagicPIG achieve comparable RULER scores: 79.40% at 28.16% access versus 78.91% at 27.83% (including estimated hash lookups). At tighter budgets, SANTA++ scores 64.72% at 15.03%, versus MagicPIG's 54.12% at 16.33% KV-only access. MagicPIG is stronger at higher budgets. These are useful complementary trade-offs, with SANTA++ particularly competitive when the KV-access budget is tight (§3, Appendix E).

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.