Position: Scaling LLM Agents Requires Asymptotic Analysis with LLM Primitives

Elliot Meyerson, Xin Qiu

TL;DR

Current multi-agent LLM systems are largely designed using human-centric intuition rather than algorithmic rigor, leading to massive hidden inefficiencies. This position paper introduces Asymptotic Analysis with LLM Primitives (AALPs), a formal framework that treats the LLM forward pass as the atomic unit of computational cost. By analyzing agent architectures mathematically, the authors demonstrate that shifting from intuitive, anthropomorphic designs to rigorous, modular problem decompositions can unlock order-of-magnitude efficiency gains critical for scaling AI.

What Problem Does This Paper Address?

As large language models (LLMs) become more reliable, developers are increasingly orchestrating them into multi-agent systems—for instance, creating a "QA Engineer" agent that chats with a "Software Developer" agent to write code. However, these systems are typically designed based on human analogies (e.g., how a human software team interacts) rather than algorithmic efficiency.

The paper addresses the lack of a formal complexity theory for these Language-based Algorithms (LbAs). Without a mathematical foundation akin to classical Big-O analysis, we risk building agent networks that hit severe scaling walls due to compounding token lengths, bloated prompt histories, and unnecessarily massive model sizes.

Methods

The authors propose a minimal theoretical framework called Asymptotic Analysis with LLM Primitives (AALPs). The core components include:

  • LLM Primitive: The fundamental unit of cost, defined as a single execution of an LLM generating a token. The cost is modeled as $m \times n$, where $m$ is the model size (parameter count/capability) and $n$ is the input context length.
  • Capabilities Set: The specific scope of tasks a given model can reliably perform. This formalizes the idea that smaller, specialized models can replace giant, expensive generalist models if the task is narrow enough.
  • Oracle Decomposition: An assumed, non-LLM operation used during analysis to represent the ideal way a large problem can be split into subproblems.

The paper applies this framework to three common agent use cases—task routing, code debugging, and evolutionary optimization—comparing a naive "anthropomorphic" approach against an optimized, structurally decomposed approach.

Datasets

Not discussed in the paper. As a purely theoretical position paper, it introduces a mathematical framework and conceptual case studies rather than empirical evaluations on datasets.

Key Insights and Ideas

  • Stop Anthropomorphizing AI Workflows: Designing multi-agent systems to mimic human conversations (e.g., passing an entire chat history back and forth) is asymptotically disastrous. It causes context lengths to explode quadratically.
  • Specialization Yields Linear Speedups: For a system handling $k$ distinct tasks, routing inputs to $k$ tiny specialized models yields a $\Theta(k)$ efficiency improvement over using a single massive generalist model, because a model's required size scales with the number of capabilities it must hold.
  • Extreme Decomposition is Mandatory: In code debugging, forcing an agent to rewrite an entire codebase to fix a single bug scales terribly. Breaking the codebase down into independently specified functions isolates the agent's focus, dropping the asymptotic cost dramatically.
  • The Exponential Trap of Global Mutation: When using LLMs for optimization (like generating prompt variations), mutating an entire solution at once results in an exponential expected cost ($\Theta(2^k)$). Isolating mutations to local blocks reduces this to polynomial time, making large-scale optimization practical.

Key Results

The paper proves massive theoretical separations in efficiency between naive and optimized agent architectures, summarized in the table below:

Overview of the three example problems comparing optimistic vs. optimized agent architectures.
  • $k$-Task Routing: Shifting from a single generalist to a delegator with specialized agents yields a $\Theta(k)$ relative improvement.
  • Iterative Code Debugging: Moving from a naive conversational multi-agent setup to a focused, function-level debugging setup yields a $\Theta(bk^2)$ improvement (where $b$ is the number of bugs and $k$ is the number of functions).
  • Evolutionary Optimization: Transitioning from global text mutation to localized block mutation transforms an impossible exponential expected cost into a linear one, achieving a $\Theta(2^k k)$ improvement.

Limitations and Future Work

The authors acknowledge several simplifications in their initial framework that represent vital directions for future research:

  • Simplified Cost Models: The current framework assumes linear cost scaling and ignores superlinear transformer attention mechanics or fixed overheads like system prompts.
  • Stochasticity and Errors: The basic framework assumes agents always succeed. Real-world LLMs make mistakes, meaning future AALPs must incorporate probability and error-correction theory (similar to quantum computing or information theory).
  • Automatic Decomposition: The optimized examples rely on an "oracle" to split problems perfectly. A critical open challenge is analyzing the cost of using LLMs to automatically decompose tasks on the fly.
  • Dynamic Learning: The framework currently treats models as static during inference, ignoring the computational costs of online learning, memory retrieval, and real-time fine-tuning.

Summary updated

Abstract

Decomposing hard problems into subproblems often makes them easier and more efficient to solve. With large language models (LLMs) crossing critical reliability thresholds for a growing slate of capabilities, there is an increasing effort to decompose systems into sets of LLM-based agents, each of whom can be delegated sub-tasks. However, this decomposition (even when automated) is often intuitive, e.g., based on how a human might assign roles to members of a human team. How close are these role decompositions to optimal? This position paper argues that asymptotic analysis with LLM primitives is needed to reason about the efficiency of such decomposed systems, and that insights from such analysis will unlock opportunities for scaling them. By treating the LLM forward pass as the atomic unit of computational cost, one can separate out the (often opaque) inner workings of a particular LLM from the inherent efficiency of how a set of LLMs are orchestrated to solve hard problems. In other words, if we want to scale the deployment of LLMs to the limit, instead of anthropomorphizing LLMs, asymptotic analysis with LLM primitives should be used to reason about and develop more powerful decompositions of large problems into LLM agents.
BibTeX
@inproceedings{meyerson2025position,
  author = {Elliot Meyerson and Xin Qiu},
  title = {{Position: Scaling LLM Agents Requires Asymptotic Analysis with LLM Primitives}},
  booktitle = {International Conference on Machine Learning},
  year = {2025},
  url = {https://openreview.net/forum?id=LEYmr1TsBW},
}
Figure