Beyond Pairwise Attention: Higher-Order Modular Attention for Efficient Sequence Learning

Shirin Amiraslani; Xin Gao

cs.LGMar 11, 2026

Beyond Pairwise Attention: Higher-Order Modular Attention for Efficient Sequence Learning

Authors: Shirin Amiraslani, Xin Gao

Organizations: Department of Mathematics and Statistics York University Toronto, ON M3J 1P3, Canada

Abstract

Sequence modeling tasks can involve intrinsic higher-order dependencies, while standard self-attention assigns scores to token pairs and does not explicitly parameterize such interactions. We introduce Higher-Order Modular Attention (HOMA), which fuses pairwise attention with an explicit triadic attention pathway made tractable through overlapping blocks, local windows, and a low-rank projection. We compare HOMA with matched pairwise and purely triadic baselines on controlled PARITY and MATCH3 tasks, as well as TAPE benchmarks. HOMA is competitive with or outperforms the baselines, with its clearest advantages when the underlying dependencies extend beyond the explicitly modeled triadic order. These advantages are accompanied in several settings by faster convergence and improved parameter efficiency, with the learned nonlinear fusion providing an effective mechanism for combining the pairwise and triadic representations. Overall, our results provide empirical evidence that HOMA is an effective attention design when task structure extends beyond pairwise interactions.

Figures & tables

Figure 1: Transformer layer with higher-order modular attention. HOMA replaces the self-attention sublayer and computes pairwise and triadic multi-head attention in parallel from shared projections $Q$ , $K$ , $V$ , and $U$ . Their outputs are concatenated, fused, and mapped through the standard output projection.

$d$	mechanism	$D{=}1$	$6$	$12$	$D{=}1$	$6$	$12$	$D{=}1$	$6$	$12$
		$k{=}3$			$k{=}4$			$k{=}5$
$\mathbf{32}$	Pairwise-2D	.978 $\pm.037$	1.000 $\pm.000$	1.000 $\pm.000$	.499 $\pm.014$	.729 $\pm.021$	.694 $\pm.011$	.503 $\pm.002$	.611 $\pm.036$	.601 $\pm.028$
	Blockwise-3D	1.000 $\pm.000$	1.000 $\pm.000$	1.000 $\pm.000$	.964 $\pm.048$	.997 $\pm.003$	1.000 $\pm.000$	.847 $\pm.125$	.991 $\pm.011$	1.000 $\pm.001$
	HOMA-add	1.000 $\pm.000$	1.000 $\pm.000$	1.000 $\pm.000$	.992 $\pm.010$	1.000 $\pm.000$	1.000 $\pm.000$	.871 $\pm.066$	.996 $\pm.007$	.999 $\pm.002$
	HOMA	1.000 $\pm.000$	1.000 $\pm.000$	1.000 $\pm.000$	1.000 $\pm.000$	1.000 $\pm.000$	1.000 $\pm.000$	1.000 $\pm.000$	1.000 $\pm.000$	1.000 $\pm.000$
$\mathbf{64}$	Pairwise-2D	1.000 $\pm.000$	1.000 $\pm.000$	1.000 $\pm.000$	.500 $\pm.004$	.782 $\pm.101$	.728 $\pm.039$	.513 $\pm.010$	.655 $\pm.043$	.702 $\pm.032$

Table 1: parity -

k

across interaction order

k

, network depth

D\in\{1,6,12\}

, and embedding size

d

. Mean final test accuracy

\pm

standard deviation over three seeds. Results for

k=3

are shown in gray since performance is near-saturated across attention mechanisms. HOMA results for

k=4,5

are bold.

Figure 2: Convergence on parity -5 at embedding size

d=64

across network depths

D\in\{1,6,12\}

. Curves show mean test accuracy over three seeds, with final values reported as acc ; shaded bands span the minimum–maximum range across seeds. The dashed line marks

0.90

accuracy. Open circles and ep@0.90 indicate the mean first-crossing epoch across seeds;

>40

indicates that no seed reached the threshold within 40 epochs.

$N\,(M)$	mechanism	$16$	$32$	$64$	$128$	$d_{0.90}$	params
		test accuracy at $d_{\mathrm{model}}$
