acceptodds
Under review as a conference paper at ICLR 2027

Learning the Cost of Reliable Inference

Abstract

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 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 datasets. The results show that the pricing margin of the most cost-competitive provider on our platform varies greatly—from to —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.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
LLM routing, mechanism design, online learning, strategic learning, reliable AI

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_a8p1OpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

The paper proposes a procurement platform for LLM inference in which providers bid for a user’s task, and the platform routes queries through a reverse second-price auction combined with UCB-style elimination of providers below a user-defined quality threshold. Providers do not know their own per-task cost and are shown to be worst-case optimal when bidding their running cost estimate. The authors prove that routing concentrates on the cheapest qualified provider and that average payments converge to the second-lowest qualified cost, and support this with simulations on GSM8K and GPQA using Llama and Qwen models.

Critical strengths

Problem framing: Treating LLM routing as a procurement auction rather than price-taking over listed rates is a new and well-motivated angle; the target price cˉ(2)\bar{c}_{(2)} is the natural Bertrand benchmark.

Clean mechanism: The cost-side optimism term cmax⁡β(mi,t)c_{\max}\beta(m_{i,t}) enters both the allocation index and the critical payment, so that truthful bidding and the UCB sandwich (Lemma 5) hold simultaneously. The proofs are complete and easy to follow.

Critical weaknesses

The provider model reduces each provider to a stationary scalar quality and a scalar mean cost, with no latency, throughput, or availability, which existing routing platforms treat as first-class criteria. Bids and payments are per query, while the targeted market prices per token, so the “token price” framing in the abstract does not match the model.

The guarantees hold for a single fixed task distribution and must be relearned per task at considerable cost. Excluding a provider 0.037 below qmin⁡q_{\min} takes about 11,000 queries, and within the first pass over each benchmark 24% to 47% of queries are exploration steps paid at cmax⁡c_{\max} (Tables 8 and 26), borne entirely by the user. The 10%/71% margins are computed on non-exploration steps only, and the appendix baselines are absent from the main text: routing to the lowest listed price among the same estimated-qualified set pays less than the platform over the long run on three of the five rosters (Tables 7,16 and 25), so the net benefit to the user is not established.

Strategic behaviour is assumed away rather than analyzed. The bandit is stochastic, and provider incentives are settled by a worst-case argument that sets T=tT=t, reducing the dynamic game to a one-shot auction. This leaves out an incentive the mechanism itself creates: the critical payment includes +cmax⁡β(mi,t)+c_{\max}\beta(m_{i,t}), so a provider that deliberately loses rounds keeps mi,tm_{i,t} small and is paid more when it next wins. The restriction that only the selected provider may revise its bid, and the absence of any experiment with non-truthful or model-switching providers, leave the strategic-arms setting the paper cites (Braverman et al., 2019; Cao et al., 2026) untested.

Questions for authors
  1. Which step of the proof of Theorem 2 fails if non-selected providers are allowed to update their bids at every round? Is the restriction needed, or only convenient?

  2. If a provider knows TT (or a lower bound on it), is the strategy of overbidding on non-exploration rounds to preserve a large β(mi,t)\beta(m_{i,t}) ever profitable under the stated payment rule? A simulation with one such provider would help.

  3. Can latency or throughput be folded into r(x,y)r(x,y) without breaking the analysis, and if so, what does the resulting scalar threshold mean to a user who wants hard quality guarantees but only soft latency preferences?

2 comments

We thank the reviewer for their thoughtful feedback. Below, we respond in detail to each of the points they raised. In the revised submission, we have highlighted changes in blue.

