acceptodds
Under review as a conference paper at ICLR 2027

Not All Tokens Deserve Equal Resolution: Score-Adaptive Indexing for Sparse Attention in Long-Context LLMs

Abstract

Indexer-based sparse attention reduces the cost of the main attention operator by retrieving only a small subset of the context, but the indexing stage itself is expensive for long sequence lengths. Hierarchical indexing reduces this cost by representing contiguous regions with compact summaries and refining only selected candidates. However, fixed-size partitions assume that every region can be represented equally well by one summary. While mean pooling is reliable when nearby keys are similar, it can obscure important token-level variation when they are not. We introduce SCALE (Score-Adaptive Indexing for Long-Context LLMs), a training-free hierarchical index that improves summary fidelity under a fixed budget by adapting which tokens are grouped together. For a fixed chunk, the mean key minimizes squared reconstruction error. For the DSA scoring function used in our evaluation, we further show that key dispersion controls an upper bound on the score approximation error induced by mean pooling. SCALE therefore splits high-dispersion regions into more chunks and merges homogeneous neighbors, while retaining the original mean representation and token-level indexer for exact refinement. Using the same number of chunks, SCALE improves Top- candidate recall over fixed-block indexing by – percentage points while consistently reducing score approximation error. With one summary per tokens on average, SCALE-64 improves pooled RULER accuracy from to and LongBench-v2 accuracy from to over fixed-block HISA-64, a recent strong fixed-block hierarchical baseline. On the 128K serving workload, the same configuration reduces end-to-end latency by relative to flat DSA (DeepSeek Sparse Attention), from s to s, while matching DSA on LongBench-v2 () and remaining close on RULER ( versus ).

Primary area:
foundation or frontier models, including LLMs
Keywords:
Long-Context LLMs, Sparse Attention, Hierarchical Indexing, Adaptive Resolution, Top-K Retrieval

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_Es63OpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper identifies a key limitation of hierarchical indexing for reducing the indexing cost of indexer-based sparse attention and proposes SCALE, a training-free adaptive indexing method. For approaches that mean-pool keys within fixed- size token segments, SCALE uses within-segment key dispersion (Key-SSE) as an indicator of approximation error. It splits high-dispersion segments and merges homogeneous adjacent segments using a dynamic-programming and Ward-merging procedure, thereby controlling the summary count, indexing cost, and refinement budget. The paper also establishes a theoretical connection between Key-SSE and the score approximation error of the DSA indexer, and integrates the method into an optimized SGLang serving pipeline. Under a fixed budget, SCALE substantially reduces TTFT relative to flat DSA while maintaining comparable downstream task accuracy.

Critical strengths

From clearly identifying limitation of existing fixed-size block-based methods, it converts an simple and intuitive idea (adaptive size indexing) into a practical and efficient algorithm as well as providing theoretical justification, and presents experiments that effectively demonstrate its benefits. Although questions remain regarding its practicality in production-scale LLM serving systems, I believe the work will be interesting and valuable to readers.

Critical weaknesses

The evaluation seems not yet establish that adaptive partitioning is preferable to strong fine-grained fixed-block indexing in practically relevant operating regimes. HISA is the only fixed-granularity hierarchical baseline evaluated, while QSA and LongCat-HI are discussed as closely related methods but omitted without explanation. Moreover, the main downstream quality and latency gains are demonstrated at relatively coarse average chunk lengths of 64 and 128, where fixed-block mean pooling is particularly susceptible to approximation error. Without matched quality–latency comparisons at finer granularities such as 4, 8, or 16 tokens—or a quantitative justification for why those operating points are impractical—it remains unclear whether SCALE’s additional partitioning complexity is preferable to simply using smaller fixed blocks. This uncertainty is compounded by the limited analysis of practical serving conditions, including continuous batching and the interaction between variable-length intervals and physical KV-page boundaries.

Questions for authors

Q1. Baseline coverage and choice of operating regime. QSA and LongCat-HI are identified as closely related fixed-granularity indexers but are omitted from the empirical comparison without explanation. More importantly, the largest downstream gains are reported at average chunk lengths of 64 and 128, where fixed-block mean pooling is naturally prone to substantial approximation error. Please clarify why these relatively coarse granularities represent practically meaningful operating points, rather than comparing SCALE primarily in a regime that particularly favors adaptive partitioning. Related systems such as QSA use much finer micro-blocks, which may already provide sufficient summary fidelity while retaining a simpler and potentially more hardware-friendly execution path. Could the authors provide matched quality–latency results at finer granularities such as 4, 8, or 16 tokens, or quantify why such configurations are impractical in terms of summary-scanning cost, memory usage, or end-to-end latency? Please also explain whether QSA and LongCat-HI were omitted because of architectural incompatibility, unavailable implementations, or an inability to match the summary and refinement budgets.

My concern is not just the absence of additional baselines, but whether the experiments establish a practically relevant regime in which adaptive partitioning is preferable to simply using finer fixed blocks. A convincing justification of the 64/128-token operating points, or matched fine-granularity quality–latency results, would improve my assessment.

Q2. How are SCALE’s variable-length logical intervals mapped to physical KV pages in the SGLang implementation? Are interval boundaries constrained or aligned to page boundaries? A comparison among unrestricted SCALE, page-aligned SCALE, and a fixed-page baseline—together with the physical page size, pages touched per query, and gather overhead—would help clarify the trade-off between partition fidelity and memory-access efficiency.

