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 presents several new self-attention variants that extrapolate better to longer contexts. The proposed KERPLE self-attentions are closely related to ALiBi self-attention. In the ALiBi method a linear bias proportional to the distance between token positions n and m is added to the pre-softmax attention score for all position pairs n and m. The paper’s contribution is to consider non-linear bias terms: a logarithmic one and a power-law one. The theoretical justification of these specific terms is that with them (as well as with ALiBi) the pre-softmax attention computation can still be seen as kernel computation. 

The key empirical result is that the log version of KERPLE attention achieves better log-likelihood on 3 language modelling tasks in a challenging extrapolation regime (train on length 512, test on 16K). The improvement upon ALiBi is very clear, the improvement upon T5-style bucketing is smaller, but noticeable. 
strengths_and_weaknesses: Strengths
- well-written paper with a clear empirical result 
- nice connections to prior (ALiBi and T5 bucketing) and kernel literatures
Weaknesses
- it would be good to see how the presented extrapolation results compare to training with longer contexts. Do we observe extrapolation, or just slower degradation?
- limited improvement upon T5 bucketing 

questions: Does the attention before softmax really have to be a kernel? My understanding is that an attention mechanism could be trained even if the underlying function is not a kernel. 

limitations: Not sure if the paper's results can really be called "extrapolation".
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: The paper proposes a family of relative position biases that can be viewed as shift-invariant CPD kernels. It proves that in the presence of softmax normalization, there is an equivalent formulation based on an inner product of position representations that lie in a latent feature space. Experimental results show that one kernel in this family results in a relative attention scheme that successfully extrapolates to longer sequences than were seen during training, whereas prior approaches to relative attention have more limited or even no generalization capability for longer sequences.
strengths_and_weaknesses: The theoretical portion of the work presents a sound argument for why CPD kernels used in the context of softmax-normalized attention have an equivalent formulation in terms of inner products of position embeddings lying in a latent feature space. This family of kernels maintains the familiar structure of attention, as well as shift invariance, and the paper provides examples of kernels that lie in this family. Separately, the paper shows that 3-para-log variant within this family leads to models that effectively generalize to longer sequences, whereas prior approaches either do not generalize at all or have degraded generalization once the sequence length at inference is sufficiently large.

One potential concern regarding length extrapolation is that it's not clear whether the relative attention scheme in question could be exhibiting a windowing effect where all attention past a certain distance is effectively prohibited, and that cutoff length is smaller than the sequence length seen during training. Local attention based on sliding windows could actually be effective for dealing with longer sequences, because the effective context would still grow with each layer applied (like in Transformer-XL). As far as I can tell none of the baseline methods use sliding windows; they all seem to attempt to allow attention between very distant tokens with some extrapolation for what the relative bias should be. In that sense the baselines used could exhibit a failure mode that windowed attention simply does not have. The results would be stronger if they compared the proposed method to a window-based approach.

Another potential weakness of the paper is that the theoretical examination of CPD kernels and the empirical results on length extrapolation don't have the strongest of connections. The implementation of relative attention can use any relative biasing scheme of the form $bias = f(m - n)$, for any arbitrary function f (even bucketed/stepwise/other approaches, including T5), so it could be that the 3-para-log approach happens to work well for reasons that have limited or no relation to the theoretical portions of the paper. Likewise, the correspondence between CPD kernels and inner products doesn't appear to have any bearing on the practical implementation, which need not deal with inner products for the attention scheme.

questions: Do you have any thoughts regarding my concerns about sliding-window attention effects?
limitations: Yes
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: As you know transformer is permutation invariant and we add positional embedding to break this invariance (in additive / multiplicative manner, in absolute or relative manner). Recent results demonstrated problems with extrapolation to larger lengths of sequences not only for absolute positional embedding but also for relative positional embedding (which was supposed to solve this problem). Last works proposed different ways on improving positional embedding like augmentation absolute positions (SHAPE, CAPE, Universal Transformer) or having fast decreasing function defined on relative position $m-n$ (T5, ALiBi). This paper continues the study on improving the relative positional embedding to be generalizable to longer sequences: it provides mathematical connection and generalization for T5 and ALiBi approaches with conditional positive-definite kernels (CPD) and positive-definite kernels (PD). With that authors experimented with polynomial and logarithmic bias functions for $m-n$ and found that logarithmic has the best behavior mostly outperforming T5 and ALiBi (and also standard embedding: rotary and sinpos) on 3 large text datasets for language modeling task.
strengths_and_weaknesses: **Strengths**
- [clarity] Paper is very well written with only little typos and very well math background and explanations. However, some details (e.g. how evaluation exactly done, how hyperparams were optimized) are needed.
- [originality] The work is providing general formulation of kernelized version of positional embedding where prior works like T5 and ALiBi can be considered as particular cases. I am glad to see nice connection and formulation supported with experiments.
- [quality] current experiments look strong and reasonable, significance test is showing that proposed logarithmic kernel improves over previous results, additional ablations are given in Appendix comparing different kernel variations and even more complex ones. Analysis on the heads (Fig.2) how much context is involved in self-attention looks good to me. Math part and explanations are also correct.
- [significance] It is nice to have general formulation and investigation of different kernels.

