Test-Time Compute Games

Ander Artola Velasco; Dimitrios Rontogiannis; Stratis Tsirtsis; Manuel Gomez-Rodriguez

cs.CYJan 29, 2026

Test-Time Compute Games

Authors: Ander Artola Velasco, Dimitrios Rontogiannis, Stratis Tsirtsis, Manuel Gomez-Rodriguez

Organizations: Max Planck Institute for Software Systems, Kaiserslautern, Germany · Hasso Plattner Institute, Potsdam, Germany

Abstract

Test-time compute has emerged as a promising strategy to enhance the reasoning abilities of large language models (LLMs). However, this strategy has in turn increased how much users pay cloud-based providers offering LLM-as-a-service, since providers charge users for the amount of test-time compute they use to generate an output. In our work, we show that the market of LLM-as-a-service is socially inefficient: providers have a financial incentive to increase the amount of test-time compute, even if this increase contributes little to the quality of the outputs. To address this inefficiency, we introduce a reverse second-price auction mechanism where providers bid their offered price and (expected) quality for the opportunity to serve a user, and users pay proportionally to the marginal value generated by the winning provider relative to the second-highest bidder. To illustrate and complement our theoretical results, we conduct experiments with multiple instruct models from the $\texttt{Llama}$ and $\texttt{Qwen}$ families, as well as reasoning models distilled from $\texttt{DeepSeek-R1}$ , on math and science benchmark datasets.

Figures & tables

\Block [fill=gray!10] Perfect rationality	\Block [fill=gray!10] Bounded rationality
$\displaystyle\mathds{1}\left\{V_{i}(\theta_{i})>\max\left\{\bm{V}_{-i}(\bm{\theta}_{-i})\right\}\right\}$	$\displaystyle\frac{e^{\beta V_{i}(\theta_{i})}}{e^{\beta V_{0}}+\sum_{j=1}^{N}e^{\beta V_{j}(\theta_{j})}}$

Table 1: Market share function,

s_{i}(V_{i}(\theta_{i});\bm{V}_{-i}(\bm{\theta}_{-i}))

Panel of Figure 1 — Figure 1: User values offered by providers in a test-time compute game. The figure shows the user values $V_{i}(\theta)$ offered by providers in a test-time compute game $\mathcal{G}$ , as a function of their test-time compute $\theta$ . Panel (a) corresponds to a test-time compute game with $N=9$ providers serving non-reasoning models from the Llama and Qwen families, where providers use best-of-n across $\theta$ samples as their test-time compute method. Panel (b) corresponds to a game with $N=3$ providers serving reasoning models distilled from DeepSeek-R1 , where $\theta$ represents reasoning effort, defined by binning the model outputs into quantiles based on the number of reasoning tokens (see Appendix D ). In both games, providers serve queries $Q$ from the GSM8K dataset, and we consider that each (average) percentage point of accuracy offers a value of $\$ 0.008$ to the users.

Panel of Figure 2 — Figure 2: Dynamics of a test-time compute game. The figure illustrates the better-response dynamics of a test-time compute game $\mathcal{G}$ when providers sequentially select a test-time compute level that increases their utility. The upper panels show the compute levels $\theta^{t}$ selected by each provider and the resulting market inefficiency (dashed black curve), defined as $\max_{\bm{\theta}}\text{W}(\bm{\theta})/\text{W}(\bm{\theta}^{t})$ , and the lower panels show the market share of each provider. Panel (a) and Panel (b) correspond to the games described in Figure 1 , where providers serve, respectively, non-reasoning from the Llama and Qwen families, and reasoning models distilled from DeepSeek-R1 . Here, we set $\beta=1000$ .

	Non-reasoning		Reasoning
	Game $\mathcal{G}$	Auction $\widetilde{\mathcal{G}}$	Game $\mathcal{G}$	Auction $\widetilde{\mathcal{G}}$
Compute level ( $\theta$ )	16	2	4	4
User value	5.5	7.1	7.1	7.3
Price	1.2	0.32	0.18	0.30
Provider(s’) utility	0.25	0.18	0.04	0.12
Social welfare	5.8	7.3	7.1	7.4

Table 2: Comparison of the equilibrium between

\mathcal{G}

and the auction

\widetilde{\mathcal{G}}

. The table compares the equilibrium outcomes of the test-time compute games

\mathcal{G}

