Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: The paper proposes to use codes based on multiple hashing functions to reduce the input and output dimensions of transformer networks. The novelty of the idea is mostly to integrate these codes with transformers. The authors present experiments on two tasks showing that keeping overall model size fixed (i..e, number of parameters), transformers with shorter (but denser) binary codes achieve better performances than standard transformers using one-hot encodings. The gain mostly comes from using larger embedding sizes and larger intermediate layers. 

While the technical contribution is limited, because most of the principles are already known or straightforward, the main contribution of the paper is to show that random hash functions are sufficient to create significantly shorter codes and maintain good performances. Such codes provide more freedom in terms of where to put model capacity (larger embeddings, more transformer layers, etc.) which may be useful in applications where most of the model parameters are in embedding matrices. 

The value of such a paper resides mostly in the experimental study. On the bright side, the experiments present in sufficient details the impact of the various hyper parameters and the new trade-offs model size/performance that can be achieved. On the other hand, the experiments are carried out on non-standard tasks without previously published baselines, and it is unclear why. Since the method is applicable to any problem involving natural language data (and more generally categorical values, such as knowledge base completion), I would have expected experiments on tasks with a well-defined state-of-the-art. This makes the experiments in the paper look more like "proofs of concept", and they are less convincing than they should be.

detailed comments:
- The paper really is *not* about bloom filters (Bloom filters are data structures that represent sets and efficiently answer membership queries). It is about using codes of identifiers of lower dimension than one-hot encoding. This idea has been used in multi class classification setting (i.e., for the output layer) since (at least) Dietterich & Bakiri (1995) "Solving Multiclass Learning Problems via Error-Correcting Output Codes" (with more insights on what makes a good code for prediction problems). The authors borrow from Bloom filter the way to create the codes using random hash functions, but the analogy stops here. 

- following the comment above, and assuming I understood correctly: There is an originality on the paper compared to other works that use binary codes/bloom filters: In the current paper, the authors actually predict the result of individual hashing functions. This is different from predicting the binary encoding that results from using the "or" of one-hot encodings generated by several hash functions, as would be done in approaches (truely) based on Bloom filters. For instance, if there are m hash functions taking values in {1, ..., P}, an approach based on Bloom filters would predict a binary output of dimension P, while here there are m multiclass problems with P classes (IIUC). This difference from previous work may be significant in practice.

- I found the description of the link prediction task (section 3.1) rather cryptic: 
* "from each page, we take a random contiguous segment of entities". If I understand clearly, the text is filtered out and only links are kept (?). Links are replaced by the entity id they point to. What happens to the entity the page is about? Is it added at the start?
* 'For evaluation, we hold out one random entity from a random segment on a test page. ": what does "holding out" mean? From my understanding, it means replaced by the [MASK] token, but it could also mean removed altogether from the input sequence.
* the task is to predict masked links in sequences of links with the surrounding text filtered out. Does that correspond to any real-life prediction problem (i don't see which one)? Is this "task" intended to serve as unsupervised pre-training of embeddings? If yes, maybe the authors might say so and give example applications.

- For the natural language task: 
* ", then apply a Bloom filter to reduce the vocabulary size." -> From my understanding, there is no bloom filter here. If I understand, what is done is to represent unigrams and bigrams by their bloom digest to reduce the input dimension.

- "We hold out 10% random entity pages for testing. " -> is there a validation set? How do you choose the hyper parameters?


minor comments:
- "Since the Wikipedia site usually removes duplicates of links on each page, the distribution of pages is rather long tail." -> I wouldn't be surprised if the distribution was long tailed even without this specific policy
- I found the formalization/notation more confusing than helping because it is not really thorough (there is no distinction between sets and sequences, "1[\eta_j(t_i)] ... where 1[.] is the indicator function" -> what is the "indicator function" of a number?)
review_title: Official Blind Review #1

final_score: rating: 3: Weak Reject
review_content: The authors propose to learn a Transformer in embedded spaces defined via $m$ hash functions, with application to (fixed length) sequence-to-sequence classification for NLP. The method differentiates itself, in large part, by formulating model outputs in terms of $m$ distinct softmax layers, each corresponding to a hash of output space $\mathcal{Y}$. The relative low dimensionality of each hashed output space $d \ll \vert\mathcal{Y}\vert$ helps to avoid computational bottlenecks associated with wide softmax layers.

For a given labelled pair $(\mathbf{x}, y)$, the model outputs a matrix $\mathbf{P} \in \mathbb{R}^{m \times d}$, whose $i$-th row is trained using the $i$-th hash $h_{i}(y)$. At test-time, predictions are made by finding tokens $y^{*} \in \mathcal{Y}$ whose hashes best 'align' with model outputs $\mathbf{P}$. By way of example, target alignment might be defined in terms of the aggregated log likelihood

    $\ell(y; \mathbf{P}) = \sum_{i=1}^{m} \log(p_{i, h_{i}(y)})$,

where $p_{i, h_{i}(y)}$ can be understood as the element of $\mathbf{P}$ corresponding to the $i$-th hash of token $y$.

At this time, the work is significantly hindered by a lack of clarity. This issue begins with the chosen notation, which routinely obscures otherwise simple points. Similarly, the section on test-time predictions (Sect 2.5) is needlessly hard to follow. Given its pivotal role, this section feels strangely rushed. Some unanswered questions I had include:
  a) What happens if two tokens' hashes collide all $m$ times?
  b) How were hash functions inverted and what was the cost of doing so?
  c) How does the test-time throughput of the proposed compare with that of alternatives?


