acceptodds
Under review as a conference paper at ICLR 2027

Inference Auctions

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 a budget on total spend 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.

Primary area:
learning theory
Keywords:
auction design, VCG mechanism, LLM inference, KV cache, autobidding

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_C7MzOpenReview ↗
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

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.

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:

Order (1024 max output tokens)Rank WelfareDelay WelfareHit RateMean TTFTp99 TTFTCompletion
DFS-BID+14.4%+31.7%0.60213s493s552s
DFS-UNIFORM+2.1%+4.2%0.59274s491s561s
BID-SORT+43.7%+47.1%0.18359s719s756s
NO-SORT-1.7%+2.0%0.17363s720s754s

Even with 8x longer max outputs, DFS-BID keeps its 0.60 cache hit rate and much lower TTFT than BID-SORT.

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.

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.

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)OrderRank WelfareLinear DelayBeat Deadline
StarsDFS-BID / DFS-UNIFORM / BID-SORT+14.4% / +2.1% / +43.7%+14.9% / +6.8% / +44.3%97% / 90% / 78%
ChainsDFS-BID / DFS-UNIFORM / BID-SORT+17.5% / +1.4% / +50.5%+17.0% / +0.7% / +51.8%100% / 100% / 80%
Long treesDFS-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.

Reviewer_muY6OpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper combines depth first scheduling on shared prefix trees, auction pricing, and automatic bidding under budget constraints to decide which requests to serve first when a large language model server becomes congested. The idea is to balance how much users are willing to pay with how efficiently the system reuses its cache. In the experiments, the authors added the mechanism as a scheduling layer in front of SGLang and used a single H100 GPU with 80 GB of memory to run a 32B model. They tested partly synthetic workloads with different shared prefix structures, measuring social welfare, cache hit rates, and the waiting time for the first output token. Compared with scheduling that optimizes cache reuse but ignores bids, the method improved social welfare by 12% to 18.6% when request valuations were independent and identically distributed and by up to about 100% in certain cases where this assumption did not hold. Overall, the method improved the economic efficiency of service prioritization while keeping cache performance and inference latency largely unchanged.

Critical strengths
  1. Auctions for inference prioritization are an interesting idea that I had not previously considered.
  2. The proposed method is well motivated. Sorting requests solely by bid can disrupt prefix cache reuse, while restricting schedules to DFS traversals and ordering subtrees by average bid balances economic value with cache efficiency.
  3. The experimental evaluation is reasonably comprehensive and clearly reported.
Critical weaknesses
  1. The reported “realized welfare” is computed from rankings induced by actual TTFT rather than from latency itself. However, request lengths, cache hits, and decoding load can all affect latency, so the same improvement in rank may translate into very different reductions in waiting time. The rank-based utility model does not capture these differences, leaving its alignment with users’ actual latency preferences insufficiently validated.

  2. The evaluation primarily uses a single worker with a backlogged queue and outputs capped at 128 tokens, emphasizing prefill and prefix caching. The benefits under long outputs, decode-dominated workloads, heterogeneous request lengths, and multiple workers remain insufficiently validated. Section 5, Figure 2 provides a concrete example of this limitation: when the workload fits entirely in the cache, the DFS restriction offers no latency benefit while sacrificing approximately 20% of welfare relative to BID-SORT.

  3. The introduction critiques fixed-price priority tiers (lines 29–32), but the main baselines are bid-independent DFS, bid-based sorting, and FCFS (sec 5). These comparisons illustrate the trade-off between cache efficiency and prioritization, but do not directly establish how much additional value the auction provides over a well-designed two- or three-tier fixed-price priority service.

Questions for authors

See Weaknesses. I would find this work more promising with a more comprehensive evaluation and a model that captures factors affecting latency beyond queue position, particularly because the method is intended for practical inference serving.

3 comments

Thank you for your review! We appreciate that you found our idea well motivated and interesting.

The reported “realized welfare” is computed from rankings induced by actual TTFT rather than from latency itself. However, request lengths, cache hits, and decoding load can all affect latency, so the same improvement in rank may translate into very different reductions in waiting time. The rank-based utility model does not capture these differences, leaving its alignment with users’ actual latency preferences insufficiently validated.

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 though bidders only submit one number per request, 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)OrderRank WelfareLinear DelayBeat Deadline
StarsDFS-BID / DFS-UNIFORM / BID-SORT+14.4% / +2.1% / +43.7%+14.9% / +6.8% / +44.3%97% / 90% / 78%
ChainsDFS-BID / DFS-UNIFORM / BID-SORT+17.5% / +1.4% / +50.5%+17.0% / +0.7% / +51.8%100% / 100% / 80%
Long treesDFS-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%).

