Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper proposes a new self-attention mechanism that generalizes attention to a graph and takes into account connections with an intermediate node. The authors develop the intuition and frame their work in the context of prior work. They then perform experiments that show that their attention mechanism does indeed help the model perform better on more challenging linguistic tasks.
strengths_and_weaknesses: Originality: The idea has roots in triplet attention and Graph Convolutional Networks which the authors mention. It does appear to be an original application to my knowledge.

Clarity: I like how the authors develop the intuition with the computer-pencil example. I was a little confused for some time because I expected to see a direct edge, but I think the authors meant they are connected only through the intermediate book token? The formal definitions and algorithms are clearly defined and motivated;

Quality: Experiments are well done. I think there could be more tasks and performance benchmarks, though.

Significance: It's interesting to see that there does indeed appear to be better performance in the more challenging linguistic tasks, so I think the authors' intuitions seem to bear out and the method is efficient enough to be generally usable.
questions: They mention that their method increases computation by 30% or 15% depending on the configuration. That seems equivalent to adding an additional 1-3 layers to BERT. Does their method still perform well against a bigger BERT?

Since their attention mechanism captures higher-order relationships, does it do well with on question-answering tasks that require multi-hop reasoning?

What is the relative RAM requirements of their mechanism? How does it scale with L? The authors only address computation.
limitations: Possibly, their method becomes harder to apply on longer sequences.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper proposes a method to model jump attention in sequence data (e.g., in the sentence “Jack is the father of John and John is the brother of Mary”, we have a jump connection between Jack and Mary using the stepping stone of John). Specifically, the authors add a one-layer GCN (without activation function) after a self-attention layer. The construction of the graph is based on the attention score (QK). In multi-head attention, parts of the heads are applied to the jump attention while the remaining preserve, making the network able to capture both first- and higher-order connection. To reduce parameters, the parameters of the GCN is merged into parameters of the self-attention layer. To reduce computation cost, the authors apply an existing sparsity measurement. The method is validated on GLUE and SQuAD comparing with baseline models and a recently proposed A3 method.

This is an interesting work with clear and convincing motivation, and it also reads smoothly. It is true that entities in texts may have relations without direct connection. The pivot entities (or say, stepping stones) become important under this case. Though GCN itself is not new, the definition of high-order connection (Definition 3.1 and Section 3.2.3) and the parameter-merging step in Eq (5) is novel. The authors find that the two parameter matrices of GCN and Attention can be merged (because they are both linear transformation).
strengths_and_weaknesses: Strengths:

+ Good readability. Same case study across the paper.
+ Convincing motivation of jump connection.
+ Novel method to combine GCN and Self-Attention.

Weaknesses:

- Lack information of comparison with related work.
- Experiments on SQuAD have no results of the competitor A3.
- Improvement is limited.


UPDATE:
The authors' responses address my main concerns, which should be included in the revised version.
questions: I have some questions for you. Correct me if I’m wrong:
1.	The definition of the adjacency matrix A. From Eq (2), we can see if S_{ij} * S_{kj} is greater than the threshold \rho, then i and k are considered as connected nodes. But this definition is a little bit different from Definition 3.1 saying both S_{ij} and S_{kj} need to be greater than \rho. Can you explain more on this point?
2.	In the combination of GCN and Self-Attention, the equations seem to omit the activation function of the GCN. Is it merged to the activation function of the later Feed-Forward Net? Or the ignoration makes no significant difference? It is better to elaborate the point clear in the method.
3.	What’s the effect of tuning the hyper-parameter \rho?
4.	The explanation of Fig. 4. I think it will be better if the definition of connection can be linked to some objectives or downstream tasks because it is hard to tell directly how “hit” is related to “Kate”. Also, in this example, it is unclear when we need jump connection or just first-order connection. For example in “The dog bite Kate”, is the “dog” directly related to “Kate” or they need a stepping stone “bite”?
5.	In Line 272, “almost all the tasks’ scores first increase then decrease” may not hold since in Table 4, the main trend is just decreasing. I think it is better to add a RoBERTa model without JAT for comparison.
6.	How slower it will be if not applying the sparsity measurement is shown in Fig. 5, but I wonder how much the performance will drop/increase.

