Learning the Cost of Reliable Inference

• Fixed per-token prices do not reflect task-specific provider costs and response quality, limiting users’ ability to secure the most competitive price.The introduction illustrates the gap with providers charging $0.06 and $0.07 per token, while task-level competition could allow a $0.04 price.Source: §1 · p. 1
• A reverse second-price auction elicits providers’ best estimates of average query-serving costs while the platform learns quality and routes to the lowest-cost provider meeting the quality threshold.With high probability, all but a vanishing fraction of queries go to the most cost-competitive qualified provider.Source: §1 · p. 2
• Pricing margins range from 10% to 71% across tasks and quality thresholds, indicating substantial inefficiency in the current fixed-price market.The authors state that the platform may enable maximum savings when competitive market conditions permit.Source: §1 · p. 2
• The work positions its contribution in LLM service pricing and routing, considering providers as bidders whose costs and serving qualities vary across tasks.It contrasts its setting with Patra et al. [2026], which assumes providers know their task-specific generation costs.Source: §1 · p. 2

• Provider competition lets the platform secure the most competitive pricing at a guaranteed quality level on all but a vanishing fraction of queries.The platform serves users seeking tasks such as coding, mathematical reasoning, or question answering.Source: §2 · p. 3
• Each round, the platform receives a query, selects a provider, grades its response, and sets the payment; the selected provider incurs the query’s generation cost.The score ranges from unsatisfactory (0) to fully satisfactory (1), and the selected provider may update its standing bid.Source: §2 · p. 3
• The platform uses an optimistic quality estimate so that, with probability at least 1 − δ, its estimated-qualified set contains every provider meeting the user’s threshold.The confidence radius accounts for error in the empirical quality estimate.Source: §2 · p. 3
• Providers in the estimated-qualified set who have been selected fewer than g(t) times receive exploration selections; otherwise, the platform favors the lowest optimistic bidding index.The confidence-radius term gives additional advantage to providers whose estimates remain uncertain.Source: §2 · pp. 3–4
• The payment rule builds on second-price auctions: exploration selections receive cmax, while other payments depend on selection history and other providers’ bids, not the winner’s bid.If the minimum in the critical-payment rule is over an empty set, it is treated as +∞; the actual payment is capped at cmax.Source: §2 · p. 4

3 Pricing Inference Through Competition

• When the exploration set is empty, a provider is assigned the query if its bid is below the critical payment threshold and is not assigned if it is above.The threshold depends on other providers’ bids; the payment rule leaves the winner’s payout independent of its own bid, supporting truthful cost bidding.Source: §3 · p. 4
• The platform maintains an optimistic set of providers meeting the quality threshold, exploring under-selected providers before choosing among qualified providers.If no provider is optimistically qualified, the algorithm chooses one uniformly at random; the section’s allocation rule then narrows selection to the qualified provider offering the lowest price.Source: §3 · p. 5
• Bidding the estimated cost of the next query maximizes a provider’s worst-case utility under uncertainty about rivals’ types and the total query horizon.The strategy offers the best worst-case utility for histories compatible with the provider’s observations.Source: §3 · p. 6
• A provider bidding its cost estimate never incurs expected loss, while a deviation that changes assignment lowers its worst-case utility.The argument considers the possibility that the current query is the last one: a deviation can forfeit a profitable query or require serving an unprofitable one.Source: §3 · p. 6
• The profile of cost-estimate bidding strategies is a robust equilibrium.The paper frames the strategy choice as maximizing utility under uncertainty about other providers’ distributions and the query horizon.Source: §3 · p. 6

4 Finding the Lowest Competitive Inference Price

