Justitia: Fair and Efficient Scheduling of Task-parallel LLM Agents with Selective Pampering

framework 2510.17015
agent-schedulingfair-queuingkv-cachevllmapplication-level-schedulingvirtual-time-wfq
← Synthesis ← framework Survey Source ↗

Justitia: Fair and Efficient Scheduling for LLM Applications #

Mingyan Yang, Guanjie Wang, Manqi Luo, Yifei Liu, Chen Chen, Han Zhao, Yu Feng, Quan Chen, Minyi Guo (Shanghai Jiao Tong University) | 2025-10 | arXiv:2510.17015 Category: framework | Tags: agent-scheduling, fair-queuing, kv-cache, vllm, application-level-scheduling Read: 2026-04-18

Core Contribution #

Justitia 把 网络包调度里的 Virtual-Time Fair Queuing (WFQ) 搬到 LLM 应用级调度——以 KV token-time（显存占用 × 持续时间）作为成本度量，用 per-app 轻量 MLP 在应用到达瞬间预测其成本，再以 GPS (Generalized Processor Sharing) 参考系统下的 virtual finish time 作为优先级，在保证最坏延迟 $\le 2c_{\max}+C_{\max}/M$ 的前提下，把平均应用完成时间比 VTC 降低 57.5%。

Summary #

动机：现代 LLM 应用（MapReduce 摘要、Doc Merging、Fact Verification、Self-Consistency 等）由多条并行的 LLM 推理组成，用户只关心整个应用的端到端完成时间（JCT）。现有调度器要么在推理级 FCFS（vLLM、Parrot）产生 head-of-line blocking，要么严格执行瞬时公平分享（VTC、FairServe），把每个应用锁死在"公平份额"里，导致本可以更快完成的应用被无谓拖慢。作者的洞察是用户真正需要的是 长期公平（long-term fairness / finish-time fairness） 而非 短期公平：只要保证没有任何应用比在理想公平调度下更慢完成，就可以允许应用串行"吃饱"（saturated serving），通过近似 SJF 的顺序降低平均 JCT。

方法：Justitia 由三件配套工具组成。(1) Memory-centric cost modeling — 因为 vLLM 的吞吐瓶颈在 KV cache 显存而不是算力，Justitia 把一条推理的成本定义为整个生命周期里的 KV 累计占用 $c=\sum_{i=1}^{d}(p+i)=pd+d^2/2$（KV token-time），一个应用的成本是其所有推理成本之和，成本与输出长度 $d$ 的关系天然是 二次 的，比 VTC 的线性 $p+2d$ 更能反映真实资源压力。(2) Per-app MLP demand predictor — 应用到达时用 TF-IDF 向量化 prompt，送入该应用类型专属的 4 层 MLP（每类 100 样本训练），预测其总 KV token-time；对比 S³ 用 Distillbert（66M 参数）的方案，MLP 把预测开销从 55.7ms 降到 2.16ms，相对误差从 452% 降到 53%。(3) Virtual-time fair queuing — 借鉴 1990 年代网络 WFQ：定义虚拟时间 $V(t)$，其变化率 $dV/dt = M/N_t$（$M$ 是总 KV blocks，$N_t$ 是 GPS 下的活跃应用数），应用 $j$ 到达时一次性算出虚拟完成时间 $\bar f_j = V(a_j)+C_j$，之后无论有多少新应用到来都不需要刷新这个值，调度时按 $\{\bar f_j\}$ 升序（即 GPS 完成顺序）优先；堆操作 $O(\log N_t)$。

结果：在 A100 + LLaMA-7B（单卡）与 4×V100 + LLaMA-13B（多卡）上，用 300 个 9 类混合应用、按 Mooncake 到达 trace 测试。相比 VTC 平均 JCT 降低 57.5%（相对 Parrot 降低 61.1%），且 92% 的应用在 Justitia 下比在 VTC 下更早完成，最坏延迟 26% 远小于其它调度器。同时理论证明了常数延迟界 $f_j - \bar f_j \le 2c_{\max}+C_{\max}/M$。消融实验显示去掉 memory-centric（改回 VTC 的 compute-centric 成本）JCT 恶化 42.3%；scheduling overhead 即使在 100 app/min 下也只有 8ms。