Q3. Equation (6) appears to optimize the Lagrangian relaxation. Could the authors clarify the role the λ\lambda-penalized objective, i.e., its relationship to the partitioning problem and what optimality guarantee the split–merge procedure provides?

7 comments
AuthorsOpenReview ↗

Response to Q1 (Part 1): Fine-Grained Baseline Evaluation

Q1. Comparison with Fine-Grained Baselines

We thank the reviewer for highlighting the importance of fine-grained fixed-block baselines and practically relevant operating points. Our expanded experiments show that SCALE achieves a more favorable accuracy–latency–summary-memory trade-off than fine-grained fixed-block indexing. At comparable accuracy, SCALE-16 achieves 7.3% lower TTFT and 81.1% less summary storage than HISA-4. At similar latency, SCALE-64 achieves higher accuracy on both RULER and LongBench-v2, with 75.1% less summary storage than HISA-16.

To further support these findings, we (1) extend our evaluation to finer granularities of 4, 8, and 16 tokens, (2) compare accuracy, latency, and memory across different configurations, and (3) add comparisons with LongCat-HI and a QSA-style block-selection baseline, both adapted to DeepSeek-V3.2. We also clarify how these adaptations differ from the original methods.

(1) Fine-grained quality–latency–memory comparisons.

We evaluate RULER on 364 examples (182 each at 32K and 128K) and LongBench-v2 on 401 examples. HISA, SCALE, and the adapted LongCat-HI baseline use the same candidate and refinement budgets of C=8,192 and K=2,048 tokens. All latency measurements are conducted on NVIDIA H200 GPUs.

Table 1. Accuracy, latency, and summary-memory comparison across configurations.

ConfigurationChunk SizeRULER Accuracy (%) ↑LongBench-v2 Accuracy (%) ↑TTFT (s) ↓TPOT (ms/token) ↓Summary (MiB/GPU) ↓Peak Memory (GiB/GPU) ↓Reserved Summary Pool (MiB/GPU) ↓
HISA12856.146.912.2314.467.86122.1042.27
SCALE12877.449.612.9614.137.80126.5734.89
HISA6465.646.412.45414.48715.73122.0482.07
SCALE6483.550.413.1213.85515.69126.7161.43
HISA1682.949.112.93914.70262.91122.42320.92
SCALE1686.251.113.8615.2247.62130.61220.66
HISA885.149.613.5514.878125.81122.74640.37
SCALE886.250.413.90516.68696.47128.34433.46
LongCat-HI858.1145.6414.84916.698126.75122.74640.37
HISA486.149.414.94615.356251.63125.761278.77
SCALE486.050.415.0716.84110.48136.26859.06
QSA-style486.5148.3813.50514.383251.63126.251278.77

Summary memory denotes the effective FP8 summary payload per GPU, excluding reserved capacity and partition-construction workspace. Peak GPU memory is reported separately. The table compares the evaluated inference configurations, including their respective attention policies. LongCat-HI-8 is a budget-matched adaptation, not its complete native system.

AuthorsOpenReview ↗

Response to Q1 (Part 2): Quality–Efficiency Trade-offs and Default Configuration

The expanded results reveal three informative operating points.

A. Highest-accuracy operating point: HISA-4 versus SCALE-16.

HISA-4 achieves the highest RULER accuracy among the evaluated HISA configurations (86.1%). However, SCALE-16 achieves slightly higher RULER accuracy (86.2%) and higher LongBench-v2 accuracy (51.1% vs. 49.4%), while providing:

  • 7.3% lower TTFT: 13.860 vs. 14.946 s.
  • Lower TPOT: 15.220 vs. 15.356 ms/token.
  • 81.1% less effective summary storage: 47.62 vs. 251.63 MiB/GPU.

Thus, even when HISA uses 4-token blocks to maximize retrieval quality, SCALE achieves comparable or higher downstream accuracy with lower inference latency and substantially smaller summaries.

B. Similar-latency operating point: SCALE-64 versus HISA-16.

SCALE-64 and HISA-16 achieve closely matched TTFTs (13.120 vs. 12.939 s, a difference of only 1.4%). At this similar latency, SCALE-64 provides:

  • Higher RULER accuracy: 83.5% vs. 82.9%.
  • Higher LongBench-v2 accuracy: 50.4% vs. 49.1%.
  • Lower TPOT: 13.855 vs. 14.702 ms/token.
  • 75.1% less effective summary storage: 15.69 vs. 62.91 MiB/GPU.

This comparison directly addresses whether reducing the size of fixed blocks is sufficient: SCALE provides higher downstream quality at comparable first-token latency, with lower decoding latency and a substantially smaller summary footprint.

C. Fastest HISA operating point: HISA-128 versus SCALE-128.

HISA-128 achieves the lowest TTFT among the evaluated HISA configurations. At the same average chunk granularity, SCALE-128 achieves:

  • 21.3 percentage points higher RULER accuracy: 77.4% vs. 56.1%.
  • Higher LongBench-v2 accuracy: 49.6% vs. 46.9%.
  • Comparable effective summary storage: 7.80 vs. 7.86 MiB/GPU.
  • Lower TPOT: 14.130 vs. 14.460 ms/token.

SCALE-128 incurs a modest 6.0% TTFT increase (12.960 vs. 12.230 s), but substantially improves retrieval quality while maintaining nearly identical summary-storage requirements.

Together, these comparisons show that SCALE's advantages are not limited to coarse-granularity comparisons. SCALE offers favorable operating points at both comparable accuracy and comparable latency, with substantially reduced summary-storage requirements relative to fine-grained fixed-block indexing.

(2) Why choose an average chunk length of 64?

