Does a Learned Encoder Need Densification? Autoencoders over One-Permutation Sketches with Empty Bins Left Visible

One Permutation Hashing is a fast way to summarize a huge, sparse binary vector, such as the set of words in a document, as a short, fixed-length signature. It shuffles the feature indices once, cuts the shuffled range into $k$ bins, and records the smallest surviving index in each bin. It costs time proportional to the number of nonzeros, not the vocabulary size. The price is the empty bin problem: short or very sparse items leave many bins with nothing in them. A decade of work has "densified" these signatures by copying values from occupied bins into empty ones, so that the collision probability still equals Jaccard similarity. Autoencoders take a different route to dimensionality reduction. An autoencoder is a network trained to compress an input through a narrow bottleneck and reconstruct it. It learns which features co-occur, which random hashing cannot do. It is also hard to run on vocabularies of millions, because its first layer needs a weight for every input dimension.

This note proposes putting the two in series. A densification-free sketch is the constant-cost front end. A small autoencoder reads the sketch, with each empty bin shown as an explicit, learned "absent" token. The note then asks a question neither literature has posed: once a learned model sits after the sketch, is densification still the right treatment of empty bins, or does it throw away information the encoder could use? Our hypothesis is that leaving empty bins visible gives better semantic retrieval codes than feeding densified sketches. We expect the gain to fall almost entirely on items with few occupied bins, which is exactly the regime where densification degenerates into copying one value hundreds of times.

Why the question is open

The densification line is thorough within its own goal, which is unbiased Jaccard estimation. Densifying One Permutation Hashing via Rotation fills each empty bin from its nearest occupied neighbour to the right, adding an offset. It shows zero bias where the naive "empty equals empty" and "empty never equals" rules drift badly. Improved Densification of One Permutation Hashing randomizes the borrowing direction per bin, which lowers variance. On Densification for Minwise Hashing characterizes valid densification as consistent sampling and gives an expected $O(k \log k)$ push scheme. Revisiting Winner Take All Hashing for Sparse Datasets and Densified Winner Take All Hashing carry the same idea to rank-based codes on sparse visual bag-of-words data. These papers motivate the proposal, and one of them also supplies a method we reuse: the push scheme is our densified-input condition. All of them optimize a fixed estimator that counts collisions. None asks what a trainable consumer of the sketch needs. For a collision counter, a shared empty bin is poisonous. For a network that can see a per-bin "absent" marker and the item's overall occupancy, absence may be ordinary evidence. For example, the pattern of empty bins encodes document length and density. The known weakness of densification also matters here: an item with two occupied bins out of 1,000 gets a signature made almost entirely of copies. That is the variance floor the research file flags, and a learned model might sidestep it.

The autoencoder line supplies the other half and one constraint. Winner-Take-All Autoencoders enforces hard top-$k$ sparsity in the hidden layer instead of fragile L1 or KL penalties. We borrow its lesson that hard selection beats tuned penalties when we choose the bottleneck. Our "empty bins" are in the input sketch, not in the latent layer, and we do not propose densifying latent units. In a sparse autoencoder zeros are intended, and copying values into them has no clear meaning. Learning Compressed Sentence Representations for On-Device Text Processing trains an autoencoder with a straight-through binarizer to produce Hamming-searchable codes from dense 4096-dimensional embeddings. We reuse its binarization for equal-bit comparisons. It also constrains us. That paper reports that plain random projection performed "remarkably well" at 512 bits, so any learned code must be checked against a random one at matched bits.

Core Claim

Define the encoder input for item $A$ as a sequence of $k$ tokens. The token for bin $j$ is

$$t_j(A) = \begin{cases} u_j & \text{if bin } j \text{ is empty,} \\ E[\,g(j, h_j(A))\,] + p_j & \text{otherwise,}\end{cases}$$

Here $h_j(A)$ is the minimum permuted index in bin $j$, and $g$ is a hash into a table $E$ of $M$ learned embeddings, with $M$ around $2^{18}$, so parameter memory does not grow with vocabulary size $D$. The vector $p_j$ is a learned bin-position embedding, and $u_j$ is a learned "empty" embedding for bin $j$. A light encoder, a small attention or pooling stack, maps the $k$ tokens to a $d$-dimensional code, which is optionally binarized. The decoder reconstructs the item's features in the same hashed output space with sampled negatives. Encoding cost is $O(\text{nnz} + kW)$ for layer width $W$. It is independent of $D$ and bounded even for long documents.

The claim has two parts. First, holding everything else fixed, the masked-empty input will beat the densified input in label-based retrieval quality. Second, the margin will grow as the number of occupied bins shrinks. The claim is falsified if densified input matches or beats masked input overall, or if the gain does not concentrate in low-occupancy items.

Research Program

We will build three input conditions for one encoder–decoder: masked-empty tokens, push-densified tokens following Mai et al., and the naive "empty equal" constant token. We also build the non-learned and alternative-learned competitors below. Everything uses the same sketch size $k$ (chosen from 256, 1,024 and 4,096), code size, training data and tuning budget.