$6\,(30)$	Pairwise-2D	0.816 $\pm$ 0.009	0.835 $\pm$ 0.001	0.830 $\pm$ 0.003	0.783 $\pm$ 0.009	$>$ 256	–
	Blockwise-3D	0.836 $\pm$ 0.007	0.921 $\pm$ 0.012	0.958 $\pm$ 0.008	0.927 $\pm$ 0.028	$32$	1.08 $\times$
	HOMA-add	0.835 $\pm$ 0.003	0.929 $\pm$ 0.002	0.990 $\pm$ 0.002	0.975 $\pm$ 0.006	$32$	1.08 $\times$
	HOMA	0.857 $\pm$ 0.006	0.967 $\pm$ 0.007	0.993 $\pm$ 0.002	0.991 $\pm$ 0.003	$32$	1.60 $\times$
$8\,(56)$	Pairwise-2D	0.708 $\pm$ 0.005	0.744 $\pm$ 0.004	0.761 $\pm$ 0.009	0.731 $\pm$ 0.012	$>$ 256	–

Table 2: match3 across sequence lengths

N

and embedding sizes

d_{\mathrm{model}}

. Mean final test accuracy

\pm

standard deviation over three seeds;

M

denotes the modulus. Bold marks the highest mean accuracy at each length and embedding size.

d_{0.90}

is the smallest tested embedding size achieving mean accuracy

\geq 0.90

. params reports the parameter count at

d_{0.90}

relative to Pairwise-2D at the same embedding size. A dash means the threshold is never reached within the tested range, also indicated by

d_{0.90}>256

. The two additional widths

d_{\mathrm{model}}=8

and

256

are in Appendix D , Table D.2 .

Figure 3: Test performance and performance-matched parameter efficiency across TAPE Secondary Structure (CB513), Contact Prediction, and Fluorescence. Results are averaged over three seeds. (a) Mean performance across embedding sizes, with shaded regions showing

\pm 1

standard deviation. (b) For each attention mechanism, we report the minimum parameter count across tested widths that matches each HOMA performance target. A run is considered to match a target if its score is within

1.5

pooled seed standard deviations of the HOMA score or within

0.5\%

in relative terms. Dotted arrows denote targets not reached; annotations show parameter count relative to HOMA . The parameter axis is logarithmic.

Figure 4: Triadic window coverage on parity -3. All panels use dedicated coverage-sweep runs with $d_{\mathrm{model}}=32$ and sequence length $L=24$ ; results are averaged over three seeds. (a,b) Test accuracy across interaction reach $R$ for window sizes $w{=}3$ and $w{=}7$ ; the shaded region and dashed line indicate the triadic reach limit $R_{w}$ . (c) Blockwise-3D accuracy across interaction reach and depth for $w{=}3$ .

	Component			parity -3		parity -4		parity -5		match3
Design	pooling	third factor	fusion	acc	ep@0.90	acc	ep@0.90	acc	ep@0.90	acc	ep@0.90
HOMA	softmax	$W^{(U)}$	MLP	1.000	5.7	1.000	7.7	1.000	9.3	0.967	10.7
Replace	uniform	$W^{(U)}$	MLP	1.000	9.7	0.994	16.3	0.955	21.7	0.861	$>$ 40
	softmax	$W^{(U)}{=}W^{(K)}$	MLP	1.000	4.3	1.000	7.3	0.983	9.7	0.933	19.3
Replace	softmax	$W^{(U)}$	sum	1.000	7.3	0.992	17.0	0.871	32.0 †	0.929	19.3
	uniform	$W^{(U)}$	sum	0.988	18.7	0.495	$>$ 40	0.500	$>$ 40	0.838	$>$ 40

Table 3: Component teardown of HOMA on parity -

k

and match3 . Each row ablates one component with the others fixed. Results use one attention layer,

d_{\mathrm{model}}{=}32

and three seeds. acc is mean final test accuracy; ep@0.90 is the mean epoch to reach

0.90

accuracy among successful seeds within 40 epochs. † and ‡ denote one and two successful seeds, respectively;

>40

denotes no successful seed.

Appendix figures & tables10 assets

Supplementary material from the paper’s appendix.

Appendix

Train / valid / test	3,000 / — / 800	30,000 / — / 2,000	8,678 / 2,170 / 3 sets	25,299 / 224 / 40	21,446 / 5,362 / 27,217
	parity /	match2 /	Secondary Structure	Contact Prediction	Fluorescence
	majority	match3
