Hierarchical Kernel Transformer: Multi-Scale Attention with an Information-Theoretic Approximation Analysis

Giansalvo Cirrincione

cs.LGApr 10, 2026

Hierarchical Kernel Transformer: Multi-Scale Attention with an Information-Theoretic Approximation Analysis

Authors: Giansalvo Cirrincione

Organizations: Laboratoire LTI, Université de Picardie Jules Verne, 33 rue Saint-Leu, Amiens, 80039, France

Abstract

The Hierarchical Kernel Transformer (HKT) is a multi-scale attention mechanism that processes sequences at L resolution levels via trainable causal downsampling, combining level-specific score matrices through learned convex weights. The total computational cost is bounded by 4/3 times that of standard attention, reaching 1.3125x for L = 3. Four theoretical results are established. (i) The hierarchical score matrix defines a positive semidefinite kernel under a sufficient condition on the symmetrised bilinear form (Proposition 3.1). (ii) The asymmetric score matrix decomposes uniquely into a symmetric part controlling reciprocal attention and an antisymmetric part controlling directional attention; HKT provides L independent such pairs across scales, one per resolution level (Propositions 3.5-3.6). (iii) The approximation error decomposes into three interpretable components with an explicit non-Gaussian correction and a geometric decay bound in L (Theorem 4.3, Proposition 4.4). (iv) HKT strictly subsumes single-head standard attention and causal convolution (Proposition 3.4). Experiments over 3 random seeds show consistent gains over retrained standard attention baselines: +4.77pp on synthetic ListOps (55.10+-0.29% vs 50.33+-0.12%, T = 512), +1.44pp on sequential CIFAR-10 (35.45+-0.09% vs 34.01+-0.19%, T = 1,024), and +7.47pp on IMDB character-level sentiment (70.19+-0.57% vs 62.72+-0.40%, T = 1,024), all at 1.31x overhead.

Figures & tables

Figure 2: Experiment 1 (top) and kurtosis analysis (bottom). Top left: validation accuracy vs. epoch. Top right: comparison with same-setting MHA baseline and contextual LRA figures ( Tay et al., 2021 ) . Bottom left:

\kappa_{l}

vs. epoch (ceiling

\approx 286

). Bottom right:

\kappa_{l}

vs.

d_{\mathrm{model}}

post-training.

Model	Val Acc (%)	Overhead
Same setting ( $T=512$ , synthetic ListOps, 3 seeds):
MHA (retrained)	$50.33\pm 0.12$	$1.00\times$
HKT-Small ( $d=128$ )	$\mathbf{55.10\pm 0.29}$	$1.313\times$
HKT-Medium ( $d=256$ )	$55.5$	$1.313\times$
HKT-Large ( $d=512$ )	$55.6$	$1.313\times$
Contextual reference (LRA, $T=2{,}048$ , Tay et al. 2021 ):

Table 1: Validation accuracy and computational overhead. HKT and MHA-Retrained: same synthetic task (

T=512

, same training setup), mean

\pm

std over 3 seeds. LRA figures from Tay et al. (2021) (

T=2{,}048

) — contextual reference only.

Configuration	Val Acc (%)	$\Delta$
Full HKT-Small	55.2	—
w/o hierarchy ( $L=1$ , flat)	36.8	$-18.4$
w/o conv branch ( $\beta=1$ )	52.1	$-3.1$
w/o attn branch ( $\beta=0$ )	43.7	$-11.5$
w/o dynamic fusion ( $\alpha$ uniform)	53.6	$-1.6$
w/o $\mathcal{L}_{\mathrm{div}}$	54.1	$-1.1$