• The platform selects the lowest-cost qualified provider on all but a vanishing fraction of queries.The bound on queries assigned elsewhere is sublinear in the total number of queries.Source: §4 · p. 7
• Small quality shortfalls or cost gaps make providers harder to distinguish from the optimal provider and can increase interim allocation to them.For unqualified providers the bound grows with 1/ε_i^2; for qualified competitors it includes a term growing with 1/∆_i^2.Source: §4 · p. 7
• The average payment converges to the second-lowest mean cost among qualified providers, the lowest price the optimal provider can sustain while remaining cheaper than its nearest competitor.The average difference vanishes at rate max{T^-(1−α), T^-α/2}, up to logarithmic factors; α = 2/3 yields T^-1/3.Source: §4 · pp. 7–8

5 Experiments

• The experiments use GSM8K grade-school math problems with nine providers and GPQA graduate-level science questions with four providers.The datasets contain 1,319 and 546 questions, respectively; responses are scored as correct or incorrect, and each experiment simulates 70,000 queries across 30 runs.Source: §5 · p. 8
• Generation costs are estimated from recorded output token counts and Hugging Face per-token prices, discounted by a fixed 25% margin unknown to the platform.The experiments use recorded generations for each model and benchmark query.Source: §5 · p. 8
• The quality threshold is set midway between adjacent provider qualities, yielding three qualified providers on GSM8K and two on GPQA.The settings represent weak competition on GSM8K and strong competition on GPQA, based on whether the second-lowest qualified cost exceeds the optimal provider’s listed price.Source: §5 · p. 9
• Over the final benchmark pass, the platform routes at least 96% of queries to the optimal provider, which becomes most selected after roughly 10,000 GSM8K and 30,000 GPQA queries.Both milestones precede the theoretical guarantee thresholds; the text describes the sample-complexity bounds as conservative in practice.Source: §5 · p. 9
• GPQA identification takes longer because an unqualified Llama-3.2-1B model is only 0.037 below qmin and requires about 11,000 queries to exclude.The near-threshold model delays statistical exclusion from the qualified set.Source: §5 · p. 9
• On GPQA, average payment lies 10% above generation cost and 12% below listed price; on GSM8K, it lies 71% above cost and 37% above listed price.These final-pass non-exploration payments reflect the strength of competition among qualified providers.Source: §5 · p. 10

Methodology

• The analysis assumes providers bid their current cost estimate; bounded bid deviations are considered, while other game-theoretic solution concepts remain open.Small provider cost differences or quality near the threshold can also require relatively many queries; the platform places exploration costs on users.Source: §6 · p. 10

Evaluation

• Evaluation uses simulated providers, verifiable benchmark outputs, and generation costs estimated by discounting public token prices by 25%.The authors identify open-ended queries, precise cost profiling, and real-world production evaluation as future steps.Source: §6 · p. 10

Practical considerations

• The platform assumes it can accurately estimate response quality; viability in domains without established metrics depends on progress in LLM evaluation.Source: §6 · p. 10
• Because second-price auction payments depend on competitors’ bids, the mechanism may be vulnerable to manipulation or collusion [Hendricks and Porter, 1989, Mailath and Zemsky, 1991, Che et al., 2018].Source: §6 · p. 10

7 Conclusions

• Pricing margins vary from 10% to 71% by task and quality threshold, while the platform routes all but a vanishing fraction of queries to the most cost-competitive qualified provider.The theoretical pricing margin converges to the difference between that provider’s average cost and the second-lowest average cost among qualified providers.Source: §7 · pp. 10–11

A.1 Concentration inequalities for the qualities and costs

• With probability at least 1 − δ, empirical quality and cost averages are simultaneously close to their population averages across providers and selection counts.Source: §A.1 · p. 15

A.2 Properties of exploration steps

• Exploration selections are bounded by the exploration schedule, while qualified providers remain in the estimated-qualified set on the high-probability event.In particular, the estimated-qualified set is nonempty after initialization under that event.Source: §A.2 · pp. 16–17

A.3 Properties of non-exploration steps

• For qualified but suboptimal providers, selection at non-exploration steps is limited by the cost gap, and eventually stops once the selection count exceeds its bound.Source: §A.3 · pp. 18–19

A.4 Elimination of unqualified providers

• Each unqualified provider is selected only a bounded number of times after initialization and cannot be selected once its count exceeds that bound.Source: §A.4 · p. 19