Sequence length	$L{=}16$	$N\in\{6,8\}$	pad to 512	crop to 256	fixed at 237
Vocabulary	2 (binary)	$M$ (calibrated)	30 (IUPAC)	30 (IUPAC)	30 (IUPAC)
Label	per position	per position	per residue	per pair	per sequence
Test split	held out	held out	CB513 / CASP12 / TS115	CASP12	$H_{d}\!\geq\!4$

Appendix

Table A.1: Data and task specification. “—” denotes a non-applicable setting. The match modulus

M

is calibrated by sequence length and task order (Section D.1 ).

	parity /	match2 /	Secondary Structure	Contact Prediction	Fluorescence
	majority	match3
$d_{\mathrm{model}}$ range	8–128	8–256	32–512	32–256	32–256
Layers	1, 6, 12 (grid); 1 (capacity); 1, 2, 4 (coverage)	1	12	12	12
Heads	4	4	8	8	8
FFN width	none	none	$2d_{\mathrm{model}}$	$2d_{\mathrm{model}}$	$2d_{\mathrm{model}}$
Dropout	0	0	0.4	0.1	0.1

Appendix

Table A.2: Architecture and attention. Only the attention mechanism varies within a task; every other quantity here is shared across mechanisms at a given width.

	parity /	match2 /	Secondary Structure	Contact Prediction	Fluorescence
	majority	match3
Optimizer	Adam	Adam	Adam	AdamW	Adam
Learning rate	$2\times 10^{-3}$	$3\times 10^{-3}$	$10^{-4}$	$10^{-4}$	$10^{-4}$
Weight decay	0	0	0	0.01	0
LR schedule	none	none	none	OneCycle (10% warm-up)	cosine (6% warm-up)
Gradient clipping	none	none	none	1.0	1.0

Appendix

Table A.3: Optimization, loss, and evaluation settings.

$d_{\mathrm{model}}$	params	acc	ep@0.90	params	acc	ep@0.90	params	acc	ep@0.90
	Pairwise-2D			Blockwise-3D			HOMA
$8$	466	0.586 $\pm.041$	$>$ 40	594	0.946 $\pm.058$	22.5 (2/3)	1,492	0.982 $\pm.030$	19.3
$16$	1,442	0.879 $\pm.082$	35.5 (2/3)	1,698	0.989 $\pm.019$	10.0	3,366	1.000 $\pm.000$	6.0
$32$	4,930	0.978 $\pm.037$	21.0	5,442	1.000 $\pm.000$	4.7	8,650	1.000 $\pm.000$	5.0
$64$	18,050	1.000 $\pm.000$	11.7	19,074	1.000 $\pm.000$	3.0	25,362	1.000 $\pm.000$	3.0

Appendix

Table C.2: Capacity on parity -3. Trainable parameters, mean final test accuracy over three seeds, and mean epochs to

0.90

among successful seeds. One attention layer without a residual connection; a separate run series from the depth grid of Table C.1 .

		test accuracy at $d_{\mathrm{model}}$
$N\,(M)$	mechanism	$16$	$32$	$64$	$128$
$6\,(9)$	Pairwise-2D	1.000 $\pm.000$	1.000 $\pm.000$	1.000 $\pm.000$	1.000 $\pm.000$
	Blockwise-3D	1.000 $\pm.000$	1.000 $\pm.000$	1.000 $\pm.000$	1.000 $\pm.000$
	HOMA-add	1.000 $\pm.000$	1.000 $\pm.000$	1.000 $\pm.000$	1.000 $\pm.000$
	HOMA	1.000 $\pm.000$	1.000 $\pm.000$	1.000 $\pm.000$	1.000 $\pm.000$
$8\,(14)$	Pairwise-2D	1.000 $\pm.000$	1.000 $\pm.000$	1.000 $\pm.000$	0.979 $\pm.036$

Appendix

Table D.1: match2 control. Mean final test accuracy

\pm

standard deviation over three seeds across sequence lengths

N

, calibrated moduli

M

, and embedding widths

d_{\mathrm{model}}

		test accuracy at $d_{\mathrm{model}}$
$N\,(M)$	mechanism	$8$	$16$	$32$	$64$	$128$	$256$
$6\,(30)$	Pairwise-2D	0.760 $\pm.008$	0.816 $\pm.009$	0.835 $\pm.001$	0.830 $\pm.003$	0.783 $\pm.009$	0.776 $\pm.026$
	Blockwise-3D	0.770 $\pm.015$	0.836 $\pm.007$	0.921 $\pm.012$	0.958 $\pm.008$	0.927 $\pm.028$	0.774 $\pm.008$
	HOMA-add	0.741 $\pm.038$	0.835 $\pm.003$	0.929 $\pm.002$	0.990 $\pm.002$	0.975 $\pm.006$	0.817 $\pm.010$
	HOMA	0.786 $\pm.009$	0.857 $\pm.006$	0.967 $\pm.007$	0.993 $\pm.002$	0.991 $\pm.003$	0.819 $\pm.015$
