🤖 AI

Test-Time Compute Games

This paper identifies the social inefficiency in LLM-as-a-service markets where providers are incentivized to overuse costly test-time compute, and proposes a reverse second-price auction mechanism to align pricing with marginal value, validated through experiments on various model families across math and science benchmarks.

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

Published 2026-05-11

📖 6 min read🧠 Deep dive

CC BY 4.0

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

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: The "Over-Engineering" Problem

Imagine you need a taxi to get to the airport. You have two taxi companies: Company A and Company B.

Company A usually takes 10 minutes to get you there.
Company B usually takes 12 minutes.

However, both companies have a secret button they can press called "Super-Drive."

If Company A presses it, they take 11 minutes but charge you double.
If Company B presses it, they take 11 minutes and charge you triple.

In a normal world, you would just pick Company A for the standard 10-minute ride because it's cheaper and faster. But here is the twist: The taxi companies get paid based on how much gas they burn, not just how fast they get you there.

Because of this, Company A thinks: "If I press 'Super-Drive' and take 11 minutes, I can charge you double. Even though you only saved 1 minute compared to my old speed, I make more money. So, I will always press the button."

The Result: You end up paying double for a ride that is barely faster, and the company burns extra gas for no real benefit. This is what the paper calls "Test-Time Compute" (TTC). In the world of AI, "gas" is computer power, and "Super-Drive" is making the AI think longer or try many different answers before giving you one.

The Problem: Why the Market is Broken

The authors argue that the current way we buy AI services is socially inefficient.

The Provider's Incentive: AI companies want to make money. They know that if they make their AI "think harder" (use more compute), they can charge you more. Even if the extra thinking only makes the answer 1% better, they might still do it because the extra cost to them is low, but the extra price they can charge is high.
The User's Loss: You end up paying for "thinking" that doesn't actually help you much. It's like paying for a fancy, slow-cooked meal when a simple sandwich would have been just as filling and much cheaper.

The paper shows that in a free market, AI companies will naturally choose to "over-think" problems to maximize their own profits, even if it wastes money and resources for everyone.

The Solution: A Reverse Auction

To fix this, the authors propose a new way to buy AI services, similar to a reverse auction (like when a government wants to buy 1,000 desks and asks suppliers to bid the lowest price).

Here is how their "Smart Auction" works:

The Setup: You (the user) have a task. You tell a neutral platform, "I need an AI to solve this math problem."
The Bids: Several AI companies submit a bid. They say:
- "I can solve this with 90% accuracy."
- "I will charge $5."
- (They also secretly decide how much "thinking" to do to get that 90% accuracy).
The Winner: The platform picks the company that offers the best deal (highest accuracy for the lowest price).
The Payment (The Magic Part): This is the most important rule. The winner does not get paid what they asked for.
- Instead, they get paid based on the second-best offer.
- Example: If Company A bids 90% accuracy for $5, and Company B bids 85% accuracy for $4, Company A wins. But Company A only gets paid $4 (plus a tiny bit for the quality difference), not $5.

Why this changes everything:
Because the winner gets paid based on the competitor's price, not their own, they have no incentive to overcharge or over-engineer.

If Company A tries to "think harder" to get 95% accuracy, they might win, but they still only get paid based on Company B's lower standard.
If Company A tries to charge $10, they will lose the bid to Company B.
The Best Strategy: The only way for a company to win and make a profit is to find the most efficient way to solve the problem (the right amount of "thinking") that gives the best value. They are forced to stop "over-thinking" because it costs them money without helping them win the bid.

The Results: What the Experiments Showed

The authors tested this idea using real AI models (like Llama and Qwen) on math and science problems.

The Current Market is Wasteful: In the normal "pay-per-token" market, they found that the system was up to 19% inefficient. This means we were wasting nearly 20% of the money and computing power because companies were choosing to "think" too much just to make a few extra dollars.
The Auction Fixes It: When they simulated their auction, the inefficiency dropped to zero. The AI companies automatically chose the perfect amount of "thinking" to solve the problem efficiently.
Who Wins?
- Users: Get much better value. They pay less and get answers that are just as good (or better).
- Providers: It's a mixed bag. Some companies might make less money because they can't overcharge anymore, but others might make more because they can finally compete fairly on efficiency rather than just inflating costs.

Summary Analogy

Current System: Like a restaurant where the chef gets paid for every ingredient they chop. They will chop onions into dust just to charge you more, even though you only needed them sliced.
Proposed System: Like a restaurant where the chef gets paid a fixed price based on what the neighbor restaurant charges for a similar dish. The chef is now forced to chop onions efficiently. If they chop them too finely, they waste time and money but don't get paid extra. If they chop them too roughly, they lose the customer. They find the perfect middle ground.

The paper concludes that by changing the rules of the game (the payment mechanism), we can stop AI companies from wasting resources and ensure that the "thinking" they do actually helps the user.

Technical Summary: Test-Time Compute Games

Problem Statement

The rapid adoption of Large Language Models (LLMs) as a service has created a market where users pay cloud providers for the computational resources consumed during inference. A critical driver of this cost is Test-Time Compute (TTC)—additional computations performed at inference time (e.g., chain-of-thought, tree-of-thought, best-of-n sampling) to enhance model performance. While TTC improves output quality, providers currently charge users for all generated tokens, including intermediate reasoning steps.

