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

arXiv:2610.37524v1 Announce Type: new 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 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 (extbf{WPNet}), this work introduces extbf{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 (8192imes) on a single commodity GPU in linear O(N) memory, maintaining near-perfect accuracy where standard and RoPE Transformers suffer from out-of-distribution attention collapse and out-of-memory exhaustion.

Source: arXiv cs.LG | 2026-10-28