We select SCALE S8M64 as our default because it provides a practical balance among downstream accuracy, inference latency, and summary storage.

Our measurements reveal a clear trade-off:

  • From SCALE-128 to SCALE-64: RULER accuracy improves from 77.4% to 83.5% (+6.1 percentage points), while TTFT increases by only 0.160 s.
  • From SCALE-64 to SCALE-16: RULER accuracy improves by a further 2.7 percentage points, but TTFT increases from 13.120 to 13.860 s, TPOT increases from 13.855 to 15.220 ms/token, and summary storage increases from 15.69 to 47.62 MiB/GPU.

Thus, S8M64 retains much of the accuracy benefit of finer partitioning while avoiding its additional latency and memory costs.

This trade-off is also consistent with HISA's original design motivation. HISA recommends B=128 and m=64 as a practical default to balance retrieval quality and indexing efficiency.

For fixed-block indexing, the number of summaries scales approximately as N/B. At a 128K context length, reducing B from 64 to 4 increases the number of summaries from 2,048 to 32,768, a 16× increase.

Our measurements confirm the corresponding costs: reducing HISA's block size from 64 to 4 increases TTFT from 12.454 to 14.946 s and effective summary storage from 15.73 to 251.63 MiB/GPU.

Therefore, fine-grained fixed blocks are not inherently impractical, but their accuracy improvements incur substantially higher summary-scanning and storage costs. SCALE instead allocates finer partition resolution selectively, providing a more favorable trade-off at its default S8M64 configuration.

AuthorsOpenReview ↗

Response to Q1 (Part 3): Additional Baselines and Memory Overhead

(3) Additional baseline comparisons: LongCat-HI and QSA.

LongCat-HI. We additionally adapt the hierarchical indexing component of LongCat-HI to DeepSeek-V3.2. Following its original design, we use 8-token summary sub-blocks and 128-token pages.

The original LongCat-HI long-context configuration selects 1,024 pages. For a controlled comparison under the DSA pipeline, we reduce this to 64 pages, matching SCALE's candidate-token budget of C=8,192, followed by token-level refinement to K=2,048. The results of this budget-matched adaptation are reported in Table 1.

We explicitly identify this implementation as a budget-matched adaptation of LongCat-HI's hierarchical retrieval component, rather than a reproduction of its complete native system, which additionally incorporates streaming-aware and cross-layer indexing mechanisms.

At the same 8-token summary granularity, SCALE-8 achieves:

  • Higher RULER accuracy: 86.2% vs. 58.11%.
  • Higher LongBench-v2 accuracy: 50.4% vs. 45.64%.
  • Lower TTFT: 13.905 vs. 14.849 s.
  • Comparable TPOT: 16.686 vs. 16.698 ms/token.
  • Lower effective summary storage: 96.47 vs. 126.75 MiB/GPU.

These results favor SCALE under the evaluated budget-matched DSA configuration. We do not interpret them as a direct comparison against the complete native LongCat-HI system.

QSA. Native QSA uses a separately trained 4-token block-level indexer and a backbone trained with block-sparse attention. In contrast, SCALE reuses DeepSeek-V3.2's pretrained token-level DSA indexer without additional training.

Moreover, QSA directly selects 4-token blocks for attention, whereas SCALE uses chunk-level filtering followed by token-level refinement from C=8,192 candidate tokens to K=2,048 selected tokens.

Consequently, integrating native QSA into DeepSeek-V3.2 would require additional model training or architectural modifications. Conversely, evaluating SCALE on Qwen3.8-Flash-Next would require adapting its trained block-level selection mechanism to support variable-length chunks and token-level refinement. A comparison across the two native backbones would additionally conflate indexing effects with differences in the underlying models.

We therefore use HISA-4 as the controlled fine-grained fixed-block baseline, retaining the same DeepSeek-V3.2 model, pretrained indexer, and token-level refinement pipeline. A separate direct 4-token block-selection experiment using the DeepSeek indexer is treated only as a mechanism ablation, not as an evaluation of native QSA.

(4) Partition-construction and GPU-memory overhead.

We further distinguish effective summary storage from allocated summary capacity, partition-construction memory, and total peak GPU memory.

At the default S8M64 configuration, SCALE requires 15.69 MiB/GPU of effective summaries and reserves a 61.43 MiB/GPU summary pool. Adaptive partition construction additionally uses 203.26 MiB/GPU of persistent buffers and up to 118.16 MiB/GPU of temporary workspace.

In comparison, HISA-16 requires 62.91 MiB/GPU of effective summaries and reserves a 320.92 MiB/GPU summary pool, without SCALE's additional partition-construction machinery.

While SCALE substantially reduces summary storage, its partition-construction buffers can increase total peak GPU memory, as reported in Table 1. We explicitly separate these components to characterize the memory trade-off accurately.

Summary.

The expanded experiments directly address the reviewer's central concern: whether adaptive partitioning offers practical advantages over simply reducing fixed-block size.

At HISA's highest-accuracy operating point, SCALE achieves comparable or better downstream quality with lower latency and 81.1% less summary storage. At comparable latency, SCALE-64 improves downstream accuracy over HISA-16 while reducing summary storage by 75.1%.

The additional LongCat-HI comparison broadens the evaluation, while the QSA discussion clarifies the architectural and training constraints that prevent a faithful same-model comparison.

Overall, these results establish that SCALE provides practically meaningful quality–latency–summary-memory trade-offs beyond coarse-granularity operating points, and that its adaptive partitioning offers favorable alternatives to the evaluated fine-grained fixed-block indexers.

