Superbloom: Bloom filter meets Transformer
Authors: John Anderson
Qingqing Huang
Walid Krichene
Steffen Rendle
Li Zhang
Venue:  (2020)
Keywords: Bloom filter
Transformer
word pieces
contextual embeddings

Abstract: We extend the idea of word pieces in natural language models to machine learning tasks on opaque ids. This is achieved by applying hash functions to map each id to multiple hash tokens in a much smaller space, similarly to a Bloom filter. We show that by applying a multi-layer Transformer to these Bloom filter digests, we are able to obtain models with high accuracy. They outperform models of a similar size without hashing and, to a large degree, models of a much larger size trained using sampled softmax with the same computational budget. Our key observation is that it is important to use a multi-layer Transformer for Bloom filter digests to remove ambiguity in the hashed input. We believe this provides an alternative method to solving problems with large vocabulary size.

Under review as a conference paper at ICLR 2020
SUPERBLOOM: BLOOM FILTER MEETS TRANSFORMER
Anonymous authors
Paper under double-blind review
ABSTRACT
We extend the idea of word pieces in natural language models to machine learning tasks on opaque ids. This is achieved by applying hash functions to map each id multiple hash tokens in much smaller space, similarly to a Bloom filter. We show that by applying a multi-layer Transformer to these Bloom filter digests, we are able to obtain models with high accuracy. They outperform models of similar size without hashing and, to a large degree, models of a much larger size trained using sampled softmax with the same computational budget. Our key observation is that it important to use multi-layer Transformer for Bloom filter digests to remove ambiguity in the hashed input. We believe this provides an alternative method to solving problems with large vocabulary size.
INTRODUCTION
In natural language processing, one recent development, made popular Wu et by smaller sub-word vocabulary (Sennrich et al. (016)), or so called word piece model. In such a model, only frequent words and word pieces are kept in the vocabulary. Each word then segmented as sequence of word pieces. Both the input and the prediction are then represented in the smaller word piece space.
(2016) is to use
The word piece model has multiple benefits. Besides its generalizability and compact size, one erucial benefit is that This leads to more precise predictions, (measured e.g. using recall at is for small values of k), compared to alternative approaches such as the sampled softmax method (Bengio & Sénécal [003] 2008) or the hierarchical softmax (Morin & Bengio 2005). Word pieces have been shown to work well for natural language understanding (NLU) tasks. For example, the recent treak-through of BERT (Devlin et al.] 2018)) uses a vocabulary of about 30K word pieces. The goal of this paper to extend this idea to machine learning tasks where we have to model large number of categorical values, which are represented by opaque ids (e.g. product ids, video ids) or named entities (e.g. Wikipedia or Knowledge Graph entities).
afford to compute the full softmax loss its much smaller vocabulary.
While word pieces are a natural way for breaking up words, it is unclear how this could be done for a set of arbitrary categorical values (referred to as vocabulary throughout the paper). We adopt a technique proposed by /eerrà & Karatzoglou (0177) of using multiple hashing to reduce the vocab- ulary size while still keeping each entity identifiable. The idea is to map each id to multiple hash tokens in smaller space, similarly to Bloom filter (Bloom 1970). and then embed and predict at the token, instead of the id, level. This way, the vocabulary is reduced to a much smaller size, similar to the effect of word pieces. However, hashing introduces much ambiguity due to random collisions. To solve this problem, we propose to use hashing in combination with a multi-layer Transformer (Vaswani al., 2017), based on observations that the Transformer can disambiguate word meanings well using context. A hashed token can be viewed as a word piece with many dif- ferent meanings. We hope that Transformer model is also able to remove the ambiguity of hash tokens using the context, i.e. the set of other input tokens.
With these motivations, we build Superbloom in which we apply Transformer model to the Bloom filter digest of the input. On the output side, the predictions are on the hashed tokens, similar to (Serra & Karatzoglou 2017). We demonstrate, through experiments, that Superbloom works well for tasks with large vocabulary size it can be efficiently trained and outperforms hashed models of a similar size, and larger models trained with sampled softmax with the same computational budget.

---

