- Rating
- 3
- Confidence
- 3
- Informativeness
- 3
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper proposes Inference Auctions, an auction-based mechanism for allocating priority among LLM inference requests. To preserve KV-cache efficiency, the mechanism restricts scheduling decisions to depth-first-search (DFS) traversals of the request radix tree. The authors show that ordering child subtrees by their average bids maximizes social welfare within the set of DFS schedules. They further develop an efficient Vickrey–Clarke–Groves (VCG) payment algorithm to incentivize truthful bidding and introduce a budget-aware autobidding strategy with theoretical regret guarantees. Experiments integrated with SGLang demonstrate improvements in the defined social welfare objective while maintaining cache utilization and average latency.
Critical strengths
The paper investigates an important intersection of LLM serving systems and mechanism design. Allocating inference priority according to heterogeneous user preferences while preserving computational efficiency is a meaningful research direction.
The paper provides a characterization of welfare-optimal DFS scheduling, an efficient algorithm for computing VCG payments, and theoretical guarantees for budget-aware autobidding. In particular, the efficient payment computation represents a concrete contribution beyond simply combining existing auction mechanisms with inference serving systems.
The authors implement the mechanism on top of SGLang and evaluate different prefix-sharing structures, workload conditions, and model sizes. The results provide useful evidence that bid-aware scheduling can be integrated with existing inference infrastructure.
Critical weaknesses
Limited generalizability to realistic online and distributed inference serving. The main experimental setting considers a single inference worker with exogenously formed scheduling batches and a heavily loaded request queue. Although the appendix includes a limited online-arrival experiment and a second model, the evaluation does not sufficiently investigate multiple serving workers, dynamic cache capacities, heterogeneous request lengths, or changing traffic intensity.
Some technical details of the radix-tree representation require clarification. Definition 2.1 assumes that each request corresponds to a leaf of the radix tree, whereas the workload statistics in Appendix D.2 report substantial numbers of requests located at interior nodes, particularly for agent trajectories. The authors should clarify how such requests are represented in the theoretical model and handled by the scheduling and payment algorithms, and whether any transformation is required to maintain the stated guarantees.
Questions for authors
Can the authors evaluate whether the proposed welfare-maximizing scheduling mechanism remains effective when user utility is defined over actual time-to-first-token rather than relative queue position? In particular, the current theoretical guarantees apply to a rank-based utility function, which may not accurately represent heterogeneous and nonlinear latency preferences in real-world inference services.
3 comments
Can the authors evaluate whether the proposed welfare-maximizing scheduling mechanism remains effective when user utility is defined over actual time-to-first-token rather than relative queue position? In particular, the current theoretical guarantees apply to a rank-based utility function, which may not accurately represent heterogeneous and nonlinear latency preferences in real-world inference services.
Allowing user utility to be defined over actual TTFT is an important challenge for future work.
We agree that fractional priority is not a perfect proxy for true request latency, so you are right that our welfare objective does not precisely capture fine-grained latency preferences real users might have.
However, we believe that our work takes an important first step in addressing issues of economic efficiency in inference serving. We settled on a simple rank-based bidding language since it is very easy for bidders to use, and lends itself to a computationally tractable auction design that integrates neatly into SGLang.
We agree with you that a practical inference auction needs to more directly allow bidders to express their values over true request latency as measured by TTFT (which would then allow us, as you suggest, to measure welfare gains over actual time delays). A successful inference auction design will likely need to build upon our work by integrating accurate measures/predictions of elapsed TTFT, and making it easy for bidders to express values over TTFT. We view this as an important challenge for future work, but is one that is outside the scope of our paper.
We think that our key conceptual contribution, that an economically efficient auction can be designed and easily implemented within the bounds of cache-optimal serving, is an important enough standalone contribution. Indeed it does not reflect all the complex realities of inference serving, but we do not think that is a reason to discount our approach. Any real world inference auction will have to reckon with the tradeoffs between making the bidding experience simple and easy to use versus capturing all intricacies of latency preferences. We believe that our auction design opens up various fruitful avenues for future research.
Even so, we can still check how well our schedules do when we measure utility from actual TTFT. Below, we recalculate welfare on our main runs (n = Q) using both linear delay, v_r * (1 - TTFT_r / T) where T is total batch time, and a simple deadline (what fraction of total bid value finishes faster than NO-SORT's median TTFT in each trial):
| Workload (n = Q) | Order | Rank Welfare | Linear Delay | Beat Deadline |
|---|---|---|---|---|
| Stars | DFS-BID / DFS-UNIFORM / BID-SORT | +14.4% / +2.1% / +43.7% | +14.9% / +6.8% / +44.3% | 97% / 90% / 78% |
| Chains | DFS-BID / DFS-UNIFORM / BID-SORT | +17.5% / +1.4% / +50.5% | +17.0% / +0.7% / +51.8% | 100% / 100% / 80% |
| Long trees | DFS-BID / DFS-UNIFORM / BID-SORT | +20.8% / -2.3% / +48.8% | +22.8% / +1.7% / +49.1% | 100% / 100% / 79% |
Note that DFS-BID's welfare gains look almost identical whether we use queue rank or actual TTFT, and DFS-BID beats the deadline on 97-100% of bid value (compared to ~79% for BID-SORT). We also ran the token-weighted DFS variant from Appendix A (where we sort subtrees by bid per prompt token instead of per request): on stars it keeps a 0.61 hit rate, cuts mean TTFT in half (37s vs. 78s), and reaches +59.5% linear delay welfare, trading off rank welfare (+5.1%).
Thank you for the author's response; I will keep my score.
Multiple serving workers, dynamic cache capacities, and other real world inference serving complexities are certainly important issues a practical inference auction should address, but these are outside the scope of our work.
We believe that our simplified setting with a single inference worker and exogenously formed scheduling batches is an important first step that can lead to more practical designs in future research. As we are the first to study inference auctions, it was not known how to design an auction for even a single inference worker without compromising latency before our work.
Also, prompts in stars already vary from ~100 to 5,000 tokens (Appendix D.2), and we ran a new stars experiment (n = Q) raising max output length from 128 to 1024 tokens to test heavier decoding:
Even with 8x longer max outputs, DFS-BID keeps its 0.60 cache hit rate and much lower TTFT than BID-SORT.
The statistics in Appendix D.2 report on shared prefix structure. Requests that end at an internal node of the radix tree are given an auxiliary leaf child, as stated in the definition of the request-augmented radix tree T (Definition 2.1). So, there is no discrepancy here.
Those auxiliary leaves just have empty (zero token) edges, so we run our scheduling and VCG payment algorithms on them as is without changing anything.