$8\,(56)$	Pairwise-2D	0.625 $\pm.014$	0.708 $\pm.005$	0.744 $\pm.004$	0.761 $\pm.009$	0.731 $\pm.012$	0.726 $\pm.007$

Appendix

Table D.2: Extended match3 width sweep. Mean final test accuracy

\pm

standard deviation over three seeds. Widths 16–128 reproduce Table 2 for completeness; widths 8 and 256 are additional.

		score at $d_{\mathrm{model}}$
task	mechanism	$32$	$64$	$128$	$256$	$512$
Secondary Structure (CB513)	Pairwise-2D	0.513 $\pm.001$	0.518 $\pm.001$	0.521 $\pm.001$	0.518 $\pm.002$	0.527 $\pm.001$
	Blockwise-2D	0.536 $\pm.001$	0.542 $\pm.002$	0.552 $\pm.004$	0.622 $\pm.004$	0.642 $\pm.005$
	Blockwise-3D	0.620 $\pm.001$	0.636 $\pm.002$	0.643 $\pm.002$	0.642 $\pm.005$	0.644 $\pm.010$
	HOMA	0.625 $\pm.003$	0.642 $\pm.001$	0.651 $\pm.001$	0.656 $\pm.001$	0.659 $\pm.003$
Secondary Structure (CASP12)	Pairwise-2D	0.542 $\pm.010$	0.543 $\pm.005$	0.539 $\pm.003$	0.544 $\pm.006$	0.538 $\pm.011$

Appendix

Table E.1: TAPE results by task and width. Mean

\pm

standard deviation over three seeds; the best mechanism at each width is bold. Secondary Structure reports Q3 accuracy on CB513, CASP12, and TS115; Figure 3 plots CB513. Contact Prediction reports long-range P@

L/5

, and Fluorescence reports Spearman

\rho

. “–” denotes an untested width.

Secondary Structure
	Pairwise-2D			Blockwise-2D			Blockwise-3D			HOMA
$d_{\mathrm{model}}$	par	tput	mem	par	tput	mem	par	tput	mem	par	tput	mem
$32$	120k	165	2.04	120k	217	0.42	126k	138	0.91	146k	102	2.14
$64$	437k	159	2.19	437k	215	0.60	449k	129	1.64	487k	97.1	2.97
$128$	1.7M	147	2.50	1.7M	216	0.99	1.7M	112	3.11	1.8M	84.3	4.63
$256$	6.5M	101	3.14	6.5M	137	1.81	6.5M	72.0	6.08	6.7M	57.1	8.02

Appendix

Table F.1: Parameters, throughput, and peak memory by task and width. par : trainable parameters; tput : thousands of residues per second; mem : peak allocated GB. Values are means over three seeds. Throughput is compute-only for Secondary Structure and Fluorescence and wall-clock-derived for Contact Prediction, so comparisons are valid within, but not across, tasks. “–” denotes an untested width.

		interaction reach $R$
window	mechanism	$1$	$2$	$3$	$4$	$5$	$6$
$w{=}3$ ( $R_{w}{=}1$ )	Pairwise-2D	0.907 $\pm.024$	0.951 $\pm.013$	0.913 $\pm.035$	0.884 $\pm.049$	0.816 $\pm.080$	0.857 $\pm.097$
	Blockwise-3D	1.000 $\pm.000$	0.501 $\pm.009$	0.496 $\pm.008$	0.499 $\pm.001$	0.500 $\pm.003$	0.501 $\pm.004$
	HOMA-add	1.000 $\pm.000$	0.858 $\pm.065$	0.936 $\pm.071$	0.862 $\pm.074$	0.854 $\pm.046$	0.829 $\pm.065$
	HOMA	1.000 $\pm.000$	0.964 $\pm.015$	0.968 $\pm.031$	0.915 $\pm.055$	0.909 $\pm.122$	0.986 $\pm.024$
