acceptodds
Under review as a conference paper at ICLR 2027

A Quadratic Lower Bound for Two-Stage Preferential G-Optimal Design

Abstract

In preference learning, G-optimal design, which minimizes the largest prediction variance over candidate responses, guides comparison allocation across prompts and response pairs. We study a two-stage strategy that first optimizes response distributions separately at each prompt, then allocates the prompt budget with those distributions fixed. For this strategy, a quadratic upper bound in the feature dimension was known, but whether prompt allocation could always recover linear scaling remained open. We establish a matching worst-case lower bound, showing that prompt allocation cannot always recover linear scaling. Joint allocation on the same instances attains the optimal linear value. A geometric decomposition explains this gap through within-prompt response concentration and cross-prompt covariance coverage, and yields linear scaling for uniformly comparable prompt covariances. The Bradley–Terry model assigns preference probabilities through a logistic function of response-score differences. With independent response pairs, these instances yield an analogous quadratic-versus-linear separation for uniform within-prompt score estimation at fixed parameter radius and sufficiently small target error.

Primary area:
learning theory
Keywords:
preference learning, optimal experimental design, G-optimal design, two-stage allocation, lower bounds, comparison complexity, Bradley–Terry model

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_Rj8HOpenReview ↗
Rating
2
Confidence
3(+1)
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies a design over the prompts and responses in preference learning. Previous works studies this design separately over the prompts and responses for which a quadratic upper bound in the feature dimension was known. This paper shows that this bound is essentially tight and proposes a joint design over the prompts and responses which attains linear scaling. They consider a signed axis family based coverage where they prove these results.

Critical strengths

This paper demonstrates a clear separation between the separate and joint design over prompts and responses by considering a signed axis family. The authors provide intuition on how the joint design might be useful to attain a tighter upper bound. Efficient algorithms to do joint GG-optimal design might be useful in the broader regime of preference learning.

The results appeared to be technically correct as much as I checked in the main paper. I did not read over the appendices carefully though.

Critical weaknesses

I divide the weakness of the paper into two parts.

Presentation issues

I think the presentation of the paper leaves much to be desired. The paper uses words like "linear scaling" and "signed axis family" in the third paragraph of the first page without defining them or providing any pointer to it. I had to read the entire paper to figure out what they actually meant. A similar problem remains in the abstract too where the authors use the word "quadratic upper bound" but it it is not clear on what this upper bound is on.

Similar clarity issues remain in the introduction section and the diagrams (Figure 1) as well. On the left figure it is quite unclear what the colors actually refer to. Do they refer to the prompt or the responses? If 1,2 and 3 refer to the prompt, then I guess each color refers to a distinct prompt. But it is used for the feature axis too. This makes it quite unclear what it actually means.

While I could probably guess it after reading section 3.3 (signed-axis-family) where the both the responses and prompts share a dimension axis [d], it is quite hard to guess it from the initial introduction section.

Technical points

The authors essentially show that this gap exists on a signed axis construction that they propose, the significance of this result is unclear to me. The motivation for signed axis family including the definition of ϕρ(⋅)\phi_{\rho}(\cdot) is not very clear to me either.

Thus, showing the quadratic vs linear gap on such a family over prompts and responses does not seem very significant to me. The Bradley Terry model considered in section 5 uses this feature ϕρ\phi_{\rho} in equation (10) and showing results on this setting does not answer the previous question either.

It would be interesting to see if such feature modelling is useful by providing the right references or performing experiments on some real preference data.

Additionally computational feasibility is not at all discussed. Computing a joint GG optimal design on prompts and responses might be computationally hard unlike computing a G-optimal design on just one set of features which is known to give an approximation of 2 in polynomial time.

Questions for authors

I would like to see a response to some of the technical points mentioned above in "Critical Weakness" section.

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

This paper studies a two-stage approach for collecting preference data under linear rewards. First, for each prompt, a response-sampling distribution is chosen to be G-optimal. Then, those distributions are frozen and only the prompt marginal is optimized. Kim et al. (2026) showed this costs at most O(d*d) in worst-case leverage.

