acceptodds
Under review as a conference paper at ICLR 2027

Directions That Matter: Efficient Online RLHF via Preference Geometry Sketching

Abstract

Online Reinforcement Learning from Human Feedback (RLHF) enables models to continually collect preference feedback and refine their reward models during interaction. However, scaling existing online RLHF methods to large language models (LLMs) remains computationally challenging. Their one-pass estimators rely on high-dimensional local curvature to preserve statistical efficiency, leading to substantial computation and memory costs that grow at least quadratically with the feature dimension. We address this challenge by proposing a geometry-sketched reward modeling framework that reduces the dependence on the feature dimension to linear. The key idea is to approximate the geometry of accumulated preference data using matrix sketching: we retain the dominant directions of preference geometry without explicitly maintaining the full curvature matrices. We establish theoretical efficiency–utility trade-offs for representative online RLHF settings with different data-collection strategies and forms of comparison feedback. Extensive experiments show that our method provides an effective efficiency–utility trade-off, consistently improves over existing approximation baselines, and scales to larger LLMs with limited additional computational overhead.

Primary area:
reinforcement learning
Keywords:
Reinforcement Learning from Human Feedback, Preference Learning, Matrix Sketching

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_F8NmOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper introduces GeoSRM, an efficient online reward modeling method that uses Frequent Directions to compress historical preference curvature while retaining exact corrections for the current round. It establishes estimation, suboptimality, and regret guarantees that explicitly incorporate sketching error. Experiments validate the effectiveness of the proposed method.

Critical strengths
  1. The paper addresses an important computational bottleneck in scaling online RLHF: maintaining and operating on high-dimensional preference curvature. The proposed geometry-sketching method substantially reduces these costs while retaining useful directional information, making the contribution practically relevant.
  2. The analysis explicitly characterizes how sketching affects estimation accuracy and policy performance. Experiments in both active preference optimization and deployment-time adaptation demonstrate favorable efficiency–utility trade-offs, including approximately fivefold algorithm-time savings in the 7B active-learning setting. Together, these results support the method’s soundness and practical effectiveness.
Critical weaknesses
  1. The (O(\ell d)) cost is linear in (d) only when the sketch size (\ell) is fixed. However, the main experiments use (\ell=d/4), making this cost quadratic in (d). The results therefore demonstrate computational savings but do not establish that dimension-linear scaling preserves utility. Experiments with a fixed sketch budget across feature dimensions would strengthen this central claim.
  2. The deployment regret guarantee relies on uncertainty-aware response selection, whereas experiments select the highest- and fourth-highest-scoring responses from 64 samples. This substitution leaves the analyzed exploration mechanism empirically unvalidated and weakens the connection between the theoretical guarantees and reported deployment performance.
Questions for authors
  1. Since the main experiments use (\ell=d/4), under what spectral conditions can (\ell) remain independent of (d) while preserving statistical efficiency? What theoretical or empirical evidence supports these conditions in the evaluated settings?
  2. Does the deployment regret guarantee extend to the experimental rule that selects the highest- and fourth-highest-scoring responses from 64 samples? If not, what justification or existing evidence connects this heuristic to the uncertainty-aware selection rule analyzed in the theorem?
Reviewer_82yiOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

In this paper, the authors focus on online RLHF with one-pass reward estimators, and in particular on the high cost of the OMD estimators used in existing methods, which need to maintain the full curvature matrix of the feature space and therefore scale at least quadratically with the feature dimension. To address this problem, the authors propose GeoSRM, which approximates the curvature accumulated in previous rounds with an FD sketch, while keeping the curvature of the current round exactly. In this way, the per-round cost becomes linear in the feature dimension for a fixed sketch size, and the statistical guarantees still hold, with the feature dimension replaced by the sketch size plus a term that depends on the spectral tail. Experiments on active preference optimization and deployment-time adaptation show that GeoSRM achieves comparable or better results than the baselines while requiring less computation time.

Critical strengths
  1. In this paper, the authors improve the efficiency of online RLHF while keeping its theoretical guarantees. Existing implementations either maintain the full curvature matrix, which is costly for LLM features, or rely on heuristic approximations whose effect on the statistical guarantees is not characterized. The authors reduce the cost to linear in the feature dimension for a fixed sketch size, and explicitly show how the sketching error enters the estimation error and the final bounds. This makes theoretically grounded online RLHF methods more applicable to LLMs.

  2. The authors present a clear motivation. The authors state the time and memory costs of existing one-pass estimators and relate them to the feature dimensions of commonly used LLMs, so readers can directly see why these methods are hard to scale. The authors then explain the key design of the method in a simple way: only the curvature from previous rounds is sketched, while the curvature of the current round is kept exactly, and the two parts are clearly marked in the equation. This makes the difference from standard covariance sketching easy to understand.

  3. The authors provide good visualizations. Figure 1 compares the approximation error of the sketch with that of the isotropic approximation used in prior work, Figure 2 shows the overall framework, and Figure 3 shows the spectral concentration of the curvature on real LLM features. These figures connect the motivation, the method and the experiments, which makes the paper easy to catch up on.

