PaperlayerView exact revision on arXiv

Source-linked AI summary

Scaling Small Agents Through Strategy Auctions

Lisa Alazraki, William F. Shen, Yoram Bachrach, Akhil Mathur

arXiv:2602.02751v3cs.MAcs.AIcs.CL

TL;DR

Small agents match larger ones on simple tasks but do not scale reliably with task complexity, leaving open how to route heterogeneous agents efficiently. The paper introduces SALE, a test-time strategy-auction framework with shared-memory refinement, and finds improved pass@1 with lower cost and reduced reliance on the largest agent across deep search and coding.

  • Problem

    The paper addresses how agent performance changes with task complexity and how to route heterogeneous agents to balance accuracy and cost on long-horizon workloads.

  • Method

    SALE has off-the-shelf agents bid with strategic plans, scores bids by cost and value, and refines them using shared auction memory without training a separate router.

  • Results

    Across deep search and coding tasks, SALE improves the strongest agent’s pass@1 while reducing total cost and shifting substantial workload away from the largest model.

  • Takeaways & Limitations

    The findings indicate that coordinating heterogeneous agents through adaptive allocation and test-time learning can scale the workload handled by smaller agents without sacrificing accuracy.

  • Takeaways & Limitations

    The evaluation covers deep search and coding but not all agent applications, and complexity-scaling analysis uses only the Qwen3 model family.

Abstract

from arXiv · show

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.

1 Introduction

Small agents can approach large-agent performance on simple tasks but diverge as complexity grows, creating a need for cost-aware routing across heterogeneous agents. SALE addresses this through strategy auctions that combine per-task allocation with test-time refinement from shared auction memory.

  • Existing routing approaches struggle with agentic workloads because full-trace execution is expensive and task descriptions poorly predict long-horizon outcomes.
  • SALE evaluates agents’ strategic plans using predicted cost and value, then selects and executes a winning plan for each task.
  • SALE refines candidate strategies using outcomes stored in shared auction memory, coupling routing with test-time self-improvement.
  • Small agents closely match large agents on simple tasks but diverge sharply as task complexity increases.
  • SALE achieves a better performance–cost Pareto frontier than individual agents and existing routers on deep search and coding tasks.

2 Related Work

Related work studies agent scaling with task duration, routes among heterogeneous systems, uses memory for adaptation, and explores market mechanisms for coordinating agents.

  • Agent Performance Under Task Complexity: Prior agent-scaling studies connect capability to task duration or examine performance degradation as tasks become more demanding.
  • Multi-Agent Routing: Routing methods are commonly divided into non-predictive selection after multiple models run and predictive selection based on inputs or learned policies.
  • Memory-Driven Adaptation: Memory systems typically improve individual agents by reusing successful routines or retaining structured records of prior interactions.
  • Agent Systems as Virtual Economies: Prior work also proposes auctions, virtual economies, and direct transactions as mechanisms for coordinating autonomous agents.

3 Experimental Setup

The experiments benchmark Qwen3 agents across deep search and coding tasks, measuring complexity with expert human solution time and evaluating performance across five complexity bins.

  • Experiments run in the standardized Agent Research Environment to compare agent behavior consistently across domains.
  • The evaluation covers deep search and coding tasks representing extended reasoning, information integration, multi-step planning, and precise execution.
  • Task complexity τ(t) is defined as the average time expert annotators require to solve each task.
  • Tasks are grouped into five non-overlapping bins ranging from 0 < τ(t) ≤0.1 to 12.5 < τ(t) ≤60 minutes.
  • The study uses Qwen3 agents with 4B, 8B, 14B, and 32B parameters, assigning effective prices of $0.05, $0.09, $0.16, and $0.36 per million tokens.

4 Agent Performance vs. Task Complexity

Small and large agents perform similarly on low-complexity tasks, but the gap widens as deep-search and coding tasks become harder. Larger agents therefore help on complex workloads, while universal deployment wastes resources on simpler tasks.

  • Performance is measured with pass@1 using LLM-as-a-judge evaluation against ground-truth answers.
  • On the simplest tasks, the cheapest agent reaches about 87% of the most expensive agent’s pass@1 for deep search and about 92% for coding.
  • As task complexity increases, performance differences between cheaper and more expensive agents become increasingly pronounced.
  • As complexity rises, all models use more tokens, and larger agents do not consistently produce shorter traces than smaller agents.
  • Cheaper agents are effective for low-τ(t) tasks, whereas complex workloads expose their limitations and make universal largest-model deployment inefficient.

