PaperlayerView exact revision on arXiv

Source-linked AI summary

PriorityFEC: Deadline-Aware Streaming FEC for KV-Cache Handoff in Edge Multi-Agent Systems

Han Shen, Qifu Tyler Sun, Fanyang Meng, Ye Wang, Yongsheng Liang

arXiv:2610.21390v1cs.NIcs.AI

TL;DR

Collaborative edge agents can avoid redundant prefill by reusing KV caches, but strict TTFT deadlines and unreliable links can prevent complete transfer. PriorityFEC orders KV blocks by utility and adapts Streaming FEC repairs; experiments report its largest gains when deadlines are too tight for complete transfer.

  • Problem

    Reusable KV state must cross bandwidth-constrained, potentially unreliable links before decode startup, and fixed repair schedules may waste or mistime limited repair opportunities.

    Source: §I · pp. 1–2

  • Method

    PriorityFEC places model-derived high-utility KV blocks earlier in the source stream and adapts Streaming FEC repairs to decoding progress under a repair budget.

    Source: §I · p. 2

  • Results

    PriorityFEC provides its largest gains when the decode-start deadline is too tight to permit complete KV transfer, with its advantage decreasing as the deadline relaxes.

    Source: §VI · p. 15

  • Takeaways & Limitations

    For reusable model state crossing a constrained network before a deadline, transport should optimize the utility of state available then rather than treating every byte equally.

    Source: §VI · p. 15

    The transport utility is a surrogate, not an exact additive measure of downstream LLM quality, because missing KV regions may interact nonlinearly in attention.

    Source: B. Mapping KV Utility to Transport… · p. 5

Abstract

from arXiv · show

Multi-agent large language model (LLM) systems are increasingly deployed at the edge to support complex tasks that require collaboration and information exchange among multiple agents. However, when task contexts are passed across agents, shared context that has already been processed by upstream agents often needs to be prefilled again, resulting in substantial redundant computation. Reusing an already prefilled key--value (KV) cache can avoid this recomputation, but requires the reusable KV state to be transferred across the network before the receiving agent can begin generation. Under strict time-to-first-token (TTFT) deadlines and unreliable edge links, delivering the complete KV cache may be infeasible, making it necessary to prioritize and protect the most valuable KV information within a limited transmission budget. This paper proposes PriorityFEC, a utility-aware KV-cache handoff scheme that jointly exploits model-side KV importance and transport-side reliability. PriorityFEC first constructs a utility-aware source stream by placing high-utility KV blocks at earlier transmission positions. It then protects the ordered stream using a feedback-adaptive Streaming Forward Erasure Correction (FEC) mechanism, which schedules repair packets according to receiver feedback before the TTFT deadline. We implement PriorityFEC on a distributed edge LLM serving prototype and evaluate it with Qwen2.5-7B-Instruct and Llama-3.1-8B-Instruct across multiple datasets. Results show that PriorityFEC achieves superior task quality over the compared transport schemes, with its advantages becoming particularly pronounced under stringent deadline constraints. These results demonstrate the importance of jointly optimizing KV-cache utility and deadline-aware transport reliability when reusable LLM state must be handed off across unreliable edge networks.

I. Introduction

Collaborative edge agents can reuse upstream KV state to avoid redundant prefill, but the cache must arrive before decode startup over constrained, unreliable links. PriorityFEC orders KV blocks by utility and adapts Streaming FEC repairs to improve the utility of reconstructed state before the TTFT deadline.

