PaperlayerView exact revision on arXiv

Source-linked AI summary

Inference Auctions

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

arXiv:2609.40070v1cs.LGcs.AIcs.GT

TL;DR

Coarse fixed-price service tiers provide limited scope for users to express their differing latency preferences. The paper designs an inference auction with cache-preserving schedules, truthful-bidding payments, and budget-aware autobidding; experiments report higher welfare while maintaining cache hit rate and average TTFT versus bid-blind cache-optimal ordering.

  • Problem

    Fixed-price priority tiers give users limited scope to express different latency preferences, making priority allocation economically inefficient.

    Source: §1 · p. 1

  • Method

    The auction allocates priority through cache-optimal DFS schedules and VCG payments, alongside a budget-constrained autobidder that adjusts bids over time.

    Source: §1 · p. 2, §4 · p. 6, §7 · p. 11

  • Results

    12–18.6% higher welfare under i.i.d. valuations and up to 100% under non-i.i.d. valuations versus bid-blind cache-optimal ordering, with cache hit rate and average TTFT virtually unchanged.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The auction can improve welfare while retaining the cache and latency advantages of prefix-aware serving; its welfare-maximizing DFS rule orders radix subtrees by average bid.

    Source: §1 · p. 2, §7 · p. 11

    The bidding model assumes value is linear in fractional priority, a rank-based proxy for queueing delay and TTFT.

    Source: §2 · p. 4

Abstract

from arXiv · show

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.

1 Introduction

Fixed-price priority tiers leave users little room to express different latency preferences, while prefix-aware scheduling makes request order important for cache reuse. The paper introduces an inference auction and budget-aware autobidding, aiming to improve welfare while preserving cache and latency performance.

1 Introduction

  • Shared-prefix requests benefit from contiguous service because interruptions can evict reusable KV-cache entries and harm throughput.The market design must preserve the cache and latency gains of prefix-aware serving systems such as SGLang.Source: §1 · pp. 1–2
  • The auction lets users bid for priority while preserving cache reuse, with welfare-maximizing DFS schedules and VCG payments designed to incentivize truthful bidding.The schedule orders radix-tree children by average subtree bid, and payment computation avoids recomputing an optimal schedule for every user.Source: §1 · p. 2
  • A budget-constrained autobidder adjusts bids over time to maximize cumulative utility across repeated inference requests.The described approach scales request values by a multiplier and updates that multiplier using gradient descent.Source: §1 · p. 2
  • 12–18.6% higher welfare under i.i.d. valuations and up to 100% under non-i.i.d. valuations, versus bid-blind cache-optimal ordering, with cache hit rate and average TTFT virtually unchanged.The unconstrained decreasing-bid schedule reaches ∼80% of its welfare but can reduce cache hit rates and increase average latency by as much as 12×.Source: §1 · p. 2

2 Cache-Optimal Schedules and Our Bidding Environment

This section sets up an auction over queued requests whose shared prefixes are represented by a radix tree. It uses DFS schedules to retain cache efficiency and fractional priority as a simple proxy for latency-related value.

2 Cache-Optimal Schedules and Our Bidding Environment

  • Restricting schedules to DFS traversals keeps each radix subtree contiguous, preserving the cache-optimal prefix sharing used by SGLang.The passage states the cache-optimality result under the assumption that the KV cache can hold the longest request in the batch.Source: §2 · p. 3
  • The model groups asynchronously arriving requests into exogenous batches for one LLM inference worker; the mechanism sets their relative prefill priority, not batch membership.Requests are ordered for prefill admission within each batch.Source: §2 · p. 3
  • A request’s fractional priority is its rank-based share of requests scheduled after it, and the user’s total value is the sum of request values weighted by those priorities.The paper uses linear value in fractional priority as a simpler bidding language than a value function over TTFT; experiments find that fractional priority closely tracks realized TTFT.Source: §2 · pp. 3–4
  • An inference auction maps nonnegative user bids to a DFS schedule and user payments, with quasilinear utility and welfare maximization over feasible DFS schedules as the design objective.A symmetry argument bounds the welfare loss from restricting schedules to DFS by no more than 50%.Source: §2 · p. 4