Under review as a conference paper at ICLR 2020
The key insight from our experiments is that the multiple-layer Transformer is effective for resolv- ing the ambiguity in the hashed input, hence works particularly well for Bloom filter digests. For instance, we find that the model quality gap between a one layer and twelve layer Transformer model is significantly larger when using Bloom filter digests, compared to that when the vocabulary is not hashed. This capability of the Transformer to "unhash" the Bloom digest is key differ- ence to earlier work on feature hashing (Weinberger et al., (209)) and multiple hashing (Serrà & Karatzoglou 2017, [venstrup et al. 2017 Daniely et al. 2017). In addition, we propose an efficient approximate inference algorithm. by applying "beam search" the much smaller token space. Such fast inference is another useful property of Superbloom.
The Superbloom model is trained using BERT's masked language model task, i.e. on predicting hash tokens masked out from the input. Since the hashes have a much smaller vocabulary. this aspect is closely related to the error-correcting output codes (ECOC) (Dietterich & Bakiri 1994] Berger 1999 In the ECOC model, a multi-class classification is converted into many binary classification problems where redundancy is added to improve the robustness of the model. The prediction task of Superbloom can be viewed as reducing a large multi-class classification problem to few smaller multi-class classification problems. However, unlike the ECOC models, we do not reduce the problem all way down to binary predictions. This might the additional reason that Superbloom is able to achieve high accuracy.
1.1 RELATED WORK
Learning with a large vocabulary is a well-studied but still open research problem. Weinberger et al.] al.] (2009) proposed feature hashing which uses random hashing to reduce the input vocabulary size, and then learns embeddings for hashed ids in the smaller vocabulary. Several follow-up works propose to better resolve collisions by using multiple hashes: [Svenstrup et al. (2017) proposed to learn a weighted sum of hashed embeddings; [Shu & Nakayama (2018) used an unweighted sum, but proposed instead to learn the hash function itself; and Chen et al. (2018) proposed to learn both the hash function and the combiner, for which they use either a linear function or an LSTM. A key difference with the aforementioned work is that we do not resolve the hashing early at the input of the model; instead, we feed all hashed embeddings to the Transformer and let it learn to resolve the hashing collisions using the context. Our experiments show that multi-layer Transformer models indeed have the capacity to resolve hashing collisions while learning a high quality model.
Besides reducing the imput space and memory usage, another set of related work focuses on deal- ing with large output vocabularies and improving training efficiency. A commonly used method is sampled softmax (Bengio & Sénécall 2003) 2008) where for each gradient update, only a subset of the output vocabulary is considered. Another line of work is hierarchical softmax where classes organized in clusters (Gooodman) 2001) or in a tree structure (Morin & Bengio 2005) to allow for experiments, we show that Superbloom,
efficient pruning of the output vocabulary. Through which allows us to train full softmax on the hashed vocabularies, can lead to more accurate results than using sampled softmax on the larger output vocabulary. Seerr & Karatzoglou (2017) proposed to use Bloom filters as a general tool in deep models, for both the input and output. Our work demon- strates the efficiency of multi-layer Transformer-lik architecture to use contextual information to resolve hash ambiguity. Indeed, we show that shallow models, even with attention, fail.
SUPERBLOOM MODEL ARCHITECTURE
Given discrete sets St, S SOS representing respectively the input and output spaces (e.g. word tokens or entities), the goal is to model function that maps sequence of n elements in St, to a sequence of probability distributions over S The space of probability distributions over a set S will be
denoted by A(S) = (p E R E.ssP =
The input and output entities are typically represented using embedding matrices E² E R and EO E f which map each entity to an embedding vector of dimension d. This makes training and inference expensive if the number of entities is very large. In order to reduce the model size and
1 This connection is suggested by an anonymous reviewer. We assume a fixed sequence length for simplicity. This is also useful assumption for practical implemen- tation on TPU, which requires fixed input dimensions.
2

---

Under review as a conference paper at ICLR 2020
Input layer
Transforer layess
Output layer
Ousput bashing
yi1
Pla
Jpves
Aue En
Attrettionn
Food Rorwan
Iuure SuRTs
Reif
g
Mruk
Par
(S)
ym
R Ramndd
B Reno
A yuu
[NO
(S
Figure 1: Superbloom model architecture
improve efficiency, we hash each element follows. Given hash functions h2, J {1,..., m), each element s is represented by the hashes (#) hm (s),, which we refer to as a Bloom digest, given its similarity to the Bloom filter data structure. The set of values the hashes can take much smaller than the original spaces St ,0 which allows us to reduce the vocabulary size and thus the size of embedding matrices.
We decompose the Superbloom model architecture into M O (T₁, o.... o Ti) o I, as illustrated in Figure an input layer (Sec. 2.1 I (8')" + Rmax which maps each item in the input sequence embeddings of dimension d: L transformer layers (Sec. (Sec. (.2) T₃ R Ronxd - Rmxxd which apply transformations in the embedding space; and an output layer (Sec. 2.3 O Rmxx A(H mapping each embedding to a probability distribution. Since the model predicts distri- butions over 7t instead of So, both training (Sec. 2.4) and inference (Sec. 2.5 need to be adapted accordingly.
2.1
INPUT LAYER :: (8t)" -> Rmaxd
The input layer consists of hash functions
m} S + H' m.. and embedding matrix E E |R] The input sequence ($1....,8p 8p) is mapped the sequence of embeddings (Bhy(er))---- (o.); FA, (em)...... () ). For ease of notation, we will write Ti.j En, (+.) Rd, and denote the sequence by (zi,)) hash of the i-th element.
Throughout, we use subscripts i.j to denote the j-th
2.2 TRANSFORMER LAYERS T Rmaxd - Roaxd
The Transformer is an attention-based model that was initially proposed for sequence transduction tasks, and that has been used in various other settings such BERT. For the intermediate layers of Superbloom, we use the same architecture as the original transformer model (Vaswani et al. 2017). which we briefly summarize in Appendix A Each transformer layer is function 7 R ma Rmaxdd x which maps a sequence of mn embeddings in Rd to another sequence in the same space. We
will denote by (Wa.)) (Ir.)) i=I..... the output sequence of the last transformer layer, where each yi.j E Rdd
2.3 OUTPUT LAYER: O R.nn A(H0)mm
Similarly to the input layer, we have m hash functions "/ SO + HO f1,..., m) for the output space. We modify the original goal of predicting distribution over 8 to predicting distributions over HO, as follows. If (mr.)) is the output of the last transformer layer, then the output layer O maps each Vi to
Pr, = o (v.
A(H)).
'The hash functions and their inverse mappings are randomly generated and stored as look-up up tables. When generating the hash functions, we make sure that each hash bucket is evenly sized, and that there are complete collisions.
3

---

Under review as a conference paper at ICLR 2020
I is output embedding matrix, and a is the softmax function. Note that in some problems, the input and output spaces coincide, so it can be advantageous to use identical input and output hash functions, hy = Mlj, and the same embedding matrices E' E
where E
2.4 TRAINING
If the target sequence in So is (ti....,tt)) [n). then the corresponding target sequence in 70 is (ns (4.)) We define the training objective
n
m
where pij AAH)) are the model's output distributions, and l A(H 70 I is loss function, e.g. the cross-entropy loss. Note that we can pre-process the training data to map the elements in the original spaces (S")",((") to the hash spaces (H')m, (HO)mm, and training proceeds entirely the hash spaces.
Model size and efficiency Compared to model trained on the original space, the main advantage of Superbloom a reduction in the size of the embedding matrices E F For instance, if a a-to- one hashing is used (i.e., each hash bucket contains elements), then [7|| = |S|/a a and the size of the input matrices reduced by factor a. This not only reduces the memory cost, but may also improve the efficiency of gradient updates during training. Consider a cross-entropy loss, for each training example, all elements in the output space have a non-zero gradient due the partition function in softmax, and thus the full matrix E needs to be updated at each step, unless approximate methods such as sampled softmax (Bengio & Sénécal 2003) are used. Our experiments (see Section 3.5) show that the cost of updating Eo dominates that of training, and reduction in vocabulary size allows us significantly reduce training time without resorting negative sampling.
Algorithm Approximate and exact inference in Superbloom
1: Input: Beam width B, maximum iteration number N, model outputs P5 E A(H and hash inverse look-up tables f7 for j = I....,
2: For each j, sort Pj
3: for b B,..., NB do
4: Let p be the 6-th largest value in Pj.
5: For each j. compute S/ {s S (s() 2 pÿ}.
6: Score all candidates in 5h St U... U.h Let arg max 7(s).
7: if (s*) 2 Σg log then break.
This guarantees 7(8) 7s*)) for all
8: return 8*.
2.5 INFERENCE
For each position in the sequence, the model outputs m distributions (pi.) A(H and goal is to these distributions rank the elements of S To simplify notation, assume in this section that is fixed and will omit it by writing Pj instead of pi.j-
One simple way to rank items, proposed by Serrà & Karatzoglou (2017), is to compute, for each 5, (ss) == Σm= log p. (=). When So is very large, this can be expensive, so instead of exhaustively scoring all items 8, we propose an iterative beam-search, given Algorithm [ and illustrated in Figure 2 that can be used to compute the top-k element either exactly, or approximately by fixing a maximum iteration number.
Let us fix a beam width b, and let p be the b-th largest value of Pj. and let S) {s E SO ps (s)(ss)) p.}- In words, Sy are elements whose hash is in the top b values according to Pj-
*Note unlike ECOC (Dietterich Bakiri 1994), the task is not to predict the individual bits output Bloom digest, but rather to predict (a probability distribution over) the index of the m non-zero hits. For simplicity, we descrihe the algorithm for & 1, but we apply it for larger & in experiments.
4

---

Under review as a conference paper at ICLR 2020
S
S
S
42
SP Figure 2: Illustration of approximate and exact inference, with number of hashes m = 2, four- to-one hashing scheme, and a beam width = 2.
S/ is obtained by pre-computing and storing inverse look-up tables 6 M1j" for each hash function, and observing that S (1)2)())2 (h). This defines a of candidates to score Sh == S U U...U % and guarantees the following upper-bound: for all $ 8h (()) E, log D/. If the best scored element s* == arg max s (ss) satisfies 7(s") 2 Σj log pj. then we have a certificate that s* is the best element over the entire set and the algorithm terminates. Otherwise, we increase the beam width and score
set of candidates.
example illustrated in Figure 2 for m 2, beam width B 2, and hash functions with = 4 (four elements share the same hash value along each dimension). The subset of candidates to score during the first iteration is highlighted in blue. The top element s* circled, and the solid line shows its level set. In the left figure, the level set does not intersect the shaded area (unscored elements), thus we have a certificate that s* is the exact maximizer. In the right figure, the level set does intersect the shaded area, so to find the exact maximizer, a second iteration is performed where the search region is extended (highlighted in red).
Computational complexity Consider an a-to-one hashing scheme. Sorting the vectors Pý (line 2) costs (m/[H)) log 1). Each iteration consists of computing Sy (line 5) then scoring candidates in 5h (line 6) which costs O(m² Bai). The total cost for N iterations is Om log (?( + m N Ba)) which can be significantly cheaper than scoring all candidates (((89).. For example, with the parameter setting described in Section 3.3] approximate inference 10 times faster than exhaustive scoring. In Appendix B we study the effect of the beam width on the quality of the model.
Remark 1. While we describe a particular choice of ranking function 7, it is possible to generalize the algorithm to other ranking functions that are increasing, in sense described in Appendix C
3 WIKIPEDIA ENTITY PREDICTION
We apply Superbloom to the Wikipedia entity prediction task, in which we use surrounding links on Wikipedia page to predict held-out link. This task is derived from the same data set as many NLU tasks, but uses entities instead of natural language. We believe this study is complementary to previous NLU models trained on Wikipedia, that focus on modeling language. Indeed, we show through examples that the model can learn entity relations well and demonstrates strong use of contextual information.
The task needs to model about 5.3 million entity pages on Wikipedia. This vocabulary size is two orders of magnitude larger than in previous work that applies a Transformer model with full softmax loss (Devlin et al., 2018 Zhang et al. 2018 Sun et al. 2019). Other works, such as Zhang ctt al.) (2019) and [Soares et al. (2019), train a Transformer model with a large number of entities using sampled softmax, with either in-batch or in-example negative sampling. But shall show, sampled softmax, even with a large number of 128K negative samples, results in much worse quality.
'The cost of storing inverse look-up tables dominated by that of storing embedding tables long as ma < for an a-to-one hashing scheme, since the inverse lookups have total size O (7. " while the emhedding tables have size (dd? This is always the case in our experiments.
5

---

Under review as a conference paper at ICLR 2020
3.1 TASK
We take all the entity pages on the website en. wiw.ipeddiiiorg. For each page, we obtain the URL links to other Wikipedia entity pages. We only use "raw" links, i.e. links that explicitly appear on the page. We obtain 5,281,889 pages and 462,588,415 links. Since the Wikipedia site usually removes duplicates of links on each page, the distribution of pages is rather long tail. For example, the top 100 most frequent pages represent only 3.8% of the total links, and the top 10% most frequent pages represent about 60% of the total links.
We hold out 10% random entity pages for testing. For the training data, we apply masking similar to BERT-frie from each page, we take a random contiguous segment of entities, of length up to = 32, and mask 15% of the segment. The task is then predict the masked entities. We also apply the same input perturbation, where for the input, each masked out link is either replaced with a special [MASK] entity (with 80% probabilty). replaced with random entity (with 10% probability), or left unchanged (with 10% probability). For evaluation, we hold out (i.c. replace with the [MASK] token) one random entity from a random segment on test page. For quality evaluation, we use recall at k metric (abbreviated as rec k below), which represents the chance the held out entity is in one of the top l predictions.
3.2 MODEL
To apply Superbloom, we first create m hash maps from entities to hash tokens with a given hash density a. Each hash map is obtained by applying a random permutation to the vocabulary and map every consecutive a entities to the same token. This way we guarantee each hash token to have the same number of collisions α Special tokens [CLS], [MASK], [SEP]. are each mapped to m tokens with no collisions. For example we create [MASK]].... [MASKm.] tokens corresponding to [MASK].
We apply the hashing to the input and target, to map each entity to m tokens as described in Section 2 We then apply the Transformer model to the input to predict the masked tokens. Unlike in BERT, we do not use position embeddings, in other words, we treat the input as set instead of sequence. Since the input and output spaces coincide, we use the same hash functions and the same embedding matrices in the input and output layer.
We carry out experiments on both the full vocabulary as well as a smaller subset consisting of the able to train baseline model with large
top 500K entity pages. On the smaller vocabulary, capacity, with no hashing and no sampling, which useful for understanding the best achievable model quality.
We train all of our models on 16 Cloud TPUs. We use a batch size of 1024 for experiments with full vocabulary and 4096 for experiments with 500K vocabulary. All the experiments use the Adam optimizer (Kingma Ba, 2014), and use a decreasing learning rate sequence with inverse square root decay, and initial learning rate le-4 for the full vocabulary and 2e-4 for the 500K vocabulary. All the experiments have been run for more than million steps reach near convergence.
3.3 SUPERBLOOM IS MORE ACCURATE
We experiment with two models of similar size: one is baseline model (baseline) with full vo- cabulary size N equal to the number of entities; the other is Superbloom model (superblow oom) with heavy 50 to hashing. We set other hyper-parameters (such as the embedding dimension) so both models have a similar size, We also compare to a large model (samples) -aleeddssfmaax trained using sampled softmax. Table [ lists the hyper-parameters. of each model. Recall that denotes the number of collisions (1 if there is no hashing), d the embedding dimension, n. the number of attention heads, de the dimension of intermediate hidden layers, and L the number of transformer layers. In all of our experiments, we use two hash functions for Superbloom models. Hence their vocabulary size is 2N/a.
Thhe procedure described here is for simplicity. If we concerned with space, we may use some space efficient methods, for example perfect hash function (Fredman al. 1984).

---

Under review as a conference paper at ICLR 2020
model
d
RA
dr
L
#parameters
#samples
baseline
48
4
1024
12
248M
5.3M
sampled-softmax
512
8
2048
12
2.6G
128K
superbloom
50
768
12
3072
12
229M
200K
Table 1:
Model parameters. "#samples" lists the number of samples in the softmax loss computa- tion. For baseline and superbloom, since there is no sampling, this number corresponds to the full vocabulary, 5.3M and 200K, respectively. For sampled-softmin we use 128K samples.
Table 2 shows the recall metrics of the models. For the Superbloom model, the beam width to 20 (our experiments suggest that is sufficient to set k in order to achieve the best @ k metric, Appendix B for details).
model
rec 1
rec 10
rec @ 20
baseline
36.2%
63. %
68.2%
sampled-softmi
3.1%
36.2%
55.1%
superbloom 51.1%
72.3%
76.5%
Table 2: Recall metrics for different models.
The Superbloom model clearly outperforms, to a large extent, both the baseline and the sampled- softmax model. We note that the sampled-softmax model has much worse @ k than the other two models, and this gap is larger for smaller k. This is not surprising given the relatively small afford sample.
percentage (2.5% of negative examples
While the Superbloom model performs well overall, there is possibility that it devotes most of the embedding capacity the top entities, we plot the rec@ value as a function of label frequency. In Figure we show the mean rec for every 10 percentile bucket in terms of the label frequency. We can observe that Superbloom all the buckets. Another interesting phenomenon that most challenging labels are those in the 20 and 30 percentile. One possible reason is that they lack the higher predictability of the most frequent labels, and also the strong regularity of less frequent labels.
loses accuracy on the less frequent entities. To test this,
more accurate than the baseline
0.7
0.4
0.3
superbioom baseline
0.1
10
20
40
50
60
70
80
90
100
label frequency (percentle)
Figure 3: Rec@1 with respect to label frequency, starting from the most frequent labels.
Besides the high predictive accuracy, the prediction from the model shows strong semantic ability and context dependency. We show some examples of predictions in Figure 4 in Appendix E In one set of examples, we pair "Copenhagen" with different entities, and observe that the predictions change accordingly, depending on the context. Another observation is that despite the heavy hash- ing, there are almost unrelated entities in the top 10 predictions. The model even exhibits ability to perform certain analogy tasks (without being trained on such tasks) for example, given "Tunisia Tunis Thailand", it predicts "Bangkok" as the top result.

---

Under review as a conference paper at ICLR 2020
3.4 MULIT-LAYER TRANSFORMER IS IMPORTANT FOR SUPERBLOOM
Intuitively, given the large noise introduced by hashing, it is more important for Superbloom to multiple attention layers in Transformer "remove" the noise. To test this intuition, experiments with smaller vocabulary size of the top 500K entity pages (about 60% of the links). On this smaller vocabulary size, we can afford to run a full softmax model with larger embedding dimension.
model
Q
d
A
dp
#parameters
rec
rec 10
rec 20
baseline-11
256
1
1024
123M
51.0%
70.4%
75.5%
baseline-112
256
8
1024
12
132M
55.0%
73.7%
77.3%
superbloom-d256l
20
256
1
1024
13M
17.8%
35.8%
42.6%
superbloom-d38411
20
384
1
1536
21M
30.6%
52.9%
58.7%
superbloom-d2555
20
256
8
1024
12
21M
43.4%
60.1%
64.0%
Table 3: Model parameters and recall metrics.
We consider different embedding dimensions and model complexity. Table 3 lists the model pa- rameters as well as the recall metrics for each model. We observe that for the baseline models, the quality difference is small between models of different complexity. For example, rec 1 of baseline- 112 (55.0%) about 8% better than baseline-ll (51.0%). Since one layer Transformer close to bag-of-words (BOW) model, one may argue that it may be unnecessary to use a Transformer in this case instead one can use larger dimension BOW model to achieve similar accuracy.
However, for Superbloom models, the quality improves significantly with more layers. When in- creasing the number of layers from 1 (superbloom-d2566 increases from 17.8% to 43.4%. The multi-layer model also performs much better than the single layer model with the same size (superbloom-d3841) Note that previous work hashed vocabu- laries relies on BOW models, which are less expressive than even a single-layer transformer. This highlights one of our key observations that multi-layer Transformer models are more effective for working with hashed vocabularics.
to 12 (superbloom-d256112) rec@)
EXPERIMENTS ON NATURAL LANGUAGE DATA
In this section, apply Superbloom to natural language data. We consider large vocabulary that contains frequent unigrams and bigrams and use to tokenize the text, then apply a Bloom filter to reduce the vocabulary size. We show that despite high hash collisions, the model can achieve high accuracy on natural language data. Since many named entities appear in the large vocabulary, we observe that the model seems to make better predictions of named entities than the BERT model.
While each hash id can regarded as word piece in NLU model, there are important differ- ences between hash ids and word pieces. First, hashing causes random collisions, while wordpiece tokenization be viewed herence between words that share a word piece. As suggested by the experiments in Appendix [ random hashing with Superbloom digests may outperform coherent hashing. In addition, as every token in the large vocabulary is hashed, we do not have unambiguous anchors (such as the exact word pieces) help bootstrap the disambiguation process. Despite these differences, our experi- ments suggest that even with high hashing collision a = 40, the Transformer is capable of resolving, unhashing, the Bloom filter digest effectively and produces highly accurate predictions and mean- ingful embeddings.
special hashing scheme based the spelling there often co-
We construct vocabulary of size 1M by taking the union of standard BERT word piece vocabulary (~ 30K) with the most frequent unigrams and bigrams, and follow the same procedure in BERT to create training examples. For Superbloom, we apply random hash maps to the 1M vocabulary simi- lar to the approach described in Section 3.2 to ensure an even number of collisions. The Superbloom architecture is chosen to have a comparable model size to the baseline BERT model.
We compare four models: For the non-hashed baselines, dimension d = 256, and small model with = 64. And we have two Superbloom models with similar model sizes. We list the parameters in Table In Table 5 we list the recall metrics for the
have large model with embedding
8

---

Under review as a conference paper at ICLR 2020
model
d
n
dr
L.
#parameters
baseline-hôo
64
4
256
12
62.6M
baseline-h256
256
8
1024
12
254.4M
hash40-h512
40
512
8
2048
12
62.3M
hash20-h1024
20
1024
16
4096
12
246.3M
Table 4: The model parameters.
models. We observe that with comparable model size, Superbloom outperforms the baseline model in all the recall metrics, and the improvement is more significant for smaller model size.
model name
rec @ I
rec 10
rec@20
model name
rec
rec 10
rec @ 20
baseline-h64
28. 28.4%
44.9%
48.6%
baseline-h256
37.2%
57.4%
63.3%
hash40-h512
31.7%
48.3%
52.9%
hash20-h1024
39.2%
58.5%
64.5%
Table 5: Recall metrics.
Since many named entities are included in the larger vocabulary, the Superbloom model shows that it may have better "understanding" or representation of those entities. We show some anecdotal evidence in Appendix E by comparing predictions pretrained BERT and Superbloom model on some fill-n-thheblanks examples. The BERT model often predicts generic words, seemingly ignor- ing other named entities in the sentence. The Superbloom model, the other hand, can often fill in the blank with related entities.
CONCLUSION
Our experiments show that the multi-layer Transformer is effective for achieving high accuracy on hashed inputs, represented using Bloom filter digests. Besides applying it to tasks with large vocabularies, it also points to few interesting future research directions.
The Transformer model has been mostly studied in natural language settings and for sequence data. In our setup, we show that can work effectively with sets of hashed entities. We hope that by vestigating this simpler setup, it can help us better understand the properties of the Transformer. For example, due to hashing, each token is similar to words with multiple meanings, so its embedding can be viewed as a combination, possibly linear (Arora et al. 2018), of the embeddings of multiple entities. multi-layer Transformer model may provide a mechanism for iteratively filtering such noisy representations, using the context. It would be interesting to further study this mechanism.
While hashing adds noise to the learned representations, it also increase the flexibility of these representations when we hash multiple entities to the same token, the model is free to allocate the corresponding embedding unevenly among entities, which results in different effective embedding dimension for each entity. Such learned capacity allocation might be more efficient than using a fixed embedding size or frequency-based allocation. Of course, effective "denoising" model is pre-requisite for such an approach to work. Perhaps Superbloom, with strong denoising ability, can help further realize the potential of embedding models on hashed vocabularies.
REFERENCES
Sanjeev Arora, Yuanzhi Li, Yingyu Liang, Tengyu Ma. and Andrej Risteski. Linear algebraic struc- ture of word senses, with applications to polysemy. Transactions of the Association for Compu- tational Linguistics, 6:483-495, 2018.
Yoshua Bengio and Jean-Sébastien Sénécal. Quick training of probabilistic neural nets by impor- tance sampling. In Proceedings of the conference on Artificial Intelligence and Statistics (AIS- TATS), 2003.

---

Under review as a conference paper at ICLR 2020
Yoshua Bengio and neural probabilistic language model. Transactions on Neural Networks, 19(4):713-722 April 2008. ISSN 1045-9227.
Sénécal. Adaptive importance sampling to accelerate training of
Adam Berger. Error-correcting output coding for classification. In IJCAI-99; Workshop on machine learning for information filtering, 1999.
Burton H Bloom. Space/time trade-offs in hash coding with allowable enrors. Communications of the ACM, 13(7):422 426, 1970.
Ting Chen, Martin Renqiang Min, and Yizhou Sun. Learning k-way d-dimensional discrete codes for compact embedding representations. In Proceedings of the 35th International Conference on Machine Learning, pp. 854 863, 2018.
Amit Daniely, Nevena Lazic, Yoram Singer, and Kunal Talwar. Short and deep: Sketching and neural networks. ICLR Workshop. 2017.
Jacob Devlin, Ming- Wei Chang. Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04805.. 2018.
Thomas G Dietterich and Ghulum Bakiri. Solving multiclass learning problems via correccorecting output codes. Journal of artificial intelligence research, 2:263-286, 1994.
Michael L. Fredman, János Komlós, and Endre Szemerédi. Storing sparse table with 0(1) worst case access time, ACM, 31(3)538-544, June 1984. ISSN 0004-5411.
Joshua Goodman. Classes for fast maximum entropy training. In IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP '0/). IEEE, 2001.
Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint arXiv: 14/2.6981 2014.
Frederic Morin and Yoshua Bengio. Hierarchical probabilistic neural network language model. In Robert G. Cowell and Zoubin Ghahramani (eds.), Proceedings of the Tenth International Work- shop on Artificial Intelligence and Statistics, pp. 246-252. Society for Artificial Intelligence and Statistics, 2005.
Rico Sennrich. Barry Haddow, and Alexandra Birch. Neural machine translation of rare words with subword units. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics, 2016.
Joan Serrà and Alexandros Karatzoglou. Getting deep recommenders fit: Bloom embeddings for sparse binary input/output networks. In Proceedings of the Eleventh ACM Conference on Recom- mender Systems, RecSys 17, pp. 279-287, 2017.
Raphael Shu and Hideki Nakayama. Compressing word embeddings via deep compositional code learning. ICLR, 2018
Livio Baldini Soares, Nicholas FitzGerald, Jeffrey Ling, and Tom Kwiatkowski. Matching the blanks: Distributional similarity for relation learning. arXiv preprint arXiv: 1906.0318, 2019.
Fei Sun, Jun Jun Liu, Jian Wu, Changhua Pei, Xiao Lin, Wenwu Ou, and Peng Jiang. Bert4rec: Sequen- tial recommendation with bidirectional encoder representations from transformer. arXiv preprint 19Xiv:1904.06690 2019.
D. T. Svenstrup. J. Hansen, and O. Winther, Hash embeddings for efficient word representations. In Advances in Neural Information Processing Systems, 2017.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pp. 5198-5999088 6008, 2017.
Kilian Weinberger, Anirban Dasgupta, Josh Attenberg, John Langford, and Alex Smola. Feature hashing for large scale multitask learning. In ICML, 2009.
10

---

Under review as a conference paper at ICLR 2020
Yonghui Wu, Mike Schuster, Zhifeng Chen, Quoc V Le, Mohammad Norouzi, Wolfgang Macherey, Maxim Krikun, Yuan Cao, Qin Gao, Klaus Macherey, et al. Google's neural machine trans- lation system: Bridging the gap between human and machine translation. arXiv preprint (rXiv:6009.000 144, 2016.
Shuai Zhang, Tay, Lina Yao, and Aixin Sun. Dynamic intention-aware recommendation with self-attention. arXiv preprini arXiv: 1808 004006 2018.
Zhengyan Zhang. Xu Han, Zhiyuan Liu, Xin Jiang, Maosong Sun, and Qun Liu. Ernic: Enhanced language representation with informative entities. arXiv preprint arXiv: 2019.

---

Under review as a conference paper at ICLR 2020
A TRANSFORMER ARCHITECTURE
We briefly recall the Transformer architecture following Vaswani et al. (2077) Each transformer layer is function T R Rmaxd which transforms sequence of mn embedding in I to another sequence of mn embeddings the same space. Identifying the sequence 2i, with the matrix X E Rmnx xd we can write T as the composition T F o A, where
A is an attention function,
AA A(X)
Σ (IXQ))XXa) XVaWT.
where a {L...., A indexes attention heads, da S d an internal embedding dimension (usually da d)nx),, and for each a, Qa, Kay Va, W. Bdxds, Finally, |Raxn A(n))) is the row-wise softmax function, given by
exp(Yr)
(Y) E exp(Ya)
One interpretation of the attention function is that forms the i-th output embedding by taking a convex combination of input embeddings weighted by the softmax weights, followed by low-rank transformation Va W. Raxd
F is a fully connected feed-forward network given by F(X) ReLU(XU, b.)UU b2. where U, E gdxdr for some dp 2 d.
residual connection and layer normalization are also applied at each stage A, F.
B THE QUALITY OF BEAM SEARCH
We investigate the effect of beam search width (parameter B in Algorithm on model quality. Table [6] shows rec @ k for k 1, 10, 20 for different beam widths B, using small number of test examples, for the Superbloom model described in Section 3.2 In all our experiments, run approximate inference with one step.
We observe that while the quality generally increases with increased beam width, the increase in rec @ l is only marginal when B 2 k. Thus, to obtain highest rec @ k, is sufficient to set the beam width to B = k.
beam width
rec
rec@ 10
rec
B=1
53.0%
56.0%
56.0%
B=10
53.2%
68.2%
69. 19.1%
B=20
53.2%
97.9%
71.0%
B=100
53.2%
67.8%
71.5%
Table 6: Recall metrics different beam width.
C BEAM SEARCH WITH GENERAL SCORE FUNCTIONS
The beam search algorithm described in Algorithm I can be generalized any ranking function that is increasing, in the following sense.
The output of the model defines, for each candidate 80, vector of scores ())(nn()))))>...... To sort the candidates, one can define an aggregated score yss) (1;()))))) for any function T IR. that induces total ordering over m One natural assumption to require of is that it be increasing, in the sense that if p ž p' element-wise then c(p) 2 c(p'). This holds for
AA minor difference with the original Transformer model is that operate on Rmaxd instead of Raxd since have embeddings for each element the sequence.
12

