Recompute or Restore? Host-Tier KV for Multi-Model Agent Workflows on a Static-Graph NPU Serving Stack

Sungwon Woo, Seyeon KimarXiv 2026 · arXiv

TL;DR

This paper investigates a critical bottleneck in serving LLM agent workflows on static-graph NPUs: the cost of recomputing evicted context prefixes. By implementing a host-DRAM tier to "restore" rather than "recompute" these prefixes, the authors achieved a dramatic jump in service-level objective (SLO) attainment—from as low as 9.4% to nearly 100%—while highlighting the non-trivial performance trade-offs of synchronous data transfers.

What Problem Does This Paper Address?

AI "agent" workflows are increasingly common, involving sequences of LLM calls where a "planner" model breaks down a task and "executor" models carry out sub-steps. These calls often share long context prefixes (e.g., a shared document or task history). To serve these efficiently, systems use a Key-Value (KV) cache to store and reuse the intermediate states of these prefixes.

However, many modern AI accelerators, like Neural Processing Units (NPUs), use static-graph compilation. This means the memory budget for the KV cache is fixed at compile time. When the system is under heavy load, these fixed-size caches fill up, forcing the NPU to evict old prefixes. When a subsequent request needs that prefix, the NPU must recompute it from scratch—a process called "prefill" that is computationally expensive.

While GPUs often offload these prefixes to host CPU memory, it wasn't clear if this "restore" strategy would work for NPUs. On the hardware studied (the Rebellions ATOM+), data transfers between the NPU and host memory share the same engine thread as the actual model execution. This creates a quantitative dilemma: Does the time saved by not recomputing outweigh the time lost to synchronous data transfers?

Methods

The authors conducted a measurement study on a commercial NPU stack (Rebellions ATOM+ with vLLM) serving a Qwen3-8B planner and a Qwen3-0.6B executor. Their approach had two main pillars:

  1. Host-Tier KV Bridge: They built an adapter that connects vLLM’s offloading manager to the NPU’s proprietary KV layout. This allows evicted prefixes to be stored in host DRAM and restored on demand. Crucially, these transfers are synchronous, meaning they block the NPU engine from doing other work.
  2. Scheduler-Aware Event Model: To understand the performance trade-offs, they developed a discrete-event simulation of the NPU's scheduler. This model was calibrated on a single data "seed" and then used to make "frozen" predictions (predictions made before seeing the actual test data) for various workloads.
Figure 2: Overview of the serving path (top) and the prospective evaluation (bottom), with a chain workflow as the dependency example. On the planner, restore, prefill, store, and decode share one engine thread: the full host prefix is restored when the usable host prefix is longer than the local one (Hh > Hl), and missing host entries are stored after prefill. Boxes show the order of operations, not their durations. The event model makes predictions from the frozen trace and does not control serving.

Datasets

The study used synthetic workflow Directed Acyclic Graphs (DAGs) designed to mimic real agent behavior:

  • Chain workflows: A linear sequence of planner and executor calls.
  • Fork workflows: A planner call followed by multiple parallel executor branches.
  • Mixed/Bursty workloads: Combinations of the above with varying arrival rates.
  • The authors also released a 50,000-workflow dataset with these profiles to the public.

Key Insights and Ideas

  • Redundant Prefill is the Killer: In a system collapse under overload, the authors found that 89.5% of planner prompt tokens had already been processed in previous calls. The system was essentially choking on work it had already done.
  • The "Restore" Rescue: Moving these prefixes to host memory instead of recomputing them allowed the system to absorb nearly the entire arrival rate that previously caused a total collapse.
  • The Synchronous Tax: Because transfers are synchronous on this stack, "restoring" isn't free. For "fork" workflows, while the host tier improved median latency, it actually increased 99th-percentile (P99) latency by 16–18%. This is because the time spent storing and restoring prefixes can delay subsequent requests on the same engine thread.
  • Predictability: A relatively simple discrete-event model can predict median and P99 latencies within a 15% tolerance, proving that these complex scheduling dynamics are understandable and predictable.