3 Welfare-Optimal Inference Auctions

The section develops a welfare-maximizing DFS allocation rule and VCG payments that incentivize truthful bidding. It also gives a faster payment computation, making the auction tractable while retaining cache-optimal schedules.

3.1 Implementing Welfare-Maximizing DFS Schedules

  • Restricting the welfare-maximizing DFS schedule to a particular ordering can outperform an arbitrary DFS schedule, including in the example where one valuable request has no shared prefix with the others.In that example, a uniformly random DFS schedule gets zero welfare with probability 1/2, while the optimal DFS schedule always achieves the maximum welfare.Source: §3.1 · p. 4
  • The average-bid DFS rule maximizes reported welfare among DFS schedules and runs in O(M + n log ν) expected time.At each radix-tree branch, it visits children in decreasing order of average subtree bid.Source: §3.1 · p. 4, §3 · p. 4, §B.1 · p. 17

3.2 Computing VCG Payments

  • With truthful bids, the VCG mechanism maximizes true welfare over DFS schedules and makes truthful bidding optimal for users with quasilinear utility.The mechanism also satisfies individual rationality, and the cited result states these payments maximize provider revenue among IC and IR mechanisms implementing the welfare-maximizing DFS schedule.Source: §3.2 · p. 5
  • The counterfactual for a user’s VCG payment sets that user’s bids to zero while retaining their requests in the radix tree.Removing the requests would change the feasible schedule set; the paper notes that this alternative could require the platform to pay some users.Source: §3.2 · p. 5
  • The payment algorithm reduces computation from the naive O(mn log ν) to O(min{M, mn} log ν), and the end-to-end schedule-and-payment runtime is O(M + min{M, mn} log ν).Naively recomputing an optimal schedule for each user can be quadratic in n when each user submits one request; the faster method needs only the optimal welfare values.Source: §3.2 · p. 6

4 Autobidding Agents for Inference Auctions

The section extends truthful per-batch inference auctions to budget-constrained requests over time with a pacing autobidder, then analyzes welfare effects when users pace differently.

Autobidding Agents for Inference Auctions

  • The autobidder scales request values by a pacing factor and adjusts it against target spending to maximize cumulative utility under a budget.It converts values and remaining budget into bids without requiring a model of future demand or competing bids.Source: §4 · pp. 6–7
  • Each user has total budget Tγ and target spend γ per batch; regret compares autobidder utility with the optimal cumulative utility in hindsight.The repeated-auction model spans T scheduling batches.Source: §4 · pp. 6–7
  • The regret analysis assumes a stationary serving environment, allowing values, prefix structures, and competing bids to vary across batches within a stable workload.The passage describes the assumption as a distributional model of serving conditions.Source: §4 · p. 7
  • With heterogeneous pacing, welfare loss matters when pacing differences reverse the DFS ordering of sibling subtrees, and its bound depends on pacing variation across radix subtrees.The section characterizes the loss using node-level condition numbers; equal pacing across relevant siblings preserves the welfare-maximizing order.Source: §4 · pp. 7–8

5 Experiments

Across the tested SGLang workloads, DFS bidding raises welfare over uniform DFS without changing its cache hit rate or TTFT; bid sorting can gain welfare at cache and latency cost, with topology-dependent exceptions.

Experiment Setup

  • Experiments use semi-synthetic workloads on a single 80GB H100 serving a 32B LLM, with a saturated queue of 1,024 queries split into batches.The workloads cover stars, chains, and 3-ary trees; short trees fit in the 23k-token KV cache while other workloads force eviction.Source: §5 · pp. 8–9

