Learning the Cost of Reliable Inference
Dimitrios Rontogiannis, Ander Artola Velasco, Manuel Gomez Rodriguez
cs.AI, cs.GT, cs.LG
2026-09-24
Second-price routing prices each qualified query at the runner-up provider's cost. Margins are 71% on GSM8K (37% over list) and 10% on GPQA (12% under list).
Routing sites already help a user pick a model. Providers on those sites still charge a fixed price per token. Cost and accuracy move with the task; the posted rate does not. The introduction makes the gap concrete: two providers list $0.06 and $0.07 per token while their costs are $0.01 and $0.04. Similar quality, and the user pays $0.06. Bid only on this task, and the price can fall to $0.04, the point at which the second-cheapest provider would lose money and drop out.
Under list prices that spread stays with the cheaper provider. Artificial Analysis and OpenRouter still compare or route on posted rates. This work, from the Max Planck Institute for Software Systems, turns the intermediary into a procurement platform. The user sets a quality floor. Competition sets the unit price.
One user has a fixed task. N LLM providers sit on the other side. The user chooses a quality threshold qmin, a floor on average accuracy. The analysis assumes at least two providers clear it. If only one looks qualified, that provider is paid the cost cap cmax. Providers do not know the query count T. Each keeps a standing bid between 0 and cmax. Each round the platform assigns one query. The winner answers, pays the compute cost, and receives a score from 0 to 1. Only the winner may change its bid.
Quality is the mean of past scores plus a radius β that shrinks as the provider is sampled. The radius is a Hoeffding bound at a level δ chosen by the platform. A provider enters the optimistic qualified set only when mean plus β still meets qmin. With probability at least 1−δ, every truly qualified provider stays in that set on every round.
A sublinear schedule g(t)=k(t/N)^α says how often each provider must be tried. Among optimistic-qualified providers that have not yet been picked g(t) times, the platform samples uniformly and pays cmax, ignoring bids. The user pays for this exploration. Once everyone eligible has been sampled enough, the platform picks the smallest bid minus cmax·β. Subtracting β favors providers with thin samples, so the platform does not lock onto a winner too early.
Payment is a reverse second price. Think of a procurement tender: the low bidder wins, and the check is written from other people's bids. The winner receives its own confidence bonus plus the lowest adjusted bid among the other optimistic-qualified providers, capped at cmax. The first N rounds give each provider one query at the same cap, so the averages are defined.
A provider bids the average cost of queries it has already served. It does not need to know its mean cost in advance. Theorem 2 says this bid is a robust equilibrium. Rival types and T are unknown, so the provider cannot rule out that the current query is the last one. The payment ignores its own bid, and the lowest quote that does not lose money in expectation is the cost estimate. A deviation that flips whether it wins makes the worst case strictly worse.
When every provider bids this way, two guarantees hold with probability at least 1−δ. Theorem 3: all but a vanishing fraction of queries go to i, the qualified provider with the lowest mean cost. Smaller quality gaps and smaller cost gaps send more queries elsewhere. Theorem 4: average payment converges to c̄(2), the second-lowest mean cost in the qualified set. That runner-up cannot keep pricing under its own cost, so c̄(2) is the floor competition can support. At α=2/3 the gap shrinks like T to the power −1/3, times a log factor. The experiments use α=3/4 and k=2, which explores harder early and converges more slowly.
Providers are simulated. Each serves one Llama or Qwen Instruct model, and each answer is drawn from a public log of 128 generations per question per model. Costs are not metered. They are Hugging Face list prices divided by 1.25, a uniform 25% margin the platform never sees. A correct answer scores 1 and a wrong one scores 0. qmin sits midway between two adjacent accuracies. Each setting runs T=70,000 queries and is repeated 30 times. Money is in units of 1e-6 dollars per query. δ=0.05. The simulated providers bid the equilibrium strategy exactly.
The margin is the final-pass payment on non-exploration steps, relative to the winner's own cost. Competition is strong when the second-lowest qualified cost sits under the winner's list price.
| Setting | Winner | Cost | List price | 2nd-lowest cost | Non-explore pay | Margin | Final-pass share |
| GSM8K, N=9, qmin=0.764, 3 qualified | Qwen2.5-3B | 16.1 | 20.1 | 34.4 | 27.5 (30.3 overall) | 71% | 0.96 |
| GPQA, N=4, qmin=0.145, 2 qualified | Llama-3.1-8B | 43.0 | 53.8 | 50.7 | 47.4 (48.3 overall) | 10% | 0.97 |
GSM8K has 1,319 grade-school problems, about 53 passes, and the qualified rivals are much more expensive. On the final pass the non-exploration payment is 27.5: 71% above cost 16.1, 37% above list price 20.1, and still short of c̄(2)=34.4. Routing through the auction costs more than paying the winner's posted price.
GPQA has 546 graduate science questions, about 128 passes, and the only qualified rival is slightly more expensive. Payment is 47.4: 10% above cost 43.0, 12% below list price 53.8, and closer to c̄(2)=50.7.
On the final pass at least 96% of queries go to i. It becomes the most selected provider after about 10,000 queries on GSM8K and 30,000 on GPQA, well before the theorem's checkpoints of 63,740 and 153,697. GPQA is slower because Llama-3.2-1B sits only 0.037 under qmin and takes about 11,000 queries to drop out. Until then, cheap unqualified models pull the non-exploration payment below the winner's cost.
Choosing the cheapest listed model that clears a bar saves the user from picking the wrong model. It does not pull out the spread between qualified providers on one task. Here an upper confidence bound holds the quality line, and a second-price rule pushes payment toward the second-lowest qualified cost. With many queries on a stable task, that payment moves toward the competitive floor.
Whether the user beats list price depends on the runner-up. On GSM8K the runner-up is far more expensive, and the auction price sits 37% above the winner's list price, so buying the winner directly is cheaper. On GPQA the runner-up is close, and the user pays 12% under list. The abstract's range, 10% to 71%, is the winner's markup over its own cost. It is not a discount against posted rates.
Section 6 states the assumptions directly. Providers may not bid to maximize worst-case utility. If they know something about T or about rivals, bidding the cost estimate is no longer automatically optimal. The appendix only covers bid deviations bounded relative to the confidence radius.
Small cost gaps, and accuracies that sit on the threshold, need many queries. A gap of 0.037 on GPQA takes about 11,000 queries to resolve. Users pay for exploration. The cheapest qualified provider captures most of the benefit, and the current rule does not move that bill onto providers.
The evaluation is the larger discount. Bidders follow the equilibrium exactly, with no probing and no collusion. Scores are exact-match correctness. On open-ended work, a noisy automatic judge would bend the qualified set. Costs are list prices divided by 1.25, so the cost the platform learns is constructed, not measured from power or hardware. Second-price payments depend on rival bids, and collusion remains possible. With a single qualified provider the payment falls back to cmax, which can exceed the list price.
Read 10% to 71% as the width of the winner's markup under a shared margin assumption. On GSM8K the payment has not reached c̄(2). It is not a saving a user can book by switching platforms.