Quantizing With Randomized Hadamard Transforms: Efficient Heuristic Now Proven

• URL: http://arxiv.org/abs/2605.06014v1
• Date: Thu, 07 May 2026 11:11:54 GMT
• Title: Quantizing With Randomized Hadamard Transforms: Efficient Heuristic Now Proven
• Abstract summary: Uniform random rotations (URRs) are a common preprocessing step in modern quantization approaches.<n>In practice, URRs are often replaced by randomized Hadamard transforms (RHTs)<n>We show that two RHTs achieve performance thatally matches URRs, but two RHTs may not be sufficient for Vector Quantization (VQ)<n>We propose a linear-time $O(d)$ check on the input's moments to dynamically adapt the number of RHTs used at runtime to improve performance.
• Score: 16.408056537803308
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Uniform random rotations (URRs) are a common preprocessing step in modern quantization approaches used for gradient compression, inference acceleration, KV-cache compression, model weight quantization, and approximate nearest-neighbor search in vector databases. In practice, URRs are often replaced by randomized Hadamard transforms (RHTs), which preserve orthogonality while admitting fast implementations. The remaining issue is the performance for worst-case inputs. With a URR, each coordinate is individually distributed as a shifted beta distribution, which converges to a Gaussian distribution in high dimensions. Generally, one RHT is not suitable in the worst case, as individual coordinates can be far from these distributions. We show that after composing two RHTs on any $d$-sized input vector, the marginal distribution of every fixed coordinate of the normalized rotated vector is within $O(d^{-1/2})$ of a standard Gaussian both in Kolmogorov distance and in $1$-Wasserstein distance. We then plug these bounds into the analyses of modern compression schemes, namely DRIVE and QUIC-FL, and show that two RHTs achieve performance that asymptotically matches URRs. However, we show that two RHTs may not be sufficient for Vector Quantization (VQ), which often requires weak correlation across fixed-size blocks of coordinates (as opposed to only marginal distribution convergence for single coordinates). We prove that a composition of three RHTs leads to decaying coordinate covariance. This ensures that any fixed, bounded, multi-dimensional VQ codebook optimized for URRs has the same expected error when using three RHTs, up to an additive term that vanishes with the dimension. Finally, because practical inputs are rarely adversarial, we propose a linear-time ${O}(d)$ check on the input's moments to dynamically adapt the number of RHTs used at runtime to improve performance.

Related papers

• LC-GRPO: Bridging Train-Inference Gap for Flow-Based GRPO with Langevin Correction [59.32834240526981]
  Flow-based generative models are typically sampled by solving a deterministic ordinary differential equation (ODE)<n>Existing GRPO methods for flow models replace the Euler-time ODE with aotropic differential equation (SDE) during training.<n>We introduce LC-GRPO, a flow-based GRPO framework with Langevin correction targeting the marginal distribution at the resulting timestep.
  arXiv  Detail & Related papers  (2026-08-06T04:47:57Z)
• The Value of Covariance Matching in Gaussian DDPMs and the Lanczos Sampler [4.538165276831438]
  A central error measure in Gaussian DDPMs is the path-space KL divergence between the exact reverse chain and the learned Gaussian reverse process.<n>We show that matching the full posterior covariance breaks this barrier, yielding an order-wise improvement that reduces the path KL to $O(1/T2)$.<n>We prove that LGS approximation error decays exponentially in the number of Lanczos steps, where each Lanczos step requires a single Jacobian-vector product.
  arXiv  Detail & Related papers  (2026-05-21T16:57:27Z)
• Approximating Uniform Random Rotations by Two-Block Structured Hadamard Rotations in High Dimensions [0.8307668828380427]
  Uniform random rotations are a useful primitive in applications such as fast Johnson-Lindenstrauss embeddings, kernel approximation, communication-efficient learning, and recent AI compression pipelines.<n>A common practical replacement is repeated structured random rotations built from Walsh-Hadamard transforms and random signs.<n>Applying the structured random rotation twice has been shown empirically to be useful, but the supporting theory is still limited.
  arXiv  Detail & Related papers  (2026-04-25T19:22:42Z)
