arXiv CS open access

Nebula: Distributed Position-Independent Caching for LLM Serving

Yifei Liu et al. · arxiv_cs

arXiv CS · Papers

cloud distributed-computing parallel-computing

Modern LLM workflows, such as retrieval-augmented generation (RAG) and LLM agents, build long prompts from multiple independent text segments, making prefill a major source of computation. Reusing KV caches is therefore important for reducing serving costs and latency: distributed caching systems sp

Conceptio Open Archive

Analyze & explore related research in Conceptio

Connect this record directly into your research workflow or AI agent. Explore citations across open repositories, query full text, and export structured proof bundles.

Explore in Search →Connect via MCP / API ↗

N EBULA: Distributed Position-Independent Caching for LLM Serving

arXiv:2611.09474v1 [cs.DC] 6 Nov 2026

Yifei Liu1∗† Junbin Pan1∗ Junhao Hu3 Yang Liu2 Junyi Chen2 Juntong Wu3 Chen Chen2 Haiyuan Zhao1 Xiaoxu Chen1 Weihang Chen1 1 Xiaohongshu 2 Shanghai Jiao Tong University 3 Peking University

Abstract Modern LLM workflows, such as retrieval-augmented generation (RAG) and LLM agents, build long prompts from multiple independent text segments, making prefill a major source of computation. Reusing KV caches is therefore important for reducing serving costs and latency: distributed caching systems spread KV cache across a cluster to increase aggregate capacity, while position-independent caching (PIC) enables reuse of recurring segments under different prefixes. However, existing systems distribute KV caches but still rely on prefix caching (PC), while existing PIC methods enable position-independent reuse without cluster-wide resource management. We present N EBULA, the first distributed LLM serving framework to treat PIC segments as first-class citizens, enabling remote PIC reuse and parallel prefill. To track PIC’s fine-grained, asynchronous state changes, N EBULA combines optimistic accounting with event-driven updates to provide a timely and truthful cluster view for cache management and prefill scheduling. To accommodate diverse reuse patterns across workloads, N EBULA leverages cluster-wide ghost-hit feedback to automatically tune the allocation of shared cache capacity between PC and PIC. Finally, N EBULA incorporates queueing, computation, and KV transfer costs into a unified prefill completion time model to guide elastic parallelism adjustment and locality-aware compute placement. Across four models and four real-world RAG and agentic workloads, N EBULA reduces median TTFT by an average of 61.4% compared with the strongest existing baseline and recovers an average of 76.1% of the tokens missed by prefix caching.

(b) Nebula

Figure 1: Distributed PIC for a single request. Both plans start with the same cache placement and worker loads, with PIC segments A and B cached on different workers. (a) Workerlocal PIC reuses A but leaves remote B and an idle worker unused. (b) N EBULA reuses B across workers and computes C and D on separate workers while preserving prefix reuse. W1 combines the KV cache and processes query segment q.

(RAG) and long-horizon agents. RAG inserts retrieved documents into prompt templates [2, 4, 12, 28], while long-horizon agents extend their context with tool outputs, memory and skill files [7, 21, 32]. Prefilling these growing contexts requires substantial GPU computation and increases time-tofirst-token (TTFT). Reusing KV caches to avoid repeated prefill computation is therefore important for lowering serving costs and improving responsiveness. Distributed inference systems extend KV caching across the cluster. Mooncake [22], LMCache [11], and MemServe [5] support cross-node indexing, storage, and transfer, allowing requests to reuse KV generated on other nodes and benefit from aggregate cache capacity. Yet their distributed reuse still relies on strict prefix caching (PC): only content

Introduction

Large language model (LLM) serving is expanding beyond single-turn chat to support retrieval-augmented generation ∗ Both authors contributed equally to this work. † Yifei Liu is the corresponding author (liuyifei5@xiaohongshu.com).

that matches continuously from the beginning of a request can be reused. PC therefore cannot reuse a previously seen document or tool result independently when its preceding context changes. In parallel, position-independent caching (PIC) [6, 9, 13, 14, 26, 27, 31] expands the scope of reuse. Methods such as CacheBlend [31] and EPIC [6] cache semantically independent segments and combine their KV under a different prefix with correction or recomputation as needed. This matches the recombination of retrieved documents in RAG and the reuse of shared content in different agent contexts. Across six real-world RAG and agent workloads, our reuse breakdown shows that PIC can recover approximately 72.1% of the tokens missed by PC on average (§3.1). However, simply combining existing PIC algorithms with distributed inference systems does not realize the full capabilities of distributed PIC. Routers still match caches by prefix and cannot locate cached PIC segments across nodes; schedulers still treat each request as monolithic and cannot parallelize prefill of its cold segments across workers. Figure 1 illustrates the resulting missed opportunities for remote cache reuse and parallel prefill. We present N EBULA, the first distributed LLM serving framework to treat PIC segments as first-class citizens. N EB ULA enables remote PIC reuse and parallel prefill of uncached segments across workers while preserving PC semantics. Through a unified backend interface, N EBULA supports multiple PIC algorithms and decouples algorithm-specific KV processing from cluster-wide resource management. Building on this framework, we further introduce three designs, each addressing a distinct challenge posed by distributed PIC.

the target PC/PIC capacity ratio using cluster-wide ghost-hit feedback, which captures reuse demand after eviction. Capacity allocation thus adapts to the actual reuse patterns observed across the cluster (§6). C3: Balancing compute and transfer through elastic, locality-aware prefill scheduling. A distributed PIC request must both fetch cached KV and compute uncached segments. Placing computation on cache-affine nodes may cause load imbalance, while placing it on idle nodes may increase network traffic. Optimizing cache locality or load balance alone does not necessarily minimize the prefill completion time of a PIC request. N EBULA incorporates queueing, computation, and KV transfer costs into a unified prefill completion time estimate and uses a greedy search to select the best candidate execution plan. The prefill plans therefore dynamically adjust parallelism and compute placement as load and cache distribution change, accounting for both available compute resources and data locality (§7). We implement N EBULA on SGLang [33] and Dynamo [18], with support for PIC methods including CacheBlend [31], A3 [34], EPIC [6] and HYPIC [10]. We evaluate N EBULA with four diverse models on four real-world RAG and agentic workloads. N EBULA reduces median TTFT by an average of 61.4% compared with the strongest existing baseline and recovers an average of 76.1% of the tokens missed by prefix caching. N EBULA’s source code will be released at https://github.com/redai-studio/Nebula.

2 2.1

C1: Keeping the cluster view timely and truthful through optimistic, event-driven view synchronization. Distributed PIC can break a single request into hundreds of scheduling units whose states change asynchronously across workers, while routing decisions and actual execution are separated in time. Inferring cache state solely from scheduling decisions may report invalid cache hits, while relying solely on execution feedback may lead to redundant computation. N EBULA combines these complementary sources: the router immediately records expected cache locations and compute load upon dispatch, and workers confirm or correct these records through cache residency, eviction, and task completion events. This allows N EBULA to maintain an accurate and timely cluster view, providing a common basis for cache management and prefill scheduling (§5).

Background Prefix Caching at Scale

Prefix Caching. To reduce prefill computation and TTFT for long contexts, mainstream LLM serving systems, such as vLLM [8] and SGLang [33], reuse KV cache across requests with prefix caching (PC). Under causal attention, each token’s KV state depends on that token and its preceding context. PC therefore requires strict prefix matching: when a new request shares its first n tokens with an earlier request, it can reuse the corresponding KV cache directly with exact numerical equivalence. Once a prefix mismatch occurs, the KV cache from that point onward becomes immediately unusable. Distributed Caching Systems. In a serving cluster with multiple LLM instances, reusable KV cache may reside on different nodes and storage tiers, requiring efficient lookup and access during request execution. Mooncake [22], LMCache [11], and MemServe [5] support cluster-wide reuse through cache indexing, tiered storage, and KV transfers across nodes, with Mooncake and MemServe further considering cache location and compute load during request scheduling. TokenLake [29] extends prefix cache management to the segment level, while segment reuse still requires prefix matching.

