GTFormer: A Syntax-Free Graph Network Alternative to Transformers for 8192$\times$ Length Extrapolation in Linear Time

Elisabeth Fink

cs.LGOct 27, 2026

GTFormer: A Syntax-Free Graph Network Alternative to Transformers for 8192 $\times$ Length Extrapolation in Linear Time

Authors: Elisabeth Fink

Organizations: Middlesex University, Department of Computer Science The Burroughs, Hendon, London NW4 4BT, UK.

Abstract

Self-attention mechanisms have established the Transformer as the dominant backbone across natural language processing, source code intelligence, and automated theorem proving. However, all-to-all pairwise token comparison enforces a quadratic $\mathcal{O}(N^2)$ compute and memory barrier alongside severe softmax attention dilution as sequence length $N$ scales beyond the training horizon. Inspired by recent advances in algebraic graph learning (WPNet), this work introduces GTFormer, a syntax-free hierarchical Graph Neural Network (GNN) that replaces flat self-attention for general long-context sequence modeling. GTFormer organizes raw token streams into a bounded-degree hierarchy combining a balanced binary reduction tree ( $\lceil \log_2 N \rceil$ depth), horizontal boundary-bridging shift edges, random expander shortcuts, multi-channel convex highway gating, and a top-down broadcast pass. Across eight long-context code, log, and multi-hop retrieval benchmarks trained exclusively on sequences of length $N \le 512$ , GTFormer extrapolates zero-shot to $N = 4{,}194{,}304$ ( $8192\times$ ) on a single commodity GPU in linear $\mathcal{O}(N)$ memory, maintaining near-perfect accuracy where standard and RoPE Transformers suffer from out-of-distribution attention collapse and out-of-memory exhaustion.

Figures & tables

Panel of Figure 1 — Figure 1: Structural comparison of information routing over a sequence of length $N=8$ containing an odd-split key-value binding $[K_{r},V_{v}]$ at indices $(3,4)$ and a pointer $[P_{p},K_{r}]$ at indices $(7,8)$ . (a) GTFormer: Local 1-hop horizontal shift edges (orange) bind adjacent tokens across odd binary boundaries before hierarchical reduction. At each tree level, shared-salience convex highway gates suppress filler nodes (dashed gray) and route active variable and pointer channels (solid blue) to the root in $\log_{2}N$ steps and $O(N)$ memory. (b) Flat Transformer: All-to-all $O(N^{2})$ self-attention connects every filler token to every other token, causing severe softmax attention dilution on out-of-distribution lengths and quadratic VRAM exhaustion.

Task Name	Input Token Sequence ( $N=16$ )	Event Progression / Semantics	Target Class
override_qa	[42, 203, 118, 207, 12, 201, 88, 206, 91, 155, 202, 33, 200, 77, 94, 18]	$r_{0}\leftarrow 3\to r_{1}\leftarrow 3\to r_{0}\leftarrow 1\to r_{1}\leftarrow 2\to r_{2}\leftarrow 1$ . Final state: $[1,2,1]$	25
unaligned_kv	[42, 118, 12, 200 , 205 , 88, 201 , 203 , 91, 155, 202 , 206 , 33, 200 , 204 , 77]	Odd-boundary pairs: $[K_{0},V_{2}]\to[K_{1},V_{0}]\to[K_{2},V_{3}]\to[K_{0},V_{1}]$ . Final state: $[1,0,3]$	19
pointer_hop_triple	[14, 213 , 83, 212 , 90, 214 , 111, 200 , 211 , 49, 201 , 208 , 170, 202 , 210 , 88]	$V_{0}\leftarrow 3$ , $V_{1}\leftarrow 0$ , $V_{2}\leftarrow 2$ ; Dereference $\text{PTR}_{0}\to V_{1}$ , $\text{PTR}_{1}\to V_{0}$ , $\text{PTR}_{2}\to V_{2}$ $\implies$ final values = [0, 3, 2]	14
intrusion_fsm	[81, 203 , 45, 207 , 19, 250 , 99, 110, 202 , 130, 14, 66, 92, 140, 50, 12]	$r_{0}\leftarrow 3,r_{1}\leftarrow 3\to\text{{RESET}}(250)\implies[0,0,0]\to r_{0}\leftarrow 2$ Final state: $[2,0,0]$	32
code_scope_shadow	[ 202 , 41, 260 , 12, 203 , 89, 261 , 73, 99, 102, 18, 45, 160, 11, 82, 39]	Global $r_{0}\leftarrow 2\to\text{{ENTER}}(260)\to\text{Local }r_{0}\leftarrow 3\to\text{{EXIT}}(261)\implies$ revert to 2 Final state: [2,0,0]	32
multi_needle_rag	[18, 201 , 207 , 44, 210 , 92, 200 , 206 , 11, 145, 202 , 209 , 67, 83, 104, 5]	Query $Q_{0}(210)\implies\text{retrieve }(E_{0},E_{1},E_{2})$ ; Bindings: $E_{1}\leftarrow 1,E_{0}\leftarrow 0,E_{2}\leftarrow 3$ Retrieved slots: $[0,1,3]$	7

