Inference Auctions

Keegan Harris; Siddharth Prasad; Asher Trockman; Nika Haghtalab; Michael I. Jordan

cs.LGSep 30, 2026

Inference Auctions

Authors: Keegan Harris, Siddharth Prasad, Asher Trockman, Nika Haghtalab, Michael I. Jordan

Organizations: University of California, Berkeley · Toyota Technological Institute at Chicago · Google Research · Inria & École Normale Supérieure

Abstract

When inference demand exceeds available compute capacity, model providers must decide which requests should be served first. Users have different tolerances for delay from an LLM API, but current priority pricing schemes compress these differences into coarse fixed-price service tiers. We design an inference auction that allows users to bid for faster service. Our auction allocates priority in an economically efficient way without sacrificing latency, and we develop fast algorithms for implementing prices that incentivize truthful bidding. We also design an autobidding agent for our inference auction, where users specify an inference budget and the autobidder dynamically adjusts its bids over time to maximize user utility subject to the budget constraint. Experiments validate the practicality of our auction: it increases system welfare while maintaining the cache utilization and latency advantages of SGLang, a state-of-the-art inference serving framework.

Figures & tables

Figure 1

Figure 2 : Tree topologies at $n=Q$ . When the workload exceeds the cache (all topologies except small trees), bid-sort pays for its welfare lead (left) in cache misses (middle) and latency (right).

Figure 3 : One cluster has non-zero bids, everyone else bids zero ( mixshare -50). dfs-bid matches bid-sort ’s welfare (left; curves offset slightly for readability) while keeping dfs-uniform ’s hit rate (middle) and latency (right).

Figure 4 : Welfare under autobidding when $T=60$ . Details are in Appendix D.11 .

Appendix figures & tables17 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 5 — Figure 5 : A request radix tree. Each request is a root-to-leaf path; requests with a common prefix share the path from the root to their lowest common ancestor, and non-branching paths are contracted into a single edge. The maximum branching factor of this tree is $3$ . Requests in the same subtree are easier to store together in the KV cache, as their shared prefixes only need to be stored once.

Panel of Figure 6 — Figure 6 : The welfare-maximizing DFS schedule on an example radix tree. At every internal node, children are visited in decreasing order of average subtree bid (blue marks the child visited first). The resulting schedule is $1,3,2,5,6,4$ . Note that request 5 bids $8 but is served after request 2, which bids$ 3. This is because request 5 belongs to a subtree with a lower average bid, and a DFS schedule cannot interleave the two subtrees.

Figure 8

	Our Notation	Balseiro et al. [9]
Time Horizon:	$T$	$T$
Capacity:	$T\gamma$	$T\rho$
Action Set:	$\mathcal{Y}=\{\mathbf{y}\geq\mathbf{0}:\sum_{k}\mathbf{y}[k]\leq 1\}$	Generic action set $\mathcal{X}$
Decision
Variable:	Menu selection vector $y\in\mathcal{Y}$	Action $x_{t}\in\mathcal{X}$
Reward

Appendix

Table 1 : Notation translation between our setting and Balseiro et al. [9] .

Panel of Figure 7 — Figure 7 : Welfare under heterogeneous pacing. Leaves show true values $v_{r}$ and pacing factors $\alpha_{r}$ , so that $b_{r}=\alpha_{r}v_{r}$ . Internal subtrees are labeled with their value-weighted pacing factor $\alpha(\mathsf{c})=F_{b}(\mathsf{c})/F_{v}(\mathsf{c})$ , and $\kappa_{\mathsf{u}}$ is the ratio of the largest to smallest $\alpha(\mathsf{c})$ among the children of $\mathsf{u}$ . Red nodes are where paced bids reverse the value-optimal order. At the root, “this email” now has the higher average bid ( $3.2$ versus $3$ ), and under “the article,” request 3 now outbids request 1 ( $4.5$ versus $3.6$ ). The realized schedule is $5,6,4,3,1,2$ , which attains $87/99\approx 0.88$ of the optimal DFS welfare. Theorem 4.4 guarantees at least $\sum_{\mathsf{u}}\Omega_{\mathsf{u}}/\kappa_{\mathsf{u}}\big/\sum_{\mathsf{u}}\Omega_{\mathsf{u}}\approx 0.63$ , and hence at least $1/\max_{\mathsf{u}}\kappa_{\mathsf{u}}\approx 0.24$ . Node 3 has the largest condition number but no reversal, so it loses nothing.

workload	tokens	tokens	KV cache	fraction	prompt	shared prefix	unique suffix	interior nodes
	total	distinct	distinct $/$	shared	median tokens per query			queries at
stars	2.05M	781k	33.7	0.62	1086	381	57	0
chains	3.32M	437k	18.9	0.87	2854	2852	0	876
short trees	168k	23k	1.0	0.86	159	147	12	357
long trees	4.07M	124k	5.4	0.97	4143	4127	15	335

Appendix

Table 2 : Radix-tree statistics of one

Q=1024

