Unverified 2026

Hamming-ball coverage regularizer

Implementation & benchmark of arXiv:2608.01134 — Perfect codes as exact minimizers of quadratic discrepancy in q-ary Hamming spaces

Usefulness5/10

Difficulty5/10

Novelty7/10

Regularization Generalization Accuracy Stability Tokenizer Quantization Regularization Combinatorics Harmonic analysis Geometry

Source paper: Perfect codes as exact minimizers of quadratic discrepancy in q-ary Hamming spaces arXiv:2608.01134 ⓘ · analyzed Aug 31, 2026

AI-generated research hypothesis, automatically tested. Not peer-reviewed.

Idea description

Add a multiscale Hamming-ball discrepancy penalty to a learned discrete codebook or tokenizer. The penalty forces the selected codewords to distribute their mass so that every center and radius sees approximately the global expected fraction of codewords, discouraging collapsed or highly clustered codebooks and potentially improving robustness to symbol substitutions.

Formulas

$$V_t=|B(x,t)|=\sum_{j=0}^{t}\binom{n}{j}(q-1)^j$$

$$D^{L_{2}}(\mathcal{C})=\sum_{t=0}^{n}\sum_{x\in G^n}\left(\frac{|\mathcal{C}\cap B(x,t)|}{N}-\frac{V_t}{q^{n}}\right)^{2}$$

$$D^{L_{2}}(q,n,N)=\min_{\substack{\mathcal{C}\subseteq G^n\\|\mathcal{C}|=N}}D^{L_{2}}(\mathcal{C})$$

$$\mathcal{R}_{\mathrm{HB}}=\frac{1}{|S||T|}\sum_{x\in S}\sum_{t\in T}\left(s(x,t)-\frac{V_t}{q^n}\right)^2,\qquad s(x,t)=\sum_{y\in G^n}p(y)\,\mathbf{1}\{d_H(x,y)\le t\}$$

Mathematical statement

For a finite abelian alphabet group G with |G|=q, the discrete space is X_n=G^n and d_H(y,x) is Hamming distance. A codebook C is a subset of X_n with N=|C| codewords. The Hamming ball is B(x,t)={y in X_n:d_H(y,x)<=t}, whose volume is V_t=sum_{j=0}^t binom(n,j)(q-1)^j and is independent of x. The paper defines the quadratic discrepancy D^{L_2}(C)=sum_{t=0}^n sum_{x in X_n} (|C intersection B(x,t)|/N - V_t/q^n)^2. The first term is the empirical fraction of codewords in the ball centered at x, while the second is the fraction that a uniformly distributed codeword would occupy. The paper proves that, for parameter settings admitting a perfect code, perfect codes are exact minimizers over all N-element subsets, without assuming linearity or a minimum-distance condition. For neural training, replace the hard count by s(x,t)=sum_y p(y) 1[d_H(y,x)<=t], where p(y) is the model’s soft distribution over codewords; minimize the same squared deviation. The exact theorem justifies the hard objective, while the soft version is a differentiable relaxation.

Implementation notes

(1) Integration point: apply this to the codebook logits of a VQ-VAE, residual vector quantizer, or discrete tokenizer. Represent each codeword as n categorical symbols from an alphabet of size q; the full codebook has N active codewords. Compute the regularizer on the codeword distribution, not on continuous encoder activations. Use a small subset S of centers x and a radius subset T, for example T={0,1,...,floor(n/2)}. (2) Pseudocode: sample or enumerate centers x in G^n; for every active codeword y compute h=d_H(x,y); for each t compute hard_count[x,t]=mean_y 1[h<=t]. For differentiable training, let each codeword slot have per-coordinate categorical probabilities p_{j,a}; define p(y)=prod_j p_{j,y_j}, and compute s(x,t)=sum_y p(y)1[d_H(x,y)<=t]. For small n, enumerate y. For larger n, compute s by dynamic programming over coordinates: initialize r[0]=1 and r[k>0]=0; for coordinate j update r_new[k]=r[k]p_{j,x_j}+r[k-1](1-p_{j,x_j}), where p_{j,x_j} is the probability of matching center symbol x_j; then s(x,t)=sum_{k=0}^t r[k]. Add lambda*R_HB to the reconstruction or language-model loss. Use straight-through hard code assignments for the task loss and soft probabilities only for this regularizer. (3) Quantities from the paper are V_t, the target V_t/q^n, and the squared multiscale discrepancy. Estimate the full center sum by uniformly sampling S, or use all centers for q^n up to roughly 4096. Estimate the codeword distribution from the current soft codebook probabilities; no perfect-code assumption is needed for the experiment. Normalize by |S||T| so lambda is independent of sample count. (4) First experiment: train a small VQ-VAE on MNIST or CIFAR-10 with q=4, n=8, N=256, comparing standard commitment/codebook losses against the same model plus this regularizer. Measure reconstruction error, fraction of dead codes, perplexity of code usage, and accuracy after randomly corrupting 1-2 discrete symbols. The expected signal is lower codebook collapse and improved corrupted-token reconstruction at equal codebook size, with no substantial clean-data degradation. Sweep lambda and compare t=0 only against multiscale T; the multiscale version should produce more uniform local coverage than a simple entropy penalty.

Verification

This idea has not been verified yet.

Verification happens in two stages: Stage 1 — a mechanism check on a toy system confirms the claimed mathematical phenomenon reproduces; Stage 2 — a benchmark implements the idea on a real (small) neural network task and compares it against a tuned baseline over 8 paired seeds with a permutation test.

Artifacts

Artifacts unavailable.