A.5 Selection and identification bounds

• With probability at least 1 − δ, a fraction tending to one of queries is assigned to the lowest-cost qualified provider.The result follows by bounding selections of unqualified and qualified-suboptimal providers; after the stated count conditions hold, every non-exploration step selects the optimal provider.Source: §A.5 · p. 21

A.6 Generic cumulative counting and confidence-radius bounds

• A generic counting argument bounds the sum of confidence radii along selected providers, independently of whether steps are exploratory.The bound is used in the proof of Theorem 7.Source: §A.6 · p. 21

A.7 User performance guarantees

• On event E, the analysis bounds cumulative quality shortfall under qmin, unqualified-provider assignments, and generation-cost regret relative to optimal provider i*.The generation-cost regret guarantee assumes all providers use their equilibrium strategy.Source: §A.7 · pp. 22–23

A.8 Payments on exploration and non-exploration steps

• Under event E and equilibrium strategies, Theorem 9 bounds user payments across initialization, exploration, and non-exploration rounds.Exploration steps pay the selected provider cmax; non-exploration payments depend on the adjusted bid of the cheapest competing eligible provider.Source: §A.8 · p. 25

A.9 Payment convergence

• With probability at least 1 − δ, payments on every non-exploration step after T0 approach the second-cheapest qualified provider’s mean cost as time grows.The theorem also bounds average excess payment for every T > T0.Source: §A.9 · p. 28

A.10 Robust optimality of the truthful strategy

• At a fixed history, bidding the provider’s cost estimate is the best per-step choice for its net payment.The result concerns each step’s net payment as a function of the provider’s bid.Source: §A.10 · p. 29
• Under truthful bidding, every step’s gain is nonnegative, making conditional expected utility nonnegative and nondecreasing over finite horizons, with its infimum attained at the current step.Conditional on the history at that step, the net payment does not depend further on other providers’ types.Source: §A.10 · p. 30
• At the current step, the proof compares any alternative bid with truthful bidding and establishes a strict comparison when the step is not exploration and the alternative bid’s gain is lower.The comparison applies for every realization of the platform’s draw.Source: §A.10 · p. 30

Resulting guarantees

• The user-facing guarantees extend to Bayesian estimators with the radius widened by 1 + γ and unchanged asymptotic rates.The ordinary-step selection threshold for a qualified suboptimal provider grows with γ, while the quality guarantee remains unchanged.Source: B Bayesian cost estimation · pp. 31–32

Estimation model

• Bayesian providers use posterior-mean cost estimates, with the prior constrained to move the estimate from the empirical mean by at most a fixed multiple of the confidence radius.The constant γ describes the estimation rule; γ = 0 recovers the empirical mean.Source: B Bayesian cost estimation · p. 31

Bayesian variant of the mechanism

• The Bayesian mechanism widens the cost-estimation radius by 1 + γ in adjusted bids and critical payments, while leaving quality estimates, qualification, exploration, and payment caps unchanged.Providers bid their current estimate, and utility is evaluated relative to that estimate.Source: B Bayesian cost estimation · p. 31

Resulting guarantees

• Average payments still converge to the second-cheapest qualified provider’s mean cost for fixed γ.The payment bounds use the widened radius, which vanishes with more observations.Source: B Bayesian cost estimation · p. 32

Provider incentives

• Bidding the current cost estimate remains worst-case optimal for any estimator valued in [0, cmax], without requiring Assumption 1.This holds in the Bayesian variant as well as the original mechanism.Source: B Bayesian cost estimation · pp. 31–32

Selection and identification

• The quality-estimation and forced-exploration results do not depend on bids, so unqualified providers are eliminated and the quality guarantee remains unchanged under bounded deviations.Cost-based identification is affected through the bid-dependent results instead.Source: C Robustness to deviations from… · p. 33
• When a qualified competitor’s cost gap is at most d− + d+, the platform need not identify the cheapest provider, but its ordinary-round selection is within d− + d+ plus a vanishing term in mean cost.The selected provider is qualified on all but the rounds bounded by Lemma 8.Source: C Robustness to deviations from… · p. 34