I. Introduction

  • KV-cache reuse avoids redundant prefill only if the state reaches the receiving agent in time, a challenge amplified by long contexts and bursty edge-link losses.The paper notes that communication delay can dominate handoff latency for large KV states.Source: §I · pp. 1–2
  • Under tight TTFT budgets, waiting for complete reliable delivery can delay agent activation, motivating transport that prioritizes useful state available by the deadline.The objective trades eventual completeness for timely availability of task-relevant model state.Source: §I · p. 2
  • PriorityFEC places high-utility KV blocks earlier in the source stream and adjusts Streaming FEC repairs according to decoding progress under a repair budget.The two mechanisms address delivery order and recovery timing, respectively.Source: §I · p. 2
  • The design formulates handoff as maximizing decode-start KV utility rather than eventual byte completeness, because equal amounts of recovered data can preserve different levels of model-relevant information.The contribution describes the adaptive scheduler as a finite-horizon source–repair problem under hard deadline and repair-budget constraints.Source: §I · p. 2
  • PriorityFEC maps model-derived importance to equal-sized transport blocks, preserving all blocks for possible reconstruction while giving higher-utility blocks earlier delivery opportunities.Its scheduler adapts repair decisions to causal transport feedback and KV utility.Source: §I · p. 2
  • Adaptive source–repair allocation is particularly beneficial when complete KV-cache delivery is infeasible before decode startup.The introduction reports this experimental result for the target regime.Source: §I · p. 3

II. Related Work

Prior work supports KV reuse, movement, and adaptive loss recovery, while PriorityFEC addresses which reusable KV blocks should arrive over lossy links before decode startup. Its utility profiles show that partial-cache identity matters for model fidelity.

A. KV-Cache Reuse and Movement in Distributed LLM Serving

  • Distributed serving, paging, external cache systems, and compression reduce KV recomputation or transfer costs, while PriorityFEC addresses delivery of valuable KV regions over lossy edge paths.The work treats transport as complementary once reusable state has been identified.Source: A. KV-Cache Reuse and Movement in… · p. 3

B. FEC for Deadline-Constrained and Lossy Transport

  • Streaming FEC uses overlapping windows to help unresolved packets benefit from later repairs; adaptive schemes use feedback, while PriorityFEC also incorporates utility-aware source ordering.Prior UEP methods generally encode importance in coding windows, protection levels, or scheduling policies.Source: B. FEC for Deadline-Constrained and… · p. 3

C. Positioning of This Work

  • PriorityFEC assumes compatible reusable KV state is already identified and asks which blocks deserve favorable delivery and recovery opportunities under a fixed TTFT deadline and bounded repair budget.Its objective is deadline-available KV utility rather than eventual byte completeness, while preserving the pretrained LLM.Source: C. Positioning of This Work · pp. 3–4

III. Utility-Aware Source Ordering for Deadline-Constrained KV Handoff

  • The handoff scenario transfers already-computed KV state from a source agent to a receiving agent before decoding, under a stringent TTFT budget and varying bandwidth and RTT.The transport-oriented question is whether the identity of partially available KV state affects model fidelity.Source: §III · p. 4, A. Transport-Oriented KV-Utility… · p. 4

A. Transport-Oriented KV-Utility Validation

  • At 40% retention, profile-ranked KV retention reaches 55.2% teacher-forced top-1 agreement versus 44.0% for random retention on held-out prompts.The profiles also show heterogeneous layer sensitivity and greater sensitivity in prompt-prefix and recent-context positions.Source: A. Transport-Oriented KV-Utility… · p. 4

B. Mapping KV Utility to Transport Blocks

The method maps model-derived KV importance to equal-sized transport blocks, then places higher-utility blocks earlier so they receive more pre-deadline delivery opportunities. This ordering maximizes expected deadline-complete utility under the stated position-probability condition, but the utility is only a transport-oriented surrogate for downstream LLM quality.

B. Mapping KV Utility to Transport Blocks

  • The utility of a transport block is derived from measured sensitivity across profiled layer–position cells, accounting for the fractions of cells carried by source packets.Transport blocks contain equal-size packets, and padding in the final block carries zero utility.Source: B. Mapping KV Utility to Transport… · pp. 4–5
  • Block utility is a transport-oriented surrogate, not an exact additive decomposition of downstream LLM quality.The analytical results concern deadline-complete transport utility; downstream task quality is evaluated directly in Sec. V.Source: B. Mapping KV Utility to Transport… · p. 5