Critical weaknesses
  1. The gap between the theoretical setting and the experimental implementation is not explained in the main text. The step size and the regularization parameter used in the experiments are much smaller than those required by Lemma 1. In the deployment experiments, the second response is selected by rejection sampling rather than by the optimistic rule in Eq. (10), and in the active experiments the query is selected within a small minibatch of prompts rather than over the whole context set as in Eq. (9). These differences are only given in the appendix. The authors may consider stating them in the main text and discussing how the theoretical results relate to the implemented algorithms.

  2. Some details of the evaluation protocol appear only in the appendix and affect how the results should be read. The evaluation uses the same prompt pool as the query selection, so the reported accuracy does not measure performance on unseen prompts. In addition, the accuracy only compares the highest-ranked and the lowest-ranked retained responses, so experiments with different maximum assortment sizes are evaluated on tasks of different difficulty. The authors may consider stating these details in the main text and, if possible, reporting results on a separate test set or on a fixed set of response pairs.

  3. The attribution of the speed-up is not consistent between the main text and the appendix. The main text attributes the larger time reduction on the 7B model to the sketched curvature operations, while the appendix notes that the 7B runs use smaller assortments and therefore perform fewer updates. In addition, the abstract emphasizes the reduction of memory cost, but no memory measurement is reported. The authors may consider separating the two sources of the speed-up, for example by reporting the time per update, and adding measurements of memory usage.

Questions for authors
  1. The bounds replace the feature dimension with the sketch size plus a term that depends on the spectral tail. Since this term is not scale-free and may grow with the number of rounds, could the authors explain under what conditions it is smaller than the feature dimension, and report its measured value in the experiments?

  2. Since the evaluation uses the same prompt pool as the query selection and the accuracy depends on the assortment size, could the authors report the accuracy on a separate test set or on fixed response pairs, and explain whether the differences between GeoSRM-A and M-AUPO and the effect of the assortment size still hold?

  3. Could the authors report the average assortment size and the number of comparisons per round for GeoSRM-A and M-AUPO on the 7B model, together with the time per update and the measured memory usage, so that the speed-up from sketching can be separated from the effect of fewer updates?

Reviewer_kQiaOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper tackles an interesting problem : reducing the dimensionality of optimization for online learning from preferences. The authors introduce GeoSRM a method that takes insipiration from matrix sketching a technique from online learning that uses the online preference data to construct the local curvature of optimization and then preserves the dominant directions only. First, the authors show that in reward modelling, singular vectors of the curvature matrix are covered largely by the first few singular vectors, motivating the dimensionality reduction. Then, they show across two settings: active preference learning and test-time adaptation that using the low dimensional updates speeds up the reward model learning with slight improvements to final performance. The authors test the method across different model sizes, and present ablation over different settings of preference learning. Overall, the idea is pretty interesting and intuitive but the results show very limited improvement in the test-time adaptation setting.

Critical strengths
  • The paper introduces a very interesting problem in RLHF and presents a very grounded and intuitive solution to the problem.
  • The authors show that the framework under two setups: learning rewards online during deployment and another setup where the model actively queries users for preference feedback.
  • The authors conduct experiments across different model sizes and parameter configurations to demonstrate their method.
  • The authors include clear and detailed theoretical proofs and explanation of the overall method.
Critical weaknesses
  • The paper has very limited baselines. An important set of baselines are in the zeroth order optimization setting, where the optimization is O(d) complexity [1]. Additionally, prior work has also tried learning low rank reward models by using basis functions [2]. Comparison or discussion to these baselines would help make the contribution stronger.
  • The current results show a weak improvement over baselines in the test-time deployment setting. The only strong result is over the reduction in the time to reach a certain accuracy in the active learning setting. However, the paper lacks details about the metric and how is it calculated? Is the reduction achieved because of low dimensional optimization requiring less FLOPs or does it also require less number of learning samples?
  • There are no statistical bars across results and plots so it is hard to understand the significance of improvements. Are the experiments done across multiple seeds?

[1] Fine-Tuning Language Models with Just Forward Passes, Malladi et al. [2] LoRe: Personalizing LLMs via Low-Rank Reward Modeling, Bose et al.

Questions for authors

see weaknesses.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.