Figure 1: Planner work in the KV64 fork collapse run (seed 501, 0.55 workflows/s). Under stock serving (B0), 89.5% of the executed prompt tokens are repeated (a), and prefill calls made only of repeated tokens take 59.3% of the host-inclusive API time (b). Repeated tokens are classified from earlier runtime completions and block history. The panels use different numerators and denominators, and API time includes warmup and failed-client requests, so it is not divided by the client wall time in (c).

Key Results

  • Overload Recovery: In high-load conditions where stock serving failed (SLO attainment of ~22.8% for chains and ~9.4% for forks), the host-tier system achieved 100% and 99.8% SLO attainment, respectively.
  • Capacity Gains: The host tier provided confirmed load gains of 11.8% for chain workflows and 18.2% for fork workflows.
  • Latency Accuracy: The frozen model successfully predicted latencies across 24 different common-load conditions within its 15% error budget.
Figure 3: Recovery under KV32 mixed-burst overload (seed 505, 0.65 workflows/s, 1,200 arrivals per arm). Each point summarizes a 60 s arrival cohort; the horizontal axis is arrival time, not completion time. SLO attainment counts all workflows including errors, and latency quantiles use successful workflows only. With the host tier, both B0 and F6 keep SLO attainment near 100% and latency flat, whereas without it SLO attainment falls to zero and latency rises to hundreds of seconds. Error counts are in Table 2.

Limitations and Future Work

  • Hardware Specificity: The study is pinned to a specific NPU vendor (Rebellions) and SDK version. The results might differ on hardware that supports asynchronous transfers.
  • Synthetic Workloads: The use of fixed-input synthetic DAGs means the study doesn't account for dynamic agent behavior, such as tool-use branching or varying output lengths based on model reasoning.
  • Energy Measurement: Energy savings were measured at the board level only, excluding host CPU/DRAM power.
  • Future Directions: The authors suggest that future work could explore scheduler changes to interleave prefill and decode steps more effectively, or investigate the impact of cheaper, optimized store paths for KV data.

Summary updated

Abstract

Agent workflows issue dependent model calls that share long context prefixes, so serving them efficiently depends on reusing the key-value (KV) cache of those prefixes. On accelerators that compile model graphs ahead of time, however, the device KV budget is fixed, and prefixes evicted under load must be recomputed. Restoring them from host memory avoids this recomputation, but the transfer occupies the same engine thread as prefill and decode, so its benefit is not guaranteed. In this paper, we study when restoring beats recomputing on a commercial static-graph neural processing unit (NPU) stack (Rebellions ATOM+, vllm-rbln 0.10.2) that serves a Qwen3-8B planner on two cards and a Qwen3-0.6B executor on one. We first show that repeated prefill dominates planner work when default serving collapses: 89.5% of the executed planner prompt tokens had been materialized before. We then build a synchronous host-DRAM tier on the runtime's public KV copy calls, together with a scheduler-aware event model whose predictions are frozen before each test cohort. Experimental results show that the host tier raises workflow service-level objective (SLO) attainment from 22.8% to 100% and from 9.4% to 99.8% in the two tested overload conditions, and endpoint confirmation on two new seeds supports conservative load gains of 11.8% (chain) and 18.2% (fork), while mixed and bursty workloads remain seed-sensitive. The frozen model predicts median and 99th-percentile (P99) latency within its 15% tolerance in all 24 common-load conditions, including the 16-18% P99 increase that the tier causes for fork workflows, but it misorders three policy contrasts and overestimates the benefit of a cheaper store path (11% predicted against 3.1% measured). The trade-off therefore depends on runtime scheduling and transfer cost as well as cache capacity.
BibTeX
@misc{woo2026recompute,
  author = {Sungwon Woo and Seyeon Kim},
  title = {{Recompute or Restore? Host-Tier KV for Multi-Model Agent Workflows on a Static-Graph NPU Serving Stack}},
  year = {2026},
  eprint = {2611.15126},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.15126},
}
Figure