C. Utility-Aware Source Queue Construction

  • Higher-utility KV blocks enter the stream earlier, while lower-utility blocks remain at later source positions.The original packet order within each transport block is preserved.Source: C. Utility-Aware Source Queue… · p. 5
  • Descending-utility ordering maximizes expected deadline-complete transport utility when earlier source positions have no lower completion probabilities.The result concerns source ordering under fixed position-dependent probabilities, not the complete adaptive PriorityFEC policy.Source: C. Utility-Aware Source Queue… · p. 5
  • ACK-sliding Streaming FEC transmits source packets systematically and generates repairs over the current unacknowledged source window.As cumulative decoding advances, the recovered prefix leaves subsequent coding windows while unresolved packets remain protected.Source: Figure 3 · p. 5

IV. Adaptive Streaming FEC

Adaptive Streaming FEC combines the utility-ordered source queue with ACK-sliding loss recovery and a scheduler that chooses when to spend transmission opportunities on repairs. Its coding window tracks unresolved packets, while the scheduler controls timing without changing source order or the coding rule.

IV. Adaptive Streaming FEC

  • Source and repair packets share a limited transmission budget, creating a tradeoff between delivering new KV state and recovering losses before decode startup.Fixed schedules may waste repairs during normal transmission or react too slowly as correlated losses expand the unresolved window.Source: §IV · p. 5
  • PriorityFEC combines the utility-ordered source queue, ACK-sliding Streaming FEC, and an adaptive repair scheduler.The queue determines what to send first, FEC provides loss recovery, and the scheduler decides when to send repairs.Source: §IV · p. 5

A. ACK-Sliding Streaming FEC

  • Sparse random linear coding limits each repair packet to a subset of the current unresolved source window, with maximum coding degree K = 48.The source packets are transmitted sequentially in the fixed utility-aware order.Source: A. ACK-Sliding Streaming FEC · pp. 5–6
  • Cumulative ACK progress removes the decoded prefix from the coding window, while erased packets remain eligible for later sparse repair combinations.The scheduler changes the temporal allocation of source and repair opportunities, not the utility-derived source order or sparse coding rule.Source: A. ACK-Sliding Streaming FEC · p. 6

B. Adaptive Repair-Scheduling Problem

The adaptive repair-scheduling problem allocates a finite number of pre-deadline transmission opportunities and a bounded repair budget between source delivery and loss recovery. Its objective is to maximize the normalized utility of KV blocks fully recovered by decode startup.

B. Adaptive Repair-Scheduling Problem

  • The scheduler has a finite number of packet-transmission opportunities before decode startup and a maximum repair budget.A decision epoch can transmit multiple packets, so it is distinct from an individual packet opportunity.Source: B. Adaptive Repair-Scheduling Problem · p. 6
  • Actions either continue source transmission or send a burst of a selected number of repair packets.A source action sends up to M_s consecutive packets without crossing the current KV-block boundary.Source: B. Adaptive Repair-Scheduling Problem · p. 6
  • The scheduling objective is to maximize normalized receiver utility from KV blocks completely recovered by the deadline.The objective is optimized over feasible policies, with separate costs for repair-budget and transmission-slot consumption.Source: B. Adaptive Repair-Scheduling Problem · p. 6
  • Because repair decisions affect future losses, delayed feedback, decoding progress, and remaining time, the problem is a finite-horizon stochastic scheduling problem solved as an MDP with Double DQN.The learner selects a policy for sequential source–repair decisions under the deadline and repair-budget constraints.Source: B. Adaptive Repair-Scheduling Problem · p. 6

C. MDP Formulation

The scheduler uses a compact state reconstructed from sender-side history and feedback to adapt source–repair decisions to transport conditions, decoding progress, and KV utility. It formulates the sequential decision process as a finite-horizon MDP and learns a policy with Double DQN.