The evaluation primarily uses a single worker with a backlogged queue and outputs capped at 128 tokens, emphasizing prefill and prefix caching. The benefits under long outputs, decode-dominated workloads, heterogeneous request lengths, and multiple workers remain insufficiently validated. Section 5, Figure 2 provides a concrete example of this limitation: when the workload fits entirely in the cache, the DFS restriction offers no latency benefit while sacrificing approximately 20% of welfare relative to BID-SORT.

Yes, that's actually why we included the short tree setting in Figure 2 -- when the whole batch fits in GPU memory at once, SGLang never has to evict cached prefixes, so you don't need the DFS constraint. To test heavier decoding, we ran new experiments on stars (n = Q) raising max output length from 128 to 1024 tokens:

Order (1024 max output tokens)Rank WelfareDelay WelfareHit RateMean TTFTp99 TTFTCompletion
DFS-BID+14.4%+31.7%0.60213s493s552s
DFS-UNIFORM+2.1%+4.2%0.59274s491s561s
BID-SORT+43.7%+47.1%0.18359s719s756s
NO-SORT-1.7%+2.0%0.17363s720s754s

DFS-BID keeps the same cache hit rate and much lower TTFT than BID-SORT, and its linear delay gain is even larger because long outputs make waiting behind earlier requests more expensive. Also, prompts in stars already vary from ~100 to 5,000 tokens (Appendix D.2); we leave routing across multiple workers to future work.

The introduction critiques fixed-price priority tiers (lines 29–32), but the main baselines are bid-independent DFS, bid-based sorting, and FCFS (sec 5). These comparisons illustrate the trade-off between cache efficiency and prioritization, but do not directly establish how much additional value the auction provides over a well-designed two- or three-tier fixed-price priority service.

We ran new SGLang experiments (n = Q) comparing to 2 tier (top ~19% of bids) and 3 tier (top 10% / next 30% / bottom 60%) fixed price priority, both flat (where we sort by tier in arrival order and ignore the tree) and inside the DFS (where we replace each bid with its tier price, 2/1 or 3/2/1, and sort subtrees by average):

OrderStars WelfareStars HitStars Mean TTFTChains WelfareChains HitChains Mean TTFT
DFS-BID+14.4%0.5978s+17.4%0.74110s
2 tiers in DFS+11.3%0.6077s+8.5%0.76108s
3 tiers in DFS+11.6%0.5983s+9.5%0.74112s
DFS-UNIFORM+2.1%0.6075s+1.3%0.76108s
2 tiers flat+30.7%0.21148s+38.3%0.49261s
3 tiers flat+38.9%0.21149s+45.4%0.49261s
BID-SORT+43.7%0.23145s+50.5%0.48266s

Flat tiers break up shared prefixes and roughly double mean TTFT, while putting tiers inside the DFS keeps cache hits high and gets ~50-75% of DFS-BID's welfare gain over DFS-UNIFORM.

I thank the authors for their detailed rebuttals -- I'm increasing my score.

Reviewer_hEuaOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper studies auctions for prioritizing LLM inference requests while preserving prefix-cache reuse. It restricts allocations to DFS traversals of a request radix tree, derives a welfare-optimal ordering based on average subtree bids, and develops an efficient algorithm for computing VCG payments. It also introduces a budget-pacing autobidder and analyzes its regret and the welfare loss caused by heterogeneous pacing. Experiments integrate an external scheduling layer with SGLang.

Critical strengths
  1. The paper identifies an interesting connection between economic priority allocation and prefix-aware inference scheduling. Restricting allocations to DFS schedules provides a tractable way to incorporate bids while preserving cache locality.
  2. The average-bid characterization is clean, and the fast VCG payment algorithm is a substantive contribution beyond applying the standard VCG framework.
  3. The evaluation covers several prefix-sharing topologies, correlated valuations, alternative value distributions, and a limited online-arrival setting. The appendix also validates the fast payment implementation against naive recomputation.