The paper identifies a fundamental market inefficiency: providers have a financial incentive to increase the amount of TTC allocated to a query to maximize their own profit, even when the marginal gain in output quality is negligible or when the additional compute does not align with the socially optimal balance between cost and quality. In a competitive market where users select providers based on value (quality minus price), providers may strategically over-provision compute to differentiate themselves or capture market share, leading to a suboptimal allocation of resources from a societal welfare perspective.

Methodology

The authors formalize the LLM-as-a-service market as a normal-form game involving $N$ providers competing for user demand.

Game-Theoretic Model

Players: $N$ providers, each serving a pre-trained LLM.
Strategies: Each provider $i$ selects a level of test-time compute $\theta_i$ from a finite set $\Theta$ . This level determines the average output quality $q_i(\theta_i)$ and the generation cost $c_i(\theta_i)$ .
Pricing: Providers set prices $p_i(\theta_i)$ proportional to the generation cost (plus a profit margin).
User Utility: Users derive value $V_i(\theta_i) = q_i(\theta_i) - p_i(\theta_i)$ .
Market Allocation: Users distribute demand based on the offered value. The paper considers two market share functions:
1. Perfect Rationality: Users always select the provider with the highest value.
2. Bounded Rationality: Users select providers probabilistically based on value (Logit/Softmax choice), controlled by a rationality parameter $\beta$ .
Provider Utility: Defined as market share multiplied by profit margin $(p_i - c_i)$ .

Theoretical Analysis

The authors analyze the Nash Equilibrium of this game. They prove that the game is a generalized ordinal potential game, guaranteeing the existence of a pure Nash equilibrium and convergence via better-response dynamics. They characterize the equilibrium compute levels and demonstrate that, generally, the equilibrium is not socially optimal. The Price of Anarchy (PoA) is used to quantify the ratio between the maximum possible social welfare and the welfare achieved at equilibrium.

Proposed Mechanism

To address this inefficiency, the paper proposes a reverse second-price auction mechanism:

Process: Users submit a task; providers bid simultaneously with a pair $(q_i, p_i)$ representing estimated quality and price.
Allocation: The provider offering the highest value ( $q_i - p_i$ ) wins.
Payment Rule: The winning provider is paid an amount determined by the second-highest bidder's offer, specifically $P = q_{winner} - V_{second\_best}$ .
Incentive Alignment: The authors prove that under this mechanism, selecting the compute level that maximizes individual contribution to social welfare ( $\theta^*_i = \arg\max_\theta (q_i(\theta) - c_i(\theta))$ ) and bidding the generation cost is a dominant strategy. This ensures the auction outcome achieves the maximum possible social welfare (PoA = 1).

Key Contributions

Game-Theoretic Modeling: The paper introduces "Test-Time Compute Games," modeling the strategic interaction between LLM providers regarding compute allocation in a service market.
Inefficiency Characterization: It formally demonstrates that in a standard pay-for-compute market, providers are incentivized to select compute levels that are not socially optimal, leading to a Price of Anarchy greater than 1.
Auction Mechanism Design: It proposes a reverse second-price auction where providers bid on quality and price. Theoretical analysis shows this mechanism guarantees social optimality by aligning provider incentives with the maximization of social welfare.
Empirical Validation: The authors conduct extensive experiments using models from the Llama, Qwen, and DeepSeek-R1 families across datasets (GSM8K, GPQA, AIME, TruthfulQA) to validate theoretical findings.

Experimental Results

The experiments simulate the dynamics of test-time compute games and compare them against the proposed auction mechanism.

Market Inefficiency: In the standard market game, the Price of Anarchy was found to be up to 1.19 (a 19% loss in social welfare) for non-reasoning models and approximately 1.006 for reasoning models. This confirms that competition does not naturally lead to social optimality.
Convergence: The better-response dynamics of providers converging to a Nash equilibrium were observed to stabilize within a finite number of iterations (e.g., 44 iterations for non-reasoning models).
Auction Performance: When the proposed auction mechanism was applied:
- Social Welfare: Increased by 25% for non-reasoning models and 4% for reasoning models compared to the game equilibrium.
- User Value: Increased by 29% for non-reasoning models and 2.8% for reasoning models.
- Provider Utility: Varied significantly; in some cases, provider utility decreased (e.g., -28% for non-reasoning models), while in others, it increased substantially (e.g., +200% for reasoning models), depending on market competitiveness.

Significance and Claims

The paper claims to be the first to demonstrate that in the LLM-as-a-service market, providers are incentivized to strategically decide the amount of test-time compute used, and that this strategic behavior leads to social inefficiency.

The significance of the work lies in:

Economic Insight: It shifts the focus from purely technical performance of TTC methods to their economic implications, highlighting that current pricing models may encourage wasteful computation.
Mechanism Design: It offers a concrete, theoretically grounded alternative (the reverse second-price auction) that can align market incentives with social welfare, ensuring that compute resources are allocated efficiently.
Practical Relevance: The findings suggest that without mechanism design interventions, the growing reliance on expensive test-time compute may lead to suboptimal outcomes for both users and society, even in competitive markets.

The authors remain modest regarding the immediate deployment of their auction, noting that it relies on the ability of platforms to verify model quality and that adoption incentives depend on how utility changes for providers. They frame their work as a step toward exploring alternative market structures for generative AI that prioritize social welfare.