Authors construct a “signed-axis” family with d prompts. Prompt i has a strong coordinate i and weak access to all others. The unique local optimum is uniform over all 2d signed responses (cause G-optimality is scale invariant), which spends most of the budget on weak directions.

Critical strengths
  • The paper addresses a clear, open question

  • The intuition is clear. Locally balanced designs actually spends too much budget on directions that a prompt is locally weak at, which would have been saved by optimizing over prompts and responses jointly.

Critical weaknesses
  • No evidence the failure mode occurs in realistic settings. The construction needs about d prompts, one strong axis per prompt, weak scale, and signed candidates. Nothing shows that candidate pools from real models and reward-model embeddings come near this regime. (see also the first question below)

  • The candidate response set and its feature geometry are taken as given. The construction picks the feature vectors first and assumes matching responses exist, whereas in practice responses come first.

Questions for authors
  • On a preference dataset (say UltraFeedback), what are the exact two-stage value Q, a joint-design value J, and the local condition numbers? Can we compute these numbers? If yes, can you please report the slope of Q versus d? This would show whether the quadratic regime actually occurs in practice or is only a worst-case boundary.

  • How would the extension to Plackett–Luce look like? Does the separation extend to K-wise rankings under Plackett–Luce? The frozen covariance Σ_x doesn’t depend on K, so I would expect the mechanism to persist, but can you clarify?

  • KL regularization and policy quality. Does the factor-d gap in worst-case leverage translate into a gap in the suboptimality of the KL-regularized policy?

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

This paper studies the lower bound of the two-stage preferential G-optimal design of Kim et al. (2026). In the first stage, the response distribution at each prompt is chosen to be G-optimal. In the second stage, these distributions are frozen and the budget is split across prompts. This paper shows that the sample complexity cannot always be improved to O(d)O(d). It constructs a case in which each prompt sees one coordinate at scale 1 and all other coordinates at scale ρ\rho. The per-prompt optimum is the uniform distribution, and the two-stage value is exactly d2/(1+(d−1)ρ2)d^2/(1+(d-1)\rho^2), which is about d2/2d^2/2 at ρ=d−1/2\rho = d^{-1/2}. On the same features, choosing the prompt weights and the response distributions jointly achieves the optimal value dd. The paper also splits the two-stage value into a within-prompt term and a covariance domination factor, which gives a sufficient condition for linear scaling. Finally, it turns the gap into Ω(d2/ϵ2)\Omega(d^2/\epsilon^2) versus O(d/ϵ2)O(d/\epsilon^2) comparisons under a Bradley–Terry model.

Critical strengths
  • The paper gives an exact and tight answer to a question that Kim et al. explicitly left open, with closed-form values rather than only rates.
  • The results are stated precisely, and full proofs are given in the appendix.
Critical weaknesses
  • The paper has a limited scope. It studies one specific heuristic, and its main result is a worst-case construction for it. Joint allocation is analyzed only as a benchmark on that same construction. Apart from the general lower bound that no design can beat dd, there is no result for joint allocation on other instances and no method for computing it. So the paper points out a problem with the two-stage design but does not offer a general alternative.
  • The paper limits its impact by showing no empirical results, not even a simulation on its own example. A simulation comparing the number of comparisons needed under the two designs on the signed-axis family would help. Evidence from real preference data, for example estimates of the domination factor, would also show whether the bad case happens in practice.
  • The paper is hard to read. It contains many numbered results, each followed by a compressed proof sketch, with little explanation in between. As a result, the main message and key intuition gets buried. Important caveats such as Proposition 15 are left to the appendix, and there is no discussion of limitations. At the sentence level, the text is dense and sentences often do not connect. For example, the abstract inserts "The Bradley–Terry model assigns preference probabilities through a logistic function of response-score differences" between two results.
Questions for authors

Is there any evidence, empirical or theoretical, that per-prompt covariances in realistic preference data are lopsided and misaligned in the way the signed-axis family requires? And for real data, what is the range of the lopsided level?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.