Key Findings #

Limitations #

Key Figures #

Figure 1: Concurrent vs Sequential Serving (Motivation) #

Figure 1a: Concurrent

Figure 1b: Sequential

What it shows: 两个 LLM 应用并发（instantaneous fair sharing）时总 JCT 长，而按 GPS 完成顺序串行"吃饱"（saturated serving）时平均 JCT 更短，且没有任何一个应用比并发情况下更晚完成。

Why it matters: 这是整篇论文的"灵魂图"——说明 trade 短期公平换长期公平 + 效率 的可行性。

Detailed description: 两个甘特图。左图每个应用只占总资源的一半并行跑到各自 endpoint；右图 app-1 先独占所有资源、提前完成、然后 app-2 独占、同一时刻结束。平均完成时间右图 < 左图，但右图 app-2 的完成时刻 ≤ 左图 app-2 的完成时刻。

Figure 3: KV Block Usage — Two DocMerging Apps on LLaMA2-7B A100 #

Figure 3a: Instantaneous Fair Sharing

Figure 3b: Saturated Serving

What it shows: 真实 testbed 中，并发公平分享下 DM-1 与 DM-2 每个被限制在约 230 blocks（总 459），平均 JCT = 210s；串行"吃饱"时 DM-1 先用满 459 blocks、完成后 DM-2 接上，平均 JCT = 166s。

Why it matters: 这是 Fig.1 概念图的实测验证，直接量化出 21% 的平均 JCT 下降且无应用被延迟。

Detailed description: 横轴是 inference iteration (0-4000+)，纵轴是 GPU Blocks Usage (0-400+)。左图两条曲线重叠在中间高度；右图一条曲线先拉满、后让另一条拉满，像两个连续的方波。

Figure 5: KV Token-Time Cost Model #

Figure 5: KV token-time

What it shows: 一条推理的 KV 累计占用示意——prefill 阶段固定 $p$ tokens，decode 阶段每步增加 1 个 token，直到总长 $p+d$，积分面积即成本 $c=pd+d^2/2$。

Why it matters: 这是 核心技术壁垒——整个调度器的每一步排序都依赖这一个公式；它把 VTC 的线性 $p+2d$ 替换为二次 $pd+d^2/2$，是 Justitia/C 消融实验 42.3% JCT 恶化的根源。

Detailed description: 一个梯形图：横轴是 iteration，纵轴是 token 数。左边矩形（宽度 1、高度 $p$）代表 prefill；右边三角形（宽度 $d$、高度从 $p$ 线性增到 $p+d$）代表 decode。阴影面积 = $p \cdot d + d \cdot d/2$。

$$c = \sum_{i=1}^{d}(p+i) = pd + \frac{d^2}{2}$$

Figure 6: MLP-based Demand Prediction Workflow #

Figure 6: MLP Predictor

What it shows: 应用到达时，system prompt + user prompt 被 TF-IDF 向量化成定长向量，送入该应用类型专属的 4 层 MLP，输出预测的总 KV token-time。

Why it matters: 这是把 "预测 application cost" 从 S³ 那种 66M DistillBert 推理 降维到 数千参数 MLP 前向 的关键——2.16 ms vs 55.7 ms 的 25× 加速；训练只需 100 样本。

Detailed description: 左边是两段文字（系统 prompt 与用户 prompt），中间是 TF-IDF 向量化箭头，向量元素如 [0, 0, 0.3, 0.2, 0.9, 0.4, 0.2, 0.1] 送入方框标注 "MLP for app-i"，输出箭头指向 "Predicted resource demand"。

Figure 7: Justitia Queuing — GPS vs Real Execution #

Figure 7: Justitia Queuing

What it shows: 上图展示 GPS 参考系统下三应用（App-1/2/3）的完成顺序；下图展示 Justitia 按这个 GPS 完成顺序作优先级，实际执行时每个应用独占 KV-block 依次跑完。

Why it matters: 展示了 virtual-time fair queuing 的调度决策——GPS 里 App-1 最先完成、App-3 次之、App-2 最后；Justitia 就按这个顺序做非抢占式独占调度，既近似 SJF 又保证最坏延迟界。

