acceptodds
Under review as a conference paper at ICLR 2027

Towards a Theory of Inference-time Alignment with Unknown Rewards

Abstract

Generative model alignment has received broad interest, and significant progress has been made in supervised fine-tuning and inference-time computation. Yet, alignment has remained poorly understood from a statistical learning perspective. We formulate inference-time alignment as a weak-to-strong learning problem, where a reference policy (weak model) is assumed to be fairly good and the goal is to produce a strong model that predicts a good response at test time with arbitrarily high probability. Our problem is formulated as learning from scratch — everything is learned from data rather than assuming access to a good reward estimate, and thus differs from the existing inference-time alignment theory. Our framework shares similarity to the recent work of Joshi et al., 2026, where for each prompt, there could be multiple good responses. Our definition of the alignment learnability follows the standard PAC learning principle. We introduce a novel combinatorial dimension of the reward class which we call the alignment dimension, and show that it completely characterizes the alignment learnability — a reward class is alignment learnable if and only if its alignment dimension is finite. The core of our learning procedure works by learning a pairwise comparator and then running a tournament over candidate responses. We believe that our results might shed light toward establishing a complete theoretical understanding of alignment.

Primary area:
learning theory
Keywords:
PAC Learning, Inference-time Alignment, Weak-to-strong Learning

Reviews

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

The paper studies the statistical learnability of inference-time alignment with unknown binary rewards. In its framework, the learner receives pairs of responses sampled from a reference policy together with their individual correctness labels, and must select a correct response from a candidate pool at test time. Under realizability and a uniform lower bound on the reference policy’s probability of generating a correct response, the paper introduces the alignment dimension and establishes that its finiteness is necessary and sufficient for learnability. The sufficiency proof reduces the problem to learning partial binary comparisons and uses a tournament-based selection procedure; the necessity proof constructs hard instances from shattered response pairs. The paper also presents examples intended to distinguish alignment learnability from standard reward classification and examine limitations of common learning principles. Validation consists of theoretical proofs and constructed examples, without empirical experiments.

Critical strengths

The paper provides a meaningful characterization of inference-time alignment learnability within its formal setting: a reward class is learnable if and only if its alignment dimension is finite. The reduction to learning partial binary comparisons, together with the necessity argument, identifies a structural property governing response selection rather than full reward prediction. This distinction is consequential because it allows alignment learnability to be characterized even for reward classes with infinite VC dimension, providing useful insight into the difference between selecting a correct response and accurately classifying all responses.

Critical weaknesses
  1. Example 3 contains an incorrect lower bound and an unsupported inference about algorithmic failure. On page 6, lines 275–277, the paper claims that any learned binary reward predictor has expected classification error at least 1/21/2 on an unseen prompt. For p=1p=1, consider
\widehat r(x_i,y^{(2)})=\widehat r(x_i,y^{(3)})=0.$$ Under the stated reference distribution, its classification error is $0$ when $s_i=1$ and $1/2$ when $s_i=2$. Since these cases are equally likely, $$\mathbb E_{s_i}[\operatorname{err}(\widehat r)]=\frac14<\frac12.$$ Moreover, a positive classification-error lower bound does not establish failure to select a correct response. In this example, correctness is downward closed in the response index, so selecting the smallest-indexed candidate succeeds whenever the pool contains a correct response. A constant binary predictor combined with this tie-breaking rule achieves failure probability $2^{-k}$ under the specified reference distribution. Unless such tie-breaking is explicitly excluded, the example does not establish the claimed failure of every binary learn-and-optimize strategy. These issues undermine the paper’s asserted separation from an important family of existing approaches, although they do not themselves refute the main learnability theorem. 2. **The connection between the formal characterization and practical inference-time alignment is insufficiently established.** The theorem assumes exact realizability, access to the individual correctness labels of both training responses, and a positive uniform lower bound on the reference policy’s probability of producing a correct response for almost every prompt. Individual correctness labels provide stronger information than ordinary relative preferences, while the coverage assumption excludes positive-probability sets of prompts on which the reference policy cannot generate a correct response. These are legitimate modeling assumptions, but they substantially delimit the result’s practical scope. The paper provides no empirical evaluation, comparisons with representative baselines, or ablation studies. Without experimental validation or supporting empirical data and statistical analysis, the practical effectiveness of the proposed selection procedure and its advantages over existing approaches remain unverified, leaving the argument for its practical significance insufficiently substantiated.
Questions for authors
  1. Clarification of the lower bound in Example 3. How do the authors reconcile the 1/21/2 classification-error lower bound on page 6, lines 275–277, with the following counterexample? For p=1p=1, let