**Weaknesses**
- [quality] In my opinion (as in prior work this study is absent) some extra experiments and analysis are needed: analysis how every position is recognized, window attention as a baseline to understand if we are inferring anything from larger context, analysis on the tail of kernel function values, probably Transformer-XL baseline comparison (every this point see in Questions section with more context).
- [significance] The work presents results only for language modeling task and it is open question how it is applicable to other domains, like vision transformer and speech recognition. Also current results (though significance test is showing improvements) doesn't show huge improvement from the simple ALiBi / T5 variant. That is why would be great to have some more analysis what is going on with this type of embeddings to strengthen the papers results and observations.
questions: Thanks authors for providing interesting analysis on what context has contribution to the attention for every head (Fig. 2), careful math formulation (including known facts, and properties) without typos (it is very simple to read and follow) and formulation as CPD/PD kernels. Happy to see some math behind and connection to it for positional embedding!

**References**

[mentioned in rows 21-23]: There are recent several papers which studied augmentation of absolute sinusoidal positional embedding to be able to extrapolate. I recommend to add their links in the introduction and change a bit statement that the success is not only in relative positional embedding. "Kiyono S, Kobayashi S, Suzuki J, Inui K. Shape: Shifted absolute position embedding for transformers. EMNLP 2021" https://aclanthology.org/2021.emnlp-main.266/, and "Likhomanenko, T., Xu, Q., Synnaeve, G., Collobert, R. and Rogozhnikov, A., 2021. CAPE: Encoding relative positions with continuous augmented positional embeddings. Advances in Neural Information Processing Systems, 34, pp.16079-16092." https://proceedings.neurips.cc/paper/2021/hash/865bf46435bd84fa5d89f64cf3ba7347-Abstract.html 

[mentioned in Sec 2.2] Would be nice to add recent works on different positional embeddings in other domains like vision, speech, etc. At least the recent overview paper on positional embeddings for transformers "Dufter, P., Schmitt, M. and Schütze, H., 2021. Position information in transformers: An overview. Computational Linguistics, pp.1-31." https://arxiv.org/abs/2102.11090.

[mentioned in Sec. 2.2 line 62]. Could authors add a bit more description for rotary positional embedding as it is different from all previous in the sense of being multiplicative, not additive and having math formulation to be shift invariant?

[line 72]. Do authors have an exact proposal how to use KERPLE in linearized case? Because rotary positional embedding and absolute positional embedding are applicable directly to "linear attention". And rotary positional embedding (as far as I know) is the first relative positional embedding which is applicable to "linear attention". I would suggest to mention this (other relpos are not extended yet for this case).

**Typos and improving text**
- line 53 missed space "Autoregressive decoding[..]" -> "Autoregressive decoding [..]"
- The message on why we want PD kernel is a bit lost in the text. Maybe a bit clearly formulate this in Sec. 4 or at the end of Sec. 3.
- line 118: ". We prove" -> "we prove"
- line 124: "Lemma. 1" -> "Lemma 1"
- line 135-136 formula - I didn't get why authors have different functions for numerator and denominator? In the denominator it should be the same as in nominator. Same in lines 137-138 formula. I would even simplify this a bit with just proper notations and having only (*) equality and the final expression with specifying what we have right now in lines 138-140
- line 141: "applying a composite kernel to the softmax function" - strange formulation, I have in mind that we do $k(softmax(x))$ not vice versa.
- line 144: How do authors come up with multiplicative positional embedding? in this case all theory is broken as we will have $k_1(q_m, k_n) * k_2(m, n) + k_3(m, n)$ which is not PD or CPD. We can only have $k_1(q_m, k_n) + k_3(m, n)$ being PD/CPD. Some clarification here is needed why we do multiplicative posemb.
- Appendix, line 492: it is a bit obvious but for reader with less math background it is great to add why it is enough to find $c$ only for $v$ on the unit sphere and not the whole space.
- Appendix, line 519: $T_\delta \subset S_{\delta_2}$ - I think it is wrongly to write this subset property. I would say we should just write that "then $v'$ also belongs to $S_{\delta_2}$ and thus ..."


**Experiments**

- First, I would suggest to perform additional experiment on understanding how much extra context is really giving us as for now it seems that methods like T5, ALiBi and the current paper just propose to restrict attention. This reminds local / fixed-context attention, like in Big Bird window attention. I know that T5 and even recent ALiBi didn't investigate this and one can argue (which stated in the current paper) that we see improved perplexity on the dataset with longer context evaluation. This depends how evaluation is done exactly, but here I assume that the text is just segmented in different manner for say 512 and 1024 tokens and then we have just N sentences and N/2 correspondingly to evaluate. In this case perplexity is not fully comparable as tokens at positions 0, 1, .. are different ones, but magnitude of perplexity can give us understanding if something is broken (like in sinpos embedding). If you agree with these points then the test with window attention (as we do same exact evaluation) will give us understanding if we are using larger context and embedding is really helpful (as this is claimed in the paper).