C2: Balancing PC and PIC allocation through shared, selftuning cache management. Workloads differ in their PC and PIC reuse patterns: RAG documents recur under different prefixes, while successive agent interactions extend the same prefix. Uncontrolled competition between PC and PIC for shared cache space can cause cache pollution, while fixed quotas can strand cache capacity. N EBULA dynamically adjusts 2

Category Workload

A meaningful assessment of PIC’s incremental benefits for RAG and agent workloads must therefore account for what existing systems already achieve. Let hPC and hPIC denote the fractions of a request’s input tokens reusable through prefix caching and position-independent caching, respectively. In this theoretical matching analysis, a prefix is a special case of a segment at the beginning of the sequence, so hPIC ≥ hPC . We use two metrics to quantify PIC’s additional benefit over prefix caching:

PC% PIC% NPHR% PMRR%

RAG RAG RAG

ChatRAG-doc2dial [4, 12] 2.63 99.68 ChatRAG-QuAC [2, 12] 3.15 87.50 RAGPulse [28] 31.53 72.01

97.06 84.36 40.48

99.7 87.1 59.1

Agent Agent Agent

nebius-SWE-agent [1] τ-bench-Retail [32] ChatDev [21]

2.23 4.07 18.98

47.0 55.1 84.7

95.26 97.49 92.62 96.69 77.59 96.57

Table 1: Theoretical cache hit analysis of PC and PIC on RAG and agent workloads.

2.2

• Non-prefix hit rate (NPHR) = hPIC − hPC : the fraction of input tokens that miss prefix matching but hit positionindependent matching, or the absolute increase in hit rate provided by PIC.

Efficient Position-Independent Caching

Position-Independent Caching. Position-independent caching (PIC) relaxes strict prefix matching and allows semantically independent segments to be reused at arbitrary positions. The cached KV still depends on the segment’s original position and preceding context, so direct concatenation introduces numerical deviations. PIC methods typically use recomputation to reduce these deviations: CacheBlend [31] recomputes tokens with the largest KV deviations; A3 [34] identifies key tokens for recomputation from attention distributions; EPIC [6] uses attention sink patterns to statically select the first k tokens of each chunk for recomputation. HYPIC [10] further enables PIC for linear attention through transition matrices.

• Prefix-miss recovery rate (PMRR) = NPHR / (1 − hPC ): the fraction of prefix-missed tokens that PIC can reuse, directly reflecting how much computation can be further reduced after prefix caching has been fully exploited. We select six public workloads spanning RAG and agent scenarios. For RAG, ChatRAG-doc2dial [4, 12] and ChatRAGQuAC [2, 12] are conversational RAG workloads, and RAGPulse [28] is a public RAG serving trace. For agents, nebiusSWE-agent [1] is a coding agent trace, τ-bench-Retail [32] is a tool-use agent trace, and ChatDev [21] is a multi-agent software collaboration trace. As shown in Table 1, RAG and agent workloads exhibit markedly different reuse patterns. RAG requests concatenate independently retrieved texts after a system prompt, often leaving repeated content outside the shared prefix. ChatRAGdoc2dial and ChatRAG-QuAC have prefix hit rates of only about 3%, yet their NPHR reaches 97% and 84%, respectively, with most hits coming from non-prefix reuse. Even RAGPulse, with a higher prefix hit rate of 31.5%, has a PMRR of 59.1%. Agent requests grow over successive interactions, giving tool-use and coding workloads high prefix hit rates: 92.6% for τ-bench-Retail and 95.3% for nebius-SWE-agent, with NPHR of only 2% to 4%. Yet the dominance of prefix reuse does not mean that PIC has no value: for the less than 10% of input tokens that miss the prefix cache, PMRR is still 55.1% and 47.0% in these two workloads, respectively. A role-level breakdown further shows that environment observations account for 85.4% of the non-prefix reuse in nebius-SWE-agent, while tool-returned database records account for 89.5% in τ-bench-Retail. This means that even with such high prefix hit rates, nearly half of the remaining computation can still be saved by PIC. In the multi-agent workload ChatDev, content shared across agents appears at different positions, also creating considerable PIC reuse opportunities with a PMRR of 84.7%. Despite their different reuse patterns, both RAG and agent workloads can save a substantial fraction of prefill computation by adding PIC to existing PC.

System Gap. However, existing distributed caching systems are built on prefix caching, and none provides complete distributed support for PIC. CacheBlend implements PIC on top of LMCache but does not integrate it into distributed cache management. MEPIC [26] and MiniPIC [20] explore practical PIC implementations but do not consider distributed support. HYPIC is the closest work to ours, but it uses distributed computation only to accelerate cold prefill and does not address the new challenges that PIC introduces for distributed caching systems (§4.3).

Analysis

As discussed in §2, PIC can reuse non-prefix content that PC cannot, yet no existing system fully supports distributed PIC. Before diving into N EBULA design (§4), we first examine two questions: (i) How much additional reuse can PIC provide on top of prefix caching for RAG and agent workloads (§3.1)? (ii) Is deploying single-node PIC within existing distributed prefix caching systems sufficient to exploit the cluster’s cache and compute resources (§3.2)?

3.1

The Opportunity for PIC

PIC Benefit on Prefix Caching. Although PC yields low hit rates on RAG workloads, existing production systems already achieve cache hit rates above 90% on agent workloads. 3

Prefix

CHR (%)

Worker-local PIC

99.5 88.9

100

PIC upper bound 96.4

90.0

80.082.8

68.1

82.6 72.0

96.5

94.9

72.8

We present N EBULA, the first distributed LLM serving system to treat PIC segments as first-class citizens. Distributed PIC is more than introducing a new cache object: it entails joint, system-level optimization across view synchronization, cache management, and prefill scheduling. This section first presents the design principles (§4.1) and system architecture (§4.2), then outlines three new challenges posed by distributed PIC (§4.3). We then detail the three corresponding solutions: Optimistic, Event-Driven View Synchronization (§5), Shared, Self-Tuning Cache Management (§6), and Elastic, LocalityAware Prefill Scheduling (§7).

52.7

41.7 33.4

31.5

25 0

1.6

1.9

Doc2Dial

QuAC

RAGPulse

SWE

τ-bench

ChatDev

(a) Cache hit ratio. P50 9.5×

P99

10.2× 8.7×

TTFT (s)

P95

6.1×

6.6× 6.7×

4.1×

4.0× 1.6×2.1×

Doc2Dial

QuAC

RAGPulse

1.5×2.3×

SWE

τ-bench

4.1

Design Principles

ChatDev

(b) Tail TTFT of worker-local PIC.

Treat PIC segments as first-class citizens. Existing PIC works identify and reuse PIC segments only within individual workers, whereas existing distributed caching systems still manage prefix caches across nodes. Simply composing the two neither enables cross-node reuse of cached PIC segments nor allows independently computable PIC segments to be offloaded to idle workers (§3.2). A PIC segment must therefore be more than a piece of KV state internal to the inference engine. It must become a first-class distributed cache object and the common unit of operation for view synchronization, cache management, and prefill scheduling. Each PIC segment can then be independently indexed, placed, transferred, reused, or computed across the cluster, extending PIC from a worker-local optimization to a cluster-wide capability.

Figure 2: Limitations of deploying PIC-enabled workers behind a prefix-cache-aware router. (a) Worker-local PIC improves cache hit ratio (CHR) over PC but remains below the ideal PIC upper bound. (b) Worker-local PIC exhibits substantial tail TTFT across the same workloads.

3.2

N EBULA Overview

From PIC to Distributed PIC