Questions:
  - Did you compare against different approaches to sparse softmax, such as LSH-based methods [1]?
  - What was the impact of approximate vs. exact inference and which was used during experiments?
  - How important were embedding matrices $E^{I}, E^{O}$? What happens if you directly feed hashes into the Transformer or use random projections for $E$?.


[1] "Deep Networks With Large Output Spaces", Vijayanarasimhan et al, 2015
review_title: Official Blind Review #3

final_score: rating: 6: Weak Accept
review_content: This work presents Superbloom, which applies the bloom filter to the Transformer learning to deal with large opaque ids. Quantitative results demonstrate it can be efficiently trained and outperforms non-hashed models of a similar size. The authors also highlight an important distinction from learning using the entire vocabulary: the depth is crucial to get good performance.

The size of the vocabulary could be largely reduced through hashing, which makes a larger embedding dimension and more complex internal transformation eligible and thus better performance. To make the story complete, it is good to have the results with the same embedding dimension and internal complexity as the baseline model to see the limitations. In Section 4, it is equally interesting to compare the performance between the bloom filter reduction and the data-driven word piece reduction. That is, models learned with the bloom filter applied to the whole vocabulary and models learned with the word pieces only.

I think the empirical contribution is above the bar, but I do not think the authors gave enough credit to (Serra & Karatzoglou, 2017). The adoption of bloom filter on large opaque ids has already been proposed in (Serra & Karatzoglou, 2017) as bloom embeddings to deal with sparse high-dimensional binary-coded instances. It seems that the technical part of Superbloom, including the hashing and the inference, is the same as those in (Serra & Karatzoglou, 2017). I would appreciate a lot if the authors could revise the presentation to either emphasizing the adoption of the work, or highlighting the differences.


review_title: Official Blind Review #2

Meta-review: This paper presents to integrate the codes based on multiple hashing functions with Transformer networks to reduce vocabulary sizes in input and output spaces. Compared to non-hashed models, it enables training more complex and powerful models with the same number of overall parameters, thus leads to better performance. 
Although the technical contribution is limited considering hash-based approach itself is rather well-known and straightforward, all reviewers agree that some findings in the experiments are interesting. On the cons side, two reviewers were concerned about unclear presentation regarding the details of the method. More importantly, the proposed method is only evaluated on non-standard tasks without comparison to other previous methods. Considering that the main contribution of the paper is in empirical side, I agree it is necessary to evaluate the method on more standard benchmarking tasks in NLP where there should be many other state-of-the-art methods of model compression. For these reasons, I’d like to recommend rejection. 
Decision: Reject