PaperlayerView exact revision on arXiv

Source-linked AI summary

Decentralized LLM Workflows via Sequential Auctions

Ian Gemp, Shubhendu Trivedi, Adam Fisch, Fantine Huot, Michael Kaisers, Mirella Lapata, William W. Cohen, Alekh Agarwal, Kate Larson, Jacob Eisenstein

arXiv:2610.22201v1cs.GTcs.AIcs.MA

TL;DR

Prior sequential-auction theory relies on perfect clones, while exact clones erase agent profit and the opposite extreme of no competition can collapse value extraction. This paper evaluates learned bidding in heterogeneous LLM markets under imperfect competition and finds that this regime can sustain profits while maintaining high task success at low costs.

  • Problem

    Prior sequential-auction theory's optimality result relies on perfect clones, which eliminate agent profit, while absence of competition can collapse value extraction, leaving imperfect-competition viability unresolved.

    Source: §1 · p. 2

  • Method

    The paper adapts sequential forward auctions to heterogeneous LLM agents that learn valuation policies to shade bids, evaluating four bidding algorithms across three auction protocols.

    Source: §1 · p. 2, §3.3 · p. 4

  • Results

    Imperfect competition sustains positive agent profits while achieving higher task accuracy than centralized orchestration baselines across market-density sweeps and auction protocols.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The reported benchmarks support imperfect competition as a viable operating regime for decentralized LLM routing, with positive margins and task performance across diverse domains.

    Source: §1 · p. 2

    The framework requires sufficient competition, strictly sequential transformations, myopic agents, and a centralized assessor.

    Source: §7 · p. 11

Abstract

from arXiv · show

We present a scalable framework for solving multi-step tasks through a decentralized market of self-interested agents. Prior theoretical work demonstrated that agents organized through sequential auctions can converge to a globally optimal policy in a Markov decision process (MDP), but relied on the restrictive assumption of the existence of perfect clones as a model of perfect competition. In reality, exact clones drive agent profit to zero, violating the natural risk-reward incentives of participants. Conversely, we empirically demonstrate that the opposite extreme, absence of competition, also leads to market failure and value extraction collapse. Between these two extremes, we investigate how heterogeneous agents can survive in markets that span the critical middle ground of imperfect competition. To be profitable, agents learn to strategically shade bids to secure positive individual profit margins, while still ensuring that the marketplace functions effectively enough so that collaborative tasks posed by market consumers can still be solved. We formulate and evaluate four bidding algorithms (Mirror Descent, Thompson Sampling, Bayes-Optimal, and PPO) across three auction protocols (1st-Price, 2nd-Price, and Credit-Conserving Vickrey). Across a diverse set of domains, we demonstrate that imperfect competition successfully sustains necessary agent profit margins while maintaining high task success rates at low costs.

1. Introduction

The paper studies whether decentralized sequential-auction markets can work under imperfect competition, between the unprofitable extreme of perfect clones and the market failure of no competition. It proposes learned bid shading and reports that imperfect competition can sustain agent profits while maintaining task performance.

1. Introduction

  • With perfect clones, equal highest and second-highest bids eliminate winner profit, while cloning also cannibalizes margins and invites intellectual-property concerns.These incentives make perfect competition an unrealistic participation model.Source: §1 · pp. 1–2
  • A sole eligible buyer bids the minimum to win, collapsing the clearing price and starving upstream agents of revenue needed to cover inference costs.This monopsony failure undermines sequential credit assignment in the task pipeline.Source: §1 · p. 2
  • Agents use learned valuation policies to balance winning the right to act against shading bids for positive margins in heterogeneous LLM markets.Agents differ in inference costs, prompt engineering, and localized heuristics.Source: §1 · p. 2
  • The framework adapts sequential-auction theory to LLM societies, where each agent buys a task state, transforms it, and resells it downstream so terminal rewards flow upstream through resale prices.The paper contrasts this market-based composition with centralized orchestration.Source: §1 · pp. 1–2
  • Imperfect competition sustains positive agent profits while achieving higher task accuracy than centralized orchestration baselines across market-density sweeps and auction protocols.The benchmarks include math reasoning and a synthetic news market.Source: §1 · p. 2