(

\beta=1000

) in Figure 1 with the outcomes of the auction

\widetilde{\mathcal{G}}

for the same set of providers using best-of-n with non-reasoning models, and chain-of-thought with reasoning models. For

\mathcal{G}

, the table shows the providers’ average utility, the users’ average value and price, all weighted by their equilibrium market shares, together with the social welfare. For

\widetilde{\mathcal{G}}

, where the auction winner is Qwen2.5-7B , followed by Qwen2.5-3B and R1-D-Qwen-7B, followed by R1-D-Qwen-1.5B , respectively for non-reasoning and reasoning models, the table shows the value received by the user (once the auction is conducted), the price they pay (according to Eq. 10 ), the provider’s utility, and the social welfare. All quantities (except the compute level) have units

(\

\times 10^{-3})$ .

Appendix figures & tables52 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 3 — Figure 3: Accuracy of Llama and Qwen models on GSM8K using majority voting and best-of-n. Panels (a) and (b) show the average accuracy of various LLMs from the Llama and Qwen families over questions from the GSM8K dataset, where the responses of the models are obtained using majority voting or best-of-n, respectively. Panel (c) shows, as a function of the number of samples used to generate the response, the total number of tokens that the models generate to obtain the response to each question, averaged across questions. We show $95\%$ confidence intervals obtained by bootstrapping $50$ times.

Panel of Figure 4 — Figure 4: Accuracy of reasoning models distilled from DeepSeek-R1 on GSM8K using chain-of-thought. Panel (a) shows the average accuracy of various reasoning models from the Llama and Qwen families distilled from DeepSeek-R1 over questions from the GSM8K dataset. Here, the reasoning effort is defined by binning the model outputs into quantiles based on the number of reasoning tokens (see Appendix D ). Panel (c) shows, as a function of the reasoning effort, the total number of tokens (including reasoning and non-reasoning tokens) that the models generate as a response to each question, averaged across questions. We show $95\%$ confidence intervals obtained by bootstrapping $50$ times. Refer to Appendix D for further details regarding the evaluation of the models. The reported accuracies are computed only over outputs in which the model generates at least $5$ reasoning tokens and does not exceed the maximum generation length of $2048$ tokens (see Appendix D for more details).

Panel of Figure 5 — Figure 5: Accuracy of Llama and Qwen models on AIME using majority voting and best-of-n. Panels (a) and (b) show the average accuracy of various LLMs from the Llama and Qwen families over questions from the AIME dataset, where the responses of the models are obtained using majority voting or best-of-n, respectively. Panel (c) shows, as a function of the number of samples used to generate the response, the total number of tokens that the models generate to obtain the response to each question, averaged across questions. Here, we compute the accuracies for majority voting, and best-of-n are computed across the same outputs, and hence both majority voting and best-of-n generate the exact same number of average tokens. We show $95\%$ confidence intervals obtained by bootstrapping $50$ times. Refer to Appendix D for further details regarding the evaluation of the models.

Panel of Figure 6 — Figure 6: Accuracy of reasoning models distilled from DeepSeek-R1 on AIME using chain-of-thought. Panel (a) shows the average accuracy of various reasoning models from the Llama and Qwen families distilled from DeepSeek-R1 over questions from the AIME dataset. Here, the reasoning effort is defined by binning the model outputs into quantiles based on the number of reasoning tokens (see Appendix D ). Panel (c) shows, as a function of the reasoning effort, the total number of tokens (including reasoning and non-reasoning tokens) that the models generate as a response to each question, averaged across questions. We show $95\%$ confidence intervals obtained by bootstrapping $50$ times. Refer to Appendix D for further details regarding the evaluation of the models. The reported accuracies are computed only over outputs in which the model generates at least $5$ reasoning tokens and does not exceed the maximum generation length of $2048$ tokens (see Appendix D for more details).

Panel of Figure 7 — Figure 7: Accuracy of Llama and Qwen models on GPQA using majority voting and best-of-n. Panels (a) and (b) show the average accuracy of various LLMs from the Llama and Qwen families over questions from the GPQA dataset, where the responses of the models are obtained using majority voting or best-of-n, respectively. Panel (c) shows, as a function of the number of samples used to generate the response, the total number of tokens that the models generate to obtain the response to each question, averaged across questions. Here, we compute the accuracies for majority voting, and best-of-n are computed across the same outputs, and hence both majority voting and best-of-n generate the exact same number of average tokens. We show $95\%$ confidence intervals obtained by bootstrapping $50$ times. Refer to Appendix D for further details regarding the evaluation of the models.

