HFQ (Hash-based Quantization)#

TL;DR — HFQ (Hash-based Quantization) utilise des fonctions de hachage pour déterminer les paramètres de quantification ou les affectations de codebooks. Au lieu d'apprendre un codebook coûteux (comme AQLM), HFQ utilise une hash function déterministe pour assigner chaque poids à un « bucket » quantifié. Résultat : une compression rapide, sans calibration et à footprint minimal, particulièrement adaptée à l'edge computing.

Le problème fondamental (expliqué pour un néophyte)#

Les méthodes de vector quantization comme AQLM ou QuIP# doivent apprendre un codebook — un dictionnaire de vecteurs de référence. C'est puissant mais coûteux : il faut des heures de calcul, des données de calibration, et stocker le codebook lui-même.

L'idée de HFQ : et si on remplaçait le codebook appris par une simple fonction mathématique déterministe (une hash function) ? Au lieu de chercher « quel vecteur du codebook ressemble le plus à mes poids ? », on calcule simplement hash(poids) → bucket. C'est comme remplacer un dictionnaire de 65 000 entrées par une formule qui donne la réponse instantanément.

Contexte scientifique#

La quantification par hachage s'inspire du « hashing trick » (feature hashing), une technique classique en machine learning pour projeter des données dans un espace réduit de manière déterministe. Pour les réseaux de neurones, cette idée a été popularisée par HashedNets (2015) qui utilise le hachage pour le weight sharing — tous les poids dans le même « hash bucket » partagent une seule valeur.

Pour les LLMs spécifiquement, HFQ reste un domaine plus niche que GPTQ ou AWQ, mais les concepts de hash-based quantization sont très pertinents pour l'edge computing et les scénarios où le temps de quantification doit être minimal.

Papier de référence principal#

HashedNets est le travail fondateur du hachage pour la compression de réseaux de neurones. Il introduit le concept de virtual weights (poids apparemment nombreux) mappés à un petit ensemble de physical weights (poids réels) via une fonction de hachage.

Mécanisme#

Niveau néophyte#

Imagine que tu veux ranger 1000 objets dans 100 boîtes. Deux stratégies :

1. Codebook classique : tu analyses chaque objet, tu trouves la boîte « la plus proche » en comparant avec le contenu de chaque boîte. Lent mais précis.
2. Hash function : tu utilises une formule qui, à partir de l'objet, te donne directement le numéro de la boîte. Instantané, mais la répartition n'est pas optimale.

HFQ choisit la deuxième approche. La hash function agit comme un « aiguillage » automatique : chaque poids est envoyé dans un bucket sans qu'on ait à le comparer à quoi que ce soit.

Niveau intermédiaire#

HFQ remplace le codebook appris par une fonction de hachage h qui mappe l'espace des poids vers un ensemble discret de 2^b buckets (où b = nombre de bits) :

Quantification classique (codebook) :

  q(w) = argmin_i || w - c_i ||²     (recherche du nearest neighbor)

  où c_i sont les vecteurs du codebook (appris)