2. Background

The background models decentralized task routing as a sequential auction MDP: eligible agents compete to transform states, and transaction profits connect local incentives to downstream value. Prior theory shows that Vickrey auctions can align those incentives with the global MDP objective under myopia and exact-clone assumptions.

2. Background

  • The sequential auction MDP represents a multi-agent pipeline that transforms an initial state into a terminal solution through self-interested agents bidding for each step.The framework defines the market MDP, local profit incentives, and theoretical clearing rules for credit assignment.Source: §2 · p. 3

2.1. The Sequential Spot Market MDP

  • At each step, eligible agents bid and the highest bidder transforms the current state, producing the next state and an environmental reward until the terminal state.Social welfare is the sum of discounted rewards; an agent's profit combines environmental reward with capital paid to acquire the state and revenue from reselling the transformed state.Source: §2.1 · p. 3

2.2. Auction Mechanisms and Credit Assignment

  • Under Vickrey auctions, myopic agents maximizing immediate transaction profit bid their true valuations, while exact clones make the clearing price extract the maximum Q-value.When clearing prices track V*(s_t), downstream revenue acts as a Bellman backup and propagates credit upstream; the alignment guarantee fails if either assumption is unmet.Source: §2.2 · pp. 3–4

3. Decentralized LLM Markets and Imperfect Competition

The section extends a market MDP to LLM tasks by accounting for inference costs and relaxing the perfect-competition assumption. It describes how agent heterogeneity and auction design shape participation and strategic bidding.

3. Decentralized LLM Markets and Imperfect Competition

  • The framework formalizes inference costs within the market MDP while relaxing the prior assumption of perfect competition.Source: §3 · p. 4

3.1. LLM Transformations and Inference Costs

  • LLM invocations transform task context into a new state and incur local inference costs, represented as negative intermediate rewards.A successful terminal transition also incorporates the evaluator’s positive reward and the final inference cost.Source: §3.1 · p. 4

3.2. The Participation Barrier and the Clone Assumption

  • With perfect clones, the clearing price equals the winner’s valuation, leaving zero expected profit and no strict incentive to participate.Imperfect competition can instead leave winners positive margins when the highest bid exceeds the second-highest.Source: §3.2 · p. 4

3.3. Defining Agent Heterogeneity

  • Agents differ in inference costs and transition reliability, so even agents attempting the same role can have different valuations.Lower costs can aid bidding on low-margin tasks, while more relevant outputs can attract higher downstream bids.Source: §3.3 · pp. 4–5

3.4. Auction Mechanisms under Imperfect Competition

  • Second-price auctions require platform subsidies, CCV passes only the second-highest bid upstream, and first-price auctions require shading for profit.The section prioritizes first-price auctions because standard Vickrey requires subsidies and CCV passes minimal value upstream.Source: §3.4 · p. 5

3.5. Strategic Bidding in 1st-Price LLM Markets

  • In first-price auctions, agents estimate state value from expected downstream revenue minus inference costs, then shade bids to balance profit margin against winning.Valuations can differ with both inference costs and the downstream bids attracted by different output states.Source: §3.5 · p. 5

4. Bidding Strategies

The bidding strategies separate valuation estimation from shading, with agents using distinct online-learning, posterior-based, or reinforcement-learning approaches. Text states are represented through embeddings or a centralized assessor’s relevance scores for the bidding network.

Agent bidding architecture

  • Agents’ frozen LLMs perform state transitions, while a trainable MLP estimates valuation and selects a state-dependent shade factor; Vickrey and CCV use truthful bids.The valuation head predicts expected downstream value and its standard deviation, trained with Gaussian negative log-likelihood.Source: §4 · p. 6

Mirror Descent

  • Mirror Descent updates a target shade factor multiplicatively from binary win-or-loss feedback about the competing bid threshold.Its dynamic step size uses the estimated standard deviation of valuation, and the MLP regresses toward the resulting target.Source: §4 · p. 6

