Overview
The Hadamard module provides functions for constructing Hadamard matrices of arbitrary dimensions using multiple construction methods, with LRU caching for efficient reuse during quantization.
Description
Hadamard matrices are square matrices with entries of +1 or -1 whose rows are mutually orthogonal. They are used in quantization algorithms (e.g., QuIP#) to rotate weight matrices before quantization, spreading quantization error more uniformly across dimensions.
The module provides several construction methods that are tried in priority order by the cached dispatcher get_hadamard(n):
- Pre-computed constants - The module loads Hadamard matrices from text files (
hadamard_*.txt) at import time via load_constants(). These files use '+' and '-' characters to represent +1 and -1 entries. A primes list is also loaded from primes.txt.
- Sylvester construction - sylvester(h) doubles the dimension of an existing Hadamard matrix using the recursive formula:
H(2n) = [[H(n), H(n)], [H(n), -H(n)]]. The dispatcher uses this for any even dimension by recursively halving.
- Paley construction type 1 - paley(n) constructs a matrix for dimension n where n-1 is prime and n-1 mod 4 = 3, using quadratic residues modulo n-1. Uses a C extension for performance with a pure Python fallback paley_torch().
- Paley construction type 2 - paley2(n) constructs a matrix for dimension n where n/2-1 is prime, using a 2x2 block structure based on quadratic residues. Also backed by a C extension with paley2_torch() as fallback.
The get_hadamard() function is decorated with @lru_cache(maxsize=100) to avoid recomputation. assert_hadamard(h) validates that a matrix satisfies all Hadamard properties: square, all entries +/-1, and rows mutually orthogonal (H * H^T = n * I).
Usage
Use get_hadamard(n) when you need a Hadamard matrix of a specific dimension during quantization or weight transformation. The function returns None if no construction is available for the given dimension. Typical dimensions in LLM quantization are powers of 2 or multiples of 128.
Code Reference
Source Location
Signature
@lru_cache(maxsize=100)
def get_hadamard(n: int) -> torch.Tensor | None: ...
def sylvester(h: torch.Tensor) -> torch.Tensor: ...
def paley(n: int) -> torch.Tensor: ...
def paley_torch(n: int) -> torch.Tensor: ...
def paley2(n: int) -> torch.Tensor: ...
def paley2_torch(n: int) -> torch.Tensor: ...
def load_constants() -> None: ...
def assert_hadamard(h: torch.Tensor) -> None: ...
def is_quadratic_residue(a: int, p: int) -> bool: ...
def test_hadamard_dims(min_dim: int, max_dim: int, step: int) -> None: ...
Import
from exllamav2.hadamard.hadamard import get_hadamard
I/O Contract
get_hadamard()
| Parameter |
Type |
Description
|
| n |
int |
Desired dimension of the Hadamard matrix
|
| Return |
Type |
Description
|
| h |
None |
Hadamard matrix of shape (n, n) with dtype float16, or None if no construction exists for dimension n
|
sylvester()
| Parameter |
Type |
Description
|
| h |
torch.Tensor |
Input square Hadamard matrix of shape (d, d)
|
| Return |
Type |
Description
|
| s |
torch.Tensor |
Doubled Hadamard matrix of shape (2d, 2d)
|
assert_hadamard()
| Parameter |
Type |
Description
|
| h |
torch.Tensor |
Matrix to validate as a Hadamard matrix (moved to CUDA for computation)
|
Usage Examples
from exllamav2.hadamard.hadamard import get_hadamard, assert_hadamard
# Get a Hadamard matrix for a specific dimension
h = get_hadamard(128)
print(f"Shape: {h.shape}") # torch.Size([128, 128])
print(f"Dtype: {h.dtype}") # torch.float16
# Validate Hadamard properties
assert_hadamard(h) # Raises AssertionError if invalid
# Use in quantization: rotate weights before quantizing
# weight_rotated = (h @ weight) / math.sqrt(n)
# Check if a dimension is supported
h_odd = get_hadamard(127)
print(h_odd is None) # True - no Hadamard matrix for 127
# Powers of 2 are always supported via Sylvester construction
h_large = get_hadamard(4096)
print(f"4096-dim shape: {h_large.shape}") # torch.Size([4096, 4096])
Related Pages
Page Connections
Double-click a node to navigate. Hold to expand connections.
