△ Mechanism confirmed, baseline not beaten 2026

Sparse-Graph Tensorized Linear Layer

Implementation & benchmark of arXiv:2608.02849 — Computing with traceable tensor networks

Usefulness8/10

Difficulty6/10

Novelty5/10

Architecture Memory Speedup Accuracy Mlp Transformer Inference speedup Quantization Tensor decomposition Linear algebra Graph theory Approximation theory

Source paper: Computing with traceable tensor networks arXiv:2608.02849 ⓘ · analyzed Aug 31, 2026

AI-generated research hypothesis, automatically tested. Not peer-reviewed.

Idea description

Replace a dense neural-network weight tensor with a graph tensor network whose physical modes and internal edge ranks are specified by a sparse rank-adjacency matrix. Unlike tensor-train or hierarchical Tucker layers, the graph can contain selected cycles and skip connections between tensor modes, allowing the factorization topology to match correlations in the weight tensor. Fit the layer with GTN-SVD at a prescribed tolerance and compare accuracy, parameter count, and tensor-contraction throughput against dense and TT baselines.

Formulas

$$\mathbf{R}_{ij}=\begin{cases}n_i,&i=j,\\ r_{i,j},&i\neq j\text{ and an edge connects }i\text{ and }j,\\ 1,&i\neq j\text{ and no edge connects }i\text{ and }j.\end{cases}$$

$$\overline{i_1i_2\ldots i_d}=1+\sum_{k=1}^{d}(i_k-1)\prod_{j=1}^{k-1}n_j$$

$$\|\mathcal{X}-\widetilde{\mathcal{X}}\|_F\leq\varepsilon\|\mathcal{X}\|_F$$

$$\|A-A_r\|_F^2=\sum_{q>r}\sigma_q(A)^2,\qquad r=\min\left\{s:\sum_{q>s}\sigma_q(A)^2\leq\delta^2\|\mathcal{X}\|_F^2\right\}$$

Mathematical statement

A graph tensor network has p cores, with physical mode size n_j on vertex j and edge rank r_{i,j} on every connected pair. These choices are encoded by the symmetric rank-adjacency matrix R: R_{ij}=n_i when i=j, R_{ij}=r_{i,j} when an edge connects i and j, and R_{ij}=1 when no edge exists; diagonal entries n_j=1 may represent internal vertices. The represented tensor is the contraction W(i_1,...,i_d)=sum over all edge indices of the product of core entries G_k(i_k, incident edge indices), with unit-rank absent edges omitted. GTN-SVD uses the fact that every graph is a subgraph of the complete graph K_p, embeds the target tensor into the corresponding fully connected tensor network, and applies recursive SVDs after grouping indices into matrix unfoldings. For target tensor X and approximation X_tilde, the construction is controlled by the relative Frobenius guarantee ||X-X_tilde||_F <= epsilon ||X||_F. At each SVD A=U Sigma V^T, rank truncation uses the discarded singular-value energy sum_{q>r} sigma_q(A)^2.

Implementation notes

Integrate this at the weight tensor of an MLP projection or Transformer output projection. Reshape a dense matrix W in R^{m x n} into a d-way tensor X with physical dimensions n_1,...,n_d, and choose sparse candidate graphs: a path, a tree, a ring, and a path augmented with one or two chords. Store one core G_k per vertex, with dimensions n_k times the ranks of all incident edges. For offline decomposition, use the following procedure: (1) input X, the symmetric rank-adjacency matrix R, and tolerance epsilon; (2) choose a traceable path through the graph; (3) at each elimination step, reshape the remaining tensor into a matrix using the multi-index ordering above; (4) compute A=U Sigma V^T; (5) retain the smallest rank r such that the discarded singular-value energy is at most delta_k^2 ||X||_F^2, with sum_k delta_k^2 <= epsilon^2; (6) absorb U Sigma into the next incident core and continue until all cores are produced. In training and inference, contract the graph directly with the tensorized input rather than materializing W. The exact mathematical quantities are SVD factors, graph ranks, and truncation energy. Empirically measure which topology gives the best validation loss at fixed parameter count; optionally add a chord when the corresponding mode-group unfolding has slowly decaying singular values. Start with a 4-layer MLP on CIFAR-10 and a small Transformer on WikiText-103, replacing one projection layer. Compare dense, TT, and graph layers at matched loss. Success is at least 2x fewer parameters at equal validation loss, or lower loss than TT at equal parameter count, with measured reconstruction error tracking epsilon.