instance of each workload. Distinct tokens is the total edge length of the tree; a query’s shared prefix is its longest common prefix with any other query. Stars corresponds to mixshare -50, chains corresponds to agent , short trees corresponds to tot , and long trees corresponds to tot-long .

Figure 8 : Per-query distributions of prompt, shared prefix, and unique suffix length (log scale).

Panel of Figure 9 — Figure 9 : Raw welfare and mean TTFT for the sharing-fraction (top) and batch-size (bottom) sweeps of Figure 1 .

Figure 10 : Chains ( agent ) against batch size $n$ .

Figure 11 : Short trees ( tot ) against batch size $n$ . The workload fits in the cache, so hit rate and TTFT do not depend on the order.

Figure 12 : Long trees ( tot-long ) against batch size $n$ , second machine.

Figure 13 : Offline sweeps on the planned orders, three trials. (a) dfs-bid ’s welfare as a fraction of the unconstrained optimum against the minimum-prefix threshold $L$ , per sharing fraction. (b) Planned welfare of each algorithm against within-cluster value correlation $\rho$ .

Figure 14 : Within-cluster value correlation $\rho$ on chains (top) and long trees (bottom) at $n=Q$ , third machine.

rate	$n$	wait	dfs-bid		no-sort
			mean TTFT	hit	mean TTFT
4/s	64	8	150	0.33	211
4/s	512	63	160	0.56	314
1/s	64	31	45	0.30	47
1/s	512	254	328	0.56	406

Appendix

Table 3: Poisson arrivals on mixshare -50. “Wait” is the mean time from a query’s arrival to the release of its batch; all times in seconds.

experiment	algorithm	7B	32B	7B	32B	7B	32B
		welfare		hit rate		completion time (s)
mixshare -50, $n=Q$	dfs-bid	1541	1542	0.60	0.60	87	319
	bid-sort	1936	1936	0.22	0.23	163	615
	dfs-uniform	1376	1376	0.60	0.59	91	322
	no-sort	1322	1322	0.21	0.21	165	629
mixshare -75, $n=256$	dfs-bid	1660	1660	0.70	0.69	81	327

Appendix

Table 4: Qwen2.5-7B-Instruct against the 32B model on identical instances; means over three trials.

Figure 15 : Welfare gain on mixshare -50 and agent under Pareto, uniform on $[1,5]$ , and lognormal ( $\sigma=0.5$ ) values with the same mean.

Figure 16 : Pacing autobidders over $T=60$ batches of $n=256$ , half the users pacing and half truthful. (a) Spend relative to the per-batch target. (b) Welfare under pacing as a fraction of the DFS optimum at true values.

Explore similar work

Learning the Cost of Reliable Inference
Sep 23, 2026Dimitrios Rontogiannis, Ander Artola Velasco, Manuel Gomez RodriguezQuestion-Answering Benchmarks
Max Planck Institute for Software Systems Kaiserslautern, Germany
The Shadow Price of Reasoning: Economic Perspective on Optimal Budget Allocation for LLMs
Jun 2, 2026Xu Wan, Speed Zhu, Jianwei Cai +4Token Budget Allocation Economies
1Zhejiang University · 2Tecent HY Team · 3Peking University
End-to-End Dynamic Sparsity for Resource-Adaptive LLM Inference
Jun 26, 2026Yuhang Chen, Jinhao Duan, Ruichen Zhang +11LLM Inference Optimization Sparsity
University of North Carolina at Chapel Hill · Meta AI

Sep 23, 2026, cs.AIJ/K move · Enter open · S save

Learning the Cost of Reliable Inference

Dimitrios Rontogiannis, Ander Artola Velasco, Manuel Gomez Rodriguez

Max Planck Institute for Software Systems Kaiserslautern, Germany

Question-Answering Benchmarks

Open paper AskPDF arXiv

Benchmarking and routing platforms increasingly act as intermediaries connecting large language model providers with end-users. However, providers on these platforms typically use a fixed price per token, preventing users from achieving the most competitive price for their tasks. In this work, we design a procurement platform where token prices for each task are driven by provider competition, enabling users to secure competitive pricing for guaranteed quality levels. To this end, the platform sequentially routes queries via a reverse second-price auction that incentivizes model providers to truthfully bid their best estimate of the average cost to serve a user's query. As it routes queries, the platform learns the quality offered by each provider and progressively routes queries to the most cost-competitive provider among those meeting a desired quality threshold. To validate our design, we conduct experiments with multiple LLMs from the Llama and Qwen families on popular mathematical reasoning and question-answering benchmarks. The results show that the pricing margin of the most cost-competitive provider on our platform varies significantly---from

10\%

71\%

---depending on the task and quality threshold. This suggests a substantial inefficiency in the current fixed-price market, and it demonstrates that our platform may enable users to capture maximum savings whenever competitive market conditions permit.

Abstract

Explore similar work

Learning the Cost of Reliable Inference

The Shadow Price of Reasoning: Economic Perspective on Optimal Budget Allocation for LLMs

End-to-End Dynamic Sparsity for Resource-Adaptive LLM Inference