[Latency] We make no assumptions about the score r(x,y)r(x,y) used by the user to evaluate a model’s response beyond boundedness. Consequently, our theoretical results on the providers’ equilibrium bidding (Theorem 2) and user guarantees (Theorems 3 and 4) remain valid if the user includes other response metrics, such as latency or provider availability, as long as the resulting score is normalized to the interval [0,1][0,1]. For example, for queries with verifiable ground truth, one can define a generalized scalar score as an indicator of whether the model’s response is correct, minus a bounded term penalizing each additional second of latency. This captures how routing platforms such as OpenRouter trade off model quality against latency, throughput, and time to first token [1].

In Appendices E and F of the revised submission, in response to the reviewer’s comment, we have extended our platform and its theoretical guarantees to: (i) multidimensional scores and thresholds, which can encode multiple hard constraints on the mean values of different response metrics, for example, quality and latency, and (ii) a selection and payment rule that accounts for both cost and latency, and thus can encode soft constraints on latency. In extension (i), our theoretical guarantees retain the same form, whereas in extension (ii), we prove that, with high probability, all but a vanishing fraction of queries are routed to the provider offering the best cost and latency tradeoff among those meeting the quality threshold.

[Token price] In the revised abstract, we will clarify that our procurement platform sets prices per response rather than per token.

[Number of required queries] Any routing mechanism seeking to learn unknown provider qualities and costs requires observing a minimum number of responses to user queries, and therefore a sufficient number of routed queries, to provide statistical guarantees. In Theorems 3, 4, and 7, we establish finite-time guarantees on identifying the most competitive qualified provider, payment convergence, and unqualified selections.

[Number of exploration steps] While our experiments show that exploration can initially result in a relatively high number of exploration steps, these rapidly amortize as the platform learns. On the final pass, the fraction of queries assigned to the optimal qualified provider is over 9696% of all queries. Because the reported 1010%/7171% margins are calculated over the final pass, which is heavily dominated by non-exploration steps, these values do not significantly change if computed over both step types, directly resolving the reviewer’s concern.

[Net benefit to the user] The goal of our platform is not to reduce user payments relative to routing to the provider with the lowest listed price (among the same estimated-qualified set). Instead, it is designed to guarantee that users pay task-specific competitive prices. This requires identifying the lowest-cost qualified provider and ensuring that average payments converge to the second-lowest mean cost among qualified providers. Whether this results in users paying higher or lower prices depends on how competitive the LLM market is for the specific user task, as we extensively demonstrate in our experiments in Section 5 and Appendices I, J, and K. We have clarified this in Section 5 of the revised submission.

AuthorsOpenReview ↗

Rebuttal (cont.)

[Optimal strategy under known T] Knowledge of the horizon TT, or a lower bound on it, does not guarantee that deliberately losing early rounds is profitable. The gain depends on competitors’ private costs and qualities. In Appendix G of the revised submission, we give a two-provider example in which overbidding is profitable for every T≥4T \ge 4, while respecting the original standing-bid update rule. In this example, delaying a win lets the competitor’s confidence radius shrink and its adjusted bid increase, raising the later payment. The deviator’s own confidence radius contribution at its win remains unchanged. More generally, note that the term cmax⁡β(mi,t)c_{\max}\beta(m_{i,t}) in the payment is the same for a given number of previous selections, regardless of when the win occurs. This possibility is consistent with Theorem 2, which establishes optimality under a worst-case horizon criterion.

In addition, in Appendix G, we also bound the gain from any unilateral bidding deviation against competitors that bid their cost estimates, even if the deviator knows the horizon and competitors’ types. On the high-probability event E\mathcal E, the cumulative additional estimated profit is at most O(Tα+T1−α/2log⁡T)=o(T)O\left(T^\alpha+T^{1-\alpha/2}\sqrt{\log T}\right)=o(T), yielding a vanishing bound on the gain per query. Consequently, the corresponding expected-utility bound establishes that cost-estimate bidding is an approximate Nash equilibrium.