• Analysis of Nystrom method with sequential ridge leverage scores [69.32538992633842]
  Large-scale kernel ridge regression (KRR) is limited by the need to store a large kernel matrix K_t.<n>Recent works show that a sampling distribution proportional to the ridge leverage scores (RLSs) provides strong reconstruction guarantees for the approximation.<n>We introduce the INK-ESTIMATE algorithm, that incrementally computes the RLSs estimates.
  arXiv  Detail & Related papers  (2026-04-22T00:49:25Z)
• Test-Time Scaling with Diffusion Language Models via Reward-Guided Stitching [66.39914384073145]
  We propose a self-consistency framework that turns cheap diffusion-sampled reasoning into a reusable pool of step-level candidates.<n>We find that step-level recombination is most beneficial on harder problems.<n>Our training-free framework improves average accuracy by up to 2 across six math and coding tasks.
  arXiv  Detail & Related papers  (2026-02-26T11:08:39Z)
• VAE with Hyperspherical Coordinates: Improving Anomaly Detection from Hypervolume-Compressed Latent Space [56.362776482614976]
  Variational autoencoders (VAE) encode data into lower-dimensional latent vectors before decoding those vectors back to data.<n>We propose to formulate the latent variables of a VAE using hyperspherical coordinates, which allows compressing the latent vectors towards a given direction on the hypersphere.<n>We show that this improves both the fully unsupervised and OOD anomaly detection ability of the VAE, achieving the best performance on the datasets we considered.
  arXiv  Detail & Related papers  (2026-01-25T03:10:24Z)
• Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
  We propose two variance reduced ZO estimators for complex gradient problems. We improve the state-of-the-art function complexities from $mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$ to $tildecalOleft(fracdepsilon2right)$.
  arXiv  Detail & Related papers  (2024-10-03T15:04:01Z)
• Reverse Transition Kernel: A Flexible Framework to Accelerate Diffusion Inference [29.589117191576875]
  DDPM uses a Gaussian approximation for the RTK, resulting in low per-subproblem complexity but requiring a large number of segments. We develop a general RTK framework that enables a more balanced subproblem decomposition, resulting in $tilde O(1)$ subproblems. We then propose leveraging two fast sampling algorithms, the Metropolis-Adjusted Langevin Algorithm (MALA) and Underdamped Langevin Dynamics (ULD) for solving these strongly log-concave subproblems.
  arXiv  Detail & Related papers  (2024-05-26T00:26:57Z)
• Distributed Extra-gradient with Optimal Complexity and Communication Guarantees [60.571030754252824]
  We consider monotone variational inequality (VI) problems in multi-GPU settings where multiple processors/workers/clients have access to local dual vectors. Extra-gradient, which is a de facto algorithm for monotone VI problems, has not been designed to be communication-efficient. We propose a quantized generalized extra-gradient (Q-GenX), which is an unbiased and adaptive compression method tailored to solve VIs.
  arXiv  Detail & Related papers  (2023-08-17T21:15:04Z)
• Adaptive Annealed Importance Sampling with Constant Rate Progress [68.8204255655161]
  Annealed Importance Sampling (AIS) synthesizes weighted samples from an intractable distribution. We propose the Constant Rate AIS algorithm and its efficient implementation for $alpha$-divergences.
  arXiv  Detail & Related papers  (2023-06-27T08:15:28Z)
• Distributed Random Reshuffling over Networks [7.013052033764372]
  A distributed resh-upr (D-RR) algorithm is proposed to solve the problem of convex and smooth objective functions. In particular, for smooth convex objective functions, D-RR achieves D-T convergence rate (where $T counts epoch number) in terms of distance between the global drives.
  arXiv  Detail & Related papers  (2021-12-31T03:59:37Z)
• Variance reduction for Random Coordinate Descent-Langevin Monte Carlo [7.464874233755718]
  Langevin Monte Carlo (LMC) that provides fast convergence requires computation of gradient approximations. In practice one uses finite-differencing approximations as surrogates, and the method is expensive in high-dimensions. We introduce a new variance reduction approach, termed Coordinates Averaging Descent (RCAD), and incorporate it with both overdamped and underdamped LMC.
  arXiv  Detail & Related papers  (2020-06-10T21:08:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.