Generation-cost regret

• Average generation-cost regret is bounded by d− + d+ plus a term that vanishes with the horizon, regardless of cost gaps.This bound follows under Assumption 2.Source: C Robustness to deviations from… · p. 34

Summary

• Under bounded deviations, qualified providers are served on all but bounded rounds; the platform identifies the lowest-cost qualified provider when competitors are more than d− + d+ costlier, and otherwise selects a qualified provider within d− + d+ in mean cost.Average payments converge to within [c̄(2) − d−, c̄(2) + d+]; the quality guarantee is unchanged.Source: C Robustness to deviations from… · p. 35

Payments

• Underbidding lowers the payment guarantee’s lower side by at most d−, while overbidding raises its upper side by at most d+; neither changes the quality guarantee.Setting both deviation bounds to zero recovers the original theorems.Source: C Robustness to deviations from… · p. 35

Summary

• With d− = d+ = 0, the bounded-deviation results recover the original theorems verbatim.For the Bayesian variant, the same statements hold with the cost-estimation radius multiplied by 1 + γ.Source: C Robustness to deviations from… · p. 35

Recorded generation data

• The simulator uses recorded generations for GSM8K and GPQA, retaining correctness, token counts, and reward scores rather than prompts or generated text.It includes 1,319 GSM8K questions and 546 GPQA questions, or 545 for experiments requiring aligned Best-of-n_i records.Source: D Experimental details · p. 36

Provider construction

• Providers combine a base model with service multiplicity n_i; Best-of-n_i generates multiple candidates, returns the highest-reward candidate, and incurs generation cost for every candidate.The ladder roster creates a cost–quality trade-off within each base model.Source: D Experimental details · pp. 36–37

Empirical quality, price, and cost

• Query price is the listed token rate multiplied by all sampled output tokens, while private generation cost is constructed from that price using a fixed margin unavailable to the platform.Quality and cost parameters are derived from the same recorded sampling procedure.Source: D Experimental details · p. 37

Settings and metrics

• Quality thresholds are placed midway between adjacent empirical provider qualities, and experiments report quality, cost, price, payment, and provider-selection outcomes.The experimental settings table reports thresholds, benchmark sizes, qualified-provider counts, and the lowest-cost qualified provider.Source: D Experimental details · pp. 37, 39

Routing policies

• The main routing comparisons are uniform selection among eligible providers, lowest listed price among eligible providers, and lowest listed price without quality screening.A no-quality-filter platform ablation isolates the contribution of online quality screening.Source: D Experimental details · p. 38

Horizons and long-run evaluation

• Long-horizon resampling reuses observed benchmark questions and recorded generations, so the resulting evidence remains conditional on those empirical pools.It does not create new questions or model generations.Source: D Experimental details · p. 39

E.1 Providers and environment

• Figure 2 plots provider quality against mean query price and marks qmin; on the full roster i∗ has the lowest listed price, while on the ladder roster that price is shared by two unqualified providers.The setting uses expected costs and prices per query; Table 5 describes provider costs, prices, quality gaps, and selection bounds.Source: Figure 2 · p. 40, Table 4 · p. 41, Table 5 · p. 41

E.2 One-pass behavior

• On the full roster, the two listed-price rules coincide because the lowest listed price belongs to i∗; Figure 3 compares quality regret per step with generation cost per query.One-pass outcomes are averaged over 30 paired runs with 95% confidence intervals.Source: Figure 3 · p. 42, Table 6 · p. 42

E.3 Long-horizon learning and identification

• On the ladder roster, the no-filter rules retain all N providers, while the filtered listed-price rule rules out only providers it samples before settling on i∗.Figure 5 tracks provider selections and identification; its full-roster listed-price rules coincide.Source: Figure 5 · p. 44, Figure 6 · p. 45

E.4 Regret and theoretical bounds