$w{=}7$ ( $R_{w}{=}3$ )	Pairwise-2D	0.907 $\pm.024$	0.951 $\pm.013$	0.913 $\pm.035$	0.884 $\pm.049$	0.816 $\pm.080$	0.857 $\pm.097$

Appendix

Table G.1: Triadic-window coverage on parity -3 at depth 1. Dedicated coverage-sweep runs use

d_{\mathrm{model}}=32

and sequence length

L=24

. The window reach is

R_{w}=(w-1)/2

. Mean final test accuracy

\pm

standard deviation over three seeds. Pairwise-2D is independent of

w

, so the same runs are shown for both window settings.

		attention layers
reach	mechanism	$1$	$2$	$4$
$R{=}1$	Blockwise-3D	1.000 $\pm.000$	1.000 $\pm.000$	1.000 $\pm.000$
	HOMA-add	1.000 $\pm.000$	1.000 $\pm.000$	1.000 $\pm.000$
	HOMA	1.000 $\pm.000$	1.000 $\pm.000$	1.000 $\pm.000$
$R{=}2$	Blockwise-3D	0.501 $\pm.009$	1.000 $\pm.000$	1.000 $\pm.000$
	HOMA-add	0.858 $\pm.065$	1.000 $\pm.000$	1.000 $\pm.000$

Appendix

Table G.2: Accuracy by reach and depth for

w=3

(

R_{w}=1

). Dedicated coverage-sweep runs use

d_{\mathrm{model}}=32

and sequence length

L=24

. Mean final test accuracy

\pm

standard deviation over three seeds.

Explore similar work

Poly-attention: a general scheme for higher-order self-attention
Feb 2, 2026Sayak Chakrabarti, Toniann Pitassi, Josh AlmanLinear Attention Transformer Architectures
Computer Science, Columbia University, New York, NY 10027.
Boltzmann Attention: Learnable Ising Couplings for Cooperative Attention
Jun 10, 2026Gilhan Kim, Daniel K. ParkLinear Attention Sequence Modeling
Department of Statistics and Data Science, Yonsei University, Seoul 03722, Republic of Korea · Department of Applied Statistics, Yonsei University, Seoul 03722, Republic of Korea · Department of Quantum Information, Yonsei University, Seoul 03722, Republic of Korea
SMat-Attention: Structured Long-Context Sequence Modeling
Sep 28, 2026Emile Anand, Abdullah Ateyeh, Archer Wang +1Linear Attention Sequence Modeling
Massachusetts Institute of Technology

Feb 2, 2026, cs.LGJ/K move · Enter open · S save

Poly-attention: a general scheme for higher-order self-attention

Sayak Chakrabarti, Toniann Pitassi, Josh Alman

Computer Science, Columbia University, New York, NY 10027.

Linear Attention Transformer Architectures Object Tokens Representational Capacity Worst-Case

Open paper AskPDF arXiv

The self-attention mechanism, at the heart of the Transformer model, is able to effectively model pairwise interactions between tokens. However, numerous recent works have shown that it is unable to perform basic tasks involving detecting triples of correlated tokens, or compositional tasks where multiple input tokens need to be referenced to generate a result. Some higher-dimensional alternatives to self-attention have been proposed to address this, including higher-order attention and Strassen attention, which can perform some of these polyadic tasks in exchange for slower, superquadratic running times. In this work, we define a vast class of generalizations of self-attention, which we call poly-attention mechanisms. Our mechanisms can incorporate arbitrary higher-order (tensor) computations as well as arbitrary relationship structures between the input tokens, and they include the aforementioned alternatives as special cases. We then systematically study their computational complexity and representational strength, including giving new algorithms and matching complexity-theoretic lower bounds on the time complexity of computing the attention matrix exactly as well as approximately, and tightly determining which polyadic tasks they can each perform. Our results give interesting trade-offs between different desiderata for these mechanisms, including a tight relationship between how expressive a mechanism is, and how large the coefficients in the model may be so that the mechanism can be approximated in almost-linear time. Notably, we give a new attention mechanism which can be computed exactly in quadratic time, and which can perform function composition for any fixed number of functions. Prior mechanisms, even for just composing two functions, could only be computed in superquadratic time, and our new lower bounds show that faster algorithms for them are not possible.

Abstract

Explore similar work

Poly-attention: a general scheme for higher-order self-attention

Boltzmann Attention: Learnable Ising Couplings for Cooperative Attention

SMat-Attention: Structured Long-Context Sequence Modeling