Verification

Mechanism confirmed, baseline not beaten

Stage 1 · Toy mechanism gate: Passed ✓

Stage 2 · Mechanism transferred to benchmark: Confirmed ✓

Stage 2 · Practical benchmark result: Significantly worse ✗

Methodology: 8 paired seeds, permutation test (p<0.05) against a learning-rate-tuned baseline. How verification works

Stage 1 — Mechanism check agent confidence 8/10

Built a readable sparse graph tensor-network MVP using torch.einsum, with a TT-SVD baseline, topology fitting, parameter counts, and throughput measurements. The numerical checks confirmed the Frobenius tolerance guarantee and monotonic rank/parameter reduction as tolerance loosened; ring/chord connectivity substantially outperformed a path on a chord-generated tensor. This is a mechanism-level success rather than a definitive end-to-end win: the chord only slightly improved over the ring at higher parameter cost, and no CIFAR-10 or Transformer benchmark was run.

Agent confidence: 8/10

Baseline: TT/path: relative reconstruction error 0.5042 with 48 parameters on the chord-generated target; TT-SVD relative errors were 1.7e-7, 1.7e-7, 1.7e-7, and 0.0835 for eps=0.02, 0.05, 0.10, and 0.20; path throughput was 718.1 contractions/sec.
Idea: Ring: relative error 0.1310 with 64 parameters and 906.2 contractions/sec; chord graph: relative error 0.1284 with 72 parameters and 896.4 contractions/sec. TT parameter count decreased from 120 to 100 when epsilon increased from 0.10 to 0.20.

Limitations: Only a 4-way synthetic tensor was tested. Graph fitting used 400-step Adam optimization rather than a full GTN-SVD elimination algorithm; no CIFAR-10, Transformer, matched-parameter training, production contraction kernel, or large-scale speed/memory evaluation was performed.

How to run: python3 experiment.py

Stage 2 — Benchmark vs. tuned baseline (arXiv:2608.02849) Sep 2, 2026

Significantly WORSE than the tuned baseline (+65.5%, p=0.0081, wins 0 / 8 paired seeds).

Benchmark: Tabular regression (Friedman)
Model: mlp_tiny
Paired seeds: 8
Baseline mean: 9.9066
Idea mean: 16.3916
Effect (Δ): 6.485 (+65.5%; negative = idea better)
Wins: 0 / 8 paired seeds
p-value: 0.0081 (permutation test, 20 000 shuffles)
Smallest detectable effect: ±17.0%
Mechanism: Confirmed ✓
Practical effect: Hurts
Baseline tuning: swept over 6 configs

Limitations:

Only the tabular MLP track and a ring topology were tested; no CIFAR-10, sequence, dynamics, GTN-SVD offline decomposition, matched-parameter topology sweep, or optimized contraction kernel was evaluated.

How to run: python3 stage2_bench.py

Verdict computed by deterministic test code from paired-seed statistics — not by the language model.

Stage 2 — Benchmark Aug 31, 2026 latest Failed ✗

Agent confidence: 9/10

Implemented a sparse ring graph-tensorized replacement for the first projection of mlp_tiny and evaluated it on the structurally matched tabular Friedman#1 regression track. The dense baseline achieved test MSE 9.9066 versus 16.3916 for the idea across 8 paired seeds; the idea was significantly worse (delta +6.4850, permutation p=0.0081). Parameter reduction was observed but modest, so the promised end-to-end win was not demonstrated.

Baseline: Dense mlp_tiny, best lr=0.01, weight_decay=0.0001: mean MSE 9.906578, std 0.783495.
Idea: Ring graph projection, best lr=0.01, weight_decay=0.0, rank=4: mean MSE 16.391593, std 1.658133; 4657 vs 4929 parameters, ratio 0.944816.
Mechanism signature: map[confirmed:true observed_parameter_ratio:0.944816 observed_test_prediction_relative_difference:0.102702]
Paired delta: idea - baseline = +6.485015 MSE
Permutation p: 0.0081

Benchmark result