We present a new class of near-linear algorithms for efficiently integrating general tensor fields defined on trees with distance dependent kernels, the Structure-Adaptive Tree Field Integrators (STAD-TFIs). STAD-TFIs exploit the tree's underlying structure through decompositions built around path backbones and single vertex separators, and use two-dimensional fast Fourier transforms to compute interactions jointly. By exploiting this structural information, STAD-TFIs achieve more computationally efficient integration than their regular efficient tree field integrators (TFI) counterparts. We provide a detailed theoretical analysis of our proposed approach and complement it with an exhaustive empirical evaluation, ranging from speed tests on synthetic trees, through accelerated Sinkhorn-based relaxations of the Optimal Transport algorithms on real meshes, to Topological Attention Transformers for vision tasks. To the best of our knowledge, we provide some of the first results showing that efficient to compute and accurate relaxations of the geodesic Sinkhorn-based solutions of the Optimal Transport problem can be derived by applying fast TFI methods.
Figures & tables
Figure 2: Integration time as a function of number of vertices for kernel f(d)=1/(1+d) . Diameter-1D versus Diameter-2D isolates the convolution strategy; Diameter-2D versus Adaptive-2D measures the effect of separator selection. See Table 5 in Appendix C.3 for detailed numbers.
Tree Approximation
Rel. OT Error
Plan TV
Kernel Error
Minimum Spanning Tree (MST)
0.028±0.027
0.329±0.155
0.680±0.135
Random Shortest-Path Tree (Random SPT)
0.033±0.047
0.183±0.082
0.677±0.050
Diameter/Backbone Spanning Tree
0.021±0.020
0.124±0.063
0.599±0.155
Alon et al. (1995) (AKPW) Tree
0.018±0.025
0.236±0.101
0.573±0.100
Abraham and Neiman (2012) Tree
0.026±0.048
0.211±0.100
0.677±0.072
Table 1: Tree approximations for geodesic Sinkhorn on Thingi10K. Results are reported as mean ± standard deviation across the evaluated meshes. Lower is better for all metrics.
Figure 3: Runtime comparison as a function of the number of vertices. Speedup Numbers are in Table 6 in Appendix D.4 . StAd-TFI (SpclK-Diameter) is ≈3.35× its FTFI counterpart.
CIFAR-100
Tiny-ImageNet
Configuration
N=196
N=1,024
N=196
Linear, unmasked
49.94±0.26
51.89
36.77±0.49
Softmax, unmasked
51.71±0.26
53.19±0.49
37.96±0.78
Linear, masked (random)
55.27±0.68
58.02±0.08
40.14±0.33
Linear, masked (serpentine)
54.14±1.37
57.84±0.89
41.35±0.99
Table 2: Top-1 accuracy (%, mean ± standard deviation over seeds) for ViT-S, trained from scratch under a single fixed recipe. Seed counts and protocol are given in Appendices E.2 and E.7 .
Method (tree)
1,024
4,096
16,384
65,536
262,144
Dense ( Θ(N2) )
0.15
2.24
36.07
—
—
FTFI (random)
1.10
4.93
25.20
99.99
424.97
StAd-TFI (serpentine)
0.39
1.76
8.02
37.82
165.67
Table 3: Runtime (seconds) of the masked-attention workload as a function of N (median of at least five runs; protocol in Appendix E.6 ). FTFI uses its most favorable configuration (random tree).
Appendix figures & tables16 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 4: The schematic grid presents a matrix where each entry Gq[s] sums over source depths r and anchors t .
Family
Construction and vertex count
Tested parameters
Path
One chain, N vertices.
N∈N .
Balanced binary
Complete binary tree; N=2d+1−1 .
d∈{4,5,6,7,8,9} .
Complete 3-ary
Complete ternary tree; N=(3d+1−1)/2 .
d∈{3,4,5,6} .
Caterpillar
Three leaves per spine vertex, N=4ℓ .
ℓ∈L .
Caterpillar + hanging paths
One ℓ -edge path at every spine vertex, N=ℓ+ℓ2 .
ℓ∈{8,12,16,24,32} .
Comb
Two leaves per spine vertex, N=3ℓ .
ℓ∈L .
Appendix
Table 4: Deterministic tree constructions and complete parameter sweeps. All leaves and hanging paths are distinct.
Family
N
BF
FTFI
D1
D2
A2
Path
800
250.93
59.31
1.19
1.15
2.09
Balanced binary
1023
399.17
64.10
49.46
23.80
56.63
Complete 3-ary
1093
458.63
56.36
63.56
29.72
61.63
Caterpillar
1600
1,004.16
84.25
35.77
35.43
38.02
Caterpillar + paths
1056
435.47
64.77
62.78
6.68
16.67
Comb
1200
577.43
67.53
24.20
24.11
25.74
Appendix
Table 5: Largest-size integration times (in milliseconds). BF denotes brute force; D1, D2, and A2 denote Diameter-1D, Diameter-2D, and Adaptive-2D. Random-family entries are means across three tree seeds. Bold indicates the lowest recorded mean in each row.
Figure 5: Additional runtime sweeps for complete 3-ary trees, caterpillars with three branches, combs with two teeth, brooms, and double brooms.
Figure 6: Additional runtime sweeps for uniform spiders, short-arm spiders, and stars.
Figure 7: Runtime sweeps for random trees, random weighted MST trees, and preferential attachment trees. Curves show means of per-seed timing minima across three tree seeds; bands show approximate 95% confidence intervals.
Figure 8: The 28 Thingi10K meshes used in the geodesic Sinkhorn experiments.
StAd-TFI variant ( A )
Baseline ( B )
Meshes
Single Kx
Per iteration
Sinkhorn
With setup
SpclK-Diameter
FTFI ( SpclK-Centroid )
28
3.31×
3.38×
3.38×
3.35×
SpclK-Adaptive
28
3.00×
3.07×
3.07×
2.98×
Adaptive-2D-FFT
FTFI ( 1D-FFT )
28
5.99×
6.32×
6.32×
5.84×
SpclK-Diameter
FTFI ( SpclK-LinearExactDP )
28
1.24×
1.28×
1.28×
1.20×
SpclK-Adaptive
28
1.12×
1.17×
1.17×
1.07×
Appendix
Table 6: Geometric-mean speedups tB/tA over 28 meshes. Values greater than one indicate that A is faster.
Metric
Mean ± std.
Median
Maximum
Kernel error EK,Q
0.3158±0.1409
0.3201
0.6909
Relative OT error Erel(Q)
0.0295±0.0262
0.0274
0.1014
Plan variation TVQ
0.0295±0.0258
0.0238
0.1140
Appendix
Table 7: Quantization and transport-cost errors on the MSTs of 28 Thingi10K meshes at B=64 . Kernel error and plan TV compare the quantized and original tree problems; relative OT error uses the original-graph transport-cost reference. Each mesh has equal weight. We report the arithmetic mean ± sample standard deviation, median, and maximum. All values are dimensionless.
Figure 9: CIFAR-100 top-1 accuracy versus training epoch. (a) Masked softmax and masked linear attention at N=196 (curves are means over three seeds). (b, c) Masked linear attention across spanning trees at N=196 and N=1,024 ; multi-seed configurations are drawn as seed means, the remaining configurations as single seeds. In all panels, the dashed and dotted horizontal lines mark the best accuracy of the unmasked softmax and unmasked linear baselines, respectively. Every masked tree exceeds both baselines (Appendix E.7 ).
Figure 10: The five spanning-tree families of the patch grid evaluated in the tree sweep, from bushy (random) to path-like (serpentine, Hilbert). Every spanning tree of the unit-weight grid is a minimum spanning tree, so all are admissible under the topological-mask construction.
tree
family
avg. edge stretch
top-1 (%)
Δ vs. unmasked
unmasked
—
—
49.79
—
fishbone
caterpillar
4.50
55.95
+6.16
comb
caterpillar
7.50
54.86
+5.07
random
Kruskal
5.35
54.80
+5.01
serpentine
path
7.50
52.82
+3.03
Hilbert
path
8.81
51.74
+1.95
Appendix
Table 8: Accuracy as a function of tree choice (CIFAR-100, ViT-S, masked linear attention, N=196 , single seed), together with the average edge stretch on the 14×14 grid. Accuracy decreases with stretch (Pearson −0.86 ).
tree
avg. edge stretch ( 322 )
top-1 (%)
Δ vs. softmax
random
7.21
58.02
+4.83
serpentine
16.50
57.84
+4.65
fishbone
9.00
56.38
+3.19
rec. bisection
6.99
n.c.
—
Appendix
Table 9: Accuracy as a function of tree choice at N=1,024 (patch 7 , 32×32 grid; CIFAR-100, ViT-S, masked linear attention); random and serpentine are means over two seeds (Section E.7.5 ), fishbone single seed; average edge stretch on the 32×32 grid. References: unmasked linear 51.89 , plain softmax 53.19±0.49 (three seeds). “n.c.”: not converged at this scale (Section E.7.5 ).
N
16,384
65,536
147,456
262,144
StAd-TFI , serpentine (path, H=0 )
8.89
41.80
96.71
196.49
StAd-TFI , fishbone ( H≈N/2 )
13.41
103.19
492.82
813.26
StAd-TFI , comb ( H≈N )
30.70
264.71
786.96
2593.84
StAd-TFI , random
27.63
133.01
397.78
1618.01
FTFI , serpentine
240.31
1099.08
†
†
FTFI , fishbone
34.69
225.81
†
†
Appendix
Table 10: Single-pass runtime (seconds) of the masking primitive per tree at C=4,160 on a 32 -core CPU; all methods within a row are timed in the same process. The upper block reports StAd-TFI ; the middle block reports FTFI on the same tree ( † : not completed within a 15 -minute budget); the final row is the incumbent FTFI -random baseline. The path scales near-linearly for StAd-TFI , deeper trees super-linearly, and the relative efficiency shifts toward StAd-TFI as trees become more backbone-dominated (cf. Table 11 ).
Tree
H
T\textscFTFI
TStAd
T\textscFTFI/TStAd
Random
616
100.0
121.4
0.82×
Comb
255
379.3
231.1
1.6×
Fishbone
128
217.1
91.4
2.4×
Serpentine
0
964.1
37.8
25.5×
Appendix
Table 11: Runtime crossover at N=65,536 , C=4,160 (seconds; protocol as in Table 3 ). H is the off-backbone depth of the diameter backbone; the relative efficiency shifts toward StAd-TFI on backbone-dominated trees.
path construction
stretch ( 142 )
stretch ( 322 )
row-snake (serpentine)
7.50
16.50
column-snake
7.50
16.50
Hilbert
8.81
19.62
diagonal-snake
9.50
21.50
spiral
16.64
40.56
Appendix
Table 12: Hamiltonian-path constructions ranked by average edge stretch; all attain identical H=0 runtime. The row-snake (serpentine) ordering attains the lowest stretch.
Tensor networks, originally developed for quantum many-body physics, are promising models for machine learning. We derive stochastic Riemannian optimizers for tree tensor networks (TTNs) on both their parameter and quotient manifolds, including adaptive and learning-rate-free schemes suitable for minibatch training. Using a hybrid CNN-TTN architecture, we evaluate the methods on Fashion-MNIST, CIFAR10, and Imagenette. The proposed optimizers achieve predictive performance comparable to unconstrained optimization while enabling numerically stable downstream compression.
Marius Willner, Maximilian Scharf, André Uschmajew +2
Institute of Mathematics, University of Augsburg, 86159 Augsburg, Germany · Centre for Advanced Analytics and Predictive Sciences, University of Augsburg, 86159 Augsburg, Germany · Tensor AI Solutions GmbH, 89284 Pfaffenhofen an der Roth, Germany +1
Tree tensor networks (TTNs) are widely used in low-rank approximation and quantum many-body simulation. In this work, we present a formal analysis of the quotient geometry underlying the TTN parameter space. Our framework allows for arbitrary horizontal distributions, and we develop efficient first- and second-order optimization algorithms that exploit this geometry. Additionally, we devise a backpropagation algorithm for training TTNs in a kernel learning setting. We validate our methods through numerical experiments on a representative digit classification task and reveal an important tradeoff between two different horizontal distributions that are available for TTNs: while one offers cleaner geometric statements, the other ultimately leads to more efficient algorithms.
Marius Willner, Marco Trenti, Dirk Lebiedz
Chair of Mathematical Data Science, University of Augsburg, Augsburg, Germany · Tensor AI Solutions GmbH, Pfaffenhofen a.d. Roth, Germany · Institute for Numerical Mathematics, University of Ulm, Ulm, Germany
Persistence-based topological optimization deforms a point cloud X⊂Rd by minimizing objectives of the form L(X)=ℓ(Dgm(X)), where Dgm(X) is a persistence diagram. In practice, optimization is limited by two coupled issues: persistent homology is typically computed on subsamples, and the resulting topological gradients are highly sparse, with only a few anchor points receiving nonzero updates. Motivated by diffeomorphic interpolation, which extends sparse gradients to smooth ambient vector fields via Reproducing Kernel Hilbert Space (RKHS) interpolation, we propose a more scalable pipeline that improves both subsampling and gradient extension. We introduce subsampling via random slicing, a lightweight scheme that promotes iteration-wise geometric coverage and mitigates density bias. We further replace the costly kernel solve with a fast Nadaraya-Watson (NW) Gaussian convolution, producing a globally defined smooth update field at a fraction of the computational cost, while being more suited for topological optimization tasks. We provide theoretical guarantees for NW smoothing, including anchor approximation bounds and global Lipschitz estimates. Experiments in 2D and 3D show that combining random slicing with NW smoothing yields consistent speedups and improved objective values over other baselines on common persistence losses.