PaperlayerView exact revision on arXiv

Source-linked AI summary

TOPAS: Workflow-Aware Prefix-State Scheduling for Multi-Agent LLM Serving

Hongqiu Ni, Han Tian, Chi Zhang, Guopeng Li, Haisheng Tan

arXiv:2608.25523v1cs.CL

TL;DR

Shared KV-cache budgets make prefix reuse and workflow progress competing scheduling objectives that affect task-level JCT. TOPAS jointly selects resident prefixes and admitted requests using a utility that balances remaining-path reduction, near-term reuse, and transition costs. Across synthetic DAGs and MetaGPT workflows, it reduces JCT versus the best-performing baselines, with the largest reported gains on synthetic workloads and MetaGPT-TL.

  • Problem

    Under a constrained shared KV-cache budget, serving systems must coordinate prefix residency and request admission because optimizing locality or workflow progress alone can prolong task-level JCT.

  • Method

    TOPAS jointly schedules resident agent prefixes and admitted requests using JCT-oriented utility that trades off remaining service-path reduction, near-term reuse, prefix movement, and preemption.

  • Results

    TOPAS reduces synthetic-workload mean/p99 JCT by up to 39.8%/49.4%, MetaGPT-SOP mean JCT by 9.8%, and MetaGPT-TL mean/p99 JCT by 22.0%/26.6% versus the best-performing baselines.

  • Takeaways & Limitations

    Explicitly coordinating prefix residency with request admission improves task-level JCT across the evaluated synthetic DAG and MetaGPT workloads.

Abstract

from arXiv · show

Prefix caching introduces a fundamental tradeoff in multi-agent large language model (LLM) serving: retaining a long system-prompt key-value (KV) cache for an agent accelerates future calls, yet it reduces the GPU memory available for batching concurrent requests. In multi-stage workflows, existing schedulers tend to prioritize either immediate prefix locality or overall workflow progress. However, under a shared KV cache budget, optimizing either objective in isolation can prolong tasklevel job completion time (JCT) through downstream delays or frequent prefix replacement. To strike a balance, we here propose TOPAS, a Task-Oriented Prefix-Aware Scheduler that jointly decides which agent prefixes to keep in the cache and which requests to schedule for execution. TOPAS scores candidate post-decision states by trading off the expected reduction in each task's longest remaining service path against the near-term benefit of downstream prefix reuse, accounting for the costs of prefix movement and preemption. A task-level aging mechanism is also incorporated to prevent starvation. We implement TOPAS within the SGLang framework and assess its performance on three synthetic DAGs and two MetaGPT software-development workflows. Compared with the best performing baseline for each workload and metric, TOPAS reduces the mean/p99 JCT by up to 39.8%/49.4% on the synthetic workloads, while lowering mean JCT by 9.8% on MetaGPT-SOP and mean/p99 JCT by 22.0%/26.6% on MetaGPT-TL.

I. INTRODUCTION

Multi-agent LLM workflows require coordinating prefix residency and request admission under a shared KV-cache budget because locality and workflow progress can conflict. TOPAS makes this coordination explicit and evaluates joint states using JCT-oriented utility, reuse, movement, preemption, and aging considerations.

  • Motivation: Multi-agent LLM requests use reusable agent-specific static prefixes, whose GPU residency avoids redundant prefill but competes with batching capacity.
  • Motivation: Existing schedulers operate mainly at request level, indirectly reflecting workflow dependencies and program-level progress.
  • Motivation: Locality-first and progress-first strategies create complementary problems: locality can delay downstream stages, while progress can incur prefix switching and movement overhead.
  • Problem formulation: The scheduling problem jointly selects resident prefixes and admitted ready requests under a shared KV-cache budget to minimize task-level JCT.
  • TOPAS: TOPAS treats prefix residency as an explicit workflow-level decision and searches compatible post-decision GPU states using a JCT-oriented utility.
  • Evaluation: 39.8%/49.4%: TOPAS reduces mean/p99 JCT by up to these amounts on synthetic workloads versus the best-performing baseline per workload and metric.

II. MOTIVATION: A PROGRESS–REUSE CONFLICT