\widehat r(x_i,y^{(2)})=\widehat r(x_i,y^{(3)})=0.$$ Under the specified reference distribution, the classification errors for $s_i=1$ and $s_i=2$ are $0$ and $1/2$, respectively, giving an expected error of $1/4$. Is an additional restriction missing from the statement, or should the bound be corrected? Please clarify which subsequent conclusions depend on this bound. 2. **Clarification of selection failure and synthetic verification.** What restrictions on optimization and tie-breaking are needed for Example 3 to rule out every binary learn-and-optimize strategy? Selecting the smallest-indexed candidate succeeds whenever a correct response is present. A constant binary predictor with this tie-breaking rule therefore has failure probability $2^{-k}$ under the example’s reference distribution. Please explain why this procedure is excluded, or revise the claimed separation accordingly. To verify the claims in Examples 2–4, could the authors provide synthetic reproductions that separately report reward-classification error and response-selection failure, explicitly specify tie-breaking rules, and compare the proposed procedure with ERM-based selection and pessimistic selection? In particular, Example 3 should include both random and smallest-index tie-breaking. These checks would help determine whether the reported failures arise from the learning principles themselves or from particular implementation choices. 3. **Potential practical implications under controlled comparisons.** I recognize that the paper’s main contribution is theoretical. Still, could the authors provide a small-scale experiment on GSM8K or MATH to explore whether the pairwise-selection principle offers useful guidance for practical inference-time alignment? If implementing the theoretical learner is impractical, please explain the obstacles and how any experimental approximation relates to it. A controlled comparison could train a pairwise comparator and a scalar correctness predictor using the same underlying responses and binary correctness annotations. The scalar baseline should be allowed to use continuous scores for Best-of-N selection. Please specify how equally rewarded training pairs and inference-time ties are handled. Both methods should use the same base model, prompting and sampling settings, identical test candidate pools, and prompt-disjoint training, validation, and test splits. Please report selected-response accuracy, candidate-pool coverage, and selection accuracy conditional on a correct response being present, together with uncertainty across repeated runs. Test correctness labels should be used only for evaluation or an explicitly identified oracle reference. A limited variation of training-set or candidate-pool size, with comparison counts and runtime, would also help assess the tradeoffs. This request concerns the framework’s potential practical implications, not an empirical test of the learnability theorem. Such evidence, or a clear explanation of the implementation limitations, would help me understand how the theoretical insights might inform practical algorithm design.
1 comment
AuthorsOpenReview ↗

To reviewer C6af

We thank you for your time and effort in reviewing our work.

  • Example 3 and Learn-and-optimize principle: The expected error is greater than or equal to 1/4 or more specifically 1/2 - 1/4p. However, this fact does not change or disprove the message we want to convey through this example: that no matter what reward function you pick without seeing the test-time samples, the best response (Uniformly randomly pick one if there are multiple responses having value 11 based on the learned reward function) based on that learned reward function will be incorrect with constant probability. We consider the worst-case tie-breaking, because the best-case tie-breaking, which always chooses the response with the smallest index, can be interpreted as the closure algorithm or pessimism principle, which is discussed in the next example. We already mentioned this in the last paragraph of Appendix B.2 on page 18. We also emphasize that this example does not rule out the case where the reward functions are real-valued, as we restrict in this paper the reward class of binary reward functions. We are the first to provide a PAC-style formulation of the inference-time alignment problem and characterize its learnability, which we believe is a contribution to the theoretical understanding of alignment. We hope our work could facilitate more rigorous understanding of the alignment problem.

    For the connection between the formal characterization and practical inference-time alignment, we consider the case of binary rewards, and assuming access to the individual correctness of each training response matches exactly the data assumption of RLVR (see our discussion in Appendix A). Regarding assuming a positive uniform lower bound on the reference policy’s probability of producing a correct response, we refer the reviewer to Subsection 2.2, where we discussed one possible revision to the loss objective, which allows us to pick an arbitrary γ\gamma and get the error guarantee at those prompts where πref\pi_{\mathrm{ref}} has a correct probability of at least γ\gamma by O((1/γ)log⁡(1/ϵ))O((1/\gamma)\log(1/\epsilon)) inference sampling. Regarding the exact realizability assumption, we would like to point out that theoretical work on statistical machine learning usually starts with the realizable case and then extends to general cases with noise, which we leave open for future work.

  • This is a learning theory paper, like all the rest of papers in the learning theory area, we prove theorems instead of running experiments to improve the understanding of problems. In learning theory, people usually utilize tools from mathematics to prove the results. Or, more formally, the theorists usually rely on deductive reasoning (math proof) instead of inductive reasoning (multiple experiments) in their inference. Deductive reasoning is as valid as inductive reasoning (or more) and therefore, we do not see the necessity of experiments to finish our argument. Our theorem and proof hold under our formalization of this problem, and we believe this formalization grasps the main aspects of inference-time alignment. However, this work shares the spirit of the PAC learning framework, which only provides a simple mathematical framework for some practical problems. There might not be an exact match between the theoretical framework and the practical problem, but it helps people to understand the foundations of statistical learning. We also provide a potential suggestion for practical alignment, which is that learning how to compare a pair of responses instead of learning the reward function might be a better choice when designing an alignment algorithm. However, we would like to emphasize that this work, by its nature, is a theoretical work and does not claim a direct implication in practice.

  • Moreover, we believe the theoretical nature of the submission should not be the ground for rejection. In fact, in addition to practical works, the interdisciplinary ICLR conference also includes learning theory as a relevant topic and has accepted pure theoretical works studying similar topics [e.g., JLB+26, WGS25, HK26].

    [JLB+26]: Learning to answer from correct demonstrations. ICLR 2026

    [WGS25]: No free lunch: fundamental limits of learning non-hallucinating generative models. ICLR 2025

    [HK26]: Enforcing axioms for AI alignment under loss-based rules. ICLR 2026