Panel of Figure 8 — Figure 8: Accuracy of reasoning models distilled from DeepSeek-R1 on GPQA using chain-of-thought. Panel (a) shows the average accuracy of various reasoning models from the Llama and Qwen families distilled from DeepSeek-R1 over questions from the GPQA dataset. Here, the reasoning effort is defined by binning the model outputs into quantiles based on the number of reasoning tokens (see Appendix D ). Panel (c) shows, as a function of the reasoning effort, the total number of tokens (including reasoning and non-reasoning tokens) that the models generate as a response to each question, averaged across questions. We show $95\%$ confidence intervals obtained by bootstrapping $50$ times. Refer to Appendix D for further details regarding the evaluation of the models. The reported accuracies are computed only over outputs in which the model generates at least $5$ reasoning tokens and does not exceed the maximum generation length of $2048$ tokens (see Appendix D for more details).

Panel of Figure 9 — Figure 9: Quality of Llama and Qwen models on TruthfulQA using best-of-n. Panel (a) shows the average quality of various LLMs from the Llama and Qwen families over questions from the TruthfulQA dataset, where the responses of the models are obtained using best-of-n. To measure quality, we use a BLEURT -based score defined as the difference between the maximum similarity to a true reference answer and the maximum similarity to a false reference answer. Panel (b) shows, as a function of the number of samples used to generate the response, the total number of tokens that the models generate to obtain the response to each question, averaged across questions. We show $95\%$ confidence intervals obtained by bootstrapping $50$ times. Refer to Appendix D for further details regarding the evaluation of the models.

Panel of Figure 10 — Figure 10: User values offered by providers in a test-time compute game on GSM8K. The figure shows the user values $V_{i}(\theta)$ offered by providers in a test-time compute game $\mathcal{G}$ , as a function of their test-time compute $\theta$ . Panel (a) and (b) correspond to games with $N=9$ providers serving non-reasoning models from the Llama and Qwen families, where providers use, respectively, majority voting and best-of-n across $\theta$ samples. Panel (c) corresponds to a game with $N=3$ providers serving reasoning models distilled from DeepSeek-R1 , where $\theta$ represents reasoning effort, defined by binning the model outputs into quantiles based on the number of reasoning tokens (see Appendix D ). In both games, providers serve queries $Q$ from the GSM8K dataset, we set $\beta=1000$ and consider that each (average) point of accuracy offers a value of $\$ 0.008$ to the users.

Panel of Figure 11 — Figure 11: Dynamics of a test-time compute game using majority-voting. The figure shows, for different levels of user rationality $\beta$ , the better-response dynamics of a test-time compute game $\mathcal{G}$ where $N=9$ providers sequentially select a test-time compute level that increases their utility. The upper panels show the compute levels $\theta$ selected by each provider and the resulting market inefficiency $(\text{PoA}(\mathcal{G})-1)$ , and the lower panels show the market share of each provider. Here, all providers use majority-voting across $\theta$ samples as their test-time compute method to serve queries $Q$ from the GSM8K dataset. We consider that providers operate with a margin of $25\%$ between per-token price and per-token cost, and that each (average) point of accuracy offers a value of $\$ 0.008$ to the users.

Panel of Figure 12 — Figure 12: Potential of a test-time compute game using majority-voting. The figure shows, for different levels of user rationality $\beta$ , the evolution of the potential $\Phi$ (see Eq. 7 ) in the test-time compute games in Figure 11 where $N=9$ providers sequentially select a test-time compute level that increases their utility.

Figure 13: Inefficiency of a test-time compute game using majority-voting. The figure shows, as a function of users’ rationality

\beta

, the inefficiency (

\text{PoA}(\mathcal{G})-1

) of the test-time compute game in Figure 11 , where

N=9

providers sequentially select a test-time compute level that increases their utility.