[Proof of Theorem 2] No step of the proof of Theorem 2 fails if non-selected providers are allowed to (simultaneously) update their bids at every round. Bidding the cost estimate still ensures that payments cover that estimate, and the argument that the current round may be the last remains valid. That said, please note that, at equilibrium, as long as a provider is not selected, the current bid remains optimal for the next round, since its cost estimates have not changed. The restriction is therefore only a convenience. In the revised submission, we have clarified this whenever we state Theorem 2.

References

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

The paper proposes a procurement platform for LLM inference using reverse second-price auctions and online learning. Providers bid their estimated serving costs, while the platform learns which providers satisfy a quality threshold. The authors derive equilibrium bidding and asymptotic allocation and payment guarantees, and evaluate the mechanism through simulations using recorded LLM generations from GSM8K and GPQA.

Critical strengths

The paper considers a relevant economic problem: how competition between LLM providers could affect inference pricing. The proposed combination of quality screening and auction-based allocation is reasonable, and the authors provide a detailed theoretical analysis with finite-time guarantees.

Critical weaknesses
  1. Limited novelty and insufficient justification of the research gap.

The main framework combines established ideas from reverse second-price auctions, incentive-compatible online learning, and confidence-based bandit selection. Closely related work, including Singla and Krause (2013), Patra et al. (2026), and Cao et al. (2026), has already studied procurement mechanisms with learning and strategic providers, including LLM routing.

The authors distinguish their work by allowing providers to learn their own generation costs and establishing convergence to the second-lowest qualified cost. However, the paper does not convincingly explain why these extensions constitute a substantial methodological advance.

The theoretical guarantees also rely on restrictive assumptions, including stationary provider quality and cost distributions, independent repeated queries, and providers adopting a worst-case utility criterion. The bidding result is a maximin guarantee under an unknown horizon, not a general dominant-strategy truthfulness result for strategic providers maximizing expected long-run profit. The paper needs to better justify the relevance of this equilibrium concept.

  1. Artificial evaluation and weak support for the economic conclusions.

The experiments use simulated providers, rather than actual market participants. More importantly, the providers' private costs are not observed: they are constructed by discounting listed prices using an assumed common 25% margin. Providers are also programmed to follow the proposed bidding equilibrium. Thus, the experiments do not independently establish either strategic behavior or actual market inefficiency.

The practical results are not particularly convincing. The highlighted 10%–71% figures describe provider pricing margins, not savings for users. In the GSM8K setting, auction payments are 37% higher than the listed price even after excluding exploration steps. During the first benchmark pass, 69.2% of queries go to unqualified providers, compared with 0.5% under the lowest-listed-price baseline.

The asymptotic guarantees do not resolve this practical issue. The experiments simulate 70,000 queries through repeated sampling from small benchmark datasets, while real workloads may have shorter horizons, changing task distributions, and uncertain quality evaluation.

Finally, the presentation is unnecessarily difficult to follow. The extensive theoretical derivations obscure the main contribution, and many plots and tables use small fonts that make the results difficult to interpret.

Questions for authors
  1. What is the central theoretical novelty relative to existing truthful procurement auctions and bandit mechanisms, particularly Patra et al. (2026)? Which results fundamentally require the proposed new formulation?

  2. How justified is the maximin bidding assumption? Would the claimed equilibrium and convergence guarantees hold for providers maximizing expected long-run profit rather than worst-case utility?

  3. Can the authors provide evidence using actual provider costs and realistic query horizons? In particular, how do they reconcile the claimed pricing and quality benefits with the higher user payments and large share of unqualified selections observed in several experiments?

Singla, Adish, and Andreas Krause (2013). Truthful Incentives in Crowdsourcing Tasks Using Regret Minimization Mechanisms.

Patra, Pronoy, Sankarshan Damle, Manisha Padala, and Sujit Gujar (2026). Truthful Reverse Auctions for Adaptive Selection via Contextual Multi-Armed Bandits.

Cao, Yuhan, Yu Wang, Sitong Liu, Miao Li, Yixin Tao, and Tianxing He (2026). Pay for The Second-Best Service: A Game-Theoretic Approach Against Dishonest LLM Providers.