The Gap between PIC and Distributed PIC. To assess the gap between the existing system and the ideal state, we first construct a direct-composition strawman by deploying PICenabled workers behind Dynamo, an existing prefix-cacheaware router. On the one hand, this setup lacks remote cache reuse: it cannot locate cached PIC segments on other nodes, so it may recompute content that could instead be fetched over the network for reuse. On the other hand, this setup lacks parallel prefill: it cannot offload independently computable PIC segments to idle nodes, so it may leave available cluster compute resources unused and suffer from high TTFT. We deploy the worker-local PIC strawman in a cluster with seven prefill workers and one decode worker, and replay the six workloads at 8 requests/s in their original order from a cold cache. Figure 2 (a) shows that worker-local PIC improves CHR over PC, yet remains 10.6–56.7 percentage points below the ideal PIC upper bound across the six workloads. The gap is largest on ChatRAG-QuAC, where worker-local PIC achieves only 33.4% CHR against an upper bound of 90.0%. Figure 2 (b) further shows substantial tail TTFT: P99 is 2.1– 10.2× P50, reaching 9.5× on ChatRAG-doc2dial and 10.2× on ChatRAG-QuAC. Because each request remains bound to one worker, the strawman cannot use idle workers to accelerate the prefill of its uncached PIC segments. These observations motivate a distributed PIC system that can fully exploit cluster-wide cache and compute resources.

Complement prefix caching rather than replace it. The relative benefits of PC and PIC vary across workloads (§3.1), while rebuilding prefix cache with recomputation-based PIC still incurs overhead [6, 10, 31, 34]. A distributed PIC framework should therefore preserve existing prefix-caching semantics and add PIC as a complementary capability. The two cache types should share the same storage and transfer infrastructure while retaining their distinct matching semantics. Make PIC algorithms pluggable. Different PIC algorithms handle segment reuse and recomputation in different ways (§2.2). A distributed PIC framework should therefore not be tied to a single algorithm. Instead, it should integrate existing PIC algorithms as pluggable backends through a unified interface that decouples cluster-wide cache management and prefill scheduling from algorithm-specific KV processing, enabling single-node PIC algorithms to operate in distributed settings. N EBULA leaves KV reuse and recomputation policies, including their accuracy tradeoffs, to the PIC backend. It adapts different PIC backends for distributed execution and focuses on cluster-wide resource management. 4

Nebula Router · Control Plane RAG / Agents

Request Interface

Cache Manager (§6)

Cluster View (§5)

Prefill Scheduler (§7)

Execution plan

Cache reuse

Combine prefill

Scatter prefill

Data Plane Worker 1

Worker c

Worker N

Inference engine

PIC backend

PIC

Commands

PIC

KV transfer

Figure 5: Execution timeline for one PIC request.

Application Interface and PIC Segments. N EBULA lets applications define where PIC is used. The application partitions each request into text segments: content enclosed by the PIC tags <pic>...</pic> forms an application-defined PIC segment, while each maximal unmarked span forms a regular segment. The interface removes these tags before tokenization. Unlike PIC segments, regular segments cannot be independently prefilled, cached, transferred, or reused across the cluster. Instead, they are reused through the prefix cache or recomputed in the request context on a prefix-cache miss. Figure 4 shows example segmentations for RAG and agent requests. RAG applications mark retrieved documents as PIC segments in their request templates, while agent applications mark tool outputs, environment observations, and cross-agent messages as PIC segments. The remaining unmarked content forms regular segments. System prompts typically form stable request prefixes and can be reused through prefix caching, so they remain unmarked in these examples.

PIC

View updates

Figure 3: N EBULA system architecture. Inference engine Inference engine

RAG application input System: You are a customer-support assistant. User: <pic>A damaged product PC PC may be returned within 30 days.</pic> <pic>Refunds use the original payment method.</pic> Question: How long do I have to return a damaged product? Agent application input System, user, assistant: coding instructions and conversation history Tool: <pic>[parser.py] def parse_config(path): ...</pic> Tool: <pic>[SKILL.md] Normalize keys before validation.</pic> User: Update the parser to follow these guidelines.

Figure 4: Application-defined text segmentation.

4.2

System Architecture

Request lifecycle. When a request arrives, the control plane first performs prefix matching over the complete request, then position-independent matching for PIC segments not covered by the prefix hit. The Prefill Scheduler uses the matching results and worker load to construct an execution plan. The plan specifies a worker for each PIC segment, either to supply cached KV or to perform prefill, and a combine home, where the required KV is gathered to complete the request’s prefill. We detail plan generation in §7. Figure 5 illustrates execution through three types of operations. Scatter prefill independently computes cold PIC segments on assigned workers and transfers their generated KV to the combine home when needed. Cache reuse makes matched PC/PIC KV available at the combine home, transferring remotely cached KV when needed. Combine prefill invokes the PIC backend at the combine home to reuse PIC segments, compute the remaining content, and perform necessary recomputation. Scatter workers can begin computation once they receive their tasks, but transfer generated KV via direct GPU writes only after receiving destination GPU addresses from the combine home. Scatter prefill, cache reuse, and control message delivery can overlap, while combine

Framework components. As shown in Figure 3, N EBULA consists of a control plane and a data plane. The control plane makes cluster-wide cache and compute decisions, and the data plane executes them. The control plane is implemented by a cluster-level router and contains three components: • Cluster View maintains cluster-wide cache state and load state, providing a unified view for cache management and prefill scheduling (§5). • Cache Manager uses this view to allocate shared cache capacity between PC and PIC (§6). • Prefill Scheduler uses the same view to construct execution plans (§7). The data plane comprises two PIC-enhanced components: • Cache Pool retains existing prefix cache storage and transfer capabilities and extends them to PIC segments. • Inference Workers retain their existing model execution paths and invoke specific PIC algorithms through a unified backend interface. 5

prefill begins only after all required KV is available at the combine home. Once prefill completes, N EBULA hands off the request and its KV state to a decode worker through the standard PD-disaggregated serving path. N EBULA leaves the decode path unchanged, focusing on reducing TTFT through prefill optimization.

Challenges

P95

P99

P50

P95

P99

106 35 11

112 127 13

113 203 15

334 536 319

670 773 521

1,190 939 521

nebius-SWE-agent τ-bench-Retail ChatDev

31 14 22

253 34 65

413 44 73

69 93 818

1,032 1,240 2,253

1,431 1,240 2,780

Invalid hit tokens (k)

C1: Keeping the Cluster View Timely and Truthful under Fine-Grained Reuse. Distributed PIC substantially increases the number of independently scheduled units whose cache and compute states change asynchronously across workers, while routing decisions and actual execution are separated in time. An inaccurate view can cause invalid cache hits, whereas delayed updates can lead to redundant computation. The cluster view must therefore be both timely and truthful to support cache management and prefill scheduling (§5).

Optimistic Accounting 750.4 600 300 0

176.9 12.6

1.5

RAGPulse

τ-bench

(a) Invalid hits

Event-Driven Updates 1,612.0 1200 600 0

3.6

275.5

RAGPulse

64.4 τ-bench

(b) Repeated computation

Figure 6: Limitations of Optimistic Accounting and EventDriven Updates used in isolation: (a) invalid hit tokens and (b) repeated computation tokens on RAGPulse and τ-benchRetail. subsequent requests arrive, while cache insertions and evictions occur asynchronously across workers. We construct two strawmen for distributed-PIC cache-directory maintenance based on existing viewsynchronization mechanisms: (i) Optimistic Accounting infers PIC cache state from scheduling decisions, worker capacity, and an LRU model, following the SGLang router [24] and vLLM router [25]. (ii) Event-Driven Updates maintains the PIC cache index using worker-reported cache events, following Dynamo [18] and llm-d [15]. However, the optimistic strawman exposes assigned work immediately but can report invalid cache hits when its predicted PIC-segment locations drift from actual residency. The event-driven strawman does not assume cache availability before worker confirmation, which can lead to redundant prefill of the same segment across requests. We compare the two variants using Qwen3.5-35B-A3B on a 7P1D cluster, replaying the RAGPulse and τ-benchRetail traces at 40 QPS. We measure invalid hit tokens, where expected holders have neither usable KV nor earlier in-flight work, and repeated computation tokens, where directory misses trigger redundant segment prefill despite earlier in-flight work. Figure 6 shows that Optimistic Accounting incurs 59.4× and 114.3× as many invalid hit tokens as EventDriven Updates on the two workloads, respectively. Conversely, Event-Driven Updates incurs 77.3× and 25.0× as many repeated computation tokens. Therefore, under fine-grained PIC reuse, view synchronization cannot rely on router-side speculation or worker-side confirmation alone. It must address both view drift and delayed