Table 1: Representative token input sequences, event streams, and target output states across the eight benchmark tasks for sequence length

N=16

(vocabulary size

V=320

). Filler tokens

t\in[0,199]

represent background noise; tokens

t\geq 200

carry structured operational semantics.

Panel of Figure 2 — Figure 2: Architecture of the syntax-free GTFormer topology shown for $N=8$ ( $D=3$ ). At Level $d=0$ , an unaligned two-token phrase $[\textit{KEY},\textit{VAL}]$ at odd indices $(v_{1}^{(0)},v_{2}^{(0)})$ straddles the boundary between subtrees $v_{0}^{(1)}$ and $v_{1}^{(1)}$ , but is bound locally via the horizontal shift edge $\mathcal{E}_{\text{shift}}$ ( $v_{2}^{(0)}\to v_{1}^{(0)}$ ). Bottom-up tree edges $\mathcal{E}_{\text{tree}}$ and horizontal expander shortcuts $\mathcal{E}_{\text{exp}}$ compress sequence state in $\log_{2}N$ steps, while top-down broadcast edges $\mathcal{E}_{\text{down}}$ resolve remote pointer queries ( PTR ).

Model Variant	Topology	Local Shift	Expander	Convex Gate	Top-Down	Primary Role / Ablation Target
		( use_local_shift )	( use_expander )	( use_convex_gate )	( use_top_down )
GTFormer_Bidirectional	Hierarchical	✓	✓	✓	✓	Full proposed architecture
GTFormer_BottomUp	Hierarchical	✓	✓	✓	✗	Feed-forward root readout only
GTFormer_NoExpander	Hierarchical	✓	✗	✓	✓	Ablates horizontal peer shortcuts ( $\mathcal{E}_{\text{exp}}$ )
Pure_Binary_Tree	Hierarchical	✗	✗	✓	✓	No horizontal edges; tests odd-index splitting
Unbounded_Tree_MLP	Hierarchical	✓	✓	✗	✓	Unconstrained MLP merge; tests depth drift

Table 2: Architectural comparison of evaluated model variants and ablation configurations.

Architecture	Time	Memory	Graph	Max	Odd-Split	2-Hop Ptr
			Diam.	Fan-In	Safe	Safe
Flat Transformer (Sin / RoPE)	$\mathcal{O}(N^{2})$	$\mathcal{O}(N^{2})$	$1$	$N$	Yes	Yes (ID)
Pure Binary Tree-GNN	$\mathcal{O}(N)$	$\mathcal{O}(N)$	$2\log N$	$2$	No	No
Unbounded Tree-MLP	$\mathcal{O}(N)$	$\mathcal{O}(N)$	$2\log N$	$3$	Yes	No
GraphTree (Bottom-Up)	$\mathcal{O}(N)$	$\mathcal{O}(N)$	$\leq 2\log N$	$4$	Yes	Partial
GraphTree (Bidirectional)	$\mathbf{\mathcal{O}(N)}$	$\mathbf{\mathcal{O}(N)}$	$\mathbf{\leq 2\log N}$	$\mathbf{4}$	Yes	Yes ( $1024\times$ )

Table 3: Theoretical complexity and structural comparison across sequence length

N

. Bounded fan-in (

\Delta_{\text{in}}\leq 4

) and convex highway gating enable scalable linear extrapolation to

N=4{,}194{,}304

without attention dilution.

Figure 3: Average performance on all tests in zero-shot extrapolation of all architectures.

Architecture	$N=64$ (ID)	$N=256$ (ID)	$N=512$ (ID)	$N=1024$	$N=4096$	$N=16384$
GraphTree (Bidirectional: Up + Down)	$70.8\%$	$72.0\%$	$72.1\%$	$72.2\%$	$71.8\%$	$71.2\%$
GraphTree (Bottom-Up + Shortcuts)	$97.3\%$	$97.3\%$	$97.3\%$	$97.3\%$	$97.3\%$	$95.5\%$
GraphTree (Local Shift, No Expander)	$97.8\%$	$97.9\%$	$98.0\%$	$97.8\%$	$97.9\%$	$97.7\%$
Pure Binary Tree-GNN (No Shortcuts)	$86.7\%$	$86.5\%$	$86.9\%$	$86.9\%$	$85.9\%$	$83.3\%$
Unbounded Tree-GNN (No Convex Gate)	$3.0\%$	$3.1\%$	$3.5\%$	$3.1\%$	$3.1\%$	$2.8\%$
Flat Transformer (Sinusoidal)	$59.5\%$	$54.3\%$	$53.9\%$	$32.4\%$	$16.0\%$	OOM

