Feature Hashing and the Collision Bound That Sets Its Width

Hashing replaces a vocabulary of V tokens with a fixed number D of columns. Each token is mapped to a column index by a hash function, and the model learns a weight for the column rather than for the token. The vocabulary can grow without changing the design’s width, a token unseen in training lands somewhere sensible, and the mapping needs no fitted state, so no vocabulary has to be stored with the model or merged across shards. The price is collisions, and the price is quantifiable.

The construction and the sign trick

For a token t, compute a hash h(t) and reduce it modulo D, and separately derive a sign of plus or minus one from a second hash, or from a spare bit of the first. The feature vector with one active token becomes a vector with a single non-zero at column h(t) mod D, equal to the sign times the token’s value. For a bag of tokens with counts, the contribution to column j is the signed sum of the counts of the tokens that map there.

Without the sign the construction adds counts of colliding tokens, so two distinct tokens in the same column become indistinguishable and their weights are forced to be equal. With the sign they cancel in expectation: if two tokens collide, their contributions add with random signs and the expected value over the choice of signs is zero. This is the trick that makes the estimator unbiased, and the argument is the one from sketching.

Take two example vectors in the unreduced V-dimensional space and their hashed images in D dimensions. For each basis vector, the hash maps it to a single basis vector of the reduced space; call the image of basis vector i by h(i). For the inner product,

expectation of the hashed inner product: sum over i, j of x_i * x'_j * E[s_i * s_j * [h(i) = h(j)]]

For distinct indices i and j the expectation is P(h(i) = h(j)) * E[s_i] * E[s_j], which is (1 / D) * 0 and so zero, given independent signs; for i = j it is one. So the expectation is the sum of x_i * x'_i, the unreduced inner product. The hashed inner product is an unbiased estimator of the unreduced one, whatever the collision rate. What changes with D is the variance.

How large the error is

The variance of the estimator is driven by the cross terms, and its size is set by the products of coordinate pairs over colliding indices. A standard statement of the bound is that for a sparse vector with n non-zeros, the variance of the hashed inner product is at most the product of the squared norms divided by D under a fully random hash, and Jensen’s inequality converts that into a mean-squared error that decreases as 1/D. The practical reading: to keep the relative error on inner products at a level epsilon, the width must be on the order of 1/epsilon^2 times a constant depending on the sparsity, which is far more pessimistic than the common rule of thumb that the width should exceed the number of tokens by a comfortable factor.

The intuition behind the constant is worth stating. If a row has n non-zero tokens and the width is D, the expected number of non-zeros per column is n/D, and the expected number of a given token’s colliding partners is also n/D. Collisions are not rare events that occasionally coincide; they are a dense background of small contributions, and the estimator’s variance is a sum over that background. A width of 2^18, that is 262,144 columns, with 20 tokens per row gives a collision probability per token pair of about 3.8e-6, so a given token almost never collides; but a row has 190 token pairs, and over millions of rows the total number of colliding pairs is on the order of the number of tokens itself, so collisions shape the learned weights rather than perturbing them.

A second, more practical bound concerns the maximum bucket load. With n token occurrences distributed uniformly over D columns, the load of the busiest column is of order n/D + sqrt(n log D / D) with high probability, where the first term is the mean load and the second the fluctuation over D independent bucket counts. The fluctuation is what hurts: a column that accumulates many more tokens than average has a weight fitted over a mixture of them, and the model’s coefficient on that column reflects the average effect of a heterogeneous set.

The interaction with regularisation and sparsity

A hashed design’s columns are mostly zero and its rows have far fewer than D non-zeros, so the representation has the same sparsity as the unhashed one; hashing does not densify anything. What it does change is the norm structure. Two tokens that collide are, from the model’s point of view, the same feature. Under an L2 penalty the colliding tokens share a single weight, and the shrinkage applies to the sum rather than to the parts, so a token with a strong effect and a token with no effect in the same column are shrunken together toward a value that fits neither. Under an L1 penalty the collision has a different consequence: the column can be zeroed as a unit, so either both tokens are discarded or both are kept.

The collision becomes more damaging as the ratio of vocabulary to width grows, and the usual mitigation, rather than widening, is to hashing only the high-cardinality tokens and keeping a small vocabulary of frequent tokens exact. A token that appears millions of times contributes the dominant part of the inner product, and giving it a dedicated column removes its collisions with the long tail; rare tokens collide with each other, where the individual contributions are small and the cancellation is close to what the sign trick promises. The same split between a bounded exact vocabulary and a hashed remainder appears in the collision analysis of one-hot geometry and the dummy trap, where the choice is framed as how much weight to give a level seen a handful of times.

def murmur3_32(data: bytes, seed: int = 0) -> int:
    c1, c2 = 0xcc9e2d51, 0x1b873593
    h, length, i = seed, len(data), 0
    while i + 4 <= length:
        k = int.from_bytes(data[i:i + 4], "little")
        k = (k * c1) & 0xffffffff
        k = ((k << 15) | (k >> 17)) & 0xffffffff
        k = (k * c2) & 0xffffffff
        h ^= k
        h = ((h << 13) | (h >> 19)) & 0xffffffff
        h = (h * 5 + 0xe6546b64) & 0xffffffff
        i += 4
    tail = data[i:]
    k = 0
    for shift, byte in zip((0, 8, 16), tail):
        k |= byte << shift
    if tail:
        k = (k * c1) & 0xffffffff
        k = ((k << 15) | (k >> 17)) & 0xffffffff
        k = (k * c2) & 0xffffffff
        h ^= k
    h ^= length
    h ^= h >> 16
    h = (h * 0x85ebca6b) & 0xffffffff
    h ^= h >> 13
    h = (h * 0xc2b2ae35) & 0xffffffff
    return h ^ (h >> 16)

The function returns 32 bits, which bounds D at 2^32 in principle and at whatever the model’s index width allows in practice; indices are usually taken from the low bits after masking, which is why the final mixing step matters. Hashing strings without a stable seed across processes makes the mapping unreproducible between training and serving, and a token’s column can change between runs. Every serious implementation fixes the seed in configuration and treats the mapping as part of the model’s definition.

Why the mapping must be frozen

The hash function and its seed are state, even though they are not fitted. Changing the hash algorithm, the seed, or the width invalidates every learned weight, because column j no longer corresponds to the tokens it was trained on. A width change cannot be applied to a trained model by extending the array, since tokens map to different columns at a different modulus. This makes the width a versioned interface between training and inference, and it is the reason hashing is chosen for a system whose vocabulary is unknown up front but whose width must then be fixed early, before the first model is trained.

The second state requirement is the sign. Deriving the sign from a bit of the same hash is convenient but couples the two: a hash function whose low bits are used for the index and whose high bits are used for the sign is fine, whereas using the same bit for both forces all tokens in a column to share a sign and the cancellation argument collapses. Deriving the sign from an independent hash, or from a disjoint bit range, keeps the independence the bound assumes. Implementations that use one 64-bit hash and take the index from the low log2(D) bits and the sign from bit 63 satisfy this by construction.

None of these bounds depend on the data distribution, which is both the appeal and the limitation. The variance bound is worst-case over inputs, so it overstates the error for the common case where a small vocabulary dominates; the concentration bound on bucket load assumes ideal hashing, and real hash functions behave well on natural token distributions but are adversarial inputs away from the ideal. Testing the realised collision structure directly, by counting the occupancy of the busiest columns on a sample, is the only check that reflects the tokens a deployment will actually see.