C2: Balancing PC and PIC Allocation under a Shared Budget. PC and PIC share finite cache capacity, but their relative reuse demand varies across workloads. Uncontrolled competition between them can crowd out frequently reused content, while fixed partitions can leave capacity idle for one type even as the other runs out of space. Cache management must therefore dynamically coordinate PC and PIC allocation as cluster-wide reuse demand changes (§6). C3: Balancing Compute and Transfer under Shifting Load. Remote cache reuse incurs network transfer delays, while parallel prefill must wait for the slowest computation to finish. Under changing load, placing computation on cacheaffine nodes may increase queueing delays, while placing it on less-loaded nodes may increase KV transfer costs. Scheduling must therefore balance compute and transfer when jointly selecting compute placement and parallelism (§7).

5.1

P50

ChatRAG-doc2dial ChatRAG-QuAC RAGPulse

Table 2: Distributions of segment counts and lengths across RAG and agent workloads.

The framework above extends PIC from a single worker to the entire cluster. However, making the system efficient remains non-trivial: distributed PIC introduces three new system challenges in view synchronization, cache management, and prefill scheduling.

Length (tokens)

Workload

Repeated tokens (k)

4.3

Segments/request

Optimistic, Event-Driven View Synchronization Problem Analysis

Distributed PIC divides each request into multiple PIC segments that can be independently placed, transferred, and computed. This shift from request-level to segment-level scheduling increases the number of scheduling units by 11–106× at the median and up to 413× at P99 (Table 2). Dispatched segment computations may still be queued or running when 6

Unified LRU 0.45 0.40

Fixed Partition

0.435 0.373

0.367 0.338

0.35 DS-V2-Lite ChatRAG

Qwen3.5-35B RAGPulse

(a) TTFT

CHR (%)

P50 TTFT (s)

Nebula Nebula Router Router

80.68 82.79

60.55

60 DS-V2-Lite ChatRAG

57.40

Qwen3.5-35B RAGPulse

(b) Cache hit ratio

Figure 8: Cache allocation trade-off: (a) median TTFT and (b) token-weighted cache hit ratio. Total

queued or running. The router releases a reservation only after confirming that the task has completed or will not execute, and deduplicates completion reports so that each reservation is released at most once.

512 128

Shared, Self-Tuning Cache Management

Figure 7: View synchronization in N EBULA.

6.1 updates, providing a basis that is both timely and truthful for cache management and prefill scheduling.

5.2

Problem Analysis

Recompute-based PIC methods may store different KV representations of the same segment in PC and PIC, creating competing demands for finite cache capacity. The relative demand for the two cache types depends on workload reuse patterns (§3.1)— doc2dial and QuAC reuse RAG documents under different prefixes, whereas nebius-SWE-agent and τbench-Retail repeatedly extend the same prefix; RAGPulse and ChatDev exhibit both patterns. We construct two strawmen for PC–PIC cache allocation based on existing capacity-management policies: (i) Unified LRU, as used by MiniPIC [20], manages PC and PIC in a shared cache pool on each worker without cache-type quotas and selects eviction victims by access recency. (ii) Fixed Partition, following HYPIC’s separate capacity budgets and per-pool LRU [10], divides capacity between PC and PIC at a preset ratio, with no borrowing between the two pools. However, Unified LRU allocates shared capacity solely through recency-based eviction, which may allow one cache type to crowd out frequently reused content from the other. Fixed Partition limits this interference but cannot adapt to changing demand, potentially leaving capacity idle in one pool while the other repeatedly evicts entries for lack of space. We compare the two policies on a 7P1D cluster using DeepSeek-V2-Lite with ChatRAG-QuAC at 16 QPS and Qwen3.5-35B-A3B with RAGPulse at 40 QPS. Figure 8 shows that Fixed Partition achieves a higher cache hit ratio on ChatRAG (82.79% versus 80.68%), while Unified LRU wins on RAGPulse (60.55% versus 57.40%). Neither policy dominates across these two configurations. Therefore, under a shared cache budget, the Cache Manager cannot rely solely on a unified eviction policy or fixed quotas to allocate capacity. Instead, it must self-tune the PC and PIC capacity shares as cluster-wide reuse demand changes, improving cache reuse under finite capacity.

Our Solution

The key insight of N EBULA is to combine the router’s immediate scheduling decisions with workers’ execution feedback. View Organization. The cluster view of N EBULA consists of a cache view and a load view (Figure 7). The cache view retains the existing PC prefix index and organizes the PIC map by content hash. For each PIC segment, it records its worker locations, storage tiers, and whether each record has been confirmed by a worker-side event. The load view records each task’s target worker and reserved compute work and aggregates these reservations into each worker’s outstanding compute load. Optimistic Accounting and Event-Driven Updates. When dispatching an execution plan, the router immediately records expected PIC-segment locations in the cache directory and reserves compute load for scatter prefill and combine prefill tasks. Subsequent requests can thus identify and await matching in-flight results on the assigned workers, avoiding redundant prefill. During execution, workers send incremental events to the router: cache-store events confirm the corresponding locations, cache-eviction events remove invalid locations, and compute-completion reports release the corresponding tasks’ load reservations. N EBULA assigns each unconfirmed cache-location entry a TTL and removes it upon expiration. When a cache-store event arrives, the corresponding location becomes confirmed and is no longer subject to the TTL. Late cache-store events can still re-register the corresponding locations. Unlike unconfirmed cache-location entries, load reservations do not expire on timeout, because their tasks may still be 7

Locality-aware 3000

3071.37

1500 481.51

RAGPulse

Load-aware

3363.23

573.71

τ-bench

(a) Network traffic

1.595

1.586

Compute CV

Network traffic (GiB)

Nebula Cache Manager

1.2 0.6 0.0

0.797 0.346

RAGPulse

τ-bench

(b) Compute imbalance

Figure 10: Locality–load trade-off on RAGPulse and τ-benchRetail. Locality-aware reduces network traffic, while Loadaware lowers the CV of cumulative prefill tokens across workers. Worker-Side Soft Allocation. All prefill workers use the same target ratio. Let RPC and RPIC denote the local cache occupancy of PC and PIC, respectively. If RPC > p RPC + RPIC , (2)

Figure 9: Self-tuning cache management in N EBULA.

6.2

Our Solution

The key insight of N EBULA is to use cluster-wide reuse feedback to dynamically adjust the shares of PC and PIC.

the worker prioritizes PC eviction; otherwise, it prioritizes PIC eviction. Updating p changes only the cache-type priority for subsequent reclamation and triggers no immediate eviction. For tiered storage, N EBULA maintains the four queues separately for each storage tier and adjusts its PC/PIC target shares using that tier’s reuse feedback. Workers independently apply soft allocation at each tier based on its target shares.

Cluster-Wide Reuse Feedback. Inspired by ARC’s adaptation between recency and frequency [16], N EBULA uses revisits to evicted cache entries to identify which cache type needs more space. As shown in Figure 9, the router maintains four queues: TPC and TPIC track PC and PIC entries present in the cluster, while BPC and BPIC track previously cached entries no longer present in the cluster. All four queues store only identifiers, not cached data. When an entry appears in the cluster view, the router adds it to the corresponding T queue and removes its history from the corresponding B queue. When the cluster view no longer reports any available holder for an entry, the router moves it from T to B. Reuse feedback follows the prefix-first principle (§4.1). The router first matches existing prefix caches in TPC , then checks BPC to retain revisit feedback for missing prefix caches, even when PIC can still serve the same content. It then checks TPIC and BPIC in order to assess PIC reuse demand. Each token in a request contributes to at most one feedback category.

7 7.1

GPC − GPIC , GPC + GPIC pnew = clip[0,1] [p + 0.01g] .

