# Test-Time Compute Games

arXiv: https://arxiv.org/abs/2601.21839 · HTML: https://mlsanity.com/paper/2601.21839/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning.
- Builds on 20 of its 76 references that are in the map.
- First posted on arXiv 29 Jan 2026.

## Placed in

- LLM reasoning / [Test-time compute and efficient thinking](https://mlsanity.com/lr/test-time-compute-and-efficient-thinking/)

## Builds on (most cited first, 20 of 20)

- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [TruthfulQA: Measuring How Models Mimic Human Falsehoods](https://mlsanity.com/paper/2109.07958/) (2021)
- [BLEURT: Learning Robust Metrics for Text Generation](https://mlsanity.com/paper/2004.04696/) (2020)
- [UltraFeedback: Boosting Language Models with Scaled AI Feedback](https://mlsanity.com/paper/2310.01377/) (2023)
- [When More is Less: Understanding Chain-of-Thought Length in LLMs](https://mlsanity.com/paper/2502.07266/) (2025)
- [Can 1B LLM Surpass 405B LLM? Rethinking Compute-Optimal Test-Time Scaling](https://mlsanity.com/paper/2502.06703/) (2025)
- [Are You Getting What You Pay For? Auditing Model Substitution in LLM APIs](https://mlsanity.com/paper/2504.04715/) (2025)
- [ParaThinker: Native Parallel Thinking as a New Paradigm to Scale LLM Test-time Compute](https://mlsanity.com/paper/2509.04475/) (2025)
- [Cost-of-Pass: An Economic Framework for Evaluating Language Models](https://mlsanity.com/paper/2504.13359/) (2025)
- [CoIn: Counting the Invisible Reasoning Tokens in Commercial Opaque LLM APIs](https://mlsanity.com/paper/2505.13778/) (2025)
- [Is Your LLM Overcharging You? Tokenization, Transparency, and Incentives](https://mlsanity.com/paper/2505.21627/) (2025)
- [Optimal Stopping vs Best-of-N for Inference Time Optimization](https://mlsanity.com/paper/2510.01394/) (2025)
- [BEACON: Bayesian Optimal Stopping for Efficient LLM Sampling](https://mlsanity.com/paper/2510.15945/) (2025)
- [Pay for The Second-Best Service: A Game-Theoretic Approach Against Dishonest LLM Providers](https://mlsanity.com/paper/2511.00847/) (2025)
- [Economic Evaluation of LLMs](https://mlsanity.com/paper/2507.03834/) (2025)
- [Efficiency in Truthful Auctions via a Social Network](https://mlsanity.com/paper/1904.12422/) (2019)
- [Best-of-∞ -- Asymptotic Performance of Test-Time LLM Ensembling](https://mlsanity.com/paper/2509.21091/) (2025)
- [Welfare as a Guiding Principle for Machine Learning -- From Compass, to Lens, to Roadmap](https://mlsanity.com/paper/2502.11981/) (2025)
- [Robust Analysis of Auction Equilibria](https://mlsanity.com/paper/2310.03702/) (2023)
- [How to sell a service with uncertain outcomes](https://mlsanity.com/paper/2502.13334/) (2025)

## Built on by (most cited first, 4 of 4)

- [Post-Training at the Edge of Detectability: A Game-Theoretic Approach to Fine-Tuning](https://mlsanity.com/paper/2607.26358/) (2026)
- [Learning the Cost of Reliable Inference](https://mlsanity.com/paper/2609.28322/) (2026)
- [Inference Auctions](https://mlsanity.com/paper/2609.40070/) (2026)
- [Price of Anarchy of First-Price Auctions in Agentic Markets](https://mlsanity.com/paper/2610.20587/) (2026)

## Abstract (arXiv)

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 textttLlama and textttQwen families, as well as reasoning models distilled from textttDeepSeek-R1, on math and science benchmark datasets.