DualMap: Enabling Both Cache Affinity and Load Balancing for Distributed LLM Serving
Authors: Ying Yuan
Pengfei Zuo
Bo Wang
Zhangyu Chen
Zhipeng Tan
Zhou Yu
Venue: ICLR 2026 Poster (2026)
Keywords: Distributed LLM Serving
LLM Context Caching
Request Scheduling
Cache Affinity
Load Balancing
Primary area: infrastructure, software libraries, hardware, systems, etc.
TL;DR: This paper proposes DualMap, a dual-mapping inference scheduler that enables KV cache reuse and balanced workload distribution, boosting effective request capacity by up to 2.25× under the same TTFT SLO compared to SOTA.

Abstract: In large language model (LLM) serving, reusing the key-value (KV) cache of prompts across requests is a key technique for reducing time-to-first-token (TTFT) and lowering serving costs. Cache-affinity scheduling, which co-locates requests with the same prompt prefix to maximize KV cache reuse, often conflicts with load-balancing scheduling, which aims to distribute requests evenly across compute instances. Existing schedulers struggle to reconcile this trade-off, as they operate within a single mapping space, typically applying cache-affinity routing to a subset of requests and load-balanced routing to the rest, without a unified solution to achieve both goals. To overcome this limitation, we propose DualMap, a dual-mapping scheduling strategy for distributed LLM serving that simultaneously enables cache affinity and load balancing. The key idea of DualMap is to map each request to two candidate instances using two independent hash functions based on the request prompt, and then intelligently select the better candidate based on current system states. This design increases the likelihood that requests with shared prefixes are co-located, while evenly dispersing distinct prefixes across the cluster via ``the power of two choices''. To make DualMap robust under dynamic and skewed real-world workloads, we incorporate three techniques: 1) SLO-aware request routing,  which prioritizes cache affinity but switches to load-aware scheduling when TTFT exceeds the SLO, enhancing load balance without sacrificing cache reuse; 2) hotspot-aware rebalancing, which dynamically migrates requests from overloaded to underloaded instances, mitigating hotspots and rebalancing the system; 3) lightweight dual-hash-ring scaling, which leverages a dual-hash-ring mapping to support fast and low-overhead instance scaling without costly global remapping. Experiments on real-world workloads show that DualMap improves effective request capacity by up to 2.25$\times$ under the same TTFT SLO constraints, compared with the state-of-the-art work.

Published as a conference paper at ICLR 2026
DUALMAP: ENABLING BOTH CACHE AFFINITY AND LOAD BALANCING FOR DISTRIBUTED LLM SERVING
Ying Yuan" Huazhong University of Science and Technology
Pengfei Zuo Huawei
Bo Wang
Huawei
Zhangyu Chen Huawei
Zhipeng Tan
Zhou Yu Huawei
Huazhong University of Science and Technology
ABSTRACT
In large language model (LLM) serving, reusing the key-value (KV) cache prompts across requests is key technique for reducing time-to-first-oken (TTFT) and lowering serving costs. Cache-affinity scheduling, which co-locates requests with the same prompt prefix to maximize KV cache reuse, often conflicts with load-balancing scheduling, which aims to distribute requests evenly across com- pute instances. Existing schedulers struggle to reconcile this trade-off, as they operate within single mapping space, typically applying cache-affinity routing a subset of requests and load-balanced routing to the rest, without unified so- lution to achieve both goals. To overcome this limitation, a dual-mapping scheduling strategy for distributed LLM serving that simulta- neously enables cache affinity and load balancing. The key idea of DualMap is to map each request to two candidate instances using two independent hash functions based the request prompt, and then intelligently select the better candidate based on current system states. This design increases the likelihood that requests with shared prefixes are co-located, while evenly dispersing distinct prefixes across the cluster via "the power of two choices". To make DualMap robust under dynamic and skewed real-world workloads, we incorporate three techniques: 1) SLO-aware request routing. which prioritizes cache affinity but switches load-aware scheduling when TTFT exceeds the SLO, enhancing load balance without sacrificing cache reuse; 2) hotspot-aware rebalancing, which dy- namically migrates requests from overloaded to underloaded instances, mitigating hotspots and rebalancing the system; 3) lightweight dual-hash-ring scaling, which leverages a houl-hhsh--ing mapping to support fast and low-overhead instance scaling without costly global remapping. Experiments show that DualMap improves effective request capacity by up to 2.25x under the same TTFT SLO constraints, compared with the state-of-the-art work. Code be found at: https: / /ighhb....... com ASssay/SSsss//.a... DMaMMap
propose DualMap,
real-worke workloads
INTRODUCTION
Recently, large language models (LLMs) have exhibited strong performance in scenarios such as multi-turn conversations and agent-based applications (Sha, 2025; Gao et al., 2024; Hao et al., 2023). A common characteristic of these scenarios the repeated use of prompt prefixes. For example, in conversational sessions, requests share the dialogue history, while agent tool usage typically includes repeated instruction prompts.
To reduce redundant prompt computation, modern LLM serving systems widely adopt context caching- also referred to as prompt caching or prefix caching which stores the historical key- value (KV) cache of prompts (Gao et al., 2024; Qin et al., 2025; Dyn, 2025; 202, 2025; Zheng
Work done during her internship at Huawei. 1 'Corresponding authors are Pengfei (tanzhipeng hust.cdu.cn).
7no (pfzuo.cs@gmail.com and Zhipeng
Tan

---

Published as a conference paper at ICLR 2026
et al., 2024a). This allows subsequent requests to directly reuse the stored KV cache, eliminating the need for repeated prefill computation. This technique significamtly improves GPU utilization and reduces inference latency, especially the mame-to-fissttokee arrival to the first token which is critical to user experience. Ensuring TTFT stays within a service level objective (SLO), is essential in practice. Under such constraints, system efficiency is com- monly measured by effective request capacity, defined as the proportion of served requests that meet the target SLO (Qin et al., 2025).
(TTFT) latency from request
In production environments, LLMs are deployed in distributed serving clusters, where request scheduling plays a crucial role in reducing inference latency and cost (Qin et al.. 2025; Dyn, 2025; Srivatsa et al., 2024; Cao et al., 2025). Effective scheduling must ensure both cache affinity, which routes requests to compute nodes that store the KV cache of their prompt prefixes to maximize cache reuse and minimize TTFT, and load balancing, which distributes requests evenly across nodes to avoid hotspots and improve resource utilization.
However, achieving cache affinity and load balancing often conffict with each other. Specifically, a cache-affinity strategy maps requests with identical prompt prefixes to the same instance using a prompt-aware function. While this approach maximizes KV cache reuse, it does not guarantee load balancing. This is because prompt popularity in real-world workloads is typically skewed (Wang et al., 2025b), causing nodes responsible for hot prefixes to become overloaded, while those handling cold prefixes remain underutilized. In contrast, load-balancing strategies such as the Least Loaded strategy map requests to the instance with the lowest load, without considering KV cache hits. While this approach achieves even load distribution, it scatters requests with shared prefixes across different instances. This reduces the KV cache hit rate and increases recomputation overhead.
The fundamental trade-off between cache affinity and load balancing arises because both cache- affinity and load bal-balanning strategies are implemented within a single mapping space. Cache- affinity strategies rely on prompt-aware mapping function that prioritizes routing requests to nodes with relevant KV caches, while load-balaneing strategies use a load-aware mapping function to evenly distribute requests across nodes. Prior work, such as Mooncake (Qin et al., 2025), Pre- ble (Srivatsa et al., 2024), and Dynamo (Dyn, 2025), attempts to balance cache affinity and load balancing, but fails to achieve both simultaneously. This is because they remain constrained by single mapping space, typically applying prompt-aware routing to a subset of requests and load- aware routing to the rest.
To break the trade-off between cache affinity and load balancing, we propose DualMap, a dual- mapping scheduling strategy for distributed LLM serving that enables both objectives simultane- ously. DualMap draws inspiration from the power of two choices (PoTC) principle (Mitzenmacher, 2002), which demonstrates that selecting the less loaded option among two randomly chosen can- didates can significantly improve the system load balancing. Specifically, DualMap employs two independent hash functions, fi and f2, to map each request to two candidate compute nodes, and dispatches the request to the more suitable node based on the current system state. The random- ness of the two hash functions ensures requests are distributed evenly across the cluster. To enable cache affinity, DualMap uses request's 's partial prefix as the input key to the two hash functions. This increases the likelihood that requests with shared prefixes are consistently mapped to the same node where their KV caches can be stored and reused locally. In this way, DualMap simultaneously promotes cache affinity and load balancing.
However, implementing this design in real-world serving systems introduces three challenges:
1) How to select the optimal one from two candidate instances to maximize system effective re- quest capacity? Selecting between two candidate instances also involves a trade-off between cache affinity and load balancing. 2) Skewed prefix popularity leads to hotspot instances. The PoTC prin- ciple achieves load balancing under the assumption that requests are randomly distributed across all instances. In practice, this assumption is often violated due to skewed prompt popularity. For example, frequently invoked tools can cause large number of requests with identical prefixes to concentrate on a small subset of instances (Wang et al., 2025b) in $A.2.2). This leads to load imbalance and high TTFT tail latency. 3) Static hash mappings limit system elasticity. Static hash mappings tightly bind request prefixes to specific instances. Scaling operations (e.g., adding or removing instances) disrupt these mappings, degrade cache hit rates, increase recomputation, and introduce service jitter, ultimately compromising elasticity.
2

---

Published as a conference paper at ICLR 2026
Cache Hit Rate (%)
DualMap
Cache Affinity
Cache Hit Rate (%)
65
DualMap
Cache Affinity
25
Min TTFT
Min TTFT
20
60
15
Preble
Least Loaded
Least Loaded
Preble
55
0.5
1.0
1.5
2.0
0.0
0.5
1.5
2.0
Load balance ratio (CV)
Load balance ratio (CV)
(a) Conversation
(b) Tool&Agent
Figure 1: Pareto trade-off' between cache hit rate and load balance ratio (coefficient of variation, CV) across different scheduling strategies the Conversation and Tool&Agent datasets. A lower CV indicates more even load distribution across instances.
To tackle these challenges, DualMap incorporates three key techniques. First, to select the optimal instance from two candidates for maximizing system effective request capacity, DualMap introduces an SLO--waare routing strategy, which prioritizes prompt-aware scheduling achieve cache affinity and minimize recomputation overhead, but dynamically shifts to load-aware scheduling only when expected TTFT exceeds the predefined SLO, ensuring stable performance under fluctuating load.
Second, to resolve hotspots caused by skewed prefix popularity, DualMap introduces a hotspol- aware rebalancing strulegy. It selectively migrates requests from overloaded instances to their backup instances, i.e., the alternative instance from the initial dual mapping. DualMap prioritizes migrating the requests whose backup instance is underutilized and exhibits high cache reuse, en- abling effective load redistribution without significantly compromising cache affinity.
Third, support efficient elasticity, DualMap adopts a dual-hash- haahhlhhh--nng -iisg scaling strategy. Request-to- instance assignments depend solely on the relative positions in the hash rings, ensuring that scaling operations (e.g., instance addition or removal) affect only a small portion of the mappings. This design avoids expensive global remapping and enables fast adaptation to dynamic workloads.
We implement DualMap distributed LLM serving system with the vLLMM engine (Kwon al., 2023). Experimental results real-world workloads demonstrate that DualMap improves effective request capacity by 2.25 compared to state-of-the-art scheduling approaches.
BACKGROUND AND MOTIVATION
2.1 LLM INFERENCE AND CONTEXT CACHING
Transformer- based LLM inference first processes the input prompt in parallel to produce the initial output and KV caches, which are then used for autoregressive decoding (Pope et al., 2023; Kwon et al., 2023; Zheng et al., 2024a). The KV caches are often stored and reused across requests, a technique known context caching, prompt caching,
prefix caching (Gao et al., 2024; Srivatsa et al., 2024: Qin et al., 2025; Dyn, 2025). KV caches for a shared prefix (I1..... IR) are identical and can be reused across requests, avoiding redundant prefill computation. Prefix sharing, where multiple requests share a common prefix, frequently arises in practical scenarios such as multi- turn conversations and tool-agent interactions (Sha, 2025; Qin et al., 2025). Reusing KV caches for these shared prefixes instead of recomputing them can significantly reduce prefill latency and improve inference efficiency (Gao al., 2024; Srivatsa al., 2024; Qin et al., 2025; Dyn, 2025).
2.2 SCHEDULING IN DISTRIBUTED LLM SERVING
Ideally, an efficient scheduler should achieve both high cache efficiency and balanced load. How- ever, these goals are inherently conflicting.
3