Problem Analysis

Distributed PIC allows cold PIC segments to be prefilled in parallel across workers, while PC and PIC may reside on different workers. Under changing cluster load, scheduling must jointly select each cache’s reuse path, the combine home and the placement of cold PIC-segment computation so that the required KV becomes ready at the combine home as early as possible for the subsequent combine prefill. Building on existing cache-aware and load-balancing approaches, we construct two strawman schedulers for distributed PIC: (i) Locality-aware selects the combine home with the most local PC/PIC hits, computes cold PIC segments there, and fetches the remaining PIC hits from other workers. (ii) Load-aware assigns scatter and combine prefill tasks to workers using longest-processing-time-first (LPT) scheduling and transfers both cached and generated KV from remote workers to the combine home. However, Locality-aware may increase queueing delays by placing computation on a cacheaffine but busy worker. Load-aware may incur higher transfer costs when fetching cache hits or returning newly generated KV. Having more local cache hits or more balanced computation does not necessarily lead to earlier prefill completion. We compare the two schemes using Qwen3.5-35B-A3B on a 7P1D cluster, replaying the RAGPulse and τ-benchRetail traces at 8 QPS. We measure total network traffic and

Self-Tuning Capacity Shares. Let GPC and GPIC denote the token counts covered by ghost revisits for the two cache types. Let p ∈ [0, 1] be the global target soft share for PC, with 1 − p for PIC. The router updates this share over request windows: g=

Elastic, Locality-Aware Prefill Scheduling

(1)

More PC ghost tokens increase p, while more PIC ghost tokens decrease it. N EBULA initializes p to 0.5 and updates it every U = 16 requests, changing it by at most one percentage point per update. After each update, the router asynchronously broadcasts the new allocation ratio to all prefill workers. 8

assigned to worker w. For cache hits Sw (π) ∩ Hw , N EBULA reuses the KV already stored at that worker; for cache misses Sw (π) \ Hw , it performs scatter prefill there. We estimate the prefill completion time of plan π as:

Algorithm 1 Greedy Prefill Planning Require: S , W , {Hw , Qw }, {Pi }, cache-hit sources, Tb(·) Ensure: Execution plan πbest S 1: cold ← sort S \ w∈W Hw by decreasing Pi 2: Π ← ∅ 3: for each c ∈ W do 4: a ← empty mapping 5: for each i ∈ S do 6: a(i) ← c if i ∈ cold, else its cache source 7: π ← (c, a) 8: for each i ∈ cold do 9: if W \ {c} = ∅ then break 10: w ← arg min [Qv + Pv (π)]

Tb(π) = max [Qw (π) + Pw (π) + Dw (w → c; π)] +C. w∈W

