Technical Summary: HARP (Hadamard-Preconditioned Adaptive Rotation Processor)

1. Problem Statement

Post-training quantization (PTQ) is critical for deploying Large Language Models (LLMs) under memory and bandwidth constraints. However, extreme low-bit quantization (2–4 bits) faces two primary challenges:

1. Activation Outliers and Heavy-Tailed Statistics: A small subset of coordinates carries disproportionate weight mass and curvature sensitivity, causing severe reconstruction errors when quantized.
2. Anisotropic Weight Curvature: Standard quantizers (scalar or block-wise vector) perform poorly when weight mass or curvature-sensitive directions align with specific coordinate axes.

Existing solutions rely on Incoherence Processing, which applies a structured orthogonal change of basis before quantization to spread weight mass across coordinates. The current standard is the Randomized Hadamard Transform (RHT). While RHT is fast ($O(d \log d)$) and exactly orthogonal, it is fixed. It does not adapt to:

• Specific layer statistics.
• The calibration data distribution.
• The block structure of the downstream quantizer.

Recent work suggests that learning rotations end-to-end improves quality, but these methods often relax the "drop-in" nature of PTQ pipelines, alter the full-precision model, or introduce computational costs too high for inference. There is a gap for a processor that is learnable from calibration data, remains an exact orthogonal change of basis (preserving the full-precision model), and maintains Hadamard-like efficiency.

2. Methodology: HARP

The authors propose HARP (Hadamard-Preconditioned Adaptive Rotation Processor), a learnable, two-sided orthogonal processor designed to replace fixed RHT in PTQ pipelines.

2.1 Core Architecture

HARP parameterizes the orthogonal rotation as a product of sparse, stride-based stages, mimicking the structure of fast Hadamard and butterfly transforms.

• Structure: For a dimension $d$, HARP uses a Mixed-Radix schedule $\mathbf{b} = (b_0, \dots, b_{m-1})$ where $\prod b_t = d$.
• Stages: Each stage $t$ applies a block-diagonal orthogonal matrix $\mathbf{B}_t$ to groups of coordinates, separated by stride permutations.
• Mixed-Radix Support: Unlike standard Hadamard transforms limited to powers of two, HARP supports arbitrary dimensions (e.g., 5120) using a Mixed-Radix schedule (e.g., $8, 8, 8, 5, 2$). Non-power-of-two radices utilize a deterministic orthogonal fallback (QR factorization of a fixed Gaussian matrix).

2.2 Hadamard Preconditioning & Initialization

A key innovation is the Hadamard-preconditioned block kernels. Each learnable block $B_{t,c}$ is defined as:
$$B_{t,c}(\theta) = Q_{t,c}(\theta) G_{b_t}$$

• $G_{b_t}$ is a fixed base mixer (Normalized Sylvester Hadamard for power-of-two, QR fallback otherwise).
• $Q_{t,c}(\theta)$ is a learnable orthogonal matrix (Givens rotation for $b_t=2$, Cayley map for $b_t > 2$).

Initialization: All learnable parameters $\Theta$ are initialized to zero. At $\Theta=0$, $Q_{t,c}(0) = I$, meaning $B_{t,c}(0) = G_{b_t}$. Consequently, the HARP transform exactly recovers the fixed RHT processor (up to a fixed permutation convention) at initialization. Calibration then learns a structured orthogonal refinement around this strong baseline.

2.3 Optimization Objective

HARP is fitted per layer using only calibration data. The optimization minimizes a surrogate loss aligned with the deployed blockwise quantizer:

1. Diagonal Hessian-Weighted Reconstruction: Minimizes the error between the rotated weight and its blockwise codebook target, weighted by the diagonal of the Hessian proxy. Gradients are stopped through the discrete codebook assignment to ensure stability.
2. Off-Block Hessian Energy Penalty: A regularization term ($R_{bd}$) penalizes energy in off-diagonal blocks of the Hessian proxy, encouraging the rotation to align curvature with the quantizer's block structure.