• Figure 9 compares cumulative quality regret, generation regret, and excess payment with their bounds; the regrets include exploration steps, but excess payment excludes them.The diagnostics cover the long horizon of T = 70,000 queries.Source: Figure 9 · p. 49, Table 9 · p. 50

E.5 Payments and provider outcomes

• Figure 10 tracks realized generation cost, query price, payment, winning bid, and non-exploration payment; early platform payments include exploration steps paid at cmax.Figure 11 shows non-exploration payments within provider-specific bounds that close as selection counts grow; Table 11 defines the reported economic quantities.Source: Figure 10 · p. 52, Table 11 · p. 52, Figure 11 · p. 53

F.1 Providers and environment

• Figure 12 plots provider quality against mean query price and marks qmin; the lowest listed price belongs to a qualified provider on the full roster, but is shared by two unqualified providers on the ladder roster.Table 14 lists providers by mean generation cost and defines the quality gaps and corresponding selection bounds.Source: Figure 12 · p. 54, Table 14 · p. 55, Table 13 · p. 55

F.2 One-pass behavior

• Within one pass, the quality filter rules out no provider on either roster, so the two listed-price rules coincide.Figure 13 compares quality regret per step with generation cost per query; Table 15 reports one-pass outcomes over 30 paired runs.Source: Table 15 · p. 56, Figure 13 · p. 56

F.3 Long-horizon learning and identification

• On the full roster, the single unqualified provider is never ruled out, so the number of providers remaining under the quality filter stays at N; on the ladder roster, the no-filter rules stay at N.The identification horizon lies beyond T = 70,000 on both rosters.Source: F GPQA weak-competition experiments · p. 54, Figure 16 · p. 59

F.4 Regret and theoretical bounds

• Figure 19 compares cumulative quality regret, generation regret, and excess payment with their bounds; the regrets include exploration, while excess payment is also assessed without exploration.The long-run diagnostics are evaluated at T = 70,000 queries.Source: Figure 19 · p. 63, Table 18 · p. 64

F.5 Payments and provider outcomes

• Figure 20 tracks costs, prices, and payments, with early platform payments including exploration steps paid at cmax; Figure 21 shows provider-specific payment bounds closing as selection counts grow.Table 20 reports one-pass economic quantities, distinguishing the platform payment from query prices used for other rules.Source: Figure 20 · p. 66, Table 20 · p. 66, Figure 21 · p. 67

G.1 Providers and environment

• On the strong-competition roster, both lowest-listed-price providers are unqualified; Figure 22 plots provider quality against mean query price and marks the quality threshold.The roster includes the newest large model and the smallest model of each family, with both large models qualifying and both small models not qualifying.Source: Figure 22 · p. 68, G GPQA strong-competition experiment · p. 68, Table 22 · p. 69

G.2 One-pass behavior

• Within one pass, the quality filter rules out no provider, so the two listed-price rules coincide.Table 24 reports one-pass outcomes as means with 95% half-widths over 30 paired runs.Source: Table 24 · p. 70, Figure 23 · p. 70

G.3 Long-horizon learning and identification

• The two listed-price rules coincide until the filter rules out the two cheap providers; Figure 24 tracks identification and the number of providers remaining under the filter.The long-horizon roster outcomes are measured at T = 70,000 queries.Source: Figure 24 · p. 71, Table 25 · p. 72

G.4 Regret and theoretical bounds

• Figure 27 compares cumulative quality regret, generation regret, and excess payment with their bounds; the regrets include exploration steps, but excess payment excludes them.The theoretical diagnostics cover the long run of T = 70,000 queries.Source: Figure 27 · p. 74, Table 27 · p. 75

G.5 Payments and provider outcomes

• Figure 28 tracks generation costs, query prices, and payments, while its second panel places non-exploration payments within the payment bounds; Table 29 reports one-pass economic quantities.The figure’s monetary values are in units of 10^-6 USD.Source: Figure 28 · p. 76, Table 29 · p. 76