acceptodds
Under review as a conference paper at ICLR 2027

Provably Efficient Test-Time Alignment via Shared Candidate Pools

Abstract

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 , overcoming the linear 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.

Primary area:
learning theory
Keywords:
Test-time alignment, Importance sampling, Sample complexity, Robust estimation, Uniform guarantees, Language models

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_KaugOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

The paper considers the following problem: For a question, generate a pool of answers and then based on user's preference sample an answer from the pool that aligns with user's preference. The goal is to construct a sampling distribution that optimize an objective function which is a sum of user's preference score and the KL divergence of with the original sampling distribution(without taking user's preference into account) The contribution is an algorithm called POOLALIGN, whose objective function value is close to the ideal optimum with high probability. The authors also proved some theoretical results that characterize the difficulties of the problem.

Critical strengths

The strength is a good theoretical guarantee of the algorithm and a precise characterization of the hardness of the problem.

Critical weaknesses

My biggest concern is about the motivation of the problem.

  1. The paper does not clearly identify cases in which questions are known in advance, while user preferences become available only after the candidate response pool has been generated.
  2. The paper does not demonstrate that a shared response pool reduces total cost compared with generating responses after the user's preference is known,
Questions for authors

Please see weakness.

Reviewer_WxiNOpenReview ↗
Rating
3(+1)
Confidence
2(−1)
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary
  • This paper formulates the post-generation preference revelation problem, in which preferences are revealed after candidate responses have been generated.
  • This paper identifies the worst-case second moment of the density ratio between the target and proposal distributions as a key quantity governing the sample complexity of the shared candidate response pool.
  • To perform test-time alignment in this setting, this paper proposes PoolAlign, an algorithm that combines blockwise self-normalized importance sampling with median-of-means estimation, and establish uniform approximation guarantees for the resulting serving policies.
Critical strengths
  • The problem setting is interesting and well-motivated. Since preferences vary across users, generating a shared pool of candidate responses in advance and selecting appropriate responses based on individual preferences is an efficient approach.
  • Although I have not fully understood all the theoretical details, the proposed algorithm and its theoretical guarantees appear reasonable. The objectives defined in Eqs. (2), (3), and (4) seem well-formulated, and I appreciate the worst-case guarantees. Introducing blockwise SNIS to address the properties of the importance weights also seems well-justified. Furthermore, estimating the optimal value using median-of-means could provide a quantitative measure for evaluating response selection.
Critical weaknesses
  1. The problem setting is interesting, but its practical applications are unclear to me. I understand that a preference θ\theta is represented through a score function sθs_\theta, which appears to correspond to a reward model. However, assuming that a reward model reflecting each individual preference is available seems somewhat unrealistic. Could you provide concrete examples of practical scenarios in which this setting would be applicable?

  2. I am concerned that the density ratio between the optimal policy and the proposal distribution can easily become unbounded. For example, this could happen when the optimal policy assigns positive probability to responses that the proposal distribution cannot generate. I understand that the authors introduce techniques such as blockwise SNIS to mitigate issues arising from large importance weights. However, how does the proposed method behave in such cases, particularly when the proposal distribution fails to cover the support of the optimal policy?

  3. The proposed method substantially underperforms Best-of-N (BoN) in terms of win rate in Figure 10. I understand that BoN has an inherent advantage under this evaluation setting, since it directly maximizes the reward used for evaluation. Nevertheless, these results raise concerns about the practical response quality of the proposed method. Could you provide additional evaluations using independent benchmarks or evaluators, such as AlpacaEval LC Win-Rate and accuracy on BIG-Bench Hard? Even if the proposed method does not outperform BoN, demonstrating reasonable performance on these benchmarks would help establish its practical usefulness.

Questions for authors

Please see Critical Weaknesses.

Reviewer_iQmbOpenReview ↗
Rating
3(+1)
Confidence
1(−1)
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies a test-time alignment scenario where preference is revealed after candidate responses have been generated. The proposed method POOLALIGN averages blockwise self-normalized importance sampling and uses a median-of-means estimator for the partition function.

Critical strengths
  1. The setting with shared candidate pool is reasonably motivated, which is meaningful for scenario where prompts repeat and user preferences vary.
  2. The paper provides detailed theoretical analysis.
Critical weaknesses
  1. The paper characterizes the required pool size via a coverage coefficient for a fixed proposal distribution, but the relationship between candidate count, semantic diversity, and preference coverage remains insufficiently explored. Increasing the pool size may add redundant responses rather than meaningfully expand coverage. Thus, the sample-complexity guarantees do not provide practical insights on how to construct an effective candidate pool.
  2. The partition strategy is insufficiently explored. While the theory provides guidance on the number of blocks, it offers limited insight into how candidates should be assigned to blocks. It remains unclear how sensitive performance is to the particular block partition strategy.
Questions for authors

Please refer to the weaknesses.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.