Table 4: Aggregate summary of results over all eight tasks (OOM=Out-Of-Memory).

Architecture	$N=64$	$N=256$	$N=512$	$N=1024$	$N=4096$	$N=16384$
GraphTree (Local Shift, No Expander)	31 MB	64 MB	108 MB	196 MB	373 MB	725 MB
GraphTree (Bottom-Up + Shortcuts)	32 MB	65 MB	109 MB	197 MB	373 MB	726 MB
GraphTree (Bidirectional: Up + Down)	34 MB	66 MB	111 MB	199 MB	375 MB	728 MB
Pure Binary Tree-GNN	24 MB	36 MB	54 MB	88 MB	156 MB	292 MB
Unbounded Tree-GNN	32 MB	64 MB	109 MB	197 MB	373 MB	726 MB
Flat Transformer (Sinusoidal)	27 MB	45 MB	69 MB	117 MB	213 MB	OOM

Table 5: Memory usage per model and evaluation lenght.

Architecture	$N=64$	$N=256$	$N=512$	$N=1024$	$N=4096$	$N=16384$
GraphTree (Local Shift, No Expander)	0.17 ms	0.23 ms	0.29 ms	0.38 ms	1.12 ms	3.65 ms
GraphTree (Bottom-Up + Shortcuts)	0.24 ms	0.34 ms	0.40 ms	0.51 ms	1.57 ms	5.38 ms
GraphTree (Bidirectional: Up + Down)	0.34 ms	0.42 ms	0.49 ms	0.60 ms	1.69 ms	5.57 ms
Pure Binary Tree-GNN	0.16 ms	0.19 ms	0.21 ms	0.30 ms	0.75 ms	2.33 ms
Unbounded Tree-GNN	0.12 ms	0.17 ms	0.21 ms	0.29 ms	0.89 ms	2.79 ms
Flat Transformer (Sinusoidal)	0.13 ms	0.12 ms	0.17 ms	0.36 ms	2.10 ms	OOM

Table 6: Average training times of all models across the eight tasks.

Figure 4: Performance of the architecture variations on the eight defined tasks.

Appendix figures & tables16 assets

Supplementary material from the paper’s appendix.

Appendix

Architecture	$N=64$ (ID)	$N=256$ (ID)	$N=512$ (ID)	$N=1024$ (OOD)	$N=4096$ (OOD)	$N=16384$ (OOD)
GraphTree (Bidirectional: Up + Down)	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$
GraphTree (Bottom-Up + Shortcuts)	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$
GraphTree (Local Shift, No Expander)	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$
Pure Binary Tree-GNN (No Shortcuts)	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$
Unbounded Tree-GNN (No Convex Gate)	$1.5\pm 0.8\%$	$1.6\pm 0.9\%$	$1.6\pm 0.6\%$	$1.1\pm 0.8\%$	$1.4\pm 1.0\%$	$1.2\pm 1.2\%$
Flat Transformer (Sinusoidal)	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$16.0\pm 4.4\%$	$6.1\pm 3.8\%$	OOM

Appendix

Table A1: Zero-shot length extrapolation accuracy on task override_qa (Part 1).

Architecture	$N=65536$	$N=131072$	$N=262144$	$N=524288$	$N=1048576$	$N=2097152$
GraphTree (Bidirectional: Up + Down)	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$98.8\pm 2.5\%$	$98.8\pm 2.5\%$	$97.5\pm 3.1\%$
GraphTree (Bottom-Up + Shortcuts)	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$
GraphTree (Local Shift, No Expander)	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$
Pure Binary Tree-GNN (No Shortcuts)	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$
Unbounded Tree-GNN (No Convex Gate)	$1.9\pm 1.5\%$	$1.2\pm 2.5\%$	$1.2\pm 2.5\%$	$3.8\pm 3.1\%$	$3.8\pm 5.0\%$	$0.0\pm 0.0\%$
Flat Transformer (Sinusoidal)	OOM	OOM	OOM	OOM	OOM	OOM

Appendix

Table A2: Zero-shot length extrapolation accuracy on task override_qa (Part 2).