Panel of Figure 14 — Figure 14: Better-response dynamics of a test-time compute game using best-of-n. The upper panels show, for varying levels of user rationality $\beta$ , better-response dynamics when providers serving models from the Llama and Qwen families use best-of-n to serve queries from the GSM8K dataset. The solid colored lines (left $y$ -axis) represent the test-time compute $\theta$ selected by each provider at each iteration, corresponding to the number of samples used for best-of-n. The dashed black line (right $y$ -axis) tracks the Market Inefficiency, defined as $(\text{PoA}-1)\times 100$ (see Eq. 9 ). The lower panels show the evolution of the market share at each time step of the better-response dynamics. The initial compute level $\bm{\theta}^{1}$ is taken as the lowest possible compute. We apply a small vertical jitter to the strategy lines to distinguish overlapping providers and take a fixed profit margin of $25\%$ .

Panel of Figure 15 — Figure 15: Potential of a test-time compute game using best-of-n. The figure shows, for different levels of user rationality $\beta$ , the evolution of the potential $\Phi$ (see Eq. 7 ) in the test-time compute games in Figure 14 where $N=9$ providers sequentially select a test-time compute level that increases their utility.

Figure 16: Inefficiency of a test-time compute game using best-of-n. The figure shows, as a function of users’ rationality

\beta

, the inefficiency (

\text{PoA}(\mathcal{G})-1

) of the test-time compute game in Figure 14 , where

N=9

providers sequentially select a test-time compute level that increases their utility.

Panel of Figure 17 — Figure 17: Better-response dynamics of a test-time compute game using CoT. The upper panels show, for varying levels of user rationality $\beta$ , better-response dynamics when providers serving models from the Llama and Qwen families distilled from DeepSeek-R1 use chain-of-thought to serve queries from the GSM8K dataset. The solid colored lines (left $y$ -axis) represent the test-time compute $\theta$ selected by each provider at each iteration, corresponding to the reasoning effort used. The dashed black line (right $y$ -axis) tracks the Market Inefficiency, defined as $(\text{PoA}-1)\times 100$ (see Eq. 9 ). The lower panels show the evolution of the market share at each time step of the better-response dynamics. The initial compute level $\bm{\theta}^{1}$ is taken as the lowest possible compute. We apply a small vertical jitter to the strategy lines to distinguish overlapping providers and take a fixed profit margin of $25\%$ .

Panel of Figure 18 — Figure 18: Potential of a test-time compute game using CoT. The figure shows, for different levels of user rationality $\beta$ , the evolution of the potential $\Phi$ (see Eq. 7 ) in the test-time compute games in Figure 17 where $N=3$ providers sequentially select a test-time compute level that increases their utility.

Figure 19: Inefficiency of a test-time compute game using CoT. The figure shows, as a function of users’ rationality

\beta

, the inefficiency (

\text{PoA}(\mathcal{G})-1

) of the test-time compute game in Figure 17 , where

N=3

providers sequentially select a test-time compute level that increases their utility.

Panel of Figure 20 — Figure 20: User values offered by providers in a test-time compute game on AIME. The figure shows the user values $V_{i}(\theta)$ offered by providers in a test-time compute game $\mathcal{G}$ , as a function of their test-time compute $\theta$ . Panel (a) and (b) correspond to games with $N=9$ providers serving non-reasoning models from the Llama and Qwen families, where providers use, respectively, majority voting and best-of-n across $\theta$ samples. Panel (c) corresponds to a game with $N=3$ providers serving reasoning models distilled from DeepSeek-R1 , where $\theta$ represents reasoning effort, defined by binning the model outputs into quantiles based on the number of reasoning tokens (see Appendix D ). In both games, providers serve queries $Q$ from the AIME dataset, we set $\beta=1000$ and consider that each (average) point of accuracy offers a value of $\$ 0.05$ to the users.

Panel of Figure 21 — Figure 21: Dynamics of a test-time compute game using majority-voting. The figure shows, for different levels of user rationality $\beta$ , the better-response dynamics of a test-time compute game $\mathcal{G}$ where $N=9$ providers sequentially select a test-time compute level that increases their utility. The upper panels show the compute levels $\theta$ selected by each provider and the resulting market inefficiency $(\text{PoA}(\mathcal{G})-1)$ , and the lower panels show the market share of each provider. Here, all providers use majority-voting across $\theta$ samples as their test-time compute method to serve queries $Q$ from the AIME dataset. We consider that providers operate with a margin of $25\%$ between per-token price and per-token cost, and that each (average) point of accuracy offers a value of $\$ 0.008$ to the users.

