FAME: QoS-aware Async Service Orchestration for Agentic Workflows

Abstract

Agentic workflows built on Large Language Models (LLMs) increasingly rely on external tools, with Model Context Protocol (MCP) services emerging as a common interface for tool discovery and invocation. These workflows are stateful, bursty and can block for minutes to hours while external tools execute. Always-on virtual machines and managed agent runtimes simplify deployment, but can over-provision capacity, bill idle wait time or encounter execution limits for long-running tool calls. We present FAME, a service-oriented middleware that optimizes MCP-enabled agentic workflows through modular service orchestration, explicit state management, MCP service input/output reduction and timeout-safe async invocation for long-running external services. FAME realizes these composite services using FaaS-based agent roles, persists workflow state through agent memory injection, and reduces MCP service overhead using S3 handle passing and tool-output caching. For long-running external MCP tools, FAME checkpoints agent and orchestrator state, suspends execution and resumes from callbacks without billing idle waits. Across 26 short-running service tasks over 10 MCP servers, FAME improves service-level QoS by reducing infrastructure cost by 8-12x relative to virtual machines and 43-106x relative to managed runtimes, while reducing latency by up to 17x, input tokens by up to 88% and total cost by up to 66%. On two long-running MLZero workloads from MLE-Bench, FAME completes all iterations while synchronous AWS Step Functions time out, and is 3.64-4.24x cheaper than AWS Durable Functions at the agent level and 2.67-8.23x cheaper at the orchestrator level.

Extended version of paper to appear in the proceedings of the International Conference on Web Services (ICWS), 2026