Sequential Consensus Policy Optimization for Test-time Reinforcement Learning

Test-time policy optimization improves language models by sampling multiple rollouts per prompt and using their majority-vote answer as a pseudo-label, without any ground-truth supervision. This procedure is expensive since allocating a fixed rollout budget to every prompt wastes compute on prompts whose answer has already settled. Adaptive stopping rules help, but existing methods decide using only the current visit, discarding what earlier visits to the same prompt revealed about its answer distribution. We introduce Sequential Consensus Policy Optimization (SCPO), which maintains a Dirichlet posterior over each prompt's answer distribution, warm-started by an exponential moving average of past answer counts, and stops sampling once the posterior probability that some answer is the mode exceeds a certified threshold. We establish guarantees for adaptive stopping and gap-dependent rollout complexity, and characterize when the EMA-based memory remains accurate and reduces the rollout budget. Across Qwen2.5-Math-1.5B and Llama-3.1-8B-Instruct on MATH-500, AIME 2024, and LiveCodeBench, SCPO cuts rollouts per prompt by up to 71% and generated tokens by up to 66% relative to TTRL, while maintaining competitive accuracy.