Panel of Figure 22 — Figure 22: Potential of a test-time compute game using majority-voting. The figure shows, for different levels of user rationality $\beta$ , the evolution of the potential $\Phi$ (see Eq. 7 ) in the test-time compute games in Figure 21 where $N=9$ providers sequentially select a test-time compute level that increases their utility.

Figure 23: Inefficiency of a test-time compute game using majority-voting. The figure shows, as a function of users’ rationality

\beta

, the inefficiency (

\text{PoA}(\mathcal{G})-1

) of the test-time compute game in Figure 21 , where

N=9

providers sequentially select a test-time compute level that increases their utility.

Panel of Figure 24 — Figure 24: Better-response dynamics of a test-time compute game using best-of-n. The upper panels show, for varying levels of user rationality $\beta$ , better-response dynamics when providers serving models from the Llama and Qwen families use best-of-n to serve queries from the AIME dataset. The solid colored lines (left $y$ -axis) represent the test-time compute $\theta$ selected by each provider at each iteration, corresponding to the number of samples used for best-of-n. The dashed black line (right $y$ -axis) tracks the Market Inefficiency, defined as $(\text{PoA}-1)\times 100$ (see Eq. 9 ). The lower panels show the evolution of the market share at each time step of the better-response dynamics. The initial compute level $\bm{\theta}^{1}$ is taken as the lowest possible compute. We apply a small vertical jitter to the strategy lines to distinguish overlapping providers and take a fixed profit margin of $25\%$ .

Panel of Figure 25 — Figure 25: Potential of a test-time compute game using best-of-n. The figure shows, for different levels of user rationality $\beta$ , the evolution of the potential $\Phi$ (see Eq. 7 ) in the test-time compute games in Figure 24 where $N=9$ providers sequentially select a test-time compute level that increases their utility.

Figure 26: Inefficiency of a test-time compute game using best-of-n. The figure shows, as a function of users’ rationality

\beta

, the inefficiency (

\text{PoA}(\mathcal{G})-1

) of the test-time compute game in Figure 24 , where

N=9

providers sequentially select a test-time compute level that increases their utility.

Panel of Figure 27 — Figure 27: Better-response dynamics of a test-time compute game using CoT. The upper panels show, for varying levels of user rationality $\beta$ , better-response dynamics when providers serving models from the Llama and Qwen families distilled from DeepSeek-R1 use chain-of-thought to serve queries from the AIME dataset. The solid colored lines (left $y$ -axis) represent the test-time compute $\theta$ selected by each provider at each iteration, corresponding to the reasoning effort used. The dashed black line (right $y$ -axis) tracks the Market Inefficiency, defined as $(\text{PoA}-1)\times 100$ (see Eq. 9 ). The lower panels show the evolution of the market share at each time step of the better-response dynamics. The initial compute level $\bm{\theta}^{1}$ is taken as the lowest possible compute. We apply a small vertical jitter to the strategy lines to distinguish overlapping providers and take a fixed profit margin of $25\%$ .

Panel of Figure 28 — Figure 28: Potential of a test-time compute game using CoT. The figure shows, for different levels of user rationality $\beta$ , the evolution of the potential $\Phi$ (see Eq. 7 ) in the test-time compute games in Figure 27 where $N=3$ providers sequentially select a test-time compute level that increases their utility.

Figure 29: Inefficiency of a test-time compute game using CoT. The figure shows, as a function of users’ rationality

\beta

, the inefficiency (

\text{PoA}(\mathcal{G})-1

) of the test-time compute game in Figure 27 , where

N=3

providers sequentially select a test-time compute level that increases their utility.

Panel of Figure 30 — Figure 30: User values offered by providers in a test-time compute game on GPQA. The figure shows the user values $V_{i}(\theta)$ offered by providers in a test-time compute game $\mathcal{G}$ , as a function of their test-time compute $\theta$ . Panel (a) and (b) correspond to games with $N=9$ providers serving non-reasoning models from the Llama and Qwen families, where providers use, respectively, majority voting and best-of-n across $\theta$ samples. Panel (c) corresponds to a game with $N=3$ providers serving reasoning models distilled from DeepSeek-R1 , where $\theta$ represents reasoning effort, defined by binning the model outputs into quantiles based on the number of reasoning tokens (see Appendix D ). In both games, providers serve queries $Q$ from the GPQA dataset, we set $\beta=1000$ and consider that each (average) point of accuracy offers a value of $\$ 0.02$ to the users.