C. MDP Formulation

  • The repair-scheduling process is modeled as a finite-horizon MDP because decisions unfold under uncertain packet losses and delayed feedback.The formulation comprises transport states, actions, stochastic transition dynamics, and rewards.Source: C. MDP Formulation · p. 6

1) State Representation:

  • The scheduler uses a compact state rather than requiring the complete packet-transmission history.State features are reconstructed from sender-side transmission history and the latest feedback, then normalized to [0, 1].Source: 1) State Representation · pp. 6–7
  • State features capture remaining repair budget and time, source-delivery pressure, estimated packet loss, and burst-loss tendency.These features describe deadline pressure and the estimated Gilbert–Elliott channel condition.Source: 1) State Representation · p. 6
  • Other state features track decoding-deficit severity, unresolved-window scale, and lack of recent cumulative decoding progress.Together, these features characterize the current recovery need.Source: 1) State Representation · p. 6
  • Application-aware features represent current-block transmission progress, its normalized utility, upcoming-block utility, and estimated repair effectiveness.They allow otherwise similar network states to yield different repair decisions when the KV state at risk has different utility.Source: 1) State Representation · p. 6
  • The DoF deficit indicates how much additional innovative repair information is needed before cumulative decoding can advance.It is defined from the unresolved coding-window size and the independent degrees of freedom available for that window.Source: 1) State Representation · pp. 6–7

2) Action and Feasibility:

The scheduler masks actions that violate transmission constraints and learns when repair is worthwhile. Double DQN is trained with shaped rewards that preserve the deadline-level objective.

2) Action and Feasibility:

  • Repair actions are enabled only when unresolved information and sufficient repair budget and transmission opportunities remain; source delivery stops when its queue is exhausted or the deadline arrives.The state-dependent action mask enforces these hard constraints, leaving the policy to decide when repair is worthwhile.Source: 2) Action and Feasibility · p. 7

3) Reward Design:

  • The reward combines newly recovered KV utility with a potential that rewards decoder progress and penalizes repair-budget deficit and unresolved coding-window growth.With γ = 1, the shaping terms telescope and do not change the deadline-level optimization objective.Source: 3) Reward Design · p. 7

D. Double-DQN-Based Repair Scheduling

  • Double DQN uses an online network to select feasible actions and a target network to evaluate them, learning repair scheduling from replayed transitions.The online network is a two-hidden-layer Q-network with 64 ReLU units per layer; deployment requires one lightweight inference per decision epoch.Source: D. Double-DQN-Based Repair Scheduling · pp. 7–8, Figure 4 · p. 8

V. Evaluation

The evaluation asks whether utility-aware ordering increases model-relevant KV state available before decoding and improves downstream task quality. It tests two LLMs on three QA workloads under paired network realizations and two decode-start deadlines.

V. Evaluation

  • The evaluation tests whether utility-aware ordering improves deadline-available KV utility and whether that transport-level gain translates into higher LLM task quality.The study evaluates deadline-available utility and end-to-end task quality under controlled burst-loss conditions.Source: §V · p. 8

A. Experimental Setup

  • Two instruction-tuned LLMs are evaluated on three LongBench-E QA workloads using 1,536-token contexts, with token-level F1 as the task-quality metric.Each model–dataset pair uses 48 examples across five paired network realizations, for 240 example–network realizations per operating point.Source: A. Experimental Setup · p. 8
  • The main network setting is a 100-Mbps link with 20-ms RTT and bursty Gilbert–Elliott losses averaging approximately 8.42%.The tested deadline ratios are ρ = 0.8, where full loss-free serialization is infeasible, and ρ = 1.0, which allows one loss-free serialization interval but no extra time for losses or repair traffic.Source: A. Experimental Setup · p. 8

B. Implementation and Training Details