Table 2: Ablation study, HKT-Small (

d=128

$L$	$s$	Val Acc (%)	Overhead	Params
1	2	49.9	$1.000\times$	738K
2	2	55.7	$1.250\times$	749K
3	2	55.3	$1.313\times$	752K
4	2	57.7	$1.328\times$	755K
1	3	49.9	$1.000\times$	738K
2	3	55.7	$1.111\times$	749K

Table 3: Sensitivity to number of levels

L

and stride

s

, HKT-Small (

d=128

, 30 epochs). Overhead from Proposition 4.6 .

Model	Val Acc (%)	Test Acc (%)	Overhead
Same setting ( $T=1{,}024$ , 3 seeds):
MHA (retrained)	$34.01\pm 0.19$	$33.97\pm 0.21$	$1.00\times$
HKT-Small ( $d=128$ )	$\mathbf{35.45\pm 0.09}$	$\mathbf{35.30\pm 0.10}$	$1.313\times$
Contextual reference ( Tay et al., 2021 ) :
MHA (LRA)	—	42.44	$1.00\times$

Table 4: Sequential CIFAR-10 results, mean

\pm

std over 3 seeds. HKT and MHA retrained in the same setting (

T=1{,}024

). LRA figure from Tay et al. (2021) (contextual reference).

Model	Val Acc (%)	Overhead
Same setting ( $T=1{,}024$ , 3 seeds):
MHA (retrained)	$62.72\pm 0.40$	$1.00\times$
HKT-Small ( $d=128$ )	$\mathbf{70.19\pm 0.57}$	$1.313\times$
Contextual reference ( Tay et al., 2021 ) :
MHA (LRA, $T=4{,}096$ )	65.90	$1.00\times$

Table 5: IMDB character-level sentiment classification, mean

\pm

std over 3 seeds (

T=1{,}024

). LRA reference from Tay et al. (2021) (

T=4{,}096

, contextual only).

Level $l$	Scale	Mean $\\|M_{s}\\|_{F}$	Mean ratio
0 (local)	$s^{0}=1$	0.153	1.529
1 (medium)	$s^{1}=2$	0.248	1.480
2 (global)	$s^{2}=4$	0.277	1.112

Table 6: Mean

\|M_{s}^{(l)}\|_{F}/\|M_{a}^{(l)}\|_{F}

across encoder layers, HKT-Small trained on ListOps. A ratio

>1

indicates

M_{s}

dominant (more reciprocal); ratio closer to

1

indicates increasing directionality.

$T$	Model	Train (ms/batch)	Inf. (ms/batch)	Peak Mem. (MB)
128	MHA	13.4	1.4	96
128	HKT	30.7	4.6	118
256	MHA	9.9	1.4	160
256	HKT	20.4	4.6	240
512	MHA	10.1	2.6	291
512	HKT	18.0	4.6	586

Table 7: Wall-clock time and memory, A100 GPU (

B=16

d=128

L=3

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

	Pre-training		Post-training
Level	$b_{2,p}$	$\kappa_{l}$	$b_{2,p}$	$\kappa_{l}$
$l=0$	2978.7	24.82	3980.0	33.17
$l=1$	2951.9	24.60	3980.0	33.17
$l=2$	2793.6	23.28	3980.0	33.17

Appendix

Table 8: Mardia’s normalised kurtosis

\kappa_{l}=b_{2,p}/(p(p+2))

(

d=128

n=300

p=10

). Gaussian reference:

\kappa_{l}=1

. The test instrument is calibrated up to

\kappa_{l}\approx 16.5

(its asymptotic critical region); values above this threshold indicate

\kappa_{l}

exceeds the ceiling, not that

\kappa_{l}

is bounded.

Figure 3: Evolution of $\kappa_{l}$ during training ( $d=128$ , 30 epochs). Top: training loss/accuracy and $b_{2,p}$ vs. epoch. Centre: p-values for kurtosis and skewness. Bottom: QQ-plot of the first principal component of $S^{(0)}$ and heatmap of final p-values.

Explore similar work

Quasi Linear Kernel Attention with Infinite Capacity
Sep 28, 2026Nicolaj Rux, Johannes Hertrich, Sebastian NeumayerTransformer Expressivity Attention Mechanisms
Faculty of Mathematics, Chemnitz University of Technology, 09126 Chemnitz, Germany · Institute of Computer Science, University of Göttingen, 37073 Göttingen, Germany
Projection-Free Transformers via Gaussian Kernel Attention
May 4, 2026Debarshi Kundu, Archisman Ghosh, Swaroop Ghosh +1Transformer Self-Attention
The Pennsylvania State University, University Park, USA
Flexformer: Flexible Linear Transformer with Learnable Attention Kernel
Jun 26, 2026Haoran Zhang, Feng ZhouFourier Feature Embeddings Long-Context Language Modeling
Center for Applied Statistics and School of Statistics, Renmin University of China Beijing, China

Sep 28, 2026J/K move · Enter open · S save

Quasi Linear Kernel Attention with Infinite Capacity

Nicolaj Rux, Johannes Hertrich, Sebastian Neumayer

Faculty of Mathematics, Chemnitz University of Technology, 09126 Chemnitz, Germany · Institute of Computer Science, University of Göttingen, 37073 Göttingen, Germany

Transformer Expressivity Attention Mechanisms

Open paper AskPDF arXiv

The evaluation cost of transformers with softmax attention scales quadratically with sequence length. Kernel attention addresses this by replacing softmax with a more general kernel function. In this paper, we aim to identify kernels that retain the expressivity of attention while enabling quasi linear computation. To quantify expressivity, we introduce a capacity for each kernel, measuring the maximum sequence length for which the attention matrix can approximate the identity. A higher capacity thus indicates greater expressivity. We show that expressive kernels like softmax, Gauss, and Laplace have infinite capacity. In contrast, common quasi linear kernels, such as those derived from finite dimensional feature maps, exhibit finite capacity. As a solution, we propose additive kernels constructed from univariate spline and polynomial exponential kernels. We prove that these maintain infinite capacity while allowing quasi linear computation via sorting. Finally, we implement additive sorting kernels efficiently and benchmark them against modern softmax backends, demonstrating advantages for long sequences.

Abstract

Explore similar work

Quasi Linear Kernel Attention with Infinite Capacity

Projection-Free Transformers via Gaussian Kernel Attention

Flexformer: Flexible Linear Transformer with Learnable Attention Kernel