Quantification hash-based (HFQ) :

  q(w) = h(w) mod 2^b               (évaluation d'une fonction)

  où h est une hash function déterministe

Weight sharing par hachage (HashedNets) :

Le principe central de HFQ est que plusieurs poids partagent une seule valeur physique via le hachage. Pour une couche avec N connexions :

HashedNets : N connexions virtuelles → K << N poids physiques

  hash(i) mod K → bucket_id  →  poids physique W_phys[bucket_id]

  Connexion virtuelle i utilise : W_phys[hash(i) mod K]

  → On stocke seulement K valeurs au lieu de N
  → Compression ratio = N / K

8 connexions → 4 poids physiques stockés → compression 2x · La hash function est la « table de correspondance »

Niveau tech avancé#

La théorie derrière HFQ repose sur trois piliers :

1. Le hashing trick (feature hashing)

Le hashing trick, introduit par Weinberger et al. (2009), projette un vecteur de dimension d vers une dimension k << d via :

φ(x)_i = Σ_{j: h(j)=i} ξ(j) × x_j

  où :
  h : {1,...,d} → {1,...,k}  (hash function)
  ξ : {1,...,d} → {-1, +1}   (sign hash, élimine le biais)

La lemma de Johnson-Lindenstrauss garantit que cette projection préserve approximativement les distances avec haute probabilité. Pour les poids de réseaux de neurones, cela signifie que les collisions de hash (deux poids dans le même bucket) introduisent un bruit borné.

2. Weight sharing forcé

HashedNets force un partage de poids dur (hard weight-sharing) : toutes les connexions dans le même bucket utilisent exactement la même valeur. Le nombre de paramètres libres passe de N à K. Pendant l'entraînement, les gradients de toutes les connexions d'un bucket sont sommés et appliqués au poids physique partagé.

3. Structured Multi-Hashing

Eban et al. (CVPR 2020) étendent l'idée avec du multi-hash structuré : au lieu d'une seule hash function, on utilise plusieurs fonctions de hachage en cascade pour créer une structure de partage hiérarchique :

Multi-Hash :

  Niveau 1 : h₁(i) mod K₁   → partage grossier
  Niveau 2 : h₂(i) mod K₂   → partage fin
  Niveau 3 : h₃(i) mod K₃   → partage residual

  w_phys(i) = W₁[h₁(i)] + W₂[h₂(i)] + W₃[h₃(i)]

  → Combinaison additive de tables de hash
  → Similaire à AQLM mais avec des tables hash au lieu de codebooks appris

4. Application aux LLMs

Pour les LLMs, deux variantes émergent :

• HFQ-assign : la hash function assigne chaque poids à un niveau de quantification (remplace la recherche de nearest-neighbor dans le codebook)
• HFQ-share : la hash function force le partage de poids (compression structurelle, pas seulement précision réduite)

Le trade-off : HFQ est moins précis qu'un codebook optimisé (car la répartition par hash est aléatoire, pas optimisée), mais beaucoup plus rapide à calculer et ne nécessite ni calibration ni entraînement de codebook.

Illustration : le process HFQ#

Hash function : choix et propriétés#

HFQ-assign vs HFQ-share : tableau comparatif#

Bits / Formats supportés#

HFQ est particulièrement adapté aux scénarios où la vitesse de quantification et le footprint mémoire sont plus critiques que la qualité maximale.

Résultats#

HashedNets — Compression de MLPs (résultats fondateurs)#

Compression ratio : 8× à 32× · Perte d'accuracy : < 1% (souvent négligeable)
Note : résultats sur petits modèles. Pour les LLMs modernes, HFQ n'a pas encore de benchmarks standardisés.

Positionnement pour les LLMs#

⚡ Instantané ← Vitesse maximale, qualité modérée · · · Qualité maximale, vitesse minimale → ⏳ Lent

Avantages et inconvénients#

Exemple pratique#

Implémentation HFQ-share (weight sharing par hash) en PyTorch#

import torch
import torch.nn as nn
import hashlib

class HashedLinear(nn.Module):
    """
    Couche linéaire avec weight sharing par hash (HashedNets-style).
    N connexions virtuelles → K poids physiques.
    """
    def __init__(self, in_features, out_features, compression=8):
        super().__init__()
        self.in_features = in_features
        self.out_features = out_features
        self.N = in_features * out_features  # connexions virtuelles

        # K = nombre de poids physiques (compression ratio)
        self.K = max(1, self.N // compression)

        # Poids physiques (seuls ceux-ci sont stockés)
        self.physical_weights = nn.Parameter(
            torch.randn(self.K) * 0.02
        )

        # Table de hash précalculée : connexion → bucket
        self.register_buffer(
            'hash_table',
            self._build_hash_table()
        )

    def _build_hash_table(self):
        """Hash function : connexion_idx → bucket_idx"""
        # Hash simple : (a*i + c) mod K
        indices = torch.arange(self.N)
        a, c = 2654435761, 12345  # constantes de hash
        return ((a * indices + c) % self.K).long()

    def forward(self, x):
        # Reconstruire la matrice virtuelle à partir des poids physiques
        W_flat = self.physical_weights[self.hash_table]
        W = W_flat.view(self.out_features, self.in_features)
        return torch.nn.functional.linear(x, W)

# Usage
model_dim = 4096
layer = HashedLinear(model_dim, model_dim, compression=16)

# Compression : 4096×4096 = 16.7M params → 16.7M/16 ≈ 1M params
# Taille : 67 MB → 4.2 MB (16x compression)
# Quantification : instantanée (juste la construction de la hash table)
# Calibration : AUCUNE

HFQ-assign : quantification par hash#

import torch

def hfq_assign(weights, bits=4, seed=42):
    """
    Quantification par hash : chaque poids est assigné
    à un bin via une hash function.
    """
    num_bins = 2 ** bits

    # Centres des bins (distribution uniforme dans [-max, max])
    w_max = weights.abs().max()
    bin_centers = torch.linspace(-w_max, w_max, num_bins)

    # Hash des indices → bucket
    indices = torch.arange(weights.numel())
    a, c = 2654435761 * (seed + 1), 999983
    buckets = (a * indices + c) % num_bins

    # Assignation : poids → centre du bucket hashé
    quantized = bin_centers[buckets].view_as(weights)

    # Résultat :
    # ┌──────────────────────────────────────────────┐
    # │  Poids FP16  →  poids quantifiés par hash    │
    # │  Bits : 4                                     │
    # │  Calibration : AUCUNE                        │
    # │  Vitesse : O(N) instantané                    │
    # │  Qualité : modérée (non-optimale)             │
    # └──────────────────────────────────────────────┘
    return quantized

# Quantifier une matrice de poids
W = torch.randn(4096, 4096)  # couche de LLM
W_hfq = hfq_assign(W, bits=4)

# Comparaison erreur
mse = ((W - W_hfq) ** 2).mean()
print(f"HFQ 4-bit MSE: {mse:.6f}")

Quantifier un LLM avec HFQ-share (proof of concept)#

python -c "
import torch
from transformers import AutoModelForCausalLM

model = AutoModelForCausalLM.from_pretrained(
    'meta-llama/Llama-2-7b-hf',
    torch_dtype=torch.float16,
    device_map='auto'
)

# HFQ-share : remplacer chaque nn.Linear par HashedLinear
# (proof of concept — pas d'outil prêt à l'emploi pour LLMs)

# Résultat attendu (théorique) :
# ┌──────────────────────────────────────────────┐
# │  Llama-2-7b FP16      :  13.5 GB             │
# │  HFQ-share 8x         :  ~1.7 GB  (−87%)     │
# │  HFQ-share 16x        :  ~0.85 GB (−94%)     │
# │  Temps de quantif.    :  < 30 secondes        │
# │  Calibration          :  AUCUNE               │
# │  Perte de qualité     :  significative en     │
# │                          bas bitrate (à évaluer)│
# └──────────────────────────────────────────────┘

print('HFQ pour LLMs : concept prometteur pour edge,')
print('mais nécessite validation empirique et kernels optimisés.')
"

Comparaison avec les alternatives#

HFQ est la méthode la plus rapide et la plus simple conceptuellement, mais aussi la moins précise pour les LLMs modernes. Son intérêt principal réside dans l'edge computing où la vitesse de quantification prime sur la qualité.

Références#

• HashedNets — Chen et al., « Compressing Neural Networks with the Hashing Trick », ICML 2015 — PDF | NVIDIA Research
• Structured Multi-Hashing — Eban et al., « Structured Multi-Hashing for Model Compression », CVPR 2020 — PDF
• Balanced Weight-Sharing — « Balanced and Deterministic Weight-sharing Helps Network Compression », 2023 — arXiv:2312.08401
• Feature Hashing — Weinberger et al., « Feature Hashing for Large Scale Multitask Learning », ICML 2009 — fondement théorique du hashing trick
• Johnson-Lindenstrauss — lemme de projection aléatoire qui garantit la préservation des distances par hash
• Page HashedNets — cse.wustl.edu/~yixin.chen/HashedNets
• Page de référence — Voir Quantification LLM pour le panorama complet
• Méthodes comparables — Voir HQQ (autre approche sans calibration), AQLM (codebook appris)