Research map / Large language models / Reasoning and chain of thought
Test-Time Compute Games
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Models LLM-as-a-service test-time compute competition as a potential game, shows equilibria are socially inefficient under pay-for-compute pricing (PoA up to 1.19), and proposes a reverse second-price auction that achieves PoA=1.
Problem
Providers of LLM-as-a-service are financially incentivized to over-allocate test-time compute, even when it adds little output quality, so the pay-for-compute market is socially inefficient.
Approach
Model providers' test-time compute choices as a normal-form potential game under perfect or bounded user rationality, bound the price of anarchy, and introduce a reverse second-price auction where providers bid (quality, price) and the user's payment equals the winner's quality minus the runner-up's value, making the outcome socially optimal.
Key results
- Non-reasoning model game on GSM8K reaches a pure Nash equilibrium after 44 better-response iterations with price of anarchy 1.19 (about 16% welfare loss).
- Reasoning-model game (DeepSeek-R1 distills) has PoA about 1.006 at equilibrium, converging after 12 iterations.
- Under the proposed auction, user value rises 29% and social welfare 25% for non-reasoning models relative to the pay-for-compute game, while PoA is 1 by theory.
Surprising findings
- Under the auction, providers can lose utility (-28%) for non-reasoning models, while utility can rise +200% for reasoning models.
Limitations
- Assumes providers can accurately estimate quality on representative queries; auction depends on verifiable quality metrics.
- Second-price payments depend on competitors' bids and may be vulnerable to manipulation or collusion.
- Market model ignores non-price factors such as popularity or reliability and assumes homogeneous user valuations.
Experimental setup
Datasets: GSM8K GPQA AIME TruthfulQA
Benchmarks: GSM8K GPQA AIME TruthfulQA
Metrics: price of anarchy social welfare user value provider utility accuracy BLEURT-based score
Baselines: pay-for-compute market (test-time compute game) second-price auction (own mechanism comparison)
Builds on: potential games scoring auctions best-of-n sampling chain-of-thought
Closest papers by meaning
- The Shadow Price of Reasoning: Economic Perspective on Optimal Budget Allocation for LLMs (ICML 2026 · similarity 0.88)
- A Theory of Training Profit-Optimal LLMs (NeurIPS 2026 · similarity 0.87)
- Every Rollout Counts: Optimal Resource Allocation for Efficient Test-Time Scaling (NeurIPS 2025 · similarity 0.87)
- Fairshare Data Pricing via Data Valuation for Large Language Models (NeurIPS 2025 · similarity 0.87)
- D-LLM: A Token Adaptive Computing Resource Allocation Strategy for Large Language Models (NeurIPS 2024 · similarity 0.86)
- Matching Markets Meet LLMs: Algorithmic Reasoning with Ranked Preferences (NeurIPS 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.