Test-Time Compute Games¶
会议: NeurIPS 2026
arXiv: 2601.21839
OpenReview: https://openreview.net/forum?id=bS1tznbzuA
代码: https://github.com/Human-Centric-Machine-Learning/strategic-ttc
领域: LLM 推理
关键词: 测试时计算, 大模型服务市场, 博弈论, 纳什均衡, 次高价逆向拍卖
一句话总结¶
本文将大模型即服务（LLM-as-a-service）市场中服务商对测试时计算（TTC）的策略性配置形式化为正规型博弈，证明了基于 token 计费的现有市场必定收敛到牺牲社会福利的纯策略纳什均衡（无序代价 PoA 高达 1.19），并设计了一种基于质量与报价的多属性次高价逆向拍卖机制，从理论与经验上严格恢复社会福利最优。
研究背景与动机¶
以思维链（Chain-of-Thought）、思维树（Tree-of-Thought）以及 Best-of-N 采样为代表的测试时计算（Test-Time Compute, TTC）技术，已成为大幅提升大语言模型复杂推理与数学规划能力的核心范式。伴随这一技术演进，云计算市场中“大模型即服务”（LLM-as-a-service）的商业模式迅速普及。在这种模式下，模型提供商（如 OpenAI、Anthropic、Google 及各类 API 聚合平台）通常根据模型推理过程中消耗的 token 总量向终端用户计费，其中不仅包含最终呈现给用户的答案，还涵盖了用户不可见的中间长推理过程或多路采样计算。
然而，服务商在接收到用户请求时，普遍拥有根据输入动态调整推理预算与测试时计算深度的自由度（例如自适应思考路由与采样轮数控制）。这种技术自由度在多服务商竞争的市场环境下引入了全新的策略维度。由于服务商的单次请求收益与计算量正向挂钩，服务商存在强烈的财务动机去人为增加测试时计算量，即便由此带来的边际质量提升微乎其微。这导致了显着的市场失灵与社会福利损耗：用户为冗余的思考 token 支付了过高溢价，而真正兼顾高性价比的模型与计算配置却在恶性收益博弈中被边缘化。
为了从根源上刻画这一经济学困境并重构健康的激励体系，本文首次从微观经济学与算法博弈论视角对测试时计算市场展开形式化建模。核心 idea：将服务商对测试时计算的自私配置建模为正规型势博弈并揭示其社会福利无序性，进而提出一种按边际生成价值结算的多属性次高价逆向拍卖机制，使服务商真实披露模型质量与边际成本成为弱占优策略，从根本上实现社会福利最大化。
方法详解¶
整体框架¶
本文构建了完整的理论与机制设计闭环：首先建立包含 \(N\) 个服务商与异质理性用户的正规型测试时计算博弈 \(\mathcal{G}\)；随后借助广义序数势博弈理论证明纯策略纳什均衡的存在性与收敛性，并严格量化其无序代价（Price of Anarchy, PoA）；最后设计基于质量验证的次高价逆向拍卖机制 \(\widetilde{\mathcal{G}}\) 消除市场无效率。
整个系统运行的数据流与博弈演进流程如下所示：
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["用户提交代表性任务与查询集合 Q"] --> B["测试时计算博弈建模<br/>定义质量-成本-定价与市场份额函数"]
B --> C["势函数收敛与纯纳什均衡分析<br/>证明收敛到利润最大化且福利受损的均衡点"]
C --> D["社会福利无序代价量化<br/>理论下界揭示过度消耗算力引发的福利损失"]
D --> E["次高价逆向拍卖机制设计<br/>服务商竞标质量与价格，平台按次优边际价值结算"]
E --> F["社会最优均衡达成<br/>真实披露为占优策略，无序代价严格降为 1.0"]关键设计¶
1. 测试时计算博弈建模：将算力分配与市场竞争解耦映射为正规型博弈
针对传统大模型评估忽略计算成本与市场竞争动态的缺陷，研究将针对特定任务 \(\mathcal{T}\) 的市场竞争形式化为正规型博弈 \(\mathcal{G}\)。每个服务商 \(i \in [N]\) 可策略性选择离散的计算档位 \(\theta_i \in \Theta\)（如采样数或思考分位数）。给定计算量 \(\theta_i\)，模型展现出平均质量 \(q_i(\theta_i)\)（如准确率），同时产生平均生成成本 \(c_i(\theta_i)\)，并以加成定价 \(p_i(\theta_i)\) 向用户收费，从而为用户提供净价值 \(V_i(\theta_i) = q_i(\theta_i) - p_i(\theta_i)\)。市场份额分配采用涵盖完全理性（Bertrand 式最大价值胜出）与有限理性（Logit 随机效用模型，由理性参数 \(\beta\) 控制）的统一函数： $\(s_i(V_i(\theta_i); \boldsymbol{V}_{-i}(\boldsymbol{\theta}_{-i})) = \frac{e^{\beta V_i(\theta_i)}}{e^{\beta V_0} + \sum_{j=1}^N e^{\beta V_j(\theta_j)}}\)$ 服务商效用为 \(U_i = s_i \cdot (p_i(\theta_i) - c_i(\theta_i))\)。定义社会福利为全社会用户获得价值与所有服务商利润的总和： $\(\text{W}(\boldsymbol{\theta}) = \sum_{i=1}^N s_i \cdot (q_i(\theta_i) - c_i(\theta_i)) + V_0 s_0\)$ 这一表述巧妙消去了内部转移价格 \(p_i(\theta_i)\)，严格证明了社会总福利仅取决于输出质量与生成真实成本之间的净剪刀差。
2. 势函数收敛性与均衡异化分析：证明算力通胀诱发的无序均衡
在多智能体非合作博弈中，纯策略纳什均衡的存在性往往难以保障。本文构造了一个精妙的显式势函数 \(\Phi(\boldsymbol{\theta})\)： $\(\Phi(\boldsymbol{\theta}) = \begin{cases} \log(p_{\pi(1)}(\theta_{\pi(1)}) - c_{\pi(1)}(\theta_{\pi(1)})) + C \cdot V_{\pi(2)}(\theta_{\pi(2)}) & (\beta = \infty) \\ \sum_{i=1}^N \log(p_i(\theta_i) - c_i(\theta_i)) + \beta \sum_{i=1}^N V_i(\theta_i) - \log\left(e^{\beta V_0} + \sum_{i=1}^N e^{\beta V_i(\theta_i)}\right) & (\beta < \infty) \end{cases}\)$ 证明了任何单方提升自身效用的算力变动必然严格提升势函数 \(\Phi\)，从而确立 \(\mathcal{G}\) 为广义序数势博弈。由此推导出有限动作空间下的改善响应动态（Better-response Dynamics）必然在有限步内收敛至纯策略纳什均衡 \(\boldsymbol{\theta}^\dagger\)。在完全理性均衡下，主导服务商为了击败第二名并最大化自身利润，会选择满足 \(V_1(\theta_1) > V_2^*\) 的最大计算量 \(\theta_1\)，将计算预算强行推高至远超社会最优水平的过载区间。
3. 社会福利无序代价量化：建立算力博弈效率损失的下界理论
为了从数学上刻画自私博弈导致的资源浪费，研究引入算法博弈论中的无序代价度量 \(\text{PoA}(\mathcal{G}) = \frac{\max_{\boldsymbol{\theta}} \text{W}(\boldsymbol{\theta})}{\text{W}(\boldsymbol{\theta}^\dagger)}\)。本文通过将均衡配置 \(\boldsymbol{\theta}^\dagger\) 与服务商独立最大化个体福利贡献的理想配置 \(\boldsymbol{\theta}^*\)（即 \(\theta_i^* = \arg\max_\theta (q_i(\theta) - c_i(\theta))\)）对比，推导出显式下界： $\(\text{PoA}(\mathcal{G}) \geq 1 + \frac{\text{W}_{\pi^*(1)}(\theta_{\pi^*(1)}^*) - \text{W}_{\pi(1)}(\theta_{\pi(1)}^\dagger)}{\text{W}_{\pi^*(1)}(\theta_{\pi^*(1)}^*)} + \mathcal{O}(e^{-\beta \Delta V})\)$ 该式表明，只要存在高算力带来的利润增长掩盖了边际价值衰减，主流服务商便会陷入囚徒困境式的“算力军备竞赛”，导致 PoA 严格大于 1，产生显著的宏观算力浪费。
4. 次高价逆向拍卖机制设计：以边际生成价值结算消除博弈偏差
为彻底消除现存市场激励扭曲，本文提出一个面向大模型算力配置的次高价逆向拍卖机制 \(\widetilde{\mathcal{G}}\)。平台向服务商广播用户提供的少量代表性样例 \(\mathcal{Q}\)，各服务商提交竞标二元组 \((q_i, p_i)\)。平台按照出价价值 \(V_i = q_i - p_i\) 进行降序排序并遴选最优服务商 \(\pi(1)\)，但最终用户向获胜服务商支付的结算价格 \(P\) 不取决于其自身报价，而是锚定在获胜者真实质量与次优服务商报价价值之间的差额： $\(P(\boldsymbol{\theta}, \mathbf{p}) = q_{\pi(1)}(\theta_{\pi(1)}) - V_{\pi(2)}(\theta_{\pi(2)}, p_{\pi(2)})\)$ 在此规则下，获胜服务商获得的净效用严格等于其相对于次优竞争者所创造的超额社会福利： $\(U_{\pi(1)} = P - c_{\pi(1)} = (q_{\pi(1)} - c_{\pi(1)}) - V_{\pi(2)} = \text{W}_{\pi(1)} - V_{\pi(2)}\)$ 研究进一步引入基于抽样无偏估计 \(\mathbb{E}[\hat{q}_{\pi(1)}] = q_{\pi(1)}\) 的质量审计协议，从理论上证明了各服务商如实选取社会最优计算量 \(\theta_i^* = \arg\max_\theta (q_i(\theta) - c_i(\theta))\)、真实上报质量并按边际成本出价 \(p_i^* = c_i(\theta_i^*)\) 构成弱占优策略。整个机制天然实现 \(\text{PoA}(\widetilde{\mathcal{G}}) \equiv 1\)，完全恢复帕累托最优配置。
实验关键数据¶
主实验¶
实验覆盖 12 款主流大语言模型，包括两大家族非推理模型（Llama-3-8B、Llama-3.1-8B、Llama-3.2-1B/3B 与 Qwen2-0.5B/1.5B/7B、Qwen2.5-3B/7B，采用 Best-of-N 采样 \(\theta \in \{1, 2, 4, 8, 16, 32, 64\}\)）以及 3 款基于 DeepSeek-R1 蒸馏的推理模型（DeepSeek-R1-Distill-Llama-8B、Qwen-1.5B、Qwen-7B，采用 CoT 思考长度 5 分位划分）。在 GSM8K 经典基准上的博弈均衡与拍卖机制对比如下：
| 模型类型与服务商配置 | 机制机制 / 模式 | 计算档位 \(\theta\) | 用户价值 (\(\times 10^{-3} \$\)) | 结算价格 (\(\times 10^{-3} \$\)) | 服务商效用 (\(\times 10^{-3} \$\)) | 社会总福利 (\(\times 10^{-3} \$\)) |
|---|---|---|---|---|---|---|
| 非推理模型 (9家服务商, BoN) | 传统计费博弈 \(\mathcal{G}\) (\(\beta=1000\)) | 16 | 5.5 | 1.20 | 0.25 | 5.8 |
| 非推理模型 (9家服务商, BoN) | 逆向拍卖 \(\widetilde{\mathcal{G}}\) (胜者 Qwen2.5-7B) | 2 | 7.1 (+29.1%) | 0.32 (-73.3%) | 0.18 (-28.0%) | 7.3 (+25.9%) |
| 推理模型 (3家服务商, R1蒸馏) | 传统计费博弈 \(\mathcal{G}\) (\(\beta=1000\)) | 4 | 7.1 | 0.18 | 0.04 | 7.1 |
| 推理模型 (3家服务商, R1蒸馏) | 逆向拍卖 \(\widetilde{\mathcal{G}}\) (胜者 R1-D-Qwen-7B) | 4 | 7.3 (+2.8%) | 0.30 (+66.7%) | 0.12 (+200.0%) | 7.4 (+4.2%) |
消融实验与参数敏感性分析¶
在 GSM8K 测试集上以 Qwen2.5-7B 为核心获胜模型，通过调节用户理性程度 \(\beta\)、服务商利润率（Margin）以及单位精度价值换算系数 \(\alpha\) 评估博弈动态与拍卖机制的稳定性：
| 实验条件配置 (Margin, \(\alpha\)) | 机制或理性参数 \(\beta\) | 计算档位 \(\theta\) | 用户价值 (\(\times 10^{-3} \$\)) | 结算价格 (\(\times 10^{-3} \$\)) | 服务商总效用 (\(\times 10^{-3} \$\)) | 社会福利 \(\text{W}\) (\(\times 10^{-3} \$\)) |
|---|---|---|---|---|---|---|
| Margin = 0.25, \(\alpha = \$0.008\) | 博弈 \(\mathcal{G}\) (\(\beta=200\)) | 32 | 4.40 | 1.60 | 0.32 | 4.70 |
| Margin = 0.25, \(\alpha = \$0.008\) | 博弈 \(\mathcal{G}\) (\(\beta=1000\)) | 16 | 5.50 | 1.20 | 0.25 | 5.80 |
| Margin = 0.25, \(\alpha = \$0.008\) | 博弈 \(\mathcal{G}\) (\(\beta=100000\)) | 4 | 7.10 | 0.33 | 0.07 | 7.20 |
| Margin = 0.25, \(\alpha = \$0.008\) | 逆向拍卖 \(\widetilde{\mathcal{G}}\) | 2 | 7.20 | 0.32 | 0.18 | 7.30 |
| Margin = 0.15, \(\alpha = \$0.008\) | 博弈 \(\mathcal{G}\) (\(\beta=1000\)) | 16 | 5.58 | 1.26 | 0.16 | 5.75 |
| Margin = 0.15, \(\alpha = \$0.008\) | 逆向拍卖 \(\widetilde{\mathcal{G}}\) | 2 | 7.17 | 0.33 | 0.18 | 7.35 |
| Margin = 0.05, \(\alpha = \$0.008\) | 博弈 \(\mathcal{G}\) (\(\beta=1000\)) | 16 | 5.58 | 1.26 | 0.06 | 5.64 |
| Margin = 0.05, \(\alpha = \$0.008\) | 逆向拍卖 \(\widetilde{\mathcal{G}}\) | 2 | 7.15 | 0.34 | 0.18 | 7.33 |
关键发现¶
- 算力过载与效率倒挂：在非推理模型的 Best-of-N 实验中，传统博弈均衡收敛至 \(\theta=16\)，而在拍卖机制中社会最优计算量仅为 \(\theta=2\)。计算量虚增 8 倍仅换取了极微小的准确率收益，却导致结算价格膨胀近 4 倍，系统无序代价达到 1.19（社会福利损失高达 16% 至 19%）。
- 用户理性参数的双重影响：随着用户理性程度 \(\beta\) 从 200 增至 \(10^5\)，市场逐渐向纯粹性价比倾斜，博弈配置的计算量从 32 回落至 4，社会福利稳步提升；但由于服务商单向利润驱动的存在，其依然无法自发达到社会最优的 \(\theta=2\)。
- 服务商收益分化与市场结构：在非推理激烈竞争市场中，拍卖机制压缩了过度膨胀的 token 费用，服务商整体利润下降 28%；而在推理模型等高技术壁垒市场（如 R1 蒸馏系列），优质服务商通过边际质量优势获得正向技术溢价，利润反而暴增 200%。
亮点与洞察¶
- 研究视角的颠覆性迁移：打破以往仅关注测试时计算能够提升多少 Benchmark 分数的纯技术路线，敏锐地指出在“按 Token 计费”的现实商业模式下，服务商存在诱导过度计算的天然逆向选择，具有高度的行业警示价值。
- 优雅的机制设计保真度：将古典微观经济学中的 Vickrey-Clarke-Groves（VCG）思想与打分逆向拍卖深度融合，通过锚定次优提供商的价值差实现按边际贡献结算，使理性自私的算力提供商自愿收敛至全社会最高效的计算水平。
- 高度务实的工程可迁移性：所提拍卖机制无需强行审计服务商内部复杂的私有网络结构，仅需输入少量验证集并在输出端执行蒙特卡洛抽样校验即可落地，为未来类似 OpenRouter、Together AI 等大模型中继路由平台的计费革新提供了直接落地方案。
局限与展望¶
- 用户效用异质性简化：模型假设所有用户对准确率与延迟的折算系数 \(\alpha\) 相同，但在实际工业生产中，高频低时延任务与高容错学术探索对质量和价格的容忍度极具异质性。
- 任务质量评估开销：在数学、竞赛编程等有明确 Ground-truth 的闭卷场景中，质量评估成本低廉；但在开放式写作、创意思维等模糊任务中，无偏质量估计器自身的评估开销和裁判模型偏置将构成机制运行瓶颈。
- 共谋与逆向作弊风险：次高价拍卖在博弈论上天然对投标方共谋（Collusion）与恶意哄抬次优报价较为敏感，未来需结合密码学承诺协议与抗合谋审计技术进一步加固。
相关工作与启发¶
- vs Velasco et al. (ICML 2026)：后者关注服务商在文本分词阶段通过恶意虚报 Token 数牟利的欺诈行为；本文则进一步深入算法内核，揭示出即使服务商完全如实报告 Token，仅凭对测试时计算深度的自私调度即可合法攫取超额利润并造成福利沉没。
- vs Snell et al. / Wang et al. (2024-2025)：既有测试时计算文献侧重于通过最优停止理论（Optimal Stopping）或预算感知评估在单机环境下提升计算利用率；本文则将问题拓展至多服务商非协同竞争的宏观市场生态，提供了首个博弈论视角的形式化解。
评分¶
- 新颖性: ⭐⭐⭐⭐⭐ 首次系统性提出测试时计算博弈并设计匹配机制，理论视角极具开创性。
- 实验充分度: ⭐⭐⭐⭐⭐ 兼顾非推理与前沿 R1 推理模型，数学推导与 4 大数据集实证高度自洽。
- 写作质量: ⭐⭐⭐⭐⭐ 符号系统严谨，经济学直觉叙述通透，图表与附录证明详实。
- 价值: ⭐⭐⭐⭐⭐ 对大模型云服务产业定价体系及 API 平台机制重塑具有重大的理论与现实指导意义。