I3S: Importance Sampling Subspace Selection for Low-Rank Optimization in LLM Pretraining

Haochen Zhang, Junze Yin, Guanchu Wang, Zirui Liu, Tianyi Zhang, Anshumali Shrivastava, Lin Yang, Vladimir Braverman

Abstract

Training Large Language Models (LLMs) is constrained by massive memory requirements, primarily from optimizer states. Low-rank optimization methods like GaLore mitigate this by projecting gradients into a low-rank subspace. However, these methods often suffer from a "frozen subspace" phenomenon where the dominant subspace stabilizes prematurely, limiting model expressivity. We present SARA (Importance SAmpling for Low-RAnk optimization), a novel subspace selection technique that employs importance sampling to promote exploration of non-dominant gradient directions. SARA significantly reduces subspace overlap, closing the performance gap between memory-efficient and full-rank training by up to 46% across various model scales and optimizer variants.

Introduction

The memory footprint of training state-of-the-art LLMs is a major bottleneck. While the model parameters themselves are large, a significant portion of GPU memory is consumed by optimizer states, such as the moving averages in Adam. Low-rank optimization techniques, notably GaLore, address this by projecting gradients into a smaller subspace, thereby reducing the memory needed for optimizer states.

A critical limitation of current low-rank methods is their reliance on the "dominant subspace"—the directions corresponding to the largest singular values of the gradient. Empirical evidence suggests that these dominant subspaces quickly "freeze" during pretraining, leading to redundant updates and a narrow optimization trajectory. This restriction prevents the model from learning complex patterns, resulting in a performance gap compared to standard full-rank training.

Methodology: SARA

To overcome the frozen subspace bottleneck, we propose SARA, a "plug-and-play" replacement for deterministic subspace selection. Instead of always picking the top $r$ singular vectors, SARA utilizes importance sampling.

Importance Sampling Subspace Selection

SARA considers a larger set of $m$ singular vectors and samples $r$ of them with a probability proportional to their corresponding singular values. This stochastic approach offers several advantages:

  1. Information Preservation: Weighting by singular values ensures that the most significant gradient directions are still prioritized.
  2. Enhanced Exploration: The introduction of randomness allows the optimizer to explore "non-dominant" but relevant directions, preventing the update trajectory from becoming trapped in a frozen subspace.
  3. Computational Efficiency: The sampling overhead is negligible as it leverages the Singular Value Decomposition (SVD) already performed by low-rank optimizers.

Furthermore, SARA provides a provable convergence guarantee, offering a theoretical foundation that deterministic dominant subspace selection lacks.

Experimental Results

We evaluated SARA by pretraining LLaMA models ranging from 60M to 1.1B parameters on the C4 and SlimPajama datasets.

Performance Gains

SARA consistently outperformed existing low-rank methods. In LLaMA-130M pretraining, SARA reduced the validation perplexity (PPL) gap between low-rank and full-rank Adam by 46.05%. These benefits were robust across different optimizer variants, including Adafactor, Adam-mini, and 8-bit quantized optimizers.

SARA consistently reduces validation perplexity across different model sizes and optimizer variants compared to standard GaLore.

Subspace Dynamics

A key insight into SARA's success is its ability to maintain diversity in weight updates. By sampling different subspaces, SARA produces cumulative updates that are effectively higher-rank than those from dominant subspace methods. This is reflected in the significantly lower overlap between subspaces used in consecutive training steps.

SARA (blue) maintains much lower overlap between adjacent and anchor subspaces compared to the dominant subspace approach (orange), enabling better exploration of the optimization landscape.

Discussion and Conclusion

SARA demonstrates that "dominant" is not always optimal for long-term optimization. By prioritizing diversity through importance sampling, SARA enables low-rank optimizers to achieve performance levels much closer to full-rank training while maintaining memory efficiency.

While highly effective for LLM pretraining, future work could explore SARA's applicability to other domains such as fine-tuning or reinforcement learning. Additionally, investigating the optimal balance between the sampling pool size ($m$) and rank ($r$) for different architectures remains an open area for research. In conclusion, SARA provides a robust, theoretically grounded, and efficient solution for scaling LLM training under memory constraints.

Summary updated

Abstract

Low-rank optimization has emerged as a promising approach to enabling memory-efficient training of large language models (LLMs). Existing low-rank optimization methods typically project gradients onto a low-rank subspace, reducing the memory cost of storing optimizer states. A key challenge in these methods is identifying suitable subspaces to ensure an effective optimization trajectory. Most existing approaches select the dominant subspace to preserve gradient information, as this intuitively provides the best approximation. However, we find that in practice, the dominant subspace stops changing during pretraining, thereby constraining weight updates to similar subspaces. In this paper, we propose importance sampling subspace selection (I3S) for low-rank optimization, which theoretically offers a comparable convergence rate to the dominant subspace approach. Empirically, we demonstrate that I3S significantly outperforms previous methods in LLM pretraining tasks.
BibTeX
@inproceedings{zhang2025i,
  author = {Haochen Zhang and Junze Yin and Guanchu Wang and Zirui Liu and Tianyi Zhang and Anshumali Shrivastava and Lin Yang and Vladimir Braverman},
  title = {{I3S: Importance Sampling Subspace Selection for Low-Rank Optimization in LLM Pretraining}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2025},
  url = {https://openreview.net/forum?id=ZdmmOAN4h3},
}
Figure