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 1 : Stars topology. Welfare, cache hit rate, and mean TTFT, varying: batch size n (left), sharing fraction P with n=256 (middle), and within-cluster bid correlation ρ (right).
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
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.
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 8butisservedafterrequest2,whichbids3. 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γ
Tρ
Action Set:
Y={y≥0:∑ky[k]≤1}
Generic action set X
Decision
Variable:
Menu selection vector y∈Y
Action xt∈X
Reward
Appendix
Table 1 : Notation translation between our setting and Balseiro et al. [9] .
Figure 7 : Welfare under heterogeneous pacing. Leaves show true values vr and pacing factors αr , so that br=αrvr . Internal subtrees are labeled with their value-weighted pacing factor α(c)=Fb(c)/Fv(c) , and κu is the ratio of the largest to smallest α(c) among the children of 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≈0.88 of the optimal DFS welfare. Theorem 4.4 guarantees at least ∑uΩu/κu/∑uΩu≈0.63 , and hence at least 1/maxuκu≈0.24 . Node 3 has the largest condition number but no reversal, so it loses nothing.
total
distinct
distinct /
shared
median tokens per query
queries at
workload
tokens
tokens
KV cache
fraction
prompt
shared prefix
unique suffix
interior nodes
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).
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 ρ .
Figure 14 : Within-cluster value correlation ρ 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.
welfare
hit rate
completion time (s)
experiment
algorithm
7B
32B
7B
32B
7B
32B
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 ( σ=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.
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% to 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.
Dimitrios Rontogiannis, Ander Artola Velasco, Manuel Gomez Rodriguez
Max Planck Institute for Software Systems Kaiserslautern, Germany
Inference-time scaling has emerged as a critical avenue for enhancing Large Language Models' performance, yet real-world deployment is constrained by strict computational budgets. In this work, we formulate inference budget allocation as a global constrained optimization problem governed by economic principles. By modeling per-query reasoning utility with a shifted-surge function, we derive an optimal allocation policy based on a global shadow price that equilibrates marginal utility under resource scarcity. Based on this theory, we propose Constrained Latent-utility Equilibrium Allocation for Reasoning (CLEAR). It performs rational abandonment and reallocates resources from insolvent queries to solvable queries near their emergence thresholds. Extensive experiments on several reasoning tasks with different traffic streams demonstrate that CLEAR significantly improves the Pareto frontier of total token cost versus mean accuracy. In resource-scarce regimes, CLEAR achieves up to a 3x improvement in global accuracy compared to uniform allocation.
Xu Wan, Speed Zhu, Jianwei Cai +4
1Zhejiang University · 2Tecent HY Team · 3Peking University
Large Language Models (LLMs) inference is typically deployed under a static resource assumption, where models execute a fixed computational graph regardless of the runtime environment. However, real-world cloud infrastructure is inherently dynamic, characterized by fluctuating availability (e.g., spot instance preemption) and tiered Quality-of-Service requirements. In such volatile settings, static models are inflexible: they either crash under resource constraints or waste compute on redundant operations. To bridge this gap, we propose Learning to Allocate (L2A), an end-to-end framework for resource-adaptive inference. Unlike prior methods that condition only on input difficulty, we formulate inference as a constrained allocation problem conditioned on both the input and the runtime resource budget itself. We introduce lightweight, budget-conditioned and input-aware gating networks integrated into the LLM. These gates are trained via a unified objective that jointly optimizes task performance, logical consistency, and resource costs along three axes matching how real-world dynamics manifest: layer skipping for memory and depth pressure, head pruning for throughput contention, and reasoning-token reduction for latency tightening. This lets the model learn a budget-aware policy beyond input difficulty alone: it adaptively configures its computational footprint with respect to real-time resource dynamics, maximizing reasoning depth when resources permit while enforcing strict frugality when budgets tighten. A single L2A model traces the entire compute-accuracy Pareto frontier on Llama-3-8B and Qwen-3-4B: at up to 34% realized layer sparsity, it stays within 0.6% of the dense baseline on GSM8K, with the same gap holding zero-shot on out-of-distribution tasks, while every static or heuristic baseline requires a separately tuned model and still drops by 5-10% at comparable inference time.
Yuhang Chen, Jinhao Duan, Ruichen Zhang +11
University of North Carolina at Chapel Hill · Meta AI