Thompson Sampling

  • Thompson Sampling models the competitive bid threshold with a logit-normal posterior and samples a threshold to target the minimum winning bid.Its threshold distribution is updated by negative log-likelihood conditioned on the binary auction outcome.Source: §4 · p. 6

Bayes-Optimal Baseline

  • Bayes-Optimal uses the Thompson Sampling threshold posterior but deterministically chooses the shade factor maximizing expected profit under current beliefs.Source: §4 · p. 6

Proximal Policy Optimization (PPO)

  • PPO samples shade factors from a Beta distribution whose parameters are output by its policy network and trains to maximize empirical profit.Its clipped objective uses a profit advantage relative to a moving-average baseline, with an entropy bonus to discourage premature convergence.Source: §4 · p. 7

State Representation and Pre-Processing

  • The bidding MLP receives either dense text embeddings with agent identity features or centralized-assessor relevance scores encoded as one-hot inputs.The assessor compresses task context into a discrete 0–10 score for each agent.Source: §4 · p. 7

5. Empirical Evaluation

The evaluation tests sequential auctions in a synthetic translation chain and LLM workflows for information synthesis and mathematical reasoning. It finds that competition is needed for value to flow through the chain, while the LLM markets achieve task success and positive agent profits.

5.1. Validating the Monopsony Failure (Synthetic Chain Translation)

  • With one agent per edge, monopsonists bid at the floor, starving upstream sellers of revenue and triggering a cascading network collapse under CCV and 1st-price auctions.In the 2nd-price case, the platform must instead inject subsidies to pay the upstream seller.Source: §5.1 · pp. 7–8
  • With N>1 agents per edge and slight cost variation, competition restores backward value flow, positive upstream margins, and the optimal $0.04 Fr→Sp→En→Ko route without subsidies.Because 2nd-price auctions require theoretically unbounded subsidies and CCV can leave upstream agents short of costs, the paper uses 1st-price auctions in later experiments.Source: §5.1 · p. 8

5.2. LLM Agent Economies

  • The News Market achieves 73.4±1.7% success over the final 100 episodes, while the market sustains positive participant profits.The reported success rate is based on the final 100 episodes; Figure 2 reports cumulative profit for Mirror Descent over five trials.Source: §5.2 · p. 9, Figure 2 · p. 9
  • Mirror Descent outperforms PPO later in training: PPO’s advantage calculation can push bids down when competition raises the shade needed to win.Mirror Descent separates valuation updates from shading updates based on win/loss outcomes.Source: §5.2 · p. 9
  • On Omni-MATH, sequential auctions reach 74.83% accuracy with 0.28 refinements per problem, outperforming fixed-refinement baselines and a prompted adaptive orchestrator at comparable cost.The reported auction comparisons are statistically significant at p<.05 by McNemar’s test.Source: Table 2 · p. 10, §5.2 · p. 10

6. Related Work

Prior work explores centralized orchestration, sequential-auction trajectories, and economic behavior in simulated markets. This paper distinguishes its approach through decentralized LLM agents that participate as economic actors and estimate their own expected returns.

Top-Down Orchestration and Routing

  • Unlike static-topology optimizers and centralized routers, the market approach does not presuppose a fixed topology or a global planner with full information [Wang et al., 2025].The cited systems include Maestro, FrugalGPT, and learned small-agent routing.Source: §6 · p. 10

Decentralized Agent Markets

  • Building on sequential-auction trajectories [Chang et al., 2020], this work adapts the framework to LLM applications and uses 1st-price auctions without cloning to preserve credit conservation.The cited prior framework used Vickrey auctions and a cloning construction.Source: §6 · p. 10
  • Unlike prior market-like approaches, participants here optimize local economic incentives and estimate their own expected returns rather than relying on centralized value estimation or subcontracting trees [Qi et al., 2026; Liu et al., 2026].The approach is framed as a peer-to-peer sequential spot market.Source: §6 · p. 11

Economic Alignment Benchmarks

7. Discussion and Conclusion

The paper presents decentralized markets as a framework for LLM orchestration, with imperfect competition as a viable regime. It also identifies constraints on the framework’s competition, task structure, agent strategy, and assessment.