5 Strategy Auctions

SALE routes tasks by scoring agents’ strategic plans on cost and value, then refines eligible bids using shared auction memory before executing one selected agent. Its min–max scoring objective and lightweight auction process target efficient, robust assignment for complex agentic workloads.

  • Strategy Auctions: SALE interprets each agent’s strategic plan as a task-specific bid, using strategic intent rather than task descriptions alone for model selection.Plans are generated for the task and environment, then scored to support routing.
  • Cost and Value Assignment: Strategy cost combines agent token price, strategy length, and a tuned weight.Strategy length is used as a proxy for total inference cost because it correlates with final trace length and longer plans can increase failed-execution waste.
  • Cost and Value Assignment: Strategy value combines normalized token entropy with self-and-peer jury judgments scored from 0 to 5.Entropy supplies an intrinsic signal, while jury assessments provide extrinsic quality evaluation; ablations find that removing self-evaluation or shrinking the jury degrades performance.
  • Winning Bid Selection: SALE selects the agent with the lowest cost-minus-value score, with weights learned through a min–max objective that protects against poor assignments on individual training tasks.The same scoring rule is applied to route new tasks after training.
  • Strategy Refinement from Auction Memory: Shared auction memory stores winning and losing strategies, enabling cheaper unselected agents to retrieve relevant examples, refine bids, and compete again.Refinement is opportunistic rather than applied to every agent by default, and the best improved bid replaces the provisional winner only when it improves the trade-off.
  • Execution and Overhead: The auction executes only the selected agent’s winning strategy, while its added inference cost remains under 1% of total inference cost on average.The auction phase uses a few hundred tokens, compared with final agentic traces that typically consume tens of thousands to millions of tokens.

6 Results

SALE is evaluated across deep-search and coding tasks with randomized test-set orders, comparing its performance–cost trade-offs against single agents, established routers, and a no-memory ablation. Across complexity levels, it improves or maintains accuracy while reducing cost, and its gains advance the performance–cost frontier.

  • Table 1 reports pass@1 and price per million tokens across complexity bins, with SALE results averaged over five randomized test-set orders.
  • SALE exceeds the best single agent on complex deep-search tasks by 3.8 pass@1 points while reducing cost by 36%.
  • SALE improves complex coding pass@1 by 3.3 points while operating at 19% lower cost than the best single agent.
  • Across both domains and complexity levels, SALE dominates the single-agent Pareto frontier with statistically significant improvements robust to randomized task orderings.
  • Established routers trade off accuracy and cost less effectively: WTP modestly reduces deep-search cost by 11% but usually underperforms the best single agent, while FrugalGPT degrades as complexity rises.
  • Without memory-based self-refinement, SALE still matches or improves the best single agent’s average pass@1 while reducing effective cost across all complexity bins.

7 Analysis

SALE’s analysis shows that workload allocation, auction memory, and indirect agent contributions jointly support efficient coordination. Smaller agents handle meaningful fractions of tasks and become more competitive over time, while refined strategies exhibit domain-specific improvements.

  • 7.1 Agent Allocation: In deep search, smaller agents receive substantial workload shares across complexity bins, with 4B and 8B agents together processing nearly 30% even in the highest-complexity bin.
  • 7.2 Agent Contributions via Shapley Values: Shapley values measure each agent’s average marginal contribution across coalitions, including direct execution and indirect effects through jury and memory roles.
  • 7.2 Agent Contributions via Shapley Values: Without memory, the largest agent has the highest Shapley values across domains and complexity bins, while smaller agents can contribute indirectly through judgment and memory.
  • 7.1 Agent Allocation: The 4B agent’s cumulative selection share rises from 3.7% to 11.1% in deep search and from 1.4% to 5.3% in coding as auction memory grows.
  • 7.1 Agent Allocation: Memory-guided refinement reuses recurrent structures from winning bids, adding explicit tool use and search checks for search tasks and precise functions and testing for coding tasks.
  • 7.3 Complementary Failure Modes: Complementary failure modes arise because the largest agent sometimes bypasses tools, over-engineers simple problems, or skips verification, whereas simpler strategies can succeed.

