Source-linked AI summary
Markets, Not Planners: Decentralized Orchestration of LLM Agents with Private Information
Xiao Liu, Haoyang Li, Songwei Li, Hongbo Fang, Fengli Xu, Feng Shi, James Evans
TL;DR
Centralized orchestration struggles with heterogeneous agents, private execution costs, scaling, and preference sensitivity. AgentLance addresses this with a repeated labor market using bids, public reputations, VCG-style payments, and subcontracting. Across four benchmark types, it adapts allocation to specialization and cost sensitivity, outperforms the cited baselines, and gains further from subcontracting and improved cost estimation and bidding.
Problem
Existing centralized orchestration struggles to process dispersed private information effectively as agent and task counts grow, while agents differ in capabilities and costs.
Method
AgentLance is a repeated labor market in which agents bid using private information, an allocator uses bids and public reputations, and winners can subcontract complex tasks.
Results
Across diverse benchmarks, AgentLance adapts allocations to specialization and cost sensitivity, outperforms fixed-model, centralized-orchestration, and market baselines, and benefits further from subcontracting.
Takeaways & Limitations
Improving inaccurate cost estimation and sub-optimal bidding consistently enhances market performance, indicating further improvement opportunities within the framework.
Takeaways & Limitations
The framework assumes agents can estimate their total execution costs from task demands and expected token usage, but agents often estimate costs inaccurately.
Abstract
from arXiv · showhide
As LLM agents proliferate, built by different parties and with different capabilities and costs, orchestrating them is more like assembling labor across the economy than a computer calling a subroutine. Existing orchestration is typically centralized, with a single planner assigning every task, but this creates a bottleneck as agent pools grow, requires private information (e.g., agents' execution costs), and can easily be manipulated, such that a single inserted preference nearly doubles a favored agent's task share under a centralized LLM allocator. We introduce AgentLance, a repeated labor market in which agents bid on tasks using their private costs and self-maintained strategy notes, an allocator selects winners from bids and public reputation records, and a VCG-style payment rule rewards cost-aware bidding. Complex tasks are handled by hierarchical delegation: winning agents can decompose work and subcontract it through the same mechanism. Across mathematical reasoning, code generation, knowledge-intensive QA, and agentic tasks, AgentLance matches agents to their specializations, shifts work toward cheaper agents as cost sensitivity rises, and consistently outperforms single-model, centralized-orchestration, and market baselines. Diagnosing market failures, including inaccurate cost self-estimation and sub-optimal bidding, then correcting them in controlled experiments yields further gains, charting a path toward more efficient agent economies.
1. Introduction
AgentLance frames heterogeneous-agent orchestration as a labor-market problem under private execution costs, replacing centralized assignment with bidding, reputation, and subcontracting. Across diverse tasks, it adapts allocation to specialization and cost sensitivity, outperforms baselines, and improves further when cost estimation and bidding are corrected.
- Heterogeneous agents differ in strengths, costs, scaffolding, and tools, creating a task-allocation and collaboration problem.
- Centralized orchestration requires complete information, can be biased by inserted preferences, and faces an information-processing bottleneck as agents and tasks grow.
- AgentLance is a repeated labor market where agents bid using private costs and experience, while an allocator uses bids and public performance records.
- Winners can decompose complex tasks and subcontract subtasks through the same market mechanism, with outcomes updating private strategies and public reputations.
- Across mathematical reasoning, code generation, knowledge-intensive reasoning, and agentic problem solving, AgentLance matches specialization, shifts work toward cheaper agents as cost sensitivity rises, and outperforms baselines.Controlled improvements to inaccurate cost estimation and sub-optimal bidding consistently enhance market performance.
2. Motivation for Decentralized Orchestration
The paper motivates decentralizing orchestration because centralized allocators depend on dispersed private information and create a vulnerable single decision point. Markets instead distribute participation and information through agent bids while retaining platform selection using observable records.
- Centralized orchestration assumes one allocator can collect and process information effectively, an impractical assumption when agents possess private task-specific information.
- Inserted preferences in a centralized allocator increased a favored agent’s task share from 34% to 62%.Favoring expensive allocations also raised average execution cost from $0.014 to $0.018 per task.
- Distributing decisions across multiple agents can reduce the influence of any single attack, although decentralization cannot eliminate bias entirely.
- A centralized allocator may struggle to infer agents’ costs, task suitability, and available tools, making the information bottleneck more severe as agent and task counts grow.
- The proposed design decentralizes information and participation decisions: agents choose whether and how much to bid, while the platform selects using bids and observable performance records.
3. The AgentLance Framework
AgentLance allocates tasks through repeated bidding, reputation-based success estimates, and VCG-style payments, with winners optionally managing subcontracted decomposition. Its objective balances correctness against cost, while market records and private notes support future rounds.
- 3.1. Problem Formulation: The platform balances task success against cost using Score(t) = 1{Correct(ŷt, yt)} − α Cost(t), where larger α means greater cost sensitivity.
- 3.2. Agent Decisions: Agents observe tasks, histories, prices, payment rules, and private notes, then estimate suitability and cost before participating, bidding, or abstaining.
- 3.3. Allocation and VCG-Style Payments: The allocator estimates each bidder’s success probability from public reputation records and assigns the task to the highest score Si(t) = p̂i(t) − αbi(t).
- 3.3. Allocation and VCG-Style Payments: The winner’s VCG-style payment is based on the next-best allocation score rather than its own bid, encouraging bids that reflect expected execution costs.
- 3.4. Execution and Subcontracting: For complex tasks, a winner may become a manager, decompose the task, budget subtasks, and select workers through a separate market using the same allocation and payment rules.Subcontracting is rejected when proposed budgets exceed the primary payment, and failed worker selection triggers independent execution.
- 3.5. Reputation and Note Update: Market rounds update public reputations from execution outcomes and private reflective notes from agents’ bidding, payment, cost, profit, and task results.
- 3.5. Reputation and Note Update: As cost sensitivity increases, more tasks are allocated to the cheaper model.
4. Experiments
Experiments evaluate AgentLance across heterogeneous benchmarks, testing specialization-aware allocation, cost sensitivity, overall performance, subcontracting, and component ablations. The market consistently favors task-suitable agents, improves relative to baselines, and gains further from hierarchical delegation and reflective bidding strategies.
- Experimental Setup: AgentLance is evaluated on OlympiadBench, BigCodeBench, SuperGPQA, and GAIA using heterogeneous models with different task performance and execution costs.Each benchmark uses a randomly sampled 100-task pool, with 25 warmup tasks and 75 evaluation tasks.
- Does the Market Behave as Intended?: 89.2% of SuperGPQA tasks go to Gemini 3 Flash and 77.6% of GAIA tasks go to DeepSeek-V3.2, matching their complementary strengths.Gemini scores 0.64 versus 0.55 on SuperGPQA, while DeepSeek scores 0.27 versus 0.20 on GAIA.
- Does the Market Behave as Intended?: 70.7% of tasks go to GPT-5 nano at α = 100, up from 3.3% at α = 1, as cost sensitivity increases.Grok is more accurate, while GPT-5 nano costs $0.0014 versus $0.0045, producing a performance–cost tradeoff.
- Main Results: AgentLance without subcontracting achieves the highest average score among all baselines and exceeds the per-α best-single-model oracle by 5.0 percentage points at α = 10.Its advantage grows with α, while the comparison includes single-model, centralized-orchestration, and market baselines.
- Main Results: Subcontracting raises the average score from 52.2 to 54.2 and improves accuracy by 27.3% while reducing cost by 64.1% on invoked tasks.With subcontracting, AgentLance performs best across all four tested cost-sensitivity settings, with statistically significant average improvements over every baseline (p < 0.05).
- Ablation Study: Removing reflective notes reduces the average score from 52.2% to 48.6%, while replacing critical payments with submitted bids reduces it by 2.5%.Reflective notes consolidate past outcomes into reusable bidding strategies, and VCG-style critical payments generally support more effective bidding and allocation.
5. Diagnosing and Improving Market Performance
The analysis identifies inaccurate cost estimation and sub-optimal bidding as market bottlenecks, then shows that jointly correcting them improves performance across cost-sensitivity settings. Agents also develop strategies around task fit, reputation, auction positioning, and selective participation.
- Bottlenecks: Cost Estimation and Bidding Strategy: Cost-estimation correlations range from 0.091 to 0.299, while MAPE ranges from 114% to 2308%, revealing severe prediction errors before bidding.Historical cost information helps some models but hurts others, with the highest observed correlation reaching only 0.354.
- Bottlenecks: Cost Estimation and Bidding Strategy: The proportion of bidding notes mentioning cost-truthful bidding rises from 47.9% to 66.7% over market rounds, but adaptation remains incomplete.Approximately one-third of bidding notes still omit the strategy after repeated participation.
- Potential Gains from Addressing the Bottlenecks: Correcting cost estimation alone helps when execution cost receives greater weight, whereas enforcing cost-truthful bidding alone produces inconsistent gains and can reduce performance as α increases.The theoretically optimal bidding strategy can be harmful when based on inaccurate cost estimates.
- Potential Gains from Addressing the Bottlenecks: Correcting both bottlenecks improves scores by 1.5, 2.5, 5.4, and 7.7 points at α = 1, 2, 5, and 10, respectively.The interventions show that reliable cost information and cost-truthful bidding are complementary.
- What Do Agents Learn in Their Private Notes?: Task fit is the most prevalent note theme at 34.7%, followed by success and reputation at 22.3% and auction positioning at 21.4%.Cost and payment account for 10.3% of snippets, while risk and abstention account for 9.7%.
- Market Outcomes: Under subcontracting, Grok 4.3 earns the highest cumulative profit at nearly every α, suggesting profits accrue mainly to frequent winners of primary or subcontract tasks.Most agents accumulate profits over successive market rounds.
6. Related Work
Related work studies centralized routing, manually or automatically coordinated multi-agent systems, and LLM-based economic simulations. AgentLance instead decentralizes routing and collaboration through agent bidding, private information, and subcontracting markets.
- Model Routing: Model-routing methods centrally select one model from heterogeneous pools using cascades, classifiers, task difficulty, capabilities, or explicit reasoning.These methods improve executor selection but retain centralized routing.
- Multi-Agent Coordination: Multi-agent orchestration divides tasks among agents and coordinates outputs through roles, workflows, optimized prompts, communication topologies, or learned orchestrators.The literature includes both manually specified and automatically optimized coordination approaches.
- AgentLance’s Position: AgentLance primarily addresses model routing through a primary market and extends it with task decomposition and multi-agent coordination through subcontracting.Agents bid using their own information and recruit collaborators through the same market mechanism.
- LLM Economic Simulation: LLM-based economic simulations model individual decisions, labor and consumption, consumer-business interactions, and economic policies or institutional designs.This line of work uses large populations of LLM agents to study economic behavior and institutions.
- Economic Mechanisms for Coordination: Economy of Minds uses auctions, payments, and wealth accumulation for decentralized credit assignment and agent evolution, while MarketBench evaluates agents’ capability and cost estimation.AgentLance focuses on market mechanisms for orchestrating existing LLM agents.
7. Conclusion
AgentLance is a decentralized labor market for heterogeneous LLM agents operating with private execution costs. Across four benchmarks, it adapts allocation to specialization and cost sensitivity, outperforms the stated baselines, and gains further from subcontracting.
- Conclusion: AgentLance coordinates heterogeneous LLM agents by combining private-cost bidding, public reputation records, and subcontract markets for decomposed complex tasks.Its analysis identifies inaccurate cost estimation and sub-optimal bidding as interdependent bottlenecks.
- Conclusion: Across four complementary benchmarks, AgentLance matches allocations to agent specialization and cost sensitivity, outperforms single-model, centralized-orchestration, and market-based baselines, and benefits from subcontracting.Controlled interventions show substantial gains when the two bottlenecks are addressed jointly.
A. Market Algorithm
AgentLance repeatedly releases task batches, collects bids from agents using private information and notes, and allocates tasks using bids and reputation. Winners execute tasks alone or delegate eligible work through subcontracting, with records updated for future rounds.
- Market Rounds: The workflow initializes a pending-task pool and processes it in repeated market-round batches until no tasks remain.Each round releases a subset of pending tasks and tracks retry counts.
- Bidding: For each task, agents observe the batch, their histories, token prices, payment rule, and private reflective notes before submitting bids.The workflow uses agents’ available private and historical information during bidding.
- Subcontracting: For subcontract-eligible tasks, the winner chooses solo execution or proposes subtasks with budget limits.Invalid decompositions or budgets exceeding the task payment revert the task to solo execution.
- Subcontracting: The allocator collects valid worker bids, estimates bidder success probabilities, and selects workers and payments using shared allocation and payment rules.Assigned workers execute subtasks and return outputs for the manager to synthesize.
- Execution: If no valid workers are assigned, the task returns to solo execution; otherwise, the manager synthesizes available subcontract outputs into the final result.The algorithm explicitly handles empty subcontract assignments by switching modes.
B. Implementation Details
The implementation evaluates AgentLance across complementary benchmarks, automated metrics, and comparisons with fixed-model, centralized-routing, and one-shot market baselines. It also tests susceptibility to planner bias under different cost sensitivities.
- Task suite: Four benchmarks cover mathematical reasoning, code generation, knowledge-intensive question answering, and multi-step agentic tasks.OlympiadBench, BigCodeBench, SuperGPQA, and GAIA use task-specific output formats and automated evaluation procedures.
- Baselines: AgentLance is compared with fixed single-model policies, centralized routing methods, and MarketBench-style one-shot market variants.The centralized baselines receive cost information, unlike market allocators, while the one-shot variants omit repeated market state.
- Bias experiment: The bias experiment appends instructions that favor agent-2 or maximize overall execution cost in the centralized planner.Both interventions are conducted at α = 10, where execution cost receives greater weight in the allocation objective.
C. Details of Note Analysis
The note analysis classifies agents’ private strategy notes into recurring themes and checks the classification procedure against manually reviewed examples.
- Validation: Manual review of 20 notes finds all classifications correct, while Table C.1 provides a representative snippet for each identified theme.The supplied table caption identifies these as example snippets from agents’ notes.
D. Profit Analysis
AgentLance’s repeated market lets labor agents bid using private notes, estimated costs, and public reputation, while winners can subcontract complex tasks through the same mechanism. Profit declines as cost sensitivity increases because the VCG-style payment surplus narrows.
- Profit analysis: As α increases from 1 to 10, individual-agent cumulative profits decrease substantially because stronger cost sensitivity narrows VCG-style payment surplus.Agents retain less profit after covering execution costs.
- Primary-market bidding: Agents bid selectively by estimating task-specific completion costs and choosing prices that balance winning probability with expected profit.Omitted tasks represent abstention, and subtask bids additionally include the manager’s budget limit.
- Allocation and payment: The allocator estimates each candidate’s task-specific success probability from public reputation and task fit, then combines estimates with bids using p_hat − αb.The winner’s payment follows the VCG-style rule based on the second-best score.
- Repeated interaction: Private reflective notes convert each round’s bidding rationale, outcomes, costs, payments, and profits into guidance for later participation and pricing.Updated notes overwrite the previous note and become part of the agent’s private context in the next round.
- Subcontracting: Winners can execute tasks solo or subcontract by decomposing them, assigning budgets, opening subtask markets, and synthesizing selected workers’ outputs.Subcontracting is available only for GAIA tasks in the main experiments, and plans exceeding the primary payment execute in SOLO mode.
- Manager synthesis: The manager receives worker outputs as structured evidence and reconciles them with the original task to submit one concise final answer.Workers receive self-contained subtask instructions and return focused answers for manager synthesis.
- Centralized baseline: The centralized planner selects one agent using historical success and realized-cost records under the same accuracy–cost objective.Its prompt defines score as probability_of_success − alpha * execution_cost.