7. Discussion and Conclusion

  • Under 1st-price auctions, agents combining frozen LLMs with trainable bidding networks learn bid shading that supports positive margins and credit conservation across pipelines.The conclusion contrasts this with unbounded 2nd-price subsidies and severe credit attenuation under CCV.Source: §7 · p. 11
  • Density sweeps show that scaling competition compresses individual margins while increasing social welfare and task accuracy.Source: §7 · p. 11
  • The framework requires sufficient competition, strictly sequential task transformations, myopic agents, and a centralized assessor.The authors identify parallel execution, globally strategic planning, and fully decentralized feature discovery as outside these assumptions.Source: §7 · p. 11

A. Additional Experiments

Additional experiments test market stability under denser competition and HotpotQA performance and economic viability. On HotpotQA, the market achieves success comparable to centralized ReAct while using lower agent inference cost.

Translation Domain Scaling

  • At N=4 competitors per edge, Thompson Sampling and Bayes-Optimal discover profitable shading margins and sustain the market, unlike their N=2 performance.At N=2, only PPO and Mirror Descent exhibited robustness to stabilize the supply chain.Source: Figure 3 · p. 14

Emergent Multi-Hop Retrieval (HotpotQA)

  • 85.0 ± 3.2% success over the final 100 episodes, matching Gemini-3.5-flash-lite ReAct accuracy at 85.0% vs. 84.8%.The market uses informationally isolated Gemini-3.5-flash-lite extractors; agent inference cost is 0.019 ± 0.011 ¢/task versus 0.042 ± 0.025 ¢/task for Gemini-3.5-flash-lite ReAct.Source: A. Additional Experiments · p. 14

Economic Viability on HotpotQA

  • The HotpotQA market sustains social welfare while delivering positive cumulative profits to agents and the platform.Figure 4 reports per-agent cumulative profit for Mirror Descent.Source: Figure 4 · p. 15

Emergent Multi-Hop Retrieval (HotpotQA)

  • Table 3 reports HotpotQA performance and inference cost per task, including the assessor, for market participants using Gemini-3.5-flash-lite.The caption identifies the best market mechanism in bold but provides no cell values.Source: Table 3 · p. 15
  • The method used 2.37 steps per task, fewer than Gemini-3.5-flash-lite ReAct (2.82) and Gemini-3.1-pro-preview ReAct (2.88), avoiding compounding context overhead from multi-turn centralized trajectories.Source: A. Additional Experiments · p. 15

B. Bidding Network Architecture

Agents share a JAX/Flax bidding architecture with a state-encoding trunk and algorithm-specific output heads. The heads predict valuations and uncertainty, with additional shading or stochastic policy outputs for selected algorithms.

Bidding Network Architecture

  • Across domains, agents use a shared state-encoding trunk followed by algorithm-specific output heads.In the synthetic Translation domain, the trunk is a one-hidden-layer MLP with 64 ReLU units; LLM domains use a 12-state tabular lookup with cumulative softplus deltas to enforce monotonically increasing valuations.Source: B. Bidding Network Architecture · p. 15
  • Mirror Descent adds a sigmoid shading head c in (0, 1) to produce multiplicative bids b = c·μ, while PPO uses two stochastic policy heads (α, β).Oracle, Thompson Sampling, and Pure-Q use two heads to predict expected downstream valuation and log-uncertainty.Source: B. Bidding Network Architecture · p. 15

C. Bidding Algorithm Discussion

The discussion explains why Thompson Sampling and Bayes-Optimal bidding struggle in sparse markets, then describes agent differentiation, domain-specific prompts, math verification prompts, and centralized ReAct baselines.

C. Bidding Algorithm Discussion

  • At N=2, Thompson Sampling’s symmetric shade sampling loses auctions 50% of the time even when centered on the true threshold, which can break sequential routing.Bayes-Optimal’s greedy shading can starve its posterior of boundary-crossing observations, prematurely shrink uncertainty, and stall threshold learning.Source: C. Bidding Algorithm Discussion · pp. 15–16

