Large Transformer models routinely achieve state-of-the-art results on a number of tasks but training these models can be prohibitively costly, especially on long sequences. We introduce two techniques to improve the efficiency of Transformers. For one, we replace dot-product attention by one that uses locality-sensitive hashing, changing its complexity from O(
, where L is the length of the sequence. Furthermore, we use reversible residual layers instead of the standard residuals, which allows storing activations only once in the training process instead of N times, where N is the number of layers. The resulting model, the Reformer, performs on par with Transformer models while being much more memory-efficient and much faster on long sequences.
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.