- 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 -penalized objective, i.e., its relationship to the partitioning problem and what optimality guarantee the split–merge procedure provides?
7 comments
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.
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.
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.
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.