We have incorporated the expanded chunk-granularity comparison into Section 4.5 and Figure 7, with the complete quality, latency, and memory results provided in Appendix J (Tables 12–13). The corresponding revisions are highlighted in blue.

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

The paper introduces SCALE , a training-free hierarchical indexing method designed to accelerate sparse attention in long-context Large Language Models. While existing systems compress history into uniform, fixed-size blocks, SCALE argues that regions with high token-level variation suffer from severe summary distortion when mean-pooled. SCALE dynamically allocates its summary budget by splitting heterogeneous text regions into smaller chunks and merging homogeneous neighbors into larger chunks.

Contributions

  1. Proposes using Key-SSE to measure chunk representation fidelity, mathematically proving that key dispersion controls an upper bound on score approximation errors for the DeepSeek Sparse Attention scoring function.
  2. Implements a two-stage method consisting of a Lagrangian dynamic programming split to identify high-dispersion regions, followed by a Ward-merging step to greedily eliminate redundant boundaries until a precise target summary count is reached.
  3. Develops CUDA-graph-compatible kernels.

Validation & Results

Tested using DeepSeek-V3.2 across long-context benchmarks like RULER and LongBench-v2:

  1. it significantly improved pooled RULER accuracy from 65.3% to 82.1% and LongBench-v2 accuracy from 46.4% to 50.4% over HISA-64.
  2. On LongBench-v2, SCALE-64 fully matched the accuracy of the exact, uncompressed flat DSA indexer (50.4%).
  3. On a 128K context workload, SCALE-64 reduced end-to-end latency by 36% relative to flat DSA (from 65.30s to 41.69s) while maintaining a nearly identical decoding token-to-token latency as fixed-block baselines.
Critical strengths

The authors do not just use key dispersion as a heuristic; they provide a formal mathematical foundation proving that the Key-SSE directly controls the root-mean-square score approximation error induced by mean pooling under the DeepSeek Sparse Attention framework. This theoretical alignment is crucial because Key-SSE relies entirely on stored index keys and can be computed before future queries arrive. In long-context systems, query-dependent indexing introduces massive serving overhead. Proving that an offline, query-independent metric reliably bounds online scoring errors resolves a fundamental architectural dilemma—allowing the system to optimally position chunk boundaries without needing to see the query beforehand.

Critical weaknesses

Tight Architectural Coupling and Model Specificity

The entire mathematical foundation and the empirical validation are strictly tailored to DeepSeek's Sparse Attention scoring function and Multi-head Latent Attention architecture.

Disconnect Between Theoretical "Exact" Algorithm and "Relaxed" Serving Path

There is a significant gap between the theoretical algorithm analyzed in the text and the one actually deployed for latency measurements. The paper's mathematical insights rely on an "exact-count" construction bracket search with exact-count repair. However, to avoid host-device synchronization and maintain CUDA graph safety, the actual serving path uses a "relaxed" schedule rounds.

Questions for authors

Your system design employs a "dense-final" policy, which retains full, exact flat DSA scoring for the final prompt chunk (the last 8,192 tokens) that determines the first generated token. In many long-context benchmarks , key details or retrieval triggers are often located near the very end of the prompt context.

  1. To isolate the true efficacy of your adaptive partitioning algorithm on historical tokens, what is the downstream accuracy (on RULER and LongBench-v2) if the "dense-final" policy is disabled?

  2. Specifically, how much of the reported 16.8 percentage point accuracy gain over HISA-64 is uniquely attributable to your adaptive algorithm versus being shielded by keeping the final 8K tokens exact?

4 comments
AuthorsOpenReview ↗

Response to W1 & W2: Architectural Scope and Implementation Guarantees

We thank the reviewer for the constructive feedback. We clarify SCALE's architectural scope, distinguish its theoretical construction from its serving implementation, and examine the contributions of adaptive partitioning and the dense-final policy.

W1. Architectural Coupling and Model Specificity

Our current analysis and implementation are instantiated for DeepSeek Sparse Attention (DSA), with evaluations on both DeepSeek-V3.2 and GLM-5. These experiments provide evidence across two DSA-based models.

MLA, adopted by DeepSeek-V2/V3, Kimi K2, and GLM-5, reduces KV-cache memory through compressed latent representations. In its MQA mode, query heads share latent KV entries. DSA uses a trained indexer to aggregate scores across indexer heads and select a shared token set. We have added this background and relevant references to Section 2.1 ("Indexer Setup") of the revised manuscript, with the changes highlighted in blue.

SCALE accelerates this indexing process by organizing historical keys into adaptive contiguous partitions, filtering candidates using chunk summaries, and applying the original token-level indexer to the selected candidates. Although Key-SSE partitioning is not inherently restricted to MLA, transferring SCALE's scoring approximation, analysis, and system benefits to other indexers requires further adaptation and evaluation. We will make this scope explicit in the revised manuscript.

W2. Exact-Count Construction vs. Relaxed Serving Implementation

The two variants share the Key-SSE objective and split–merge framework but differ in how they enforce partition-count constraints.

Exact-count construction. For any fixed penalty, the dynamic-programming split stage globally minimizes the penalized objective over admissible dyadic partitions. Bracket search and count adjustment enforce the prescribed interval counts. When the DP directly produces the target number of intervals, the splitting stage is also globally optimal for the corresponding fixed-budget objective. Otherwise, greedy count adjustment achieves the target count without necessarily preserving this optimality. The subsequent Ward merging is also greedy and does not guarantee global optimality of the final merged partition.