The implementation combines a native Streaming FEC codec with an LLM serving prototype and compares transport policies using complementary transport- and task-level measures. Training uses synthetic transport conditions, and the reported task-quality results have stated transfer and context-length boundaries.

B. Implementation and Training Details

  • The prototype runs PyTorch and Transformers with a native C Streaming FEC codec over GF(2^8), while a complementary socket prototype transfers real KV bytes over TCP or UDP on a single-host loopback path.Controller and codec overhead are measured separately from the simulated transmission deadline.Source: B. Implementation and Training Details · pp. 8–9
  • The main receiver zero-fills BF16 elements unless both serialized bytes are recovered, preserving cache shape and token positions without repeating full-prompt prefill.A separate attention-mask receiver can use intact head–token rows within incomplete blocks; comparisons of repair schedulers must hold this receiver condition constant.Source: B. Implementation and Training Details · p. 9
  • The 15–64–64–4 Double-DQN scheduler chooses source or repair bursts under hard feasibility masks, and training uses synthetic utility-ranked blocks and randomized GE channels without QA examples or task-F1 rewards.Its transport-potential reward favors completed-block utility and prefix progress while penalizing decoder deficit and coding-window backlog; evaluation uses the actual codec.Source: B. Implementation and Training Details · p. 9
  • The task-quality results do not establish 4K/8K-context scalability because training blocks differ in fragment count from deployment blocks and the current profiler constructs full attention tensors.The existing 5G trace replay uses a recorded loss process and 20.48-Mbps offered-rate assumption; broader held-out tests across network conditions remain necessary.Source: B. Implementation and Training Details · p. 9
  • Comparisons include retransmission-based TCP and QUIC, FIFO UDP, uniform FEC, FlEC-RT, and PriorityFEC; recovered utility and token-level F1 measure transport recovery and downstream task quality, respectively.PriorityFEC combines utility-aware ordering with learned adaptive repair scheduling.Source: B. Implementation and Training Details · p. 9

C. Deadline-Available KV Utility

PriorityFEC improves downstream task quality most when the deadline prevents complete KV delivery, and it recovers a larger share of model-defined KV utility under that tight constraint. Both advantages diminish as the deadline is relaxed.

C. Deadline-Available KV Utility

  • At ρ = 0.8, PriorityFEC retains 99.1% average normalized KV utility versus 82.3% for the strongest per-case baseline, an average improvement of 16.8 percentage points.The normalized utility measures recovered model-defined utility, not the fraction of KV bytes delivered; high-utility blocks are prioritized and protected against burst losses.Source: Figure 5 · p. 10, C. Deadline-Available KV Utility · p. 10
  • At ρ = 1.0, PriorityFEC retains approximately 99.2% normalized utility, with an average advantage over the strongest baseline of approximately 5.6 percentage points.Task-quality gaps also narrow as more KV state becomes recoverable; FLEC-RT exceeds PriorityFEC in several cases at this relaxed deadline.Source: C. Deadline-Available KV Utility · p. 10, D. End-to-End Task Quality · p. 11

D. End-to-End Task Quality

  • At ρ = 0.8, PriorityFEC averages 43.4% task score versus 8.1% for the strongest per-case baseline, an average advantage of 35.3 percentage points across six model–workload combinations.The task-quality advantage is largest when decoding must start with substantially incomplete KV state.Source: Figure 6 · p. 11, D. End-to-End Task Quality · p. 11

E. Component Ablation

The ablation finds that utility-aware ordering and adaptive repair complement one another, with PriorityFEC leading task-quality and recovered-utility comparisons under tight deadlines. Runtime measurements show the controller keeps pace with packet transmission in the evaluated settings.

