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 Llama and Qwen families, as well as reasoning models distilled from DeepSeek-R1, on math and science benchmark datasets.
Figure 1: User values offered by providers in a test-time compute game. The figure shows the user values Vi(θ) offered by providers in a test-time compute game G , as a function of their test-time compute θ . 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 θ 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 θ 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.
Figure 2: Dynamics of a test-time compute game. The figure illustrates the better-response dynamics of a test-time compute game G when providers sequentially select a test-time compute level that increases their utility. The upper panels show the compute levels θt selected by each provider and the resulting market inefficiency (dashed black curve), defined as maxθW(θ)/W(θ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 β=1000 .
Non-reasoning
Reasoning
Game G
Auction G
Game G
Auction G
Compute level ( θ )
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 G and the auction G . The table compares the equilibrium outcomes of the test-time compute games G ( β=1000 ) in Figure 1 with the outcomes of the auction G for the same set of providers using best-of-n with non-reasoning models, and chain-of-thought with reasoning models. For 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 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
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.
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).
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.
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).
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.
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).
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.
Figure 10: User values offered by providers in a test-time compute game on GSM8K. The figure shows the user values Vi(θ) offered by providers in a test-time compute game G , as a function of their test-time compute θ . 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 θ samples. Panel (c) corresponds to a game with N=3 providers serving reasoning models distilled from DeepSeek-R1 , where θ 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 β=1000 and consider that each (average) point of accuracy offers a value of \0.008$ to the users.
Figure 11: Dynamics of a test-time compute game using majority-voting. The figure shows, for different levels of user rationality β , the better-response dynamics of a test-time compute game G where N=9 providers sequentially select a test-time compute level that increases their utility. The upper panels show the compute levels θ selected by each provider and the resulting market inefficiency (PoA(G)−1) , and the lower panels show the market share of each provider. Here, all providers use majority-voting across θ 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.
Figure 12: Potential of a test-time compute game using majority-voting. The figure shows, for different levels of user rationality β , the evolution of the potential Φ (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 β , the inefficiency ( PoA(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.
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 β , 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 θ 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 (PoA−1)×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 θ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% .
Figure 15: Potential of a test-time compute game using best-of-n. The figure shows, for different levels of user rationality β , the evolution of the potential Φ (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 β , the inefficiency ( PoA(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.
Figure 17: Better-response dynamics of a test-time compute game using CoT. The upper panels show, for varying levels of user rationality β , 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 θ 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 (PoA−1)×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 θ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% .
Figure 18: Potential of a test-time compute game using CoT. The figure shows, for different levels of user rationality β , the evolution of the potential Φ (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 β , the inefficiency ( PoA(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.
Figure 20: User values offered by providers in a test-time compute game on AIME. The figure shows the user values Vi(θ) offered by providers in a test-time compute game G , as a function of their test-time compute θ . 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 θ samples. Panel (c) corresponds to a game with N=3 providers serving reasoning models distilled from DeepSeek-R1 , where θ 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 β=1000 and consider that each (average) point of accuracy offers a value of \0.05$ to the users.
Figure 21: Dynamics of a test-time compute game using majority-voting. The figure shows, for different levels of user rationality β , the better-response dynamics of a test-time compute game G where N=9 providers sequentially select a test-time compute level that increases their utility. The upper panels show the compute levels θ selected by each provider and the resulting market inefficiency (PoA(G)−1) , and the lower panels show the market share of each provider. Here, all providers use majority-voting across θ 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.
Figure 22: Potential of a test-time compute game using majority-voting. The figure shows, for different levels of user rationality β , the evolution of the potential Φ (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 β , the inefficiency ( PoA(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.
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 β , 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 θ 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 (PoA−1)×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 θ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% .
Figure 25: Potential of a test-time compute game using best-of-n. The figure shows, for different levels of user rationality β , the evolution of the potential Φ (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 β , the inefficiency ( PoA(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.
Figure 27: Better-response dynamics of a test-time compute game using CoT. The upper panels show, for varying levels of user rationality β , 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 θ 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 (PoA−1)×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 θ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% .
Figure 28: Potential of a test-time compute game using CoT. The figure shows, for different levels of user rationality β , the evolution of the potential Φ (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 β , the inefficiency ( PoA(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.
Figure 30: User values offered by providers in a test-time compute game on GPQA. The figure shows the user values Vi(θ) offered by providers in a test-time compute game G , as a function of their test-time compute θ . 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 θ samples. Panel (c) corresponds to a game with N=3 providers serving reasoning models distilled from DeepSeek-R1 , where θ 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 β=1000 and consider that each (average) point of accuracy offers a value of \0.02$ to the users.
Figure 31: Dynamics of a test-time compute game using majority-voting. The figure shows, for different levels of user rationality β , the better-response dynamics of a test-time compute game G where N=9 providers sequentially select a test-time compute level that increases their utility. The upper panels show the compute levels θ selected by each provider and the resulting market inefficiency (PoA(G)−1) , and the lower panels show the market share of each provider. Here, all providers use majority-voting across θ 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.
Figure 32: Potential of a test-time compute game using majority-voting. The figure shows, for different levels of user rationality β , the evolution of the potential Φ (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 β , the inefficiency ( PoA(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.
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 β , 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 θ 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 (PoA−1)×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 θ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% .
Figure 35: Potential of a test-time compute game using best-of-n. The figure shows, for different levels of user rationality β , the evolution of the potential Φ (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 β , the inefficiency ( PoA(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.
Figure 37: Better-response dynamics of a test-time compute game using CoT. The upper panels show, for varying levels of user rationality β , 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 θ 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 (PoA−1)×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 θ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% .
Figure 38: Potential of a test-time compute game using CoT. The figure shows, for different levels of user rationality β , the evolution of the potential Φ (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 β , the inefficiency ( PoA(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.
Figure 40: User values offered by providers in a test-time compute game on TruthfulQA. The figure shows the user values Vi(θ) offered by providers in a test-time compute game G , as a function of their test-time compute θ . 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 θ samples. Providers serve queries Q from the TruthfulQA dataset, we set β=1000 and consider that each (average) point of quality (as reported in Figure 9 ) offers a value of \0.008$ to the users.
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 β , 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 θ 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 (PoA−1)×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 θ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% .
Figure 42: Potential of a test-time compute game using best-of-n. The figure shows, for different levels of user rationality β , the evolution of the potential Φ (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 β , the inefficiency ( PoA(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 G and the auction G on GSM8K using majority voting. The table shows, for 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 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 α , 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 G and the auction G on GSM8K using best-of-n. The table shows, for 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 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 α , 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 G and the auction G on GSM8K using chain-of-thought. The table shows, for 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 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 α , 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 G and the auction G on AIME using majority voting. The table shows, for 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 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 α , 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 G and the auction G on AIME using best-of-n. The table shows, for 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 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 α , 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 G and the auction G on AIME using chain-of-thought. The table shows, for 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 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 α , 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 G and the auction G on GPQA using majority voting. The table shows, for 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 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 α , 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 G and the auction G on GPQA using best-of-n. The table shows, for 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 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 α , 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 G and the auction G on GPQA using chain-of-thought. The table shows, for 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 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 α , 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 G and the auction G on TruthfulQA using best-of-n. The table shows, for 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 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 α , 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
G , all users served at equilibrium compute
Qwen2.5-7B
θi†=16
\0.00643$
Auction G
Qwen2.5-7B
θi∗=2
\0.00736$
Appendix
Table 13: Effect of compute on social welfare in the best-of- n game on GSM8K at β=103 , with the allocation held fixed.
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% to 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.
Dimitrios Rontogiannis, Ander Artola Velasco, Manuel Gomez Rodriguez
Max Planck Institute for Software Systems Kaiserslautern, Germany
We study a large language model (LLM) service in which a provider chooses a per-token price and a default reasoning-token allocation, while a user may accept the default, customize the allocation, or exit. Larger allocations can improve accuracy but increase token cost and latency. We model this interaction as a Stackelberg game and derive the user's unique optimal customized allocation in closed form. For any price, the acceptable defaults form either an empty set or a compact interval. We characterize the provider's optimal default through a three-regime rule, reduce equilibrium computation to a one-dimensional price optimization, and prove the existence of the equilibrium. We further show that defaults affect the implemented reasoning allocation only when users value the convenience of avoiding customization; otherwise, every service-providing outcome implements the user's optimal customized allocation. Experiments with two compact open-weight reasoning models on five mathematics and science benchmarks support the accuracy-token model and show how model and task characteristics determine equilibrium prices, defaults, and reasoning allocations.
Ahmet Bugra Gundogan, Yigit Turkmen, Melih Bastopcu
Department of Electrical and Electronics Engineering
Test-time compute scaling, the practice of spending extra computation during inference via repeated sampling, search, or extended reasoning, has become a powerful lever for improving large language model performance. Yet deploying these techniques under finite inference budgets requires a decision that current systems largely ignore: which inputs deserve more compute, and which can be answered cheaply? We formalize this as a constrained optimization problem (maximize expected accuracy subject to an average compute budget) and solve it with a two-stage Solve-then-Learn pipeline. In the solve stage, Lagrangian relaxation decomposes the global constraint into per-instance sub-problems, each admitting a closed-form oracle action that optimally prices accuracy against cost. We prove that the induced cost is monotone in the dual variable, enabling exact budget targeting via binary search. In the learn stage, a lightweight classifier is trained to predict oracle actions from cheap input features, amortizing the allocation rule for real-time deployment. We establish that the task-level regret of the learned policy is bounded by its imitation error times the worst-case per-instance gap, yielding a clean reduction from constrained inference to supervised classification. Experiments on MATH and GSM8K with three LLMs (DeepSeek-V3, GPT-4o-mini, Qwen2.5-7B) show that our method consistently outperforms uniform and heuristic allocation baselines, achieving up to 12.8% relative accuracy improvement on MATH under matched budget constraints, while closely tracking the Lagrangian oracle upper bound with over 91% imitation accuracy.