The motivation experiments expose a conflict between batching through prefix reuse and advancing workflows through progress-first scheduling. Grouping same-agent requests improves capacity, whereas locality or progress alone can delay completion through upstream focus or prefix movement.

  • Prefix reuse and batching: GROUPED doubles the average running batch size, while ALTERNATING takes 1.8–1.9× as long to finish the same workload.
  • Prefix reuse and batching: Same-agent grouping lets one resident prefix support a larger batch; alternating divides KV capacity across prefixes and leaves less room for dynamic content and decoding.
  • Locality-first scheduling: LPM favors immediately reusable prefixes but can keep service near continuously arriving upstream stages, delaying downstream stages B and C.
  • Progress-first scheduling: SRPT advances shorter remaining work but repeatedly switches agents, causing prefix transfers or recomputation and reducing effective service capacity.
  • Progress–reuse conflict: In the A →B →C example, each stage transition changes the resident prefix and incurs another setup cost under SRPT.
  • Design implication: An effective scheduler must group requests for batching while moving to another prefix when continued reuse delays task completion.

III. PROBLEM FORMULATION

The paper formulates online prefix-state scheduling for minimizing average task-level JCT under online arrivals and constrained GPU memory. At each scheduling point, the system jointly selects resident prefixes and admitted requests while accounting for dynamic KV capacity and unknown future events.

  • Tasks execute stages in a known DAG, with each stage assigned to an agent and becoming ready after all predecessors complete.
  • The scheduler minimizes average task-level JCT under online arrivals.
  • At each scheduling point, the scheduler selects resident prefixes and admitted requests as a joint post-decision GPU state.
  • The joint state must fit a shared KV budget that includes dynamic-suffix KV, retained output tokens, and decode reservations.
  • Future arrivals, readiness events, ReAct iterations, and unexpanded tool outputs are unknown when scheduling decisions are made.

IV. TOPAS: WORKFLOW-AWARE PREFIX-STATE SCHEDULING

TOPAS replaces indirect request-level cache behavior with workflow-aware joint scheduling of prefixes and requests. It evaluates feasible transitions by balancing task-path progress against movement, repeated work, revocation, and preemption costs.

  • TOPAS treats prefix residency as an explicit workflow-level decision jointly optimized with request admission.
  • Candidate states are feasible only when their prefix and request allocation satisfies the joint KV capacity constraint.
  • The base utility rewards reductions in tasks’ remaining longest LLM-service paths and subtracts transition delay and work invalidated by preemption.All utility terms are measured in seconds.
  • TOPAS estimates task-path progress from empirical residual-service distributions, updating unfinished-stage residuals after hypothetical request completions.
  • Prefix movement accounts for incoming and outgoing caches, serialized transfers, and affected tasks waiting for incoming prefixes.
  • Repeated computation and revoked admission credit penalize preemption, while stored credit is cleared on completion and recreated on re-admission.

C. Short-Horizon Prefix Reuse

TOPAS adds a one-hop lookahead that values resident prefixes likely to serve downstream stages becoming ready soon. The lookahead is limited to one workflow transition because farther demand depends on unresolved runtime events.

  • TOPAS counts downstream stages assigned to each agent whose only unfinished predecessor is running, treating fork children separately and joins only when all other predecessors finish.
  • The lookahead values retaining an expensive prefix using its reload time and a pressure-strength parameter.
  • Lookahead stops after one workflow transition because farther demand depends on unresolved branches, ReAct rounds, and tool outcomes.

D. Task-Level Aging

TOPAS uses task-level aging to keep newer arrivals from repeatedly overtaking older tasks with similar progress. Aging scales only admission progress using normalized task age.

  • Task-level aging prevents new arrivals from repeatedly overtaking older tasks with similar progress.
  • The aging weight uses task arrival time, an observed service-time scale for normalization, and a strength parameter.
  • The admission term is age-weighted, and stored admission credit uses the same weight before revocation on preemption.

E. Hierarchical State Search

TOPAS separates prefix-set generation from request allocation, then selects among feasible joint states using an event-level score. Its hierarchical search enumerates small active-agent pools and bounds larger-pool exploration while accounting for admissions, preemptions, and reuse.

  • E. Hierarchical State Search: TOPAS generates feasible joint states by separating resident-prefix selection from request allocation under the shared KV budget.GREEDYPACK preserves covered running requests, derives preemptions, and admits fitting requests using age-weighted conditional progress.
  • E. Hierarchical State Search: For small active-agent pools, TOPAS enumerates all prefix sets; for larger pools, it uses greedy additions, pair tests, and repair operations.The bounded large-pool procedure limits prefix-set evaluations to O(|At|2).
  • E. Hierarchical State Search: The search caps admissions and preemptions separately, commits natural completions before search, and retains the incumbent state among generated candidates.Natural completions do not enter the preemption set.
  • E. Hierarchical State Search: At each scheduling event, TOPAS executes the highest-scoring feasible candidate and re-optimizes using progress, transition costs, and reuse value.The score estimates progress through expected remaining-path reduction under empirical conditional residual distributions.

