Learning to Discover at Test Time

Motivation

• Known: AlphaEvolve와 같은 기존 test-time scaling 방법은 frozen LLM에 진화적 탐색(evolutionary search)을 적용해, 버퍼에 저장된 과거 시도들을 hand-crafted heuristic으로 재구성한 프롬프트를 통해 반복 샘플링하며 최적 해를 찾는다.
• Gap: 기존 방법에서는 LLM 자체(가중치 θ)가 고정되어 있어 문제에 대한 경험이 프롬프트 개선에만 쓰이고 정책 내재화로 이어지지 못하며, 표준 RL은 평균 보상 극대화와 여러 문제로의 일반화를 목표로 하는 반면 discovery 문제는 단 하나의 최고 해를 이 특정 문제에서만 찾는 것이 목표라는 근본적 차이를 다루지 않았다.
• Why: 과학적 발견 문제는 정의상 모델의 학습 데이터뿐 아니라 인류의 기존 지식 전체를 벗어나는 아이디어를 요구하므로, 프롬프트만으로는 한계가 있고 정책 자체가 test time에 학습을 통해 개선될 수 있어야 실제 새로운 state-of-the-art 발견이 가능하다.
• Approach: 단일 테스트 문제를 하나의 MDP(환경)로 정의하고, 그 환경에서 정책 πθ에 대해 test time에 강화학습을 수행하되, 학습 목표와 탐색 서브루틴(reuse)이 평균 성능이 아닌 가장 유망한 해(best solution)를 우선시하도록 설계한다.

Achievement

Figure 3. Results in GPU kernel engineering. TTT-Discover

1. 네 개 분야에서 SOTA 달성: 수학(Erdős 최소 중첩 문제, 자기상관 부등식), GPU 커널 엔지니어링(GPUMode TriMul 대회, 최대 2배 속도 향상), 알고리즘 설계(과거 AtCoder 대회), 생물학(단일세포 RNA-시퀀싱 디노이징 문제)에서 거의 모든 문제에 대해 새로운 state-of-the-art를 달성했다.
2. 오픈 모델만으로 결과 재현: 기존 최고 성능이 closed frontier model을 요구했던 것과 달리, 공개 모델인 OpenAI gpt-oss-120b만으로 모든 결과를 달성하고 코드도 공개했다.
3. 저비용 test-time training: Thinking Machines의 Tinker API를 이용해 문제당 단 수백 달러 수준의 비용으로 test-time RL을 수행했다.
4. 전문가/주최자 검증: 해결책들이 각 분야 전문가 또는 대회 주최자에 의해 검토·검증되었다.

How

• 과학 문제를 텍스트 설명 d, 후보 해 s(상태), 연속 보상함수 R(s), 최고 기지 해 ssota, rsota로 구성된 MDP(환경)로 정형화하고, R(s) > rsota가 되는 s를 찾는 것을 discovery로 정의한다.
• Best-of-N: πθ(·|d,s)에서 i.i.d. 샘플링하여 탐색, 초기 상태 s는 보통 exploration을 위해 <empty>로 설정.
• State reuse: 버퍼 Hi에서 고보상 해를 선호하되 저보상 해에도 확률을 부여하는 reuse heuristic으로 초기 상태 si를 샘플링해 warm start.
• State-action reuse (evolutionary search, AlphaEvolve 등에서 사용): thinking tokens·중간 결과 등 action 정보까지 재사용하고 자연어 컨텍스트 ci로 변환.
• TTT-Discover (Algorithm 1): 위 reuse 서브루틴에 더해 정책 자체를 버퍼 Hi에 누적된 자신의 탐색 시도들로 온라인 학습(train 서브루틴)시켜, 표준 RL과 달리 평균 보상이 아닌 최고 해(best solution) 발견을 우선시하도록 학습 목표와 탐색을 설계한다.

Originality

• Test-time scaling을 프롬프트 기반 frozen-LLM 탐색에서 test-time RL을 통한 정책 자체의 계속 학습으로 전환한 새로운 패러다임을 제시했다.
• 표준 RL의 목표(평균 보상 극대화, 다중 문제 일반화)와 근본적으로 다른 discovery 문제 고유의 목표(단일 최고 해, 단일 문제 특화)를 명시적으로 정식화하고, 이에 맞춰 학습 목표와 탐색 서브루틴을 재설계했다.
• 수학, GPU 커널, 알고리즘, 생물학 등 이질적인 네 도메인에 걸쳐 시도한 거의 모든 문제에서 SOTA를 달성함으로써 방법의 범용성을 폭넓게 실증했다.
• Closed frontier model 없이 오픈 모델(gpt-oss-120b)과 저비용 API(Tinker)만으로 재현 가능한 결과를 제공하여 접근성을 크게 높였다.

Limitation & Further Study

• 연속 보상 함수가 존재하는 문제로 범위가 제한되어 있어, 보상을 정의하기 어려운 개방형·정성적 과학 문제에는 적용이 어려울 수 있다.
• test-time에 매 문제마다 별도의 RL 학습을 수행해야 하므로, 문제 수가 많아질 경우 총 비용과 시간이 누적될 위험이 있다(문제당 수백 달러라도 스케일링 시 부담).
• 보고된 성과가 전문가/주최자 검토에 의존하는데, 검토 기준의 엄밀성이나 모든 분야에 대한 재현성 검증이 충분히 상세히 제시되지 않았을 가능성이 있다.
• 후속 연구로 reuse heuristic과 train 서브루틴의 이론적 분석, 다양한 보상 형태(비연속·희소 보상)로의 확장, 더 큰/다른 오픈 모델과의 비교가 필요하다.

Evaluation

총평: Test-time에 정책 자체를 학습시켜 단일 과학 문제의 최고 해를 찾는다는 아이디어는 기존 프롬프트 기반 진화적 탐색의 근본적 한계를 짚어내며, 네 개 이질적 도메인에서의 광범위한 SOTA 달성과 오픈 모델 기반 재현성까지 갖춘 인상적인 연구다.