TL;DR
NALAR is a new serving framework designed specifically for the "wild" nature of LLM agent workflows. By decoupling workflow logic from execution through metadata-rich "futures" and a two-level control plane, it enables dynamic scheduling and state migration, cutting tail latencies by up to 74% and achieving nearly 3x speedups over existing baselines.
What Problem Does This Paper Address?
Serving LLM agents is fundamentally harder than serving standard inference requests. While a typical LLM call is a single "shot," an agentic workflow is a long-running, stateful, and highly dynamic process. These workflows often involve multiple agents (e.g., a "Manager" and a "Coder") and various tools (web search, compilers, databases).
The authors identify three core challenges that current frameworks (like LangGraph, AutoGen, or Ray) struggle to solve simultaneously:
- Dynamic Control Flow: Agents don't follow a fixed graph; they branch, loop, and retry based on model outputs that are unpredictable at runtime.
- Complex Statefulness: Agents accumulate rich state over long sessions. If this state is "sticky" to a specific server, it creates load imbalances.
- Heterogeneous Latencies: A tool call might take milliseconds, while an LLM reasoning step might take minutes, leading to massive "head-of-line blocking" where short tasks get stuck behind long ones.
Methods
NALAR introduces a "ground-up" architecture built on three pillars:
- Lightweight Specification (Stubs & Futures): Developers write standard Python code. NALAR uses an automated tool to generate "stubs" for agents and tools. When called, these stubs return Futures—rich objects that carry dependency metadata. This allows the runtime to "see" the workflow's structure as it evolves without forcing the developer to define a static graph.
- Managed State Layer: NALAR provides
managedListandmanagedDictabstractions. By using these, the framework can decouple logical state from physical hardware. If a server becomes overloaded, NALAR can move the entire session—including its state—to a different node transparently. - Two-Level Control Architecture:
- Global Controller: Periodically evaluates the entire system to set high-level policies (e.g., "migrate this session to Node B").
- Local Controllers: Co-located with each agent/tool, these enforce policies in real-time based on local events (like a task finishing), ensuring the system stays responsive.
Datasets
The researchers evaluated NALAR across three diverse, real-world agentic workloads:
- Financial Analyst: Based on the FinQA dataset, involving multi-step numerical reasoning and stateful sessions.
- Router-based Workflow: Using Microsoft Azure LLM traces to simulate a system that classifies queries and routes them to specialized agents.
- Software Engineering Workflow: A recursive workflow based on MetaGPT and evaluated using the SWE-bench dataset, involving code generation, testing, and iterative bug-fixing.
Key Insights and Ideas
- Futures as Coordination Handles: Instead of just being placeholders for values, NALAR's futures act as the "glue" for the runtime. They allow the system to perform late binding—deciding where to run a task only when its dependencies are actually ready.
- Push-Based Readiness: When a future is resolved, the producing node immediately "pushes" the result to all consumers. This decentralized approach avoids the bottleneck of a single central coordinator.
- Policy-Driven Serving: One of the most powerful features is the ability to write custom scheduling policies in just a few lines of Python. For example, a developer can implement a "Shortest Remaining Time First" policy in 12 lines of code to optimize job completion times.
- K,V Cache Awareness: Because NALAR knows which requests are likely to arrive next based on the workflow's progress, it can provide "hints" to LLM engines (like vLLM) to keep specific K,V caches in memory, significantly reducing latency for multi-turn conversations.
Key Results
NALAR significantly outperforms popular baselines like AutoGen, CrewAI, and Ayo:
- Tail Latency: Reduced P95–P99 latencies by 34–74% in stateful workloads.
- Throughput: NALAR sustained 80 requests per second (RPS) in scenarios where baselines failed due to memory errors or extreme load imbalance.
- End-to-End Speedup: Achieved up to 2.9× speedup by dynamically reallocating resources to bottlenecked agents.
- Scalability: In emulation tests, the control plane scaled to 130,000 futures with less than 500ms of overhead, proving it can handle massive, complex deployments.
Limitations and Future Work
- Fault Tolerance: Like many current inference systems, NALAR does not yet have a robust mechanism for automatic recovery from system-level crashes (e.g., a node going down). The authors suggest this as a primary area for future work.
- Batching Constraints: Currently, "managed state" cannot be used with "batchable agents." This is because the framework cannot yet perfectly attribute state updates to individual requests when they are processed in a batch.
- Human-in-the-loop: While NALAR handles automated retries well, more work is needed to optimize the "human-in-the-loop" pattern where a workflow might pause for hours waiting for user input.
Summary updated