5 comments

We thank the reviewer for their thoughtful feedback. Below, we respond in detail to each of the points they raised. In the revised submission, we have highlighted changes in blue.

[Methodological advance] In closely related work, including Patra et al. (2026) and Cao et al. (2026), the mechanism handles a single-sided learning problem: the platform learns unknown qualities, but providers bid using oracle knowledge of their own costs. In contrast, in our work, the mechanism handles a dual-sided learning problem. Because providers do not know their costs a priori, they must learn them sequentially through experience. This means their underlying valuations—and consequently their bids—are non-stationary and shifting over time. In standard mechanism design, proving incentive compatibility and convergence relies on static or predictably bounded strategies. Proving that a reverse second-price auction still asymptotically converges to the second-lowest average cost among qualified providers, even when the inputs are learned estimates that fluctuate over time, constitutes a substantial methodological advance. We have clarified this in the comparison with Patra et al. (2026) and Cao et al. (2026) in “Further related work” of the revised submission.

[Stationarity and independent repeated queries] In our procurement platform, and more broadly in any routing platform, the stationarity assumption on the provider quality and cost distributions is reasonable, and not really restrictive, as long as the task distribution and the models used by the providers are fixed. Consequently, Patra et al. (2026) and Cao et al. (2026) also make such an assumption, which is also common in the stochastic multi-armed bandit literature. That said, lifting this assumption to account for model updates over time would be an important direction for future work. We have clarified this in Section 2 of the revised submission.

[Worst-case utility criterion and equilibrium concept] We thank the reviewer for the opportunity to clarify that we do not view the equilibrium concept we build upon—where providers adopt a worst-case utility criterion—as a restrictive assumption; rather, it was a deliberate modeling choice. In routing platforms, providers do not know when the user will stop submitting queries for a given task. Consequently, providers are incentivized to prioritize securing a robust, worst-case payoff to protect their margins against early termination, rather than optimizing for expected long-run profits based on an assumed horizon, which can lead to highly suboptimal payoffs if the queries stop before that horizon. That said, in Appendix D of our original submission, we have theoretically shown that, even when providers deviate from the best response under the worst-case utility criterion, the theoretical guarantees offered by our platform degrade gracefully and, in Appendix L of the revised submission, we have empirically validated this theoretical result.

In this context, please note that, while dominant-strategy truthfulness is highly desirable in static, full-information auctions, it is notoriously difficult to guarantee—and often practically unachievable—in multi-sided online learning environments with non-stationary valuation estimates as in our setting. In our work, by relying on a robust maximin guarantee, we can ensure dominant-strategy truthfulness and derive equilibrium and convergence guarantees. While cost-estimate bidding need not be optimal for providers maximizing expected long-run profit, Appendix G of the revised submission shows that, when a provider faces competitors who bid their cost estimates, deviating from cost-estimate bidding yields an additional estimated profit per query that vanishes asymptotically with high probability.

Finally, we would also like to emphasize that the equilibrium concept we rely upon is well-established in the field of robust game theory (see, e.g., Aghassi and Bertsimas, 2006), and it has been previously used in settings where strategic agents operate with severely limited information about the future duration of the game. In Section 3 of the revised submission, we have expanded our discussion of our equilibrium concept.

AuthorsOpenReview ↗

Rebuttal (cont.)

[Experimental setup] Conducting experiments with actual market participants would require setting up significant infrastructure to deploy our platform and, more importantly, recruit users, frontier model developers, and inference providers to evaluate it. Since this is infeasible, instead, we have conducted experiments with simulated providers using popular open-weight models. In this context, we would like to emphasize that the main goal of our experiments is to validate our theoretical results, and not to validate the assumptions we make about the providers’ strategic behavior and costs. However, to address the reviewer’s concerns, we have included the following additional results in the revised submission.