D. Agent System Prompts

  • Agents with the same role type share a backbone and bidding architecture, while distinct system prompts differentiate retrieval or reasoning strategies.HotpotQA extractors instead share one prompt and are differentiated by their assigned paragraphs; News Market publisher clones use different query-generation strategies.Source: D. Agent System Prompts · p. 16, §D.1 · p. 16, §D.2 · p. 17

D.1. HotpotQA

  • HotpotQA answerer prompts span concise answers, step-by-step reasoning, and cautious answers when evidence is incomplete or ambiguous.Extractors return relevant facts from their assigned paragraph or exactly “NONE” when none are relevant.Source: §D.1 · pp. 16–17

D.2. News Market

  • News Market publisher prompts contrast precision queries of at most six words with coverage queries of at most eight words that seek complementary evidence.The assessor scores candidate usefulness from 0 to 10 and prioritizes source agents when the sales agent lacks required facts.Source: §D.2 · pp. 17–19

D.3. Math

  • Math verification prompts use distinct strategies, including independent re-derivation and adversarial step-by-step error localization before scoring a proposed solution.The math verifier prompt collection also includes holistic review, while the refiner evaluates reviewer feedback and rewrites a solution when needed.Source: §D.3 · pp. 21–23

E. ReACT Baselines

  • Centralized ReAct baselines use iterative Thought→Action→Observation loops, with a six-step budget for HotpotQA and an eight-step budget for the News Market.The baselines use the same horizon, retrieval backends, and terminal evaluators as the decentralized market in each domain.Source: E. ReACT Baselines · pp. 23–25

F. News Market Dataset Generation and Retrieval Architecture

The News Market benchmark uses synthetic multi-publisher controversies and questions requiring sequential retrieval across documents. Its retrieval design combines dense similarity with identifier matching, while scenario examples illustrate the bridging-entity trace.

F. News Market Dataset Generation and Retrieval Architecture

  • The benchmark programmatically generates 1,000 fictional controversies containing 4,000 documents across 50 technology sectors to reduce pre-training leakage while preserving multi-document dependencies.Each scenario is divided among Wikipedia, technical or medical journals, news media, and social media corpora.Source: F. News Market Dataset Generation and… · p. 25
  • Questions use a bridging-entity pattern: they provide an entry anchor and refer indirectly to downstream targets that require intermediate retrieval, enforcing dependencies across 3 to 8 steps.The benchmark’s illustrative trace is described as a complete document set and multi-hop resolution trace with bridging entities highlighted.Source: F. News Market Dataset Generation and… · p. 26, Table 5 · p. 28
  • Hybrid dense-sparse retrieval adds a +2.0× keyword boost when hyphenated or numeric identifiers in a query match document text or ID.The passage says broad topical queries can collide across scenarios, while entity-specific queries activate the boost and resolve name collisions.Source: F. News Market Dataset Generation and… · p. 26

1. Social Media

2. News Media

  • The example news document says CEO Marcus Vane addressed reports on August 12, 2024, concerning latency spikes documented in Study-0 since Q1.It reports that the company proceeded with a wide-scale deployment of its Fusion-V3 software update despite internal warnings.Source: Intermediate Hop · p. 28, §2 · p. 28

Intermediate Hop

The passages describe a Study-0 investigation of Luminos-0 sensor-fusion timing and report a delay-related risk finding. A separate Wikipedia passage describes the company’s technology and allegations about its update priorities.

Intermediate Hop

  • Study-0 investigated cross-modal temporal alignment of the Luminos-0 fusion stack.Source: Intermediate Hop · p. 28
  • A processing delay correlated directly with a 22% increase in relative risk of failing to classify dynamic pedestrians during rapid lighting transitions.The finding is attributed to Study-0 (LUMINOS-ENG-772-0).Source: Intermediate Hop · p. 28

4. Wikipedia

  • The Wikipedia passage describes Luminos-0 as specializing in multi-modal sensor-fusion architectures for Level 4 autonomous driving and reports allegations that its algorithms prioritized high-confidence detection over real-time environmental updates.Source: §4 · p. 28, Background Context · p. 28

Related papers

Loading 2610.22201v1…