We would be happy to discuss and elaborate more if you have any other concerns or questions. If our rebuttal fully addresses your concerns, we sincerely hope that you could re-evaluate our work.

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

This paper studies inference-time alignment from a statistical learning perspective, focusing on whether a learner can reliably select a correct response from multiple candidates without knowing the true reward function. The paper introduces a new measure called the alignment dimension and proves that a reward class is alignment learnable if and only if its alignment dimension is finite. To establish this result, the authors reduce the problem to learning a partial pairwise comparison class and develop a tournament-based selection procedure.

Critical strengths

1.The paper establishes a necessary and sufficient condition for inference-time alignment learnability. The result applies to potentially infinite reward classes and provides a theoretical characterization of when reliable response selection is possible.

2.The introduction of the alignment dimension provides a clear characterization of the proposed learning problem. The authors prove that a finite alignment dimension is both necessary and sufficient for a reward class to be alignment learnable.

Critical weaknesses

1.While the theoretical characterization is interesting, its practical significance remains unclear. The paper lacks empirical validation or concrete applications to realistic reward classes, making it difficult to assess whether the proposed theory can meaningfully contribute to practical alignment methods.

2.While Theorem 1 establishes a theoretical characterization of alignment learnability, it remains unclear how this result translates into actual learning in practical settings. Although the authors provide a learning procedure with statistical guarantees, these guarantees do not necessarily imply that a pairwise comparator can be successfully trained using practical learning methods.

3.The sampling bound in Theorem 2 depends on γ\gamma, a uniform lower bound on the reference policy’s success probability, which may be difficult to estimate when rewards are unknown. Without a procedure to estimate or certify this quantity, the bound provides limited guidance for choosing the inference-time sampling budget.

Questions for authors

n/a

3 comments
AuthorsOpenReview ↗

To reviewer K4kL