Relaxed serving implementation. To avoid host–device synchronization and maintain CUDA Graph compatibility, the deployed implementation uses a fixed-round search schedule without exact-count repair. It follows the same partitioning objective and guarantees full prefix coverage and at most TT valid summaries, but neither exactly TT summaries nor globally optimal Key-SSE.

We agree that guarantees established for the exact-count construction should not automatically be attributed to the relaxed serving implementation. We will explicitly distinguish these variants and their guarantees in the revised algorithm description and clarify that all reported serving latencies are measured using the relaxed implementation.

AuthorsOpenReview ↗

Response to Q1 & Q2: Dense-Final Ablation and Accuracy Attribution

Q1. Downstream Accuracy Without Dense-Final

We agree that the dense-final policy may influence downstream accuracy, particularly when relevant information appears near the end of the prompt.

Dense-final is a deliberate component of our system design: it preserves exact token-level DSA indexer scoring for the final 8,192 prompt tokens while applying accelerated indexing to earlier tokens. Preserving recent-context information is also a common motivation in sparse-attention designs, such as the local-window branch of Native Sparse Attention (NSA).

Nevertheless, to isolate the effectiveness of adaptive partitioning on historical tokens, we conducted additional experiments with dense-final disabled.

Table 1. Accuracy with and without dense-final (%).

PolicyMethodRULER Accuracy (%) ↑RULER 128K Accuracy (%) ↑RULER 32K Accuracy (%) ↑LongBench-v2 Accuracy (%) ↑
All-sparseHISA-6465.650.880.546.4
All-sparseSCALE-64 (S8M64)68.853.684.047.1
Dense-finalSCALE-64 (S8M64)83.579.587.550.4

Importantly, SCALE continues to outperform HISA when dense-final is completely disabled.

Under all-sparse indexing, SCALE-64 improves accuracy over HISA-64 by 3.2 percentage points on RULER overall (2.8 at 128K and 3.5 at 32K) and 0.7 percentage points on LongBench-v2.

These results demonstrate that adaptive partitioning provides an accuracy benefit even when all prompt tokens are processed using sparse indexing.

Q2. Attribution of the Reported Accuracy Improvement

We agree that the full accuracy improvement should not be attributed solely to adaptive partitioning.

The new experiments distinguish two contributions.

(1) Adaptive partitioning without dense-final.

Under the all-sparse policy, SCALE-64 improves RULER accuracy over HISA-64 by 3.2 percentage points and LongBench-v2 accuracy by 0.7 percentage points.

This comparison demonstrates the benefit of SCALE's adaptive indexing independently of dense-final.

(2) Additional improvement from dense-final.

For SCALE-64, enabling dense-final increases:

  • RULER accuracy: 68.8% to 83.5% (+14.7 percentage points).
  • LongBench-v2 accuracy: 47.1% to 50.4% (+3.3 percentage points).

The dense-final improvement is particularly pronounced on RULER-128K, where accuracy increases from 53.6% to 79.5%.

Thus, dense-final accounts for a substantial part of the complete system's accuracy improvement. However, the positive all-sparse results confirm that adaptive partitioning contributes independently of this policy.

We will revise the manuscript to explicitly distinguish the contribution of adaptive partitioning from that of dense-final, rather than attributing the full end-to-end improvement to partitioning alone.

Overall, the additional experiments confirm two complementary conclusions. First, SCALE improves the quality of sparse token retrieval even without dense-final. Second, combining adaptive partitioning with dense-final provides a stronger end-to-end solution.

Furthermore, our expanded fine-granularity experiments demonstrate favorable quality–efficiency trade-offs: at comparable RULER accuracy, SCALE-16 achieves 7.3% lower TTFT and 81.1% lower summary storage than HISA-4; at similar latency, SCALE-64 achieves higher downstream accuracy with 75.1% less summary storage than HISA-16.

Together, these results support the effectiveness of SCALE as a complete system and demonstrate its advantages over the evaluated fixed-chunk alternatives.

Thank you for your response. Your additional experiments have addressed some of my concerns; I will maintain my positive score.

Thank you for carefully considering our response and for updating your assessment. We sincerely appreciate your constructive feedback, which has helped us further clarify Scale's contributions and provide a more comprehensive empirical evaluation.

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

he paper proposes SCALE, a hierarchical indexing method that reduces the cost of sparse-attention indexing in long-context LLMs without retraining the model. It measures the error in each mean summary using Key-SSE: the sum of squared distances from token keys to their chunk's mean key. It uses dynamic programming on a tree to split chunks and Ward's criterion to merge adjacent chunks, keeping the number of summaries within a fixed budget. For each query, SCALE scores the chunk summaries to select a fixed number of candidate tokens. The original DSA indexer then scores these tokens individually. The theory gives a Lipschitz bound linking Key-SSE to the error in approximating DSA scores. The experiments measure candidate recall, task performance on RULER and LongBench-v2, performance on GLM-5, and end-to-end runtime with SGLang on H20 GPUs. SCALE-64 performs better than HISA-64 on downstream tasks with the same target number of summaries. It also runs faster than flat DSA on long inputs, although its prefill and end-to-end latency are higher than HISA-64's.