Regarding the providers’ costs, we originally constructed them by discounting real listed prices using a common margin because both costs and margins are proprietary information, with no reliable public estimates available. In Appendix M of the revised submission, we have conducted an additional sensitivity analysis which shows that, even when the per-token margin varies across providers, our conclusions regarding market inefficiency are qualitatively similar. Specifically, with provider-specific per-token margins ranging from 2020% to 3030%, the winner’s pricing margin is 1.41.4% under strong competition and 46.846.8% under weak competition.

Regarding the providers’ strategic behavior, as discussed previously, we have conducted additional analysis in Appendices G and L of the revised submission. Appendix G shows that, when a provider faces competitors who bid their cost estimates, deviating from cost-estimate bidding yields an additional estimated profit per query that vanishes asymptotically with high probability. Appendix L shows that, even when providers deviate from the equilibrium behavior, our conclusions regarding market inefficiency are qualitatively similar, in agreement with the theoretical analysis in Appendix D of our original submission.

[Real workloads] Our procurement platform is best suited to settings where a large volume of task-specific user queries need to be routed to providers while guaranteeing a minimum quality at the most competitive price. Crucially, this fits a variety of real-world applications, such as routing platforms (e.g., OpenRouter), which route millions of user queries daily, including queries for specific task categories (e.g., shell command execution and code repository analysis) with well-established automated evaluation pipelines. Our experiments show that the platform successfully identifies the most competitive qualified provider within 70,00070,000 queries—a substantially smaller volume than such platforms serve for recurring tasks.

Importantly, any routing mechanism seeking to learn unknown provider qualities and costs requires observing a minimum number of responses to user queries, and therefore a sufficient number of routed queries, to provide statistical guarantees. In Theorems 3, 4, and 7, we establish finite-time guarantees on identifying the most competitive qualified provider, payment convergence, and unqualified selections. Experimentally, we find that these bounds are conservative and that substantially fewer queries are needed in practice.

We have clarified the intended scope and use cases of our procurement platform in Section 2 of the revised submission.

AuthorsOpenReview ↗

Rebuttal (cont.)

[Experimental results] The goal of our platform is not to reduce user payments relative to current listed prices of inference providers. Instead, it is designed to guarantee that users pay task-specific competitive prices. This requires identifying the lowest-cost qualified provider and ensuring that average payments converge to the second-lowest mean cost among qualified providers. Whether this results in users paying higher or lower prices depends on how competitive the LLM market is for the specific user task, as we extensively demonstrate in our experiments in Section 5 and Appendices I, J, and K.

Furthermore, we would like to stress that, in contrast with the heuristic baselines we compare with, our platform provides strong high-probability guarantees on the number of queries assigned to unqualified providers (Theorem 7, Appendix B.7). While our experiments show that exploration can initially result in a relatively high number of unqualified selections as the platform learns which providers qualify, the fraction of queries assigned to the optimal qualified provider approaches 100%. Moreover, please note that the quality performance of the baselines depends on the task. For example, on GPQA under strong competition, the lowest-listed-price baseline the reviewer refers to assigns 99.6% of queries to unqualified providers during the first benchmark pass, compared with 70.7% for our platform (Table 24).

[Presentation] In the revised submission, we have increased the font size of the plots and tables to ease readability.

References

  • Aghassi et al. Robust game theory. Math. Program. 107, 231–273 (2006).
  • Cao et al. Pay for the second-best service: A game-theoretic approach against dishonest LLM providers. Proc. ACM Web Conf. (WWW), 249–260 (2026).
  • Patra et al. Truthful reverse auctions for adaptive selection via contextual multi-armed bandits. Proc. AAMAS (2026).
Reviewer_1QzxOpenReview ↗
Rating
4
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

