Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The authors propose a low-rank attention mechanism named DBA. Several experiments have been conducted to validate the proposed method's effectiveness.
strength_and_weaknesses: Strength:
* The technical details are presented clearly and with details
* The experiments include state-of-the-art methods as baselines
* The paper is structured well and easy to follow

Weakness:
* The novelty needs to be further justified
* More ablation studies would be ideal to better understand the model
clarity,_quality,_novelty_and_reproducibility: Overall the technical details are sufficient and the experiment results look promising. It would be better if the authors can further justify the novelty of the proposed method.
summary_of_the_review: My major concern is about the novelty of the proposed method. It would be great if the authors can make a table to compare the proposed method w/ other low-rank based attention modules on the their differences and why the contribution is not incremental. The authors do mention that the the proposed projection is not pre-determined, it would be better if the authors can better motivate why this pre-determination is not ideal and validate this from experiment results.

The authors list the hyper-parameters used in Sec. A.2, I wonder how these parameters may affect model performance. It would be better if the authors can conduct more ablation study to analyze the robustness of the proposed approach.

I also suggest the authors to describe how many seeds/repetitions each model has been trained in the experiments and report the accuracy variance.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper presents a new low-rank method, called DBA, to approximate the attention mechanism used in transformer layers. It has two main differences from previous approaches:

1. DBA maps the input sequences $Q, K \in \mathbb{R}^{n \times d}$ to shorter sequences $Q', K' \in \mathbb{R}^{d_p \times d}$ via a linear transformation that captures information from the input matrix itself, e.g., $Q' = \phi(WQ^\top)Q$, where $W \in \mathbb{R}^{d_p \times d}$ are learnable parameters. 
2. DBA also projects queries and key vectors to lower dimensionalities ($d_{in} \ll d$)

Results show that DBA is faster and consumes less memory than related approaches while achieving strong predictive accuracies on several tasks.


strength_and_weaknesses: Things that I liked in this paper:

- The authors explain all the matrix transformation steps in detail, making the linear algebra math easy to follow in section 3.1.
- The idea of using information about the input sequence before projecting it to a shorter sequence.
- The results are impressive.

However, there are many things that I disliked:

- The overall method is not novel, and most central ideas were proposed in previous approaches (Linformer and Performer).
- The introduction is very repetitive.
- Section 3.2 seems unnecessary and confusing. 
- The experimental section is uninformative, especially for sections 4.3 and 4.4.
- Some math terms are not defined. For example, what is "Linear" in Equation 18? Is it needed? What is the actual function used as $\psi$?


clarity,_quality,_novelty_and_reproducibility: Quality:
- The results in Tables 3 and 4 are very close to the ones obtained by related approaches. It is hard to assess the quality of the results without confidence intervals.

Clarity:
- It is unknown how DBA was applied for dynamic length inputs in section 4.3.
- The writing is casual in some parts. E.g., "A lot of studies ..." or "... by digging into the ..."
- Overall, I think the writing can be improved.
summary_of_the_review: This paper proposes a new efficient alternative to attention in transformers. The proposed method achieves impressive results on several tasks while being time and memory efficient. However, I believe this paper can be improved in terms of clarity and quality, especially regarding the experimental section.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposed to learn the projection matrices for reducing the dimension of intermediate matrices in Transformer models and achieves significant speedup while achieving better performance than previous efficient attentions.
strength_and_weaknesses: Pros:
- The learnable projection in the paper is novel and squeezes the computation not only in terms of sequence length but also in terms of hidden dimension. It is encouraging to see that simply choosing d_p and d_in to be fixed suffices for achieving good performance.
- The empirical results are promising compared to other linear attention-based models.
Cons:
- The presentation in Section 3.1 is a little confusing because the W_r' and W_c' depend on the input QK, while Equation (4) makes readers feel they are given.
- Table 2 in the paper is a little misleading because the methods are not sorted by any meaningful order (e.g., Avg)
- (Minor) the performance cannot be comparable with new models based on state-space models. It might be helpful to apply similar ideas as this paper to those models to achieve further gain.
clarity,_quality,_novelty_and_reproducibility: The presentation needs to be improved, and please refer to the cons.
summary_of_the_review: In summary, the method in this paper is novel and interesting, while some minor modifications are needed to clarify the paper.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This work suggests that the attention matrix, a key module in Transformer but computationally inefficient, can be approximated by low-rank matrix multiplications. Given the arguments, the authors proposed a new efficient Transformer variant using random projections. Experiments, including popularly used LRA benchmarks, are conducted to analyze the empirical performance of the model with comparisons to several baselines.
strength_and_weaknesses: I believe the paper is far below the paper acceptance threshold and here are several critical points that needs to be essentially addressed.