Architecture	$N=64$ (ID)	$N=256$ (ID)	$N=512$ (ID)	$N=1024$ (OOD)	$N=4096$ (OOD)	$N=16384$ (OOD)
GraphTree (Bidirectional: Up + Down)	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$
GraphTree (Bottom-Up + Shortcuts)	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$99.7\pm 0.6\%$
GraphTree (Local Shift, No Expander)	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$
Pure Binary Tree-GNN (No Shortcuts)	$98.9\pm 1.1\%$	$98.0\pm 1.1\%$	$99.3\pm 0.8\%$	$98.7\pm 0.9\%$	$96.2\pm 4.3\%$	$91.2\pm 9.6\%$
Unbounded Tree-GNN (No Convex Gate)	$0.8\pm 0.6\%$	$1.0\pm 0.7\%$	$1.8\pm 0.8\%$	$1.7\pm 0.6\%$	$1.2\pm 0.4\%$	$0.6\pm 0.8\%$
Flat Transformer (Sinusoidal)	$19.8\pm 3.8\%$	$7.8\pm 2.5\%$	$4.4\pm 0.7\%$	$2.3\pm 0.2\%$	$1.4\pm 0.9\%$	OOM

Appendix

Table A3: Zero-shot length extrapolation accuracy on task unaligned_kv (Part 1).

Architecture	$N=65536$	$N=131072$	$N=262144$	$N=524288$	$N=1048576$	$N=2097152$
GraphTree (Bidirectional: Up + Down)	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$
GraphTree (Bottom-Up + Shortcuts)	$96.9\pm 6.2\%$	$95.0\pm 10.0\%$	$88.8\pm 22.5\%$	$82.5\pm 35.0\%$	$81.2\pm 34.5\%$	$77.5\pm 39.0\%$
GraphTree (Local Shift, No Expander)	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$
Pure Binary Tree-GNN (No Shortcuts)	$86.9\pm 14.3\%$	$75.0\pm 23.1\%$	$72.5\pm 19.2\%$	$56.2\pm 34.0\%$	$58.8\pm 31.8\%$	$60.0\pm 30.0\%$
Unbounded Tree-GNN (No Convex Gate)	$0.6\pm 1.2\%$	$1.2\pm 2.5\%$	$0.0\pm 0.0\%$	$0.0\pm 0.0\%$	$2.5\pm 3.1\%$	$3.8\pm 3.1\%$
Flat Transformer (Sinusoidal)	OOM	OOM	OOM	OOM	OOM	OOM

Appendix

Table A4: Zero-shot length extrapolation accuracy on task unaligned_kv (Part 2).

Architecture	$N=64$ (ID)	$N=256$ (ID)	$N=512$ (ID)	$N=1024$ (OOD)	$N=4096$ (OOD)	$N=16384$ (OOD)
GraphTree (Bidirectional: Up + Down)	$8.1\pm 1.5\%$	$10.4\pm 2.4\%$	$10.7\pm 1.0\%$	$12.0\pm 2.6\%$	$11.6\pm 1.8\%$	$8.4\pm 1.6\%$
GraphTree (Bottom-Up + Shortcuts)	$88.4\pm 23.1\%$	$88.0\pm 24.0\%$	$88.1\pm 23.8\%$	$88.0\pm 24.0\%$	$89.2\pm 20.8\%$	$75.9\pm 35.2\%$
GraphTree (Local Shift, No Expander)	$92.5\pm 15.0\%$	$93.5\pm 12.9\%$	$93.8\pm 12.3\%$	$92.9\pm 14.2\%$	$93.6\pm 12.8\%$	$92.2\pm 15.6\%$
Pure Binary Tree-GNN (No Shortcuts)	$9.0\pm 2.1\%$	$10.8\pm 2.3\%$	$10.8\pm 1.3\%$	$10.8\pm 1.7\%$	$10.5\pm 1.1\%$	$11.6\pm 2.3\%$
Unbounded Tree-GNN (No Convex Gate)	$1.5\pm 0.8\%$	$1.2\pm 0.7\%$	$2.2\pm 1.0\%$	$1.7\pm 0.6\%$	$1.9\pm 0.8\%$	$1.6\pm 1.0\%$
Flat Transformer (Sinusoidal)	$8.7\pm 1.8\%$	$5.5\pm 2.0\%$	$4.3\pm 1.3\%$	$3.6\pm 0.7\%$	$2.3\pm 0.9\%$	OOM

Appendix

Table A5: Zero-shot length extrapolation accuracy on task pointer_hop (Part 1).