limitations: Minor suggestions:
1.	The writing can be further improved. There are typos in:
a)	Line 121, “significant \delta” should be “significance \delta”.
b)	Line 162, “is a symmetric matrix contains input” should be “is a symmetric matrix containing input”.
c)	Line 176-177, “for encourage the attended items becomes” should be “for encouraging the attended items to become”.
2.	The captions of Fig. 1 and Fig. 2 have large overlaps with your content. You can consider shrinking the captions to leave more space to your methods or related work.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: In this work, the authors found that the high-order self-attention did exist in the dot-product computation but it was too weak to contribute much to the attention layer’s output. Take two sentences “Book costs more than pencil.” and “Book costs less than computer.” as an example. “Computer” never attends to “pencil” until they were both compared with “Book”, thus “Book” is the “stepping stones” in creating high-order attention between “computer” and “pencil”. In order to capture such high-order dependency in Transformer model, this paper proposed Jump Self-attention (JAT), and the main contribution can be summarized as:

1. The authors proposed the JAT through the jump aggregation and high-order dependencies’ propagation without additional network parameters, and the efficient variant avoided the extra computation cost.
2. The authors proposed the higher-order variants of JAT and the masking strategy to allow its interchangeable usage with the common self-attention on the pre-trained models.
3. The experiments were conducted on ten different tasks to examine the effectiveness of the proposed methods. Results demonstrated the success of JAT in achieving state-of-the-art performance.
strengths_and_weaknesses: Pros:
1. The motivation of capturing high-order dependency was reasonable and very intuitive and the example they provided could help clarify concepts.
2. This paper proposed the idea of capturing high-order dependency by measuring the similarity between different queries and keys, and then used the GCN to enhance this kind of connection. The idea is novel, and the result showed that the mothed could outperform canonical self-attention.
3. This study designed several ablation studies to explan how their method worked. The run-time comparison was used to show the effect of efficient variants.

Cons:
1. They said that they were inspired by the pieces moving of English Draughts, although they spent some space explaining the rules, However, this game is not so well-known, and may still cause some confusion.
2. Although the efficient variants could indeed reduce the computation cost but still brought extra computation relative to the vanilla Transformer. And, the improvement from efficient variants to original self-attention was limited.
3. This paper mentioned “miracle heads” several times, but the authors didn’t do comparison among these related methods. The authors may show the performance and computation cost of finding miracle heads.
questions: The paper is clearly written. But, the game the authors mentioned was not popular.
limitations: The improvement is limited when compared with the related works.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper proposes Jump self-attention(JAT), which enhances first-order(i.e. dot-product of two hidden states) self-attention by running GCN
on its attention score map to capture high-order statistics. JAT can be interchangeably used with the canonical self-attention, and could be further generalized from second-order to higher orders. An efficient variant of JAT is proposed to avoid the extra computation cost. Experiments on GLUE and SQUAD show that JAT significantly increase the performance of BERT/RoBERTa-base with only 15% extra computation and no new parameters.
strengths_and_weaknesses: ### Strengths
* This paper proposes novel and simple module to enhance performance of canonical self-attention with no new learnable parameters.
* Experimental results show significant improvements over BERT/RoBERTa baselines, and authors provide ablation study on how to 
tune the hyperparams.


### Weaknesses
* Writing need improvement. The method part is quite hard to follow.
* There is no experiments on BERT/RoBERTa-large models.


I'd like to increase my score if the two weaknesses above are addressed.
questions: ## Notations
Definition 3.1 is confusing: are vector inputs x_i, x_j, x_k fixed vectors? If they are
fixed, what does `Pr[\dot]` mean? If they are random varaibles, what's the distributions?
The same question applies to weight matrix W_q and W_k.
 
Section 3.2 is very hard to follow. For example, what is `adjacency matrix A` in #L159? 
If it's the same matrix defined in Eq.(3), it's better to introduce that you're going to compute its components
earlier instead of letting reader find it themselves after 10+ lines.
I think a more detailed explanation of brute-force
method in #L151~#L153 could help readers get better understanding on motivations
and the derivation of matrix A in Eq.(3)

There are two `BERT-JAT(ours)` and two `RoBERTa-JAT(ours)` in Table1, what's the difference between them?

## Experiments
An assumption of mine is that two layers of one-order attention 
could simulate a single layer two-order attention. Therefore I'd like
to see more experiments where authors use BERT/RoBERTa-large and 
test whether the improvements of jump-attention still exist. 

limitations:
review_title: null

Meta-review: metareview: The paper presents a novel architecture named jump self-attention to capture the high-order statistics in transformers. Specifically, the model builds an GCN layer on top of the attention layer, based on the attention scores. The reviews are generally positive. The major concerns are around the significance of the improvement comparing to the original softmax. The authors may want to improve this part more in the final version. 
confidence: Less certain
Decision: Accept