Scaling Small Agents Through Strategy Auctions

AI summary

Overview

• Research area: Multi-agent systems, specifically cost-aware routing and orchestration of heterogeneous large language model (LLM) agents under test-time compute budgets.
• Technical level: Intermediate. The paper assumes familiarity with LLM agents, pass@1 evaluation, and routing baselines, but its auction mechanism is described in accessible terms; the underlying optimization (min–max over scoring weights) is more advanced.
• Scope: The paper empirically shows that small LLM agents' performance fails to scale with task complexity, and proposes a marketplace-inspired auction framework (sale) that routes tasks across agents by scoring short strategic plans rather than full task descriptions.

What This Paper Is About

There is a growing belief that small, cheap language models are "good enough" to power agentic AI. This paper tests that belief by measuring how the performance gap between small and large agents changes as tasks get harder, using human solution time as a proxy for complexity. It then asks how a system should allocate work across a pool of agents of different sizes and costs, and answers with an auction in which agents bid with short strategic plans that are scored for predicted value and cost.

Key Contributions

1. An empirical study of the small-versus-large agent gap under task complexity. The authors evaluate deep search and coding tasks across multiple horizons and find that small agents nearly match large ones on simple tasks but diverge sharply as complexity grows. They state that this is the first such investigation on realistic workloads, since prior work examined agentic scaling only on synthetic tasks.
2. HST-Bench, a benchmark that pairs agentic tasks with human solution times as a complexity proxy, containing 753 tasks, with human solution times annotated by three expert annotators (Krippendorff's α = 0.86).
3. sale (Strategy Auctions for Workload Efficiency), an agent framework in which heterogeneous agents bid with strategic solution plans, are selected by a cost–value scoring rule learned via min–max optimization, and refine future bids using a shared auction memory of past wins and losses.
4. Evidence that strategy-based routing beats both single models and existing routers. The authors report that sale extends the performance–cost Pareto frontier beyond any individual agent in the pool, and that established routers either underperform the largest agent or fail to reduce cost, often both.

Main Findings

• Small-agent performance does not scale with task complexity. On the simplest tasks, the smallest agent attains roughly 90% of the largest agent's pass@1, but on the most complex tasks this relative performance drops to roughly 21%. Broken down by domain in Section 4: for deep search, the cheapest agent reaches about 87% of the most expensive agent's pass@1 at τ(t) ≤ 0.1, falling to 25% at τ(t) ≤ 60; for coding, about 92% falling to 17%.
• Larger agents are not more token-efficient on complex tasks. Token usage grows with τ(t) for all models, and larger agents do not consistently produce shorter traces than smaller ones; where their traces are shorter, the savings are too small to offset the higher per-token price.
• sale improves accuracy while reducing cost. The abstract reports a 52% reduction in reliance on the largest agent and a 35% reduction in overall cost, with pass@1 improvements of +3.5% on deep search and +2.7% on coding. The introduction reports workload offloading of −65% (deep search) and −40% (coding), with total spend reductions of −42% (deep search) and −25% (coding).
• Per-bin results favor sale across complexity levels. Aggregated over all deep search tasks, sale reaches 67.3 pass@1 at $0.21 per million tokens versus 63.8 at $0.36 for the best single agent; on all coding tasks, sale reaches 61.1 at $0.27 versus 58.4 at $0.36 for the best single agent. sale w/o memory reaches 66.4 at $0.24 (deep search) and 59.9 at $0.27 (coding). On the most complex bins, sale records 16.3 pass@1 (deep search, τ(t) ≤ 60) and 26.1 (coding, τ(t) ≤ 60).
• Existing routers fit agentic workflows poorly. Willingness-to-Pay (WTP) gives modest deep-search cost reductions (11% on average) but slightly underperforms the best single agent at most complexity levels, and on coding drops to 6.3% pass@1 at the highest complexity versus 22.8% for the best single agent. CARROT reduces cost by 22% on deep search and 14% on coding with only small accuracy drops but still trails sale. TO-Router tends to default to the strongest agent, leaving performance and cost close to the single-agent baseline. FrugalGPT matches or slightly exceeds the best single agent on low-complexity tasks but its pass@1 declines sharply as complexity rises while average spend increases, reaching $0.61/Mt on coding versus $0.36/Mt for the best agent.
• Auction overhead is negligible. Jury scoring and strategy refinement add only a few hundred tokens, and the auction phase accounts for under 1% of total inference cost on average in both token and wall-clock terms, while executing a final agentic trace typically consumes tens of thousands to millions of tokens.
• Small agents are selected more often as memory grows. The authors observe that the smallest agents are chosen increasingly often as the auction memory accumulates, suggesting they capitalize on accumulated experience.

Methodology in Plain English

The authors run everything inside the Agent Research Environment (ARE) with Qwen3 models at 4B, 8B, 14B, and 32B parameters, using greedy decoding. They assign each model a price per million tokens based on published API rates and an observed 4:1 input-to-output token ratio: $0.05 (4B), $0.09 (8B), $0.16 (14B), and $0.36 (32B).

To measure difficulty, they ask three expert annotators to record how long each task takes a human to solve, then sort tasks into five bins with average human solution times of up to 6 seconds, 30 seconds, 2.5 minutes, 12.5 minutes, and 60 minutes. The bins progress geometrically (5× between adjacent bins).

The routing mechanism treats each agent like a freelancer bidding on a job:

1. Each agent writes a short strategic plan (a "bid") for the task rather than solving it fully.
2. Each bid gets a cost estimate, based on the agent's price per million tokens times the plan's token length, and a value estimate, which combines the plan's normalized per-token generation entropy with 0–5 Likert quality scores assigned by all agents in the pool acting as a jury (including the bidding agent itself).
3. The task goes provisionally to the agent with the lowest cost-minus-value.
4. Agents cheaper than the provisional winner may then revise their bids using a shared memory of similar past tasks, formatted as contrastive pairs of losing and winning strategies retrieved by cosine similarity over text embeddings.
5. If a refined bid beats the provisional winner's cost-minus-value, the refined agent wins instead; otherwise the provisional winner is kept and its strategy is executed.

The scoring weights are fit by a min–max optimization that minimizes the worst-case cost-minus-value across a training set of tasks, which the authors describe as guarding against any single task receiving a disproportionately poor assignment.

Evaluation uses pass@1 scored by LLM-as-a-judge against ground-truth answers. Because sale's memory evolves online and task order matters, all sale metrics are averaged over five independent random permutations of the full test set, with single runs reported for single-model baselines. Baselines (WTP, CARROT, TO-Router, FrugalGPT) are trained on the same split used to set sale's scoring weights.

Task sources: deep search draws on SimpleQA, PopQA, HotpotQA, GAIA, and an expert-validated portion of Humanity's Last Exam; coding draws on MBPP and LeetCode plus custom multiple-choice questions for lower-complexity cases.

Why This Matters

• For research: The paper argues against treating small-agent adequacy as a global yes/no question, and instead frames model size as a per-task decision. It also connects agent orchestration to market-design ideas, proposing that routing feedback can double as a self-improvement mechanism that raises the effective capability of small models.
• Real-world applications:
  • Cost-controlled deployment of deep-research assistants, where easy lookups run on small models and only long-horizon investigations escalate.
  • Coding assistants and automated debugging pipelines, where simple snippet fixes are handled cheaply and multi-step refactors route to larger models.
  • Inference-serving platforms that host a pool of open-weight models and need to decide which model handles each incoming agent request without running all of them.
  • Any agentic product with a hard compute budget that wants to increase throughput without abandoning accuracy on the hardest requests.
• Industry relevance: The framework requires no separately trained routing model and applies to off-the-shelf agents, making it attractive for teams that swap models frequently or cannot afford to fit and maintain predictive routers. The reported under-1% auction overhead is directly relevant to serving economics, since agent traces can span tens of thousands to millions of tokens.

Future Directions

• Scaling and generalizing the agent pool. The study uses four Qwen3 sizes; it is an open question how the auction behaves with many more agents, across different model families, or with agents that differ along dimensions other than size and price.
• Understanding memory dynamics. The authors observe that the smallest agents are selected more often as memory grows but do not characterize how far this trend extends, whether it plateaus, or what memory contents drive it.
• Extending beyond deep search and coding. The paper evaluates two domains; whether the same plan-bidding signal is reliable in other agentic settings, such as computer use or long tool-use chains, is not reported.
• Market-design questions. The framework uses a centralized scoring rule and a mixed self-and-peer jury; properties such as incentive compatibility, robustness to agents that write strategically inflated plans, and alternative auction formats remain open.

Target Audience

Researchers and engineers working on multi-agent systems, LLM routing, and test-time compute scaling; practitioners responsible for the cost and latency of deployed agentic products; and readers interested in applying market-design or auction ideas to coordination among AI models. The paper is most useful to those already comfortable with pass@1 evaluation and agent benchmarks, though the framework itself is described in intuitive marketplace terms.

Authors’ abstract

Small language models are increasingly viewed as a promising, cost-effective approach to agentic AI, with proponents claiming they are sufficiently capable for agentic workflows. However, while smaller agents can closely match larger ones on simple tasks, it remains unclear how their performance scales with task complexity, when large models become necessary, and how to better leverage small agents for long-horizon workloads. In this work, we empirically show that small agents' performance fails to scale with task complexity on deep search and coding tasks, and we introduce Strategy Auctions for Workload Efficiency (SALE), an agent framework inspired by freelancer marketplaces. In SALE, agents bid with short strategic plans, which are scored by a systematic cost-value mechanism and refined via a shared auction memory, enabling per-task routing and continual self-improvement without training a separate router or running all models to completion. Across deep search and coding tasks of varying complexity, SALE reduces reliance on the largest agent by 52%, lowers overall cost by 35%, and consistently improves upon the largest agent's pass@1 with only a negligible overhead beyond executing the final trace. In contrast, established routers that rely on task descriptions either underperform the largest agent or fail to reduce cost, often both, underscoring their poor fit for agentic workflows. These results suggest that while small agents may be insufficient for complex workloads, they can be effectively "scaled up" through coordinated task allocation and test-time self-improvement. More broadly, they motivate a systems-level view of agentic AI in which performance gains come less from ever-larger individual models and more from market-inspired coordination mechanisms that organize heterogeneous agents into efficient, adaptive ecosystems.