Research map / Multi-agent systems and games / LLM agents

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

NeurIPS 2026 · Multi-agent systems and games › LLM agents · approach: Robust and efficient agent execution · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes Justitia, a scheduler for task-parallel LLM agents that orders agents by their virtual finish times under idealized fair sharing (GPS), using a memory-centric KV token-time cost model and per-agent-type MLP cost predictors.

Problem

Serving task-parallel LLM agents on shared GPUs requires both low average agent completion time and worst-case fairness guarantees, which existing FCFS, SJF, and instantaneous-fair schedulers fail to jointly provide.

Approach

Selectively prioritize agents in their finish-time-fair completion order (computed one-shot with virtual time from fair queuing), so each agent runs with full resources in turn; costs are measured as KV token-time (memory space x time) and predicted by a lightweight per-agent-type MLP over TF-IDF features.

Key results

• Average JCT under Justitia is 57.5% lower than VTC and 61.1% lower than Parrot on the mixed agent workload.
• 92% of agents finish under Justitia no later than under VTC, with worst-case delay of 26.0%.
• Compute-centric cost modeling (Justitia/C) degrades JCT by up to 42.3%; MLP predictor (2.16 ms overhead) beats DistilBERT (55.7 ms, ~2 h training) in JCT (151.1 s vs 366.7 s).

Surprising findings

• SRJF, a pure shortest-remaining-job-first policy, also achieves relatively good fairness because prioritized agents often cannot saturate the backend.
• Average prediction relative error of the MLP is still 53% despite its JCT advantage.

Limitations

• Prediction error remains high (about 53% average relative error), though performance is robust up to 3x scaling.
• Delay bound assumes prompt sizes are small relative to total KV cache, neglecting memory fragmentation.
• Agent cost predictors are per agent type and rely on stable demand across runs of the same agent type.

Experimental setup

Datasets: Mooncake production traces (arrival times) agent workloads from MapReduce Summarization, Plan-and-Execution, Code Checking, KBQA verification, Equation Verificatio

Benchmarks: mixed workload of 300 LLM agents across nine agent classes

Metrics: average JCT P90 JCT finish-time fair ratio prediction relative error scheduling overhead

Baselines: vLLM vLLM-SJF Parrot VTC SRJF Justitia/C Justitia-S3

Builds on: vLLM Virtual Token Counter (VTC) Generalized Processor Sharing / fair queuing S3 finish-time fairness

Closest papers by meaning

• A Two-Tier Perspective on Inference-Time Parallelism in Multi-Agent LLM Systems (ICML 2026 · similarity 0.87)
• CONCUR: High-Throughput Agentic Batch Inference of LLM via Congestion-Based Concurrency Control (ICML 2026 · similarity 0.87)
• ScaleSim: Serving Large-Scale Multi-Agent Simulation with Invocation Distance-Based Memory Management (ICML 2026 · similarity 0.87)
• Geometry-Aware Online Scheduling for LLM Serving: From Theoretical Bound to System Practice (NeurIPS 2026 · similarity 0.87)
• Evaluating Test-Time Scaling of General LLM Agents (NeurIPS 2026 · similarity 0.86)
• LRAgent: Efficient KV Cache Sharing for Multi-LoRA LLM Agents (ICML 2026 · similarity 0.86)