In this work, the authors propose a mechanism for procurement encouraging competition between inference providers and allowing users to get competitive prices subject to desired quality levels. The authors begin by proposing a procurement platform, defining rules for selecting providers to pass to users, determining provider payouts, and aggregating provider bids. Then, they analyze this platform and show that the optimal bid is always the provider's cost estimate (mean over previous costs in the marketplace interaction), and that it hurts utility to deviate from this strategy. Lastly, they show that the payouts converge asymptotically to the second-lowest mean price, which reflects the best price a user could hope to pay (the lowest price the optimal provider would need to be to be selected over all other providers while maximizing profit). Through experiments, they validate their theoretical results under both weak and strong competition.

Critical strengths

The authors do a thorough theoretical treatment of the platform and optimal provider behavior under this platform. The results are detailed and well-explained, and capture our intuition about the optimal behavior of a provider subject to a competitive market.

Critical weaknesses

The quality component of the procurement marketplace feels like an afterthought. First, how can we expect the scores of previous queries to be indicative of the quality of future responses? For instance, maybe I'm asking some simple algebra questions and then ask the provider to write me a research proposal. Additionally, it seems to be only relevant for filtering for "quality models", but couldn't we just use the set of all models when constructing St\mathcal{S}_t and all your results would still apply?

Questions for authors

See weaknesses.

Just so I understand Fig. 1, in the limit (so no uncertainty in estimation), the winning bid should equal the generation cost (green = yellow), and the payment (red) should converge to the second-best bid (which equals second best generation cost) as predicted by Theorem 4? Why should non-exploration (blue) be below cbar at first? Isn't it an assumption that cheaper providers are low-quality, which isn't necessarily true (although likely)? And lastly, based on your experimental setup, query price (purple) should always be 1.25x larger than the mean cost price which again equals the winning bid?

1 comment

We thank the reviewer for their thoughtful feedback. Below, we respond in detail to each of the points they raised. In the revised submission, we have highlighted changes in blue.

[Quality component] Our procurement platform is best suited to settings where a user routes queries for a specific task (e.g., merging pull requests in a coding environment). Within each task, our analysis assumes that each provider’s quality scores are independent observations from a fixed distribution. Therefore, past scores are informative about the average quality of a provider’s responses to future queries. As the reviewer points out, a provider’s quality on one task need not reflect its quality on another, and our platform can therefore be applied separately to different tasks, identifying the lowest-cost qualified provider for each.

Moreover, please note that our platform also covers settings where the user imposes no quality requirement and only wants the price paid to converge to the most competitive price for the task. In this case, the user can set qmin=0q_\mathrm{min} = 0, in which case Q\mathcal{Q} is the set of all available models. Thus, including all models is a special case of our framework, while quality filtering allows users to impose a minimum average quality requirement.

[Figure 1] The reviewer's asymptotic interpretation of Figure 1 is correct. Under equilibrium bidding, as cost estimates improve and routing concentrates on i∗i^\ast, the average winning bid (yellow) converges to cˉi∗\bar c_{i^\ast}. The green curve is a moving average of the realized generation costs and settles near the same value. Moreover, Theorem 4 guarantees that the long-run average of the payments converges to the second-lowest qualified mean cost, cˉ(2)\bar c_{(2)}; the red curve displays the moving average of these payments.

Early non-exploration payments (blue) can fall below cˉi∗\bar{c}_{i^\ast} because cheaper, unqualified providers have not yet been excluded and still influence the critical payment in Eq. 4. Here, note that we do not assume that cheaper providers have lower quality, but this occurs in our experimental settings (see Figure 2).

Finally, the query price (purple) is exactly 1.25 times the realized generation cost (green), since both curves use the same generations and averaging. The same exact ratio need not hold for the winning bid (yellow), particularly early on: each bid uses the selected provider’s accumulated cost history, whereas the green curve averages costs realized by all providers selected within the plotted window.

We have clarified these interpretations in the discussion of Figure 1 in Section 5 of the revised submission.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.