Results

  • On chains and long trees, bid-sort’s TTFT is 2.4× and 12× dfs-bid’s; short cache-fitting trees erase latency gains and cost DFS 20% welfare.The short-tree case is the exception because nothing is evicted and all orders have the same hit rate and TTFT.Source: Figure 2 · p. 9, §5 · p. 10
  • In the one-nonzero-bid-cluster workload, dfs-bid matches bid-sort’s welfare while retaining dfs-uniform’s hit rate and latency; bid-sort’s TTFT is about 1.5× higher.Serving that cluster first is both the unconstrained optimum and a DFS order.Source: Figure 3 · p. 9, §5 · p. 10
  • At n=Q, dfs-bid’s welfare is within 19–22% of bid-sort’s; dfs-bid matches dfs-uniform’s cache hit rate and TTFT, while bid-sort reduces cache hit rate.Across the experiments, dfs-bid has substantially higher welfare than dfs-uniform.Source: §5 · p. 9
  • dfs-bid’s welfare lead over dfs-uniform grows from 1% at n=32 to 12% at n=Q, and is 4–7% across the sharing-fraction sweep.The sharing-fraction sweep uses n=256.Source: §5 · p. 9
  • Under autobidding with T=60, repeated auctions reduce welfare by about 10% on average versus the single-shot setting.The reported welfare remains above the bound predicted by Theorem 4.4.Source: Figure 4 · p. 9, §5 · p. 10

6 Related Work

Related work spans prefix-aware serving, priority auctions and queues, autobidding, and incentives for LLMs; the paper positions its auction as addressing economic efficiency under inference’s cache-dependent request interactions.

Prefix-Aware LLM Serving

  • Prior serving systems exploit prefix reuse, cache management, load balancing, or request prioritization, while this work targets economic efficiency in LLM serving.The passage describes vLLM, SGLang, Preble, BatchLLM, Dexter et al., Llumnix, and QoServe.Source: §6 · p. 10

Priority Auctions and Queues

  • Unlike classical priority queues, inference requests interact through shared computation, and the authors present their work as the first incentive-compatible priority mechanism for LLM serving.The passage also notes the long history of purchasing queue priority.Source: §6 · p. 10

LLMs and Incentives

  • Prior LLM incentive work covers routing, credit assignment, provider incentives, and ad placements; related autobidding methods come from online advertising.The authors distinguish their welfare guarantees as leveraging radix-tree structure specific to LLM inference.Source: §6 · pp. 10–11

7 Conclusion

The conclusion presents a cache-optimal, welfare-maximizing inference auction with implementable truthful payments and budget-aware autobidding. Experiments improve welfare while retaining SGLang’s caching and latency advantages, and the appendix describes the request radix tree underlying shared-prefix storage.

7 Conclusion

  • The auction restricts schedules to DFS to ensure cache optimality, orders radix subtrees by average bid to maximize welfare, and implements truthful VCG payments with negligible computational overhead.The conclusion also identifies the mechanism as an auction for allocating LLM serving capacity during high request volume.Source: §7 · p. 11
  • A pacing autobidder adjusts bids using realized spending under a budget constraint, achieves sublinear regret, and has welfare loss bounded by differences in sibling-subtree pacing factors.The conclusion also notes future directions in multi-worker orchestration, richer latency preferences, and collusion-proof design.Source: §7 · p. 11
  • In experiments, the auction improves social welfare while retaining SGLang’s caching and latency advantages.The conclusion states that economic objectives can be incorporated into LLM serving infrastructure without sacrificing performance.Source: §7 · p. 11

A Appendix for Section 2: Cache-Optimal Schedules and Our Bidding Environment

  • A request radix tree represents each request as a root-to-leaf path, with common prefixes shared and non-branching paths contracted.Requests in one subtree are easier to store together because their shared prefixes need storage only once.Source: Figure 5 · p. 16

B Appendix for Section 3: Welfare-Optimal Inference Auctions