8 Conclusion

The paper finds that small agents match larger agents on simple tasks but fall behind as complexity increases, motivating coordinated allocation rather than universal reliance on the largest model. SALE uses test-time strategy auctions and shared memory to improve accuracy, reduce cost, and shift work toward smaller agents.

  • Smaller agents perform comparably to larger ones on simple deep-search and coding tasks but fall substantially behind on more complex instances.
  • SALE lets heterogeneous agents bid with strategic plans, scores bids using cost–value criteria, and refines them through shared auction memory without training a separate router.
  • Across deep search and coding, SALE improves the strongest single agent’s pass@1 while reducing cost and shifting substantial workload away from the largest model.
  • The conclusion frames agentic capability as an emergent property of coordination, workload allocation, compute pricing, and adaptation among heterogeneous agents.

Limitations

The evaluation covers deep search and coding, while several limitations constrain how broadly the findings should be interpreted: model-family scope, auction-memory scale, and cost accounting. These boundaries leave generalization to other task families, larger or shifted memories, and tool-cost settings for future work.

  • Task coverage: Deep search and coding cover complementary agentic capabilities but do not span all applications of agentic systems.The passages identify data analysis and long-form report writing as examples requiring future evaluation.
  • Model scope: The scaling analysis uses a single Qwen3 family, from 4B to 32B parameters, to isolate model-size effects from architectural and training differences.The authors state that cross-family comparisons would confound scale effects with architecture, tokenizer, and training recipe differences.
  • Memory scaling: Auction-memory retrieval was not studied at much larger scales, across model-version upgrades, or under task-distribution shift.The memory bank grows linearly with the number of tasks; approximate nearest-neighbor indexing and utility-based retention are proposed for larger or changing settings.
  • Cost accounting: Cost accounting focuses on language-model tokens and does not explicitly price tool calls.The cost function can be extended with tool-related features or a blended cost-per-step metric when tool costs are non-negligible.

Broader Impacts

The paper frames SALE as a coordination mechanism for heterogeneous models and discusses its implications for efficiency, access, and dual use. It presents marketplace language as a methodological metaphor rather than a model of human labor markets.

  • Contribution: SALE coordinates heterogeneous models to allocate work efficiently across agentic systems.The paper presents this as a contribution to understanding how task complexity mediates agent effectiveness and to allocating work across models.
  • Marketplace metaphor: The marketplace analogy is methodological: bids, competition, and feedback organize allocation among software components.The framework does not model human workers or recommend substituting them with AI.
  • Efficiency: 52% lower reliance on the largest agent and 35% lower overall inference cost indicate more efficient computational-resource use.The paper connects these reductions to routing simpler tasks to smaller models without degrading performance.
  • Access: Coordinated ensembles of smaller, less expensive models may lower the cost barrier to deploying capable agentic systems.The paper cautions that efficiency benefits are not automatically equitably distributed and depend on deployment context.
  • Dual use: More efficient agentic systems are dual-use, potentially amplifying both beneficial and harmful applications by lowering capability costs.The authors do not identify risks unique to SALE beyond those already present in underlying language models and agentic frameworks.

A.1 Data Composition

HST-Bench combines open-source deep-search and coding benchmarks, assigning instances to complexity bins using average human solution time. Separate development sets and quality-controlled annotations support evaluation and tuning.

  • Benchmark composition: HST-Bench spans open-source deep-search and coding benchmarks, supplemented by a Coding-MCQ corpus for low-complexity coding instances.Samples come from official test splits, with validation and domain restrictions for selected datasets.
  • Complexity annotation: Instances are assigned to five non-overlapping complexity bins according to their average human solution time.The bins shift from short-form factual QA and Coding-MCQ toward multi-source reasoning and iterative coding workflows.
  • Development sets: The deep-search and coding development sets contain 68 and 88 disjoint instances, respectively, selected for balanced mixtures of model successes and failures.These sets support validation and tuning rather than final testing.
  • Human-time annotation: Human solution times are collected from at least three proficient annotators per task and filtered through correctness checks and outlier control.The annotation protocol specifies standardized tools, timing, and reporting procedures across domains.
  • Annotation protocol: Annotators solve deep-search and coding examples under timed, domain-specific procedures that permit web search but prohibit AI assistants.Coding tasks require a Python shell, while search tasks use Google or Bing and record completion time.