Architecture	$N=65536$	$N=131072$	$N=262144$	$N=524288$	$N=1048576$	$N=2097152$
GraphTree (Bidirectional: Up + Down)	$3.8\pm 3.1\%$	$7.5\pm 7.3\%$	$0.0\pm 0.0\%$	$2.5\pm 3.1\%$	$1.2\pm 2.5\%$	$1.2\pm 2.5\%$
GraphTree (Bottom-Up + Shortcuts)	$61.2\pm 46.2\%$	$61.2\pm 45.1\%$	$60.0\pm 46.5\%$	$60.0\pm 44.1\%$	$57.5\pm 47.2\%$	$52.5\pm 45.0\%$
GraphTree (Local Shift, No Expander)	$93.1\pm 13.8\%$	$93.8\pm 12.5\%$	$92.5\pm 15.0\%$	$90.0\pm 20.0\%$	$95.0\pm 10.0\%$	$88.8\pm 19.5\%$
Pure Binary Tree-GNN (No Shortcuts)	$13.8\pm 7.3\%$	$11.2\pm 4.7\%$	$11.2\pm 13.3\%$	$8.8\pm 8.5\%$	$8.8\pm 3.1\%$	$12.5\pm 6.8\%$
Unbounded Tree-GNN (No Convex Gate)	$1.2\pm 2.5\%$	$1.2\pm 2.5\%$	$1.2\pm 2.5\%$	$1.2\pm 2.5\%$	$2.5\pm 3.1\%$	$1.2\pm 2.5\%$
Flat Transformer (Sinusoidal)	OOM	OOM	OOM	OOM	OOM	OOM

Appendix

Table A6: Zero-shot length extrapolation accuracy on task pointer_hop (Part 2).

Architecture	$N=64$ (ID)	$N=256$ (ID)	$N=512$ (ID)	$N=1024$ (OOD)	$N=4096$ (OOD)	$N=16384$ (OOD)
GraphTree (Bidirectional: Up + Down)	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$
GraphTree (Bottom-Up + Shortcuts)	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$
GraphTree (Local Shift, No Expander)	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$
Pure Binary Tree-GNN (No Shortcuts)	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$
Unbounded Tree-GNN (No Convex Gate)	$1.7\pm 0.4\%$	$2.1\pm 0.9\%$	$1.8\pm 1.2\%$	$1.6\pm 0.9\%$	$2.3\pm 1.1\%$	$2.8\pm 1.8\%$
Flat Transformer (Sinusoidal)	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$30.8\pm 7.1\%$	$17.7\pm 5.1\%$	OOM

Appendix

Table A7: Zero-shot length extrapolation accuracy on task intrusion_fsm (Part 1).

Architecture	$N=65536$	$N=131072$	$N=262144$	$N=524288$	$N=1048576$	$N=2097152$
GraphTree (Bidirectional: Up + Down)	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$98.8\pm 2.5\%$
GraphTree (Bottom-Up + Shortcuts)	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$98.8\pm 2.5\%$	$100.0\pm 0.0\%$
GraphTree (Local Shift, No Expander)	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$
Pure Binary Tree-GNN (No Shortcuts)	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$
Unbounded Tree-GNN (No Convex Gate)	$1.2\pm 1.5\%$	$5.0\pm 4.7\%$	$1.2\pm 2.5\%$	$1.2\pm 2.5\%$	$0.0\pm 0.0\%$	$1.2\pm 2.5\%$
Flat Transformer (Sinusoidal)	OOM	OOM	OOM	OOM	OOM	OOM

Appendix

Table A8: Zero-shot length extrapolation accuracy on task intrusion_fsm (Part 2).

Architecture	$N=64$ (ID)	$N=256$ (ID)	$N=512$ (ID)	$N=1024$ (OOD)	$N=4096$ (OOD)	$N=16384$ (OOD)
GraphTree (Bidirectional: Up + Down)	$84.9\pm 30.2\%$	$85.8\pm 28.3\%$	$85.5\pm 29.0\%$	$87.0\pm 26.0\%$	$85.3\pm 29.4\%$	$85.6\pm 28.8\%$
GraphTree (Bottom-Up + Shortcuts)	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$
GraphTree (Local Shift, No Expander)	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$
Pure Binary Tree-GNN (No Shortcuts)	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$
Unbounded Tree-GNN (No Convex Gate)	$1.8\pm 0.5\%$	$1.2\pm 0.5\%$	$1.8\pm 0.5\%$	$1.5\pm 0.8\%$	$0.6\pm 0.6\%$	$2.5\pm 1.6\%$
Flat Transformer (Sinusoidal)	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$30.4\pm 15.9\%$	$13.9\pm 5.4\%$	OOM

Appendix

Table A9: Zero-shot length extrapolation accuracy on task code_scope_shadow (Part 1).

