- 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
- 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 on an unseen prompt. For , consider
Questions for authors
- Clarification of the lower bound in Example 3. How do the authors reconcile the classification-error lower bound on page 6, lines 275–277, with the following counterexample? For , let
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 1 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 γ and get the error guarantee at those prompts where πref has a correct probability of at least γ by O((1/γ)log(1/ϵ)) 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.