Critical weaknesses
  1. The welfare objective needs stronger validation against actual latency utility. The paper uses a standard economic objective, but its application-specific valuation model is linear in fractional queue rank rather than elapsed time. Computing welfare from the realized TTFT ordering does not resolve this issue: schedules with identical rankings receive identical welfare even when their absolute delays differ substantially. Moreover, agreement between planned and realized rank-based welfare does not validate the assumed relationship between rank and willingness to pay. Evaluation with deadline-based, nonlinear, or empirically calibrated latency utilities would substantially strengthen the practical claims.
  2. The claim of preserving latency is broader than the reported evidence. The experiments primarily report mean TTFT, cache hit rate, and some completion-time measurements. I want to know p95/p99 TTFT, end-to-end tail latency, or SLO violation rates. Since the mechanism reallocates priority, similar aggregate mean latency can conceal substantial degradation for low-bid or budget-constrained users. Please report latency distributions by valuation/budget group and clarify what service guarantees zero-bid requests receive.
  3. The baselines do not adequately evaluate the proposed market design. DFS-UNIFORM, BID-SORT, and NO-SORT isolate useful scheduling effects, but the introduction specifically motivates the work through the limitations of fixed-price priority tiers. A comparison against two- or three-tier pricing is therefore important. DFS-UNIFORM is also intended to emulate SGLang’s prefix-aware policy, while the underlying server is configured as FCFS; a direct comparison with native SGLang LPM would clarify the systems benefit.
  4. The autobidding evaluation is limited. Appendix D.11 evaluates 60 batches and reports spending behavior and welfare, but provides no direct autobidder runtime measurement or comparison against budget-aware bidding baselines. Appendix D.10 reports 34 ms for fast VCG payment computation at 1,024 requests. This is distinct from bid generation and pacing updates. Please measure these components separately, explain whether payment computation blocks admission, and report cumulative net utility and regret relative to an offline benchmark.
  5. The online setting and scope of the incentive guarantees require clarification. Most experiments start with a saturated queue. Appendix D.7 usefully includes Poisson arrivals and batching delay, but also shows a large latency penalty for large batches under lighter load; a timeout-based policy is suggested rather than evaluated. In addition, the regret theorem assumes i.i.d. auction instances, whereas interacting adaptive autobidders may induce nonstationary competing bids. The paper should distinguish the single-autobidder theorem from the multi-autobidder simulation and clarify whether truthfulness covers only value reports for fixed requests, excluding strategic changes to submission timing, request composition, or identities.
Questions for authors
  1. Can you provide p99 TTFT and SLO violation rates, particularly for zero-bid and low-budget users?
  2. Does measured TTFT include batch formation, ordering, payment computation, and autobidding overhead? Which components lie on the admission critical path?
  3. How do welfare gains change under utilities defined over actual delays or deadlines instead of rank?
  4. How does the mechanism compare with fixed-price priority tiers under comparable workloads and budgets?
  5. Can the autobidder be compared with fixed-multiplier pacing, a simple budget-aware heuristic, and an offline optimal policy, i.e. an oracle?
  6. What guarantees remain when multiple adaptive autobidders interact or users strategically alter request submissions?
4 comments

Thanks for your detailed review. We address your comments and suggestions below. (We in particular provide all additional requested experimental details.)

The welfare objective needs stronger validation against actual latency utility.

And

How do welfare gains change under utilities defined over actual delays or deadlines instead of rank?

We agree that fractional priority is not a perfect proxy for true request latency, so you're 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 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 though bidders only submit one number per request, 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)OrderRank WelfareLinear DelayBeat Deadline
StarsDFS-BID / DFS-UNIFORM / BID-SORT+14.4% / +2.1% / +43.7%+14.9% / +6.8% / +44.3%97% / 90% / 78%
ChainsDFS-BID / DFS-UNIFORM / BID-SORT+17.5% / +1.4% / +50.5%+17.0% / +0.7% / +51.8%100% / 100% / 80%
Long treesDFS-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, which loses cache hits). 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%).

The claim of preserving latency is broader than the reported evidence.

And

Can you provide p99 TTFT and SLO violation rates, particularly for zero-bid and low-budget users?

