△ Mechanism confirmed, baseline not beaten 2026

Resistance-certified tree attention

Implementation & benchmark of arXiv:2608.20778 — Resistance Curvature: Recognition, Polyhedral Structure, and Graph Products

Usefulness7/10

Difficulty7/10

Novelty7/10

Architecture Memory Speedup Stability Graph nn Attention Pruning Memory Graph theory Combinatorics Linear algebra Convex analysis

Source paper: Resistance Curvature: Recognition, Polyhedral Structure, and Graph Products arXiv:2608.20778 ⓘ · analyzed Sep 1, 2026

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

Idea description

Replace an arbitrary graph-attention mask with a fractional edge mask lying in the intersection of the spanning-tree polytope and twice the matching polytope. The mask represents a distribution over connected spanning trees while imposing expected degree at most two at every vertex, after which sampled trees can be used for sparse message passing.

Formulas

$$\Theta(G)=P(G)\cap 2M(G)$$

$$P(G)=\left\{x\in\mathbb{R}_{\ge 0}^{E}:x(E)=|V|-1,\ x(E(S))\le |S|-1\ \text{for every }\varnothing\ne S\subsetneq V\right\}$$

$$x(E(v))=\sum_{e\ni v}x_e=\mathbb{E}_{T\sim\mu}[\deg_T(v)]\le 2$$

$$x_e=c_eR_e(c),\qquad R_e(c)=b_e^{\mathsf T}L(c)^+b_e,\qquad L(c)=\sum_{e\in E}c_eb_eb_e^{\mathsf T}$$

Mathematical statement

For a connected graph G=(V,E), let P(G) be the spanning-tree polytope, the convex hull of incidence vectors 1_T of spanning trees T. Its rank-inequality description is P(G)={x in R^E: x_e>=0, x(E)=|V|-1, x(E(S))<=|S|-1 for every nonempty proper S subset V}, where x(F)=sum_{e in F}x_e. Let M(G) be the matching polytope and define Theta(G)=P(G) intersection 2M(G). In particular, x(E(v))=sum_{e incident to v}x_e<=2. If x is the edge-marginal vector of a spanning-tree distribution mu, then x(E(v))=E_mu[deg_T(v)]<=2. For positive conductances c_e, the weighted spanning-tree marginal is x_e=c_e R_e(c), where R_e(c)=b_e^T L(c)^+ b_e is effective resistance, b_e is an oriented incidence vector, and L(c)=sum_e c_e b_e b_e^T is the weighted graph Laplacian.

Implementation notes

Integrate this into a graph-attention or message-passing layer immediately before aggregation. Given node states h_v and a fixed graph G, compute positive conductances c_e=softplus(MLP([h_u,h_v])) for each edge e=(u,v). For an MVP, form z_e=c_e R_e(c), using sparse Laplacian linear solves to estimate effective resistances, then project z onto Theta(G) by solving min_x ||x-z||_2^2 subject to x_e>=0, sum_e x_e=n-1, vertex constraints sum_{e incident to v}x_e<=2, and a manageable active set of spanning-tree cut constraints sum_{e in E(S)}x_e<=|S|-1. Use the resulting x_e as an attention multiplier or normalized message weight: m_v=sum_{u:(u,v) in E} x_{uv} W h_u. For sparse inference, sample a spanning tree from x using a spanning-tree sampler or dependent rounding and aggregate only tree edges; optionally retain the largest residual edges. Compute small-graph resistances exactly and large-graph resistances with Hutchinson probes plus conjugate gradients. First test on Cora, PubMed, and a synthetic long-range node-classification task with a 2-layer GAT baseline. Compare dense attention, independent top-(n-1) pruning, and tree attention at equal message FLOPs. Success means roughly 2x lower edge aggregation and memory cost with no more than a 1 percentage-point accuracy loss, together with lower seed-to-seed variance and substantially fewer disconnected pruned supports.

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 an exact small-graph MVP for resistance marginals, Theta projection, weighted spanning-tree sampling, and sparse aggregation in verify_and_experiment.py. Complete-graph and cycle resistance predictions matched numerical results to near machine precision, and the star feasibility boundary appeared exactly at degree 3. Projection enforced the degree cap and tree-mass constraint; sampled trees reduced edges 3x but incurred nonzero aggregation error, so this is a sparsity tradeoff rather than a demonstrated accuracy win.