A. Experimental Setup

The evaluation implements TOPAS in SGLang and compares it with five request- or task-level baselines across synthetic DAG and MetaGPT workloads. Mean and p99 task JCT are the primary metrics, with controlled synthetic workloads isolating topology and prefix-state pressure.

  • A. Experimental Setup: TOPAS is implemented as a scheduling module in SGLang v0.5.3 and evaluated on an NVIDIA A100 80GB GPU.
  • A. Experimental Setup: TOPAS averages 1.9 ms per scheduling decision, with cumulative scheduler time accounting for 0.31% of experiment wall time in a MetaGPT-SOP overhead run.
  • A. Experimental Setup: The study evaluates Chain-3, DAG-4, and DAG-10-Wide synthetic workloads spanning linear, fork/join, and wide execution structures.Fixed queries, generations, arrival traces, and shared model configuration isolate topology and prefix-state pressure.
  • A. Experimental Setup: The MetaGPT workloads use real prompts from the MetaGPT SoftwareDev dataset and include five-role SOP and nine-stage TeamLeader traces.MetaGPT-TL alternates a TeamLeader with four specialists to preserve recurrent reuse of the central prefix.
  • A. Experimental Setup: The comparison includes FCFS, Longest Prefix Match, Parrot-FCFS, Autellix Least-Attained Service, and Shortest-Path-First.
  • A. Experimental Setup: Mean and p99 task JCT are primary metrics, while first-task completion time and request throughput characterize initial progress and serving capacity.Workload-level comparisons average metrics over operating points and use the lowest-average baseline as comparator for each JCT metric.

B. End-to-End Task Completion

TOPAS improves task completion across synthetic DAGs and MetaGPT workflows relative to the strongest baseline for each workload and metric. Its gains are especially large under the TeamLeader workload’s recurrent central-prefix contention.

  • B. End-to-End Task Completion: 39.8% mean and 49.4% p99 JCT reductions are the largest synthetic-workload gains reported for TOPAS against the best-performing baselines.Across Chain-3, DAG-4, and DAG-10-Wide, mean reductions are 27.5%, 39.8%, and 27.7%, while p99 reductions are 31.7%, 49.4%, and 30.8%, respectively.
  • B. End-to-End Task Completion: 9.8% mean and 4.5% p99 JCT reductions accompany a 6.7% request-throughput increase on MetaGPT-SOP.These comparisons are reported against SPF for mean JCT.
  • B. End-to-End Task Completion: 22.0% mean and 26.6% p99 JCT reductions are achieved on MetaGPT-TL against the best-performing baselines for the two metrics.TOPAS pulls ahead as contention grows in the recurrent TeamLeader trace.

C. Ablations

The ablation compares TOPAS with reduced-component variants on MetaGPT-TL, while the broader context frames TOPAS as workflow-aware scheduling under prefix and GPU-memory contention. The full policy substantially outperforms its ablations at the reported operating point.

  • C. Ablations: 60.5% mean and 53.6% p99 JCT reductions separate full TOPAS from TOPAS-base on MetaGPT-TL.TOPAS-base retains base transition utility and joint-state search but omits future reuse and aging.
  • C. Ablations: 44.9–51.0% mean and 44.2–48.5% p99 JCT reductions show that both future reuse and aging contribute relative to single-component variants.
  • C. Ablations: TOPAS makes memory contention between resident agent-prefix caches and running requests part of workflow scheduling.This distinguishes it from systems that separately optimize workflow progress, cache availability, or resource placement.
  • C. Ablations: The overall contribution couples prefix residency with ready-request admission under a shared GPU-memory budget and balances progress, reuse, movement, and preemption.On the reported workloads, synthetic mean and p99 JCT reductions reach 39.8% and 49.4%, while MetaGPT-TL reductions reach 22.0% mean and 26.6% p99 JCT.
Loading 2608.25523v1…