The main analysis stratifies every metric by occupancy, meaning the fraction of non-empty bins. The expected effect lives in the low-occupancy tail, and averages would hide it. We also measure how well each learned code still tracks true Jaccard similarity, using the Spearman correlation between code similarity and exact Jaccard on sampled pairs. This tells us what the learned code gives up relative to the provably unbiased estimator.

Baselines

The naive reference is the "empty equal" treatment. It is applied once to the raw sketch with collision counting and once as the constant-token input to our encoder. It fixes the floor that densification is known to beat.

The strongest non-learned method is the push-densified sketch of On Densification for Minwise Hashing, used directly for retrieval by counting collisions at the same $k$. It is the strongest competitor because it is unbiased for Jaccard, fast, and needs no training. On sparse text, Jaccard neighbours are already decent semantic neighbours. For bag-of-words vision data (MSRc, VOC2010) the matching non-learned competitor is Densified Winner Take All Hashing. It reports 0.032 ms per item against 8.578 ms for sparse random projection on VOC2010, which sets the latency bar our encoder must be judged against. We found no reported label-precision result on Lacuna for densified one-permutation hashing on RCV1 or NEWS20, so we will measure it ourselves. Beating it means higher label precision at 10 and 100 neighbours at equal code bits, within a stated latency multiple.

The external task anchor is the RCV1 benchmark paper, RCV1: A New Benchmark Collection. It reports microaveraged F1 of 0.765 for k-nearest-neighbour classification and 0.816 for a linear SVM on the Topics labels, both on full features. A compact code whose nearest-neighbour F1 approaches 0.765 is competitive with uncompressed neighbour search.

The strongest learned competitor is a hashing-trick autoencoder. Raw features are hashed into $M$ buckets and fed through a sparse first layer costing $O(\text{nnz} \cdot W)$, with the same bottleneck, decoder and binarizer. We add random projection at matched bits, following the warning from Learning Compressed Sentence Representations.

The ablation that isolates the key ingredient is our encoder fed the densified sketch rather than the masked one. Everything else is identical: the embedding table, the architecture, and 30 tuning trials per condition drawn from the same search space on the same hardware.

Why not just…?

Why not just use the densified sketch directly and skip learning? It is unbiased for Jaccard and costs nothing to train. If the task is literally Jaccard neighbour search, it will win, and our Jaccard-correlation measurement is designed to confirm that. The proposal only claims gains on label-defined retrieval, where co-occurrence structure matters and Jaccard is a proxy. If the densified sketch matches our encoder on label precision, the learned stage is not justified, and we will report that.

Why not just feed the densified sketch to the autoencoder? This is the central ablation, not an argument we are trying to avoid. Densified values carry an offset that marks them as borrowed, so a network could in principle recover the mask. It is therefore plausible that the two inputs perform alike. The occupancy-stratified comparison settles it. If there is no gap in the low-occupancy tail, the conclusion is that densification is harmless for learned consumers, which is itself useful to know.

Why not just use a hashing-trick autoencoder with a sparse first layer? This is the real threat. It sees every feature rather than one minimum per bin, and its cost also scales with nonzeros, not $D$. The sketch front end has two structural advantages: bounded cost on long documents, and a fixed-length input that exposes occupancy. Neither guarantees better codes. We will compare at matched wall-clock encoding cost, splitting documents by length. If the hashing-trick model wins everywhere, the sketch front end is only a speed device, and we will say so.

Why not just use random projection? Its known cost on high-dimensional inputs is the 200x latency gap reported by Densified Winner Take All Hashing. Its quality at modest bit budgets is not in doubt, so it stays in the comparison at every bit width.

Proposed Experiments

We train on RCV1-v2 (Topics labels) and NEWS20 for text, and use URL and WEBSPAM for scale and extreme sparsity, where only latency, memory and Jaccard tracking are evaluated because the label structure is binary. We use MSRc and VOC2010 bag-of-words for vision, where the one-permutation front end is replaced by its winner-take-all analogue with the same masked-versus-densified contrast.

Metrics are label precision at 10 and 100 neighbours, k-nearest-neighbour microaveraged F1 on RCV1 Topics, per-item encoding latency and memory, and Spearman correlation with exact Jaccard. Code sizes are 64, 256 and 512 bits after binarization, plus 128 floats. Three seeds are run per configuration, with paired bootstrap intervals.

Three checks decide the outcome. The first is whether masked input beats densified input in the bottom occupancy quintile, and whether that gap is larger than in the top quintile. The second is whether the masked encoder beats the hashing-trick autoencoder at matched encoding cost on at least the long-document half. The third is whether the learned code keeps Jaccard correlation high enough that it does not lose on pure near-duplicate retrieval, which we test on URL. Passing the first check alone establishes the scientific point about empty bins. Passing all three establishes a practical method.