Position: Scaling LLM Agents Requires Asymptotic Analysis with LLM Primitives

Elliot Meyerson, Xin Qiu

TL;DR

This paper argues that to effectively scale LLM-based agent systems, we need to move beyond intuitive task decomposition and adopt "asymptotic analysis with LLM primitives" (AALPs). This approach treats LLM forward passes as the fundamental computational unit, allowing us to analyze the efficiency of agent orchestration independent of LLM internals and unlock significant scaling advantages.

What Problem Does This Paper Address?

The current trend in AI development involves building complex systems by composing multiple Large Language Models (LLMs) into "agents" that handle specific sub-tasks. While this decomposition is often based on human intuition (like assigning roles in a team), its optimality for scaling is unclear. The paper addresses the critical question of how to design and analyze these agent systems to achieve maximum efficiency and scalability, especially as the complexity and number of tasks increase dramatically. Without a formal framework for understanding this scaling behavior, we risk developing systems that are inefficient or hit fundamental limitations.

Methods

The core methodological proposal is Asymptotic Analysis with LLM Primitives (AALPs). This framework involves:

  • Defining LLM Primitives: Treating a single LLM forward pass (generating a token) as the atomic unit of computation. The cost of this primitive is assumed to be proportional to the model size ($m$) and input length ($n$), i.e., $mn$.
  • Language-based Algorithms (LbAs): Defining any algorithm where one or more computational steps are performed by an LLM as an LbA. These are essentially systems of LLM-based agents.
  • Oracle Decomposition: Assuming the existence of a programmatic way to decompose a problem into subproblems, without specifying how this decomposition is achieved. This allows for theoretical analysis of the decomposition's impact on efficiency.
  • Asymptotic Analysis: Analyzing the computational cost (e.g., tokens, FLOPS, time, money) as the problem size, complexity, or number of instances grows towards infinity. This helps identify scaling trends that might be hidden by overheads at smaller scales.

The paper uses this framework to analyze three example scenarios: k-task routing, iterative code debugging, and evolutionary optimization, comparing "optimistic" (intuitive) approaches with "optimized" (AALPs-informed) ones.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and conceptual frameworks rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Beyond Intuition: Human intuition for task decomposition in LLM agents might not be optimal for scaling. Formal asymptotic analysis is needed to guide efficient design.
  • LLM Primitives as the Key: By abstracting LLMs to their fundamental forward pass cost, we can analyze the orchestration of agents, separating it from the LLM's internal efficiency improvements. This allows for orthogonal improvements.
  • Specialization Trumps Generalization at Scale: For tasks involving many distinct sub-problems (like k-task routing), using specialized, smaller LLMs for each task is asymptotically more efficient than a single large, generalist LLM.
  • Decomposition is Crucial for Debugging: In code debugging, breaking down the problem into fixing individual functions (rather than processing the entire codebase repeatedly) leads to massive asymptotic speedups, highlighting the power of fine-grained decomposition.
  • Local vs. Global Optimization: For optimization tasks, applying LLMs to modify individual components (local mutation) is vastly more efficient at scale than applying them to the entire solution (global mutation).
  • Cost Focus: The analysis suggests that for scaling LLM agent systems, minimizing the cost of specialist agents and optimizing decomposition strategies are more critical than solely focusing on the size of a central delegator agent.

Key Results

The paper presents theoretical analyses demonstrating significant asymptotic improvements through AALPs:

  • k-Task Routing: A delegator-specialist approach offers a speedup that scales linearly with the number of tasks ($k$) compared to a generalist approach.
  • Iterative Code Debugging: A focused approach where agents operate on individual functions yields a speedup of $\Theta(b k^2)$ for debugging, where $b$ is the number of bugs and $k$ is the number of functions, compared to a naive approach.
  • Evolutionary Optimization: Local mutation offers an enormous relative performance improvement of $\Theta(2^k k)$ over global mutation for a specific optimization problem.

These results are qualitative demonstrations of potential speedups rather than precise quantitative benchmarks, aiming to highlight the importance of the analytical approach.

Limitations and Future Work

Limitations:

  • Simplified Assumptions: The analysis often relies on simplified assumptions, such as linear cost scaling of LLM primitives, perfect problem decomposition (oracle decomposition), and reliable LLM execution (no errors).
  • Focus on Inference: The paper primarily considers inference costs and largely disregards LLM training costs, assuming inference dominates at scale.
  • Theoretical Framework: The paper presents a minimal framework and calls for further development.

Future Work:

  • More Nuanced Assumptions: Developing AALPs to handle more realistic assumptions about LLM costs, error rates, and decomposition messiness.
  • Stochasticity and Error Correction: Incorporating LLM errors and developing error-correction mechanisms within agent systems.
  • Asynchrony and Distributed Algorithms: Analyzing the benefits of asynchronous and distributed agent execution.
  • Automatic Decomposition: Developing LLM-based methods for automatically discovering optimal decompositions.
  • Extensions to Other Modalities: Adapting AALPs to systems involving vision, audio, and other modalities.
  • Online Learning and Adaptation: Incorporating the cost of learning and adaptation within deployed agent systems into the analysis.
  • Ethics and Sentience: Exploring how highly decomposed systems might reduce the risk of machine suffering.

Summary updated

Abstract

Decomposing hard problems into subproblems often makes them easier and more efficient to solve. With the high cost of running LLMs at scale, 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 problem decompositions, and that insights from such analysis will unlock opportunities for scaling such systems. 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