LycheeCluster: Efficient Long-Context Inference with Structure-Aware Chunking and Hierarchical KV Indexing

Dongfang Li; Zixuan Liu; Gang Lin; Baotian Hu; Min Zhang

cs.LGMar 9, 2026

LycheeCluster: Efficient Long-Context Inference with Structure-Aware Chunking and Hierarchical KV Indexing

Authors: Dongfang Li, Zixuan Liu, Gang Lin, Baotian Hu, Min Zhang

Organizations: Harbin Institute of Technology · University of Electronic Science and Technology of China

Abstract

The quadratic complexity of the attention mechanism and the substantial memory footprint of the Key-Value (KV) cache present severe computational and memory challenges for Large Language Models (LLMs) processing long contexts. Existing retrieval-based methods often compromise semantic integrity through fixed-size chunking and suffer from inefficient linear scanning. In this paper, we propose LycheeCluster, a novel method for efficient KV cache management. LycheeCluster preserves local semantic coherence via boundary-aware chunking and constructs a recursive hierarchical index rooted in the triangle inequality. This design transforms cache retrieval from a linear scan into a theoretically bounded, logarithmic-time pruning process, while a lazy update strategy supports efficient streaming generation. Experiments demonstrate that LycheeCluster achieves up to a 3.6x end-to-end inference speedup with negligible degradation in model performance, outperforming state-of-the-art KV cache management methods (e.g., Quest, ClusterKV). We will release our code and kernels after publication.

Figures & tables

Figure 1: Impact of retrieval granularity on semantic integrity. We illustrate the limitations of existing methods using a JSON retrieval query. (Left) Quest employs fixed-size pages that arbitrarily sever semantic boundaries. (Middle) ClusterKV uses token-level clustering that scatters locally coherent tokens into disjoint clusters based on vector variance. (Right) LycheeCluster (Ours) preserves the complete semantic unit via structure-aware chunking, ensuring precise retrieval.

Figure 2: Pilot Study on StrucText-Eval. We compare the standard Quest (fixed page) with a modified version using structure-aware chunks while keeping the scoring metric identical. The significant accuracy gain (e.g., +15.0% on JSON) confirms that preserving semantic integrity is a prerequisite for effective retrieval.

Figure 3: The overall pipeline of LycheeCluster . The left panel illustrates the bottom-up index construction during the prefill phase, where variable-length chunks are hierarchically clustered. The right panel demonstrates the top-down retrieval and incremental update during the decoding phase.

Method	Overall	Short	Medium	Long
Full Attention	30.02	35.56	27.91	25.00
RazorAttention Tang et al. (2025)	27.44	33.89	25.12	21.30
RaaS Hu et al. (2025)	28.23	33.89	26.51	22.02
ArkVale Chen et al. (2024)	28.63	33.89	26.98	23.15
ShadowKV Sun et al. (2025a)	25.45	32.78	22.79	18.52
Quest Tang et al. (2024)	20.68	22.78	19.07	20.37

Table 1: Performance comparison on LongBench V2 using Llama-3.1-8B-Instruct. Bold denotes the best sparse method; Blue highlights cases where LycheeCluster outperforms Full Attention.

Method	DeepSeek-R1-Distill	DeepSeek-R1-Distill
Method	Llama-8B	Qwen-14B
Full Attention	78.40	74.00
RazorAttention	72.00	70.00
RaaS	74.00	68.00
ArkVale	72.00	72.00
ShadowKV	76.00	76.00

Table 2: Accuracy on MATH500. LycheeCluster demonstrates consistent improvements over sparse baselines across different model architectures on DeepSeek-R1-Distill-Llama-8B.

Figure 4: End-to-end decoding latency (TPOT) comparison on a single H20 GPU across varying context lengths. While full attention exhibits linear latency growth, our method maintains consistently low latency.

Figure 5: Kernel-level latency breakdown. (a) Prefill Phase: Latency comparison across varying context lengths. The colored top sections represent the index construction overhead. While LycheeCluster incurs a slightly higher construction cost (10–15%) than ClusterKV, it remains a minor fraction of the total prefill time. (b) Decoding Phase: Breakdown of total latency for generating 1,024 tokens at 72k context. The combined overhead of retrieval and lazy updates in LycheeCluster is minimal compared to the massive computation reduction.

Figure 6: Ablation study on the impact of segmentation strategies. We compare the accuracy of LycheeCluster using our structure-aware chunking against a fixed-size chunking baseline across four task categories. The results demonstrate that preserving semantic boundaries consistently improves performance.

Strategy	Overall	Short	Medium	Long	Recall Rate
Max	28.83	35.56	26.98	21.3	33.60%
Mean	30.82	37.22	28.84	24.07	40.37%

Table 3: Ablation study on representative key pooling strategies. We compare mean pooling (Ours) against max pooling on the LongBench V2 (Llama-3.1-8B-Instruct). Recall Rate denotes the retrieval recall rate. It is defined as the percentage of the top-

k

tokens with the highest ground-truth attention scores (computed by full attention) that are successfully retrieved by the strategy within the same token budget.

Figure 7: Impact of token budget on LongBench V2 performance. The accuracy improves as the budget increases from 256 to 1024.

Priority Level	Category	Details & Examples
Level-1	Structural Separators	Paragraphs ( \n\n ), Markdown ( --- , *** , ‘‘‘ ), Structural Language ( } , ] , > )
Level-2	Grammatical & Semantic	Sentence Terminators (., ?, !, 。？！), Single Newline ( \n )
Level-3	Phrasal Separators	English Punctuation (,, ;, :), Chinese Punctuation (，；：、)
Level-4	Whitespace	Spaces, Tabs