We thank the reviewer for taking time and effort evaluating our work, and also for your insightful comments. Below we address your concerns.

  • Regarding your concern about the concrete applications to practical language model alignment, we emphasize that our work is, by its nature, theoretical, and thus might not have direct guidance to instruct real-world alignment applications. However, standard statistical learning theory (e.g., VC theory for binary classification) has been extensively studied for decades and has greatly facilitated humans' understanding of machine learning. Our work is motivated by the fact that, while there are plenty of works studying language model alignment, the answer to the most fundamental question of learnability, as well as a reasonable PAC learning framework for the problem, are still lacking. Our formulation is general without making strong assumptions, and the techniques are non-trivial. We expect that our work might shed light on developing more rigorous and systematic understandings of the alignment task and advance the improvements of alignment algorithms.

    That said, our theory does have the following implication — for test-time alignment (such as best-of-N or rejection sampling), it is suboptimal (or might even be incorrect) to first learn (an estimate of) the true reward function from data and then optimize over samplings accordingly (which we call the learn-and-optimize principle in Subsection 3.2). Instead, correct algorithmic principles should try to directly learn comparisons from data. We believe this could potentially lead to algorithmic advances for practical alignment tasks. For instance, one potential message of our work which might have practical relevance is that it is possible to consider reward classes that are hard to learn or even not directly learnable (large or infinite VC dimension), but for which comparisons are learnable (finite alignment dimension). Indeed, this could inspire methods such as training a neural network that maps a prompt xx and two responses y(0)y^{(0)} and y(1)y^{(1)} to a preference signal. We emphasize that, we are not saying that we should always learn comparisons, it is more that future work might consider a broader family of reward classes, including those not directly learnable.

  • Moreover, we believe the theoretical nature of the submission should not be the ground for rejection. In fact, in addition to practical works, the interdisciplinary ICLR conference also includes learning theory as a relevant topic and has accepted pure theoretical works studying similar topics [e.g., JLB+26, WGS25, HK26].

    [JLB+26]: Learning to answer from correct demonstrations. ICLR 2026

    [WGS25]: No free lunch: fundamental limits of learning non-hallucinating generative models. ICLR 2025

    [HK26]: Enforcing axioms for AI alignment under loss-based rules. ICLR 2026

  • For the dependency on γ\gamma, we would like to refer the reviewer to Subsection 2.2, where we discussed one possible revision to the loss objective. This revision allows us to pick an arbitrary γ\gamma and get the error guarantee at those prompts where πref\pi_{\mathrm{ref}} has a correct probability of at least γ\gamma by O((1/γ)log⁡(1/ϵ))O((1/\gamma)\log(1/\epsilon)) inference sampling. Further, this allows us to bypass the uniform lower bound of γ\gamma. Instead, we only need to know the γ\gamma such that Pr⁡(x∈x:πref(y:r∗(x,y)=1∣x)≥γ)≥1−ϵ/2\Pr(x\in\\{x:\pi_{\mathrm{ref}}(y:r^*(x,y)=1|x) \geq \gamma\\}) \geq 1-\epsilon/2, and a union bound will imply the learnability we defined. We can estimate this γ\gamma by sampling prompts Ω((1/ϵ)log⁡(1/ϵ))\Omega((1/\epsilon)\log(1/\epsilon)) times and querying the πref\pi_{\mathrm{ref}} until we find a correct answer for every sampled prompt. Then take the inverse of the maximum number of queries as γ\gamma.

We would be happy to discuss and elaborate more if you have any other concerns or questions. If our rebuttal fully addresses your concerns, we sincerely hope that you could re-evaluate our work.

Thank you for your response. I have few technical concerns about the paper, and I understand its theoretical focus. As I noted in my review, I would still like to see a clearer discussion of the potential applications of this work, since inference-time alignment is motivated by practical problems. Anyway, I’m willing to raise my rating.

We thank you for your feedback and for raising your score! Fair point on the lack of potential applications to real-world alignment. We definitely agree that it would be nice if a theory paper could provide guidance to practical problems. We would like to include a discussion about potential applications to the algorithmic design for practical alignment. Thanks again for motivating us to think about the practical significance of our results!

Reviewer_GsNLOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies how to align language model outputs at inference time when the true reward function is unknown. It proposes sampling multiple candidate responses from a reference policy and using labeled training data to learn how to identify a good response. Its main theoretical contribution is the alignment dimension, a measure of reward-class complexity that characterizes when this learning problem is PAC-learnable, along with upper and lower bounds on sample complexity.

Critical strengths

The introduction of alignment dimension is a key theoretical contribution, providing a problem-specific complexity measure that characterizes the PAC learnability of inference-time alignment. The necessary-and-sufficient characterization, supported by upper and lower bounds, gives a principled foundation for understanding when alignment is possible under the paper’s assumptions.

Critical weaknesses

While the alignment dimension provides an elegant theoretical characterization of learnability, the paper offers limited guidance on how this result can be translated into practical inference-time alignment systems. In particular, it remains unclear how to estimate or exploit the alignment dimension for realistic reward classes and large language models, or how the proposed learning algorithm would scale to the large candidate sets and computational costs involved in comparing responses pairwise. The absence of experiments or a concrete implementation leaves the practical utility of the theoretical results largely unexplored.

Questions for authors

Can the alignment dimension be formally related to VC dimension?

Can the authors provide a concrete example demonstrating how the proposed framework could be applied to a realistic language model alignment task, including how the alignment dimension could be estimated or bounded for a practical reward class and how the sample complexity and computational costs would scale with the number of candidate responses?

2 comments
AuthorsOpenReview ↗

To reviewer GsNL