Critical strengths
  1. Adaptive chunking with a fixed number of chunks. Fixed-length chunking might, for example, group every 64 tokens into a chunk and average their key vectors to form its summary. In some chunks, most token keys are close to the mean, so it represents them well. In others, the token keys have a large total squared distance from the mean, and averaging can hide individual token features. The authors measure this difference using Key-SSE and use it to decide where to split and merge chunks. They create smaller chunks where the mean represents the tokens poorly and merge other chunks, without increasing the total number of chunks. The method uses only the keys of past tokens, so it can build the chunks before future queries arrive and requires no model retraining.
  2. An inference implementation that limits additional overhead. The authors select a fixed number of candidate tokens even when chunk lengths differ. This keeps the number of tokens in the next scoring step fixed. They also reuse statistics for existing tokens and prepare the next set of chunk boundaries while the model continues its other calculations. This avoids repeating work and reduces waiting. These choices make adaptive chunking usable during inference. The end-to-end evaluation helps assess whether the quality gains justify the extra runtime and is a useful addition to the chunking method.
Critical weaknesses
  1. Missing comparisons with richer chunk summaries. Keeping mean summaries and the number of chunks fixed helps test the effect of changing chunk boundaries. However, fixed chunks could also use richer summaries to avoid missing high-scoring tokens when selecting candidates. Examples include UNIQUE's correction based on how much keys vary within a chunk and QUEST's minimum and maximum key values in each dimension. The paper does not compare these alternatives using the same DSA indexing process. Table 6 tests box and radius information as ways to decide where to split chunks; it does not test using this information to score chunks and select candidate tokens. The results therefore show that adaptive chunking is useful, but do not establish its advantages over richer summaries in task performance, runtime, and memory use.
  2. Missing comparisons of quality at similar runtimes. Table 10 shows that SCALE-64 takes longer than HISA-64 in the end-to-end test. The key question is: given about the same amount of time, does computing adaptive chunk boundaries or scoring more fixed chunks give better downstream quality? Figure 5(a) compares candidate recall for fixed chunks of 8 and 32 tokens, but the paper does not report downstream quality or end-to-end runtime for these smaller chunks. The comparison should use the same input and output lengths, measure actual runtime, and report the extra memory required by both approaches.
Questions for authors
  1. Have you compared fixed chunks with richer summaries, such as using both the mean key and a measure of how much token keys vary, or storing the minimum and maximum key values in each dimension? If the original DSA indexer still scores the candidate tokens individually, how do these alternatives compare with SCALE in downstream quality, total runtime, and memory needed for summaries?
  2. With the same input and output lengths, can HISA using more, smaller fixed chunks achieve similar quality in about the same measured end-to-end time as SCALE? Please use the same hardware and prompt-processing method, and report the extra memory each approach needs for summaries and for constructing chunks.
  3. How were the 401 LongBench-v2 examples used by all methods selected from the 503 questions? Why were the remaining 102 excluded, and were the selection rules set in advance?
5 comments
AuthorsOpenReview ↗

Comment 1 — W1 / Q1. Comparisons with richer chunk summaries

We thank the reviewer for the constructive feedback. We have expanded our experiments to address the two main concerns: (1) comparisons with richer fixed-chunk summaries and (2) downstream quality at comparable runtime. We also clarify the LongBench-v2 evaluation split.

W1 / Q1. Comparisons with richer chunk summaries

We agree that Table 6 examines the use of richer information for partition construction, rather than for chunk scoring and candidate selection. To address this distinction, we implemented two additional fixed-chunk baselines within the same DSA indexing pipeline:

  • UNIQUE-style: Mean-key summaries with a correction based on within-chunk key variation.
  • QUEST-style: Per-dimension minimum and maximum key summaries.

Both variants retain the original DSA token-level indexer to score the selected candidate tokens. Since the official implementation of UNIQUE is not publicly available, and QUEST's released implementation is not directly compatible with the DSA indexing pipeline, we adapt their respective summary-scoring strategies to DSA. We therefore use the "-style" designation to clarify that these are DSA-adapted implementations rather than exact reproductions of the original systems.

Table 1. Comparison with richer chunk summaries.

MethodChunk BoundariesSummaryRULER Acc (%) ↑LongBench-v2 Acc (%) ↑TTFT (s) ↓TPOT (ms/token) ↓Summary Storage (MiB/GPU) ↓Peak GPU Memory (GiB/GPU) ↓
HISA-64FixedMean65.646.412.4714.4815.73119.0
SCALE-64 (S8M64)AdaptiveMean83.550.413.1213.85515.69119.7
UNIQUE-styleFixedMean + σ62.045.113.3114.4116.20119.0
QUEST-styleFixedMin/Max60.245.418.3414.55122.00119.7

Our UNIQUE-style baseline augments HISA's fixed-chunk mean scoring with a standard-deviation correction (α = 0.5), while retaining the same DSA token-level refinement. Setting α = 0 recovers HISA's mean-only scoring rule. However, a nonzero correction does not guarantee better candidate ranking, as it may promote high-variance but query-irrelevant chunks, particularly under DSA's signed head aggregation. Thus, the lower accuracy reflects the evaluated configuration rather than an inherent disadvantage of richer summaries.

SCALE-64 achieves 83.5% RULER accuracy and 50.4% LongBench-v2 accuracy with its standard inference policy, outperforming both richer-summary baselines in the reported evaluations. SCALE-64 also achieves lower TTFT than UNIQUE-style (13.12 vs. 13.31 s) and QUEST-style (13.12 vs. 18.34 s).

These results suggest that enriching fixed-chunk summaries alone does not reproduce the performance of the complete SCALE framework under the evaluated configurations.

Regarding memory, SCALE-64 requires 15.69 MiB/GPU of summary storage, compared with 15.73 MiB/GPU for HISA-64, 16.20 MiB/GPU for UNIQUE-style, and 122.00 MiB/GPU for QUEST-style. Table 1 also reports their peak GPU memory consumption.