---

Published as a conference paper at ICLR 2026
Conflicts between Cache Affinity and Load Balancing. To systematically examine the impact of cache affinity and load balancing on system, we evaluate Cache Affinity and Least Loaded strategies on the Conversation (Qin et al., 2025) and Tool&Agent (Qin et al., 2025) datasets using an 8-instance cluster serving the Qwen2.5-7B model (Team, 2024). Detailed experimental settings are provided in $4. As shown in Figures la and Ib, the Cache Affinity strategy achieves cache hit rate 1.21 x higher than that of Least Loaded on the Conversation dataset. On the Tool&Agent dataset, Cache Affinity approaches the thcoretical upper bound, while Least Loaded falls close the lower bound. This is because Cache Affinity dispatches requests with shared prefixes to the same instance, preserving cache locality and maximizing KV cache reuse. contrast, Least Loaded considers only the current load of each instance (e.g., pending tokens for prefill), ignoring whether the required KV cache is already present. As a result, it scatters requests and significantly reduces cache hit rates.
To evaluate how well each strategy balances load, we measure the coefficient of variation (CV), standard metric that quantifies the degree of load imbalance across instances:
CV V Eh=iia (I; 12)2
Here, 2; denotes the number of pending prefill tokens on instance i, μ A E I, represents the average number of pending prefill tokens across n instances the cluster. lower CV indicates better balance, with CV of zero meaning perfectly even load. As shown in Figures 1a and 1b, Least Louded achieves near-zero CV, indicating highly uniform load distribution. contrast, Cache Affinity results in significant load imbalance. This is because when particular prefix becomes highly popular, all associated requests are directed to a single instance, causing queue buildup, elevated tail TTFT, and underutilization of the remaining instances.
Co-locating requests improves cache reuse, while spreading them evenly improves load balance and resource utilization. Within unified scheduling space, optimizing for one typically comes the cost of the other.
Existing Trade-off Approaches. Recent approaches (Srivatsa et al., 2024; Dyn, 2025; Qin al., 2025) strive to balance cache affinity and load balancing through unified scheduling mechanisms. However, they fundamentally fall short of achieving both objectives simultaneously, as improve- ments one often come at the expense of the other. Specifically, Preble enables prompt-aware scheduling when request's prefix hit rate exceeds 50%, but switches load-aware scheduling otherwise. Similarly, Dynamo and Mooncake adopt prompt-aware scheduling under cluster load imbalance, and switch to load-aware scheduling when the load is balanced, detailed in $B
In the evaluation, we compare only with Mooncake's 's request scheduling strategy, simplify Moon- cake Min TTFT. and exclude Dynamo since its cost-based design is similar to that of Mooncake. As shown in Figures la and 1b, the Min TTFT and Preble achieve cache hit rates and load balancing ratios between those of Cache Affinity and Least Loaded, indicating that they cannot simultaneously achieve both cache affinity and load balancing, because they apply prompt-aware mapping to subset of requests and a load-aware mapping to the rest.
2.3 MOTIVATION
As stated in $1, to overcome the limitation that a single mapping space cannot simultaneously guar- antee both cache affinity and load balancing, we propose dual-mapping scheduling approach for distributed LLM serving, inspired by the PoTC principle.
Cache Affinity Guarantee. For m requests with the same prompt prefix p. DualMap consistently maps them to the same candidate instance set {41 12). guarantecing a cache hit rate of max(0, 2/m). In contrast, the Cache Affinity strategy achieves a cache hit rate of max 1/m). When m is large, DualMap approaches the cache hit rate of Cache Affinity.
Load Balancing Guarantee. DualMap adopts the PoTC strategy (Mitzenmacher, 2002), clas- sic scheduling paradigm widely used for its strong theoretical guarantees load balancing in large-scale systems. For m incoming requests distributed across n instances, PoTC ensures that the maximum load remains tightly concentrated around the mean. When each request is mapped
4

---

Published as a conference paper at ICLR 2026
to d candidate instances chosen uniformly at random, the maximum load satisfies the following bound (Mitzenmacher, 2002):
max ((4) < m +
log logn + ((),
logd
where L(1,) denotes the number of requests assigned to instance I,, and m is the ideal average load per instance. The second term, randomness.
log log n captures the deviation from the average load caused by log d
Single-choice (d 1). The above bound degenerates to a much weaker guarantee:
m7 +
m mlog
max L(4)
(3)
indicating significantly larger deviation from the mean, which grows with both m and n.
Two-choices (d = 2). The deviation term becomes log log n, which is exponentially smaller than that under d In particular, for PoTC yields:
m
max ((4)
E + log logn O(1),
71
leading to exponentially better load balancing than single-choice. Consequently, DualMap deliber- ately chooses = 2, providing significantly tighter bounds on load imbalance, especially in large- scale deployments.
Why Two Choices Instead of More. Intuitively, using more choices should lead to better load balancing. However, according Eq. 2, although increasing the number of choices d reduces the deviation term loglog the improvement quickly exhibits diminishing returns. For instance, the logd reduction from d = 2 to 3 d
marginal (detailed in $A.9). contrast, increasing d expands the candidate instance set for each request, dispersing requests with the same prefix across more instances and thereby weakening KV cache locality. A global strategy that "collects information from all instances and selects the best one" is effectively equivalent to using d choices. Yet Eq. shows that this yields negligible improvement over load, while severely degrading KV cache reuse: prefix-sharing requests may be scattered across the entire cluster, increasing prefill computation and ultimately worsening TTFT. Therefore, DualMap deliberately adopts 2, achieving strong load balancing while preserving KV cache locality.
terms of maximum
3
THE DUALMAP DESIGN
3.1 OVERVIEW
To break the trade-off between cache affinity and load balancing, propose DualMap, dual- mapping scheduling strategy for distributed LLM serving that enables both objectives simulta- neously. Figure? illustrates the system architecture of DualMap, comprising two main compo- nents: the global scheduler and the inference cluster. Each inference instance hosts an LLM and is equipped with given-size host DRAM used for context caching, enabling KV cache reuse across requests to reduce redundant computation and improve serving efficiency. The global scheduler han- dles incoming requests from external users or client applications and dispatches each request to an appropriate inference instance based DualMap. Upon receiving request, DualMap employs the following three techniques to achieve both cache affinity and load balancing: 1) SLO-aware Request Routing($$. $3.2) selects the most suitable instance among two candidates to maximize system SLO compliance; 2) Hotspot-Aware Rebalancing $3.3) rebalances hotspot instances to achieve load bal- ance under skewed workloads; 3) Lightweight Dual-hashe Scaling( $3.4) enables rapid scaling and resizing of the cluster.
3.2 SLO-AWARE REQUEST ROUTING
To balance cache reuse and load distribution, the DualMap global scheduler maps each request to two candidate instances using two independent hash functions over the request's prompt prefix. This process must answer two key questions:
5

---

Published as a conference paper at ICLR 2026
Global Scheduler
Request Queue
Load Metadata
Caching Metadata
Instance:
Instanced
Map
Map
Dual-Mapping Routing (3
Inference Cluster
Instance 0
Instance 1
Instance N-1
Scaled Instance
Request Queue
Request Queue
Request Queue
Request Queue
C Context Caching
Context Caching
Contentt Coching
Context Caching
(Hot)
(Cold)
Lightweight Scaling
Hotspot-awvar Migration ($3.3)
(53.4)
Figure 2: The system overview of DualMap.
1) How long prefix is appropriate for the hash key? Ideally, the hash key should consist of the shared prefix so that requests with shared context are mapped to the same instance, enabling KV cache reuse. In practice, however, the global scheduler does not know the shared prefix length beforehand, and different requests may have varying shared prefix lengths.
Two issues arise: (1) if the hash key is too long, it may exceed the actual shared prefix, causing requests to be mapped to different instances and reducing cache reuse; (2) if the hash key is too short, different request sets may collide, concentrating load few instances and causing severe imbalance. Rorldworld request patterns are also highly skewed, with some prefixes appearing dis- proportionately and forming hotspot instances.
To address this, we propose an adaptive hash prefix length mechanism that dynamically determines the prefix length for each request. The global scheduler maintains request prefix hotness tree, where each node records prefix information. The hash prefix corresponds to the full path from root leaf. When leaf prefix becomes hot, child nodes are added to extend the hash prefix, distributing hot requests across more instances; when a parent prefix becomes cold, its child nodes are removed shorten the prefix, aggregating normal requests to the same instance and improving cache reuse. Prefix hotness is tracked via the traffic ratio p of each prefix in real time using a sliding window. Here, P is defined as the fraction of total requests within the window that share the same prefix. A prefix is hot if p > 2. where n is the number of inference instances, reflecting the dual-mapping strategy's upper bound. If hot prefix's traffic drops significantly between windows (e.g., to 4), its hotness is updated and child nodes removed to shorten the prefix.
In experiments, the distribution of hash key prefix lengths for the Conversation and Tool&Agent datasets detailed in 1.
2) Select which intance between the two candidates? Selecting between the two candidates in- volves critical trade-off between cache affinity and load balancing, which directly impacts the request's TTFT. A more detailed analysis is provided in the $A.2.1
Baseline Strategies. A naive least-loaded strategy selects the instance with the lower load, disre- garding cache availability. In contrast, a pure cache-affinity strategy always routes a request to the instance with the highest expected cache reuse. While this minimizes recomputation, can lead to severe load imbalance. To minimize the risk of TTFT SLO violations, the Min 77FT policy esti- mates TTFT for each candidate instance and selects the one with the lower value. For a request r and candidate instance we define: (r, i) estimated queuing delay of Request capturing system load, Tr(r, i) as expected computation time for Request on Instance i, depending on whether cache reuse occurs. Thus, the estimated total TTFT is TT FT. i) (r i) +T.(r. i). However, as new requests arrive, this strategy may oscillate between cache-aware and load-aware de- cisions, leading frequent cache misses under load fluctuation, increasing recomputation overhead
Instance i,

