Model Compression with Exact Budget Constraints via Riemannian Manifolds

Michael HelcigETH ZürichDan AlistarhIST Austria · 2026

Read Model Compression with Exact Budget Constraints via Riemannian Manifolds by Michael HelcigETH ZürichDan AlistarhIST Austria (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-00649.txt.

Introduction

Michael Helcig and Dan Alistarh solve a recurring allocation problem in efficient AI: assign one of several options to each of many groups, under one exact budget. Mixed-precision quantization, pruning, and expert selection all take this shape. The objective depends on all assignments jointly, so combinatorial solvers chase proxies, evolutionary search has no gradients, and penalty methods enforce the budget approximately, after heavy tuning.

Their insight is geometric. Under a softmax relaxation, the budget constraint carves out a Riemannian manifold in the model's logit space, with clean structure. The normal direction is known in closed form. Moving along the cost vector changes expected cost monotonically. Their algorithm wraps projection, retraction, and momentum transport around a standard optimizer step. It optimizes the loss, holds the budget exactly at every step, and adds no constraint hyperparameters. On synthetic and compression tasks it matched or beat leading methods, often faster.

Catalog record

CREATORMichael HelcigETH ZürichDan AlistarhIST Austria
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE90 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.00649

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Model Compression with Exact Budget Constraints via Riemannian Manifolds Michael HelcigETH ZürichDan AlistarhIST Austria Abstract Assigning one of K K options to each of N N groups under a total cost budget is a recurring problem in efficient AI, for instance in mixed-precision quantization, non-uniform pruning, and expert selection. The objective (model loss) depends on all assignments jointly and does not decompose across groups, which means that combinatorial solvers can only optimize proxy objectives. Methods such as evolutionary search evaluates the actual loss but lack gradients, while penalty-based methods enforce the budget only approximately and can require heavy hyperparameter tuning. We present a new approach to this problem by showing that under softmax relaxation, the budget constraint defines a smooth Riemannian manifold in logit space with unusually clean geometry. Specifically, the normal vector is available in closed form, shifting logits along the cost vector changes expected cost monotonically, and the vector transport reduces to a single inner product. Building on this, we propose Riemannian Constrained Optimization (RCO), which wraps tangent projection, binary-search retraction, and momentum transport around a standard Adam step. Combined with Gumbel straight-through estimation and budget-constrained dynamic programming for discrete feasibility, RCO provides first-order optimization of the actual loss under exact budget enforcement, with no constraint-related hyperparameters. RCO exceeds or matches the performance of state-of-the-art methods in both synthetic problems and realistic LLM compression settings, often at considerably lower wall-clock cost. Source code is available at https://github.com/IST-DASLab/RCO . † † footnotetext: Corresponding author: [email protected] 1 Introduction Constrained optimization over discrete choices is a pervasive problem in efficient machine learning. A common instance is budget-constrained discrete assignment : choose one of K options for each of N target groups (e.g., a compression level for each layer of a neural network), minimizing an objective that depends on all assignments jointly (the model accuracy loss), subject to a total cost constraint (the total model size). The joint dependence between groups, e.g., the interactions between layers, makes the objective non-decomposable, so it cannot simply be written as a sum of per-group terms. Dynamic programming (DP), the standard tool for budget-constrained assignment, relies precisely on this additive structure, and can therefore only optimize proxy objectives. Concretely, variants of this problem have been used in model compression where each layer or Transformer block can be assigned a different compression degree while minimizing model loss, e.g., for mixed-precision quantization ( Dong et al. 2019 ; Dong et al. 2020 ; Yao et al. 2021 ) , non-uniform pruning ( Frantar and Alistarh 2022 ; Yin et al. 2024 ) , MoE expert pruning ( Lu et al. 2024 ; Lasby et al. 2025 ; Liu et al. 2026 ) , and even MoE routing under load-balancing constraints ( Fedus et al. 2021 ; Zhou et al. 2022 ) . Figure 1 : Recovery vs. baselines across experiments: RCO matches or exceeds every baseline at lower wall-clock. Above each bar: recovery (%, bold) and wall-clock time (small). Sensitivity methods address the non-decomposability by scoring groups independently, giving each layer a “sensitivity” and finding a suitable allocation via dynamic programming or integer linear programming ( Dong et al. 2019 ; Dong et al. 2020 ; Yao et al. 2021 ; Yin et al. 2024 ; Frantar and Alistarh 2022 ; Li et al. 2023 ; Malinovskii et al. 2025 ; Duanmu et al. 2025 ) . However, sensitivity-aware allocation was shown to fail at high compression rates by Sieberling et al. 2025 . Directly evaluating the actual model loss under compression combinations avoids this, but existing methods require hundreds of forward passes to converge ( Sieberling et al. 2025 ; Liu et al. 2026 ) . Gradient-based search through continuous relaxation could be more efficient, but the standard approach ( Cai et al. 2019 ; Wu et al. 2019 ; Huang et al. 2022 ) adds a quadratic penalty \lambda\,(C(\boldsymbol{\alpha})-B)^{2} on the deviation between the total expected cost C(\boldsymbol{\alpha}) and the budget B . This never satisfies the budget exactly, and the penalty coefficient \lambda needs to be carefully tuned: too small and the budget is violated, too large and the constraint gradient dominates. On hard instances, as we show in Section 4.1 , Lagrangian methods oscillate. Projection-free methods such as Frank-Wolfe maintain feasibility by construction ( Nayman et al. 2021 ) but do not transport adaptive optimizer state. We parameterize each group’s compression assignment by logits \boldsymbol{\alpha}_{i}\in\mathbb{R}^{K} with softmax probabilities \mathbf{p}_{i}=\softmax(\boldsymbol{\alpha}_{i}) , and let \mathbf{c}=(c_{1},\ldots,c_{K})\in\mathbb{R}^{K} collect the option costs and w_{i} the weight of group i . The total expected cost is C(\boldsymbol{\alpha})=\sum_{i}w_{i}\langle\mathbf{p}_{i},\mathbf{c}\rangle , a smooth function of the concatenated logits \boldsymbol{\alpha}\in\mathbb{R}^{NK} . Given a calibration loss L and a budget B , the problem is \min_{\boldsymbol{\alpha}}L(\boldsymbol{\alpha}) subject to C(\boldsymbol{\alpha})=B . The logits \boldsymbol{\alpha} are the optimization variables; \mathbf{c} , w_{i} , and B are fixed inputs. The feasible set \mathcal{M}=\{C(\boldsymbol{\alpha})=B\} has well-behaved geometric structure. The gradient \nabla C is everywhere nonzero when options have distinct costs, so by the regular value theorem ( Boumal 2023 , Theorem 3.2) \mathcal{M} is a smooth (NK{-}1) -dimensional Riemannian submanifold of \mathbb{R}^{NK} . We call this the budget manifold ; one can optimize directly on it, projecting gradients onto its tangent plane (the subspace of budget-preserving directions) and retracting (projecting back) onto its surface after each step, enforcing the budget exactly at every iterate. The efficiently-accessible geometry of \mathcal{M} rests on the softmax parameterization: • Closed-form normal. The constraint gradient is (\nabla C)_{ik}=w_{i}\,p_{ik}(c_{k}-\mathbb{E}_{p_{i}}[c]) (Eq. 2 ); projecting onto the tangent plane costs a single inner product. • Monotonic retraction. Shifting logits along \mathbf{c} changes C monotonically with derivative \sum_{i}w_{i}\,\Var_{p_{i}}[c]>0 (Proposition 3 ); binary search therefore returns any iterate to \mathcal{M} exponentially fast. • Cheap transport. Since \mathcal{M} has codimension one, vector transport (adjusting the optimizer’s momentum to the new tangent plane) is another inner product. The resulting algorithm wraps these three operations around a standard Adam step, giving first-order optimization of the end-to-end loss under exact budget enforcement at negligible overhead. Contributions. In summary, we introduce the following main contributions: • The budget manifold (Section 2 ). The level set \{C(\boldsymbol{\alpha})=B\} is a classical m-flat submanifold; under the Euclidean (rather than Fisher) ambient metric it has closed-form normals, monotonic retraction (Proposition 3 ), and single-inner-product transport. • Riemannian Constrained Optimization (RCO) (Section 3 ). We wrap projection, retraction, and transport around Adam with no constraint-related hyperparameters. Gumbel-STE with budget-constrained DP handles discrete forward-pass feasibility; the manifold handles continuous backward-pass feasibility. • Constraint robustness under biased gradients (Section 3 , Appendix A.6 ). Tangent projection eliminates the constraint-normal component of any STE gradient bias (Proposition 6 ), so the budget is enforced exactly regardless of gradient quality. • Empirical validation (Section 4 ). On synthetic knapsack ( N{=}1000 , K{=}32 ), RCO reaches 1% of the DP optimum where vanilla Lagrangian plateaus at 37.6%; on LLM compression, RCO matches or exceeds evolutionary search at 3–16 \times lower wall-clock. 2 The Budget Manifold We briefly review the relevant concepts from Riemannian geometry; for a textbook treatment, see Boumal 2023 . A manifold is a smooth surface that may be curved globally but locally resembles flat Euclidean space. A Riemannian manifold additionally carries an inner product on each tangent space, providing notions

Read the complete text