- Another helpful analysis I propose is the following. When we evaluate for particular length, say 1024, we measure average perplexity for current position: we take words at position $k$ and compute their average perplexity. We plot this for every $k\in[1, ..., 1024]$ for different models. In this case we can analyze at which positions particular positional embedding is broken or not. I would suggest to have this plot for say 512, 4096 and 16384.

- I would like to see in Appendix description of how evaluation on different lengths is done (please confirm my above comment how I think it is done). Otherwise it is not obvious as I can come up with several (even expensive) methods.

- Why logarithmic variant of KERPLE is slower than T5 and ALiBi? I would say there probably should no be any difference as number of learnable params is very negligible compared to model size used in experiments.

- How were the parameters of training optimized? On T5 or ALiBi? or just taken some reasonable to be able to train in reasonable time? On which architecture / dataset they were optimized? It is very fair to have in the end exact setting and just vary positional embedding (please confirm this too - maybe it is worth to be specific in the text on this too).

- Would be nice to have also relative positional embedding "Dai, Z., Yang, Z., Yang, Y., Carbonell, J.G., Le, Q. and Salakhutdinov, R., 2019, July. Transformer-XL: Attentive Language Models beyond a Fixed-Length Context. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics (pp. 2978-2988). " as baseline as before it demonstrated some generalization ability on long sequences and recently (see SHAPE, CAPE) it was shown to have problems (but not in context of LM). I know ALiBi didn't provide great benchmarking on this and didn't check Transformer-XL variant. Yes, it is very expensive, but for comprehensive analysis would be nice to understand how it behaves in comparison.

- Do authors have any idea why T5 in Table 3 behaves so good compared to results on extrapolation in ALiBi where they report that T5 do not extrapolate for >5k lengths and it was consistent in their paper?

- One last thing I propose is to add in addition to Fig. 2 the plot of the kernel function itself for different heads (not doing thresholding and selecting exp(-2)) for all methods to see the difference in tail and contribution to softmax.  

limitations: Limitations are discussed in Conclusion and in Sec 4.

**Update on the rating** Based on all discussions, new revision version, all extra experiments, analysis and ablations I would like to raise my score from 6 to 7.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: Previous work, ALiBi, presented a new position embedding method that conveys positional information by subtracting a linearly growing bias from the key-query dot product in the attention mechanism. 

Here the authors present two new position embedding methods that build on ALiBi and claim to improve it by changing the way in which the bias grows as the distance between the key and query increases. In ALiBi this was just a simple linear function but here two slightly more complex alternatives are presented. 

There are experiments on a few dataset but none of these results are compared to results published in existing papers. For example, it would've been very helpful to see results on the commonly-used WikiText-103 benchmark.

I feel like this exploration is interesting and might lead to impactful results but I don't feel like it is quite ready yet. 


strengths_and_weaknesses: Strengths:
1) New formulation of the 'increasing position bias' method from ALiBi that does better on multiple language modeling datasets, as compared to strong baselines (ALiBi, Rotary and the T5 bias).

Weaknesses:
1) The authors only present results for one model size, 162M parameters. I think using the ALiBi baseline on WikiText-103, with 247M parameters would make this paper much stronger.
2) The authors run all the baselines themselves and don't compare to any existing numbers from the literature. This means that if the authors made some error in how they train or run their models, we wouldn't know- all numbers in the paper were produced by the authors themselves. Therefore I would again recommend having the WikiText-103 baseline and comparing to numbers from the ALiBi paper, that way we can ground your results in existing performance numbers from the literature.
3) The authors only train their model on one sequence length, 512. I feel like having experiments on at least one more sequence length would make the paper stronger. 
4) The math in section 3 and 4 seems unnecessary.
5) Two alternatives are presented- log and power, but it seems like the 'log' method is superior in every single dimension, so it's not clear why the power method was presented at all in the paper.
questions: Are there any advantages to the power variant?
limitations: The authors adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

Meta-review: metareview: In the context of transformer models, this paper builds on previous studies (ALiBi embeddings) to improving relative positional embeddings, to generalizable better on long sequences

The key contribution of the paper compared to the ALiBi approach, is a non-linear bias (instead of a linear one), proportional to the distance between token positions n and m, added to the pre-softmax attention score for all position pairs n and m. A the theoretical justification based on kernel computation is provided for these specific terms.

The general formulation of the kernelized version of positional embeddings is viewed as a significant contribution by all reviewers.

Reviewers had concerns regarding the experimental section, but these have been addressed during the rebuttal phase.
confidence: Certain
Decision: Accept