AuthorsOpenReview ↗

W2 / Q2. Quality at comparable runtime (Part 1: Expanded evaluation)

W2 / Q2. Quality at comparable runtime

We agree that comparing only methods with the same average chunk size does not fully establish the quality–latency trade-off. We therefore extended the downstream evaluation to chunk granularities of 128, 64, 32, 16, 8, and 4, reporting accuracy, measured latency, summary storage, and partition-construction workspace.

Measurement protocol. We evaluate all methods on DeepSeek-V3.2 using 8×H200 GPUs, with identical 131,072-token inputs, 128 generated tokens, batch size 1, and Radix Cache disabled. We report median TTFT and TPOT over repeated runs.

TTFT is measured from client request submission to receipt of the first token, including first-token decoding and transmission. TPOT is the elapsed time between receiving the first and last tokens, divided by 127. Task accuracy is evaluated separately on RULER and LongBench-v2; the synthetic input is used for controlled latency measurements.

Table 2. Performance and memory comparison across chunk granularities.

TTFT denotes time to first token, and TPOT denotes time per output token. All memory measurements are reported in MiB per GPU, taking the maximum across TP8 ranks.

ConfigurationRULER Accuracy (%) ↑LongBench-v2 Accuracy (%) ↑TTFT (s) ↓TPOT (ms/token) ↓Summary Storage (MiB/GPU) ↓Allocated Summary Pool (MiB/GPU) ↓Peak Construction Workspace (MiB/GPU) ↓
HISA-12856.146.912.2314.4277.8642.270
SCALE-128 (S32M128)77.449.612.9614.0987.8034.8935.70
HISA-6465.646.412.44714.46615.7382.070
SCALE-64 (S8M64)83.550.413.1213.85515.6961.43118.16
HISA-3275.4348.8812.58514.52331.45161.690
SCALE-32 (S4M32)84.6949.3814.4314.60330.89114.51231.81
HISA-1682.949.112.93914.63162.91320.920
SCALE-16 (S2M16)86.251.113.8615.11647.62220.66458.29
HISA-885.149.613.5514.853125.81640.370
SCALE-8 (S4M8)86.250.414.6316.42996.47433.46232.19
HISA-486.149.414.94615.279251.631278.770
SCALE-4 (S2M4)86.050.415.0716.765110.48859.06458.29

The summary-storage column reports the effective memory required by the stored summaries. The allocated summary pool includes reserved capacity, while peak construction workspace captures additional temporary memory used during partition construction. These quantities are reported separately.

(1) Comparable latency: SCALE-64 versus HISA-16.

SCALE-64 and HISA-16 have closely matched TTFTs of 13.12 s and 12.939 s, respectively, a difference of only 1.4%. SCALE-64 also achieves lower TPOT (13.855 vs. 14.631 ms/token).

At this similar latency, SCALE-64 achieves:

  • Higher RULER accuracy: 83.5% vs. 82.9%.
  • Higher LongBench-v2 accuracy: 50.4% vs. 49.1%.
  • 75.1% less summary storage: 15.69 vs. 62.91 MiB/GPU.
  • 80.9% less allocated summary-pool memory: 61.43 vs. 320.92 MiB/GPU.

SCALE-64 additionally uses 118.16 MiB/GPU of temporary construction workspace, which is reported separately.

(2) Comparable RULER accuracy: SCALE-16 versus HISA-4.

SCALE-16 and HISA-4 achieve nearly identical RULER accuracy (86.2% vs. 86.1%). However, SCALE-16 offers:

  • 7.3% lower TTFT: 13.860 vs. 14.946 s.
  • Lower TPOT: 15.116 vs. 15.279 ms/token.
  • Higher LongBench-v2 accuracy: 51.1% vs. 49.4%.
  • 81.1% less summary storage: 47.62 vs. 251.63 MiB/GPU.
  • 82.7% less allocated summary-pool memory: 220.66 vs. 1278.77 MiB/GPU.

SCALE-16 requires an additional 458.29 MiB/GPU of peak temporary workspace during partition construction.

Overall, these experiments show that reducing fixed-chunk size can substantially improve HISA's accuracy, but at the cost of increased summary storage. SCALE provides favorable operating points that achieve comparable or higher quality at similar or lower latency while using substantially less persistent summary memory. The temporary memory cost of adaptive partition construction is explicitly accounted for.

To ensure a consistent hardware basis for latency comparisons, we have re-benchmarked the serving and operator workloads on NVIDIA H200 GPUs, as the original H20 system is no longer available. End-to-end serving uses eight H200 GPUs with tensor parallelism 8, while operator microbenchmarks use a single H200. The corresponding timing results have been updated in the revised manuscript, including Figure 6 and Tables 3, 4, and 11. Downstream accuracy scores are retained from the corresponding quality evaluations.

We have incorporated the expanded chunk-granularity comparison into Section 4.5 and Figure 7, with the complete quality, latency, and memory results provided in Appendix J (Tables 12–13). The corresponding revisions are highlighted in blue.

AuthorsOpenReview ↗

Q3. Selection of the 401 LongBench-v2 examples

Due to the substantial computational cost of long-context evaluation across multiple methods and configurations, we evaluated a fixed subset of 401 questions from the original 503 LongBench-v2 questions. To ensure a representative and reproducible selection, the split was stratified by difficulty (Easy/Hard) and length (Short/Medium/Long). Within each of the six strata, we excluded 17 questions using domain-balanced round-robin sampling and SHA-256 ordering of sample IDs, leaving 401 questions for evaluation. The subset was determined before the reported SCALE comparisons, independently of any method's predictions or accuracy. All methods were evaluated on exactly the same 401 questions. We will provide the sample-ID lists and split-generation script for reproducibility.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Our Work and Rebuttal

