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

Wang, Phillip

Permalink

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

Description

Title

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

Author(s)

Wang, Phillip

Issue Date

2025-12-09

Director of Research (if dissertation) or Advisor (if thesis)

Lai, Fan

Department of Study

Siebel School Comp & Data Sci

Discipline

Computer Science

Degree Granting Institution

University of Illinois Urbana-Champaign

Degree Name

M.S.

Degree Level

Thesis

Keyword(s)

• Large Language Model
• Multi-agent System
• Optimization

Abstract

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.

Graduation Semester

2025-12

Type of Resource

Thesis

Handle URL

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

Copyright and License Information

Copyright 2025 Phillip Wang

Owning Collections