Sequence models represent past context at different resolutions, using token-level keys and values, fixed-size recurrent states, or hierarchies of compressed summaries. Full attention supports strong associative recall but requires quadratic work during training and prefill and a linearly growing key-value cache during inference. Linear attention and state-space models reduce these costs through fixed-size recurrent memory, but this compression can limit recall. Log-linear attention offers a middle ground by maintaining logarithmically many state matrices. However, its hierarchy favors finer resolution near the current query while compressing earlier context into coarser summaries. To complement this allocation of resolution, we introduce bilateral log-linear attention, which pairs the existing hierarchy with a second hierarchy anchored at the sequence origin. By combining their reads, the two branches provide finer access to both early and recent context while remaining causal. We derive recurrent and chunkwise parallel formulations for the added branch, preserving log-linear training and prefill work, logarithmic decoding work per token, and logarithmic persistent state storage at fixed feature dimensions and chunk size. In multi-query associative recall, this design raises mean overall test accuracy from 76.37% to 96.12% over forward log-linear attention across multiple training seeds. For pretrained language models under approximate parameter matching, it raises the mean score on six selected RULER needle-in-a-haystack tasks from 26.97% to 50.03% at a context length of 6144 tokens. In the same setting, bilateral attention also outperforms forward log-linear attention on seven of eight downstream retrieval tasks, including question answering and information extraction.
Figures & tables
Figure 1: Context representation in Linear attention / Mamba-2 and Log-linear attention. At t=14 , the causal prefix contains 15 tokens. (a) Linear attention and Mamba-2 summarize the entire prefix in one state matrix per head; scalar decay changes its contents without creating separate temporal buckets. (b) Log-linear attention groups tokens into buckets of sizes 8,4,2,1 , labeled by braces as Bt(ℓ) . Each bucket is represented by a separate state matrix of the same dimension and is read with its own level weight λt(ℓ) . The nonempty levels are 4,3,2,0 ; level 1 is empty ( St(1)=0 ). Color indicates bucket size, not attention strength. The hierarchical construction follows Guo et al. (2026) .
Mechanism
Training time
Decode time per token
Decode memory
Softmax attention
O(T2)
O(T)
O(T)
Linear attention w/wo. scalar decay
O(T)
O(1)
O(1)
Log-linear attention w/wo. scalar decay
O(TlogT)
O(logT)
O(logT)
Table 1: Complexity in terms of sequence-length at fixed model dimensions and chunk size, following Guo et al. (2026) . Training time refers to complexity over a length- T sequence; decode work is for one new token. Decode memory refers to persistent recurrent state or KV cache storage.
Figure 2: Complementary context resolution. At t=14 , the forward Fenwick view groups 15 positions into buckets of sizes 8,4,2,1 , while the stationary reverse view uses sizes 1,2,4,8 . Braces label the visible buckets Btf,(ℓ) and Btr,(ℓ) . Each bucket feeds one matrix of the same dimensions, read with the current query and the indicated level weight. Reverse states accumulate write-gated associations. Colors encode bucket size, consistently with Figure 1 . Both views are causal and store compressed summaries. Forward level 1 is empty in this example.
Figure 3: Reverse branch attention mask structure and parallel computation. (a) Rows are queries and columns are source tokens for a 15-token sequence; distinct outline hues identify stationary source buckets ( C0,C1,C2,C3 ), with faint matching cell fills. The stationary buckets match the reverse hierarchy in Figure 2 (b). Dashed outlines mark within-bucket causal triangles; solid outlines mark completed-bucket rectangles. C3 has no rectangle because no query follows its completion. (b,c) The regions for C2 are expanded into symbolic entries and compact forms. M4causal is the 4×4 causal mask with ones on and below the diagonal and zeros elsewhere. Within each row, visible entries in a bucket share μt(ℓ) , which may vary between queries. The triangle enforces causality while the bucket fills; the completed mask rectangle is an outer product, enabling reuse of its source summary in the attention computation. Ranges use half-open indexing, with μa:b(2)=(μa(2),…,μb−1(2))⊤ .
Forward branch
Reverse branch
Bilateral
Training/prefill work
O(TLf)
O(TLr)
O(T(Lf+Lr))=O(TlogT)
Decode work per token
O(Lf)
O(Lr)
O(Lf+Lr)=O(logT)
State matrices per head
Lf
Lr
Lf+Lr=O(logT)
Matrix-state elements per head
Lfdvdk
Lrdvdk
(Lf+Lr)dvdk=O(logT)
Table 2: Attention-core work and matrix-state storage per head for a length- T sequence, at fixed feature dimensions and chunk size. Lf levels suffice for the forward hierarchy, while Lr counts nonempty reverse levels; both grow logarithmically with T . Storage counts one matrix per level, including empty forward levels, and excludes shared feature-generation history, parameters, and training activations.
Figure 4: MQAR test accuracy. All four models have two layers and hidden size 64, with sequence length 512 and K∈{32,64,96,128} key–value pairs. Bars and curves show means over ten final training seeds (10–19); error bars and shading show ±1 sample standard deviation, with shaded bands clipped to [0,100%] . All runs share the same fixed datasets, so the spread reflects variation across training seeds. Accuracy is averaged over queries within each example and then over examples; the overall score weights the four loads equally.
Perplexity ↓
LM-Eval
RULER-NIAH ↑
Retrieval
Model (layers)
Parameters (M)
WikiText-2
LAMBADA
avg. ↑
2048
4096
6144
avg. ↑
Layer-matched (12 layers)
Mamba-2 (12)
338.1
31.37
39.66
40.92
31.37
27.23
12.79
18.76
Log-linear (12)
350.5
30.23
33.78
42.23
43.65
40.52
27.04
21.46
Bilateral (12)
365.6
30.21
33.20
41.51
63.18
59.14
50.03
25.16
Transformer (12)
275.7
32.53
40.75
40.81
67.42
61.28
59.77
29.76
Table 3: Language-modeling results under layer matching and approximate parameter matching. Parentheses give depth; parameter counts are in millions. PPL is perplexity ( ↓ ); all other scores are percentages ( ↑ ). LM-Eval averages six selected accuracy scores; RULER-NIAH averages six selected tasks separately at each length; retrieval averages eight tasks. Bold denotes the best result among Mamba-2, log-linear, and bilateral within each panel. The bilateral rows use the same checkpoint. WikiText-2 rolling PPL uses a 6144-token context for all models.
Appendix figures & tables10 assets
Supplementary material from the paper’s appendix.
Appendix
Operation
Arithmetic work
Apply source gates
O(Tdv)
Form chunk summaries
O(Tdkdv)
Scan summaries and obtain bucket totals
O(Ndkdv)
Local causal query–key/value products
O(U(dk+dv))
Read incoming chunk states
O(Tdkdv)
Read completed states at later queries
O(Fdkdv)
Appendix
Table 4: Arithmetic work per sequence and head for the unpadded scan algorithm. Scan bounds assume a work-efficient additive scan. Scaling and accumulation include both within-bucket and later-query rows.
Model
Trainable parameters
Selected peak learning rate
Mamba-2
580,656
0.00316227766
Log-linear
591,216
0.01
Bilateral
604,896
0.00316227766
Transformer
655,680
0.01
Appendix
Table 5: MQAR model sizes and selected learning rates. All models have two layers and hidden size 64. Counts include tied embeddings once.
Model
Overall
K=32
K=64
K=96
K=128
Mamba-2
70.53±22.69
90.72±21.61
79.20±26.49
63.67±24.67
48.53±20.09
Log-linear
76.37±14.35
93.34±10.59
83.89±15.70
71.00±16.36
57.25±15.23
Bilateral
96.12±3.79
99.73±0.38
98.54±1.95
95.90±5.10
90.30±7.85
Transformer
99.49±0.22
99.64±0.13
99.48±0.29
99.40±0.30
99.42±0.21
Appendix
Table 6: MQAR test accuracy in percent, reported as mean ± sample standard deviation across ten training seeds (10–19). The overall score gives equal weight to the four memory loads. Standard deviations are in percentage points. Bold means indicate the highest accuracy among Mamba-2, log-linear, and bilateral.
Training seed
Mamba-2
Log-linear
Bilateral
Transformer
10
14.47
88.71
99.01
99.49
11
78.13
81.78
96.86
99.17
12
83.17
78.14
96.77
99.53
13
69.52
45.54
87.38
99.59
14
80.69
80.85
97.01
99.67
15
83.68
80.84
98.99
99.25
Appendix
Table 7: Overall MQAR test accuracy (%) for all ten final training seeds. All runs use the same fixed training, validation, and test data. Bold denotes the best accuracy among Mamba-2, log-linear, and bilateral for each training seed.
Model
Layers
Parameters
Configuration note
Layer-matched (12 layers)
Mamba-2
12
338,147,520
One state matrix per head
Log-linear
12
350,549,952
Forward hierarchy
Bilateral
12
365,608,320
Shared, normalized, gated
Transformer
12
275,682,816
MLP width 2048
Approximately parameter-matched
Appendix
Table 8: Selected language-model configurations. Counts include all learnable parameters. The approximately parameter-matched log-linear model uses an MLP width of 2320. Both panels reuse the same bilateral checkpoint.
Model
Wiki. PPL
Lamb. PPL
Lamb.
PIQA
Hella.
Wino.
ARC-E
ARC-C
Avg.
Layer-matched (12 layers)
Mamba-2
31.37
39.66
27.93
63.71
33.83
50.20
45.71
24.15
40.92
Log-linear
30.23
33.78
30.53
64.20
34.13
51.38
46.97
26.19
42.23
Bilateral
30.21
33.20
31.13
62.79
34.15
51.46
45.92
23.63
41.51
Transformer
32.53
40.75
30.56
61.70
31.64
52.01
44.57
24.40
40.81
Approximately parameter-matched
Appendix
Table 9: Language-modeling and commonsense-reasoning results. The first two metric columns are perplexities ( ↓ ); the remaining columns are accuracy percentages ( ↑ ). The six-task average excludes perplexities. WikiText-2 uses a 6144-token context for all models. Bold denotes the best result among Mamba-2, log-linear, and bilateral within each panel.
Model
S-NIAH-1
S-NIAH-2
S-NIAH-3
MK-NIAH-1
MQ-NIAH
MV-NIAH
Avg.
Layer-matched (12 layers)
Mamba-2
77.80
13.40
33.60
26.60
19.15
17.65
31.37
Log-linear
99.80
68.20
11.20
34.40
24.05
24.25
43.65
Bilateral
100.00
100.00
70.60
49.60
28.80
30.10
63.18
Transformer
99.80
100.00
65.60
59.20
39.45
40.45
67.42
Approximately parameter-matched
Appendix
Table 10: RULER-NIAH results at context length 2048. Each task uses the same 500 prepared examples for every model. Scores are percentages; higher is better. Avg. is the unweighted mean over the six tasks. Bold denotes the best result among Mamba-2, log-linear, and bilateral within each panel.
Model
S-NIAH-1
S-NIAH-2
S-NIAH-3
MK-NIAH-1
MQ-NIAH
MV-NIAH
Avg.
Layer-matched (12 layers)
Mamba-2
58.40
41.80
1.80
22.20
20.20
19.00
27.23
Log-linear
99.40
62.40
8.00
30.20
21.20
21.95
40.52
Bilateral
99.80
98.60
55.40
49.60
23.65
27.80
59.14
Transformer
98.40
100.00
47.80
64.80
29.80
26.90
61.28
Approximately parameter-matched
Appendix
Table 11: RULER-NIAH results at context length 4096. Each task uses the same 500 prepared examples for every model. Scores are percentages; higher is better. Avg. is the unweighted mean over the six tasks. Bold denotes the best result among Mamba-2, log-linear, and bilateral within each panel.
Model
S-NIAH-1
S-NIAH-2
S-NIAH-3
MK-NIAH-1
MQ-NIAH
MV-NIAH
Avg.
Layer-matched (12 layers)
Mamba-2
38.60
6.60
6.20
12.00
5.15
8.20
12.79
Log-linear
94.80
15.00
5.60
17.40
15.30
14.15
27.04
Bilateral
99.80
89.80
23.60
45.80
20.90
20.25
50.03
Transformer
100.00
100.00
42.80
60.40
27.80
27.65
59.77
Approximately parameter-matched
Appendix
Table 12: RULER-NIAH results at context length 6144. Each task uses the same 500 prepared examples for every model. Scores are percentages; higher is better. Avg. is the unweighted mean over the six tasks. Bold denotes the best result among Mamba-2, log-linear, and bilateral within each panel.
Model
SWDE
SQuAD
FDA
TriviaQA
DROP
NQ-512
NQ-1024
NQ-2048
Avg.
Layer-matched (12 layers)
Mamba-2
20.61
28.18
10.62
38.86
16.05
13.78
11.53
10.44
18.76
Log-linear
24.93
31.20
15.43
39.75
17.87
16.63
13.62
12.28
21.46
Bilateral
29.79
33.51
32.76
39.57
17.44
17.83
15.93
14.47
25.16
Transformer
37.44
33.71
62.07
39.10
17.68
18.06
16.06
13.93
29.76
Approximately parameter-matched
Appendix
Table 13: Downstream retrieval scores under the common evaluation protocol. SWDE, SQuAD completion, FDA, TriviaQA, and DROP use their full-dataset evaluations. Scores are percentages; higher is better. Avg. is the unweighted mean over the eight retrieval tasks, counting each NQ variant separately. Bold denotes the best result among Mamba-2, log-linear, and bilateral within each panel.