Dear AC, SAC, and Program Chairs,

We thank the reviewers for their careful evaluation. We summarize SCALE's contribution, the rebuttal evidence, and the discussion status.

Core contribution. SCALE is a training-free hierarchical index for DSA built on one observation: a mean-pooled summary is reliable only where keys are similar, so a fixed summary budget should be spent where keys are heterogeneous. Unlike fixed-block indexes such as HISA, SCALE splits high-dispersion regions and merges homogeneous neighbors according to key dispersion (Key-SSE), while keeping mean summaries and the original token-level indexer for refinement. Key-SSE is query-independent and controls an upper bound on the DSA score error induced by mean pooling, so partitions are built before queries arrive. At inference, SCALE uses a dense-final policy: exact token-level DSA scoring for the final 8,192 prompt tokens and the adaptive index for all earlier tokens. On DeepSeek-V3.2 with one summary per 64 tokens on average, SCALE-64 reaches 83.5% on RULER and 50.4% on LongBench-v2 (HISA-64: 65.6% / 46.4%), matches flat DSA on LongBench-v2, and reduces 128K end-to-end latency by 37.4% relative to flat DSA (20.96 s → 13.12 s).

Evidence added during rebuttal:

  • Adaptive partitioning versus finer fixed blocks — V6QA W2/Q2; Es63 Q1. We swept average chunk sizes from 128 to 4, reporting accuracy, TTFT, TPOT, and memory (Sec. 4.5, Fig. 7, App. J). At matched TTFT (13.12 vs. 12.94 s for HISA-16), SCALE-64 scores 83.5% vs. 82.9% on RULER and 50.4% vs. 49.1% on LongBench-v2 with 75.1% less summary storage (15.69 vs. 62.91 MiB/GPU). At matched RULER accuracy (86.2% vs. 86.1%), SCALE-16 has 7.3% lower TTFT than HISA-4 (13.86 vs. 14.95 s), higher LongBench-v2 accuracy (51.1% vs. 49.4%), and 81.1% less summary storage. SCALE's construction buffers (203 MiB persistent, up to 118 MiB temporary per GPU for SCALE-64) are reported separately.
  • Comparison with UNIQUE, QUEST, LongCat-HI, and QSA — V6QA W1/Q1; Es63 Q1. DSA-adapted UNIQUE-style (mean + σ) and QUEST-style (min/max) fixed-chunk baselines reach 62.0% / 45.1% and 60.2% / 45.4% (RULER / LongBench-v2), versus 83.5% / 50.4% for SCALE-64; QUEST-style needs 122.00 MiB/GPU of summaries versus 15.69. A budget-matched LongCat-HI adaptation (8-token) reaches 58.1% / 45.6%, versus 86.2% / 50.4% for SCALE-8. A QSA-style 4-token block-selection ablation is comparable on RULER (86.5% vs. 86.2% for SCALE-16) and lower on LongBench-v2 (48.4% vs. 51.1%), with 5.3× the summary storage. These are DeepSeek-V3.2 adaptations, not the native systems; native QSA requires a separately trained indexer and backbone.
  • Contribution of each component — dLdB Q1/Q2. We added an all-sparse ablation that disables dense-final. Adaptive partitioning alone improves over HISA-64 by 3.2 points on RULER (68.8% vs. 65.6%; +2.8 at 128K, +3.5 at 32K) and 0.7 points on LongBench-v2 (47.1% vs. 46.4%). Dense-final adds a further 14.7 points on RULER and 3.3 on LongBench-v2, with the largest effect on RULER-128K (53.6% → 79.5%). The revision reports the two components separately.
  • What the theory guarantees — dLdB W2; Es63 Q3. The revision states each variant's guarantees separately. (i) Exact-count construction: for any fixed penalty, the DP globally minimizes the penalized objective over dyadic partitions; a computable certificate bounds suboptimality for the fixed-budget problem and is zero when the DP returns the target count; Ward merging is greedy. (ii) Relaxed serving path: same Key-SSE objective with a fixed-round schedule for CUDA Graph compatibility; it guarantees full prefix coverage and at most the budgeted number of summaries. All serving latencies use the relaxed path.
  • KV-page mapping and the LongBench-v2 subset — Es63 Q2; V6QA Q3. Logical intervals are independent of the 64-token physical KV pages. Unrestricted SCALE touches 7.9% more index-key pages than a fixed-page partition, with comparable TPOT (13.866 vs. 13.861 ms/token) and fused re-scoring time (9.78 vs. 9.85 μs/layer). The 401-question LongBench-v2 subset is stratified by difficulty and length, was fixed before the reported comparisons, and is identical for all methods; we will release the ID list and split script.

Discussion status and scope. All three reviewers assign 3, weak acceptance. Es63 raised their score after the rebuttal. SCALE targets DSA-based models (dLdB W1); our evidence covers DeepSeek-V3.2 and GLM-5, which the revision states explicitly.

Each claim is tied to evidence: the chunk-size sweep shows that full SCALE offers better accuracy–latency–storage operating points than finer fixed blocks; the all-sparse ablation quantifies adaptive partitioning and dense-final separately; the certificate states what the construction guarantees; the SGLang measurements establish the end-to-end gain. All additional results and clarifications will be incorporated into the revision.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.