Panel of Figure 31 — Figure 31: Dynamics of a test-time compute game using majority-voting. The figure shows, for different levels of user rationality $\beta$ , the better-response dynamics of a test-time compute game $\mathcal{G}$ where $N=9$ providers sequentially select a test-time compute level that increases their utility. The upper panels show the compute levels $\theta$ selected by each provider and the resulting market inefficiency $(\text{PoA}(\mathcal{G})-1)$ , and the lower panels show the market share of each provider. Here, all providers use majority-voting across $\theta$ samples as their test-time compute method to serve queries $Q$ from the GPQA dataset. We consider that providers operate with a margin of $25\%$ between per-token price and per-token cost, and that each (average) point of accuracy offers a value of $\$ 0.008$ to the users.

Panel of Figure 32 — Figure 32: Potential of a test-time compute game using majority-voting. The figure shows, for different levels of user rationality $\beta$ , the evolution of the potential $\Phi$ (see Eq. 7 ) in the test-time compute games in Figure 31 where $N=9$ providers sequentially select a test-time compute level that increases their utility.

Figure 33: Inefficiency of a test-time compute game using majority-voting. The figure shows, as a function of users’ rationality

\beta

, the inefficiency (

\text{PoA}(\mathcal{G})-1

) of the test-time compute game in Figure 31 , where

N=9

providers sequentially select a test-time compute level that increases their utility.

Panel of Figure 34 — Figure 34: Better-response dynamics of a test-time compute game using best-of-n. The upper panels show, for varying levels of user rationality $\beta$ , better-response dynamics when providers serving models from the Llama and Qwen families use best-of-n to serve queries from the GPQA dataset. The solid colored lines (left $y$ -axis) represent the test-time compute $\theta$ selected by each provider at each iteration, corresponding to the number of samples used for best-of-n. The dashed black line (right $y$ -axis) tracks the Market Inefficiency, defined as $(\text{PoA}-1)\times 100$ (see Eq. 9 ). The lower panels show the evolution of the market share at each time step of the better-response dynamics. The initial compute level $\bm{\theta}^{1}$ is taken as the lowest possible compute. We apply a small vertical jitter to the strategy lines to distinguish overlapping providers and take a fixed profit margin of $25\%$ .

Panel of Figure 35 — Figure 35: Potential of a test-time compute game using best-of-n. The figure shows, for different levels of user rationality $\beta$ , the evolution of the potential $\Phi$ (see Eq. 7 ) in the test-time compute games in Figure 34 where $N=9$ providers sequentially select a test-time compute level that increases their utility.

Figure 36: Inefficiency of a test-time compute game using best-of-n. The figure shows, as a function of users’ rationality

\beta

, the inefficiency (

\text{PoA}(\mathcal{G})-1

) of the test-time compute game in Figure 34 , where

N=9

providers sequentially select a test-time compute level that increases their utility.

Panel of Figure 37 — Figure 37: Better-response dynamics of a test-time compute game using CoT. The upper panels show, for varying levels of user rationality $\beta$ , better-response dynamics when providers serving models from the Llama and Qwen families distilled from DeepSeek-R1 use chain-of-thought to serve queries from the GPQA dataset. The solid colored lines (left $y$ -axis) represent the test-time compute $\theta$ selected by each provider at each iteration, corresponding to the reasoning effort used. The dashed black line (right $y$ -axis) tracks the Market Inefficiency, defined as $(\text{PoA}-1)\times 100$ (see Eq. 9 ). The lower panels show the evolution of the market share at each time step of the better-response dynamics. The initial compute level $\bm{\theta}^{1}$ is taken as the lowest possible compute. We apply a small vertical jitter to the strategy lines to distinguish overlapping providers and take a fixed profit margin of $25\%$ .

Panel of Figure 38 — Figure 38: Potential of a test-time compute game using CoT. The figure shows, for different levels of user rationality $\beta$ , the evolution of the potential $\Phi$ (see Eq. 7 ) in the test-time compute games in Figure 37 where $N=3$ providers sequentially select a test-time compute level that increases their utility.

Figure 39: Inefficiency of a test-time compute game using CoT. The figure shows, as a function of users’ rationality

\beta

, the inefficiency (

\text{PoA}(\mathcal{G})-1

) of the test-time compute game in Figure 37 , where

N=3

providers sequentially select a test-time compute level that increases their utility.