We thank you for taking time and efforts evaluating our submission and appreciate your positive feedback. We found your comments insightful and constructive.

  1. Regarding your question of how to relate the alignment dimension to the VC dimension, it is clear that if (x1,y1(0),y1(1)),…,(xd,yd(0),yd(1))(x_{1}, y_{1}^{(0)}, y_{1}^{(1)}), \ldots, (x_{d}, y_{d}^{(0)}, y_{d}^{(1)}) are alignment shattered by the reward class R\mathcal{R}, then (x1,y1(0)),…,(xd,yd(0))(x_{1}, y_{1}^{(0)}), \ldots, (x_{d}, y_{d}^{(0)}) are VC-shattered by R\mathcal{R}. Hence, the alignment dimension is at most the VC dimension. On the other hand, our Example 1 presents a reward class whose VC dimension is infinity and alignment dimension is zero, suggesting that they can indeed be arbitrarily separated. This is a great catch because basically, the VC dimension captures the complexity of learning absolute reward values while the alignment dimension captures the complexity of learning comparisons. Our theory thus has the following implication — for test-time alignment (such as best-of-N or rejection sampling), it is suboptimal (or might even be incorrect) to first learn (an estimate of) the true reward function from data and then optimize over samplings accordingly (which we call the learn-and-optimize principle in Subsection 3.2). Instead, correct algorithmic principles should try to directly learn comparisons from data.

    While the alignment dimension and the VC dimension of a reward class can have a gap between them, for any reward class, there is an induced partial concept class whose VC dimension is equivalent to the alignment dimension of the original reward class. We state formally at the beginning of Subsection 4.1 that the alignment dimension of a reward class R\mathcal{R} is equivalent to the VC dimension of its induced partial comparison class G(R)\mathcal{G}(\mathcal{R}). Indeed, this equivalence plays an important role in our analysis, allowing us to leverage existing techniques of learning partial concept classes.

  2. Regarding your concern and question about the potential applications to real-world language model alignment, we would say that our work is by nature theoretical, and thus might not have direct guidance to instruct real-world alignment applications. However, standard statistical learning theory (e.g., VC theory for binary classification) has been extensively studied for decades and has greatly facilitated humans' understanding of machine learning. Our work is motivated by the fact that, while there are plenty of works studying language model alignment, the answer to the most fundamental question of learnability, as well as a reasonable PAC learning framework for the problem, are still lacking. Our formulation is general without making strong assumptions, and the techniques are non-trivial. We expect that our work might shed light on developing more rigorous and systematic understandings of the alignment task and advance the improvements of alignment algorithms.

    As mentioned above, one potential message of our work which might have practical relevance is that it is possible to consider reward classes that are hard to learn or even not directly learnable (large or infinite VC dimension), but for which comparisons are learnable (finite alignment dimension). For instance, this could inspire methods such as training a neural network that maps a prompt xx and two responses y(0)y^{(0)} and y(1)y^{(1)} to a preference signal.

AuthorsOpenReview ↗

Continue response to reviewer GsNL

  1. To answer the rest of your questions.
  • How to estimate or bound the alignment dimension for practical reward classes: most reward classes in popular use would be learnable (e.g., linear classifiers or neural networks) so their VC dimension provides a bound on the alignment dimension. Again, what our theory suggests is that it may be worth exploring reward classes beyond these, i.e., potentially non-learnable rewards, while comparisons may still be learnable.

  • Sample complexity dependence on number of candidates: our lower bound improves linearly in the number of candidates while our upper bound degrades naively quadratically (though, of course, we can simply ignore additional candidates beyond the minimal required number O((1/γ)log⁡(1/ϵ))O((1/\gamma)\log(1/\epsilon))). However, this naive quadratic dependence can be improved to linear by a slight refinement of the tournament: for candidates y(1),…,y(k)y^{(1)},\ldots,y^{(k)} with at least one having reward 11, start with "winner" y(1)y^{(1)}, then compare to y(2)y^{(2)}, keep the winner of the pair, then compare the winner to y(3)y^{(3)}, only keep the winner of this, and so on; since a reward 11 will always win against a reward 00, once we've set the winner to a reward 11 candidate yy, we will only ever replace it with another reward 11 candidate, so we end up with a final winner that has reward 11. Resolving the precise optimal sample complexity is left open for future work.

  • Computational cost dependence on the number of candidates: the test-time dependence on the number of candidates is quadratic and can be improved to linear as suggested above. Since the focus of this work is on learnability, without computational considerations (as in the Vapnik-Chervonenkis statistical learning theory), the one-inclusion predictor we consider could have rather large computational complexity, possibly exponential in the alignment dimension. However, there is a literature on more-efficient implementations of the one-inclusion graph algorithm which can be expressed as polynomial-time reductions to an oracle (e.g., an oracle that tests whether a given dataset is realizable by the partial concept class). See [DG24].

    [DG24]: Is efficient PAC learning possible with an oracle that responds 'yes' or 'no'?

We would be happy to discuss and elaborate more if you have more concerns or questions.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.