# Krul: Efficient State Restoration for Multi-turn Conversations with Dynamic Cross-layer KV Sharing

arXiv: https://arxiv.org/abs/2507.08045 · HTML: https://mlsanity.com/paper/2507.08045/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in KV cache optimization, one of 12 directions in Efficient LLM inference and serving.
- Builds on 20 of its 37 references that are in the map.
- First posted on arXiv 10 Jul 2025.

## Placed in

- Efficient LLM inference and serving / [KV cache optimization](https://mlsanity.com/inference/kv-cache-optimization/)

## Builds on (most cited first, 20 of 20)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [Efficient Streaming Language Models with Attention Sinks](https://mlsanity.com/paper/2309.17453/) (2023)
- [ShareGPT4V: Improving Large Multi-Modal Models with Better Captions](https://mlsanity.com/paper/2311.12793/) (2023)
- [Transformer in Transformer](https://mlsanity.com/paper/2103.00112/) (2021)
- [KVQuant: Towards 10 Million Context Length LLM Inference with KV Cache Quantization](https://mlsanity.com/paper/2401.18079/) (2024)
- [LongBench v2: Towards Deeper Understanding and Reasoning on Realistic Long-context Multitasks](https://mlsanity.com/paper/2412.15204/) (2024)
- [FlashInfer: Efficient and Customizable Attention Engine for LLM Inference Serving](https://mlsanity.com/paper/2501.01005/) (2025)
- [InfiniGen: Efficient Generative Inference of Large Language Models with Dynamic KV Cache Management](https://mlsanity.com/paper/2406.19707/) (2024)
- [Cost-Efficient Large Language Model Serving for Multi-turn Conversations with CachedAttention](https://mlsanity.com/paper/2403.19708/) (2024)
- [Keyformer: KV Cache Reduction through Key Tokens Selection for Efficient Generative Inference](https://mlsanity.com/paper/2403.09054/) (2024)
- [Model Tells You Where to Merge: Adaptive KV Cache Merging for LLMs on Long-Context Tasks](https://mlsanity.com/paper/2407.08454/) (2024)
- [KV Cache is 1 Bit Per Channel: Efficient Large Language Model Inference with Coupled Quantization](https://mlsanity.com/paper/2405.03917/) (2024)
- [Cross-Attention is All You Need: Adapting Pretrained Transformers for Machine Translation](https://mlsanity.com/paper/2104.08771/) (2021)
- [Stateful Large Language Model Serving with Pensieve](https://mlsanity.com/paper/2312.05516/) (2023)
- [MMDialog: A Large-scale Multi-turn Dialogue Dataset Towards Multi-modal Open-domain Conversation](https://mlsanity.com/paper/2211.05719/) (2022)
- [KVSharer: Efficient Inference via Layer-Wise Dissimilar KV Cache Sharing](https://mlsanity.com/paper/2410.18517/) (2024)
- [NaturalConv: A Chinese Dialogue Dataset Towards Multi-turn Topic-driven Conversation](https://mlsanity.com/paper/2103.02548/) (2021)
- [Fast State Restoration in LLM Serving with HCache](https://mlsanity.com/paper/2410.05004/) (2024)
- [Compute Or Load KV Cache? Why Not Both?](https://mlsanity.com/paper/2410.03065/) (2024)

## Built on by (most cited first, 1 of 1)

- [Agent Memory Below the Prompt: Persistent Q4 KV Cache for Multi-Agent LLM Inference on Edge Devices](https://mlsanity.com/paper/2603.04428/) (2026)

## Abstract (arXiv)

Efficient state restoration in multi-turn conversations with large language models (LLMs) remains a critical challenge, primarily due to the overhead of recomputing or loading full key-value (KV) caches for all historical tokens. To address this, existing approaches compress KV caches across adjacent layers with highly similar attention patterns. However, these methods often apply a fixed compression scheme across all conversations, selecting the same layer pairs for compression without considering conversation-specific attention dynamics. This static strategy overlooks variability in attention pattern similarity across different conversations, which can lead to noticeable accuracy degradation. We present Krul, a multi-turn LLM inference system that enables accurate and efficient KV cache restoration. Krul dynamically selects compression strategies based on attention similarity across layer pairs and uses a recomputation-loading pipeline to restore the KV cache. It introduces three key innovations: 1) a preemptive compression strategy selector to preserve critical context for future conversation turns and selects a customized strategy for the conversation; 2) a token-wise heterogeneous attention similarity estimator to mitigate the attention similarity computation and storage overhead during model generation; 3) a bubble-free restoration scheduler to reduce potential bubbles brought by the imbalance of recomputing and loading stream due to compressed KV caches. Empirical evaluations on real-world tasks demonstrate that Krul achieves a 1.5x-2.68x reduction in time-to-first-token (TTFT) and a 1.33x-2.35x reduction in KV cache storage compared to state-of-the-art methods without compromising generation quality.