💻 computer science

Rethinking Query Optimization for Multi-Agent Systems [Vision]

This paper introduces NOMA, a novel query optimization framework for multi-agent data pipelines that addresses the unique challenges of heterogeneous data models and variable topologies by jointly optimizing topology, model, and engine choices to significantly reduce cost and latency while improving quality, as demonstrated by empirical findings of extreme inefficiencies in current ad hoc approaches.

Original authors: Zoi Kaoudi, Ioana Giurgiu

Published 2026-07-08

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Zoi Kaoudi, Ioana Giurgiu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the manager of a massive, high-tech kitchen where a team of chefs (called "agents") works together to prepare complex meals based on customer orders. In the past, these kitchens ran on fixed recipes: Chef A always chops, Chef B always cooks, and they always use the same ovens. But now, with the rise of powerful AI tools (Large Language Models), these kitchens have become chaotic. You have dozens of different chefs, some are human-like AI, some are traditional database robots, and they can talk to each other in endless ways.

The paper "Rethinking Query Optimization for Multi-Agent Systems" argues that our current way of running these kitchens is broken. We are just guessing which chef does what, which oven to use, and in what order, leading to wasted money, slow service, and sometimes bad-tasting food.

Here is the paper's vision, explained simply:

1. The Problem: The "Guessing Game" is Too Expensive

The authors ran a real-world experiment with a 10-chef team handling customer support reports. They tested thousands of different ways to organize the team. The results were shocking:

Cost: Some team setups cost 153 times more than others to run.
Speed: Some setups took 5 times longer to finish the same task.
Quality: The accuracy of the final report varied by 25%.

The Metaphor: Imagine you need to drive from New York to Boston. Currently, developers just pick a car and a route based on habit. They might drive a massive truck on a backroad (expensive and slow) when a small sports car on the highway (cheap and fast) would have been perfect. The paper shows that the "best" route isn't obvious; it's a weird mix of a small car for part of the trip and a fast train for another part that no human would ever think to plan manually.

2. The New Challenge: It's Not Just a Recipe, It's a Living Thing

In old database systems, the "recipe" (the plan) was fixed. The optimizer just decided the order of steps.
In this new AI world, the recipe itself is a variable.

Topology: Should Chef A talk to Chef B directly, or should they go through a manager? Should they work in a line or a circle?
Model Selection: Should we use a cheap, fast AI for simple tasks and a super-expensive, smart AI for hard tasks?
Engine Selection: Should this task run on a supercomputer or a standard server?

The paper argues that you can't optimize these separately. You have to solve them all at once, like trying to solve a Rubik's cube where the colors keep changing.

3. The Solution: NOMA (The "Smart Kitchen Manager")

The authors propose a new framework called NOMA. Think of NOMA as a super-intelligent kitchen manager that doesn't just follow a recipe but invents the best recipe every single time an order comes in.

NOMA works through four main tricks:

The Creative Generator (Variable Search): Instead of trying every possible combination (which is impossible), NOMA uses AI to imagine new team structures. It might say, "Let's merge these two chefs into one super-chef," or "Let's split this task into two smaller steps." It creates plans that humans wouldn't think of.
The Crystal Ball (Unified Cost Models): It predicts the future. It estimates how much money, time, and quality a specific team setup will produce. But because AI is unpredictable (sometimes it makes mistakes), this "crystal ball" doesn't just give a single number; it gives a range of possibilities to account for uncertainty.
The Mid-Flight Pilot (Continuous Refinement): In old systems, once the plane takes off, you can't change the route. In NOMA, the system watches the chefs as they work. If a chef is struggling or the data looks weird, the manager can instantly change the plan for the remaining steps. It's like a pilot who reroutes the plane mid-flight to avoid a storm.
The Memory Bank (Semantic Caching): If the kitchen has already made a "chicken soup" for a customer, and a new customer asks for "a warm broth with chicken," the system recognizes they are the same thing (even if the words are different) and reuses the result. This saves huge amounts of money and time.

4. The Big Vision

The paper concludes that we need to stop treating these AI pipelines as static programs written once and forgotten. Instead, they should be self-evolving artifacts.

Just as a living organism adapts to its environment, NOMA envisions a system that constantly learns:

It learns which chefs work best together.
It learns when to use expensive tools vs. cheap ones.
It learns to save money by waiting for cheaper times to run tasks.

In short: The paper says, "Stop guessing. Let's build a system that automatically designs, tests, and improves its own team of AI workers to get the best results for the lowest cost, every single time."

Technical Summary: Rethinking Query Optimization for Multi-Agent Systems [Vision]

Problem Statement

The proliferation of Large Language Models (LLMs) has accelerated the adoption of multi-agent data pipelines, where agents collaborate to execute complex, data-driven tasks. However, current construction methods remain ad hoc, relying on fixed pipeline structures, pre-selected models, and single execution engines. This approach fails to systematically optimize across heterogeneous data sources and engines.