Panel of Figure 40 — Figure 40: User values offered by providers in a test-time compute game on TruthfulQA. The figure shows the user values $V_{i}(\theta)$ offered by providers in a test-time compute game $\mathcal{G}$ , as a function of their test-time compute $\theta$ . The panel corresponds to games with $N=9$ providers serving non-reasoning models from the Llama and Qwen families, where providers use best-of-n across $\theta$ samples. Providers serve queries $Q$ from the TruthfulQA dataset, we set $\beta=1000$ and consider that each (average) point of quality (as reported in Figure 9 ) offers a value of $\$ 0.008$ to the users.

Panel of Figure 41 — Figure 41: Better-response dynamics of a test-time compute game using best-of-n. The upper panels show, for varying levels of user rationality $\beta$ , better-response dynamics when providers serving models from the Llama and Qwen families use best-of-n to serve queries from the TruthfulQA dataset. The solid colored lines (left $y$ -axis) represent the test-time compute $\theta$ selected by each provider at each iteration, corresponding to the number of samples used for best-of-n. The dashed black line (right $y$ -axis) tracks the Market Inefficiency, defined as $(\text{PoA}-1)\times 100$ (see Eq. 9 ). The lower panels show the evolution of the market share at each time step of the better-response dynamics. The initial compute level $\bm{\theta}^{1}$ is taken as the lowest possible compute. We apply a small vertical jitter to the strategy lines to distinguish overlapping providers and take a fixed profit margin of $25\%$ .

Panel of Figure 42 — Figure 42: Potential of a test-time compute game using best-of-n. The figure shows, for different levels of user rationality $\beta$ , the evolution of the potential $\Phi$ (see Eq. 7 ) in the test-time compute games in Figure 41 where $N=9$ providers sequentially select a test-time compute level that increases their utility.

Figure 43: Inefficiency of a test-time compute game using best-of-n. The figure shows, as a function of users’ rationality

\beta

, the inefficiency (

\text{PoA}(\mathcal{G})-1

) of the test-time compute game in Figure 41 , where

N=9

providers sequentially select a test-time compute level that increases their utility.

Table 3: Comparison of the equilibrium between

\mathcal{G}

and the auction

\widetilde{\mathcal{G}}

on GSM8K using majority voting. The table shows, for

\widetilde{\mathcal{G}}

, the value received by the user (once the auction is conducted), the price they pay (according to Eq. 10 ), the provider’s utility, the social welfare, and the provider (LLM) that wins the auction. For

\mathcal{G}

, the table shows the providers’ average utility, the users’ average value and price, all weighted by their equilibrium market shares, together with the social welfare. We vary the provider margin—used to derive the per-token cost from the per-token price—and the proportionality parameter

\alpha

, which linearly converts a percentage point of accuracy into a monetary value (see Appendix D ). All quantities (except the compute) have units

(\

\times 10^{-3})$ .

Table 4: Comparison of the equilibrium between

\mathcal{G}

and the auction

\widetilde{\mathcal{G}}

on GSM8K using best-of-n. The table shows, for

\widetilde{\mathcal{G}}

\mathcal{G}

\alpha

, which linearly converts a percentage point of accuracy into a monetary value (see Appendix D ). All quantities (except the compute) have units

(\

\times 10^{-3})$ .

Table 5: Comparison of the equilibrium between

\mathcal{G}

and the auction

\widetilde{\mathcal{G}}

on GSM8K using chain-of-thought. The table shows, for

\widetilde{\mathcal{G}}

\mathcal{G}

\alpha

, which linearly converts a percentage point of accuracy into a monetary value (see Appendix D ). All quantities (except the compute) have units

(\

\times 10^{-3})$ .

Table 6: Comparison of the equilibrium between

\mathcal{G}

and the auction

\widetilde{\mathcal{G}}

on AIME using majority voting. The table shows, for

\widetilde{\mathcal{G}}

\mathcal{G}

\alpha

, which linearly converts a percentage point of accuracy into a monetary value (see Appendix D ). All quantities (except the compute) have units

(\

\times 10^{-3})$ .

Table 7: Comparison of the equilibrium between

\mathcal{G}

and the auction

\widetilde{\mathcal{G}}

on AIME using best-of-n. The table shows, for

\widetilde{\mathcal{G}}

\mathcal{G}

\alpha

, which linearly converts a percentage point of accuracy into a monetary value (see Appendix D ). All quantities (except the compute) have units

