SKYAPI: structural-aware orchestration for LLM-based multi-agent systems

The proliferation of Large Language Models (LLMs) has catalyzed the development of Multi-Agent Systems (MAS) capable of autonomous reasoning and complex workflow execution. These systems heavily rely on third-party inference APIs, where providers exhibit significant heterogeneity in latency and pricing. However, existing API routing strategies typically optimize requests in isolation, failing to account for the structural dependencies and synchronization barriers inherent in multi-agent collaboration. In this paper, we introduce SkyAPI, a structural-aware routing framework that shifts the optimization paradigm from per-query selection to stage-level orchestration. By decomposing dynamic agent workflows into ordered execution stages, SkyAPI employs a Mixed-Integer Linear Programming (MILP) formulation to explicitly optimize the trade-off between stage makespan and monetary cost. Furthermore, we propose a prefix-aware scheduling mechanism with Time-To-First-Token (TTFT) deferral to maximize KV-cache reuse among collaborative agents. Extensive evaluations on complex benchmarks, including DeepResearch and Gama-Bench, demonstrate that SkyAPI significantly outperforms state-of-the-art baselines, reducing operational costs by up to 3× while satisfying strict latency constraints across diverse model architectures.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois Urbana-Champaign

Year dc:date

2025

Author dc:creator

• Wang, Phillip

Contributors dc:contributor

• Lai, Fan

• Large Language Model
• Multi-agent System
• Optimization

Statement dc:rights

• Copyright 2025 Phillip Wang

Language dc:language

en

Handle dc:identifier

https://hdl.handle.net/2142/132596

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/132596