Detailed description: 双甘特图。(a) GPS 横轴虚拟时间 [0,5,12.5,13.5]，三条彩色横条分别代表 App-1/2/3，在 5 时 App-1 结束、App-1 退出使剩余两个应用的 rate 增大、13.5 时 App-2 完成。(b) Justitia 横轴真实时间 [0,4,5,6,8,11,12]，App-1 的 i1/i2 先串行执行，接 App-2 的 i1（因其已到达且 App-3 还未到）、App-3 的 i1/i2/i3 插入执行、最后 App-2 的 i2/i3/i4 完成。

Figure 8: JCT Performance under LLaMA-7B #

Figure 8: JCT LLaMA-7B

What it shows: 在 1×/2×/3× 负载强度下，Justitia 与 5 个 baselines（vLLM FCFS、vLLM-SJF、Parrot、VTC、SRJF）的平均 JCT 和 P90 JCT。

Why it matters: 这是论文的 主结果图——Justitia 明显优于所有 fair baselines（VTC/Parrot），并逼近 SRJF（效率上界）但无 SRJF 的 starvation 问题。

Detailed description: 左子图 Avg JCT、右子图 P90 JCT；每组 6 个柱子对应 6 个调度器，随负载强度递增柱高递增。3× 下 Justitia Avg ≈ 300s，VTC ≈ 700s，Parrot ≈ 770s，SRJF ≈ 290s。

Figure 10: CDF of Finish-Time Fair Ratio #

Figure 10: Fairness CDF

What it shows: 3× 负载下各调度器的公平率（realistic JCT / VTC JCT）的 CDF。

Why it matters: 这是 公平性证据——Justitia 有 92% 的应用 ratio ≤ 1（比 VTC 更早完成），最坏 ratio 仅 1.26；vLLM/Parrot/vLLM-SJF 的 CDF 长尾严重，大量应用 ratio > 2 甚至 > 10（因 head-of-line blocking）。

Detailed description: 横轴 Fair Ratio (0-10)，纵轴 CDF (0-1)。Justitia 曲线在 1.0 处迅速逼近 0.92，1.26 处到 1.0；VTC 严格在 ratio=1 处跳到 1.0（作为基准）；SRJF 类似 Justitia 但有更长尾；vLLM/Parrot 曲线平缓上升，很多在 5-10。

Figure 11: Starvation Micro-benchmark (Elephant + Mice) #

Figure 11: Starvation

What it shows: 先提交 1 个大 MapReduce-Summarization（elephant），再每秒提交小的 KBQAV/CC/ALFWI（mice）。横轴 mice 数量 (100/300/500)，纵轴 elephant 的 JCT。

Why it matters: 证明 Justitia 没有 SRJF 的 starvation 问题——elephant JCT 在 Justitia 下基本不随 mice 数增加（延迟有界），而 SRJF 下随 mice 数量线性增加（饥饿加剧）。

Detailed description: 两条柱状图系列。SRJF 的 elephant JCT 从 100 mice 时的约 400s 增长到 500 mice 时的约 800s；Justitia 维持在 200-300s 附近几乎平坦。

Key Tables #

Table II: MLP vs Distillbert Prediction Comparison (2× workload) #

Prediction ModelAvg Relative Error (%)Avg Inference Overhead (ms)Avg JCT (s)Training Time
MLP53.02.16151.1~1 min
Distillbert45255.7366.7~2 h

Takeaway: per-app 小 MLP 在误差（8.5× 更准）、预测延迟（25× 更快）、端到端 JCT（2.4× 更低）、训练时间（120× 更快）全面碾压 Distillbert 单模型；这也解释了为什么 "light-weight yet accurate" 不是空话。

Table III: Scheduling Overhead vs Arrival Rate #

Arrival Rate (app/min)15203050100
Scheduling Overhead (ms)0.7781.8273.0765.1908.093

Takeaway: 从 15 到 100 app/min（实际生产非常高的负载），调度延迟始终 < 10ms，相对秒级 LLM 推理可忽略；这是 $O(\log N_t)$ 堆操作 + 常数更新的直接体现。

Infrastructure Impact #

Deep Analysis (framework) #

1. System Scope #

2. Architecture & Data Flow #