D.3 Implementation Details

SALE combines learned cost–value scoring, strategy refinement, and auction memory to allocate agents. The procedure adds little overhead while improving selection behavior under tool costs and producing stronger final outcomes.

  • Learned weights: Entropy receives the highest learned weight across both domains, indicating that strategy information density is a strong expected-performance signal.Judge-model importance varies by domain.
  • Auction scoring: SALE minimizes a learned cost-minus-value objective, jointly weighting strategy cost, entropy, and judge-based value without hard constraints.The objective favors agents that are both efficient and effective, while avoiding a manually chosen quality threshold.
  • Tool-aware allocation: 52% relative reduction: increasing tool-latency penalties lowers the 32B agent’s allocation share from 23% to 11%.The 14B agent rises from 18% to 28%, reflecting a stronger cost–value trade-off under tool latency.
  • Strategy refinement: Auction memory retrieves contrastive prior outcomes so cheaper agents can refine initial strategies before final assignment.Representative examples show refined strategies becoming more constrained and checkpointed, with successful downstream answers.
  • Overhead: 669 additional tokens for deep search and 1042 for coding represent under 1% of total token consumption.The full auction phase also takes approximately 1% of the final trace’s wall-clock time.
  • Evaluation: SALE achieves significantly higher pass@1 than all baselines across both task types, with large effect sizes and bootstrap confidence-interval support.The supplied result reports all |t| > 5 and p < .005.

G.1 Baseline Implementation Details

The baseline comparison covers four routers with different prediction and cost-trade-off mechanisms. SALE shifts the accuracy–cost frontier outward across nearly all complexity settings, while oracle comparisons show remaining routing headroom.

  • Baseline routers: WTPRouter uses nearest-neighbor retrieval over sentence embeddings and a willingness-to-pay parameter to select models by performance–cost trade-off.Its configuration uses 50 cosine-distance neighbors with all-MiniLM-L6-v2 embeddings.
  • Baseline routers: CARROT predicts per-model success probabilities with a RoBERTa classifier and selects models using a tunable performance–cost score.TO-Router similarly predicts model performance with a BERT encoder, while FrugalGPT combines correctness scoring with cascade optimization.
  • Accuracy–cost trade-off: SALE shifts the deep-search Pareto frontier outward for every complexity value and improves coding trade-offs in all bins except τ ≤0.5.WTP can achieve lower coding cost only with substantial accuracy degradation.
  • Oracle comparison: At τ(t) ≤60, the oracle reaches 25.0 pass@1 on deep search versus 16.3 for SALE, and 34.2 versus 26.1 on coding.The oracle selects the smallest agent producing a correct answer and otherwise defaults to the smallest agent.
  • Oracle comparison: SALE has the smallest oracle accuracy gap among evaluated methods: 10.6 points on deep search and 7.3 points on coding.Baseline gaps range from 14.1–16.9 points on deep search and 10.0–18.3 points on coding.

H.2 Routing Diagnostics

SALE’s routing errors are dominated by over-escalation rather than under-escalation, especially on easier tasks. As complexity rises, unavoidable failures increasingly replace opportunities for cheaper correct routing.

  • Diagnostic categories: Routing diagnostics classify decisions as correct, over-escalation, under-escalation, or unavoidable when no agent succeeds.These categories compare SALE’s selected agent with the oracle assignment.
  • Deep search: In deep search, 65.1% of 14B selections and 61.0% of 32B selections could have been handled by 4B according to the oracle.Under-escalation is infrequent, while 4B selections have the highest overall diagonal accuracy at 54.0%.
  • Deep search: Deep-search over-escalation from 32B to the 4B oracle falls from 86.2% at τ ≤0.1 to 16.7% at τ ≤12.5 and near-zero at τ ≤60.The hardest bin instead has a dominant “none” column reaching 73–100%, indicating mostly unavoidable failures.
  • Coding: In coding, 55.2% of 14B selections and 31.5% of 32B selections could have been handled by 4B, with another 25.0% of 32B selections mapping to 8B.SALE’s 4B selections are predominantly correct, and under-escalation remains limited.
  • Implications: Further improvement requires reducing over-escalation on low-complexity tasks, while SALE’s conservative errors preserve accuracy and under-escalation remains rare.The diagnostic interpretation identifies unnecessary escalation, rather than insufficient model capacity, as the main routing opportunity.