Agent confidence: 8/10

Baseline: Dense resistance-weighted aggregation on K6: 15 undirected edges.
Idea: Sampled spanning-tree aggregation on K6: 5 undirected edges, a 3.0x reduction; tree-vs-dense MSE 0.3837 +/- 0.0050 over 500 samples. Empirical weighted-tree marginal RMSE was 0.00734 over 3000 samples.
Predictions: For K_n, observed mean degrees exactly matched 2-2/n for n=4,...,10, with edge marginal error below 2.3e-16. On cycles, the resistance formula error was at most 3.2e-15 over conductance ratios 0.01-100, and maximum degree stayed below 1.982. Stars were feasible at n=3 and infeasible for n=4,...,8. Projection changed maximum degree from 2.8656 to 2.0000 and produced total mass 5.0000.

Limitations: No Cora, PubMed, or learned GAT/node-classification experiment was run. The sampler enumerates Prüfer trees and is practical only for tiny complete graphs; scalable sparse Laplacian solves, Hutchinson estimates, dependent rounding, GPU execution, timing benchmarks, and seed-to-seed accuracy comparisons were not tested. The MVP projection includes all spanning-tree cuts and vertex degree caps but does not encode the full odd-set inequalities of the matching polytope.

How to run: python3 verify_and_experiment.py

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

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

Benchmark: Sequence modeling
Model: transformer_tiny
Paired seeds: 8
Baseline mean: 0.391
Idea mean: 0.432
Effect (Δ): 0.0409 (+10.5%; negative = idea better)
Wins: 0 / 8 paired seeds
p-value: 0.0081 (permutation test, 20 000 shuffles)
Smallest detectable effect: ±3.2%
Mechanism: Confirmed ✓
Practical effect: Hurts
Baseline tuning: swept over 3 configs

Limitations:

Only the built-in sequence forecast track was tested, using a fixed path spanning tree rather than learned conductances, exact effective-resistance computation, Theta projection, or stochastic spanning-tree sampling. The implementation adds a sparse path residual alongside the standard TransformerEncoder rather than replacing the encoder's internal dense self-attention, so the measured edge reduction reflects the explicit intervention support and not a fully sparse Transformer kernel. No Cora/PubMed graph node-classification, GPU speed benchmark, large-graph resistance estimation, or memory measurement was performed.

How to run: python3 bench_experiment.py

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

Stage 2 — Benchmark Sep 1, 2026 latest Failed ✗

Agent confidence: 10/10

Built a local transformer sequence benchmark with a fixed connected spanning-tree token support as the intervention, using identical data, model dimensions, optimizer, epochs, batch size, and shared learning-rate sweep for baseline and idea. The mechanism signature was confirmed at NN scale: 992 dense directed token edges versus 62 tree-directed edges, a 16x reduction, with maximum support degree 2.0. However, the idea had test MSE 0.43197 versus baseline 0.39103, paired delta +0.04093, and permutation p=0.0081; it was significantly worse, so worked=false.

Baseline: Sequence transformer_tiny, 8-seed test MSE mean 0.3910339922; best lr=0.001 selected by 4-seed sweep.
Edge behavior: Dense directed token edges 992; tree directed token edges 62; reduction 16.0x; maximum trained support degree 2.0; mechanism confirmed=true.
Idea: Resistance-certified tree-support transformer, 8-seed test MSE mean 0.4319681115 at best idea lr=0.001; paired delta +0.0409341194, 0/8 wins, permutation p=0.0081.

Benchmark result