We computed p95 and p99 TTFT, p99 TTFT across bid quartiles (from Q1 lowest to Q4 highest), and SLO violation rates (how often TTFT exceeds NO-SORT's median TTFT in each trial) at n = Q, along with the zero-bid queries from Figure 3:

Workload / GroupDFS-BIDDFS-UNIFORMBID-SORTNO-SORT
Stars: p95 / p99 TTFT (SLO viol.)292s / 309s (4%)310s / 313s (11%)580s / 602s (48%)594s / 619s (50%)
Chains: p95 / p99 TTFT (SLO viol.)409s / 425s (0%)417s / 433s (0%)1011s / 1053s (50%)1003s / 1052s (50%)
Long trees: p95 / p99 TTFT (SLO viol.)87s / 88s (0%)86s / 88s (0%)1061s / 1107s (50%)1047s / 1091s (50%)
Stars Q1..Q4 p99 TTFT (s)313 / 297 / 275 / 265312 / 313 / 312 / 313609 / 460 / 304 / 150618 / 617 / 616 / 617
Stars Q1 (lowest bids) SLO viol.4.7%10.2%100%46.9%
Zero bidders: mean / p99 TTFT (SLO viol.)86s / 151s (9%)75s / 151s (9%)143s / 278s (47%)150s / 302s (50%)

DFS-BID has basically the same tail TTFT as DFS-UNIFORM, and cuts Q1's p99 TTFT in half compared to BID-SORT. Because we finish one batch before starting the next and keep requests with shared prefixes together, we still serve zero-bid users (and users who run out of budget) alongside the rest of their prefix group, so they don't starve -- and anyone who bids zero pays nothing.

Does measured TTFT include batch formation, ordering, payment computation, and autobidding overhead? Which components lie on the admission critical path?

In the main text, we start timing TTFT once we send the batch to SGLang, so it doesn't include time spent waiting for a batch to form (we include that waiting time in Appendix D.7). Before sending requests to SGLang, we only build the radix tree and sort subtrees by average bid, which takes under 1 ms for 1,024 requests -- and SGLang already maintains a radix tree anyway. We compute VCG payments (~34 ms, Appendix D.10) and update the autobidders' multipliers (just a multiply and an add per user) after sending the batch, so they don't add any latency.

The baselines do not adequately evaluate the proposed market design.

And

How does the mechanism compare with fixed-price priority tiers under comparable workloads and budgets?

We ran new SGLang experiments (n = Q) comparing to 2 tier (top ~19% of bids) and 3 tier (top 10% / next 30% / bottom 60%) fixed price priority, both flat (where we sort by tier in arrival order and ignore the tree) and inside the DFS (where we replace each bid with its tier price, 2/1 or 3/2/1, and sort subtrees by average):

OrderStars WelfareStars HitStars Mean TTFTChains WelfareChains HitChains Mean TTFT
DFS-BID+14.4%0.5978s+17.4%0.74110s
2 tiers in DFS+11.3%0.6077s+8.5%0.76108s
3 tiers in DFS+11.6%0.5983s+9.5%0.74112s
DFS-UNIFORM+2.1%0.6075s+1.3%0.76108s
2 tiers flat+30.7%0.21148s+38.3%0.49261s
3 tiers flat+38.9%0.21149s+45.4%0.49261s
BID-SORT+43.7%0.23145s+50.5%0.48266s

Flat tiers break up shared prefixes and roughly double mean TTFT, much like BID-SORT. Putting tiers inside the DFS keeps cache hits high and gets ~50-75% of DFS-BID's welfare gain over DFS-UNIFORM, while continuous bids get the rest for free. We also tested SGLang's own schedulers directly: lpm switches back to FCFS whenever more than 128 requests are in the queue (changing welfare by < 1%), and dfs-weight matches DFS-UNIFORM's hit rate but runs 25-55% slower because it traverses the tree of cached tokens rather than queued requests.

The autobidding evaluation is limited.

This is by design, as we view our primary contribution as being conceptual/theoretical, and even then we chose to focus most of our experiments on the welfare and throughput of our inference auctions in order to highlight the practicality of our methods. We believe that a more thorough exploration of autobidding in inference auctions is an exciting direction for future research, but is beyond the scope of this work.

Still, we ran a comparison on our 60 batch setup (Appendix D.11) against a simple heuristic (bidding truthfully until the budget runs out), fixed pacing (μ = 0.5), and the best fixed μ in hindsight:

WorkloadPacing (Alg. 3)Naive (until out)Fixed μ = 0.5Best Fixed μ (oracle)
Stars net utility (% out of budget)6605 (13%)6503 (19%)7043 (6%)7518 (0%)
Chains net utility (% out of budget)7825 (13%)7218 (43%)8090 (7%)8735 (1%)

Algorithm 3 beats the naive heuristic, runs out of budget much less often, and gets almost 90% of the best fixed multiplier in hindsight.

What guarantees remain when multiple adaptive autobidders interact or users strategically alter request submissions?

And

The regret theorem assumes i.i.d. auction instances, whereas interacting adaptive autobidders may induce nonstationary competing bids.

This difference between what we proved and our experimental setting was an intentional choice on our part. It is difficult to prove things about the game dynamics when there are multiple adaptive autobidders, due to the budget constraints introducing a dependence across time. Moreover in practice, we suspect that each autobidder will be interacting with many different autobidders, each of whom will only share a subset of the auctions with one another. It would be interesting to explore these directions further in future work.

To clarify your other questions: Theorem 4.4 holds in every batch no matter how multipliers change over time, and VCG only makes truthful bidding optimal within a fixed batch -- it doesn't stop users from gaming when they submit requests, splitting prompts up, or using multiple accounts. Also, we only suggested adding a batch timeout in Appendix D.7; we didn't run experiments with one.

The authors have addressed most of my concerns. I’ll keep my rating.

Thanks for your reply. Given that we've addressed most of your concerns, we'd appreciate it if you would consider flipping your rating from reject to accept. We'd be happy to address any additional concerns you may have.

Comments on the paper

1 comment

Hi everyone,

Thank you for taking the time to review our submission. We'd appreciate it if you could read our rebuttals and respond, as we've ran a few extra experiments that should clear up all of your concerns.

Best,

Authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.