Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 8: Accept
review_content: This manuscript presents a number of algorithmic techniques to reduce the computational and space complexity of Transformer, a powerful and very popular deep learning model for natural language processing (NLP). Although Transformer has revolutionized the field of NLP, many small groups cannot make a full use of it due to lack of necessary computational resources. As such, it is very important to improve the space and computational complexity of this popular deep model. The techniques presented in this manuscript seem to be very reasonable and the experimental results also indicate that they are effective. My major concern is that the authors shall present more detailed experimental results. In addition to bits per dim, it will also better if the authors can evaluate the performance in terms of other metrics. 
review_title: Official Blind Review #2

final_score: rating: 8: Accept
review_content: This paper presents a method to make Transformer models more efficient in time and memory. The proposed approach consists mainly of three main operations: 
- Using reversible layers (inspired from RevNets) in order to prevent the need of storing the activations of all layers to be reused for back propagation; 
- Using locality sensitive hashing to approximate the costly softmax(QK^T) computation in the full dot-product attention;
- Chunking the feed-forward layers computations to reduce their cost.
This approach is first applied to a toy dataset to analyze its complexity, then tested on enwik8 language modelling task and imagenet-64 image generation task for ablation study and performance assessment. 

The problem approached by the paper is interesting and the proposed approach is novel to the best of my knowledge. The paper is well structured and clearly written a part from some small typos (see minor comments below).   

While the analysis of complexity is sound and convincing, and the fact of being able to train larger Reformers is very interesting, I have some questions and concerns about the approach and experiments. 
- Effect of reversible layers: It is clear for the experiment of Imagenet64 that the effect is negligible, but the experiment on enwik8 in the paper seems unfinished. Did the authors manage to finish the training, and does it confirm the observation? 
- Sharing QK: I am a bit confused about the effect and usefulness of this operation. Can the authors comment on why it is needed for LSH attention? It seems to me that the same operations can be achieved with different Q and K. Indeed, doing so, the authors slightly reduce the capacity of the model. The observed non-significantly decreased performance can be an effect of using only 3-layers. This may explain why the results reported for larger models in figure 5 show higher bpc than similar size state of the art models.
- Time per iterations: Can the authors report the time per iteration for the larger hash rounds (8 and 16) that are closer to full attention? For the highest reported number (4), from a quick and not precise look at figure 4, it seems that the performance achieved by the proposed method after 140k iterations is achieved by the full attention after ~40k iterations. The gain in time per iteration for this particular number of hash rounds can be lost by the loss in performance. 
- Can the authors detail how they chose the hyperparameters of their approach? e.g. the size of hash buckets, the distribution used to generate the random matrix R .. 
- The reported results can be made stronger by reporting average/error bars across several trial to show consistency. 

Minor: typos: 
Dimension of matrix R [d_k, d_b/2] -> [d_k, b/2]
Last paragraph of page 6: state of these art -> state of the art

——————————————— 
After rebuttal:
I have read the authors answer, and found they addressed my concerns. I'm therefore increasing my score.
review_title: Official Blind Review #1

final_score: rating: 6: Weak Accept
review_content: This paper presents an attempt to reduce the memory complexity of Transformers. The authors call their model the Reformer. It presents a LSH based self-attention mechanism, along with reversible adaptation of Transformers. The Locality sensitive hashing scheme reduces complexity from L^2 to L which is pretty neat. 

Tackling the quadratic complexity of self-attention is indeed an important and nice direction. I think the LSH based attention quite novel and is a natural solution to reducing the complexity of the self-attention module.  However, I think the technical description could be improved as the current form is quite confusing and difficult to parse.

The experiments are a little on the weaker side. Authors presented results on imagenet, enwiki and a synthetic task. I am mainly concerned if the Reformer works on tasks such as machine translation or other NLP tasks. The paper does not present much evidence that the effectiveness of LSH is broad and versatile.

My current vote is a weak accept, based on some preliminary understanding and the general novelty of the idea. 

I do have some questions/issues/comments:

1) Given that there is some form of QK sorting, how is it possible to mask the future? Is this because tokens are sorted within buckets?
2) Can the authors clarify what "Causal masking on the Transformer is typically implemented to allow a position i to attend to itself." mean?
3) I'm a little confused about how the sorting is being done. Can this be done in an end-to-end differentiable manner?
4) Can the authors present some results on other tasks? While neat, I think other tasks (e.g., MT or QA) can be investigated to further ascertain that the LSH attention works well. Current experimental results are not too convincing.

review_title: Official Blind Review #3

Meta-review: Transformer models have proven to be quite successful when applied to a variety of ML tasks such as NLP.  However, the computational and memory requirements can at times be prohibitive, such as when dealing with long sequences.  This paper proposes locality-sensitive hashing to reduce the sequence-length complexity, as well as reversible residual layers to reduce storage requirements.  Experimental results confirm that the performance of Transformer models can be preserved even with these new efficiencies in place, and hence, this paper will likely have significant impact within the community.  

Some relatively minor points notwithstanding, all reviewers voted for acceptance which is my recommendation as well.  Note that this paper was also vetted by several detailed external commenters.  In all cases the authors provided reasonable feedback, and the final revision of the work will surely be even stronger.
Decision: Accept (Talk)