(\

\times 10^{-3})$ .

Table 8: Comparison of the equilibrium between

\mathcal{G}

and the auction

\widetilde{\mathcal{G}}

on AIME using chain-of-thought. The table shows, for

\widetilde{\mathcal{G}}

\mathcal{G}

\alpha

, which linearly converts a percentage point of accuracy into a monetary value (see Appendix D ). All quantities (except the compute) have units

(\

\times 10^{-3})$ .

Table 9: Comparison of the equilibrium between

\mathcal{G}

and the auction

\widetilde{\mathcal{G}}

on GPQA using majority voting. The table shows, for

\widetilde{\mathcal{G}}

\mathcal{G}

\alpha

, which linearly converts a percentage point of accuracy into a monetary value (see Appendix D ). All quantities (except the compute) have units

(\

\times 10^{-3})$ .

Table 10: Comparison of the equilibrium between

\mathcal{G}

and the auction

\widetilde{\mathcal{G}}

on GPQA using best-of-n. The table shows, for

\widetilde{\mathcal{G}}

\mathcal{G}

\alpha

, which linearly converts a percentage point of accuracy into a monetary value (see Appendix D ). All quantities (except the compute) have units

(\

\times 10^{-3})$ .

Table 11: Comparison of the equilibrium between

\mathcal{G}

and the auction

\widetilde{\mathcal{G}}

on GPQA using chain-of-thought. The table shows, for

\widetilde{\mathcal{G}}

\mathcal{G}

\alpha

, which linearly converts a percentage point of accuracy into a monetary value (see Appendix D ). All quantities (except the compute) have units

(\

\times 10^{-3})$ .

Table 12: Comparison of the equilibrium between

\mathcal{G}

and the auction

\widetilde{\mathcal{G}}

on TruthfulQA using best-of-n. The table shows, for

\widetilde{\mathcal{G}}

\mathcal{G}

\alpha

, which linearly converts a percentage point of accuracy into a monetary value (see Appendix D ). All quantities (except the compute) have units

(\

\times 10^{-3})$ .

Setting	Provider	Compute	Social welfare
$\mathcal{G}$ , all users served at equilibrium compute	Qwen2.5-7B	$\theta_{i}^{\dagger}=16$	$\$ 0.00643$
Auction $\widetilde{\mathcal{G}}$	Qwen2.5-7B	$\theta_{i}^{*}=2$	$\$ 0.00736$

Appendix

Table 13: Effect of compute on social welfare in the best-of-

n

game on GSM8K at

\beta=10^{3}

, with the allocation held fixed.

LLM Serving

Large language model serving studies how to deliver model responses with low latency, high throughput, and efficient use of compute and memory.

See all 207 papers

Learning the Cost of Reliable Inference
Sep 23, 2026Dimitrios Rontogiannis, Ander Artola Velasco, Manuel Gomez RodriguezCost-Aware Inference LLM Routing
Max Planck Institute for Software Systems Kaiserslautern, Germany
Keep, Customize, or Exit: Default Design and Token Pricing in LLM Reasoning Services
Aug 13, 2026Ahmet Bugra Gundogan, Yigit Turkmen, Melih BastopcuLLM Serving Inference-Time Compute Allocation
Department of Electrical and Electronics Engineering
Adaptive Test-Time Compute Allocation for Reasoning LLMs via Constrained Policy Optimization
Apr 16, 2026Zhiyuan Zhai, Bingcong Li, Bingnan Xiao +2Test-Time Scaling Constrained Optimization
Fudan University · ETH Zurich · Guangming Lab

Sep 23, 2026J/K move · Enter open · S save

Learning the Cost of Reliable Inference

Dimitrios Rontogiannis, Ander Artola Velasco, Manuel Gomez Rodriguez

Max Planck Institute for Software Systems Kaiserslautern, Germany

Cost-Aware Inference LLM Routing

Open paper AskPDF arXiv

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 for each task 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 benchmarks. The results show that the pricing margin of the most cost-competitive provider on our platform varies significantly---from

10\%

71\%

---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.

Abstract

LLM Serving

Explore similar work

Learning the Cost of Reliable Inference

Keep, Customize, or Exit: Default Design and Token Pricing in LLM Reasoning Services

Adaptive Test-Time Compute Allocation for Reasoning LLMs via Constrained Policy Optimization