2a. End-to-End Data Flow #


[User submits App] → [Per-app TF-IDF Vectorize] → [Per-app MLP predict C_j]
                           ↓                              ↓
                    [Compute V(a_j)]  →  [virtual finish time F_j = V(a_j)+C_j]
                           ↓
                    [Insert into min-heap keyed by F_j]
                           ↓
                    [On scheduling tick:
                       pick app with smallest F_j that has inference pending
                       allocate all remaining KV-blocks it needs
                       vLLM's existing paged attention + continuous batching runs]
                           ↓
                    [App completes → remove from heap → pick next]
StageInput → OutputLocationLatencyData format
TF-IDF vectorizeprompt text → feature vecCPUµssparse float vec
MLP predictfeature vec → KV token-timeCPU~2.16 msscalar (int)
V(t) updateΔt, N_t → ΔVCPUO(1)scalar
Heap insertF_j → ordered queueCPUO(log N_t)min-heap
KV allocationnext app's inferencesGPU HBMvLLM scheduler tick (~10ms)block ids
Inference exectokens → KV + logitsGPU10-50 ms/tokenpaged KV

2b. Data Movement Hotspots #

  1. prompt text → CPU MLP (once per application arrival, < 1KB, CPU-local). 不是瓶颈。
  2. KV-block allocation bitmap refresh (每个 scheduling tick，几百到几千 entries，CPU 完全可控)。
  3. 无新增 GPU↔GPU 流量——Justitia 只改变 "哪个请求先进 batch"，不触碰 TP/PP 通信路径，因此与 DistServe/DualPipe 等正交。

    4. 3. Design Space & Constraint Analysis #

    3a. Alternative approaches considered & rejected

    AlternativeFailure Mode
    FCFS at inference level (vLLM 原生)Head-of-line blocking：一个长 decode 阻塞一串短推理
    FCFS at application level (Parrot)应用级 HoL blocking 不减少，只是换了粒度
    VTC (instantaneous fair share)短期公平约束死应用上限 = $M/N_t$，错过 "独占吃饱" 的加速
    SRJF on predicted cost饥饿 —— mice 不断到达，elephant 永久延迟
    模拟 VTC 得到完成顺序需要未来请求全信息 + 每次到达/完成重算，成本 $O(N_t^2)$ 以上
    纯 virtual-time without demand prediction$F_j = V(a_j) + C_j$ 里没有 $C_j$，退化为到达顺序（FCFS）
    用 Distillbert (S³) 做成本预测55.7ms 预测 + 66M 参数训练，2h 训练成本；误差 452% 过大

    3b. Constraint Derivation

    • 为何不可纯 SJF？ —— SJF 理论上最优，但缺乏延迟保证；当存在长应用 + 源源不断的短应用时，长应用会饥饿。Justitia 的 virtual finish time 同时编码了 到达时刻 $V(a_j)$ 与 成本 $C_j$，使得即使是长应用，其 $F_j$ 也 不会被更晚到达的短应用超越（因为短应用的 $V(a_k) > V(a_j)$）。这是 Justitia 与 SRJF 的根本差别。
    • 为何不可 compute-centric 成本（VTC 的 $p+2d$）？ —— 在 vLLM 中瓶颈是 KV 显存而非算力：当一个 batch 的总 token 数 = $B \cdot L$ 达到 $M$ 时，新请求无法加入，必须 swap。compute-centric 成本低估了 长 decode 的显存占用扩张 — 一条 decode 从 100 tokens 涨到 2000 tokens，显存占用增 20×，但 VTC 里只记为 +1900 个 token 单位（忽略了 占用时长 $d$ 的乘法效应）。
    • 为何需要 per-app MLP 而非全局模型？ —— 不同应用的 cost 分布差异极大（如 FV 的 generate-queries 输入固定在 360-380 tokens，而 MRS 输入横跨 0-600+）；单一模型被平均化，per-app 模型利用了 application-specific similarity。

    3c. Assumption audit

    AssumptionWhere usedWhen it breaks
    应用类型已知且有 100 样本的 profileMLP 训练新应用冷启动无数据；用户自定义 agent 工作流
    prompt 尺寸 $\ll M$（< 3.20% 实测）证明 $f_j - \bar f_j \le 2c_{\max}+C_{\max}/M$128K+ 单 prompt 占比 > 20% 时延迟界松弛
    非抢占粒度足够细vLLM 非抢占原语单条 decode 数分钟时优先级颠倒
    $C_j$ 可预测Virtual finish timeSC/PE 这种 reasoning-depth 动态应用预测不准
    GPS 完成顺序 = 实际最优顺序WFQ 定理网络世界的 WFQ 假设 packets 相互独立；LLM 推理有 shared-prefix 复用时成本模型偏高

    3d. Core Technical Barrier

    真正的核心壁垒不是 virtual-time 算法，而是 KV token-time 这个成本度量的"量纲选择"本身——把时间 × 空间的 KV 占用变成一个可加的标量 $C_j = \sum_i (p_i d_i + d_i^2/2)$。这个度量有三个巧妙之处：

    (1) 它是 加性 的（一个应用 = 各推理求和），天然适配 WFQ 的 $F_j = V(a_j) + C_j$；

    (2) 它的量纲与 virtual time 兼容（$M/N_t$ 表示 "每单位时间每应用得到的 KV blocks"，乘以时间恰好就是 KV token-time）；

    (3) 消融实验 Fig.12 显示去掉它退化 42.3%——单是这个度量就贡献了近半增益。换言之，哪怕别人照抄 WFQ 和 per-app MLP，如果用 VTC 的 $p+2d$ 做成本，效果也不会如此显著。

    3e. Design binding critique

    Forced dependencyFlexibility lost
    必须运行在 vLLM 的非抢占 paged attention 上不能直接搬到 SGLang 的 radix tree + prefix cache（因为 cost 公式没建模 shared prefix 复用）
    每类应用单独训一个 MLP应用类型必须事先定义，agentic system 里 prompt template 频繁变化时维护成本大
    假设应用是 task-parallel 结构（fanout + join）不支持长 DAG reasoning（如 Tree-of-Thoughts 分支数运行时决定）
    单全局队列多 GPU 集群里需要额外的全局/局部虚拟时间同步，论文未设计

    4. Key Innovations #

    InnovationMechanismBenefitCost/Tradeoff
    Memory-centric KV token-time$c = pd + d^2/2$成本度量与 vLLM 真实瓶颈（KV cache）对齐，消融显示贡献 42.3% JCT不支持 prefix caching 与 P-D 分离场景下的成本偏差
    Per-app TF-IDF + 4-layer MLP每应用独立模型，100 样本、1 分钟训练预测误差 53%（vs Distillbert 452%）、开销 2.16ms（vs 55.7ms）需要云端 profile 数据；冷启动无 fallback
    Virtual-time based fair queuing (from WFQ)$V(t)$ 率 = $M/N_t$，$F_j = V(a_j)+C_j$，一次性确定避免 refresh、$O(\log N_t)$ 调度、理论常数延迟界仅在非抢占 vLLM 下成立，假设 GPS 完成顺序 ≈ 真实最优
    Saturated serving (trade short-term fairness)被选中的应用独占所有剩余 KV blocks近似 SJF 效率（57.5% JCT 降）并发度骤降时单请求尾部 latency 可能变高

    5. Scheduling & Resource Management #

    • Batch formation: 继承 vLLM 的连续 batching；Justitia 只是改变 "等待队列出队顺序"，同时被选中的应用里的多条推理 不被其它应用的推理打断，除非 KV 耗尽进入 swap。
    • Memory management: paged KV（vLLM 原生），Justitia 不动内存管理，只决定谁先分配。
    • GPU utilization: 通过 saturated serving 让被选中的应用尽可能填满 KV 空间，避免 VTC 下每个应用只用一半造成的 batch 变小、计算 utilization 下降。
    • Multi-tenancy / isolation: 有——每个 app 视为一个 tenant，常数延迟界给出 worst-case 隔离。
    • SLO-aware: 未显式支持优先级 tier，但可通过赋予不同 $C_j$ 权重扩展。

    6. Target Scenarios & Workload #

    ScenarioPatternSLO / GoalExisting systems fail because
    MapReduce summarization几十条并行 prefill + merge低 JCT、公平vLLM FCFS → HoL；VTC → 每条只占 1/N 资源变慢
    Self-Consistency reasoningN 条并行 CoT rollout低 JCT（majority vote 出最后答案）SRJF 会饿死长 rollout
    Fact Verification (FacTool)claim-by-claim 验证端到端 JCTParrot FCFS app-level → 跟在大 app 后面被阻塞
    Multi-tenant shared GPUelephant + mice 混合保证 elephant 不饥饿SRJF → elephant 饥饿；FCFS → mice HoL

    Primary bottleneck: memory-bound（KV cache capacity）——作者明确在 §IV-A 说 "inference throughput is bounded commonly on the GPU memory"。这是整篇设计的根基。

    7. Performance Evaluation #

    7a. Metrics #

    MetricDefinitionDirection
    Avg JCT应用到达到所有推理完成的平均时长↓
    P90 JCT90% 分位 JCT↓
    Finish-time fair ratiorealistic JCT / VTC JCT↓（< 1 即优于 VTC）
    Scheduling overhead每应用到达/完成的调度决策耗时↓
    Prediction error预测 - 真实/ 真实↓

    7b. Before-After Comparison #

    OptimizationMetricBaselineJustitiaGainConditions
    Virtual-time WFQ (vs VTC)Avg JCT— (VTC)57.5% 下降2.35×LLaMA-7B A100, 300 apps, Mooncake trace
    WFQ (vs Parrot FCFS)Avg JCT— (Parrot)61.1% 下降2.57×same
    Memory-centric cost (vs Justitia/C)Avg JCTJustitia/C~42.3% 下降1.73×2× workload, same hw
    MLP predictor (vs Distillbert)Pred error452%53%8.5× betterper-app data
    MLP predictor (vs Distillbert)Pred overhead55.7ms2.16ms25.8× fastersame
    Justitia (vs SRJF in elephant+mice)Elephant JCT线性发散有界bounded delaymicro-bench

    7c. Bottleneck Shift Analysis #

    
Before: HoL blocking (Parrot FCFS)     → scheduling-bound
      ↓ apply WFQ with virtual time
Intermediate: short-term fair sharing (VTC) → underutilization-bound
      ↓ trade short-term for long-term fairness, saturated serving
Justitia: memory-bound (KV cache capacity,  still)

    调度侧基本榨干，剩余瓶颈回到 KV cache 物理容量 $M$ 与单条推理时长 $c_{\max}$ — 这也是 $f_j - \bar f_j \le 2c_{\max}+C_{\max}/M$ 里两个常数的来源。

    7d. Baselines & Fairness #

    • 5 个 baselines 覆盖 FCFS / SJF / app-FCFS / app-fair / app-SJF 五个象限，设置公平（同 hw、同 trace、同 workload mix）。
    • workload: 3× 负载强度下 Justitia 优势最大（6min 提交窗口 = 最拥挤）；1× 下 Justitia 与 VTC 差距缩小到 ~30%，因为竞争少时 VTC 的短期公平约束不 binding。
    • Framework overhead: Table III 显示 100 app/min 下仅 8ms，< 1% 单请求时间。
    • Where baselines win?: 论文没明确承认，但可以推测：单应用独占 / 无竞争时 VTC = Justitia = FCFS；长 DAG dynamic fanout（像 ToT） 下 Justitia 的预测失效，可能输给 SRJF + 后期 refresh 版本。

    8. API & Usability #

    • API: 继承 vLLM HTTP/gRPC API，增加 application_id + application_type 字段让客户端声明应用类别。
    • Model format: vLLM 支持的全部（HF、safetensors）。
    • Deployment: 单节点即可部署；集成点是 vLLM 的 Scheduler 类替换。
    • Tuning knobs: MLP 结构（层数/宽度）、TF-IDF vocab 大小、per-app 训练样本数。默认 4 层 MLP + 100 样本已够用。
    • 冷启动: 论文未解答——推测用应用类型的 default priority（如 input 长度作为 proxy）。

    9. Infrastructure Impact #

    LayerImpact
    Algorithm不涉及 training 算法；但对 RL rollout、best-of-N 等 inference-time 算法的调度提供更好底座
    Kernel无改动
    LLM模型无关，但假设是标准 Transformer + KV cache；MLA / absorb-style 架构下 KV token-time 公式需要调整
    Agent强相关——本质就是 agent-workload 调度器，可与 ReAct、ToT、MCTS 等 runtime 集成
    Ops新增 per-app profiling pipeline；scheduling 决策可 log 用于审计

    10. Comparison Matrix #

    FeatureJustitiavLLMSGLangParrotVTCFairServe
    Continuous batching继承✓✓继承继承继承
    Paged attention继承✓✓ (+RadixAttention)继承继承继承
    App-level scheduling✓✗部分 (via programs)✓ (FCFS)✓ (fair)✓ (fair)
    Fairness guarantee常数延迟界无无无短期公平短期公平
    Cost predictionper-app MLP无无无无 (按 token 记账)无
    Memory-centric cost✓———✗ (compute-centric)✗
    Starvation-free✓✓✓✓✓✓
    Avg JCT (relative to VTC, 3×)0.425×~1.5×—~1.1×1×类似 VTC

    11. Adoption, Maturity & Ecosystem Influence #

    • Open source: 论文未给出 release plan；作者来自上海交大 IPADS/CS 系，过去的调度工作（如 Themis 的 fair ratio 定义）通常开源。
    • Community: 当前 arXiv preprint（2025-10-19），尚未被主流系统（vLLM/SGLang）采纳；但 WFQ 思路已被 VTC 的后续工作 FairServe 间接借鉴。
    • Production deployments: 无报告。
    • Adoption path: 可作为 vLLM 的第三方 scheduler plugin 发布，需要与 vllm.core.scheduler 的 API 对齐。
    • Downstream influence prediction: 三点可能被下游采纳——
    • KV token-time cost 度量 最通用，可直接用于 SLO-aware 调度、autoscaling；
    • Per-app MLP demand predictor 与 S³、Learning to Rank (ICLR'25) 形成同一方向，可能合流为一个"prediction-aware scheduler"子领域；
    • Virtual-time 作为 LLM 调度器优先级 是新创，值得进 vLLM 主线评估。

    Open Questions #

    • 在 prefix caching / SGLang RadixAttention 下，KV token-time 公式如何修正？是否应改为 $\sum_i (p_i - p_{\text{shared}_i}) d_i + d_i^2/2$？
    • 在 disaggregated prefill/decode (DistServe) 下，prefill 和 decode 各自的 KV 占用时间差异巨大，单一 cost metric 是否还适用？
    • 对 dynamic fanout 应用（ToT、MCTS、agentic loop）中 $C_j$ 未知的情况，是否能用 online learning / bandit 边跑边修正 virtual finish time？
    • 在 多节点集群 中，全局虚拟时间 $V(t)$ 的同步成本是否会让 O(log N) 优势消失？
    • 与 SLO-aware 优先级（如付费用户）结合时，是否仍能保持常数延迟界？WFQ 本身支持 weighted 版本，但论文未评估。

    Connections to Knowledge Base #

    • VTC (Sheng 2024, arXiv:2401.00588) — 最直接的 baseline，Justitia 在成本度量和 fair queue 策略上都 override 了 VTC。
    • Parrot (Lin OSDI'24) — 同样做 app-level 调度但 FCFS；Justitia 在此基础上引入 finish-time fair-ordering。
    • S³ (Jin NeurIPS'23) — output length 预测 baseline；Justitia 用 MLP 替换 Distillbert。
    • FastServe (Wu arXiv:2305.05920) — MLFQ 多级反馈队列；Justitia 用 WFQ 避免 MLFQ 的频繁队列切换开销。
    • Themis (Mahajan NSDI'20) — finish-time fairness 概念的原创；Justitia 把它从 DL 训练 cluster 搬到 LLM serving。
    • Parekh-Gallager GPS (IEEE ToN 1993) — WFQ 的原始定理；Justitia 是其在 LLM serving 场景的非平凡移植。
    • Mooncake (Qin arXiv:2407.00079) — 提供了 trace 和碎片化 3.20% 的实测依据；未来 Justitia 若与 Mooncake 的 kvcache-centric 分离架构集成，可作为 application-level 上层调度器。