[Writing Quality]

Thr writing is rather poor and there are plenty of mistakes. I list some of them as below but there are much more in the paper.

1. In most places, term "the" is not correctly used. 
2. In section 3.1, what is non-destructively?
3. In section 3.1, what is conditional extropy?
4. In section 3.2, why you call Johnson–Lindenstrauss lemma as "JS lemma"
5. In section 3.2, "an d \times d matrix"

[Math]

A critical flaw occurs in equation (6). It is ok to assume that QK is a low-rank matrix. However, P = softmax(QK), and softmax is a non-linear operator. There is no guarantee that a low-rank matrix passing through a non-linear operator is still a low-rank matrix. Furthermore, in practice, for the softmax function, P is usually a high-rank function. I recommend the authors have a try. Given this, we cannot get P=WrP'Wc, where all of them are low-rank.

Note that in any case, you can always use JK lemma and random projections. But such an analysis has already been used in Linformer.

[Experiment]

The author missed important effcient Transformer S4 ("Efficiently Modeling Long Sequences with Structured State Spaces"). In all of the LRA tasks, S4 is roughly better than the proposed DBA for 25 points. I have little reason to vote a paper for acceptance given the significant performance gap.


clarity,_quality,_novelty_and_reproducibility: As I described above, I found the paper is not easy to read given the writing mistakes (clarity), has mathematical flaws in the analysis (quality), leads to poor experimental results compared to SoTA (novelty).
summary_of_the_review: I believe proposing efficient Transformer is essential but the current quality of the work (writing, analysis, empirical results) are not ready to publish in the venue, and I recommend rejection.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The authors replace the attention mechanism with DBA (dynamic bilinear attention). It replaces input sequences with shorter ones and also projects queries and key vectors to lower dimensionalities. The projection matrix is computed using cross-attention type layer, which is potentially interesting.  The numerical experiments show that this architecture is quite competive.


Weaknesses: The paper is not well-written. The algorithm is not summarized anywhere, so the reader has to guess how the layers is actually implemented (i.e. how Q_DBA is computed? how project matrix is computed? What are learnable parameters?) 
The derivation of the formulas in Section 3.1 has no mathematical meaning (i.e. the notation basis_r, basis_c of a matrix), as well as "can be represented losslessly", but then the formula (6) follows ("in practice we could form"), which is just the compression of a low-rank matrix (makes sense), but it is not a derivation, and it has no connection to information theory. Basically, formula (8) is a different formula, can be used as a starting point, but please, don't call this derivation from a theory. These are just completely different formulas, you can not simply exchange softmax & matrix multplication. The formula (9) has a standard (awful) 1/eps^2 dependence on the error, so again you can use this as a "proof".  For the typical sizes, the error of approximation will be more than 100%. As a motivation it is ok, but all the text has equality (not even a single approximately equal sign). 


justification_for_why_not_higher_score: The main concern is writing and presentation. You can not write equality and claim information theory proof for something that does not hold (exchanging matrix multiplication with softmax). I think, this has to be completely rewritten.
Decision: Reject