Learning to Discover at Test Time

algorithm 2601.16175

test-time-trainingevolutionary-variationgradient-updatediscovery

§1 TL;DR #

TTT-Discover 在测试时对 LLM 执行在线 RL（entropic objective + PUCT state reuse），针对单一科学问题持续学习以发现 SOTA 解，在数学/GPU kernel/算法竞赛/生物分析上全面刷新记录，仅用开源模型和 ~$500/题。

§2 痛点 / 方法 / 结果 #

Q1 痛点 #

科学发现问题要求超越训练数据甚至全人类知识的新想法。先前 AlphaEvolve 等方法仅在冻结 LLM 上做 prompt-driven evolutionary search——模型本身不能改进，类似"永远无法内化新思想的学生"。Naive RL 在测试时也不适用：(1) 优化平均 reward 而非最大值，对 SOTA 附近的微小改进无感；(2) 从头开始的短有效视野限制复杂度；(3) 策略塌缩到安全高 reward 动作。

Q2 方法 #

TTT-Discover 在 test-time 持续训练 LLM，两个核心创新：

组件	Before (naive RL / evolutionary search)	After (TTT-Discover)
学习目标	$\mathbb{E}[R]$ — 平均 reward，对 SOTA 附近无差异	$J_\beta = \log \mathbb{E}[e^{\beta R}]$ — entropic utility，$\beta \to \infty$ 趋近 max
State reuse	无 reuse 或 heuristic $\epsilon$-greedy	PUCT — max-based $Q(s)$ + rank-based prior + UCB exploration

核心技术壁垒: Adaptive $\beta(s)$ 通过 KL 约束 $\mathrm{KL}(q_\beta \| \pi_\theta) = \gamma$ 自动调节——reward 分布均匀时增大 $\beta$ 以放大差异，存在极端 outlier 时降低 $\beta$ 防止权重集中。这使得学习信号在整个训练过程中保持有效，而 constant $\beta$ 在后期信号衰减。

Q3 结果 #

Erdős minimum overlap: 上界 0.379993（vs 前 AI SOTA 0.380127）
TriMul kernel (H100): 1161μs（vs 1st human 1371μs，提速 15.3%）
AtCoder ahc039/ahc058: 双双第一名
scRNA-seq denoising: PBMC 0.71 / Tabula 0.73（超越所有传统和 AI 方法）
仅用 gpt-oss-120b (open) + LoRA rank 32，每题 ~$500

§3 架构 / 方法图 #

flowchart TB subgraph TTT-Discover["Algorithm 1: TTT-Discover Loop (50 steps × 512 rollouts)"] A["Buffer H₀ = {(empty, R(empty))}"] --> B["s_i, c_i ~ PUCT(H_i)"] B --> C["a_i ~ π_θᵢ(· | d, s_i, c_i)"] C --> D["s'_i = T(a_i), r_i = R(s'_i)"] D --> E["H_{i+1} = H_i ∪ {(s_i, a_i, s'_i, r_i)}"] E --> F["θ_{i+1} = θ_i + η∇J_β(θ_i)"] F --> B end subgraph Entropic["Entropic Objective"] G["Batch N rollouts from same s"] --> H["Compute q_β(n) = exp(βr_n) / Σexp(βr_m)"] H --> I["Bisect β: KL(q_β ∥ u) = γ = ln(2)"] I --> J["LOO advantage: A_n = exp(β(r_n-r_max))/Z_{-n} - 1"] end subgraph PUCT["PUCT State Reuse"] K["score(s) = Q(s) + c·P(s)·√(1+T)/(1+n(s))"] L["Q(s) = max child reward (not mean)"] M["P(s) = linear rank-based prior"] end F -.-> Entropic B -.-> PUCT

§4 作者证明 #

符号表 #