---

Published as a conference paper at ICLR 2026
and worsening overall TTFT. Fundamentally, Min TTFT's pursuit of optimal latency per request inadvertently degrades cache reuse and destabilizes load balance over time.
SLO-Aware Strategy. To address these issues, DualMap adopts SLO-aware routing strategy that explicitly incorporates TTFT constraints. The key idea is to maintain cache affinity whenever possible, and only trade it off when load imbalance threatens breach SLO constraints. DualMap prioritizes cache affinity and initially selects the instance with the highest cache reuse. Requests are routed to this instance until its load causes the expected TTFT exceed the SLO. At that point, DualMap switches to a load-aware strategy and selects the less loaded instance to avoid long queues and reduce TTFT tail latency. Furthermore, if both instances have equal prefix hit rates, DualMap always chooses the less-loaded one, further enhancing load balance without sacrificing reuse. Unlike Min TTFT, DualMap does not seek per-request optimal TTFT. Instead, it preserves cache reuse whenever load conditions permit, switching to load balancing only when necessary. This reduces the frequency of recomputation and stabilizes cache hit rates.
To quantify system load, DualMap uses the number of pending prefill tokens on each instance, as prefill computation latency scales with token count. Given predefined TTFT SLO, we compute the maximum number of pending prefill tokens that GPU can process within the SLO, referred to as the wtwrssho..reeold.. This threshold used as the switching criterion to a load-aware strategy in implementation, ensuring that routing decisions remain aligned with service-level constraints.
DualMap is designed so that every request has two distinct candidate instances. If the two hash functions fi and f2 initially map request to the same instance, we deterministically adjust the second candidate as
instance_id, (instance_id, + 1) mod num _um_instances. This ensures that each request always has two distinct candidate instances.
3.3 TITSPOT-AWART REQUEST REBALANCING
As discussed in Challenge 2 ($1), for the skewed nature of real-world request patterns, some in- stances may become overloaded over time resulting long queues and elevated tail TTFT, while others remain underutilized.
To solve this problem, we introduce hotspot-aware request rebalancing, selectively migrating pend- ing requests from overloaded instances to less-loaded ones. This rebalancing strategy is inspired by Cuckoo hashing (Pagh & Rodler, 2001), where each key has two possible slots and can be relocated if its primary slot is full. In this setting, a DualMap instances play the role of slots, and requests act as keys. When an instance becomes overloaded (i.e., has a long queue of pending requests), some requests redirected their alternative candidate instance, preserving the mapping consis- tency of DualMap. Unlike traditional Cuckoo hashing, which may involve recursive evictions, we adopt a non-recursive, single-round batch migration minimize overhead. Specifically, we evaluate multiple queued requests on overloaded instances and migrate those whose alternative instance is underloaded and yields a net TTFT benefit.
Request migration directly impacts TTFT. A straightforward approach is to migrate requests near the tail of the queue, as they experience long queuing delays. However, if their alternative instance is also congested, such migration may worsen overall latency. Another heuristic is to migrate requests with low cache affinity to reduce potential cache hit loss, but this too can backfire if the target instance has even less relevant cached data. Too balance these trade-offs, we estimate the potential TIFT gain for each request by jointly considering queuing delays and computation costs on both the source and target instances. We define the migration benefit for Request currently queued at the overloaded Instance with the alternative Instance j as:
((++)) TTFT, TTFT,, = (T, T.(r. i)) (T,( + ())
(6)
Only requests with a sufficiently positive B(C are considered for migration. Requests are pri- oritized by descending benefit and migrated until all requests in the overloaded instance's 's queue are expected to meet the TTFT SLO. The alternative instance j is precisely the second candidate from the dual mapping. We do not search over all instances; instead, candidate pair {T, and migrate requests only within this pair. This approach maintains cache affinity while keeping scheduling complexity under control. Overall, this hotspot-aware migration
preserve the bound
7

---

Published as a conference paper at ICLR 2026
mechanism effectively alleviates overloaded instances while preserving cache affinity. Details are in $A.2.2.
3.4 LIGHTWEIGHT HHAL-HASH-RING SCALING
LLM inference workloads often experience pronounced temporal variation in request volume. To achieve low queuing lateney and high resource utilization, the system must support dynamic and responsive elastic scaling. However, static bash-based mapping poses significant challenges: scaling operations such as adding or removing instances trigger global remapping, which severely disrupts cache affinity.
To enable elastic scaling with minimal disruption, we adopt a dlullmapping hash ring that combines dual mapping with consistent hashing (Karger et al., 1997) to achieve lightweight elasticity. The hash ring spans a logical space [0, M), with each instance assigned an anchor point based on a unique identifier (e.g.. IP and port). Each request hashes its prefix using two independent hash functions to generate two anchor points and selects the nearest clockwise instance as a candidate. The scheduler chooses between these two candidates based on the SLO- request routing ($3.2). Because request-to-instance mappings are determined by relative positions on the ring, changes to cluster membership affect only localized regions. This design ensures that most requests retain their original mapping paths during scaling operations. As a result, cache loss is significantly reduced and elastic scaling is achieved with minimal disruption.
4 PERFORMANCE EVALUATION
4.1 EXPERIMENTAL. SETUP
Testbed. We implement DualMap as an independent global scheduling layer for distributed LLM serving systems. In our experiments, we deploy DualMap on top of vLLM (Kwon et al., 2023). All experiments are conducted on a distributed LLM serving cluster. Each node in the cluster is equipped with Ascend NPUs (910B4: 32 GB HBM or 910B3: 64 GB HBM), and 1.5 DRAM.
Metrics. We evaluate the following: Effective Request Capacity (Qin et al., 2025), the percentage of requests with TTFT below a 5s SLO, reflecting system ability handle latency-sensitee requests (Table 1); Goodput, the peak request rate sustained under required SLO (e.g., 90%), correlating with lower per-request cost (Zhong et al., 2024); P50 and P90 TTFT, measuring overall schedul- ing/inference efficiency and tail latency in the prefill stage; End-to-End Latency (E2E), total time from request arrival to final token generation, reported as P50 and P90; and Cache Hit Rate and Load Balance Ratio, assessing scheduling efficiency ($A.3.2). Elasticity evaluation is in $A...3.
Baselines and Workloads. We compare DualMap with four scheduling strategies: Cache Affinity, Least Loaded, Min TIFT (Qin et al., 2025), and Preble (Srivatsa et al., 2024). We use two real- real-world trace datasets from Mooncake (Qin et al., 2025): Conversation and & detailed in $A.3.I.
Model Deployment. We evaluate Qwen2.5 7B and 14B models (Team, 2024) using default float precision. Each instance is assigned a dedicated NPU (910B4 for 7B, 910B3 for 14B). Context caching is configured store up million tokens for the 7B model and 0.5 million tokens for the 14B model, covering 30% and 15% of total request tokens, respectively.
4.2 END-TO-END PERFORMANCE
We evaluate the end-to-end performance of various scheduling strategies under two real-world work- loads, using the Qwen2.5 7B and 14B models with instances on different request rates (QPS).
Effective Request Capacity and Goodput. As shown in Figures 3b and 3d, on the Tool&Agent dataset, the presence of a large number of skewed prefixes makes the Cache Affinity strategy per- form poorly. Even under low QPS, its SLO attainment rate is significantly lower than that of other strategies due to severe load imbalance, which leads to excessive queuing delays and frequent viola- tions of the TTFT SLO. Preble and Min TTFT achieve suboptimal performance: their load-balle boad-balancing capabilities mitigate the cluster imbalance caused by skewed loads, but at the cost of reduced cache hit rates. In contrast, DualMap, which simultaneously achieves cache affinity and load balancing.
8

---

Published as a conference paper at ICLR 2026
Cache Affinity
Least Loaded
+ Min TTFT
Preble
DualMap
SLO attalnment (%)
SLO attainment (%)
100
100
%608
1229
50
+40%
+48%
0
0
2
3
4
5
1
3
4
Req rate (req/s)
Req rate (req/s)
(a) Conversation with Qwen2.5-7B
(b) Tool& Agent with Qwen2.5-7B
SLO attalnment (%)
100
SLO attainment (%)
100
440.8% 6%.6%
50
14.3%
16.7%
0
2
Req rate (req/s)
Req rate (req/s)
(c) Conversation with Qwen2.5-14B
(d) Tool&Agent with Qwen2.5-14B
Figure 3: Effective request capacity and goodput of different scheduling strategies.
consistently outperforms other approaches. Its Effective Request Capacity increases by up to 125% (Figure 3b), while goodput improves by 16.7% compared the best baseline.
As shown in Figures 3a and 3c, on the conversation dataset, without skewed prefixes, DualMap still demonstrates significant advantages by 40.6%%80%5 80%, and its goodput improves by 44.3%-40% compared to the best baseline.
other strategies. Its Effective Request Capacity increases
TTFT and E2E Latency. As shown in Figure 4, across all experimental settings, DualMap sig- nificantly outperforms all baselines in both TTFT and E2E latency. Under high QPS scenarios, compared the best baseline, DualMap reduces P50 TTFT by 55.4%-97.4% by achieving cache affinity, which yields high cache hit rates, effectively reduces redundant computation, and lowers TTFT: and reduces P90 TTFT by 82.3%-97% by achieving load balaneing. which avoids request accumulation individual instances and effectively reduces tail queuing time. The E2E latency closely follows the TTFT trends at both P50 and P90, optimizations in the prefill stage indi- rectly impact the overall E2E latency. Comparing different models, DualMap consistently achieves lower TTFT and E2E latency than baselines on both the 7B and 14B models. Across varying QPS, DualMap maintains latency close to low-QPS levels even when QPS doubles, demonstrating strong stability, whereas baseline latencies increase rapidly with higher QPS.
4.3 ABLATION STUDY
To understand the source of DualMap's performance gains, we conduct an ablation study by in- crementally enabling the techniques described in $3 under the Conversation workload using the Qwen2.5-14B model. We compare five configurations: 1) DualMap-catee wwc---aacccaiiiteeeeee uses cache- affinity between two candidates during DualMap initial routing ($3.2). 2) Maailaap-least-oaaaeee uses least-loaded selection; 3) DuaiMMa--in-itff uses min-TTFT selection. 4) DualMap-no- rebalance, includes SI.O-aware request routing but disables the hotspot-aware rebalancing; 5) DualMap, includes both techniques introduced in $3.2 and $3.3.
shows the highest P50 (Figure 5a) and P90 (Fig- As shown in Figure 5, DualMap-cuche-afiie
ure 5b) TTFT, as maximizing cache reuse (Figure 5c) causes severe load imbalance (Figure 5d) and long queuing delays. DualMap-leas leas-pppleaa--loadedd loaded alleviates imbalance but suffers from low cache reuse, while DualMap-mine between cache- and load-aware scheduling. Compared with DualMap-min caMMaaa--i--ttiee -ift, DualMap-no- rebalance performs better, reducing P50 and P90 TTFT by 23.5% and 18.5 % through SL. SLO-awwre
slightly improves yet still has low cache hit rate due to frequent switching

---

Published as a conference paper at ICLR 2026
Cache Affinity
- Least Loaded
- Min TTFT + Preble +
DualMap
Convvesation with 7B
Conversation with 7B
Conversation with 7B
Conversation with 7B
100
P50 Latency (s)
20
P90 Latency (6)
2100
PS0 TTFT (8)
(s)
15
10
5
P90
0
0
0
2
2
Tool&Agent with 7B
Tool&Agent with 7B
Tool&Agent with 7B
Tool&Agent with 7B
100
20
100
P50 TTFT (8)
P90 TTFT
P50 Latency
15
P90 Latency
2-
0
Conversation with 148
Conversation with 148
Conversation with 148
Conversation with 148
P50 TTFT
P90 (TFT
100
P50 Latency (8)
20
P90 Latency (9)
100
15
50
10
60
2
3
2
3
Tool& with 14B
Toal&Agent with 14B
Tool&Agent with 14B
Tool&Agent with 14B
P50 TTFT (8)
P80 TTFT((s) (s)
100
P50 Latency (8)
20
P90 Latency (8)
100
2-
5
0
Req (req's)
2
Req rate (req's)
Req rate
3
Req rate (reg's)
2
(a) P50 TTFT
(b) P90 TTFT
(c) P50 E2E Latency
(d) P90 E2E Latency
Figure 4: TTFT and E2E Latency of different scheduling strategies.
DusiMap-esss--odee
DuslMasp-min-ut
DualMeg-no--rbballnne
DualMap
Cache Hit Rate (%)
2.
20
2-
1
17
12
10
15
20
22.2 25.7
0.5
1.0
0.05
(a) P50 TTFT
(b) P90 TTFT
(c) Cache hit rate
(d) Load balance ratio
Figure 5: Ablation Results under the Conversation workload using the Qwen2.5-14B model.
scheduling. Finally, DualMap achieves the lowest latency, further reducing P90 TTFT by 11.3%
with hotspot-aware rebalancing.
5 CONCLUSION
This paper addresses the conflict between cache affinity and load balancing in distributed LLM serving. We propose DualMap, dual-mapping inference scheduler that simultaneously ensures KV cache reuse and balanced workload distribution. Key techniques include SLO-aware request routing, hotspot-aware rebalancing and lightweight dual-hash-ring scaling. Experimental results show that DualMap boosts effective request capacity by up to 2.25x under the same TTFT SLO constraints, and significantly reduces P90 latency across real-world world workloads, compared with the state-of-the-art arr work.
10

---

Published as a conference paper at ICLR 2026
6 ACKNOWLEDGEMENTS
This work was supported by National Key R&D Program of China N0.2023YFB450288) and Huawei. We sincerely thank the anonymous reviewers for their constructive comments and valu- able suggestions.
REFERENCES
Automatic prefix caching, 2025. http://as//gtttt......./////pppp
2614.
Introducing nvidia dynamo, a low-latency distributed inference framework for scaling reasoning ai models, 2025.
htt../iiiiaaaaaiooooooooooa. com/blog.
Sharegpt, 2025. htttps://saarggaet
Shubham Agarwal, Sai Sundaresan, Subrata Mitra, Debabrata Mahapatra, Archit Gupta, Rounak Sharma, Nirmal Joshua Kapu, Tong Yu, and Shiv Saini. Cache-craft: Managing chunk-caches for efficient retrieval-ause -aggeeeee generation. Proceedings of the ACM on Management of Data, 3(3): 1-28, 2025.
Amey Agrawal, Nitin Kedia, Jayashree Mohan, Ashish Panwar, Nipun Kwatra, Bhargav Gulavani, Ramachandran Ramjee, and Alexey Tumanov. Vidur: A large-scale simulation framework for Ilm inference. Proceedings of Machine Learning and Systems, 6:351-366, 2024.
Shiyi Cao, Yichuan Wang, Ziming Mao, Pin-Lun Hsu, Liangsheng Yin, Tian Xia, Dacheng Li, Shu Liu, Yineng Zhang, Yang Zhou, et al. Locality-aware fair scheduling in Ilm serving. arXiv preprint arXiv:2501.1em 14312, 2025.
Renze Chen, Zhuofeng Wang. Beiquan Cao, Tong Wu, Size Zheng, Xiuhong Li, Xuechao Wei, Shengen Yan, Meng Li, and Yun Liang. Arkvale: Efficient generative Ilm inference with recallable key-value eviction. Advances in Neural Information Processing Systems, 37:113134-113555 2024a.
Weijian Chen, Shuibing He, Haoyang Qu, Ruidong Zhang, Siling Yang. Ping Chen, Zheng, Baoxing Huai, and Gang Chen. Impress: An importanse-informed multi-tier prefix ky storage system for large language model inference. In 23rd USENIX Conference on File and Storage Technologies (FAST 25), pp. 187-201, 2025.
Yilong Chen, Guoxia Wang, Junyuan Shang, Shiyao Cui, Zhenyu Zhang, Tingwen Liu, Shuohuan Wang, Yu Sun, Dianhai Yu, and Hua Wu. Nacl: A general and effective kv cache eviction frame- work for llms at inference time. arXiv preprint arXiv:2408.00 03675, 2024b.
Giuseppe DeCandia, Deniz Hastorun, Madan Jampani, Gunavardhan Kakulapati, Avinash Laksh- man, Alex Pilchin, Swaminathan Sivasubramanian. Peter Vosshall, and Werner Vogels. Dynamo: Amazon's 's highly available key-value store. ACM SIGOPS operating systems review, 41(6):205- 220, 2007.
Bin Gao, Zhuomin He, Puru Sharma, Qingxuan Kang, Djordje Jevdjic, Junbo Deng, Xingkun Yang, Zhou Yu, and Pengfei Zuo. Cost-efficient large language model serving for multi-turn conversa- tions with cachedattention. In 2024 USENIX Annual Technical Conference (USENIX ATC 24),
pp. 111-126, 2024.
Shibo Hao, Tianyang Liu, Zhen Wang, and Zhiting Hu. Toolkengpt: Augmenting frozen language models with massive tools via tool embeddings. Advances in neural information processing sys- tems, 36:45870-455555 2023.
David Karger, Eric Lehman, Tom Leighton, Matthew Levine, Daniel Lewin, and Rina Panigraby. Consistent hashing and random trees: distributed caching protocols for relieving hot spots the world wide web. Proceedings of the nwetty-ninth annual ACM Symposium on Theory of Computing (STOC), pp. 654 663. ACM, 1997.
11

---

Published as a conference paper at ICLR 2026
Woosuk Kwon, Zhuohan Li. Siyuan Zhuang. Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph Gonzalez, Hao Zhang, and Ion Stoica. Efficient memory management for large language model serving with pagedattention. In Proceedings of the 29th Symposium on Operating Systems Prin- ciples, pp. 61 1-26,, 2023.
Wonbeom Lee, Jungi Lee, Junghwan Seo. and Jaewoong Sim. Infinigen: Efficient generative infer- ence of large language models with dynamic kv cache management. 18th USENIX Symposium on Operating Systems Design and Implementation (OSDI 24), pp- 155-172, 2024.
Weizhuo Li, Zhigang Wang, Yu Gu, and Ge Yu. Xkv: Personalized kv cache memory reduction for long-context Ilm inference. arXiv preprint arXiv:2412.05890 2024a.
Yuhong Li, Yingbing Huang, Bowen Yang, Bharat Venkitesh, Acyr Locatelli, Hanchen Ye, Tianle Cai, Patrick Lewis, and Deming Chen. Snapkv: Lim knows what you are looking for before generation. Advances in Neural Information Processing Systems, 37:22947-229977 2024b.
Michael Mitzenmacher. The power of two choices randomized load balancing. IEEE transactions on parallel and distributed systems, 12(10):1094-1104 2002.
Rasmus Pagh and Flemming Friche Rodler. Cuckoo hashing. In International Symposiumm Algo- rithms and Computation, pp. 121-133. Springer, 2001.
Reiner Pope, Sholto Douglas, Aakanksha Chowdhery, Jacob Devlin, James Bradbury, Jonathan Heek, Kefan Xiao, Shivani Agrawal, and Jeff Dean. Efficiently scaling transformer inference. Proceedings of Machine Learning and Systems, 5:606-624, 2023.
Ramya Prabhu, Ajay Nayak, Jayashree Mohan, Ramachandran Ramjee, and Ashish Panwar. vat- tention: Dynamic memory management for serving Iims without pagedattention. In Proceedings of the 30th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 1. pp. 1133-1150, 2025.
Ruoyu Qin, Zheming Li, Weiran He, Jialei Cui, Feng Ren, Mingxing Zhang, Yongwei Wu, Weimin Zheng, and Xinran Xu. Mooncake: Trading more storage for less computation- a kveache- centric architecture for serving I1m chatbot. In 23rd USENIX Conference on File and Storage Technologies (FAST 25), pp. 155-170. USENIX Association, 2025.
Luohe Shi, Hongyi Zhang, Yao Yao, Zuchao Li, and Hai Zhao. Keep the cost down: A review methods to optimize I1m's kv-cache consumption. arXiv preprint 24X,::2407.18003 2024.
Vikranth Srivatsa, Zijian He, Reyna Abhyankar, Dongming Li, and Yiying Zhang, Preble: Efficient distributed prompt scheduling for I1m serving, arXiv preprint arXiv:2407.00023, 2024.
Ion Stoica, Robert Morris, David Karger, Frans Kaashoek, and Hari Balakrishnan. Chord: A
scalable peer-to-peer lookup service for internet applications. ACM SIGCOMM computer com- munication review, 1944):1491160, 2001.
Foteini Strati, Sara Mcallister, Amar Phanishayee, Jakub Tarnawski, and Ana Klimovic. D(eej' (vvu: Kv-cache streaming for fast, fault-tolerant generative Ilm serving. arXiv preprint arXiv:2403.01886, 2024.
Hanshi Sun, Li-Wen Chang, Wenlei Bao, Size Zheng, Ningxin Zheng, Xin Liu, Harry Dong, Yuejie Chi, and Beidi Chen. Shadowkv: Ky cache in shadows for high-throughput long-context I1m inference. arXiv preprint arXiv:2410.21465, 2024.
Qwen Team. Qwen2 technical report. arXiv preprint arXiv:2412.15113 2024.
Bin Wang, Bojun Wang, Changyi Wan, Guanzhe Huang, Hanpeng Hu, Haonan Jia, Hao Nie, Min- gliang Li, Nuo Chen, Siyu Chen, al. Step-3 is large yet affordable; Model-system co-design for cost-effective decoding. arXiv preprint arXiv:2507.1942 2025a.
Jiahao Wang, Jinbo Han, Xingda Wei, Sijie Shen, Dingyan Zhang, Chenguang Fang, Rong Chen, Wenyuan Yu, and Haibo Chen. Kveache cache the wild: Characterizing and optimizing kveache cache at large cloud provider. arXiv preprint 2506:25006.0634 2025b.
12

---

Published as a conference paper at ICLR 2026
Zihao Wang, Bin Cui, and Shaoduo Gan. Squeezeattention: 2d management of kv-cache in Ilm inference via layer-wise optimal budget. arXiv preprint arXiv:2404.04793, 2024.
Bingyang Wu, Shengyu Liu, Yinmin Zhong, Peng Sun, Xuanzhe Liu, and Xin Jin. Loongserve: Efficiently serving long-context large language models with elastic sequence parallelism. Pro- ceedings of the ACM SIGOPS 30th Symposium on Operating Systems Principles, pp. 640-654, 2024.
Guanlong Wu, Zheng Zhang. Yao Zhang, Weili Wang, Jianyu Niu, Ye Wu, and Yinqian Zhang- I know what you asked: Prompt leakage via kv-cache sharing in multi-tenant Ilm serving. In Proceedings of the 2025 Network and Distributed System Security (NDSS) Symposium. San Diego, CA, USA, 2025.
Jingbo Yang. Bairu Hou, Wei Wei, Yujia Bao, and Shiyu Chang. Kvlink: Accelerating large lan- guage models via efficient kv cache reuse. arXiv preprint MxXv:2552.11602 2025.
Jiayi Yao, Hanchen Li, Yuhan Liu, Siddhant Ray, Yihua Cheng, Qizheng Zhang, Kuntai Du, Shan Lu, and Junchen Jiang. Cacheblend: Fast large language model serving for rag with cached knowledge fusion. In Proceedings of the Twentieth European Conference on Computer Systems, pp. 94 109, 2025.
Lu Ye, Ze Tao, Yong Huang, and Yang Li. Chunkattention: Efficient celf-attention with prefix-aware kv cache and two-phase partition. arXiv preprint arXiv:2442.11522 2024.
Hailin Zhang. Xiaodong Ji, Yilin Chen, Fangcheng Fu, Xupeng Miao, Xiaonan Nie, Weipeng Chen, and Bin Cui. Pqcache: Product quantivation-based kvcache for long context Ilm inference. Pro- ceedings of the ACM on Management of Data, 3(3):1-30, 2025.
Lianmin Zheng, Liangsheng Yin, Zhiqiang Xie, Chuyue Livia Sun, Jeff Huang, Cody Hao Yu, Shiyi Cao, Christos Kozyrakis, Ion Stoica, Joseph E Gonzalez, et al. Sglang: Efficient execution of structured language model programs. Advances Neural Information Processing Systems, 37: 62557-62583, 2024a.
Zhen Zheng, Xin Ji, Taosong Fang, Fanghao Zhou, Chuanjie Liu, and Gang Peng. Batchlim: Op- timizing large batched IIm inference with global prefix sharing and throughput-oriente token batching, arXiv preprint arXhv:2412.03594 2024b.
Yimmin Zhong, Shengyu Liu, Junda Chen, Jianbo Hu, Yibo Zhu, Xuanzhe Liu, Xin Jin, and Hao Zhang. (DistServe): Disaggregating prefill and decoding for goodput-optimized large language model serving. In 18th USENIX Symposium Operating Systems Design and Implementation (OSDI 24), pp. 193-210, 2024.
Ruidong Zhu, Ziheng Jiang, Chao Jin, Peng Wu, Cesar A Stuardo. Dongyang Wang, Xinlei Zhang, Huaping Zhou, Haoran Wei, Yang Cheng, et al. Megascale-infer: Serving mixture-of-expee at scale with disaggregated expert parallelism. arXiv preprint 2rXiv:2504.02263, 2025.
A APPENDIX
A.1 LLM USAGE STATEMENT
In preparing this paper. used Large Language Model in polishing the writing. Specifically, the L.LM was employed to improve grammar and readability of the text. No part of the research ideation, experimental design, data analysis, results interpretation involved the use of LLMs. The authors take full responsibility for all content of the paper.
A.2 DESIGN
A.2.1 SLO-AWARE REQUEST ROUTING
To balance cache reuse and load distribution, the DualMap global scheduler maps each request to candidate instances using two independent hash functions over the request's prompt prefix.
13

---

Published as a conference paper at ICLR 2026
Selecting between the two candidates involves critical trade-off: prioritizing cache affinity reduces the prefill compute time through KV cache reuse, while prioritizing load balancing reduces queuing delays. This choice directly impacts the request's TTFT.
Request Count
Request Count
4000
4000
3622
3022
2000
2000
21
0
28
11
21
18
2
1
3
5
7
9 10
11
13
Prefix Length (Depth)
Prefix Length (Depth)
(a) Conversation
(h) Tool&Agent
Figure 6: Distribution of hash key prefix lengths for the Conversation and Tool&Agent datasets.
How long prefix is appropriate for the hash key? We analyze the distribution of hash key lengths on two datasets: Conversation and Tool&Agent, where the length represents the number of blocks (one block contains 512 tokens) the prefix.
As shown in Figure 6a, on the Conversation dataset, 95% of requests have shared prefix length of 2 blocks. This because the prefixes this dataset are not skewed. Therefore, two blocks (one system block and one user input block) sufficient to identify shared-prefix requests, allowing them to be scheduled to the same instance without being scattered across multiple instances due to overlong hash keys.
In contrast, on the Tool&Agent dataset Figgure 6b), 45.2% of requests are similar to those in the Con- versation dataset, with a hash key length of blocks, because these requests are relatively balanced. However, 14.9% and 37.8% of requests have hash key lengths of 6 and 13 blocks, respectively. This due two abnormally popular prefixes in the Tool&Agent dataset. Our adaptive hash prefix length mechanism detects these skewed prefixes and extends their hash key lengths, preventing them from being mapped the same instance and avoiding severe load imbalance.
Baseline Strategies. A naive least-loaded strategy selects the instance with the lower load, disre- garding cache availability. As shown in Figure 7, Request is routed Instance because has fewer queued requests, even though Instance already holds the matching KV cache. This results in cache miss and longer prefill compute time, which turn increases GPU occupancy and delays subsequent requests (e.g., Requests 3, 5, and 7), elevating their TTFT and increasing the risk of violating SLOs.
In contrast, a pure sache-affinity strategy always routes request to the instance with the highest expected cache reuse. While this minimizes recomputation, it can lead to severe load imbalance. For example, if all matching prefixes are cached Instance shown in Figure 7, all corresponding requests will be routed there, leading to queue buildup and long queuing delays (e.g., Requests 5, 6, and 7), despite short computation times.
To minimize the risk of TTFT SLO violations, the Min TTFT policy estimates TTFT for each can- didate instance and selects the one with the lower value. For request and candidate instance we define:
(r, i): estimated queuing delay of Request r on Instance i, capturing system load. (r(r, i): expected computation time for Request r on Instance i, depending on whether cache reuse occurs.
Thus, the estimated total TTFT is: TTFT(r, = (r, (T(rr
In the example, although Instance 1 has a longer queuing delay (T, (1, > (1,)) benefits from cache reuse (1, < T. (1,2)), resulting in lower total TTFT: TTFT(1, 1) T, (1,1) Te(1,1) TTFT(11 (1,22) T2(1,2)
(8)
14

---

Published as a conference paper at ICLR 2026
Timeline
Requests
DualMaa-least-loaded
Instance
Request
Least
Contex caching
Loaded
Instance
DualMap--ache-afffitt
Instance
Request
Cache
Affinity
Contex caching
Instance
DualMap-min-ttft
Instance
Request
4 Contex caching
Min TTFT
Instance
Diallhapssloaaarrerrust-t-uuuuu
Instance 1
Request
DualMap
Contex caching
TTFT SLO
Instance
Figure 7: SLO-aware request routing. Different colors represent different prefixes. Instance has context caching for all prefixes, while Instance 2 has no context caching.
Therefore, Min TTFT routes Request to Instance
However, as new requests arrive, this strategy may oscillate between cache-aware and load-aware decisions. For example, when Request arrives, the queue at Instance grows T3 (2, 1) > (2 2), causing the scheduler send the request to Instance 2 despite cache miss. This load rebalancing improves fairness at the cost of recomputation. As the queue at Instance shortens, future requests (e.g., Requests 3, 4, and are again routed there, until the load imbalance grows again. In cases like Request 6, the scheduler again sacrifices cache affinity for load balancing.
While adaptive, this switching behavior leads frequent cache misses under load fluctuation, in- creasing recomputation overhead and worsening overall TTFT. As observed with Request 7, re- peated recomputation and queuing can lead SLO violations. Fundamentally. Min TTFT's pursuit of optimal latency per request inadvertently degrades cache reuse and destabilizes load balance over time.
The SLO-Aware Strategy. To address these issues, DualMap adopts a TTFT-SLO-avee aware routing strategy that explicitly incorporates TTFT constraints. The key idea to maintain cache affinity whenever possible, and only trade it off when load imbalance threatens to breach SL.O constraints.
DualMap prioritizes cache affinity and initially selects the instance with the highest cache reuse. Requests are routed to this instance until its load causes the expected TTFT to exceed the SLO. At that point, DualMap switches to load-aware strategy and selects the less loaded instance to avoid long queues and reduce TTFT tail latency. As shown in Figure 7, Requests 1 1-4 are routed to Instance due to acceptable load difference and high cache reuse. Once the cache-affine instance becomes overloaded and violates the TTFT SLO, Request 5 is routed to Instance 2 to rebalance the load, even at the cost of recomputation.
Unlike Min TTFT, DualMap does not seek per-request optimal TTFT. Instead, it preserves cache reuse whenever load conditions permit, switching to load balancing only when necessary. This reduces the frequency of recomputation and stabilizes cache hit rates. Furthermore, both instances have a matching prefix in their caches (i.e., equal prefix hit rate), DualMap always chooses the less- loaded one (e.g., Requests 6 and 7), further enhancing load balance without sacrificing reuse.
A.2.2 HOTSPOT-AWARD REQUEST REBALANCING
Instance-hotspots in system. While the PoTC principle provides strong baldninlng guarantees under uniformly random choices (Mitzenmacher, 2002), real-world request patterns are often highly
15

---

Published as a conference paper at ICLR 2026
X10
x10
h Waiting tokens
Vialiing tokens
Replica ID
1000
2000
3000
1000
2000
3000
Request ID
Request
(a) Conversation
(b) Tool&Agent
Figure 8: Hot instance phenomenon in real-world datasets. The bright yellow regions indicate overloaded instances.
Request Migration benefit
Low
HHigh
Instance 0
Instance 1
Instance n
(0.1)
(13 (1.2
(n.1]
Request queue
Selected
Backup Instance
Instance
Figure 9: Hotspot-aware request migration.
skewed. In practice, KV prefix popularity often follows skewed distribution (Wang et al., 2025b), making the candidate selection DualMap non-uniform. For instance, tool-agent scenarios fre- quently involve small number of widely used tools, while conversation agents often operate trending topics. These skewed access patterns lead to certain prefixes being disproportionately com- mon, causing some instances be selected far more frequently than others, even under DualMap. As a result, persistent hotspots emerge. Empirical results in Figure 8 show that hot instances fre- quently emerge under DualMap scheduling, particularly in the tool-agent workload. This is tributed to the high concentration of requests targeting popular tool prompts, which are repeatedly hashed the same candidate instances, resulting severe queuing and load imbalance.
sestance-hotspots-awaaar Rebalancing. To achieve timely rebalancing, DualMap initiates batch migration during the initial routing phase whenever both candidate instances of a request are iden- tified overloaded. As illustrated in Figure 9, for each overloaded instance, DualMap estimates the migration benefit of each queued request using Eq. 6. request eligible for migration only satisñes satisfying B( > 0 and TTFTr,, TTFT ensuring both TTFT improvement and SLO compliance. Requests are prioritized by descending benefit and migrated until all requests in the overloaded instance's 's queue are expected to meet the TTFT SLO. This hotspot- migration mechanism effectively relieves overloaded instances while preserving cache affinity.
A.2.3 LIGHTWEIGHT WUAL-HASH-RIA SCALING
In DualMap, all instances and request prefixes are placed on a logical ring based on their hash values, and each hashed prefix selects the nearest clockwise instance as its candidate. Thus, mappings depend solely on their relative positions on the ring.
Adding an instance introduces new anchor point on the ring. Only requests whose hashed positions fall between the previous and the new anchor are remapped; all others retain their original mappings. Similarly, removing an instance affects only the prefixes that previously mapped to that instance.
We illustrate this with simple example. Suppose the cluster has four instances A, B, C, D placed on logical ring according to their hash values, with the clockwise order A resulting mefix-to-instande mapping is:
C - D. The
(A, B] B, (B,C) C. (C, D.
16

---

Published as a conference paper at ICLR 2026
Requests hashed in (A, B] map to B, those in (B, C] to C. and those in (C,
added, and its hash value places it between and C, yiclding the updated ring A B + E C + D. The mapping becomes:
Now suppose a new instance
[ + B, (B, E, (E - C, (C, + D.
Only requests whose hashed positions fall in (B, E] are remapped to the new instance E, while all other mappings remain unchanged.
A.3 EVALUATION
A.3.1 WORKLOADS
We use two real-world trace datasets from Mooncake (Qin al., 2025): Comversation and Tool&Agent. Conversation is derived from multi-turn chatbot interactions. It exhibits approximately 40% prefix caching ratio due to high intra-session prefix reuse. Tool&Agent is characterized by long and repetitive system prompts, with prefix cache ratio of 59%. Table summarizes the workload characteristics. To ensure mcaningful cache behavior under limited KV cache capacity, we evaluate the first 4,000 requests from Conversation and the first 8,000 from Tool&Agent. Arrival timestamps are preserved and scaled to simulate varying QPS levels.
Due to memory constraints NPUs, the input length of each request is capped at 20,480 tokens for the 7B model and 10,240 tokens for the 14B model. To ensure consistent cache behavior, the first 500 requests used for warm-up and excluded from all reported results.
Table 1: Workload characteristics for Conversation and Tool&Agent Agent traces.
Conversation
Tool&Agent
Avg. Input Length
12,035
8,596
Avg. Output Length
343
182
Prefix Caching Ratio
40%
59%
Number Requests
4,000
8,000
A.3.2 CACHE HIT RATE AND LOAD BALANCE RATIO
To understand the source of performance differences across scheduling strategies, we evaluate the cache hit rate and load balance ratio of four basclines and DualMap under the Conversation and Tool&Agent workloads using the Qwen2.5-7B model.
Cache Hit Rate. As shown in Figures 10a and 10b, DualMap achieves cache hit rates comparable to the Cache Affinity strategy under both the Conversation and Tool &Agent workloads, reaching 62.5% and 96.4% of the theoretical upper bound, respectively. This is attributed to DualMap'ss prompt- based mapping strategy and its cache-aware routing when conditions permit($3.2). These designs enable DualMap preserve strong cache affinity, thereby reducing prefill computation overhead, shortening the NPU occupation time per request, and decreasing queueing delays for subsequent uequests-ultimatelyy improving the likelihood of meeting TTFT SLOs.
In contrast, the Least Loaded strategy exhibits significantly lower cache hit rates on both workloads, it prioritizes load balancing across instances without regard for cache reuse. Min TTFT improves upon this by incorporating cache-aware routing for a subset of requests, resulting in higher cache hit rates. Preble performs similarly Least Loaded due its conservative policy: only engages in cache-aware scheduling when the request's prefix cache hit rate exceeds 50%, which limits its overall cache reuse potential.
Load Balance Ratio. As shown in Figures 1a and 11c, DualMap maintains consistently low and stable system load throughout the entire experiment, significantly outperforming baselines. This benefit comes from its dual-mapping design, which achieves high cache affinity and consequently reduces overall computational load, enabling faster request completion. In addition, upon detecting overload, DualMap proactively migrates requests from overloaded instances lighter ones. This allows DualMap to maintain load balance across all instances, ensuring efficient resource utilization and reduced queuing delays, shown in Figures 1 llb and 1 1d.
17

---

Published as a conference paper at ICLR 2026
Affinity
TTFT
DualMap
Cache Hit Rate (%)
Cache Hit Rate (%)
40
28.6
29.5
60
26.5
61.8
66.9
20
13.2
20
(a) Conversation
(b) Tool&Agen
Figure 10: Cache hit rate with Qwen2.5-7B.
Affintty
TTFT
Dua
x10=
Pending Tokens
2.0
Bidding Tokens
3400
1.5
2.0
200
1.0
8000
0.5
3500
0.0
0.0
0.0
0.0
x10
110
Request
Request ID
Request
x10²
Request ID
x10²
(a) Pending tokens count in Conversation
(b) Load balance ratio
(c) Pending tokens count
(d) Load balance ratio in Tool&Agent
in Conversation
in Toel&
Figure 11: Pending tokens count and load balance ratio across all instances with Qwen2.5-7B
Instance:
SLO attainment (%)
100
Request Count
300
100
SLO attainment
Ceche Ht Rata
200
50
50
50
100
0.0
4--0
100 Time(second)
200
100
160
200
0
x10*
x10
Time(second)
Time(second)
Timaasecond)
(a) Overall SLO attain- (h) Number of requests the cluster
(c) Overall S1.O attain-
(d) Cache hit rates of in- dividual instances
routed to each instance
ment across the cluster
Figure 12: Scaling experiments: (a) and (b) scale-up from 4 to 8 instances; (c) and (d) scale-down from to 4 instances. Stability at 4 instances.
The load across instances is not always perfectly balanced. This because DualMap prioritizes cache-aware scheduling among two candidate instances during initial routing, until the number of queued requests on cache-hitting instances grows too large to meet the TTFT SL.O. This approach ensures that most requests still meet their TTFT $1.O while maximizing cache reuse and reducing prefill computation. As a result, the number pending tokens per instance significantly reduced for DualMap. In contrast, Cache Affinity exhibits poor load balance, as its design co-locates requests with shared prefixes onto the same instance, resulting in severe skew, which leads to continuous ac- cumulation of pending tokens. Least Loaded achieves almost perfectly uniform load distribution (CV=0) on both workloads, consistent with its load-aware scheduling policy. However, its pend- ing token count is much higher than that of DualMap due insufficient cache reuse. Min TTFT and Preble show noticeable improvements over pending tokens count and CV by trading off load balancing and cache affinity.
A.3.3 ELASTICITY EVALUATION
We evaluate DualMap's 's elasticity under the Tool&Agent workload using the Qwen2.5-7B model. SLO attainment (i.e., percentage of requests with TTFT 5s) is used to assess scaling effectiveness.
Scaling Up. As shown in Figure 12a, with 4 instances under QPS=4, the system quickly becomes overloaded, causing widespread SL.O violations. At 74 seconds, DualMap detects overload and
18

---

Published as a conference paper at ICLR 2026
Cache Affritty
Min TIFT
Dualap
Routing
KV query
Goodpul (reuls)
40
Leasi Loaded
Preble
3
Rebalancing
KV cave
30
Latendy
10
25
30
10
15
20
25
Number
Number
(a) Scalability of goodput
(b) Function execution latency
Figure 13: Scalability and scheduler overhead under the Tool& &gentt workload using the Qwen2.5- 7B model, with the number of instances varying from 8 to 32.
adds 4 instances (Instance 4-7). SLO attainment promptly rises 90% as the scheduler routes new requests to the newly added idle instances (Figure 12b), relieving pressure on hot instances.
Scaling Down. Later, under reduced load (QPS=2) and with instances, the system becomes un- derutilized. At 1809 seconds, DualMap begins gradual downscaling, reducing to 4 instances (Fig- ure 12c), while maintaining over 90% SL.O attainment.
A.4 SCALABILITY AND OVERHEAD
We evaluate the scalability of DualMap and scheduler overhead using the Vidur-based simula- tor (Agrawal et al., 2024). We simulate cluster of instances, each with 64 GB DRAM and one NPU (910B4), serving Qwen2.5-7B the Tool&Agen workload. The number of instances is scaled from 8 to 32, and the total number of requests is increased proportionally from 8K to 32K.
A.4.1 SCALABILITY ANALYSIS.
As shown in Figure 13a, DualMap achieves near-linear growth in goodput (the maximum sustainable request rate under the 90% TTFT SLO) (Zhong et al., 2024) and consistently outperforms Cache Affinity, Least Loaded, Min TTFT, and Preble across all cluster sizes. This demonstrates the strong scalability of the dual-mapping design. These results indicate that DualMap's dual-mapping design scales well: prefix-bound dual hashing preserves cache affinity, while rebalancing always operates within candidate pairs, keeping the waad-balnneing behavior stable as the cluster grows.
A.4.2 SCHEDULER OVERHEAD.
DualMap maintains per-instance metadata for DRAM-based KV caches and request queues, up- dating it as requests are scheduled and executed. KV cache metadata supports estimating reusable tokens and thus prefill computation cost, while queue metadata provides queueing-delay estimates for TTFT prediction, enabling both SLO-aware routing and hotspot-aware rebalancing. The primary overhead of DualMap arises from the metadata footprint and the runtime footprint of key scheduler operations.
Metadata footprint. Metadata footprint is dominated by KV cache (request queues are typically short, so their cost is negligible). Following MooncakeAPC-sttle (202, 2025) designs, each 128- token block stores a hash value and block ID (8B each), i.e., 16B per block. For Qwen2.5-7B, 64GB KV cache contains 9,632 blocks, so each instance stores about 146.2 KB of metadata, which engineering-wine wise negligible; a 32-instance cluster stores 4.57MB. For Qwen2.5- 14B, the per- instance and 32-instance metadata costs are 44KB and 1.38MB, respectively, growing linearly with total KV-cache capacity.
Runtime footprint. DualMap's runtime footprint primarily comes from three operations (Fig- ure 13b): KV cache access, SLO-aware request routing($3.2),, and hotspot-aware request rebalancing($3.3).
(1) KV cache access. For each request, DualMap computes the number reusable tokens by query- ing the KV cache to estimate the remaining prefill computation and expected TTFT. Both KV cache query and save operations take ~0.2 ms and are independent cluster size, since each instance's KV cache metadata maintained and accessed independently by the global scheduler.
19

---

Published as a conference paper at ICLR 2026
1.0
0.8
0.8
0.8
[50. 0.52)
0.8
0
0.4
0.4
(50. 0.24)
0.2
0.0
0.0
0
20
40
60
80
0
20
40
60
80
Shared Prefix Rate (%)
Shared Prefix Rate (%)
(a) Conversation
(b) Agent
Figure 14: CDF of shared prefix rate for the Conversation and Tool&Agent workload.
(2) Routing((3.2). SLO-aware request routing takes ~0.6 ms per request, consisting of dual hash- ing to obtain candidate instances (~0.055 ms) and TTFT estimation via KV cache queries. These operations depend only on per-instance metadata, so routing latency does not grow with cluster size.
(3) Rebalancing( $3.3). Hotspot-aware request rebalancing takes 2.2-2.5 ms per invocation. For each request on overloaded instance, DualMap computes the current TTFT and the hypothetical TTFT after migration. Each TTFT evaluation requires two KV cache queries (one on the overloaded instance and one on its backup), so the total cost scales with the queue length of the overloaded in- stance, independent of the total number of instances in the cluster. In practice, instance request queues are typically short, so the overhead of hotspot-awart rebalancing remains bounded and ac- ceptable.
A.5 SHARED PREFIX RATE CHARACTERIZATION
Prompts are partially shared across requests real-world workloads (Srivatsa et al., 2024: Gao et al., 2024). For the workloads used in our study, Conversation and Tool&Agent, we measure the shared prefix rate, defined as the fraction of a request's prompt that overlaps with the longest shared prefix among preceding requests within the same workload, where "length" refers to the number of tokens. Figure 14a shows that 48% of Conversation requests share at least 50% of their prompt prefix, reflecting naturally recurring dialogue histories across multiple conversation turns. Figure 14b shows an even stronger effect: 76% of Tool&Agent requests share at least 50% of their prefix, largely due to repeated system prompts and consistent tool prompts. These results confirm the high prevalence of shared prefixes in practical LLM serving environments and highlight the importance of aache-afiintty-avy scheduling to maximize KV cache reuse and reduce prefill computation.
A.6 INTEGRATION INTO DISAGGREGATED ARCHITECTURES
DualMap is agnostic to the internal micro-architectural design of the serving system and only re- quires an estimated TTFT for each candidate instance.
Predill-Decode (PD) Disaggregation. In PD-disaggregated systems, TTFT is dominated by the prefill phase. DualMap therefore performs routing exclusively on the prefill instances, while decode instances are attached following the serving framework's existing mechanism (e.g., vLLM). This design avoids any invasive changes to the underlying execution pipeline.
Attention-FFN (AF) Disaggregation. AF disaggregation primarily an optimization for the de- code stage (Zhu et al., 2025; Wang et al., 2025a). In practice, many systems first apply PD disag- gregation and then perform AF disaggregation within the decode nodes. Similar to the PD setting, DualMap focuses putation and queueing delay. Because AF disaggregation occurs downstream in the decode stage, it does not affect DualMap's 's routing objective: minimizing TTFT through KV cache affi- ity and load balancing on the prefill instances. Thus, DualMap naturally remains compatible with AF- greegaggeee architectures without requiring additional modifications.
scheduling the prefill (P) instances, where TTFT is determined by prefill com-
20

---

Published as a conference paper at ICLR 2026
A.7 CLARIFYING NOVELTY AND CONTRIBUTION
While DualMap adopts hashing primitives similar to classical distributed systems such as Dy- namo (DeCandia al., 2007) and Chord (Stoica al., 2001), it addresses fundamentally different challenge specific to distributed LLM serving: reconciling KV cache affinity with load balanc- ing under strict TTFT SLOs. While both DualMap and these systems use hashing primitives, their mechanisms diverge significantly:
Novel Mechanism: Prefix-Bound Dual Candidates. Classical systems map each key to single location (e.g.. Chord's successor) or a primary with fixed replicas (e.g., Dynamo). DualMap introduces a prefix-bound dual-candidate mechanism:
Prefix(p) = (1,,2)
Each request prefix p deterministically mapped a pair of candidate instances via two independent hash functions. This provides exactly two degrees of freedom for load bal- ancing-followen the PoTC principle-whit ensuring that all requests sharing the same prefix always routed among the same two candidates. This structure is essential for maintaining KV-cache locality and is not present in traditional systems.
SLOO-Aaare Request Routing. Instead of static replica selection, DualMap chooses be- tween its two candidates using TTFT estimation function that jointly considers the cache- reuse benefit and queuing delay, which is entirely absent in traditional systems.
Hotspot-Aware Request Rebalancing. LLM workloads often display highly skewed re- quest distributions, resulting in concentrated instance hotspots that may violate SLOs by consistent hashing alone. DualMap introduces hotspot-aware request rehalancing, which selectively migrates requests only within their prefix-bound candidate pair. This migra- tion alleviates overload without scattering prefixes across instances, preserving cache lo- cality-a a property that traditional systems neither require nor are designed to support.
DualMap is not minor variant of consistent hashing. It is a novel scheduling framework purpose- built to simultaneously achieve cache affinity and load balancing under the strict SLO requirements of modern LLM serving workloads.
A.8 DISCUSSION: ROBUSTNESS OF TTFT ESTIMATION UNDER MEMORY CONTENTION
This section provides additional details on the robustness of TTFT estimation in scenarios with NPU memory contention.
A.8.1
DECODE BOTTLENECK
Under the vLLM serving backend, each inference instance prioritizes prefill computations over de- codes as long as sufficient NPU memory is available. Memory is released only after a request com- pletes its decode stage. At high request rates, repeated prefills cause "rapid memory consumption on the NPU, eventually preventing new prefills from being scheduled. Once this occurs, the sched- uler must switch to decode execution in order to free memory blocks. During this phase, a prefill request may need to wait for one more decode tasks to finish, causing a delay whose magnitude depends on the lengths of the ongoing decodes as well as the current memory pressure. We refer to this phenomenon as the memory- wwwarr--eaattttnnnnuueee decode bottleneck. The delay introduced in this state is denoted as D; for instance
A.8.2 IMPACT OF THE DECODE BOTTLENECK ON SLO-AWARE REQUEST ROUTING
SLO-aware request routing uses the original TTFT estimate TTF i) Ty(r,)) i) + Tr(r, i), where TTFT(r, i) denotes the predicted TTFT for dispatching request to instance i. When the decode bottleneck state introduces an additional delay D., the actual TTFT becomes TTFT actual D,+T, (r, i). If D, is small, TTFT typically remains below the TTFT-SLO threshold, causing negligible deviation in SLO attainment. In contrast, when D; becomes large, TTFTe likely to exceed the TIFT-SLO, causing most requests on the memory- instance to violate TTFT SLOO. This behavior effectively mirrors overloaded-instance condition, in which
21

---

Published as a conference paper at ICLR 2026
requests fail to meet their TTFT-SLO. Consequently, delegate the mitigation of persistent decode bottleneck states to the hotspot-aware request rebalancing mechanism.
A.8.3 HOTSPOT- REQUEST REBALANCING UNDER DECODE BOTTLENECKS
In the hotspot-aware request rebalancing mechanism, instance that remains in decode-bound phase for an extended period is treated as overloaded, and requests in its queue that are at risk of violating the TTFT SLO should be migrated to less-loaded instances, thereby mitigating the issue of widespread TTFT SLO violations caused by decode bottlenecks. This mechanism relies on two core components: bottleneck detection and TTFT correction.
Decode Bottleneck Detection. An instance is considered to be in decode bottleneck state when fails to complete any prefill computation for an extended period while its request queue remains non-empty. To detect this condition, the global scheduler monitors the interval prefill interval = feurrent fist prefill. where fist preill is the timestamp of the last prefill completion. Once this interval exceeds threshold T, the instance is flagged as being in the long decode bottleneck state. This heuristic provides a practical approximation of the decode-induced delay and does not depend on the decode lengths of individual requests.
The threshold T reflects a trade-off between timely detection of decode bottlenecks and the preser- vation of cache affinity. A large 7' delays bottleneck detection, potentially increasing the number of SLO violations, whereas a small T leads to frequent migrations that may undermine the cache affin- ity established by SLO-aware request routing. Based empirical observations in deployment, is set to 3 seconds, which works well in practice.
Corrected TTFT Estimation and Request Migration. For instance identified as decode bot- tleneck hotspot, the TTFT estimate for its queued requests is corrected by adding an approximation of the decode delay:TTFFTS FTysorected Destimaned + (r, i) + (r(r; i). Since the true D; cannot be de- termined accurately, DualMap approximates D Destimated using the observed prefill interval. Although this approximation may not be entirely accurate, the interval grows as the bottleneck state persists, enabling DualMap to identify requests that are at risk of exceeding the TTFT SLO. When the cor- less-loaded
rected TTFT of a request exceeds the SLO, the rebalancing mechanism migrates candidate instance, ensuring that the request meets the TTFT SLO. This mechanism effectively con- verts unpredictable decode bottleneck latency into an overload signal that the global scheduler can detect through the responses of individual instances executing requests.
Although the decode bottleneck state complicates precise TTFT estimation, the rebalancing mech- anism ensures robustness by treating such states overload conditions and migrating requests ac- cordingly. This design enables DualMap to maintain high SLO attainment even under NPU memory contention that introduces decode-latency variability.
A.9 OPTIMAL CANDIDATE SET SIZE
To determine the optimal candidate set size d, we compute the maximum load deviation according to PoTC theory. The number of inference instances ranges from to n 32, and the total number of requests m is set to 8000-32000 such that the average load m remains constant. As shown in Figure 15, increasing d from 1 to 2 produces sharp reduction in maximum load deviation, consistent with the well-established near-exponential gain enabled by two-choice load balancing. When d exceeds 2, the marginal benefit quickly tapers off, indicating that larger candidate sets contribute little additional improvement in reducing imbalance.
These trends persist across all evaluated cluster sizes. Overall, d = 2 provides an effective balance for DualMap: it delivers strong inter-instance load balancing while keeping the candidate set small, thereby preserving high KV cache reuse.
B RELATED WORK
Prefix Sharing between Requests. A common scenario among multiple requests is the sharing of prompts. For instance, requests within the same session in multi-tum conversations share the prompt history of previous requests (Sha, 2025; Gao et al., 2024; Zheng al., 2024b; Yang al.,
22

---

Published as a conference paper at ICLR 2026
Max Load Deviation
60
Instances Number
n=8
40
n=16
n=
20
n=
0
1
2
4
5
6
7
8
Candidate Choices (d)
Figure 15: Maximum load deviation for different choices across cluster sizes (n -8-2).
2025: Li et al., 2024a); in tool agents, requests accessing the same tool often have identical tool usage instructions (Hao et al., 2023). For these shared prompts, using KV cache (Kwon et al., 2023; Prabhu al., 2025; Chen al., 2025; Lee al., 2024; Wu et al., 2024; Li et al., 2024b; Wu al., 2025; Wang et al., 2025b; Sun et al., 2024; Strati et al., 2024; Wang et al., 2024; Ye et al., 2024; Yao al., 2025; Agarwal al., 2025; Shi et al., 2024; Zhang et al., 2025; Chen et al.. 2024a;b) to trade computation for storage, by reusing the prefix's s key-value (KV) tensors across multiple requests (202, 2025: Zheng et al., 2024a), allows for direct loading of the KV cache corresponding to these shared prompts without recomputation. This saves valuable GPU computing resources and significantly reduces inference latency.
Scheduling Work Balancing Cache Affinity and Load Balance. Preble (Srivatsa et al., 2024) adopts a heuristic strategy: When the prefix hit rate of request (i.e., the ratio of the number of tokens matched with shared prefixes in the system to the total number of input tokens) exceeds 50%, the request is dispatched to the instance with the highest prefix hit rate, thus favoring Cache Affinity. Conversely, when the prefix hit rate is low, Preble routes requests based on combination of request inference cost and current instance load. However, this strategy can lead to behavior similar to the Least Loaded policy. For example, consider two instances: Instance I contains the KV cache for Request 1, and Instance 2 contains the KV cache for Request 2. If Instance / is more loaded when Request arrives, it will be routed Instance 2, breaking cache locality. Later, Request 2 may be routed to Instance for similar reasons.
Dynamo (Dyn, 2025) formulates scheduling function balance cache reuse against load balancing, defined as max; (eax;KKV VMttch, Load,). Here, KVMatch, denotes the prefix hit rate of request on instance and Load, represents the current load on instance i. When the load difference between instances is large, the cost function is dominated by the load term, degenerating into a Least Loaded policy. Conversely, when the request's prefix hit rate is high, the KVMatch term dominates, resulting in behavior similar to Cache Affinity.
Mooncake (Qin et al., 2025) routes each request the instance with the lowest estimated TTFT, which is composed of two factors: the queuing delay (proportional to the instance's 's current load) and the recomputation cost (inversely related to cache reuse). We refer to this policy as Min TTFT and simplify its cost function max; (pending wtt.eokeeoooooe _count; recompute_tokens_coom Where pending.toke wtt.ttokkescueee recompute. wrtoomputettkknsscoom count, denotes the number of tokens queued for prefill on instance i, and is the number of input tokens for request that must be recomputed on instance due to lack KV cache reuse. Similar to Dynamo, when the system is heavily loaded, the cost is dominated by the queuing term pending tokens count,, degenerating into the Least Loaded policy; when the system is lightly loaded, the cost is dominated by recomputation, behaving like Cache Affinity.
However, all these methods operate within a single mapping space and are fundamentally limited balaneing the trade-off between cache affinity and load balance. In contrast, DualMap proposes a novel dual- mapping scheduling framework enabling the system to simultaneously achieve both objectives.
23


Reviews:
[{"review_id": "h9oNnjx23u", "reviewer": "Reviewer_JVha", "summary": "DualMap build a system to better optimally allocate resources balancing both cache load and cache affinity. They describe ways to determine the appropriate hash length, SLO aware scheduling based on the violation of TTFT, and a rebalancing.", "questions": "1. Possibly a scalability/scheduler analysis could be good", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "I found this paper to be a good extension on existing work and provide decent/extensive results. \n\nThey contribute and interesting hotspot aware rebalancing and light weight rebalancing.", "weaknesses": "There seems to be a lack of scalability/scheduler overhead analysis in the implementation. It would be interesting to see on more GPUs(even if simulated).\n\nThe workload talks about cache migration based on TTFT but it would also be interesting if a direct NVLink transfer/memory cache state awareness was added to this policy.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "dz4baXUW0R", "reviewer": "Reviewer_iBGX", "summary": "This paper presents DualMap, a scheduling strategy for distributed LLM serving that considers both the cache affinity and load balancing. DualMap prepares two independent hash functions and selects the better one. It implements SLO-aware request routing, hotspot-aware rebalancing, and lightweight dual-hash-ring scaling. DualMap improves the effective request capacity by up to 2.25x.", "questions": "- What is the traffic ratio ρ? It seems the paper lacks definition.\n- What happens if two hash maps return the same instance?\n- How do you choose the instance to migrate ($j$ in Equation 3)? Do you search over all possible $j$?\n- In section 3.4, this part was not clear to me: \"Because request-to-instance mappings are determined by relative positions on the ring, changes to cluster membership affect only localized regions. This design ensures that most requests retain their original mapping paths during scaling operations\"\n- I am curious if two is the optimal number for hash maps. Would there be any benefits or disadvantages in having three or more hash maps?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "- This paper solves the real trade-off in the LLM serving system: load balancing vs. cache affinity.\n- Comprehensive evaluation to show the advantage of the proposed method against multiple baselines.", "weaknesses": "- There are a few points that are unclear to me. See questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Goz0qA1LcJ", "reviewer": "Reviewer_6DK7", "summary": "The paper proposes DualMap, a dual-mapping scheduling framework for distributed LLM serving that reconciles the trade-off between cache affinity and load balancing. By mapping each request to two candidate instances via independent hash functions and using SLO-aware routing, hotspot-aware rebalancing, and dual-hash-ring scaling, DualMap achieves both efficient KV cache reuse and balanced workloads. Experiments on real-world traces show up to 2.25× higher request capacity compared to state-of-the-art schedulers.", "questions": "1. Is there any challenge integrating Dualmap into disaggregation serving system (e.g. Prefill-Decode disaggregation, Attention-FFN disaggregation)?\n2. Could you please further explain the potential drawbacks of using global information for scheduling compared to Dualmap?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The problem is well defined: the trade-off between cache affinity and load balancing in LLM serving.\n2. Extends the “power of two choices” concept to LLM scheduling, offering a novel way to achieve both objectives simultaneously.\n3. The evaluation id comprehensive. Benchmarks across models and different baselines clearly show the superior performance.", "weaknesses": "1. The motivation for using two hashes for scheduling is unclear. Is it to save scheduling latency? Or, why not collect global information from all workers and then choose the best one (e.g. based on a weighted sum of prefix-cache and balance benefits)? The paper is very unclear on this point. \n2. While “power of two choices” is cited, formal analysis of DualMap’s convergence or optimality is limited.\n3. Lacks of scheduling overhead analysis.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "z3cjYmNZOp", "reviewer": "Reviewer_J9qz", "summary": "The paper addresses the challenge of LLM serving systems that utilize KV cache reuse for popular requests. The authors observe that existing systems often face a trade-off, prioritizing either nodes with high cache affinity or nodes that offer better load balancing. The paper argues that these two objectives can be jointly optimized, introducing a system called DualMap. The key insight is the application of the _power of two choices_ technique, where two nodes are probed for each request, and the request is assigned to the more suitable one. The suitability metric is designed to intelligently switch between prioritizing cache affinity or load balancing based on the current system state. Additionally, the authors propose active request rebalancing and the use of consistent hashing to facilitate scaling. The evaluation using two datasets shows that DualMap outperforms existing baselines.", "questions": "1. What qualifies as a _sufficiently positive_ benefit $B_r(i \\rightarrow j)$​ for triggering an active request rebalancing? Is there a specific threshold, and if so, how is it determined or tuned?\n2. In the Appendix (line 665), it is stated that 95% of Conversation dataset requests share a prefix of 2 blocks. What is a block here? What is the size of a block in terms of tokens?", "limitations": "", "rating": 6, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "- The paper is well-written, clear, and concise.\n- It addresses an important and timely problem in LLM serving: the trade-off between cache affinity and load balancing.\n- The proposed solution is systematic and effectively integrates established ideas from the systems literature.", "weaknesses": "- The core problem—hashing, server selection to optimize an objective, and scaling—has been studied extensively in the systems community. The proposed solution bears a strong resemblance to the work in [1]. This raises questions about the work's novelty. While _the application_ (LLM serving) is new, the underlying problem of load-aware request routing seems very similar. The paper would be significantly strengthened if the authors clearly delineated what differentiates DualMap from systems like [1], Chord~[2], or standard consistent hashing. What specific aspects of the LLM serving problem required novel design choices that existing solutions could not address? Explicitly positioning the work, even as a novel application and integration of established techniques to a new domain, would clarify its contribution.\n\n- The assumption that the TTFT of a request $r$ can be accurately estimated a priori (using $TTFT_q$​ and $TTFT_c$​) seems overly simplistic. Request processing time is a complex function, not just of queue length or cache presence. Specifically, the execution time of a batch containing cache misses depends on the mix of prefill and decode requests within it, which is unknown at routing time. Therefore, estimating $T_q​(r, i)$ or $T_c​(r, i)$ just from the queue state seems insufficient. This estimation problem is compounded if the instance-level scheduler does not use a simple FCFS policy. Given these factors, how can the system reliably estimate TTFT and predict potential SLO violations at the moment of the routing decision?\n\nMinor Comments:\n- The paper's motivation rests on the importance of KV cache reuse. However, this claim is not substantiated with data. How frequently do large prefix overlaps occur in real-world workloads? Please add a citation or, preferably, a microbenchmark/workload-characterization figure (similar to those in related work) to demonstrate the performance impact and prevalence of this problem.\n- Figure 1, which shows the trade-off, would be more effective as a Pareto curve rather than a bar chart. Please also plot DualMap's position on this curve to contextualize its design point.\n- Equation 2 uses the term $L(s_i​)$, which is presumably the load of instance $i$. Please define this term explicitly.\n- Figure 3 is central to the paper but is difficult to read due to cluttered text. Please consider replotting it, perhaps using a smaller font or simplifying the diagram.\n- Figure 7 is key for understanding the SLO-aware strategy but is currently unclear. Please label the strategies directly on the figure to show how they map to the baselines and DualMap. This would make the figure self-contained, removing the need to cross-reference the text (e.g., line 729). Figure 7 in the Sarathi Serve paper is a good example of this.\n\n\n[1] DeCandia, Giuseppe, Deniz Hastorun, Madan Jampani, Gunavardhan Kakulapati, Avinash Lakshman, Alex Pilchin, Swaminathan Sivasubramanian, Peter Vosshall, and Werner Vogels. \"Dynamo: Amazon's highly available key-value store.\" ACM SIGOPS operating systems review 41, no. 6 (2007): 205-220.\n\n[2] Stoica, Ion, Robert Morris, David Karger, M. Frans Kaashoek, and Hari Balakrishnan. \"Chord: A scalable peer-to-peer lookup service for internet applications.\" ACM SIGCOMM computer communication review 31, no. 4 (2001): 149-160.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)