Architecture	$N=65536$	$N=131072$	$N=262144$	$N=524288$	$N=1048576$	$N=2097152$
GraphTree (Bidirectional: Up + Down)	$87.5\pm 23.5\%$	$85.0\pm 30.0\%$	$85.0\pm 30.0\%$	$81.2\pm 34.5\%$	$87.5\pm 25.0\%$	$83.8\pm 29.5\%$
GraphTree (Bottom-Up + Shortcuts)	$98.8\pm 2.5\%$	$100.0\pm 0.0\%$	$95.0\pm 7.3\%$	$88.8\pm 17.0\%$	$91.2\pm 9.3\%$	$81.2\pm 15.8\%$
GraphTree (Local Shift, No Expander)	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$98.8\pm 2.5\%$	$98.8\pm 2.5\%$	$100.0\pm 0.0\%$	$98.8\pm 2.5\%$
Pure Binary Tree-GNN (No Shortcuts)	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$
Unbounded Tree-GNN (No Convex Gate)	$1.2\pm 1.5\%$	$1.2\pm 2.5\%$	$2.5\pm 3.1\%$	$2.5\pm 3.1\%$	$0.0\pm 0.0\%$	$2.5\pm 3.1\%$
Flat Transformer (Sinusoidal)	OOM	OOM	OOM	OOM	OOM	OOM

Appendix

Table A10: Zero-shot length extrapolation accuracy on task code_scope_shadow (Part 2).

Architecture	$N=64$ (ID)	$N=256$ (ID)	$N=512$ (ID)	$N=1024$ (OOD)	$N=4096$ (OOD)	$N=16384$ (OOD)
GraphTree (Bidirectional: Up + Down)	$8.2\pm 1.9\%$	$10.7\pm 2.7\%$	$10.9\pm 0.9\%$	$11.3\pm 2.1\%$	$9.1\pm 0.9\%$	$12.2\pm 2.3\%$
GraphTree (Bottom-Up + Shortcuts)	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$
GraphTree (Local Shift, No Expander)	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$
Pure Binary Tree-GNN (No Shortcuts)	$9.2\pm 2.8\%$	$12.2\pm 3.9\%$	$10.8\pm 2.3\%$	$12.2\pm 1.7\%$	$11.4\pm 2.0\%$	$11.2\pm 1.5\%$
Unbounded Tree-GNN (No Convex Gate)	$1.5\pm 0.8\%$	$1.2\pm 0.7\%$	$2.2\pm 1.0\%$	$1.7\pm 0.6\%$	$1.9\pm 0.8\%$	$1.6\pm 1.0\%$
Flat Transformer (Sinusoidal)	$9.1\pm 1.1\%$	$5.0\pm 2.0\%$	$4.8\pm 0.6\%$	$2.9\pm 0.7\%$	$1.9\pm 0.6\%$	OOM

Appendix

Table A11: Zero-shot length extrapolation accuracy on task multi_needle_rag (Part 1).

Architecture	$N=65536$	$N=131072$	$N=262144$	$N=524288$	$N=1048576$	$N=2097152$
GraphTree (Bidirectional: Up + Down)	$11.9\pm 4.6\%$	$13.8\pm 6.1\%$	$11.2\pm 13.3\%$	$6.2\pm 6.8\%$	$8.8\pm 6.4\%$	$8.8\pm 7.5\%$
GraphTree (Bottom-Up + Shortcuts)	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$
GraphTree (Local Shift, No Expander)	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$
Pure Binary Tree-GNN (No Shortcuts)	$12.5\pm 7.1\%$	$12.5\pm 5.6\%$	$16.2\pm 12.9\%$	$8.8\pm 6.4\%$	$13.8\pm 4.7\%$	$16.2\pm 7.5\%$
Unbounded Tree-GNN (No Convex Gate)	$1.2\pm 2.5\%$	$1.2\pm 2.5\%$	$1.2\pm 2.5\%$	$1.2\pm 2.5\%$	$2.5\pm 3.1\%$	$1.2\pm 2.5\%$
Flat Transformer (Sinusoidal)	OOM	OOM	OOM	OOM	OOM	OOM

Appendix

Table A12: Zero-shot length extrapolation accuracy on task multi_needle_rag (Part 2).

Architecture	$N=64$ (ID)	$N=256$ (ID)	$N=512$ (ID)	$N=1024$ (OOD)	$N=4096$ (OOD)	$N=16384$ (OOD)
GraphTree (Bidirectional: Up + Down)	$96.7\pm 6.7\%$	$96.9\pm 6.2\%$	$96.7\pm 6.7\%$	$96.6\pm 6.9\%$	$97.0\pm 5.9\%$	$96.9\pm 6.2\%$
GraphTree (Bottom-Up + Shortcuts)	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$
GraphTree (Local Shift, No Expander)	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$
Pure Binary Tree-GNN (No Shortcuts)	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$
Unbounded Tree-GNN (No Convex Gate)	$11.9\pm 1.8\%$	$14.0\pm 1.8\%$	$15.3\pm 2.1\%$	$10.4\pm 1.8\%$	$11.7\pm 2.6\%$	$8.1\pm 3.8\%$
Flat Transformer (Sinusoidal)	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$99.0\pm 1.3\%$	$51.1\pm 13.0\%$	OOM