I.1 Cost–Value Function Ablations

Ablation results show that every cost–value component contributes to SALE’s performance, while jury diversity and memory-based refinement are especially important for robust, efficient allocation.

  • Cost–Value Function: Every ablated cost–value term lowers pass@1 across deep search and coding tasks.Deep-search ablations also increase average cost, whereas some coding ablations lower cost only by selecting smaller models at an accuracy penalty.
  • Cost–Value Function: Removing jury scoring causes the largest deep-search performance drop, averaging −3.6 pass@1 and reaching −7.6 on the most complex bin.Coding is more sensitive to removing price and strategy-length terms than to removing the jury.
  • Jury Ablations: Replacing the full jury with one judge reduces overall Pass@1 from 67.3 to 65.0–66.4 for deep search and from 61.1 to 59.0–60.5 for coding.Single judges also cost more for deep search, and no individual judge consistently dominates; the full jury’s diversity provides more robust decisions with negligible overhead.
  • Jury Ablations: Removing any individual judge lowers pass@1, with the 4B judge’s removal causing coding’s largest decline of −2.9 pass@1.This indicates that judges contribute complementary signals beyond individual judging strength.
  • Feedback Ablations: Peer judgment is more important than self-judgment: removing peer judgment reduces coding pass@1 to 48.7, while removing self-judgment remains near the best single-agent baseline.The full system still performs best on both deep search and coding.
  • Memory Ablations: Enabling memory lowers 32B reliance from 35% to roughly 17% and raises refined-plan jury scores by approximately 0.3 points.Further memory increases yield only small improvements, while a sliding window of about 10–25 recent tasks remains effective.

J.2 Predictiveness of Task Success

The supplied passages support that jury scores predict downstream success and that auction memory shifts selection toward cheaper agents over time. The remaining task-specific examples concern agent strategies and outcomes rather than a separate predictiveness result.

  • Predictiveness of Task Success: Jury scores correlate 0.36 with binary task accuracy on the full development set, with p < 0.01.This correlation is reported as good item discrimination and complements human-alignment results.
  • Agent Selection Over Time: Cheaper agents receive more opportunities for memory-based refinement because refinement occurs when a more expensive agent is the provisional winner.The 4B and 8B agents refine strategies on over 90% of samples in both domains, while the 14B refines on 62% of deep-search and 77% of coding samples.
  • Agent Selection Over Time: As auction memory accumulates, the 4B agent’s cumulative selection share rises while the 14B share mildly declines across deep search and coding.The 8B share increases for deep search but remains relatively flat for coding.

L.2 Performance Comparison on Coding Tasks

The coding examples show that the largest agent can fail through unnecessary complexity or constraint violations, while smaller agents can choose simpler, more robust strategies. SALE’s allocation mechanism also transfers across model families.

  • Coding Performance Comparison: The 32B coding agent over-engineers straightforward problems, while the 4B agent correctly identifies a fixed two-level structure.Unnecessary complexity increases the surface area for errors.
  • Coding Performance Comparison: The 32B agent may import unavailable library functions, whereas the 14B agent chooses a simpler approach consistent with task constraints.This illustrates how parametric knowledge can conflict with the allowed implementation environment.
  • Cross-Family Allocation: SALE routes 80% of the hardest coding tasks to Gemma 27B, while easier tasks distribute work more evenly across agent sizes.This matches the complexity-sensitive allocation observed for Qwen3 32B and the finding that smaller agents suffice at low complexity.
  • Cross-Family Allocation: Cross-family jury scores correlate strongly between size-matched Gemma 3 and Qwen3 agents, with Spearman ρ ∈[0.45, 0.76].Strategy-length distributions and entropy also converge or correlate across families despite differing absolute scales.
  • Cross-Family Allocation: When Llama 3.1 8B and Ministral 3 8B join the Qwen3 pool, their cost-minus-value rankings correlate with Qwen3 8B rankings at ρ = 0.40, p < 0.01.The jury remains the original Qwen3 panel, isolating transfer of global cost and entropy weights to heterogeneous bidders.
Loading 2602.02751v3…