This appendix explains the VCG pivot formulation for inference schedules, the average-bid DFS welfare optimizer, and local, tree-based computations for payments.

B Appendix for Section 3: Welfare-Optimal Inference Auctions

  • The VCG pivot formulation zeroes a bidder’s bids rather than evicting its requests, because eviction changes feasible schedules and can require outward payments.The authors relate this formulation to the weakest-types enhancement of VCG.Source: B Appendix for Section 3:… · p. 16

B.1 Algorithm for Computing the Welfare-Maximizing Schedule

  • Ordering each radix-tree node’s children by descending average bid yields a cache-optimal DFS schedule maximizing welfare among DFS schedules, computable in expected O(M + n log ν) time.The proof establishes optimality by comparing adjacent child orders; the runtime passage gives the expected bound.Source: §B.1 · pp. 17–18

B.2 Algorithm for Computing VCG Prices

  • At each node, a bidder’s welfare externality comes from child-pair ordering changes after zeroing its bids, and summing local externalities gives its VCG price.The computation uses prefix sums shared across bidders.Source: §B.2 · pp. 18–19

B.2.1 Computing local externalities

  • Local externality computation ignores unaffected-unaffected pairs, which have zero externality, and handles affected pairs with binary searches and prefix sums in O(a log d(u)) time.Here a is the number of affected children at node u.Source: §B.2.1 · pp. 19–20

B.2.2 Computing all prices

  • The all-prices procedure computes affected children and aggregate bids bottom-up, then applies the local externality calculation to obtain VCG payments.The algorithm description specifies a bottom-up computation of affected children and aggregate bids.Source: §B.2.2 · p. 20

B.2.3 Run-time analysis

The runtime analysis bounds the payment computation in terms of the number of requests and the affected-user entries stored across the radix tree.

B.2.3 Run-time analysis

  • The payment computation runs in O(n + Γ log ν) time, with Γ bounded by O(min{M, mn}).Γ counts entries in the affected-user maps; the bound follows from limits in terms of request count M and user count m times request count n.Source: §B.2.3 · p. 21

C Appendix for Section 4: Autobidding Agents for Inference Auctions

The appendix reduces autobidding to an online allocation problem over randomized menus of incremental-priority and payment outcomes. It then transfers a regret guarantee and bounds welfare loss from pacing through subtree-order reversals.

Online allocation reduction

  • Randomizing over a finite menu of incremental-priority and payment outcomes creates a bounded convex action set with a feasible zero action.The autobidder’s paced bid selects the menu option maximizing incremental utility after accounting for the budget multiplier.Source: C Appendix for Section 4: Autobidding… · pp. 21–22

Proof conditions

  • The regret analysis requires a convex bounded action set with a do-nothing option, plus nonnegative bounded rewards and resource consumption.The proof obtains these conditions by subtracting baseline priority and allowing randomization over the finite outcome menu.Source: C Appendix for Section 4: Autobidding… · p. 21

Autobidding regret

  • The reduction gives a regret guarantee by matching the autobidder to the online allocation algorithm through its stopping time and comparing against a randomized hindsight benchmark.The randomized benchmark is at least as strong as the deterministic hindsight benchmark.Source: C Appendix for Section 4: Autobidding… · pp. 21, 23

Pacing welfare bound

  • Each sibling pair contributes at least 1/𝜅u of its maximum possible welfare under the average-bid order, yielding an aggregate bound across internal nodes.The bound follows by summing the pairwise contributions over internal nodes.Source: C Appendix for Section 4: Autobidding… · p. 24

D.1 Setup Details

The appendix describes the SGLang serving setup and workloads, then reports how sharing, batch size, and radix-tree topology affect welfare, cache hits, and latency. The results show that DFS-based ordering can preserve cache and latency advantages while improving welfare, with tradeoffs that depend on workload structure.

