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

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.