Table 4: Hierarchical classification of text separators for recursive chunking, ordered by semantic priority from structural delimiters to whitespace.

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 8: Memory usage comparison between the full KV cache (left axis, GB) and index overhead of LycheeCluster (right axis, MB). The percentages annotate the relative size of the index compared to the full KV cache, showing a consistent

\sim

1% overhead.

Figure 9: Stability analysis during long-context generation. The blue represents the step-to-step Jaccard Similarity, and the green represents the Window Hit rate (

w=32

). Stability remains robust initially but shows signs of decay after 6k decode steps.

Figure 10: Sensitivity analysis on clustering granularity. We investigate the impact of the average number of chunks per fine cluster on retrieval Recall Rate (blue, left axis) and Prefill Latency (orange, right axis) using the gov_report subset.

Figure 11: Each point represents a chunk. Colors denote coarse units, while shaded polygons indicate fine clusters.

Figure 12: Statistical distribution of data length ranges in the LongBench V2 dataset, using the Llama3.1-8B-instruct tokenizer.

Task	# Samples	Avg. Length	Max Length	Expert Acc.	Expert Time
Code Repository Understanding	50	1M	4M	44%	6.4 min
Long In-context Learning	81	259k	1.5M	63%	8.3 min
Long Structured Data Understanding	33	390k	3M	73%	6.4 min
Long-dialogue History Understanding	39	74k	120k	79%	8.2 min
Multi-Document QA	125	127k	1.7M	36%	6.1 min
Single-Document QA	175	110k	860k	55%	8.9 min

Appendix

Table 5: Data statistics and expert performance across tasks of LongBench V2 .

Context / Task	single	multikey	multivalue	multiquery	vt	fwe	qa1	qa2	Avg.
Full Attention
4k	100.0	100.0	100.0	100.0	82.5	84.4	89.8	59.2	89.5
8k	91.8	100.0	100.0	99.0	79.6	87.1	81.6	59.2	87.3
16k	63.3	100.0	98.5	98.5	82.0	93.9	79.6	51.0	83.3
32k	95.9	95.9	97.5	97.5	76.3	76.9	79.6	59.2	84.8
LycheeCluster

Appendix

Table 6: Performance comparison on RULER benchmark. Note that LycheeCluster achieves comparable or even superior average performance compared to Full Attention, especially at 16k length.

KV-Cache Management

Key-value (KV) cache management reduces and coordinates Transformer attention state to make long-context inference faster and more memory-efficient.

See all 199 papers

IceCache: Memory-efficient KV-cache Management for Long-Sequence LLMs
Apr 12, 2026Yuzhen Mao, Qitong Wang, Martin Ester +1KV-Cache Management LLM Inference Acceleration
Simon Fraser University, BC, Canada · Harvard University, Cambridge, USA
TTKV: Temporal-Tiered KV Cache for Long-Context LLM Inference
Mar 27, 2026Gradwell Dzikanyanga, Weihao Yang, Hao Huang +4KV-Cache Management Long-Context Language Model Inference
Harbin Institute of Technology, Shenzhen · Guangzhou University
IndexMem: Learned KV-Cache Eviction with Latent Memory for Long-Context LLM Inference
May 25, 2026Xintong Yang, Hao Gu, Binxing Xu +6Memory-Augmented Language Models Self-Attention
The Hong Kong University of Science and Technology · Zhejiang University

Apr 12, 2026J/K move · Enter open · S save

IceCache: Memory-efficient KV-cache Management for Long-Sequence LLMs

Yuzhen Mao, Qitong Wang, Martin Ester, Ke Li

Simon Fraser University, BC, Canada · Harvard University, Cambridge, USA

KV-Cache Management LLM Inference Acceleration KV-Cache Offloading Long-Context Language Model Inference

Open paper AskPDF arXiv

Key-Value (KV) cache plays a crucial role in accelerating inference in large language models (LLMs) by storing intermediate attention states and avoiding redundant computation during autoregressive generation. However, its memory footprint scales linearly with sequence length, often leading to severe memory bottlenecks on resource-constrained hardware. Prior work has explored offloading KV cache to the CPU while retaining only a subset on the GPU, but these approaches often rely on imprecise token selection and suffer performance degradation in long-generation tasks such as chain-of-thought reasoning. In this paper, we propose a novel KV cache management strategy, IceCache, which integrates semantic token clustering with PagedAttention. By organizing semantically related tokens into contiguous memory regions managed by a hierarchical, dynamically updatable data structure, our method enables more efficient token selection and better utilization of memory bandwidth during CPU-GPU transfers. Experimental results on LongBench show that, with a 256-token budget, IceCache maintains 99% of the original accuracy achieved by the full KV cache model. Moreover, compared to other offloading-based methods, IceCache attains competitive or even superior latency and accuracy while using only 25% of the KV cache token budget, demonstrating its effectiveness in long-sequence scenarios. The code is available on our project website at https://yuzhenmao.github.io/IceCache/.

Abstract

KV-Cache Management

Explore similar work

IceCache: Memory-efficient KV-cache Management for Long-Sequence LLMs

TTKV: Temporal-Tiered KV Cache for Long-Context LLM Inference

IndexMem: Learned KV-Cache Eviction with Latent Memory for Long-Context LLM Inference