Appendix

Table A13: Zero-shot length extrapolation accuracy on task xml_bracket_check (Part 1).

Architecture	$N=65536$	$N=131072$	$N=262144$	$N=524288$	$N=1048576$	$N=2097152$
GraphTree (Bidirectional: Up + Down)	$96.9\pm 6.2\%$	$97.5\pm 5.0\%$	$98.8\pm 2.5\%$	$95.0\pm 10.0\%$	$95.0\pm 10.0\%$	$100.0\pm 0.0\%$
GraphTree (Bottom-Up + Shortcuts)	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$98.8\pm 2.5\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$
GraphTree (Local Shift, No Expander)	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$
Pure Binary Tree-GNN (No Shortcuts)	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$
Unbounded Tree-GNN (No Convex Gate)	$11.2\pm 7.5\%$	$17.5\pm 7.3\%$	$13.8\pm 10.0\%$	$10.0\pm 5.0\%$	$11.2\pm 4.7\%$	$17.5\pm 6.1\%$
Flat Transformer (Sinusoidal)	OOM	OOM	OOM	OOM	OOM	OOM

Appendix

Table A14: Zero-shot length extrapolation accuracy on task xml_bracket_check (Part 2).

Architecture	$N=64$ (ID)	$N=256$ (ID)	$N=512$ (ID)	$N=1024$ (OOD)	$N=4096$ (OOD)	$N=16384$ (OOD)
GraphTree (Bidirectional: Up + Down)	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$99.4\pm 1.2\%$
GraphTree (Bottom-Up + Shortcuts)	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$
GraphTree (Local Shift, No Expander)	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$
Pure Binary Tree-GNN (No Shortcuts)	$98.7\pm 1.1\%$	$98.0\pm 1.0\%$	$99.1\pm 1.0\%$	$99.0\pm 1.1\%$	$97.7\pm 2.6\%$	$91.2\pm 10.9\%$
Unbounded Tree-GNN (No Convex Gate)	$3.0\pm 3.8\%$	$2.9\pm 2.3\%$	$2.4\pm 1.1\%$	$2.9\pm 2.3\%$	$2.8\pm 1.5\%$	$1.9\pm 2.5\%$
Flat Transformer (Sinusoidal)	$17.9\pm 2.8\%$	$3.5\pm 1.0\%$	$3.6\pm 1.7\%$	$1.9\pm 0.6\%$	$1.4\pm 0.6\%$	OOM

Appendix

Table A15: Zero-shot length extrapolation accuracy on task adversarial_decoys (Part 1).

Architecture	$N=65536$	$N=131072$	$N=262144$	$N=524288$	$N=1048576$	$N=2097152$
GraphTree (Bidirectional: Up + Down)	$92.5\pm 15.0\%$	$83.8\pm 32.5\%$	$82.5\pm 35.0\%$	$81.2\pm 37.5\%$	$81.2\pm 37.5\%$	$80.0\pm 40.0\%$
GraphTree (Bottom-Up + Shortcuts)	$99.4\pm 1.2\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$97.5\pm 3.1\%$	$95.0\pm 7.3\%$	$96.2\pm 5.0\%$
GraphTree (Local Shift, No Expander)	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$100.0\pm 0.0\%$	$97.5\pm 5.0\%$	$98.8\pm 2.5\%$
Pure Binary Tree-GNN (No Shortcuts)	$86.2\pm 13.2\%$	$86.2\pm 18.7\%$	$75.0\pm 23.1\%$	$81.2\pm 17.2\%$	$70.0\pm 18.3\%$	$66.2\pm 25.2\%$
Unbounded Tree-GNN (No Convex Gate)	$1.9\pm 3.8\%$	$2.5\pm 3.1\%$	$1.2\pm 2.5\%$	$1.2\pm 2.5\%$	$1.2\pm 2.5\%$	$2.5\pm 3.1\%$
Flat Transformer (Sinusoidal)	OOM	OOM	OOM	OOM	OOM	OOM

Appendix

Table A16: Zero-shot length extrapolation accuracy on task adversarial_decoys (Part 2).

Long-Context Modeling

Long-context modeling studies how AI systems process, retrieve, and reason over sequences that exceed ordinary context windows.

See all 136 papers

Apr 26, 2026

Graph Memory Transformer (GMT)