---

Under review as a conference paper at ICLR 2020
c(p) E, log Pj (used in Section 2.5 but also includes much larger class, e.g. c(p) miny Pj c(p) max, Pj- The beam search Algorithm can be immediately generalized any such function. The only required change is to replace the condition line 7 (7(s*) Σj log(p")) with 7(8") 2 c(p"). To prove correctness, one needs to verify that the optimality certificate holds in this general case, i.e.,
Lemma 1. (s) c((p, (1) (s))))), where e is increasing in the sense defined above, and let p", 5 be as defined in Algorithm Then,
Va $ St 7(5) S clp)).
follows from the lemma that the algorithm can terminate whenever 7(s*) 2 c(p"), since 7(5*) 2 (s) for all E 5hh (by definition of s*) and for all s Sh (by the lemma).
(s: pi (,((n(s)) 2 }² then the complement of 5h is the set {s p);(()sss)) < Proof. Since 5h (,{s:
p) Thus, since increasing, it follows that for all s Sh (n,))(, S c(p"), as claimed.
D COMPARISON OF DIFFERENT HASHING SCHEMES
We have used random hashing functions in Superbloom. One natural alternative is "coherent" hash- ing, in which we map similar entities to the same hash bucket. potential benefit of coherent hashing is that it may use embedding capacity more effectively by sharing it among similar entities. However, the downside that it becomes difficult to distinguish those similar entities.
To create a coherent hashing function, we first run co-occurrence factorization algorithm and then group similar entities together using the following procedure, designed to guarantee equal-sized hash buckets. For each entity, in decreasing frequency order, we compute the nearest neighbors (scored using cosine similarity), then create hash bucket that includes the elements and its -1 nearest neighbors which have not been already assigned a bucket. When creating a second coherent hash function, add the constraint that any pair of elements that share bucket for the first hash function cannot be assigned to the same bucket the second hash. This ensures that no two elements have the same collision in both hash functions.
We carry out the experiments on the data set with smaller vocabulary (500K). We train different models that all use two hash functions, with the following configurations: both random, one random and one coherent; and both coherent. We also use different hashing densities a = 10 and a = 20. All the models have the same byper-parameter as the superbloom-112 model in Section 3.4 The results are given in the following table.
model
ax
#coherent hashing
token rec
entity rec I
hash hash10-00
10-00
10
0
36.32%
52.50%
hash 10-01
10
1
38. 19%
50.20%
hash10-11
10
2 38.55%
34.70%
hash20-00
20
0
33.39%
43.70%
hash20-01
20
36.98%
41.10%
hash20-11
20
2
37.65%
30.20%
Table 7: Random hashing versus coherent hashing.
We observe that with coherent hashing, we get higher accuracy for predicting hash tokens but lower accuracy for predicting entities. And the entity @ significantly lower when both hash functions are coherent. This indicates that with higher coherence, it becomes increasingly difficult for the model to make finer distinctions between similar items.
13

---

Under review as a conference paper at ICLR 2020
E EXAMPLES OF WIKIPEDIA ENTITY PREDICTIONS
Examples of pairing "Copenhagen" with different entities. The predictions vary according to the context, from Danish cities, to major European cities, to Danish royalty, and Danish culture. There a one unrelated result (underlined), which disappears the presence of additional context.
Copenhagen [MASK]
Denmark Oslo Stockholm Paris Berlin Aarhus Danish Janguage University-of.Copehhhe Sweden Copenhagen
Copenhagen Aarhus [MASK]
Denmark Odense Copenhagen Aalborg Aarhus Oslo Malmö Max. Wilms Stockholm Esbjerg
Copenhagen Paris [MASK]
Berlin Denmark London Oslo Rome Vienna Stockholm New_York.Cit Brussels Hamburg
Copenhagen Dynasty [MASK]
Denmark Margrethe II of Denmark Danish language Copenhagen Catholic Church Rome Chris- tian of Denmark Jutland When We. Wake Up Crowwn CriceePrince Denmark
Copenhagen Dynasty Danish [MASK]
Denmark German language Margrethe of Denmark hagen English language Princess Benedikte of Denmark
Catholic Church Danish language
Copen- Fred-
Denmark Christian___ooDDeeee _eemmaama_
2. Examples of Jazz musicians. These relatively long and rare entities would not appear in the vocabulary of a word piece model.
Miles Davis [MASK]
Jazz Columbia Records Miles Davis
John Coltrane
Dizzy Gillespie
Bill Evans
Album
Sonny_Rollins AllMusic Charles_Mingu
John_Coltrane [MASK]
Miles -Dvis AllMusic Jazz A.Lov_Supremn.
Rolling_Stonne
Elvin
Albert
Tenor saxophox New_York York_City Drum
Miles_Davis John_Coltrane [MASK]
Jazz Charles_Mingus Album AllMusic
Miles Dizzy-Gilleppi Thelomious
Sonny Rollins Charlie Parker Bill Evans
3. Example showing that the prediction is the set union if two entities are not related.
Miles Davis Thailand [MASK]
Vietnam Bangkok Japan Miles_Davis Cambodia Malaysia Jazz Indonesia Thai, Thai_ language Brazil Myanmar Rock_music
John.Coltrane
4. Examples for completing location analogy task!
Texas A Texas Florida [MASK]
Miami Houston Orlando, Florida Florida Dallas Jacksonville, Florida Fort Lauderdale, Florida Floridd Tampa,FForida (ecorgia_UU.S._tttt Fallahassse,_Floridaa Se..Peeerbuurg..Forrf
Tunisia Tunis Thailand [MASK]
Bangkok Philippines Montcau Tokyo Malaysia Singapore Indonesia Pattaya Vietnam Thai languae
Figure 4: Examples of Superbloom model predictions. For each example, we output the top 10 predictions of the model (computed using Algorithm [ with beam width B 10). The entity names shown here are obtained by removing the prefix "https:/en.wwiiipediai wikipedia.org/wiik. from the entity URL.
14

---

Under review as a conference paper at ICLR 2020
F EXAMPLES OF NATURAL LANGUAGE ENTITY PREDICTIONS
Miles Davis is Jazz musician, he similar [MASK].
BERT: jazz himself beethoven him davis chopin bowie williams jones
baseline-h256: miles.davis john_ coltrane bill evans charlie charlie.parker louis armstrong sonny_rollim rollins keith_jarrett thelonious_monk jazz duke_ellington hash20-h1024: miles_davis john coltranee charlie_parker thelonious -iilleeil evvnne billie.holiday duke_ellington humans is louis_armstrong
Empire state building is an iconic site of [MASKI] close to [MASK2].
[MASKI]
BERT: architecture chicago manhattan downtown pittsburgh art philadelphia history washington
america
baseline-h256. architecture modern_art contemporary aart modem.architectum national new york art its day historical significance the city
hash20-h1024: the city new.york lower manhattan manhattan the theghheihboroood downtown stre_street the_an area harlem architecture
[MASK2]
BERT: downtown it chicago philadelphia rome london broadway manhattan chinatown campus
baseline-h256: downtown downtown, dowssuow city_hall new_york the_city times_squaa columbia unniersitt san sfannniccsoo philadelphia the-pentagon
hash20-h1024: central park city hall times square wall street union station broadway lower manhattan the pentagon ffth-avenue carnegie hall
Figure 5: Natural language fill-in-the-blee examples. BERT is the base BERT model in Devlin al. (2018); bascline-h256 and hash20-h1024 the Superbloom models with 1M vocabulary, with model parameters listed in Table
15


Reviews:
[{"review_id": "rkeOdb0TFS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nFor 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\n\n    $\\ell(y; \\mathbf{P}) = \\sum_{i=1}^{m} \\log(p_{i, h_{i}(y)})$,\n\nwhere $p_{i, h_{i}(y)}$ can be understood as the element of $\\mathbf{P}$ corresponding to the $i$-th hash of token $y$.\n\nAt 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:\n  a) What happens if two tokens' hashes collide all $m$ times?\n  b) How were hash functions inverted and what was the cost of doing so?\n  c) How does the test-time throughput of the proposed compare with that of alternatives?\n\n\nQuestions:\n  - Did you compare against different approaches to sparse softmax, such as LSH-based methods [1]?\n  - What was the impact of approximate vs. exact inference and which was used during experiments?\n  - 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$?.\n\n\n[1] \"Deep Networks With Large Output Spaces\", Vijayanarasimhan et al, 2015", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HJl9otEe5H", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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. \n\nWhile 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. \n\nThe 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.\n\ndetailed comments:\n- 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. \n\n- 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.\n\n- I found the description of the link prediction task (section 3.1) rather cryptic: \n* \"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?\n* '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.\n* 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.\n\n- For the natural language task: \n* \", 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.\n\n- \"We hold out 10% random entity pages for testing. \" -> is there a validation set? How do you choose the hyper parameters?\n\n\nminor comments:\n- \"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\n- 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?)", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "H1gKSJxnKH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nThe 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.\n\nI 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.\n\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}]

Author rebuttal:

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