Provably Efficient Test-Time Alignment via Shared Candidate Pools

Test-time alignment enables a fixed language model to serve diverse user preferences without retraining. To amortize generation costs, systems often pre-generate a shared candidate pool before the specific preference is revealed, serving requests later via importance reweighting. We ask: how large must this shared pool be to reliably approximate the optimal aligned response for any revealed preference? Standard importance sampling struggles in this setting, as it requires bounded importance weights—a condition rarely met in language models—leading to loose high-probability bounds. We introduce POOLALIGN to overcome this. By employing a novel blockwise normalization strategy, POOLALIGN naturally controls extreme weights without restrictive bounded-ratio assumptions, paired with robust aggregation for stable value estimation. We prove that POOLALIGN achieves uniform approximation with a sample complexity that scales optimally with the target-proposal divergence. Crucially, it attains high-confidence guarantees with a logarithmic dependence on the failure probability $\log (1/\delta )$, overcoming the linear $1/\delta$ penalty of standard second-moment bounds. Experiments on heavy-tailed tasks and real LLM candidate pools confirm these theoretical gains. We further establish a nearly matching fixed-proposal lower bound. The construction requires only an evaluable proposal density and is otherwise agnostic to the language model. Experiments on exact, heavy-tailed, and language-model pools support the predicted scaling and confidence behavior.