符号	含义	维度/取值
$\pi_\theta$	LLM 策略	—
$d$	问题描述	text
$s, s'$	候选解(状态)	domain-specific
$R(s) \in \mathbb{R}$	连续 reward	scalar
$\mathcal{H}_i$	经验缓冲区	set of $(s, a, s', r)$
$\beta(s)$	自适应逆温度	$\geq 0$
$\gamma$	KL budget	$\ln(2)$
$w_\beta(a)$	指数优势权重	$\geq 0$
$Q(s)$	最优子节点 reward	scalar
$P(s)$	rank-based prior	$[0,1]$
$n(s)$	扩展次数	integer

方程物理意义 #

Entropic utility: $J_\beta(\theta) = \log \mathbb{E}_\pi[e^{\beta R}]$ — log-partition function of reward-weighted policy. 当 $\beta \to 0$ 退化为 $\mathbb{E}[R]$；当 $\beta \to \infty$ 趋近 $\max R$。Discovery 问题只需一个最优解，因此需要大 $\beta$。

Adaptive $\beta$ via KL: $\mathrm{KL}(q_\beta \| \pi_\theta) = \gamma$ — tilted distribution $q_\beta$ 与策略的 KL 恰好为 budget $\gamma$。类似 REPS (Peters et al. 2010)。

PUCT with max-Q: AlphaZero 用 mean，TTT-Discover 用 max——因为 discovery 只需一个最优解，不需要平均表现。

6 项检查 #

假设: reward 是连续的、可求值的（非 sparse/binary）— 所有 4 个领域满足
收敛保证: 无收敛定理；方法是 heuristic online RL with adaptive temperature
变分解释: entropic objective = 变分推断中的 log-partition function bound
样本复杂度: 50 steps × 512 rollouts = 25,600 total evaluations — 与 Best-of-N 相同预算
$\beta$ 稳定性: bisection over $\beta \geq 0$ 保证精确解存在（KL 对 $\beta$ 单调）
LOO 去偏: leave-one-out normalizer $\hat{Z}_{-n}$ 避免自举偏差

§5 实验与数据 #

训练配置 #

Stage	Purpose	Data	Steps	Technique
Pre-train (external)	通用 LLM	—	—	gpt-oss-120b 已训练好
TTT	单问题在线 RL	自身 rollouts	50	LoRA r=32, Adam lr=4e-5, batch 512

关键实验 #

Table 2 — Erdős minimum overlap: TTT-Discover 0.379993 vs ThetaEvolve 0.380127 vs AlphaEvolve V2 0.380261。每一步改进约 $10^{-4}$ 量级，数学意义重大。

Table 4 — TriMul kernel: A100 上 2198μs（vs 4531 human），H100 上 1161μs（vs 1371 human）。发现的策略：fuse LayerNorm/gating/output，matmul 转 FP16 委托 cuBLAS。训练仅在 H100 上进行却泛化到 A100/B200/MI300X。

Table 8 — Ablation: Adaptive entropic + PUCT = 1203μs; constant β = 1484μs (+23%); no TTT = 2061μs (+71%); no reuse = 5274μs (4.4× worse)。证明两个组件缺一不可。

Table 6 — AtCoder: ahc039 567,062（超越 1st human 566,997），ahc058 848,414,228（超越 ALE-Agent 848,373,282）。

超参数 #

参数	值
Model	gpt-oss-120b
LoRA rank	32
Batch	512 (8×64)
Steps	50
Adam lr	4×10⁻⁵
KL budget γ	ln(2)
PUCT c	1.0
Context	32768 tokens
Cost	~$500/problem

§6 论证链 #

Step	论据	证据	结论
1	Search alone (frozen LLM) 有瓶颈	Best-of-25600 在 kernel 上 9219μs vs 2198μs TTT-Discover; OpenEvolve 在 Erdős 上无改进	仅搜索在困难问题上收益递减，需要学习
2	Naive RL 不适合 discovery	Ablation: expected reward objective 仅达 1986μs; 无 reuse 达 5274μs	标准 RL 优化平均而非最大，且缺少 reuse 使视野短
3	Entropic objective 逼近 max	$J_\beta \to \max R$ as $\beta \to \infty$; adaptive $\beta$ 通过 KL constraint 维持有效信号	目标函数天然匹配"只需一个最优解"的需求
4	PUCT max-Q 优于 mean-Q	Table 8: PUCT (1203μs) vs ε-greedy (1329μs); Q 用 max 而非 mean 确保探索不回退	Optimistic exploitation 更适合 discovery
5	两组件协同产生 SOTA	所有 4 领域刷新记录（Table 2-7），且仅 full TTT-Discover 达到最优	方法在多样化领域泛化有效

§7 实现 cross-reference #

代码开源: 论文声明 "publicly available code"，但未给出具体 repo URL。

关键实现细节:

Importance sampling ratio correction: sampler 与 learner 可能使用不同 policy 版本（异步），通过 ratio correction 补偿 off-policy 偏差。
Teacher forcing on context overflow: 当 prompt + thinking 超过 26,000 tokens 时，注入 "okay, I am out of thinking tokens..." 作为截断标记。

基础设施: Tinker API (Thinking Machines) 提供在线 RL 训练能力，支持 LoRA 热更新和批量 rollout。

[实现未公开 — 论文声称代码公开但截至阅读时未见 repo link]