- Rating
- 3
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper is about higher-order attention. In contrast to standard attention that compares a query with each key, higher-order attention compare any query with multiple keys simultaneously. Conceptually, instead of computing the vector of attention scores (pre-softmax) between query q with c channles and L keys K with c channels by q^T@K (omitting any scale normalization), higher-order attention with three factors (triadic) uses keys K1 and K2 and compute the outer tensor products q_c * K1_{j,c} * K2_{z,c} where c runs over the number of channels. Put differently, this triadic attention procedure is equivalent to calculating the L-dimensional vectors p1=\sqrt{q_c}*K1_{j,c} and p2=\sqrt{q_c}*K2_{z,c} and then computing the outer vectors product between the p1 and p2, p1 \otimes p2 \in \setR{L \times L}.
To reduce the complexity of the resulting L \times L \ times L attention score tensor, the authors propose two clever approximations:
- They compose the input sequence into overlapping blocks of length l with some stride. Final attention results are obtained by some averaging procedure.
- The expensive triadic attention within each block is calculated only within a shorter window with size w. Thereby, the computational complexity reduces from O(l^3 d_head) to O(l w^2 d_head).
- Lastly, queries, keys1 and keys2 in the triadic pathway are not computed with the full nunber of channels d_head but a much smaller dimension to further reduce complexity.
The proposed algorithm is evaluated with synthetic experiments (parity-k, majority-k, match2 and match3) plus a short evaluation on tasks from a protein benchmark.
Critical strengths
- The proposed triadic attention is sound (I checked the formulas carefully).
- Intuitively, this much stronger attention might create more powerful transformer layers.
- I like the ideas proposed here to reduce memory and computational complexities.
Overall, I think this is a very interesting paper. The strong results on parity-k compared with standard pairwise attention are very interesting (see below).
Critical weaknesses
- A standard argument brought forth against higher-order attention could be: With ever deeper transformers, at some point these very deep transformers achieve the same performance. I suppose this could be correct. Could the authors run a simple test: Train a 1-layer transformer with their triadic attention and compare that with a standard transformer (2-attention) with k={1,2,3,..} layers with some toy data. How many layers are necessary to reach the same performance? It could be interesting to compare the computational complexity of the 1-layer triadic attention model vs the model with k-blocks with standard attention. When does pairwise attention achieve break-even?
- fig 3a, secondary structure: Why does Blockwise-2D catch up with Blockwise-3D and HOMA for d_model=256 and 512 but not pairwise-2D? Intuitively, the block partitioning has a similar mechanics as a convolution. Could pairwise attention combined with a suitable convolution achieve a similar performance improvement?
- It would be interesting to see some numbers on the computational complexities (in TFLOPs) of each model.
Questions for authors
- please add equation numbers to simplify discussion
- line 162 "\odot denotes the element-wise product": This seems wrong. Given two matrices A, B \in \setR^{m \times n}, the element-wise product C = A \odot B is also a m \times n matrix. Here, matrix \tilde{V}{jz} must be L \times L \times L \times d_head, thus the authors need something akin to the outer vector product to calculate \tilde{V}{jz}.
- line 196 "overlap averaging": What is that? Explain that (preferably with pseudo-code) in the appendix.
- line 199, windowed triadic attention within blocks: "What is meant by "we restrict (j,z) to a local neighborhood of size w<<l"? I suspect that the authors mean that they modify the computation of the unnumbered equation in lines 151-156 - is that correct? If so, define the changed formula.
- low-rank projection in line 203: If I am not mistaken, this has been proposed by Arora et al. "Simple linear attention language models balance the recall-throughput tradeoff". Please add this reference.
- The parity-k results are very interesting. Are the authors aware that standard transformers cannot solve this task (Hahn, "Theoretical Limitations of Self-Attention in Neural Sequence Models") and require auto-regression (Perez et al. "Attention is Turing-Complete")? Could the limitation of self-attention be the standard pairwise attention?
- fig 3a, contact prediction, flourescence: Why is d_model not evaluated for 512?
- ablations: Is there any explanation why the performance of the model with the triadic pathway drops when the interaction exceeds the window size but the model with HOMA attention still works? Is this because the pairwise attention in HMA is not limited to the window size?
Thank you for your feedback. We address each point below.
Weaknesses
Accuracy break-even: Pairwise-2D needs 2 layers on PARITY-4 and 3 layers on PARITY-5 to reach 0.90 in all seeds, whereas one HOMA layer reaches 1.000 on both.
Compute break-even: None within the tested 12 layers. The smallest successful Pairwise-2D models require 17× and 27× the training TFLOPs, 23× and 25× the epochs, and 1.4× and 2.0× the parameters of one HOMA layer on PARITY-4 and PARITY-5, respectively.
Increasing depth does not always help: At 12 layers, Pairwise-2D fails to reach 0.90 on either task within 400 epochs, as shown in Tables C.4–C.5 and the learning curves in Figures 2 and C.1.
Yes, overlapping blockwise attention introduces locality, much like convolution. This may explain why Blockwise-2D improves with width on Secondary Structure, where local residue interactions are important. Combining pairwise attention with convolution could offer similar benefits, but we have not tested this.
We added training TFLOPs for PARITY (Table 1; Appendix C), MATCH3 (Appendix D, Table D.3), and TAPE (Appendix F, Table F.2).
Questions
Q1. We numbered all equations and added references throughout the paper.
Q2. We should clarify that \tilde{V}_{jz} = V_j \odot V_z is defined for each pair (j,z). Since V_j, V_z \in \setR^{d_head}, their element-wise product is also in \setR^{d_head}. Across all pairs, \tilde{V} \in \setR^{L \times L \times d_head}.
There is no third sequence index because \tilde{V}{jz} does not depend on the query i, which enters through A^{(3)}{ijz} in O^{(3)}i = \sum{j,z} A^{(3)}{ijz} \tilde{V}{jz}. We have clarified the shape of \tilde{V} after Eq. (8).
Q3. Due to striding, some positions appear in multiple blocks. "Overlap averaging" means that the final output at each position is the average of its outputs from all blocks containing it. We clarified this in the methods and added pseudocode in Appendix I.
Q4. Correct. The window restricts both j and z to within R_w = (w−1)/2 of the query, giving at most w² pairs. We clarified Section 3.2 and added the modified equations in Appendix J.
Q5. We now cite Arora et al. (2024). While our low-rank factorization of W^{(U)} in Eq. (12) is related to BASED, the purpose differs. BASED reduces the query and key dimensions to bound the recurrent state size, whereas our factorization reduces the number of parameters while projecting back to the full dimension, leaving the triadic computation unchanged.
Q6. We cite Hahn (2020) in the introduction. However, Hahn's limitation concerns asymptotic behavior as sequence length grows, while Pérez et al.'s result relies on autoregressive computation. Our PARITY-k task instead involves local k-bit parity at fixed length, with L=16 and k ≤ 5, solved by non-autoregressive encoders in a single forward pass. In this setting, the distinction is one of learnability rather than impossibility. We extended PARITY-k training to 400 epochs and found that Pairwise-2D can learn PARITY-4/5 with 2–6 layers in at least two of three seeds, but a single layer reaches only 0.629/0.538, compared with HOMA's 1.000. On MATCH3, Pairwise-2D never reaches 0.90 at widths up to 256, whereas several triadic variants do.
These results suggest that HOMA provides an inductive bias that makes higher-order interactions easier to learn, without implying that pairwise attention cannot learn them or that HOMA removes Hahn's asymptotic limitation.
Q7. Figure 3 compares the width required for pairwise attention to match HOMA's performance. We extended the width range where needed and computationally feasible. On Secondary Structure, this required d_model=512, as Blockwise-2D was still improving substantially at 256, from 0.552 at 128 to 0.622 at 256. On Fluorescence, all models plateau around d_model=128–256, and both pairwise baselines nearly match HOMA at 256, with Pairwise-2D reaching 0.655, Blockwise-2D 0.656, and HOMA 0.657. On Contact Prediction, HOMA reaches 0.134 at d_model=128 and maintains this performance at 256, while Pairwise-2D reaches only 0.088 at 256. Contact Prediction was also our most computationally expensive task, so extending it to d_model=512 was beyond our available compute budget.
Q8. Yes. In these experiments, the pairwise pathway attends to the full sequence and is therefore not restricted by the triadic window. When interactions extend beyond this window, Blockwise-3D drops to chance, approximately 0.50, while HOMA can still rely on its pairwise pathway and performs at least as well as Pairwise-2D, as shown in Table G.1. HOMA-add shows the same behavior despite having no fusion MLP, suggesting that the pairwise pathway prevents this collapse.
We would be happy to address any more questions or comments.