We investigate whether an explicit learned memory graph can replace the Feed-Forward Network (FFN) sublayer in a decoder-only transformer while preserving the surrounding autoregressive architecture. In the proposed graph Memory Transformer (GMT), a memory cell routes token representations over a learned bank of centroids connected by a learned directed transition matrix, while causal self-attention remains unchanged. In the base v7 instantiation, each of 16 transformer blocks contains 128 centroids and a 128 x 128 edge matrix. Each cell uses gravitational source routing and token-conditioned target selection to return a gated displacement from the estimated source memory state toward the target memory state, rather than a retrieved value. The resulting decoder-only language model has 82.2M trainable parameters and no dense FFN sublayers; the evaluated dense GPT-style baseline has 103.0M. It trains stably and exposes centroid usage, transition structure, and source-to-target movement for direct inspection in the forward computation. It trails the larger baseline in validation loss and perplexity (3.5995/36.58 vs. 3.2903/26.85), while showing close zero-shot benchmark behavior under the evaluated setting. These results support the viability and structural interpretability of replacing dense within-token transformation with graph-mediated memory navigation, without claiming state-of-the-art performance. Broader scaling, optimized kernels, and more extensive benchmark evaluation remain for future work.

Nicola Zanarini, Niccolò Ferrari, Evelina Lamma

Bonfiglioli Engineering s.r.l. · Department of Engineering, University of Ferrara, Via Saragat 1, 44122 Ferrara, Italy · NAIS s.r.l., Via Maria Callas 4, 40131 Bologna, Italy

Memory-Augmented Neural Networks Transformer FFNs Graph Neural Networks Memory-Augmented Language Models Transformer Decoder-Only Language Models

Ask PDF

May 11, 2026

Teaching LLMs to See Graphs: Unifying Text and Structural Reasoning

Using Large Language Models (LLMs) to process graph-structured data is an active research area, yet current state-of-the-art approaches typically rely on multi-step pipelines with Graph Neural Network (GNN) encoders that compress rich textual attributes into solitary tokens, creating a significant semantic bottleneck. In this paper, we introduce the Graph Transformer Language Model (GTLM), a novel architecture that enables pretrained LLMs to natively process graph topologies while entirely eliminating this compressive bottleneck. GTLM is exceptionally parameter-efficient: by injecting graph-aware attention biases directly into the LLM's attention modules, it introduces only 0.015% additional parameters relative to the base model. We theoretically prove that our bidirectional attention prefix preserves node permutation equivariance while maintaining exact backward compatibility with the pretrained base model. Extensive evaluations demonstrate that a 1B-parameter GTLM matches or exceeds the performance of 7B-parameter state-of-the-art models on standard Text-Attributed Graph benchmarks, while significantly surpassing baselines on GraphQA. Finally, we demonstrate that GTLM attention heads implicitly learn to simulate message passing, explaining its superior performance on algorithmic tasks. This paradigm shift enables true algorithmic reasoning within LLMs and provides a scalable foundation for next-generation GraphRAG and relational deep learning.

Dario Vajda

Faculty of Computer and Information Science University of Ljubljana

LLM Reasoning with Graphs Text-Attributed Graph Learning Graph Transformer LLM Reasoning LLMs for Graph Learning

Ask PDF

May 31, 2026

LongAttnComp: Cross-Family Context Compression for Long-Context Reasoning

As real-world applications increasingly require processing inputs of 100k+ tokens, the gap between context length and inference efficiency has become a critical bottleneck. Context compression offers a way to reduce prefill costs while preserving task accuracy. However, existing training-free attention-based methods leave substantial gaps in demanding long-context tasks such as code reasoning. We present LongAttnComp, a long-context adaptation of AttnComp that fine-tunes a lightweight cross-attention scoring layer and introduces tokenlevel chunking, a token-budget top-p algorithm, positional reordering, and a formatagnostic query parser. We further design a two-stage fine-tuning recipe for the compressor: Stage 1 builds a general retrieval foundation from NIAH-style data, and Stage 2 extends it with multi-hop and reasoning data for broader long-context task coverage. On InfiniteBench Code-Debug, LongAttnComp matches or exceeds full-context accuracy, substantially outperforms training-free baselines, and transfers across four target models from three families. On LongBench v2, the two-stage recipe largely closes the Stage 1 gap on multi-document reasoning while preserving Code-Debug performance.

Mengmeng Ji, Ravi Shanker Raju, Jonathan Lingjie Li +1

SambaNova Systems, Inc. San Jose, CA, USA

LLM Compression LLM Fine-Tuning LLM Inference Acceleration Long-Context Inference LLM Context Compression

Ask PDF

Abstract

Long-Context Modeling

Explore similar work

Graph Memory Transformer (GMT)

Teaching LLMs to See Graphs: Unifying Text and Structural Reasoning

LongAttnComp: Cross-Family Context Compression for Long-Context Reasoning