Research map / Large language models / Agents, code and math
Position: Scaling LLM Agents Requires Asymptotic Analysis with LLM Primitives
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Position paper arguing that LLM-based agent systems should be analyzed asymptotically, treating an LLM forward pass (cost = model size × tokens) as the atomic primitive, illustrated with three toy analyses.
Problem
Multi-agent LLM systems are decomposed intuitively (by human-like roles), with no formal account of how their cost scales as problem size and instance count grow.
Approach
Proposes asymptotic analysis with LLM primitives (AALPs): counting LLM forward passes weighted by model size and input length as the atomic cost unit, separating the efficiency of agent orchestration from the internals of any LLM, and using oracle decompositions to show large asymptotic separations between naive and focused agent designs.
Key results
- For k-task routing, delegation to k specialists gives a speed-up that scales linearly with k: Θ(k) over a single generalist.
- For iterative code debugging with b bugs over k functions, focused decomposition gives a Θ(bk^2) improvement on the debugging expert's cost versus the naive multi-agent approach.
- For evolutionary optimization with OneMax-style blocks, local block mutation improves on global mutation by Θ(2^k k) in expected cost.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace one generalist with a delegator and task specialists | LLM system for k distinct tasks · k-Task routing | LLM primitive cost: \Theta(k) | Helped |
| Focus QA and debugging on one function at a time | Multi-agent code debugging · Iterative code debugging | LLM primitive cost: \Theta(bk^2) | Helped |
| Mutate one solution block at a time instead of the entire solution | LLM-based evolutionary optimization · Evolutionary optimization | LLM primitive cost: \Theta(2^k k) | Helped |
Surprising findings
- Analysis suggests it is more impactful to shrink specialist agents than the delegator, since the delegator is called far fewer times.
Limitations
- Analysis is intentionally loose and rests on strong assumptions such as perfect function specifications and reliable agent behavior.
- Ignores stochastic errors, asynchrony, and the cost of automatic decomposition by LLMs.
- No empirical validation of the asymptotic predictions on real LLM agent systems.
Experimental setup
Metrics: asymptotic cost (big-Theta) of LLM forward passes
Baselines: generalist single-LLM approach naive anthropomorphic multi-agent debugging (AutoGen-style) global mutation evolutionary search
Builds on: LLM-based algorithms mixture-of-experts routing (1+λ)-EA OneMax
Closest papers by meaning
- The Scaling Laws of Skills in LLM Agent Systems (NeurIPS 2026 · similarity 0.86)
- MM-Agent: LLM as Agents for Real-world Mathematical Modeling Problem (NeurIPS 2025 · similarity 0.85)
- Position: We Need An Algorithmic Understanding of Generative AI (ICML 2025 · similarity 0.84)
- Evaluating Test-Time Scaling of General LLM Agents (NeurIPS 2026 · similarity 0.84)
- LLMs Improving LLMs: Agentic Discovery for Test-Time Scaling (NeurIPS 2026 · similarity 0.84)
- UltraHorizon: Benchmarking LLM-Agent Capabilities in Ultra Long-Horizon Scenarios (ICML 2026 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.