E. Component Ablation

  • At ρ = 0.8, PriorityFEC averages 34.8% token-level F1 across three workloads, versus 27.0% for Priority-only and 25.8% for Priority+Fixed FEC.Fig. 7 reports downstream token-level F1 in its first row; the learned scheduler complements utility-aware ordering.Source: Figure 7 · p. 12, E. Component Ablation · p. 12
  • At ρ = 0.8, FIFO protection can miss valuable KV regions, while fixed repairs can displace high-utility source packets when decoding deficits do not justify redundancy.The comparison identifies source ordering as particularly important under tight deadlines and motivates adaptive repair scheduling.Source: E. Component Ablation · p. 12
  • At ρ = 0.8, PriorityFEC preserves approximately 99% of profile-derived KV utility, versus 91% for Priority-only, 92% for Priority+Fixed FEC, and 77–78% for RL StreamingFEC-only.Fig. 7 reports normalized KV utility recovered before the decode-start deadline in its second row.Source: E. Component Ablation · p. 12, Figure 7 · p. 12
  • At ρ = 1.0, PriorityFEC averages 43.8% token-level F1, compared with 35.0% for Priority+Fixed FEC, and remains the strongest variant.With the relaxed deadline, fixed FEC improves on Priority-only as additional transmission opportunities lower repair's opportunity cost.Source: E. Component Ablation · p. 12

F. Runtime Overhead and Computational Feasibility

  • Online processing takes 30.34–33.41 ms per 103 transmitted packets, approximately 27–30% of the 112 ms packet-serialization interval.The measured aggregate computation does not become the bottleneck of the evaluated transport path.Source: F. Runtime Overhead and Computational… · p. 13
  • The controller's mean latency is approximately 76–78 µs and its P99 latency is 94.35–97.58 µs, below the 112 µs packet slot in all four settings.Only 0.009–0.019% of controller decisions exceed one packet slot.Source: F. Runtime Overhead and Computational… · p. 13
  • RL inference requires approximately 3.3–3.4 ms per 103 packets; GF(28) packet construction and decoding dominate runtime, and measured transport computation is similar across the two LLMs.The transport-side cost scales primarily with packet processing and coding operations rather than model parameter count.Source: F. Runtime Overhead and Computational… · p. 13

G. Measured 5G Trace Replay

In the measured 5G trace replay, PriorityFEC has the highest observed mean F1 in all six tight-deadline cases, though exceptions occur at the relaxed deadline. The evaluation uses one selected trace segment, and the conclusion emphasizes deadline-available KV utility and the tight-deadline regime.

G. Measured 5G Trace Replay

  • The replay uses a 300-s 5G SA uplink segment with 11.65% packet loss and a 20.48-Mbps service rate; windows come from one measured segment.Each model–workload pair uses eight examples and two paired replay windows per example.Source: G. Measured 5G Trace Replay · pp. 13–14
  • At ρ = 0.8, PriorityFEC has the highest observed mean F1 against five main transport baselines in all six replay cases.Fig. 8 shows token-level F1 under measured 5G SA uplink loss replay; bars average eight examples and two paired replay windows per example.Source: G. Measured 5G Trace Replay · p. 14, Figure 8 · p. 14
  • At ρ = 1.0, FLEC-RT slightly exceeds PriorityFEC on Llama HotpotQA, while Priority+Fixed FEC exceeds it on Qwen HotpotQA at ρ = 0.8.The Llama 2WikiMultiHopQA score also falls from 40.0% to 25.7% as the deadline is relaxed, despite near-complete utility recovery.Source: G. Measured 5G Trace Replay · p. 14
  • The replay supports descriptive comparisons, not statistical-significance claims or performance claims across all 5G conditions, given the selected trace and small sample with dependent windows.The scope is limited to the selected trace and its replay assumptions.Source: G. Measured 5G Trace Replay · p. 14

VI. Conclusion

  • The conclusion frames transport for distributed LLMs as optimizing the utility of reusable model state available by a downstream deadline rather than treating every byte as equally valuable.The reported gains are largest when the decode-start deadline is too tight for complete KV transfer; prioritization's advantage decreases as the deadline relaxes.Source: §VI · pp. 14–15

Related papers

Loading 2610.21390v1…