The authors argue that optimizing agentic pipelines is a fundamentally different problem from traditional query optimization due to four central challenges:

Multi-dimensional Search Space: Optimization must jointly determine pipeline topology, model selection, and engine assignment across competing objectives (latency, cost, and accuracy).
Variable Topology: The pipeline structure itself is a decision variable, not a fixed plan.
Lack of Common Algebra: The co-existence of structured data, unstructured text, embeddings, and streaming data eliminates a common operator algebra, preventing classical pruning techniques.
Stochastic and Expensive Execution: LLM calls incur significant monetary costs and exhibit variability in output quality, making naive exploration of the search space infeasible.

Methodology and Framework: NOMA

The paper presents NOMA, a vision for a query optimization framework designed specifically for multi-agent data pipelines. NOMA treats agents as first-class units of computation and extends classical optimization principles (cost modeling, plan generation, re-optimization) to a setting where plans are heterogeneous, stochastic, and structurally dynamic.

NOMA is conceptualized as an integrated optimization loop comprising four key components that reinforce one another:

Plan Generation: Instead of enumerating plans, NOMA proposes using generative models trained on historical pipelines to directly generate executable pipelines in the joint optimization space (topology, models, engines).
Unified Cost Estimation: The framework aims to build cost models that map heterogeneous agent features into a shared representation. Rather than scalar point estimates, these models predict calibrated distributions over latency, cost, and accuracy to account for the stochastic nature of agents and non-additive quality propagation.
Runtime Refinement: Optimization is treated as a continuous process. A "pipeline refiner" uses Bayesian optimization to update cost model priors based on agent completions and decides whether the expected gain of re-planning justifies the cost.
Semantic Caching: To address redundancy, NOMA proposes a cache that stores not just intermediate results, but also optimized sub-plans and configuration decisions. It indexes these artifacts semantically (using embeddings) rather than syntactically to enable reuse across structurally different pipelines.

Key Contributions and Results

The paper makes four primary contributions, supported by controlled experiments and real-world analysis:

Quantification of Suboptimal Costs:
- Experiment: A controlled experiment was conducted on a real-world 10-agent pipeline (involving customer support reporting) with 186,624 possible plans under a fixed topology.
- Findings: The plan space exhibited extreme variance: 153× in monetary cost, 5× in latency, and a 25% gap in quality.
- Observation: Optimal plans were heterogeneous configurations (e.g., mixing different LLMs based on task difficulty) that no user would construct manually. The Pareto frontier was rich, showing that a 19% quality improvement could cost 138× more, while a balanced plan could cut costs by 65% with minimal quality loss.
- Topology Impact: Modifying the topology (e.g., adding a conditional refinement loop) allowed the system to reach performance points outside the Pareto frontier of fixed-topology plans, proving topology is a critical optimization axis.
Analysis of Real Deployments:
- Scope: Analysis of 62 real agentic pipeline deployments and 9,000 constructed pipelines.
- Findings:
  - Complexity: Pipelines are growing in complexity (often 5–10+ tasks).
  - Habitual Selection: Model selection is driven by familiarity rather than cost-quality trade-offs; users reuse the same limited set of models.
  - Inefficient Topologies: Simple chains dominate (34%), failing to exploit parallelism or feedback loops.
  - Underutilized Engines: Engine assignment is rarely optimized, with most tasks running on default structured databases despite the availability of streaming or vector engines.
  - Redundancy: Core tasks (ingestion, extraction, reporting) recur frequently without shared computation.
Problem Formalization:
- The paper formally defines the Abstract Multi-Agent Pipeline (a logical graph of agents) and the Executable Multi-Agent Pipeline (a concrete graph with specific models, engines, and structural transformations like fusion, split, or reordering).
- The goal is defined as finding Pareto-optimal executable pipelines ( $G^*$ ) from an abstract pipeline ( $G$ ) under multiple objectives.
Research Agenda:
- The paper outlines specific open research questions for the community, including how to bootstrap training data for generative models without exhaustive exploration, how to reconcile heterogeneous cost signals into unified distributions, how to manage continuous optimization under stochastic execution, and how to define semantic equivalence for caching.

Significance and Vision

The paper claims that the current state of multi-agent pipelines is "fundamentally unoptimized" and that the gap between current practices and optimal performance is "severe and unavoidable."

The significance of NOMA lies in its proposal for a paradigm shift:

From Static to Adaptive: Moving from optimizing queries over fixed plans to continuously synthesizing and adapting pipelines.
Optimization as a Persistent Function: Optimization becomes a continuous system function rather than a pre-execution phase.
Self-Evolving Systems: As the system accumulates execution experience, pipeline configurations (topology, models, strategies) continuously rewrite themselves.

The authors position NOMA as a call to action for the database, systems, and machine learning communities to jointly address the challenges of query optimization for multi-agent systems, aiming to establish the foundations for a new class of optimizers that move beyond static pipelines toward adaptive, cost-aware execution.