The estimate sums queueing Qw (π), computation Pw (π), and transfer time Dw (w → c; π) at each worker, takes the maximum across workers as the estimated KV-ready time, and adds the request’s combine prefill work C. In this model, matched prefix KV is also represented as cached segments and included in the transfer cost. All terms are normalized to equivalent prefill tokens: ( Qw , Sw (π) \ Hw ̸= ∅, Qw (π) = 0, otherwise,

v∈W \{c}

a′ ← copy(a) a′ (i) ← w π′ ← (c, a′ ) if Tb(π′ ) < Tb(π) then a ← a′ π ← π′ Π ← Π ∪ {π} 18: πbest ∼ Uniform arg minπ∈Π Tb(π) 19: return πbest 11: 12: 13: 14: 15: 16: 17:

Pw (π) =

Dw (w → c; π) = d(w → c)

(5)

∑ Pi .

Here, Pi is the token count of segment i. The per-worker queueing and scatter-computation terms arise only when a worker is assigned a cache miss. The transfer term covers both cache hits and newly computed KV. The coefficient d(w → c) is obtained through offline profiling: it is the pertoken KV transfer time from worker w to worker c, normalized by the per-token prefill time, with d(c→ c) = 0. The request’s combine prefill workload C, which includes computation of the remaining content and necessary PIC recomputation, is constant across candidate plans. Combine prefill receives the highest scheduling priority once its required KV is ready, so the estimate omits its queueing delay. Greedy Plan Generation. Using this prefill completion time estimate, N EBULA greedily optimizes the execution plan to minimize completion time (Algorithm 1). The algorithm first enumerates available combine homes c and constructs an initial plan π for each: cache hits are assigned to the source workers, and all cold PIC segments are assigned to c (lines 3–7). This initial assignment preserves cluster-wide cache reuse while avoiding KV return traffic from cold PIC-segment computation. For each cold PIC segment in decreasing order of length, the algorithm constructs a candidate plan π′ by reassigning it to the worker w ̸= c minimizing Qw + Pw (π) (lines 8–13). The search holds Qw fixed, while updating Pw (π) after each accepted move. Load guides candidate selection, but a move is accepted only if Tb(π′ ) < Tb(π) (lines 14–16). Otherwise, the plan remains unchanged and the search proceeds to the next segment. After searching all candidate combine homes, it returns a plan with the lowest estimated completion time (lines 17–19).

The key insight of N EBULA is to jointly account for queueing, computation, and KV transfer when estimating a distributed PIC request’s prefill completion time. Estimating Prefill Completion Time. N EBULA constructs execution plans in request arrival order (FIFO). Each plan consists of a combine home c and a mapping a from the request’s PIC segments to workers: a:S →W,

Pi ,

i∈Sw (π)

Our Solution

π = (c, a),

∑

i∈Sw (π)\Hw

quantify compute imbalance using the population coefficient of variation (CV) of cumulative prefill tokens across prefill workers. As Figure 10 shows, Load-aware transfers 6.4× and 5.9× as much data as Locality-aware on the two workloads, respectively, but reduces compute CV by 4.6× and 2.0×. Therefore, under changing request load and cache distribution, prefill scheduling cannot prioritize cache locality or load balance alone. Instead, it must jointly consider compute load and KV transfer costs when selecting placement and parallelism to minimize prefill completion time.

7.2

(4)

c∈W,

(3)

where S is the request’s PIC segment set and W is the cluster’s worker set. To estimate the completion time of plan π, N EBULA uses the cache and load state in the cluster view. Here, Hw denotes the set of segments cached at worker w, and Qw is its total outstanding compute load, including scatter and combine prefill. Qw is measured in tokens and excludes the current request. Let Sw (π) = {i ∈ S | a(i) = w} denote the segments 9

P50 TTFT (s)

SGLang + Dynamo

Local-PIC + Dynamo 1.5

Nebula

1.5

1.0

0.5

0.0

QPS (a) ChatRAG / CacheBlend DeepSeek-V2-Lite

QPS (b) RAGPulse / HYPIC Qwen3.5-35B-A3B

1.5

0.0

QPS (c) τ-bench / EPIC Mistral-7B

QPS (d) ChatDev / A3 Qwen3-30B-A3B

Figure 11: End-to-end median TTFT versus QPS: (a) ChatRAG with DeepSeek-V2-Lite and CacheBlend, (b) RAGPulse with Qwen3.5-35B-A3B and HYPIC, (c) τ-bench with Mistral-7B and EPIC, and (d) ChatDev with Qwen3-30B-A3B and A3 . SGLang + Dynamo 100

CHR (%)

100 50 0

Local-PIC + Dynamo 100

50 2

QPS (a) ChatRAG / CacheBlend DeepSeek-V2-Lite

Nebula

PIC upper bound 100

50 2

50 10

QPS (b) RAGPulse / HYPIC Qwen3.5-35B-A3B

QPS (c) τ-bench / EPIC Mistral-7B

QPS (d) ChatDev / A3 Qwen3-30B-A3B

Figure 12: End-to-end cache hit ratio versus QPS, with the same configurations as Figure 11.

CDF

SGLang + Dynamo 1.00 P99 0.75 0.50 0.25 0.00 −1 10

15.38× 299.60× QPS=6 10

TTFT (s) (a) ChatRAG / CacheBlend DeepSeek-V2-Lite

1.00 P99 0.75 0.50 0.25 0.00

Local-PIC + Dynamo 1.00 P99 0.75 0.50 0.25 QPS=6 0.00 1 −1 10 10

Nebula

4.18× 6.47×

TTFT (s) (b) RAGPulse / HYPIC Qwen3.5-35B-A3B

37.20× 30.25× QPS=30 10

1.00 P99 0.75 0.50 0.25 0.00 −1 10

TTFT (s) (c) τ-bench / EPIC Mistral-7B

11.04× 35.28× QPS=8 10

TTFT (s) (d) ChatDev / A3 Qwen3-30B-A3B

Figure 13: End-to-end TTFT CDFs, with the same configurations as Figure 11.

Implementation

ports. Models. We evaluate four models: DeepSeek-V2-Lite [3], Qwen3.5-35B-A3B [23], Mistral-7B [17], and Qwen3-30BA3B [30]. All models use seven prefill workers and one decode worker (7P1D), with one GPU per worker (TP1). We run DeepSeek-V2-Lite with CacheBlend, Qwen3.5-35B-A3B with HYPIC, Mistral-7B with EPIC, and Qwen3-30B-A3B with A3 .

We implement N EBULA on SGLang [33] and Dynamo [18], reusing SGLang’s radix tree and tiered storage infrastructure and Dynamo’s cluster orchestration. On the workers, we extend SGLang’s forward execution path to support CacheBlend [31], A3 [34], EPIC [6] and HYPIC [10], and adapt its storage pool allocation and indexing to manage PIC segments across storage tiers. On the router, we extend Dynamo’s cluster directory to support cache routing and prefill scheduling for distributed PIC (§4.2). We use NIXL [19] for efficient point-to-point transfers of PIC between workers across storage tiers. Our implementation comprises approximately 19K lines of code.

Evaluation

9.1

Setup

Workloads. We use four public RAG and agent workloads: ChatRAG-QuAC [2,12] for conversational RAG, RAGPulse [28] for RAG serving, τ-bench-Retail [32] for tool-using agents, and ChatDev [21] for multi-agent software development. Table 1 summarizes the theoretical cache-reuse breakdown for these workloads, while Table 2 reports the distributions of segment counts and lengths. We preserve the original request order and replay each trace with Poisson arrivals at varying rates. Since PIC targets TTFT reduction, we limit each request to one output token while retaining one decode worker to preserve prefill–decode disaggregation deployment.

Hardware. We run our experiments on two identical servers, each equipped with four NVLink-connected NVIDIA H20-3e GPUs, two 48-core Intel Xeon Platinum 8575C CPUs, 1 TiB of host memory, and four 200 Gbps RDMA-capable Ethernet

Methods. We compare three configurations: (i) SGLang + Dynamo combines SGLang [33] workers with Dynamo’s prefix-cache-aware router [18], representing a common pro10

P50 TTFT (s)

0.4

0.2 8

300

32 40

150 0

Nebula Labels: QPS

24 32

40 24 16

400

QPS

40 8

800

Invalid hit tokens (k)

(a) RAGPulse.

End-to-end performance

Event-Driven Updates

0.3 0.2 8

Repeated tokens (k)

Optimistic Accounting

P50 TTFT (s)

9.2

Event-Driven Updates

Repeated tokens (k)

Optimistic Accounting

duction deployment; (ii) Local-PIC + Dynamo is the directcomposition strawman described in §3.2, deploying PICenabled workers behind Dynamo without remote cache reuse or parallel prefill of PIC segments; and (iii) N EBULA integrates our three system designs to support remote PIC reuse and parallel prefill. Component experiments vary the mechanism under study while holding the remaining configuration fixed. Unless otherwise specified, each configuration runs from a fresh cluster without warmup.

32 40 24

1600 800 0

8 0

QPS

We evaluate N EBULA’s end-to-end performance using the four real-world workloads and four models described in §9.1.

Nebula Labels: QPS 16 8 8

32 40 24 24 32 40 16 100

200

Invalid hit tokens (k)

(b) τ-bench-Retail.

Figure 14: View synchronization at different request rates. The left plots show median TTFT, while the right plots compare invalid hit and repeated computation token counts.

Median and tail TTFT. Figure 11 shows that N EBULA achieves the lowest median TTFT across all measured settings. Across these settings, N EBULA reduces median TTFT by an average of 61.4% and 76.7% relative to Local-PIC + Dynamo and SGLang + Dynamo, respectively. At the highest tested rate for each workload, its median TTFT is 0.24, 0.79, 0.18, and 0.24 s for ChatRAG, RAGPulse, τ-bench-Retail, and ChatDev, respectively, compared with 1.26, 2.39, 3.64, and 9.57 s for Local-PIC + Dynamo and 75.73, 2.71, 8.79, and 8.46 s for SGLang + Dynamo. The results demonstrate the end-to-end benefits of jointly supporting remote cache reuse and parallel prefill beyond worker-local PIC alone.

9.3

View Synchronization

Invalid hits and repeated computation. We compare N EB ULA with Optimistic Accounting and Event-Driven Updates described in §5.1, varying only the PIC directory maintenance mechanism. Using Qwen3.5-35B-A3B, we replay the RAGPulse and τ-bench-Retail traces at different request rates. N EBULA uses a 5 s TTL for unconfirmed entries. Figure 14 shows that N EBULA achieves the lowest median TTFT on both workloads. At 40 QPS, it reduces median TTFT by 18.9% on RAGPulse and 14.9% on τ-bench-Retail relative to Optimistic Accounting. Relative to Event-Driven Updates, the reductions are 5.4% and 19.5%, respectively. At 40 QPS, N EBULA reduces the number of invalid hit tokens by 98.4% on RAGPulse and 100% on τ-bench-Retail relative to Optimistic Accounting. Relative to Event-Driven Updates, it reduces the number of repeated computation tokens by 96.1% and 95.1%, respectively.

We also report the TTFT CDF in Figure 13 at 6, 6, 30, and 8 QPS for ChatRAG, RAGPulse, τ-bench-Retail, and ChatDev, respectively. At P99, N EBULA reduces TTFT by 93.5%, 76.1%, 97.3%, and 90.9% relative to Local-PIC + Dynamo on these workloads, respectively. Relative to SGLang + Dynamo, the reductions range from 84.6% to 99.7%. TTFT-constrained goodput. We measure goodput as the number of successful requests meeting the TTFT SLO divided by the time from the first request’s start to the last request’s completion. With a 1 s TTFT SLO, N EBULA achieves 11.66 requests/s on ChatRAG at 12 QPS, compared with 1.68 requests/s for Local-PIC + Dynamo.

9.4

Cache Management

Cache capacity management variants. We compare N EB ULA with Unified LRU and Fixed Partition from §6.1, holding view synchronization and prefill scheduling fixed. We run Qwen3.5-35B-A3B on RAGPulse and Qwen3-30B-A3B on ChatDev at different request rates, both on a 7P1D cluster with TP1. Fixed Partition allocates half of the cache capacity to PC and half to PIC. In this experiment, we use the first 800 requests as warmup and report metrics over the remaining requests. Figure 15 shows that N EBULA achieves the lowest TTFT and highest CHR. On RAGPulse at 48 QPS, N EBULA increases CHR by 4.32 and 4.88 percentage points and reduces median TTFT by 11.5% and 14.7% relative to Unified LRU

Cache hit ratio. We measure Cache Hit Ratio (CHR) as the total number of input tokens served from cache divided by the total number of input tokens. Figure 12 shows that N EBULA achieves the highest CHR across all measured settings. At the highest tested rates, its CHRs are 84.82%, 58.99%, 93.67%, and 93.17% for ChatRAG, RAGPulse, τ-bench-Retail, and ChatDev, respectively, exceeding Local-PIC + Dynamo by 19.48–67.23 percentage points. Compared with SGLang + Dynamo, N EBULA recovers 84.7%, 42.1%, 86.3%, and 91.2% of the tokens missed by prefix caching on ChatRAG, RAGPulse, τ-bench-Retail, and ChatDev, respectively. 11

QPS

90 85

Figure 15: Cache management policies versus QPS for (a) Qwen3.5-35B-A3B on RAGPulse and (b) Qwen3-30B-A3B on ChatDev. U = 32

1000

2000

Feedback requests (a) Qwen3.5 / RAGPulse

3000 0

500

CHR (%) U

1000

52.5

(a) Qwen3.5 / RAGPulse

90.0

160 150 8

87.5 85.0

(b) Qwen3 / ChatDev

Locality-aware

0.5 0

U = 64

1.0

0.0

55.0

Figure 17: Effect of the update window U: median TTFT and CHR for (a) Qwen3.5-35B-A3B on RAGPulse and (b) Qwen3-30B-A3B on ChatDev. Dashed lines show the two baselines, which do not depend on U. P50 TTFT (s)

PC share p

U = 16

Nebula

50.0 8

QPS

(b) Qwen3 / ChatDev

U=8

122.5

QPS

(a) Qwen3.5 / RAGPulse

200 150

CHR (%)

250

125.0

CHR (%)

Fixed Partition

1500

Load-aware

0.4 0.2 8

Feedback requests (b) Qwen3 / ChatDev

Network traffic (GiB)

Unified LRU

P50 TTFT (ms)

Nebula

P50 TTFT (ms)

200

QPS P50 TTFT (ms)

Fixed Partition

CHR (%)

P50 TTFT (ms)

Unified LRU 400

Nebula 32

3000

40 32

1500 0

QPS

Labels: QPS 24 16 8 24 16 8

0.01

32 16

24 8

0.1

Compute CV

(a) RAGPulse.

Figure 16: Trajectory of the PC target soft share p under different update windows U for (a) Qwen3.5-35B-A3B on RAGPulse and (b) Qwen3-30B-A3B on ChatDev.

and Fixed Partition, respectively. On ChatDev at 12 QPS, the corresponding CHR gains are 5.48 and 7.37 percentage points, with median TTFT reductions of 20.8% and 23.4%.

Load-aware

0.50 0.25 8

Network traffic (GiB)

P50 TTFT (s)

Locality-aware

Nebula

32 40 4000 40 24 8 2000 0

QPS

Labels: QPS 32 24 16 8 32 16 24 40 16 8

0.1

Compute CV

(b) τ-bench-Retail.

Figure 18: Prefill scheduling at different request rates. The left plots show median TTFT, while the right plots compare total NIXL TX payload and compute CV.

Update-window sensitivity and capacity-share trajectory. We next study the update-window sensitivity and how the update window affects the shares of PC and PIC. We run Qwen3.5-35B-A3B on RAGPulse at 12 QPS and Qwen330B-A3B on ChatDev at 6 QPS, varying the update window U over 8, 16, 32, and 64 requests.

9.5

Prefill Scheduling

Traffic and Load Balance. We compare N EBULA with the Locality-aware and Load-aware strawmen from §7.1. We deploy Qwen3.5-35B-A3B and replay the RAGPulse and τbench-Retail traces at different request rates. All schedulers support remote PIC reuse. Figure 18 shows that N EBULA achieves the lowest median TTFT on both workloads at 24–40 QPS. At 40 QPS, it reduces median TTFT by 21.4% and 48.9% relative to Locality-aware, and by 21.4% and 19.8% relative to Load-aware, on RAGPulse and τ-bench-Retail, respectively. We measure total NIXL TX payload and the population CV of cumulative prefill tokens across prefill workers. At 40 QPS, N EBULA reduces traffic by 38.1% and 12.3% relative to Load-aware, and compute CV by 93.6% and 90.3% relative

Figure 16 shows how the PC target share p evolves under different update windows. On RAGPulse, p approaches zero at the maximum adjustment rate, consistent with its preference for PIC and few PC hits. On ChatDev, p decreases and then rises as feedback changes, indicating that the relative demand for PC and PIC varies over time. Figure 17 shows that U = 8 gives the lowest measured median TTFT on RAGPulse (121.46 ms), while U = 32 gives the lowest on ChatDev (146.94 ms). The U = 16 results are 122.33 ms and 147.32 ms, respectively, achieving median TTFT within 1 ms of the best tested window on both workloads. Considering the update frequency as well, we use U = 16 by default. 12

P50 planning latency (ms)

Nebula 0.30 0.15 0.00

128 256

Segments (a) Segment scalability

QuAC: Question answering in context. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pages 2174–2184. Association for Computational Linguistics, 2018.

4 2 0

[3] DeepSeek-AI. DeepSeek-V2: A strong, economical, and efficient mixture-of-experts language model. arXiv preprint arXiv:2405.04434, 2024.

128 256

Workers (b) Worker scalability

Figure 19: Scheduling overhead of N EBULA. (a) Varying the number of segments with 16 workers. (b) Varying the number of workers with 16 segments.

[4] Song Feng, Hui Wan, Chulaka Gunasekara, Siva Patel, Sachindra Joshi, and Luis Lastras. doc2dial: A goaloriented document-grounded dialogue dataset. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 8118– 8128. Association for Computational Linguistics, 2020.

to Locality-aware, on RAGPulse and τ-bench-Retail, respectively. At this rate, Locality-aware transfers less data than N EBULA but has higher compute CV on both workloads.

[5] Cunchen Hu, Heyang Huang, Junhao Hu, Jiang Xu, Xusheng Chen, Tao Xie, Chenxi Wang, Sa Wang, Yungang Bao, Ninghui Sun, and Yizhou Shan. MemServe: Context caching for disaggregated LLM serving with elastic memory pool. arXiv preprint arXiv:2406.17565, 2024.

Scheduling overhead. We measure the latency of greedy plan generation (§7.2) on one pinned vCPU. We uniformly sample segment lengths from 128–2,048 tokens and outstanding worker loads from 0–8,192 tokens, with a 50% segment cache hit ratio and each cache hit placed on a uniformly selected worker. For each setting, we measure 1,024 planning calls after 64 warmup calls. Figure 19 shows that median planning latency is 0.32 ms with 256 segments and 16 workers, and 4.43 ms with 16 segments and 256 workers.

[6] Junhao Hu, Wenrui Huang, Weidong Wang, Haoyi Wang, Tiancheng Hu, Zhang Qin, Hao Feng, Xusheng Chen, Yizhou Shan, and Tao Xie. EPIC: Efficient position-independent caching for serving large language models. In Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, pages 24391– 24402. PMLR, 2025.

Conclusion

N EBULA is the first distributed LLM serving framework to treat PIC segments as first-class citizens, enabling remote cache reuse and parallel prefill. It combines optimistic accounting with event-driven updates to maintain a timely and truthful cluster view, adapts PC/PIC capacity shares using cluster-wide ghost feedback, and selects prefill placement and parallelism through a unified completion-time estimate. Across four models and four real-world RAG and agentic workloads, N EBULA reduces median TTFT by an average of 61.4% compared with the strongest existing baseline and recovers an average of 76.1% of the tokens missed by prefix caching.

[7] Carlos E Jimenez, John Yang, Alexander Wettig, Shunyu Yao, Kexin Pei, Ofir Press, and Karthik Narasimhan. SWE-bench: Can language models resolve real-world GitHub issues? In International Conference on Learning Representations, volume 2024, pages 54107–54157, 2024. [8] Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph E. Gonzalez, Hao Zhang, and Ion Stoica. Efficient memory management for large language model serving with PagedAttention. In Proceedings of the 29th ACM Symposium on Operating Systems Principles, SOSP ’23, pages 611– 626. ACM, 2023.

References [1] Ibragim Badertdinov, Maria Trofimova, Yury Anapolskiy, Sergey Abramov, Karina Zainullina, Alexander Golubev, Sergey Polezhaev, Daria Litvintseva, Simon Karasik, Filipp Fisin, Sergey Skvortsov, Maxim Nekrashevich, Anton Shevtsov, and Boris Yangel. Scaling data collection for training software engineering agents. Nebius Blog, 2024. https://nebius.com/blog/posts/scaling-datacollection-for-training-swe-agents.

[9] Yang Liu, Yunfei Gu, Liqiang Zhang, Chentao Wu, Guangtao Xue, Jie Li, Minyi Guo, Junhao Hu, and Jie Meng. CacheSlide: Unlocking cross position-aware KV cache reuse for accelerating LLM serving. In Proceedings of the 24th USENIX Conference on File and Storage Technologies, FAST ’26, pages 83–99. USENIX Association, 2026.

[2] Eunsol Choi, He He, Mohit Iyyer, Mark Yatskar, Wentau Yih, Yejin Choi, Percy Liang, and Luke Zettlemoyer.

[10] Yifei Liu, Juntong Wu, Yang Liu, Junhao Hu, Minghao Li, Xiaoxu Chen, and Weihang Chen. HYPIC: Ac13

celerating hybrid-attention LLM serving with positionindependent caching. arXiv preprint arXiv:2607.01299, 2026.

[19] NVIDIA. NVIDIA inference xfer library (NIXL). https://github.com/ai-dynamo/nixl. Software repository; accessed: 2026-10-16.

[11] Yuhan Liu, Yihua Cheng, Jiayi Yao, Yuwei An, Xiaokun Chen, Shaoting Feng, Yuyang Huang, Samuel Shen, Rui Zhang, Kuntai Du, and Junchen Jiang. LMCache: An efficient KV cache layer for enterprise-scale LLM inference. arXiv preprint arXiv:2510.09665, 2025.

[20] Nathan Ordonez and Thomas Parnell. MiniPIC: Flexible position-independent caching in <100LOC. arXiv preprint arXiv:2606.13126, 2026.

[12] Zihan Liu, Wei Ping, Rajarshi Roy, Peng Xu, Chankyu Lee, Mohammad Shoeybi, and Bryan Catanzaro. ChatQA: Surpassing GPT-4 on conversational QA and RAG. In Advances in Neural Information Processing Systems, volume 37, pages 15416–15459. Curran Associates, Inc., 2024.

[21] Chen Qian, Wei Liu, Hongzhang Liu, Nuo Chen, Yufan Dang, Jiahao Li, Cheng Yang, Weize Chen, Yusheng Su, Xin Cong, Juyuan Xu, Dahai Li, Zhiyuan Liu, and Maosong Sun. ChatDev: Communicative agents for software development. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 15174–15186. Association for Computational Linguistics, 2024.

[13] Songshuo Lu, Hua Wang, Yutian Rong, Zhi Chen, and Yaohua Tang. TurboRAG: Accelerating retrievalaugmented generation with precomputed KV caches for chunked text. In Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing, pages 6588–6601. Association for Computational Linguistics, 2025.

[22] 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 KVCache-centric architecture for serving LLM chatbot. In 23rd USENIX Conference on File and Storage Technologies, FAST ’25, pages 155– 170. USENIX Association, 2025. [23] Qwen Team. Qwen3.5: Towards native multimodal agents. Qwen Technical Blog. https://qwen.ai/ blog?id=qwen3.5, 2026.

[14] Dongyang Ma, Yan Wang, and Tian Lan. Blockattention for efficient prefilling. In The Thirteenth International Conference on Learning Representations, pages 63774–63788, 2025.

[24] SGLang Project. SGLang Model Gateway: Cache-aware load balancing router. https://github.com/sgl-project/sglang/ blob/main/sgl-model-gateway/src/policies/ cache_aware.rs. Accessed: 2026-09-11.

[15] Sai Sindhur Malleni, Raúl Sevilla, Aleksei Vasilevskii, José Castillo Lema, and André Bauer. Evaluating Kubernetes performance for GenAI inference: From automatic speech recognition to LLM summarization. In Proceedings of the 17th ACM/SPEC International Conference on Performance Engineering, pages 135–146. Association for Computing Machinery, 2026.

[25] vLLM Project. vLLM Router: Load balancing policies. https://github. com/vllm-project/router/blob/ e7989e20b0a733fbd4e9ee6637d2df13373e9d04/ src/policies/cache_aware.rs. Source snapshot; accessed: 2026-10-16.

[16] Nimrod Megiddo and Dharmendra S. Modha. ARC: A Self-Tuning, low overhead replacement cache. In 2nd USENIX Conference on File and Storage Technologies (FAST 03), San Francisco, CA, March 2003. USENIX Association. [17] Mistral AI. Mistral-7B-Instruct-v0.2. Hugging Face model card. https://huggingface.co/mistralai/ Mistral-7B-Instruct-v0.2, 2023.

[26] Qian Wang, Zahra Yousefijamarani, Morgan Lindsay Heisler, Rongzhi Gu, Xiaolong Bai, Yizhou Shan, Wei Zhang, Lan Wang, Ying Xiong, Yong Zhang, and Zhenan Fan. MEPIC: Memory efficient position independent caching for LLM serving. arXiv preprint arXiv:2512.16822, 2025.

[18] Tiyasa Mitra, Ritika Borkar, Nidhi Bhatia, Shivam Raj, Hongkuan Zhou, Yan Ru Pei, Vishwanath Venkatesan, Kyle Kranen, Ramon Matas, Dheevatsa Mudigere, Ritchie Zhao, Maximilian Golub, Arpan Dutta, Suresh Nambi, Sailaja Madduri, Dharmesh Jani, Brian Pharris, Itay Neeman, and Bita Darvish Rouhani. Beyond the buzz: A pragmatic take on inference disaggregation. In Proceedings of Machine Learning and Systems, volume 8, pages 2001–2015. MLSys, 2026.

[27] Shihao Wang, Jiahao Chen, Yanqi Pan, Hao Huang, Yichen Hao, Xiangyu Zou, Wen Xia, Chongyang Qiu, Wentao Zhang, and Pengfei Wang. ProphetKV: Userquery-driven selective recomputation for efficient KV cache reuse in retrieval-augmented generation. In Proceedings of the 43rd International Conference on Machine Learning, volume 306 of Proceedings of Machine Learning Research, pages 125415–125434. PMLR, 2026. 14

[28] Zhengchao Wang, Yitao Hu, Jianing Ye, Zhuxuan Chang, Jiazheng Yu, Youpeng Deng, and Keqiu Li. RAGPulse: An open-source RAG workload trace to optimize RAG serving systems. arXiv preprint arXiv:2511.12979, 2025. [29] Bingyang Wu, Zili Zhang, Yinmin Zhong, Guanzhe Huang, Yibo Zhu, Xuanzhe Liu, and Xin Jin. TokenLake: A unified segment-level prefix cache pool for fine-grained elastic long-context LLM serving. arXiv preprint arXiv:2508.17219, 2025. [30] An Yang, Anfeng Li, Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, et al. Qwen3 technical report. arXiv preprint arXiv:2505.09388, 2025. [31] 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, EuroSys ’25, pages 94–109. ACM, 2025. [32] Shunyu Yao, Noah Shinn, Pedram Razavi, and Karthik Narasimhan. τ-bench: A benchmark for tool-agentuser interaction in real-world domains. In International Conference on Learning Representations, pages 9965– 10017, 2025. [33] Lianmin Zheng, Liangsheng Yin, Zhiqiang Xie, Chuyue Sun, Jeff Huang, Cody Hao Yu, Shiyi Cao, Christos Kozyrakis, Ion Stoica, Joseph E. Gonzalez, Clark Barrett, and Ying Sheng. SGLang: Efficient execution of structured language model programs. In Advances in Neural Information Processing Systems, volume 37, pages 62557–62583, 2024. [34] Yuechi Zhou, Yi Su, Jianxin Zhang, Juntao Li, Qingrong Xia, Zhefeng Wang, Xinyu Duan, and Baoxing Huai. A3 : Attention-aware accurate KV cache fusion for fast large language model serving. arXiv preprint arXiv:2511.17560, 2025. Accepted at EMNLP 2026; arXiv version cited.

Nebula: Distributed Position-Independent Caching for LLM Serving

Analyze & explore related research in Conceptio

Related documents