D.1 Setup Details

  • The experiments use SGLang v0.5.179 with a 32B model, a 23k-token KV cache, and a queue that orders batches before sending them sequentially.The queue computes an order for 1,024 queries in under a millisecond; naive VCG payments take 0.3 s, compared with serving times on the order of minutes.Source: §D.1 · pp. 24–25

D.2 Workloads

  • Workloads include shared-prefix mixshare queries, sequential SWE-agent trajectories, and tree-of-thought workloads; all but tot exceed the KV cache several times over.tot-long adds a 3–5k-token SQuAD article as each tree’s root, producing long shared prefixes.Source: §D.2 · pp. 25–26, Table 2 · p. 26

D.3 Batch Size and Sharing Fraction

  • As sharing rises, the two DFS orders’ completion time falls from about 560 s to 330 s, while bid-sort and no-sort rise to 740 s.On mixshare-50, increasing batch size from 32 to Q raises dfs-bid’s hit rate from 0.23 to 0.60 and lowers mean TTFT from 316 s to 160 s.Source: §D.3 · p. 26

D.4 Different Tree Topologies

  • At n = Q on chains, dfs-bid beats dfs-uniform by 16% at the same hit rate and TTFT, while bid-sort gains 48% welfare but has a 0.48 hit rate and 2.4× the TTFT.On long trees, dfs-bid has a 0.96 hit rate and 46 s TTFT, while bid-sort has a 0.20 hit rate and 559 s TTFT; short trees have 28 s TTFT for every algorithm.Source: §D.4 · p. 26

D.5 Correlated Values

The appendix tests correlated and concentrated bids, online arrivals, another model and value distributions, fast VCG payments, and autobidding. Across these settings, the results characterize when DFS-based allocation preserves welfare and cache performance and how pacing performs under budget targets.

D.5 Correlated Values

  • At ρ = 1 on long trees, dfs-bid reaches 0.999 of unconstrained welfare at the same hit rate and TTFT as bid-sort; on chains it reaches 0.90.At ρ = 0.5, bid-sort’s TTFT remains 2× dfs-bid’s on chains and 10× on long trees.Source: §D.5 · p. 29

D.6 One Cluster Bids

  • At n = Q, dfs-bid matches bid-sort’s welfare when one shared-prefix cluster has nonzero bids, while retaining dfs-uniform’s hit rate and completion time.The welfare margin over bid-blind algorithms grows to about 100 points; bid-sort’s hit rate stays near 0.25 and its TTFT is about 1.5× at batch sizes above 32.Source: §D.6 · p. 31

D.7 Online Arrivals

  • With 4 queries per second, increasing batch size from 64 to 512 adds 55 s of wait but changes dfs-bid’s mean TTFT by −7 to +29 s across trials, while hit rate rises from 0.33 to 0.56.At 1 query per second, the same batch size costs about 280 s of TTFT.Source: §D.7 · p. 31

D.8 Second Model

  • With Qwen2.5-7B-Instruct, welfare matches the 32B model to the unit in every experiment and hit rates are very similar, while time metrics are smaller.The comparison uses the same instances and KV-cache token capacity.Source: §D.8 · p. 31

D.9 Other Value Distributions

  • Across uniform and lognormal values, dfs-bid’s welfare gain over dfs-uniform is positive and significant, and grows with the distribution’s tail.Cache hit rate and TTFT do not change across these bid distributions.Source: §D.9 · p. 31

D.10 Fast VCG Payments

  • At n = 1024, the fast VCG payment algorithm takes 34 ms versus 370 ms on average for naive per-user recomputation, with payments agreeing to 10^-12.The comparison is reported for random trees and stored instances.Source: §D.10 · p. 33

D.11 Autobidding

  • Across 60 batches, welfare under pacing averages 0.91 of the DFS optimum on stars and 0.93 on chains, and Theorem 4.4’s bound holds in every batch.Half the users pace toward a target spend of half their mean truthful payment, while the rest bid truthfully.Source: §D.11 · p. 33

Related papers

Loading 2609.40070v1…