Paper deep dive
Dynamic Flow, Static Graph: KV Cache Reuse for Efficient LLM Serving on Mobile NPUs
Zhengxiang Huang, Shengheng Chen, Chaoyue Niu, Yujie Sun, Zhaode Wang, Zeyu Zhao, Chengfei Lv, Fan Wu, Guihai Chen
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:On-device large language model (LLM) serving is a cornerstone of local-first personal intelligence, offering users data sovereignty, strong privacy guarantees, and freedom from cloud API latency and cost. Although KV caching is widely used to reduce latency in long-context inference, existing designs were primarily optimized for cloud GPUs with dynamic execution environments and abundant memory bandwidth. These architectural assumptions do not hold on mobile NPUs, where computation graphs must be statically compiled and both memory capacity and I/O bandwidth are severely constrained. In this work, we present a compute-storage co-design for mobile-centric prefix and non-prefix KV reuse. We first propose an intra-graph mechanism that maps selective KV recomputation onto static NPU graphs, reconciling algorithmic dynamicity with NPU staticity. We further develop an inter-graph scheduler to optimize chunk merging and minimize padding with dynamic programming. To address mobile bandwidth limitations, we introduce a hierarchical KV manager featuring a tree-hash-semantic hybrid structure, along with cost-aware prefetching and eviction policies. We also build a two-dimensional pipeline that overlaps KV loading, rerotation, and storage with NPU execution, hiding data-movement latency. Experiments across representative on-device workloads and LLMs show that our design reduces time-to-first-token (TTFT) by $40-60\%$ compared with no reuse and prefix-only caching.
Tags
Links
- Source: https://arxiv.org/abs/2609.34727v1
- Canonical: https://arxiv.org/abs/2609.34727v1
Trouble viewing inline? Open PDF directly โ
Full Text
93,466 characters extracted from source content.
Expand or collapse full text
Dynamic Flow, Static Graph: KV Cache Reuse for Efficient LLM Serving on Mobile NPUs Zhengxiang Huang Shanghai Jiao Tong University Shanghai, China Shengheng Chen Shanghai Jiao Tong University Shanghai, China Chaoyue Niu โ Shanghai Jiao Tong University Shanghai, China Yujie Sun Shanghai Jiao Tong University Shanghai, China Zhaode Wang Alibaba Group Hangzhou, China Zeyu Zhao Shanghai Jiao Tong University Shanghai, China Chengfei Lv Alibaba Group Hangzhou, Zhejiang, China Fan Wu Shanghai Jiao Tong University Shanghai, China Guihai Chen Shanghai Jiao Tong University Shanghai, China Abstract On-device large language model (LLM) serving is a corner- stone of local-first personal intelligence, offering users data sovereignty, strong privacy guarantees, and freedom from cloud API latency and cost. Although KV caching is widely used to reduce latency in long-context inference, existing de- signs were primarily optimized for cloud GPUs with dynamic execution environments and abundant memory bandwidth. These architectural assumptions do not hold on mobile NPUs, where computation graphs must be statically compiled and both memory capacity and I/O bandwidth are severely con- strained. In this work, we present a compute-storage co- design for mobile-centric prefix and non-prefix KV reuse. We first propose an intra-graph mechanism that maps selective KV recomputation onto static NPU graphs, reconciling algo- rithmic dynamicity with NPU staticity. We further develop an inter-graph scheduler to optimize chunk merging and minimize padding with dynamic programming. To address mobile bandwidth limitations, we introduce a hierarchical KV manager featuring a tree-hash-semantic hybrid struc- ture, along with cost-aware prefetching and eviction policies. We also build a two-dimensional pipeline that overlaps KV loading, rerotation, and storage with NPU execution, hiding data-movement latency. Experiments across representative on-device workloads and LLMs show that our design re- duces time-to-first-token (TTFT) by 40โ60% compared with no reuse and prefix-only caching. โ Chaoyue Niu is the corresponding author (rvince@sjtu.edu.cn). This work is licensed under a Creative Commons Attribution 4.0 Interna- tional License. EuroSys โ27, Rabat, Morocco ยฉ 2027 Copyright held by the owner/author(s). ACM ISBN 979-8-4007-2971-3/2027/04 https://doi.org/10.1145/3842654.3848526 CCS Concepts:โข Human-centered computingโUbiq- uitous and mobile devices;โข Computing methodologies โ Natural language processing. Keywords: On-Device LLM Inference, Mobile NPU, KV Cache Reuse ACM Reference Format: Zhengxiang Huang, Shengheng Chen, Chaoyue Niu, Yujie Sun, Zhaode Wang, Zeyu Zhao, Chengfei Lv, Fan Wu, and Guihai Chen. 2027. Dynamic Flow, Static Graph: KV Cache Reuse for Efficient LLM Serving on Mobile NPUs. In 22nd European Conference on Computer Systems (EuroSys โ27), April 19โ23, 2027, Rabat, Morocco. ACM, New York, NY, USA, 19 pages. https://doi.org/10.1145/3842654. 3848526 1 Introduction The rapid advancement of large language models (LLMs) is driving a fundamental shift in how intelligence is delivered to end users. Rather than relying solely on cloud-centric intelligence, driven by the imperatives of low cost, user pri- vacy, offline availability, and low-latency interaction, leading technology companies are increasingly moving toward a local-first, user-centric intelligence paradigm that enables context-aware, continuously available assistance grounded in sensitive personal data. For example, Google Gemini em- phasizes personalized intelligence experiences [2], while Google AI Edge Gallery [16] demonstrates practical deploy- ment of generative models directly on smartphones; Apple Intelligence [5] adopts a hybrid deviceโcloud collaborative architecture [4], where an on-device 3B-scale LLM is re- sponsible for privacy-sensitive and personalized tasks. Re- cent systems such as ClawMobile [9] and OmniInfer [40] further demonstrate the growing feasibility of deploying autonomous LLM agents directly on mobile devices. On-device LLM serving forms the system foundation of the emerging user-centric, local-first intelligence stack. Like cloud services for personalized intelligence, mobile LLM ser- vices face significant challenges in handling long-context arXiv:2609.34727v1 [cs.OS] 28 Sep 2026 EuroSys โ27, April 19โ23, 2027, Rabat, MoroccoZhengxiang Huang et al. (a) On-device prefill latency under different prefill length on Xiaomi 15 Pro, inference backed by ExecuTorch, using mobile NPU, 2-5รslower than cloud. (Qwen3-1.7B, batch size = 1) (b) Cloud prefill latency under differ- ent prefill length on RTX 5090. Reduc- tion 1 โcomes from prefix caching, while 2 โcomes from non-prefix reuse. (Qwen3-1.7B, batch size = 16) Figure 1. Long-context prefill latency on mobile devices and KV cache reuse for latency reduction in cloud LLM serving. and repeated-context workloads. Such workload character- istics originate from how these applications construct their prompts, and are therefore shared by cloud and device LLM services alike [5,9,21,26]. Consider several representative scenarios: a long-running conversational assistant whose prompt grows progressively with chat history; a document QA assistant that repeatedly retrieves the same set of user documents; a personal agent that loads shared skill descrip- tions or tool definitions for every invoked task. In each case, context grows long through accumulation or retrieval and becomes reusable because the same content recurs across requests. Large portions of the prompt, including system prompts, retrieved document chunks, and reusable skill in- structions, are repeatedly reused across successive requests, introducing substantial redundancy during the transformer prefill phase. As illustrated in Figure 1(a), prefill latency, i.e., time-to-first-token (TTFT), increases rapidly with prompt length, reaching several seconds once prompts exceed 2k tokens and continuing to grow nearly linearly thereafter, se- verely degrading the interactive user experience. While the long and repeated context workload characteristic is dictated by the application layer rather than the hardware beneath, its cost is far higher on mobile. At the same prompt length, mobile NPUs are 2โ5รslower than cloud GPUs (Figure 1(b)). To avoid repeated prefill computation and reduce TTFT, previously computed Key-Value (KV) tensors for input to- kens can be cached and reused when similar context appears again. Existing KV cache reuse designs (e.g., Mooncake [36], RAGCache [21], and LMCache [26]) mainly target cloud- based deployment scenarios, focusing on GPU inference and distributed storage architectures. These techniques have also been integrated into LLM serving engines such as VLLM [22] and SGLang [53]. Beyond prefix reuse, CacheBlend [50] fur- ther introduces selective KV recomputation to enable reuse of non-prefix KV segments. As shown in Figure 1(b), prefix caching and non-prefix KV reuse can reduce cloud serving latency by 2รโ3รon cache hits for batched requests served on an RTX 5090 GPU. However, KV cache reuse has not been well studied in on-device LLM serving scenarios. In particular, mobile LLM inference engines (e.g., ExecuTorch [12], MLC-LLM [30], llama.cpp [14], MediaPipe [11]) focus largely on efficient single-request execution through optimized kernels, hetero- geneous CPU/GPU/NPU scheduling, and quantization. They typically provide little or no support for persistent KV reuse across requests as well as runtime hierarchical KV cache man- agement, and essentially no support for quality-preserving non-prefix reuse. This gap is increasingly important: the workloads are exactly those that exhibit strong cross-request context repetition. Without reuse, mobile systems repeatedly recompute the same long contexts, wasting time, resources, and energy. Directly porting cloud-based KV reuse techniques to mo- bile devices is fundamentally infeasible due to profound ar- chitectural differences between cloud and mobile hardware. First, from a compute perspective, mobile NPUs are archi- tecturally distinct from cloud GPUs. Whereas cloud GPUs expose flexible, programmable tensor cores with SIMT par- allelism that naturally accommodate dynamic tensor shapes and irregular computational graphs, mobile NPUs are built around fixed-shape matrix tile units that operate on statically pre-compiled computational graphs. Dynamic execution pat- terns, such as the variable token selection, input-dependent KV deviation computation, and runtime reuse-pattern varia- tion, introduced by non-prefix selective recomputation, are fundamentally incompatible with this static execution model. Second, from a storage perspective, on-device platforms op- erate under memory bandwidth and capacity constraints that are orders of magnitude tighter than cloud deployments, creating a severe memory and bandwidth wall. Loading and storing large KV tensors can easily exceed the time saved by bypassing the prefill computation. Without a specialized hierarchical management and prefetching strategy that con- siders both NPU execution and flash I/O, the overhead of KV movement can negate the benefits of reuse. These dif- ferences are structural rather than transient: mobile SoCs remain constrained by stringent power and thermal budgets, and thus cannot scale compute and memory resources in the same manner as datacenter accelerators. Consequently, al- though long-context and context-reuse workloads are shared across device and cloud services, efficiently exploiting such reuse opportunities on mobile devices requires fundamen- tally novel engine-level designs rather than directly inherit- ing cloud-oriented mechanisms. In this work, we build the first system that enables efficient prefix and non-prefix KV reuse for on-device LLM serving on mobile NPUs, as depicted in Figure 2. Unlike existing cloud designs that target cloud GPU kernels and distributed clus- ters, our key idea is a compute-storage co-design that adapts dynamic KV reuse algorithms to the static, quantized execu- tion model of mobile NPUs while simultaneously respecting the severe bandwidth and capacity constraints of on-device Dynamic Flow, Static Graph: KV Cache Reuse for Efficient LLM Serving on Mobile NPUsEuroSys โ27, April 19โ23, 2027, Rabat, Morocco Applications Compute Layer Storage Layer newnon-prefixprefix Doc Q&A 1 Chat History Reuse 2 Agent Skill Use 3 SKILL.md ยท Chunk Merge (ยง 4.2) Compare โ โ Non-prefix cached KV Chunk 0 Chunk 1 Compare Valid Mask Valid Mask โ โ โ ร ร TopK Gather Static Graph (ยง 4.1) โ ร โ โ โ Valid Mask (ยง 6.1 6.2) C0S0 C0S1 C0 S0 C0 S0 C0 S1 C1S0C1S1 C1 S0 C1 S1 (KV Load) (KV Rerotate) C0 S1 C1 S0 C1 S1 NPU CPU Pool (ยง 5.1) Shared Buffer Compute-Storage Pipelining Flash Structure (ยง 5.2) (ยง 5.3) Eviction Figure 2. System overview of our on-device KV reuse design for long-context mobile LLM serving. The system jointly optimizes compute and storage for both prefix and non-prefix KV reuse, converting dynamic selective recomputation into efficient static NPU execution while enabling hierarchical KV management and asynchronous computeโstorage pipeline overlap. memory hierarchies. On the compute side (ยง 4), to bridge the gap between dynamic algorithms and static hardware, we first map selective recomputation onto pre-compiled static NPU graphs, using chunk-andโpad, validity masking, and forced final-token selection to preserve irregular reuse se- mantics under fixed input shapes. At the inter-graph level, we formulate runtime execution as a multi-graph scheduling problem and develop a novel dynamic programming sched- uler that merges invocations across a set of pre-compiled static graphs to minimize latency under dynamic input. On the storage side (ยง 5), to fit on-device budgets while avoiding stalling NPU prefill, we design a multi-tier storage manager spanning the NPU buffer, CPU memory, and flash. It uses a hybrid on-disk data structure combining prefix trees with hash and semantic indices to efficiently locate both prefix and non-prefix reusable chunks. It also takes a lightweight, cost-aware prefetch and eviction policy that incorporates the differential cost of reloading versus recomputing prefix and non-prefix chunks, ensuring hot KV data stays close to the compute units. To prevent data movement from dominating latency (ยง 6), we jointly schedule storage I/O and CPU-NPU execution based on parallelizability analysis across model shards and input chunks. Together, these components form a cross-layer co-design with mutually complementary com- pute and storage decisions, as validated by our ablation study. We summarize the key contributions as follows: โข We identify fundamental system bottlenecks in on- device LLM serving with KV reuse: the architectural mismatch between dynamic KV recomputation and the static compiled graphs required by mobile NPUs, exacerbated by heavy KV cache transfer under tight on-device memory bandwidth and capacity. โขWe develop an intra-graph construction and a general multi-graph scheduling abstraction for dynamic inputs over pre-compiled static graphs, along with a cross- layer computeโstorage design that jointly optimizes KV recomputation, placement, and movement. โขWe take 3 different workloads, 4 LLMs from Qwen3 and Llama3.2 series, and 3 smartphones for evaluation. Evaluation results reveal that our design delivers 1.5รโ 5.4รprefill speedup over original ExecuTorch [12] with no reuse and 1.3รโ2.5รover prefix caching, cuts TTFT by 40%โ60%, and avoids the roughly 30% quality drop of direct full non-prefix reuse. 2 Background 2.1 KV Cache Prefix and Non-Prefix Reuse For transformer-based LLMs, the prefill phase computes per- layer Key-Value (KV) tensors for the input tokens. These tensors form the KV cache, which can be reused when the same context reappears, thereby reducing redundant prefill computation and reducing TTFT. For input prompt, tokens can be categorized into 3 types: prefix reusable, non-prefix reusable, and new tokens, as ex- emplified in Figure 3. Lossless prefix caching strategy di- rectly reuses the KV cache of a prompt prefix when a new request shares the same leading tokens as some previously cached prompts ( 1 โin Figure 3). Because the KV states of a prefix do not depend on subsequent tokens, this reuse is lossless and preserves generation quality, therefore widely adopted in modern cloud-based LLM serving systems, such as VLLM [22], SGLANG [53], and ChunkAttention [51], but its benefit is limited to prefix reusable texts that posit at the beginning of the prompt. EuroSys โ27, April 19โ23, 2027, Rabat, MoroccoZhengxiang Huang et al. โ Prefix reuse โก Non-prefix reuse New tokens You are a helpful assistant ... NPU is โNeural Processing Unitโ ... Whatโs NPU? direct reuse Transformer Block 0 Transformer Block n ... KV Deviation Selective Recompute Transformer Block 0 Transformer Block n ... Full Compute Transformer Block 1 Cache 1: You are a helpful assistant Cache 2: GPU is ... , while NPU is โNeural Processing Unitโ ... Query: Whatโs NPU? Input: You are a helpful assistant NPU is โNeural Processing Unitโ ... Whatโs NPU? Figure 3. Illustration of 3 types of tokens in a prompt: prefix, non-prefix, and new tokens. 1 โPrefix caching directly reuses KV states for shared prefixes. 2 โ Non-prefix KV chunks re- compute only high KV deviated tokens and reuse the rest. A more flexible but lossy non-prefix chunk reuse strat- egy targets reusable non-prefix chunks in the prompts, of- fering a substantially larger reusing space. Direct reusing non-prefix chunks in Prompt Cache [15] may significantly lose accuracy because they cannot recover the true positional dependency and cross-chunk attention of non-prefix chunks. Instead, CacheBlend [50], which recomputes a small set of selected tokens with high KV deviation while reusing the remaining chunk-level KV cache ( 2 โin Figure 3), provides a practical middle ground between exact but restrictive prefix reuse and expensive full recomputation for non-prefix reuse. Based on the insight that KV deviation is strongly correlated across layers [50], the algorithm compares cached KV with fully recomputed KV in the first few layers, selects the top-ํพ most deviated tokens, and selectively recomputes them in the subsequent layers. Thus, it reduces the computational FLOPs to approximately the recompute ratio ํ of full computation and induces only tiny precision loss. As illustrated in Figure 4(a), the selective non-prefix KV re- compute workflow of CacheBlend algorithm features 5 forms of dynamicity in its computational graph. 1 โ Input shape dy- namicity, where prompt lengths vary significantly across requests. 2 โRecomputation selection dynamicity, where the subset of tokens to recompute is determined dynamically ac- cording to KV deviation. 3 โ Dynamic numerical range, where the KV comparison operation is highly precision-sensitive. Intermediate summed squared error ofํ-th token of the layer 0 is computed as: ฮํพํ[ํ]= ํพํ layer 0 [ํ]โ c ํพํ layer 0 [ํ] 2 ํน ,(1) which spans a wide numerical range from 0 to 2000 and ex- hibits substantially different distributions across prompts as Compare โ โ โ Non-prefix cached KV โก, โข โฃ Recomputed KV โ โค ... Layer 0 Layer 1~n Update KV Next logits Compare โ โ Non-prefix cached KV Chunk 0 Chunk 1 Compare Valid Mask Valid Mask โ โ โ ร ร TopK Gather (a) Selective KV recompute algorithm workflow with 5 forms of dynamicity. 0204060 Prompt 1 Tokens 0 1 2 3 4 5 6 7 Head 0204060 Prompt 2 Tokens 0 1 2 3 4 5 6 7 Head 250 500 750 1000 1250 1500 1750 2000 2250 Summed Deviation (b) Heatmap of KV deviationฮํพํ. Figure 4. Characteristics of non-prefix KV reuse and selec- tive recompute algorithm. shown in the KV deviation heatmap in Figure 4(b). Such large dynamic ranges make quantization difficult and can lead to overflow or underflow when statically quantized to 8/16-bit integers on mobile NPUs. 4 โ Output last token dynamicity, where the final prompt token must always be selected to pro- duce logits for subsequent autoregressive decoding. 5 โ Reuse- pattern dynamicity, where the token reuse pattern within a prompt is determined at runtime, with prefix-reusable to- kens, non-prefix-reusable tokens, and new tokens appearing in arbitrary interleaved combinations and lengths. 2.2 Mobile Hardware Characteristics Mobile NPU Characteristics. Mobile NPUs equipped with specialized matrix units can substantially accelerate long-context LLM prefill, often achieving 2โ5รspeedup over mobile CPU and GPU [47]. These matrix units process fixed- shape tensor tiles streamingly, which strongly favor static graphs, i.e., offline pre-compiled computational graphs with statically determined operator shapes and workflow. In prac- tice, NPU graph preparation involves graph construction, optimization, and compilation, whose overhead is only ac- ceptable when performed offline. Unlike cloud GPUs, which leverage symmetric tensor cores and SIMT parallelism for flexible programmability and irregular-shape support, mo- bile NPUs deliberately trade this flexibility for efficiency: regular tensor shapes enable efficient mapping onto ma- trix units and streamlined hardware scheduling under strin- gent power and thermal budgets, which is what underlies their performance-per-watt advantage. Consequently, they require specialized techniques to convert dynamic execu- tion patterns into static graphs. This execution preference is not vendor-specific, but is shared across major mobile NPU platforms including Qualcomm HTP [20], MediaTek APU [19], and Apple ANE [18], and it persists across the three generations of Hexagon NPUs evaluated in this work. In addition, mobile NPUs achieve the highest compute and memory efficiency on integer GEMM workloads, such as Dynamic Flow, Static Graph: KV Cache Reuse for Efficient LLM Serving on Mobile NPUsEuroSys โ27, April 19โ23, 2027, Rabat, Morocco Main Memory ( 8~16 GB ) Flash CPU CacheNPU TCM ๆ ๆณจ ้ๅบฆ ๅ ๅคงๅฐ๏ผ CPU NPU ๆขๆๅพๆ ๏ผ Cache CPU Logic Memory ๆ ๅฐ็่ตท็ปๅฐๅๆฐๅญ๏ผ NPU Logic Memory CPU-NPU Shared Buffer TCM ~ 60GB/s ~ 300MB/s (~256 GB) Figure 5. CPUโNPU memory hierarchy of mobile devices. ํ INT4 ํด UINT16 [20,44], while floating-point execution is com- paratively more expensive. Mobile NPUs also favor static quantization, where quantization parameters are calibrated offline and reused during inference. Although effective for regular LLM prefill and decode, static quantization is less suitable for selective recomputation, because the compare- and-select stage relies on precision-sensitive KV difference computation whose distributions are highly input-dependent and difficult to calibrate offline. On-Device Memory Hierarchy. The on-device memory hierarchy typically follows a three-tier structure, as illus- trated in Figure 5: (1) CPU cache and NPU tightly coupled memory (TCM) SRAM at the top; (2) CPU-NPU shared DRAM in the middle; and (3) flash storage at the bottom. While the CPU cache and NPU TCM offer low latency for compute- intensive operations, their capacity is strictly limited (often <10 MB). On modern SoCs like the Qualcomm HTP [20], the DRAM layer is physically shared between the CPU and NPU, while logically divided into CPU logic memory, NPU logic memory, and a CPUโNPU shared buffer. At the lowest level, flash storage serves as persistent storage for models and KV data. Table 1. Comparison between on-device and cloud memory hierarchies for LLM serving and KV storage. Platform Memory LevelCapacity Bandwidth Interconnect Device Cache / TCM2โ8 MBโ CPU LPDDR8โ16 GB โผ60 GB/sOn-chip Bus Flash128 GBโ1 TB โผ500 MB/sI/O Bus Cloud GPU Cacheโผ100 MBโ GPU HBM24โ640 GB1โ3 TB/sNVLink CPU DRAM0.5โ10 TB50โ300 GB/sPCIe Distributed Storage10โ1000 TB0.5โ2 GB/sRDMA In contrast to cloud-based LLM serving, on-device plat- forms operate under substantially tighter memory-capacity and bandwidth constraints. Cloud deployments typically or- ganize memory hierarchically across GPU device memory, CPU host memory, and distributed storage, interconnected through high-bandwidth fabrics such as NVLink, PCIe, and RDMA. Table 1 summarizes cloud-based and on-device mem- ory architectural disparities, highlighting the bandwidth wall faced by mobile-class hardware. 3 New Key Challenges Given the algorithmic characteristics of prefix and non-prefix KV reuse (ยง 2.1) and the mobile hardware characteristics (ยง 2.2), two key challenges emerge from the compute and storage perspectives. 3.1 Recomputation Dynamicity vs. NPU Staticity From the compute perspective, the key challenge lies in the mismatch between the highly dynamic execution patterns in- troduced by selective recomputation for non-prefix reusable tokens and the pre-compiled static execution graphs opti- mized by mobile NPUs. The 5 forms of dynamicity discussed in ยง 2.1 translate into several concrete conflicts with mobile NPU execution. Specif- ically, dynamic tensor shapes ( 1 โ ) conflict with statically fixed tensor sizes in compiled graphs; dynamic computa- tional flows ( 2 โand 4 โ) conflict with static operator graphs; dynamic numerical ranges ( 3 โ ) conflict with static quanti- zation parameters; and dynamic reuse patterns ( 5 โ) conflict with static graph invocation strategies. These conflicts jointly complicate the design of efficient intra-graph construction and quantization schemes, as well as inter-graph scheduling and invocation optimization. 3.2 Large KV Size vs. Limited Bandwidth and Space From the storage perspective, the key challenge arises from the mismatch between the large size of KV tensors and the limited bandwidth and capacity of on-device memory hier- archies, as KV chunks must be loaded from lower memory levels with limited bandwidth and stored under tight mem- ory capacity constraints, making efficient hierarchical KV management difficult. Due to constrained I/O bandwidth, loading large KV ten- sors from flash storage can introduce substantial latency. For example, the 8-bit quantized KV cache of Qwen3-1.7B occu- pies approximately 56 KB per token, corresponding to 56 MB for a 1024-token prompt. On Xiaomi 15 Pro, loading and mapping such a prompt from flash storage into the memory pool takes approximately 200 ms, which can diminish the execution advantage of NPUs by causing them to wait if the latency is not carefully hidden. Limited on-device memory and storage capacity prevent KV tensors from being retained indefinitely. As a result, evic- tion and compaction mechanisms are required to periodically or adaptively reclaim and reorganize storage space. These maintenance operations must also be carefully overlapped with execution; otherwise, excessive secondary-storage I/O and fragmentation can significantly degrade performance and expose additional latency to users. The above new challenges make existing cloud-based KV reuse approaches inapplicable, demanding new compute- storage co-designs for efficient on-device KV reuse. EuroSys โ27, April 19โ23, 2027, Rabat, MoroccoZhengxiang Huang et al. Compare โ โ โ Non-prefix cached KV โ โก Recomputed KV โข โฃ ... Layer 0 Layer 1~n Update KV Next logits Compare โ โ Non-prefix cached KV Chunk 0 Chunk 1 Compare Valid Mask Valid Mask โ โ โ ร ร TopK Gather Figure 6. NPU static KV recompute graph on layer 0. 4 NPU Recompute for Non-Prefix Reuse To resolve the conflicts between the dynamicity of non-prefix reuse selective recompute algorithm and the staticity of NPU pre-compiled workflows, we propose intra-graph design that converts dynamic algorithm to static NPU computation graph, searches for the latency-optimal static tensor shape to optimize the graph, and supports precision-sensitive op- erators with mixed-precision operators to cover dynamic numerical range of intermediate tensors. We further pro- pose inter-graph dynamic programming to optimize dynamic reuse patterns via merging chunks and reducing padding. 4.1Intra-Graph Design for Dynamic Recomputation NPU Static Graph Construction. Converting the non- prefix reuse algorithm CacheBlend to static NPU graph re- quires addressing the dynamicity detailed in ยง2.1. The re- sulting static NPU KV recomputation graph is illustrated in Figure 6. The dynamic input shape (dynamicity 1 โ) is ad- dressed by chunking the non-prefix tokens into static size slices, padded if not divisible by the chunk length. A valid mask is applied before KV deviation computation to exclude padded tokens from the Top-K selection process, preventing invalid tokens from being mistakenly selected for recompu- tation. Additionally, the mask guarantees that the final token is always selected (green arrow in Figure 6) wherever its position in last chunk is (dynamicity 4 โ ), ensuring correct generation of the final logits. This chunk-pad-mask adapts the static graph to dynamic input and output shapes. After Top-K token selection, the scatter-gather mechanism gathers the recomputed KV of tokens with high KV deviation and scatters them back into the reused KV cache, replacing the corresponding reused KV entries to preserve generation quality, which resolves the dynamicity in token selection and KV update workflow (dynamicity 2 โ). Latency-Optimized Graph Size Configuration. The static graph input size is critical to improve NPU graph uti- lization and execution efficiency, thus maximizing hardware utilization, such as NPU TCM capacity and matrix units (e.g., Qualcomm QNN HMX tiles), while minimizing padding over- head caused by indivisible input shapes. An optimal graph size can be determined by minimizing the expected latency over a representative target workload. In our design, the pre- fill graph sizeํฟ ํ and the selective recomputation graph size ํฟ ํ are optimized. Given the latency of one graph invocation, denoted byLatency ํ (ํฟ ํ )andLatency ํ (ํฟ ํ ), the latency for processing tokens of length ํ can be expressed as: Latency ํ (ํ)=โ ํ ํฟ ํ โยท Latency ํ (ํฟ ํ ), Latency ํ (ํ)=โ ํ ํฟ ํ โยท Latency ํ (ํฟ ํ ). (2) The expected latency of graph ํบ can be computed as: E(Latency ํบ )= ํ โ๏ธ ํ=1 freq(ํ)ยท Latency ํบ (ํ), ํบ โ ํ,ํ. (3) freq(ํ)denotes the occurrence frequency of token lengthํ collected from a representative workload. 100200300400500 Pre-Compiled Input Size (tok) 0.0 0.5 1.0 1.5 Per Token Latency (ms) Lp Ls (r=0.25) (a) Graph execution per-token la- tency under different graph sizes. 2004006008001000 Non-Prefix Input Size (tok) 0 100 200 300 400 500 600 Latency (ms) Lp=128 Ls=512 (r=0.25) (b) Non-prefix tokens prefill latency under different input sizes. Figure 7. Latency analysis of static graph input sizes. Aligned with Qualcomm HMX tile utilization strategies [17], we restrict graph sizes to multiples of 32 and select the con- figuration that yields the lowest expected latency. As shown in Figure 7(a), per-token latency is initially high for small input lengths due to poor hardware utilization and then sharply decreases as input size grows and finally slowly con- verges. 2 red-circled latency-optimal points given by our optimization both correspond to the turning point of the per-token latency curve, beyond which increasing the graph input size no longer improves hardware utilization and in- stead introduces additional padding overhead. Figure 7(b) further illustrates the stair-step pattern relationship between latency and input size due to padding. It also shows that, under the latency-optimal configuration, selective recompu- tation (orange curve,ํฟ ํ =512) achieves 2โ3รlower latency than ordinary prefill (blue curve,ํฟ ํ =128) for processing non-prefix reusable tokens. Mixed-Precision Quantization for KV Deviation Com- putation. The KV deviation computation introduced in the selective KV recompute pipeline is precision-sensitive and input-dependent (dynamicity 3 โanalyzed in Section 2.1). Thus, directly quantizing it toINT8 UINT16like other inter- mediate activations can lead to significant accuracy degrada- tion. To address this, we propose a mixed-precision selective Dynamic Flow, Static Graph: KV Cache Reuse for Efficient LLM Serving on Mobile NPUsEuroSys โ27, April 19โ23, 2027, Rabat, Morocco KV recompute graph, where the deviation computation and Top-K comparison are all conducted onFP16precision. We further apply a scale factor 1 โ ํท โํํํ to scale down the interme- diate deviation tensor to preventFP16overflow. Such mixed- precision quantization successfully preserves the model pre- cision, verified in the ablation study. 4.2 Inter-Graph Design for Dynamic Reuse Pattern Within an input prompt, prefix reusable, non-prefix reusable, and new tokens may come interleavingly (dynamicity 5 โ). They invoke distinct graph calls by default: prefix reuse to- kens incur no graph calls, non-prefix reusable tokens are processed by the selective recomputation graph, and new tokens are processed by the full prefill graph. A naive sched- ule which invokes static graphs solely according to token types may cause fragmentation between tokens of different types, often producing underfilled graph calls and wastes computation due to padding. To address this inefficiency under dynamic patterns, we propose a chunk merging algo- rithm based on dynamic programming to improve the static graph utilization. The key observation is that non-cached new tokens can be safely processed by the selective recomputation graph, since they are always selected for computation. Our algorithm can dynamically merge new tokens into adjacent under-utilized selective recomputation graphs to improve efficiency. Letํ[ํ]be the minimum latency to process tokens up to positionํ. For the last chunk ending atํ, we consider 2 choices: using the selective recomputation graph or using the prefill graph. This yields the optimal substructure transition of dynamic programming: ํ[ํ]= min ํ[ํโํ ํ (ํ)]+ํก ํ , ํ[ํโํ ํ (ํ)]+ํก ํ ,(4) whereํก ํ andํก ํ are the per-call latency of the selective re- computation and prefill graphs, respectively. Here,ํ ํ is the maximum suffix length ending atํthat can be absorbed by one selective recomputation graph call under graph capacity and recomputation-ratio constraint (i.e., at leastํnon-prefix tokens can be recomputed).ํ ํ is the maximum suffix length ending atํthat can be processed by one prefill graph call under its capacity. Intuitively,ํ ํ may include both non-prefix reuse tokens and a bounded number of adjacent new tokens, whereasํ ํ simply packs as many trailing tokens as the prefill graph allows. In Equation 4, the first termํ[ํโํ ํ (ํ)]+ํก ํ is the optimum of the subproblem if the recomputation graph is used, while the second termํ[ํโํ ํ (ํ)]+ํก ํ corresponds to using the prefill graph. The dynamic program therefore globally chooses whether each trailing chunk should be ex- ecuted by recomputation or prefill, rather than making a purely local greedy decision. The formal formulation of this constrained graph scheduling and complete pseudo code are provided in the supplementary material. Figure 8 shows a toy example: when the recomputation graph processes up to 4 tokens, the prefill graph processes prefix non-prefixnewreusenew mergemerge merge prefix non-prefixnewreusenew 1 2 3 456789101116171819121314 15202122 prefix reuse non-prefix reuse new new 1 2 3 456789101116171819121314 15202122 w/o chunk merge SR:4,P: 4 w/ chunk merge SR: 4, P: 2 merged Selective Recompute Graph Call Prefill Graph Call merged merged non-prefix reuse Figure 8. Chunk merging algorithm example, which saves 2 prefill graph calls and reducesโ 25% latency. up to 2 tokens, andํ=50%, new tokens 12, 15, and 20 can be merged into adjacent recomputation calls. As a result, the number of prefill graph invocations is reduced from 4 to 2, yielding an approximate 25% latency reduction by utilizing otherwise underfilled recomputation graphs. 4.3 Generality of Our Design Our compute-side design is not specific to Qualcomm HTP. It is applicable to mobile accelerators that expose ahead-of- time compiled static graphs over fixed-shape tensors, such as MediaTek APU and Apple ANE. Under this execution model, the intra-graph mechanisms in ยง4.1, including chunkโpadโ mask and scatterโgather, can be expressed using standard tensor operators supported by these backends. The inter- graph scheduler in ยง4.2 depends only on the capacity and measured latency of the available pre-compiled graphs, and is therefore independent of a particular accelerator imple- mentation. Porting to a new backend requires recalibrating the graph sizesํฟ ํ andํฟ ํ and the hardware-specific align- ment granularity following the procedure in ยง4.1. Thus, we expect migration to require backend integration and profil- ing rather than redesigning the compute-side mechanisms. 5 On-Device Hierarchical KV Storage To stably supply reusable KV tensors to NPU under the strict on-device memory bandwidth and capacity constraints, we design a hierarchical KV storage system upon the on-device memory hierarchy. Inside, the data structures in memory and flash storage leverage heterogeneous memory characteris- tics to balance reuse efficiency and data movement overhead. Prefetch and eviction policies are also activated to mitigate cache misses across memory and storage tiers and conse- quently reduce end-to-end latency. The architectural design of KV caching system is illustrated in Figure 9. The system majorly consists of 3 structures: NPU KV manager, CPU KV memory pool, and the flash KV DB. During the work- flow, KV tensors are efficiently matched and loaded from the flash DB and (pre)fetched to the CPU memory pool. When transmission signals of NPU are received, the tensors are further transferred to the CPUโNPU shared buffer for NPU to consume. EuroSys โ27, April 19โ23, 2027, Rabat, MoroccoZhengxiang Huang et al. Shared Buffer Hierarchical KV Memory Design NPU TCM NPU KV Manager NPU Logic Memory Bus CPU KV Pool Hash Table Merger Flash KV DB Hash Table Index Map (Pre)fetcher Evictor Locality & Cost Evaluator 4 567 123 ร evict ร evict 134 67 still non-prefix prefix non-prefix losethepotential of being part of a prefix Figure 9. On-device hierarchical KV caching system. 5.1 NPU-CPU In-Memory KV Manager NPU KV Manager. A fixed-size (context-length) KV buffer on CPUโNPU shared buffer, typically on the order of 10 1 MB is allocated by the NPU KV manager. This buffer contains the KV cache of the running session, where NPU directly loads KV tensors in this region with DMA into TCM and consumes it by the matrix unit. The manager controls its sharing behavior between CPU and NPU and updates the buffer throughout LLM executions. CPU KV Memory Pool. A medium-sized KV pool is main- tained in CPU memory, typically on the order of 10 2 MB, and is implemented as a lightweight hash table based structure that indexes cached KV tensors using their corresponding un- derlying database row IDs. To save memory, the pool stores KV chunks that are either newly generated by the NPU or (pre)fetched from flash storage, rather than being a full tree- based structure as cloud-based existing works [21,53]. Upon receiving a new input request, the system first queries the CPU KV pool before accessing flash storage to enable low- latency reuse. Eviction is triggered under system memory pressure, such as when available memory becomes limited due to contention from other mobile applications. 5.2 Prefix and Non-Prefix Hybrid Structure in Flash We organize KV caches in on-device flash storage using a treeโhashโindex hybrid structure implemented on top of SQLite [13], which jointly supports both prefix-based and non-prefix KV reuse while maintaining efficient lookup and moderate storage overhead. This storage layer is designed to operate at GB scale and can dynamically trigger eviction when requested by user or system under storage pressure. Specifically, following prior work [21,53], we construct a prefix tree to support efficient prefix reuse and hierarchi- cal organization of cached KV entries. However, tree-based structures alone cannot efficiently support non-prefix reuse. To address this limitation, we augment the structure with both hash-based and semantic indexing mechanisms. For non-prefix reuse, each cached KV chunk is associated with a compact 64-bit hash code, enabling fast lookup of identical reusable chunks. For subchunk-level reuse, we additionally maintain lightweight semantic indices, including sparse em- bedding based on extracted keywords and truncated dense embedding vectors. Dense embedding is only in RAG use cases where embedding is already computed and stored in the workflow. This structure enables fast localization of poten- tial non-prefix chunk candidates that may contain reusable subchunk sequences, even when the text is not identical at chunk level. Linear-time fast longest common substring (LCS) algorithm is further applied to identify and finalize the reusable subchunks among the retrieved candidates. Together, the prefix tree for prefix reuse, and hash table and semantic index for non-prefix reuse, form a unified flash storage organization that supports both types of KV reuse across diverse long-context workloads. The detailed data- base schema and storage organization are described in the supplementary material. 5.3 Prefetch and Eviction Asynchronous Prefetch. To improve prefix hit rate in the CPU memory pool, the system performs asynchronous prefetch between flash and main memory. During idle I/O periods, prefix-reusable chunks with high predicted reuse likelihood are proactively loaded into memory to reduce fu- ture access latency. To avoid unnecessary memory pollution, the prefetch policy selectively prioritizes chunks that are likely to participate in future prefix reuse or are strongly correlated with recently accessed chunks. Cost-Aware Eviction. We jointly consider chunk reusabil- ity and eviction overhead to compute an overall eviction score for each chunk. Chunks that are both highly reusable and expensive to recompute or reload are preferentially re- tained under constrained memory and storage budgets, while lower-value chunks are evicted when necessary. This im- proves cache utilization and reduces end-to-end TTFT. For chunks in the CPU memory pool, eviction overhead mainly corresponds to reload latency from flash storage for prefix-reusable chunks, while the cost for non-prefix- reusable chunks is negligible because their loading latency can largely overlap with execution (ยง 6.1). For chunks stored in flash, eviction may incur not only the recomputation cost of the evicted chunk itself, but also additional overhead from disrupting the prefix reuse chain. In particular, evicting a chunk on a prefix path can cause its descendant chunks to lose prefix reusability (Figure 20), thereby increasing future recomputation cost. Our eviction policy explicitly models this cascading effect when making retention decisions. Dynamic Flow, Static Graph: KV Cache Reuse for Efficient LLM Serving on Mobile NPUsEuroSys โ27, April 19โ23, 2027, Rabat, Morocco Shared Buffer Hierarchical KV Memory Design NPU TCM NPU KV Manager NPU Logic Memory Bus CPU KV Pool Hash Table Merger Flash KV DB Hash Table Index Map (pre)fetcher LRAE Evictor Locality & Cost Evaluator 4 567 123 ร evict ร evict 134 67 still non-prefix prefix chain non-prefix losethepotential of being part of a prefix Figure 10. Evicting chunks on a prefix chain breaks future prefix reuse for subsequent chunks. 6 ComputeโStorage Pipeline Overlap Due to the limited bandwidth of on-device memory hier- archies, optimizing compute and storage independently is insufficient. Our system overlaps KV loading, rerotation, storing, and NPU execution through asynchronous pipeline parallelism to hide data-movement latency. 6.1 KV Loading Latency Hiding During KV preparation, KV tensors are retrieved from stor- age and rerotated for non-prefix reuse before being con- sumed by the NPU. KV CPU K Cache Rerotation Cached KV @ H.T SpinQuant Dequant Rerotate RoPE @ H SpinQuant Requant RerotatedKV INT8 FP16 Dequant Quant NPU NPU CPU C0S0 C0S1 C0 S0 C0 S0 C0 S1 C1S0C1S1 C1 S0 C1 S1 (KV Load) (KV Rerotate) C0 S1 C1 S0 C1 S1 Input Chunk 0, Shard 0 C0S0 (a) CPU KV rerotation. KV CPU K Cache Rerotation Cached KV @ H.T SpinQuant Dequant Rerotate RoPE @ H SpinQuant Requant RerotatedKV INT8 FP16 Dequant Quant NPU NPU CPU C0S0 C0S1 C0 S0 C0 S0 C0 S1 C1S0C1S1 C1 S0 C1 S1 (KV Load) (KV Rerotate) C0 S1 C1 S0 C1 S1 Input Chunk 0, Shard 0 C0S0 (b) IOโCPUโNPU pipeline parallelism of KV preparation and LLM inference. Figure 11. IOโCPUโNPU overlapping pipeline. IO-CPU-NPU Overlapping. To enable non-prefix KV reuse, the rotary embedding (RoPE) of K tensors is rerotated according to their original positions in cached prompts and their new positions in incoming queries [15,50,51]. In the quantized on-device workflow, this process additionally in- volves KV dequantization and requantization with Hadamard transforms introduced by 8-bit SpinQuant [27]. Since rerota- tion is memory-intensive 1 , it is assigned to the CPU and overlapped with compute-intensive NPU execution. As il- lustrated in Figure 11(a), both I/O-intensive KV loading and memory-intensive rerotation are executed asynchronously on the CPU to avoid stalling the NPU. 1 Fast WalshโHadamard transformation hasํ(ํ logํ)complexity and is memory-intensive in our setting. w/o shard ppw/ shard p 0 20 40 60 Latency (ms) loading (a) Shard-level parallelism re- duces prefix loading time 4ร. No ppCPU ppCPU-NPU p 0 50 100 150 200 250 Latency (ms) loading rerotation NPU execution (b) IOโCPU-NPU parallelism makes data preparation latency invisible to NPU execution. Figure 12. Hiding KV loading and rerotation latency via pipeline parallelism. (Qwen3-1.7B on Xiaomi 15 Pro) Chunk-Shard Two-Dimensional Pipeline Parallelism. Mobile NPUs execute LLMs in multiple model shards while prompts are processed in chunks [47], enabling pipeline par- allelism along both dimensions. As illustrated in Figure 11(b), while the NPU executes shards of Chunk 0, the CPU concur- rently prepares KV tensors for upcoming shards of Chunk 0 and subsequent Chunk 1. Figure 12 shows that incorporating shard-level parallelism reduces the non-overlapped loading latency of prefix chunks and the first non-prefix chunk by 4ร. Overall, this two-dimensional pipeline substantially in- creases overlap opportunities and effectively hides KV load- ing and rerotation latency. 6.2 KV Storing Latency Hiding Synchronously serializing KV tensors from the CPU memory pool to flash storage can introduce substantial user-visible latency due to limited secondary-storage bandwidth. To mit- igate this overhead, we adopt a lazy and asynchronous KV persistence mechanism. Instead of synchronously writing KV tensors to flash im- mediately after generation, newly produced KV chunks are first retained in the CPU memory pool and marked as dirty entries, while the actual serialization and storage operations are deferred and executed asynchronously by background threads when the I/O bus is idle. For example, KV storing can be overlapped with decoding. In addition, write operations are batched whenever possible to reduce flash I/O amplifi- cation and metadata overhead. This design effectively hides most flash write latency from the critical inference path. 7 Evaluation 7.1 Experimental Setup Use Cases and Datasets. We take the following three representative on-device LLM use cases. โข For document QA, we randomly sample 400 easy-level queries from HotpotQA [49]. For each query, we split its associated context into 1024-character chunks to EuroSys โ27, April 19โ23, 2027, Rabat, MoroccoZhengxiang Huang et al. build the context chunks document database, and re- trieve the top-6 chunks based on the L2 distance be- tween embeddings generated by Qwen3-Embedding- 0.6B [52]. โขFor long chat history QA, we use LoCoMo-MC10 [34], derived from LoCoMo [29]. Two sessions of very long chat history with 74 single-hop QA questions are se- lected to evaluate reuse under long conversation con- texts. Top-6 related dialog chunks are retrieved and combined into the prompt, with the same setting as HotpotQA. โขFor agent skill use, we construct a skill-oriented eval- uation set from SkillsBench [6], including 10 shared skills and 39 associated task instructions. Each test- ing sample contains a reusable skill description and a task instruction, enabling evaluation under shared skill contexts. These workloads cover both contiguous prefix reuse and more general non-prefix reuse patterns, where reusable con- tent may appear as retrieved document chunks, historical conversation segments, or shared skill descriptions. Devices. Our evaluation includes one mid-range device, Meizu 21, and two high-end devices, Xiaomi 15 Pro and Honor Magic 8. Their hardware specifications are summa- rized in Table 2. All experiments are conducted using the Qualcomm Hexagon NPUs available on these devices. Table 2. Mobile devices evaluated in our experiments. DeviceSoCMemCPUGPUNPU Meizu 21 Snapdragon12GB1*Cortex-X4+5*A720 Adreno Hexagon 8 Gen 3+256GB+2*A520750V75 Xiaomi 15 Pro Snapdragon16GB 8*Oryon Adreno Hexagon 8 Elite+512GB830V79 Honor Magic 8 Snapdragon12GB 8*Oryon Adreno Hexagon 8 Elite Gen 5 +512GB840V81 Models. We take Qwen3-1.7B and Qwen3-4B [39], and Llama3.2-1B-Instruct and Llama3.2-3B-Instruct [37,38]. Mod- els are majorly quantized into Int4. Base Engine and NPU Backend. We adopt ExecuTorch [12] as the base mobile LLM engine, which provides state-of-the- art performance on NPUs together with a stable and exten- sible deployment framework for on-device LLM inference. We target Qualcomm HTP NPUs, motivated by their broad deployment and mature public software stack. Baselines. We compare against three baselines represent- ing different KV reuse strategies: โขno reuse: the original ExecuTorch [12] implementation without KV reuse. โขprefix caching: an implementation with tree-based pre- fix caching, reproducing SGLANG Radix-Tree prefix reuse on device [53]. โขfull reuse: an implementation that directly reuses both prefix and non-prefix KV chunks without selective recomputation, reproducing Prompt Cache full reuse on device [15]. The KV storage backend used by the prefix caching and full reuse baselines is also implemented by us on top of SQLite to ensure a fair comparison under the same on-device stor- age stack. We do not directly compare against cloud-based systems, such as vLLM, SGLang, LMCache, or RAGCache, because they are designed for GPU server environments and do not support mobile hardware. Metrics. For all three use cases, we report the average TTFT (ms) over representative datasets to evaluate system efficiency. In addition, to validate the effectiveness of our CacheBlend style selective recomputation algorithm for non- prefix reuse on mobile devices, we evaluate generation qual- ity on the document QA and chat-history QA workloads and report the corresponding accuracy. We also report the average system power and total energy consumption during prefill, measured via Android BatteryManager, to evaluate whether latency reductions translate into energy savings. Key Configurations. The graph sizes of the NPU selec- tive recomputation graph and prefill graph are set to the latency-optimal values identified in ยง 4.1:ํฟ ํ =512 and ํฟ ํ =128. To preserve generation quality while fully utiliz- ing the HMX GEMM tiles [17], the recomputation ratio is set toํ=0.25, ensuring that intermediate tensor shapes remain multiples of 32. 7.2 End-to-End Improvements Reduced TTFT with Negligible Quality Degradation. Figure 14 illustrates the qualityโlatency tradeoff on Hot- potQA and LoCoMo using Qwen3-1.7B and Qwen3-4B on Xiaomi 15 Pro. The ideal operating region lies in the upper- left corner, corresponding to lower TTFT and higher task accuracy. Compared with no reuse and prefix caching, our system substantially shifts the operating point toward this region, reducing TTFT by approximately 40%โ60% with onlyโค4% accuracy degradation. Although prefix caching preserves full precision, its latency improvement is limited because it only exploits reusable contiguous prefixes. In contrast, the more aggressive full reuse achieves slightly lower TTFT but incurs significant quality degradation (ap- proximately 30%) due to direct non-prefix KV reuse without selective recomputation. Moreover, full reuse is only 12% faster than our approach because its rerotation overhead cannot be effectively hidden through pipeline overlap and becomes exposed on the critical path. Therefore, we exclude full reuse from the subsequent evaluations. Efficiency Evaluation across Tasks, Models, and De- vices. Figure 13 compares TTFT among no reuse, prefix caching, Dynamic Flow, Static Graph: KV Cache Reuse for Efficient LLM Serving on Mobile NPUsEuroSys โ27, April 19โ23, 2027, Rabat, Morocco 0 500 1000 1500 Qwen3-1.7B Meizu 21Xiaomi 15 ProHonor Magic 8 0 1000 2000 3000 4000 Qwen3-4B-Instruct-2507 N/A 0 500 1000 1500 2000 Llama3.2-1B-Instruct no reuse prefixours 0 1000 2000 3000 Llama3.2-3B-Instruct no reuse prefixoursno reuse prefixours no reuseprefix cachingours (a) HotpotQA: our design reduces 32โ56% TTFT. 0 500 1000 1500 2000 2500 Qwen3-1.7B Meizu 21Xiaomi 15 ProHonor Magic 8 0 1000 2000 3000 4000 5000 Qwen3-4B-Instruct-2507 N/A 0 500 1000 1500 2000 2500 Llama3.2-1B-Instruct no reuse prefixours 0 1000 2000 3000 4000 Llama3.2-3B-Instruct no reuse prefixoursno reuse prefixours no reuseprefix cachingours (b) LoCoMo: our design reduces 42โ65% TTFT. 0 500 1000 1500 2000 Qwen3-1.7B Meizu 21Xiaomi 15 ProHonor Magic 8 0 1000 2000 3000 4000 5000 Qwen3-4B-Instruct-2507 N/A 0 500 1000 1500 2000 Llama3.2-1B-Instruct no reuse prefixours 0 1000 2000 3000 Llama3.2-3B-Instruct no reuse prefixoursno reuse prefixours no reuseprefix cachingours (c) SkillsBench: ours design reduces 68โ81% TTFT. Figure 13. End-to-end TTFT across 3 workloads, 4 LLMs, and 3 smartphones. Our system consistently reduces TTFT compared with no reuse (original ExecuTorch) and prefix caching. The TTFT reduction ranges in each subcaption are measured against original ExecuTorch across all available model-device pairs. Figure 14. Qualityโlatency tradeoff on HotpotQA and Lo- CoMo using Qwen3-1.7B and Qwen3-4B on Xiaomi 15 Pro. Our system (yellow star) reduces TTFT substantially while preserving generation quality. and ours across different workloads, LLMs, and smartphones. Across all configurations, our system consistently achieves the lowest TTFT, delivering 1.5รโ5.4รprefill speedup over no reuse and 1.3รโ2.5ร speedup over prefix caching. In the agent skill-use workload, reuse patterns are largely prefix-dominated because multiple tasks share the same skill descriptions and tool instructions. As a result, both prefix caching and our system reduce TTFT by more than 50%. Our system further improves over prefix caching through opti- mized prefetching and computeโstorage pipeline overlap. In contrast, document QA and long-chat workloads ex- hibit substantially more non-prefix reuse. Retrieved docu- ment chunks or dialog histories are dynamically assembled into prompts with different orders and combinations, mak- ing reusable prefixes cache hits much more difficult. Under such patterns, prefix caching achieves only limited gains (1.1ร-1.2ร), especially on mobile devices where constrained memory capacity causes frequent Radix-Tree eviction and prevents caching all prompt combinations. In contrast, by supporting both prefix and non-prefix KV reuse through selective recomputation, our system continues to achieve substantial TTFT reduction, providing 1.5รโ2.9รspeedup in these workloads. Energy Reduction. We measure prefill energy consump- tion on Xiaomi 15 Pro with Qwen3-4B-Instruct-2507 across the three datasets and compare our system against no reuse. Our system maintains a comparable average power draw to no reuse: 6.34 W vs. 6.68 W, indicating that the additional KV management operations do not materially increase system power. Consequently, the reduction in prefill latency directly EuroSys โ27, April 19โ23, 2027, Rabat, MoroccoZhengxiang Huang et al. translates into lower energy consumption. As shown in Ta- ble 3, our system reduces prefill energy by 52% on HotpotQA, 67% on LoCoMo, and 77% on SkillsBench. These reductions closely track the corresponding TTFT improvements in ยง7.2, confirming that our system substantially reduces both la- tency and energy consumption. Table 3. Prefill energy reduction measured on Xiaomi 15 Pro with Qwen3-4B-Instruct-2507 across 3 datasets. Energy (J) HotpotQA LoCoMo SkillsBench No Reuse24.7632.6118.02 Ours11.8910.754.13 -52.0%-67.0%-77.1% 7.3 Sensitivity Analysis For a better understanding of on-device KV reuse mechanism, we analyze how the reuse ratio and prompt length affect the end-to-end prefill latency. We report the latency reduction range across all available model-device pairs. Varying Prefix Reuse Ratio. Figure 15 shows that prefix reuse consistently reduces prefill latency as the reuse ratio in- creases, and the benefit becomes more significant for longer prompts. At 3072 tokens, the full-prefill baseline takes 2.15โ 5.93 s across different models and devices. With 75% prefix reuse, our system reduces the prefill latency by 1.54โ4.43 s, corresponding to a 67.4โ78.3% reduction. When the reuse ratio reaches 100%, the latency reduction improves to 94.1โ 99.7%, leaving 9โ215 ms residual prefill latency. These results indicate that when reusable KV cache forms a contiguous prefix, our system can reuse with little extra overhead, while the speedup is more obvious for higher hit ratio. Varying Non-Prefix Reuse Ratio. Figure 16 shows that non-prefix reuse also reduces end-to-end prefill latency, al- though the residual latency is higher than prefix reuse. At 3072 tokens, 100% non-prefix reuse reduces the prefill latency by 1.08โ3.80 s, corresponding to a 44.9โ67.9% reduction over the no-reuse baseline. The remaining latency, 0.87โ1.99 s, is due to non-prefix reuse and selective recompute over- head. Nevertheless, the end-to-end prefill latency remains substantially lower than full prefill, showing that the saved model computation outweighs the extra reuse-management overhead. Overall, the results demonstrate that our method is con- sistently effective across different mobile devices and LLMs. Higher reuse ratios lead to larger latency reductions, and longer prompts further amplify the benefit of KV reuse. Prefix reuse provides the largest improvement due to its contiguous- cache structure, while non-prefix reuse offers a more general reuse capability with moderate additional overhead. Figure 15. TTFT under different prefix reuse ratios and input lengths across 3 mobile devices and 4 models. Figure 16. TTFT under different non-prefix reuse ratios and input lengths across 3 mobile devices and 4 models. 7.4 Ablation Study We decompose end-to-end latency into five components: prefix/non-prefix matching, eviction and storage, KV load- ing, KV rerotation, and NPU execution. Under the full system configuration, NPU execution dominates TTFT, accounting for more than 95% of total latency, indicating that the over- head introduced by KV reuse is largely hidden and amortized. As is illustrated in Figure 17, removing individual sys- tem designs introduces noticeable overheads at different stages. In particular, disabling graph-size optimization and Dynamic Flow, Static Graph: KV Cache Reuse for Efficient LLM Serving on Mobile NPUsEuroSys โ27, April 19โ23, 2027, Rabat, Morocco ours fullbaseline (ExecuTorch) w/o graph size optimization (ยง4.1) w/o chunk merge (ยง4.2) w/o CPU pool (ยง5.1) w/o flash structure (ยง5.2) w/o cost-aware eviction (ยง5.3) w/o 2-dim P (ยง6.1) w/o overlap store (ยง6.2) 0 1 2 Relative Latency 2.33x 1.48x 1.23x 1.21x 2.00x 1.64x 1.54x 1.96x matchingeviction/storingloadingrerotationNPU execution Figure 17. Ablation study and latency decomposition on Qwen3-1.7B, LoCoMo dataset, Xiaomi 15 Pro. Disabling individual components from our design increases TTFT by 1.21โ2.33ร. the chunk-merge algorithm reduces graph utilization effi- ciency and increases overall latency by 48% and 23%, re- spectively. Removing the CPU memory pool increases KV loading latency from flash storage, adding approximately 20% latency. Replacing our hybrid structure in flash storage with a simple SQLite BLOB-based DB with naive structure increases matching overhead by an order of magnitude and nearly doubles overall latency. Disabling the eviction pol- icy reduces the hit rate of non-prefix-reusable chunks by approximately threefold, resulting in a 60% latency increase. Without IOโCPUโNPU pipeline parallelism, KV loading and rerotation can no longer overlap with NPU execution, in- creasing latency to 1.5ร. Similarly, disabling asynchronous KV storage exposes synchronous flash serialization overhead on the critical path and nearly doubles latency. Overall, these results demonstrate that each major compo- nent contributes substantially to reducing end-to-end latency and improving KV reuse efficiency. 8 Related Works Cloud-Based KV Reuse and Caching Systems. Cloud- based KV caching systems focus on organizing reusable KV caches across requests and cloud-based storage hierarchies. SGLANG [53] and RAGCache [21] employ prefix-aware tree structures, namely Radix Tree and knowledge tree, to store reusable prefixes. For non-prefix reuse, CacheBlend [50] in- troduces a distributed KV storage and retrieval mechanism. More generally, LMCache [26] provides a unified KV-cache layer for cache lookup, migration, and cross-engine sharing. Strata [46] studies hierarchical context caching for long- context serving, while Mooncake [36] advocates a KV-cache centric architecture that trades additional local storage for reduced recomputation. InfiniGen [23] further accelerates KV access through essential-KV-only prefetching. On-Device LLM Acceleration. Existing approaches for accelerating on-device LLM inference primarily focus on optimized GEMM kernels, heterogeneous computing, quan- tized execution, and model sparsity. ExecuTorch [12] provides high-performance NPU back- ends for Apple, MediaTek, and Qualcomm platforms through extensible and stable interfaces. MNN [28,42] improves mo- bile CPU and GPU inference through optimized KV-cache and weight layouts that enhance memory locality. Medi- aPipe [11] (built on LiteRT [10]) and MLC-LLM [30] (built on TVM [8]) primarily optimize GPU-based prefill, while mllm [47] accelerates with optimized NPU GEMM kernels. SmartMem [32] reduces memory overhead by eliminating unnecessary NC4HW4 GPU layout transformations self- attention and GEMM execution. NPU flash attention and mixed-precision GEMM optimization [17] are also explored in recent works. To better utilize memory bandwidth, Het- eroLLM [7] introductions GPUโNPU co-execution paral- lelism. T-MAC [43] and T-MAN [44] leverage table-lookup based quantized kernels for efficient CPU and NPU inference. PowerInfer 2 [48], Apple Intelligence [3], and Neuralink [41] exploit activation sparsity for efficient weight offloading. Despite these extensive optimization efforts, KV reuse remains unexplored in prior on-device LLM systems. On-Device Tensor Storage Systems. SQLite [13], a widely used on-device database system, provides BLOB support for tensor storage but lacks tensor-specific optimizations. Exist- ing systems such as MicroNN [35] and MobileRAG [33] focus on mobile vector databases, prioritizing embedding storage and building fast indices for vector approximate nearest neighbor (ANN) searches. Walle [28] and SFSL [31] provide updateable FlatBuffers-based [1] tensor-storage systems for fixed-sized model weights and embeddings, but inefficient for dynamic-sized KV tensors. For KV storage, SparKV [25] stud- ies deviceโcloud KV transfer for mobile LLM inference, while MobiLoRA [24] introduces an on-device KV-cache design for multi-LoRA scenarios, but both consider intra-session runtime small-scale KV storage only. However, persistent and dynamically updateable hierar- chical KV storage architectures tailored for on-device KV reuse have not been studied in existing work. 9 Conclusion In this work, we have designed and built an on-device KV reuse system to accelerate LLM inference on mobile NPUs. At the compute layer, we have transformed the dynamic selective recomputation workflow of non-prefix reuse into EuroSys โ27, April 19โ23, 2027, Rabat, MoroccoZhengxiang Huang et al. efficient static graphs for mobile NPUs. At the storage layer, we have designed a hierarchical KV caching system with hybrid indexing structures for efficient matching and reuse of prefix and non-prefix KV tensors. Compute and storage are further pipelined and overlapped to hide system over- heads. Our implementation on Qualcomm Hexagon NPUs demonstrates that efficient non-prefix KV reuse is practical on commodity smartphones. Across representative work- loads, LLMs, and devices, our system consistently reduces TTFT over no reuse and prefix-only caching baselines, while maintaining negligible quality degradation. More broadly, this work provides a foundation for scalable long-context inference on resource-constrained mobile devices and open new opportunities for local-first personal intelligence that increasingly rely on persistent and reusable context. Acknowledgments We sincerely thank all the reviewers and our anonymous shepherd for instructive comments. This work was supported in part by China NSF grant (No. 62572299, No. 62441236, No. 62372296, No. 62432007, No. U24A20326, No. U25A6024, No. U25A20437), the Key Research and Development Program of Zhejiang Province (No. 2024C03270), Alibaba Innovation Re- search (AIR) Program (No. 56657574-1), CCF-Tencent Rhino- Bird Open Research Fund (No. RAGR20260126), and SJTU- Huawei Explore X Gift Fund. References [1]Google 2025. FlatBuffers: Memory Efficient Serialization Library. Google. https://github.com/google/flatbuffers [2] Google 2026. Gemini Introduces Personal Intelligence.Google. https://blog.google/innovation-and-ai/products/gemini- app/personal-intelligence/ [3]Keivan Alizadeh, Seyed Iman Mirzadeh, Dmitry Belenko, S. Khatam- ifard, Minsik Cho, Carlo C Del Mundo, Mohammad Rastegari, and Mehrdad Farajtabar. 2024. LLM in a flash: Efficient Large Language Model Inference with Limited Memory. In Proceedings of the 62nd An- nual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). Association for Computational Linguistics, Bangkok, Thailand, 12562โ12584. [4] Apple. 2024. Introducing Appleโs On-Device and Server Founda- tion Models. https://machinelearning.apple.com/research/introducing- apple-foundation-models. [5] Apple Inc. 2026. Apple Intelligence. https://w.apple.com/apple- intelligence/. [6]benchflow ai. 2026. SkillsBench:The first benchmark for evaluat- ing how well AI agents use skills. https://github.com/benchflow- ai/skillsbench. [7]Le Chen, Dahu Feng, Erhu Feng, Yingrui Wang, Rong Zhao, Yubin Xia, Pinjie Xu, and Haibo Chen. 2025. Characterizing Mobile SoC for Accelerating Heterogeneous LLM Inference. In Proceedings of the ACM SIGOPS 31st Symposium on Operating Systems Principles (SOSP โ25). Association for Computing Machinery, New York, NY, USA, 359โ374. [8]Tianqi Chen, Thierry Moreau, Ziheng Jiang, Lianmin Zheng, Eddie Yan, Meghan Cowan, Haichen Shen, Leyuan Wang, Yuwei Hu, Luis Ceze, Carlos Guestrin, and Arvind Krishnamurthy. 2018. TVM: an automated end-to-end optimizing compiler for deep learning. In Pro- ceedings of the 13th USENIX Conference on Operating Systems Design and Implementation (OSDI โ18). USENIX Association, Carlsbad, CA, USA, 579โ594. [9] Hongchao Du, Shangyu Wu, Qiao Li, Riwei Pan, Jinheng Li, Youcheng Sun, and Chun Jason Xue. 2026. ClawMobile: Rethinking Smartphone- Native Agentic Systems. In Proceedings of the Sixth European Workshop on Machine Learning and Systems (EuroMLSys โ26). Association for Computing Machinery, 370โ376. [10]Google AI Edge. 2025. LiteRT overview. https://ai.google.dev/edge/ litert. [11]Google AI Edge. 2025. MediaPipe Solutions guide. https://ai.google. dev/edge/mediapipe/solutions/guide. [12]PyTorch Foundation. 2025. GitHub - pytorch/executorch: On-device AI across mobile, embedded and edge for PyTorch. https://github.com/ pytorch/executorch. [13] Kevin P. Gaffney, Martin Prammer, Larry Brasfield, D. Richard Hipp, Dan Kennedy, and Jignesh M. Patel. 2022. SQLite: past, present, and future. Proc. VLDB Endow. 15, 12 (Aug. 2022), 3535โ3547. [14]Georgi Gerganov. 2026. GitHub - ggml-org/llama.cpp: LLM inference in C/C++. https://github.com/ggml-org/llama.cpp. [15] In Gim, Guojun Chen, Seung-seob Lee, Nikhil Sarda, Anurag Khandel- wal, and Lin Zhong. 2024. Prompt Cache: Modular Attention Reuse for Low-Latency Inference. In Proceedings of Machine Learning and Systems (MLsys โ24, Vol. 6). 325โ338. [16]Google. 2026. Google AI Edge Gallery. https://play.google.com/store/ apps/details?id=com.google.ai.edge.gallery [17]Zixu Hao, Jianyu Wei, Tuowei Wang, Minxing Huang, Huiqiang Jiang, Shiqi Jiang, Ting Cao, and Ju Ren. 2026. Scaling LLM Test-Time Com- pute with Mobile NPU on Smartphones. In Proceedings of the 21st European Conference on Computer Systems (Eurosys โ26). Association for Computing Machinery, New York, NY, USA, 2157โ2172. [18] Apple Inc. 2026. CoreML Documentation. https://developer.apple. com/documentation/coreml. [19]MediaTek Inc. 2026. NeuroPilot Documentation. https://neuropilot- developer.mediatek.com/sphinx/neuropilot-8-public/html/. [20]Qualcomm Technologies Inc. 2026. Qualcomm Documentation โ HTP Backend. https://docs.qualcomm.com/doc/80-63442-10/topic/htp_ backend.html. [21]Chao Jin, Zili Zhang, Xuanlin Jiang, Fangyue Liu, Shufan Liu, Xuanzhe Liu, and Xin Jin. 2025. RAGCache: Efficient Knowledge Caching for Retrieval-Augmented Generation. ACM Trans. Comput. Syst. 44, 1, Article 2 (Nov. 2025), 27 pages. [22] Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph Gonzalez, Hao Zhang, and Ion Stoica. 2023. Efficient Memory Management for Large Language Model Serv- ing with PagedAttention. In Proceedings of the 29th Symposium on Operating Systems Principles (SOSP โ23). Association for Computing Machinery, New York, NY, USA, 611โ626. [23]Wonbeom Lee, Jungi Lee, Junghwan Seo, and Jaewoong Sim. 2024. InfiniGen: efficient generative inference of large language models with dynamic KV cache management. In Proceedings of the 18th USENIX Con- ference on Operating Systems Design and Implementation (Santa Clara, CA, USA) (OSDIโ24). USENIX Association, USA, Article 9, 18 pages. [24] Borui Li, Yitao Wang, Haoran Ma, Ligeng Chen, Jun Xiao, and Shuai Wang. 2025. MobiLoRA: Accelerating LoRA-based LLM Inference on Mobile Devices via Context-aware KV Cache Optimization. In Proceed- ings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). Association for Computational Linguistics, Vienna, Austria, 23400โ23410. [25]Hongyao Liu, Liuqun Zhai, Junyi Wang, Zhengru Fang, Jingshu Chen, and Jun Huang. 2026. SparKV: Overhead-Aware KV Cache Loading for Efficient On-Device LLM Inference. IEEE Internet of Things Journal 13, 14 (2026), 30016โ30027. [26]Yuhan Liu, Yihua Cheng, Jiayi Yao, Yuwei An, Xiaokun Chen, Shaoting Feng, Yuyang Huang, Samuel Shen, Rui Zhang, Kuntai Du, and Junchen Dynamic Flow, Static Graph: KV Cache Reuse for Efficient LLM Serving on Mobile NPUsEuroSys โ27, April 19โ23, 2027, Rabat, Morocco Jiang. 2025. LMCache: An Efficient KV Cache Layer for Enterprise- Scale LLM Inference. arXiv:2510.09665 [cs.LG] https://arxiv.org/abs/ 2510.09665 [27]Zechun Liu, Changsheng Zhao, Igor Fedorov, Bilge Soran, Dhruv Choudhary, Raghuraman Krishnamoorthi, Vikas Chandra, Yuandong Tian, and Tijmen Blankevoort. 2025. SpinQuant: LLM Quantization with Learned Rotations. In Proceedings of The Thirteenth International Conference on Learning Representations (ICLR โ25). 24 pages. [28]Chengfei Lv, Chaoyue Niu, Renjie Gu, Xiaotang Jiang, Zhaode Wang, Bin Liu, Ziqi Wu, Qiulin Yao, Congyu Huang, Panos Huang, Tao Huang, Hui Shu, Jinde Song, Bin Zou, Peng Lan, Guohuan Xu, Fei Wu, Shaojie Tang, Fan Wu, and Guihai Chen. 2022. Walle: An End-to-End, General- Purpose, and Large-Scale Production System for Device-Cloud Col- laborative Machine Learning. In Proceedings of USENIX Symposium on Operating Systems Design and Implementation (OSDI โ22). USENIX, Carlsbad, CA, USA, 249โ265. [29]Adyasha Maharana, Dong-Ho Lee, Sergey Tulyakov, Mohit Bansal, Francesco Barbieri, and Yuwei Fang. 2024. Evaluating Very Long- Term Conversational Memory of LLM Agents. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). Association for Computational Linguistics, Bangkok, Thailand, 13851โ13870. [30]MLC team. 2023-2025. MLC-LLM. CMU Foundation and Language Model Center. https://github.com/mlc-ai/mlc-llm [31] Chaoyue Niu, Fan Wu, Shaojie Tang, Lifeng Hua, Rongfei Jia, Chengfei Lv, Zhihua Wu, and Guihai Chen. 2020. Billion-scale federated learning on mobile clients: a submodel design with tunable privacy. In Proceed- ings of the 26th Annual International Conference on Mobile Computing and Networking (London, United Kingdom) (MobiCom โ20). Association for Computing Machinery, New York, NY, USA, Article 31, 14 pages. [32]Wei Niu, Md Musfiqur Rahman Sanim, Zhihao Shu, Jiexiong Guan, Xipeng Shen, Miao Yin, Gagan Agrawal, and Bin Ren. 2024. SmartMem: Layout Transformation Elimination and Adaptation for Efficient DNN Execution on Mobile. In Proceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 3 (ASPLOS โ24). Association for Computing Machinery, New York, NY, USA, 916โ931. [33]Taehwan Park, Geonho Lee, and Min-Soo Kim. 2025. MobileRAG: A Fast, Memory-Efficient, and Energy-Efficient Method for On-Device RAG. arXiv:2507.01079 [cs.DB] https://arxiv.org/abs/2507.01079 [34] Percena. 2025.LoCoMo-MC10ยท Long Conversation Memory Multiple-Choice 10. https://huggingface.co/datasets/Percena/locomo- mc10 [35]Jeffrey Pound, Floris Chabert, Arjun Bhushan, Ankur Goswami, Anil Pacaci, and Shihabur Rahman Chowdhury. 2025. MicroNN: An On- device Disk-resident Updatable Vector Database. In Companion of the 2025 International Conference on Management of Data (Berlin, Germany) (SIGMOD/PODS โ25). Association for Computing Machinery, New York, NY, USA, 608โ621. [36]Ruoyu Qin, Zheming Li, Weiran He, Jialei Cui, Heyi Tang, Feng Ren, Teng Ma, Shangming Cai, Yineng Zhang, Mingxing Zhang, Yongwei Wu, Weimin Zheng, and Xinran Xu. 2025. Mooncake: A KVCache- centric Disaggregated Architecture for LLM Serving. ACM Trans. Storage (Nov. 2025). [37]Llama Team. 2024.The Llama 3 Herd of Models. arXiv:2407.21783 [cs.AI] https://arxiv.org/abs/2407.21783 [38] Llama Team. 2024. Llama 3.2: Revolutionizing edge AI and vision with open, customizable models. https://ai.meta.com/blog/llama-3-2- connect-2024-vision-edge-mobile-devices/. [39]Qwen Team. 2025. Qwen3 Technical Report. arXiv:2505.09388 [cs.CL] https://arxiv.org/abs/2505.09388 [40]Jun Wang, Yunxiang Yao, Wenwei Kuang, Runze Mao, Zhenhao Sun, Zhuang Tao, Ziyang Zhang, Dengyu Li, Jiajun Chen, Zhili Wang, Kai Cui, Congzhi Cai, Longwen Lan, and Ken Zhang. 2025. OmniInfer: System-Wide Acceleration Techniques for Optimizing LLM Serving Throughput and Latency. arXiv:2511.22481 [cs.DC] https://arxiv.org/ abs/2511.22481 [41]Tuowei Wang, Ruwen Fan, Minxing Huang, Zixu Hao, Kun Li, Ting Cao, Youyou Lu, Yaoxue Zhang, and Ju Ren. 2025. Neuralink: Fast on-Device LLM Inference with Neuron Co-Activation Linking. In Pro- ceedings of the 30th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 3 (ASPLOS โ25). Association for Computing Machinery, New York, NY, USA, 147โ162. [42] Zhaode Wang, Jingbang Yang, Xinyu Qian, Shiwen Xing, Xiaotang Jiang, Chengfei Lv, and Shengyu Zhang. 2024. MNN-LLM: A Generic Inference Engine for Fast Large Language Model Deployment on Mo- bile Devices. In Proceedings of the 6th ACM International Conference on Multimedia in Asia Workshops (MMAsia โ24 Workshops). Association for Computing Machinery, New York, NY, USA, Article 11, 7 pages. [43]Jianyu Wei, Shijie Cao, Ting Cao, Lingxiao Ma, Lei Wang, Yanyong Zhang, and Mao Yang. 2025. T-MAC: CPU Renaissance via Table Lookup for Low-Bit LLM Deployment on Edge. In Proceedings of the Twentieth European Conference on Computer Systems (Rotterdam, Netherlands) (EuroSys โ25). Association for Computing Machinery, New York, NY, USA, 278โ292. [44]Jianyu Wei, Qingtao Li, Shijie Cao, Lingxiao Ma, Zixu Hao, Yanyong Zhang, Xiaoyan Hu, and Ting Cao. 2025. T-MAN: Enabling End- to-End Low-Bit LLM Inference on NPUs via Unified Table Lookup. arXiv:2511.11248 [cs.AR] https://arxiv.org/abs/2511.11248 [45]Guangxuan Xiao, Ji Lin, Mickael Seznec, Hao Wu, Julien Demouth, and Song Han. 2023. SmoothQuant: accurate and efficient post-training quantization for large language models. In Proceedings of the 40th International Conference on Machine Learning (ICML โ23). JMLR.org, Article 1585, 13 pages. [46]Zhiqiang Xie, Ziyi Xu, Mark Zhao, Yuwei An, Vikram Sharma Mailthody, Scott Mahlke, Michael Garland, and Christos Kozyrakis. 2026. Strata: Hierarchical Context Caching for Long Context Language Model Serving. In 20th USENIX Symposium on Operating Systems De- sign and Implementation (OSDIโ 26). USENIX Association, 1โ16. [47]Daliang Xu, Hao Zhang, Liming Yang, Ruiqi Liu, Gang Huang, Meng- wei Xu, and Xuanzhe Liu. 2025. Fast On-device LLM Inference with NPUs. In Proceedings of the 30th ACM International Conference on Architectural Support for Programming Languages and Operating Sys- tems, Volume 1 (Rotterdam, Netherlands) (ASPLOS โ25). Association for Computing Machinery, New York, NY, USA, 445โ462. [48]Zhenliang Xue, Yixin Song, Zeyu Mi, Xinrui Zheng, Yubin Xia, and Haibo Chen. 2024. PowerInfer-2: Fast Large Language Model Inference on a Smartphone. arXiv:2406.06282 [cs.LG] https://arxiv.org/abs/2406. 06282 [49]Zhilin Yang, Peng Qi, Saizheng Zhang, Yoshua Bengio, William Cohen, Ruslan Salakhutdinov, and Christopher D. Manning. 2018. HotpotQA: A Dataset for Diverse, Explainable Multi-hop Question Answering. In Proceedings of the 2018 Conference on Empirical Methods in Natu- ral Language Processing. Association for Computational Linguistics, Brussels, Belgium, 2369โ2380. [50] Jiayi Yao, Hanchen Li, Yuhan Liu, Siddhant Ray, Yihua Cheng, Qizheng Zhang, Kuntai Du, Shan Lu, and Junchen Jiang. 2025. CacheBlend: Fast Large Language Model Serving for RAG with Cached Knowledge Fusion. In Proceedings of the Twentieth European Conference on Com- puter Systems (Rotterdam, Netherlands) (EuroSys โ25). Association for Computing Machinery, New York, NY, USA, 94โ109. [51]Lu Ye, Ze Tao, Yong Huang, and Yang Li. 2024. ChunkAttention: Ef- ficient Self-Attention with Prefix-Aware KV Cache and Two-Phase Partition. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) (ACL โ24). Associ- ation for Computational Linguistics, Bangkok, Thailand, 11608โ11620. EuroSys โ27, April 19โ23, 2027, Rabat, MoroccoZhengxiang Huang et al. [52]Yanzhao Zhang, Mingxin Li, Dingkun Long, Xin Zhang, Huan Lin, Baosong Yang, Pengjun Xie, An Yang, Dayiheng Liu, Junyang Lin, Fei Huang, and Jingren Zhou. 2025. Qwen3 Embedding: Advanc- ing Text Embedding and Reranking Through Foundation Models. arXiv:2506.05176 [cs.CL] https://arxiv.org/abs/2506.05176 [53]Lianmin Zheng, Liangsheng Yin, Zhiqiang Xie, Chuyue Sun, Jeff Huang, Cody Hao Yu, Shiyi Cao, Christos Kozyrakis, Ion Stoica, Joseph E. Gonzalez, Clark Barrett, and Ying Sheng. 2024. SGLang: efficient execution of structured language model programs. In Pro- ceedings of the 38th International Conference on Neural Information Processing Systems (Vancouver, BC, Canada) (NIPS โ24). Curran Asso- ciates Inc., Red Hook, NY, USA, Article 2000, 27 pages. A Graph Structure and Quantization Scheme of NPU Selective Recompute Graph We follow theํ INT4 ํด UINT16 ํพํ INT8 quantization adopted in ExecuTorch [12]. Specifically, KV tensors are quantized to 8-bit using SpinQuant [27], which applies a Hadamard trans- formation to mitigate the accuracy loss caused by severe outliers in KV distributions [27,45]. On the other hand, the precision-critical KV deviation computation and Top-K se- lection are retained in FP16 precision, while KV tensors are SpinQuanted to INT8, and most intermediate activations use UINT16. The graph structure and corresponding bit-width is illustrated in Figure 18. Wq X Wk Wv FP16 INT8 INT4 conv2d UINT16 SpinQuant conv2d conv2d normnorm roperope matmulmatmul quant k cache v cache slice dequant sub pow sum where topk gather gather gather quant scatter scatter diff_k: select topk recompute index recomputed Q (Int16) k cache scatter recomputed K V to KV caches expand expand GQA matmul sub attn mask softmax matmul conv2d Wo valid mask Q @ K.T QK @ V Q K V X NPU static graph dynamic select and recompute in layer 0 Int32 index INT32 K Figure 18. Quantized NPU Selective KV Recompute Graph of Layer 0. B Chunk Merge Algorithm for Efficient Static Graph Utilization We give the complete formulation of the chunk merge dy- namic program. Setup. Let the token sequence be partitioned into ordered segments ํ ํ =(ํ ํ ,ํ ํ ,ํ ํ ), ํ= 0, . . .,ํโ 1, where[ํ ํ ,ํ ํ ]is the span of segmentํandํ ํ โ 0,1,2 indicates prefix reuse, non-prefix reuse, and new tokens, re- spectively. Letํฟ ํ andํฟ ํ be the token capacity of the selective recomputation graph and prefill graph, and letํก ํ andํก ํ be their latency. Letํ โ (0,1]be the minimum recomputation ratio. We defineํ[ํ]as the minimum latency to process tokens up to positionํ. The base case is that prefix reuse tokens require no computation, so if positionํlies entirely in the prefix- reuse region, thenํ[ํ]= 0. Transition. For a chunk ending at token positionํ, we consider two options: ํ[ํ]= min ํ[ํโํ ํ (ํ)]+ํก ํ , ํ[ํโํ ํ (ํ)]+ํก ํ .(5) Here: โข ํ ํ (ํ) is the longest valid suffix ending atํthat can be packed into one selective recomputation call. โข ํ ํ (ํ) is the longest valid suffix ending at ํ that can be packed into one prefill call. The algorithmic implementation revolves around this tran- sition function, and the pseudo code is presented in Algo- rithm 1. Computation ofํ ํ (ํ). The prefill graph simply packs as many trailing tokens as allowed by its capacity. Starting from tokenํand scanning backward over segments, we accumulate tokens until either: (1) the prefill budgetํฟ ํ is exhausted, or (2) we reach the prefix reuse region. Thus, if the accumulated packed length is โ , then ํ ํ (ํ)= โ . Computation ofํ ํ (ํ). The selective recomputation graph has capacityํฟ ํ , but new tokens may only occupy a bounded portion of that capacity. When scanning backward from token ํ: โข if the current segment is non-prefix reuse (ํ ํ =1), its tokens consume recomputation capacity directly; โขif the current segment is new (ํ ํ =2), only a bounded number of its tokens may be merged into the current recomputation call so that the recomputation ratio remains at least ํ . Equivalently, if the remaining recomputation capacity isํ, then at mostโํํโnew tokens may be absorbed from the current new-token segment. Ifฮnew tokens are absorbed, they consume โฮ/ํโ units of recomputation capacity. Scan- ning stops when the recomputation capacity is exhausted or when the prefix reuse region is reached. If the total absorbed suffix length is โ , then ํ ํ (ํ)= โ . The functions for computingํ ํ (ํ)andํ ํ (ํ)are presented in Algorithm 2 and 3 respectively. Dynamic Flow, Static Graph: KV Cache Reuse for Efficient LLM Serving on Mobile NPUsEuroSys โ27, April 19โ23, 2027, Rabat, Morocco Algorithm 1: Dynamic Programming Chunk Merge Input: Segment list ํ ํ =(ํ ํ ,ํ ํ ,ํ ํ ) for ํ= 0, . . .,ํโ 1; selective recomputation capacity ํฟ ํ and latency ํก ํ ; prefill capacity ํฟ ํ and latency ํก ํ ; minimum recomputation ratio ํ Output: Minimum latencyํ[ํฟโ 1] and chunk decisions 1 ํฟ โ ํ ํโ1 + 1; 2 Initializeํ[ํ] โ+โ and dec[ํ] โโ for all ํ= 0, . . .,ํฟโ 1; 3 for ํ โ 0 to ํฟโ 1 do 4 if ํ is in the prefix reuse region then 5ํ[ํ] โ 0; 6continue; 7 ํ ํ โ ComputeSRLength(ํ,ํ,ํฟ ํ ,ํ); 8 ํ ํ โ ComputePrefillLength(ํ,ํ,ํฟ ํ ); 9 ํฃ ํ โ ํ[ํโํ ํ ]+ํก ํ ; // use 0 if ํโํ ํ < 0 10 ํฃ ํ โ ํ[ํโํ ํ ]+ํก ํ ; // use 0 if ํโํ ํ < 0 11 if ํฃ ํ < ํฃ ํ then 12ํ[ํ] โ ํฃ ํ ; 13dec[ํ] โ (ํโํ ํ , SR); 14 else 15ํ[ํ] โ ํฃ ํ ; 16dec[ํ] โ (ํโํ ํ , P); 17 returnํ[ํฟโ 1] and dec; Algorithm 2: ComputePrefillLength(ํ,ํ,ํฟ ํ ) Input: Segment list ํ , ending position ํ, prefill budget ํฟ ํ Output: ํ ํ (ํ) 1 Locate the segment index ํ such that ํ โ [ํ ํ ,ํ ํ ]; 2 ํ โ ํฟ ํ , โ โ 0, ํฅ โ ํ; 3 while ํ> 0 and segment ํ is not prefix reuse do 4 ํ โ ํฅ โํ ํ + 1; 5ฮโ min(ํ,ํ); 6 โ โ โ+ฮ; 7 ํ โ ํโฮ; 8 ํฅ โ ํฅ โฮ; 9 if ํฅ< ํ ํ then 10ํ โ ํ โ 1; 11 return โ ; C Fast LCS for Non-prefix Matching To match the reusable substrings in candidate cached chunks, we apply a linear-time LCS (Longest Common Substring) for fast matching. To compute the longest common substring between two token sequences, we use a suffix automaton with sparse Algorithm 3: ComputeSRLength(ํ,ํ,ํฟ ํ ,ํ) Input: Segment list ํ , ending position ํ, recomputation budget ํฟ ํ , ratio ํ Output: ํ ํ (ํ) 1 Locate the segment index ํ such that ํ โ [ํ ํ ,ํ ํ ]; 2 ํ โ ํฟ ํ , โ โ 0, ํฅ โ ํ; 3 while ํ> 0 and segment ํ is not prefix reuse do 4 ํ โ ํฅ โํ ํ + 1 ; // available suffix length in current segment 5 if ํ ํ = 2 then 6ฮโ min(โํํโ,ํ); 7ifฮ= 0 then 8break; 9โ โ โ+ฮ; 10ํ โ ํโโฮ/ํโ; 11 else 12ฮโ min(ํ,ํ); 13โ โ โ+ฮ; 14ํ โ ํโฮ; 15 ํฅ โ ํฅ โฮ; 16 if ํฅ< ํ ํ then 17ํ โ ํ โ 1; 18 return โ ; transitions. Given two sequencesํandํ, where each se- quence contains at most 512 tokens (database chunk size limit) and the token vocabulary can be as large as 10 6 , we build the suffix automaton over the shorter sequenceํand then stream the longer sequenceํthrough the automaton. During the scan, we maintain the current automaton state and the length of the current match; when the next token transition is absent, we follow suffix links until a valid transi- tion is found or the root is reached. The maximum matched length observed during this scan is the longest common token substring length. The key design choice is to avoid alphabet-dense transi- tion tables. Although the global vocabulary is large, each sequence contains only a small number of tokens, and a suf- fix automaton overํcontains at most 2|ํ|โ1 states and ํ(|ํ|)transitions. Therefore, we store outgoing transitions sparsely as token-id-to-state mappings, making the memory usage independent of the global vocabulary size. With hash- table transitions, transition lookup takes expectedํ(1)time, so the algorithm runs in expectedํ(|ํ|+|ํ|)time and uses ํ(|ํ|)space. For a deterministic worst-case implementa- tion, hash tables can be replaced by sorted sparse transition arrays or balanced maps, givingํ((|ํ|+|ํ|) logํ max )time andํ(|ํ|)space, whereํ max โค |ํ|is the maximum outgo- ing degree of any automaton state. Since|ํ|,|ํ| โค512, the automaton has at most 1023 states andlogํ max โค9, so the EuroSys โ27, April 19โ23, 2027, Rabat, MoroccoZhengxiang Huang et al. deterministic implementation remains approximately linear in practice. The pseudo code is presented in Algorithm 4. Algorithm 4: Longest Common Token Substring Input: Token sequences ํด and ํต Output: Longest common token substring length 1 if |ํด|> |ํต| then 2swap ํด and ํต; 3 Build a suffix automatonS over ํด with sparse token transitions; 4 ํฃ โS.root; โ โ 0; bestโ 0; 5 foreach token ํฅ โ ํต do 6 while ํฃโ S.root and ํฅโS.next[ํฃ] do 7ํฃ โS.link[ํฃ]; 8โ โS.len[ํฃ]; 9 if ํฅ โS.next[ํฃ] then 10ํฃ โS.next[ํฃ][ํฅ]; 11โ โ โ+ 1; 12 else 13ํฃ โS.root; 14โ โ 0; 15bestโ max(best,โ); 16 return best; D Flash-Storage SQLite-Based DB Organization Directly storing large KV tensors as SQLite BLOB objects can lead to severe internal and external fragmentation, especially under frequent insertion, eviction, and update operations. Fragmentation further degrades insertion efficiency because free pages become sparsely scattered, making it difficult for SQLite to allocate sufficiently large contiguous regions for KV BLOBs. Moreover, since SQLite page management itself is already built on top of the underlying file system, using SQLite to manage large KV tensors introduces another unnec- essary storage-management layer and additional overhead. In practice, both insertion and loading latency can increase to the order of seconds if KV storage is handled entirely by SQLite. Therefore, as illustrated in Figure 19, instead of embed- ding KV tensors directly inside SQLite rows as large BLOB objects, we organize flash storage using a lightweight SQLite metadata index combined with external file-system storage. Specifically, SQLite stores only compact metadata entries, including chunk keys, prompt hashes, locality statistics, and file paths, while the actual KV tensors are serialized as sepa- rate files in the underlying file system. This design avoids repeated large-BLOB reallocations within SQLite pages, sub- stantially reducing fragmentation and write amplification. It also improves eviction and compaction efficiency, since removing a KV chunk only requires deleting its metadata KeyBlob 1 2 3 N KeyPath 1 2 3 N ร โ # # # # # # ยท File System PromptPrompt KV Tensor Fragmentation Figure 19. KV tensors blob storage design (self-managed outside SQLite). entry and corresponding file without triggering large-scale database-page reorganization. As a result, the storage system maintains stable lookup efficiency while supporting scalable GB-level KV persistence on resource-constrained mobile flash storage. E Locality Model for Prefetch and Reuse The locality model estimates the probability that a KV chunk ํ ํ will be reused in the near future. The resulting locality score is used to guide both prefetch and eviction decisions across the memory hierarchy. Conventional cache policies such as LRU and LFU only capture temporal locality, while prefix-aware methods such as PGDSF in RAGCache [21] mainly target prefix reuse and cannot effectively model non-prefix reuse behaviors and their associated recomputation costs. To address this lim- itation, we propose a lightweight locality model tailored for mobile long-context workloads, together with an online eviction-cost estimator that jointly considers both prefix and non-prefix reuse. For a cached chunkํ ํ , the overall locality score is defined as: ํ (ํ ํ )=ํค ํ ํ ํ (ํ ํ )+ํค ํก ํ ํก (ํ ํ )+ํค ํ ํ ํ (ํ ํ ),(6) whereํ ํ ,ํ ํก , andํ ํ denote spatial, temporal, and semantic locality scores, respectively, andํ ํ ,ํ ํก ,ํ ํ are normalization weights. The three locality dimensions are defined as follows: โขSpatial localityํ ํ (ํ ํ )captures whether a chunk be- longs to the same prefix/non-prefix tree or document as recently reused chunks. This is motivated by the observation that recently accessed documents and his- tories are more likely to be revisited in the near future. โขTemporal localityํ ํก (ํ ํ )models both recency and ac- cess frequency through a lightweight combination of LRU and LFU signals, allowing frequently accessed chunks to remain in higher memory levels while grad- ually evicting colder entries. โขSemantic localityํ ํ (ํ ํ )models correlations among reusable chunks using a lightweight co-access lookup table. Chunks that frequently co-occur in prompts are assigned higher semantic locality scores. For example, Dynamic Flow, Static Graph: KV Cache Reuse for Efficient LLM Serving on Mobile NPUsEuroSys โ27, April 19โ23, 2027, Rabat, Morocco SMS-related skills are often co-accessed with website- login skills for verification-code handling, and there- fore exhibit strong semantic locality. The eviction policy considers all three locality dimensions, while the prefetch policy only uses spatial and semantic locality to avoid unnecessary memory pollution. F Recomputation/Reloading Cost Model The eviction cost model estimates the future overhead in- troduced by removing a KV chunk from different storage levels. Since chunks stored in the CPU memory pool and flash storage incur fundamentally different recovery costs, we model them separately. CPU memory-pool eviction cost. For a chunkํ ํ stored in the CPU memory pool, the eviction cost mainly corresponds to the future reload latency from flash storage: ํถ cpu (ํ ํ )= ํ load (ํ ํ ), ํ ํ โ P 0,ํ ํ โN ,(7) wherePandNdenote the sets of prefix-reusable and non- prefix-reusable chunks, respectively, andํ load (ํ ํ )is the flash to memory loading latency of chunkํ ํ . For non-prefix-reusable chunks, the loading latency can largely be hidden through computeโstorage overlap, making the effective eviction cost close to zero. Flash-storage eviction cost. The eviction cost of a chunk stored in flash involves 2 terms: the first is the recompu- tation cost of the evicted chunk itself, while the second is the additional overhead derived from the cascading effect of breaking the prefix reuse chain. Specifically, the primary component is the recomputation costํฟํํกํํํํฆ ํ (|ํ ํ |), denoting the full prefill latency of the chunk estimated in Section 4.1. Shared Buffer Hierarchical KV Memory Design NPU TCM NPU KV Manager NPU Logic Memory Bus CPU KV Pool Hash Table Merger Flash KV DB Hash Table Index Map (pre)fetcher LRAE Evictor Locality & Cost Evaluator 4 567 123 ร evict ร evict 134 67 still non-prefix prefix chain non-prefix losethepotential of being part of a prefix Figure 20. Evicting a chunk on prefix chain makes subse- quent chunks lose the potential of being part of a prefix. Besides recomputation cost of the evicted chunk itself, evicting a chunk on a prefix path may cause its descendant chunks to lose prefix reusability and fall back to non-prefix reuse and bring additional cascading costํถ cascade . As illus- trated in Figure 20, chunks 6 and 7 can originally be reused as part of the prefix chain 4567. However, evicting chunk 5 breaks the prefix chain and turns chunks 6 and 7 into pure non-prefix chunks, thereby increasing future recompu- tation overhead. In contrast, evicting chunk 2 introduces no additional cost to chunk 3 because it is already non-prefix- reusable. The cascading cost is formulated as: ํถ cascade = โ๏ธ ํ ํ โDes(ํ ํ ) ํ(ํ ํ )ยท ํฟํํกํํํํฆ ํ (|ํ ํ |),(8) whereDes(ํ ํ )denotes the descendant chunks ofํ ํ on the prefix tree,ํ(ํ ํ )is the prefix-hit frequency factor estimating the likelihood of future prefix reuse,ํฟํํกํํํํฆ ํ (|ํ ํ |)is the additional selective recomputation graph execution overhead caused by turning from prefix to non-prefix. Combining the 2 terms, the full eviction cost formulate as: ํถ flash (ํ ํ )= ํฟํํกํํํํฆ ํ (|ํ ํ |)+ํถ cascade (ํ ํ ).(9) G Cost-Aware Prefetch and Eviction G.1 Prefetch The prefetch policy proactively loads reusable chunks whose locality scoresํ (ํ)greater or equal to a threshold from flash storage into memory to reduce future loading latency. Prefetching is performed asynchronously during idle I/O periods and primarily targets prefix-reusable chunks with high predicted reuse probability. G.2 Eviction The eviction policy ranks chunks according to the locality- cost product:ํ (ํ)ยทํถ(ํ). Chunks with high locality and high recovery cost are preferentially retained in higher memory levels, while less useful chunks are demoted or removed. This policy jointly optimizes cache hit rate and recovery overhead under constrained on-device memory and storage capacity.