The total loss is:
$$\mathcal{L}_{fit}(\Theta) = \mathcal{L}_{diag}(\Theta) + \lambda_{bd} R_{bd}(\Theta_V)$$

2.4 Deployment Efficiency

• Storage: HARP parameters can be stored in int8 format with minimal impact on perplexity.
• Compute: The application cost is $O(d \log d)$, similar to RHT. The authors implement fused Triton GPU kernels for stride stages to avoid materialized permutations, keeping latency overhead low.
• Compatibility: HARP is a drop-in replacement for the preprocessing step in QuIP# and QTIP pipelines, requiring no changes to the quantizer backend or solver.

3. Key Contributions

1. Learnable Incoherence Processor: Introduction of HARP, a two-sided orthogonal processor fitted via calibration data that adapts to layer statistics and backend quantizer structures.
2. Drop-in Compatibility: HARP initializes exactly to the fixed RHT processor, ensuring it is a seamless upgrade for existing Hadamard-based PTQ pipelines without requiring full model retraining or graph rewiring.
3. Structured Efficiency: Utilization of Mixed-Radix butterfly-like stages allows for exact orthogonality and $O(d \log d)$ complexity on non-power-of-two dimensions, preserving the throughput advantages of quantized inference.
4. Empirical Validation: Demonstration of consistent quality gains (perplexity and zero-shot accuracy) over fixed RHT across 2–4 bit settings on models ranging from 1B to 70B parameters.

4. Experimental Results

The authors evaluated HARP on Llama 3.2 (1B, 3B) and Llama 2 (7B, 13B, 70B) using the QuIP# backend.

• Perplexity (PPL): HARP consistently outperforms fixed RHT.
  • 2-bit: The gains are most significant here, where quantization is most sensitive. For Llama 2 7B, HARP reduces WikiText2 PPL from 8.22 (RHT) to 7.23. For Llama 2 70B, it drops from 4.16 to 4.01.
  • 3-4 bit: Improvements persist but are smaller in absolute magnitude as the baseline approaches full precision.
• Zero-Shot Accuracy: HARP improves accuracy on ARC-Challenge, ARC-Easy, and WinoGrande tasks, confirming that perplexity gains translate to downstream performance.
• Latency & Throughput:
  • On an NVIDIA RTX 5080, 2-bit HARP achieves 128 tokens/sec for Llama 2 7B, compared to 61 tokens/sec for FP16.
  • The latency overhead of HARP over fixed RHT is modest (e.g., 0.0078s vs 0.0070s per token for 2-bit 7B), preserving the majority of the quantization speedup.
• Portability: When integrated into QTIP (a different backend using trellis-coded quantization), HARP again improved perplexity over fixed RHT, demonstrating backend-agnostic utility.
• Storage Overhead: Using int8 parameter storage, the effective bits-per-parameter (BPP) increase is minimal (e.g., 2.00 $\to$ 2.05 for 2-bit 7B), with negligible impact on model quality.

5. Significance and Claims

The paper claims that HARP addresses a specific gap in the PTQ landscape: the need for adaptive preprocessing that does not sacrifice efficiency or exactness.

• Adaptivity vs. Fixed: Unlike fixed RHT, HARP adapts the rotation basis to the specific layer and quantizer block structure, reducing reconstruction error in extreme low-bit regimes.
• Exactness vs. Approximation: Unlike some learned rotation methods that alter the full-precision model or require end-to-end training, HARP is an exact change of basis. The full-precision model is preserved mathematically; only the coordinate system exposed to the quantizer changes.
• Efficiency vs. Cost: Unlike dense learned rotations or complex graph modifications (e.g., SpinQuant), HARP maintains the $O(d \log d)$ computational cost of Hadamard transforms, making it practical for large-scale LLM deployment.

The authors position HARP not as a new standalone pipeline, but as a reusable module that enhances existing Hadamard-based backends (like QuIP# and QTIP) by learning a structured refinement around a strong, fixed baseline. The results suggest that for extreme low-bit quantization (2–3 bits), the cost of a one-time calibration to learn these rotations is well worth the substantial recovery in model quality.