Graph Machine (GM), Cutting the Transformer in Half

Why a graph structure now

A Transformer keeps state of size Θ(n) in its keys and values, but as each token accesses the entire state, the compute cost balloons to Θ(n²). Methods like sliding windows reduce the access range to Θ(1), but the access positions are fixed independently of the input content, making it easy to miss the information you actually need. This paper finds the middle ground: keep state at O(n) while dynamically selecting and accessing only the parts you need.

The core idea is to use edges like pointers. GM (Graph Machine) introduces two new submodules, SER (Sparse Edge Referral) and SEA (Sparse Edge Attention). Here an edge carries both an integer index and a real-valued weight: the index points to where to look, and the weight expresses the importance of that path. The referral mechanism updates edges by referencing the neighbors of the current neighbors, and attention reads only the keys and values of the small set of positions these edges point to.

The decisive difference from conventional attention

The paper classifies sequence models by three criteria: state size, access size, and dynamic address bits. RNNs/SSMs have both state and access at Θ(1), so they must compress the past; a vanilla Transformer has Θ(n) state but Θ(n) access, so compute is expensive. A sliding-window Transformer has Θ(n) state and Θ(1) access, but its addressing is static. GM belongs to a fourth category that satisfies Θ(n) state, Θ(1) access, and Θ(log n) dynamic addressing. At a sequence length of 4,096 tokens, reading only 2 or 4 positions is 0.098% and 0.195% of dense attention respectively — a numerical demonstration of the savings.

Source: arXiv:2609.02881 Figure 1

Image: arXiv:2609.02881 Figure 1 · Hou · CC BY 4.0 · unmodified

Source: arXiv:2609.02881 Figure 2

Image: arXiv:2609.02881 Figure 2 · Hou · CC BY 4.0 · unmodified

What the structure looks like

GM's state consists of node features, edge indices, and edge weights. Each token's initial edges point to itself and the immediately preceding k-1 tokens, and as layers proceed the edges are reconstructed via referral. Sparse layers repeat in the order edge-referral submodule, edge-attention submodule, and MLP, and are trained as a GLM (Graph Language Machine) mixed with dense layers.

Referral is an operation that constructs the ℓ-hop neighborhood in one step, equivalent to approximating the adjacency matrix Aℓ as a sparse matrix. In the attention step, the query·key scores and the edge weights are added in logit space and passed through softmax, forming the final weights in a product-of-experts fashion. Interestingly, there is a realignment option that writes the indices and weights used after sparse attention back into some of the stored edges, creating a loop that corrects the pointer distribution with the feature evidence attention observed.

Actual training results

The experiments are based on Qwen3-0.6B, replacing 75% of the dense Transformer layers with GM sparse layers and pretraining from scratch at a scale of 15.7B tokens. Model names are distinguished by sparsity budget, number of stored edges, number of referral steps, and whether dense-refresh is used. The Theia line uses a (2,4,4,2) budget to read 2 positions per KV head, while Hyperion uses (4,4,4,4) to read 4 positions.

Training took 53–236 hours on a single H100 SXM, with most GLM configurations clustered in the 150–160 hour range. By test loss, Qwen3 is at 2.587 at the 100% training point, the best Theia is +0.014, and the best Hyperion is -0.003. In particular, Hyperion-K16-R3-S with dense-refresh recorded the lowest overall loss. Performance improvement is clear when referral steps go from 0 to 3, but increasing them further does not always help. It is also interesting that parameter count and total compute are not strong predictors of performance — Hyperion-K16-R3-S was relatively cheap yet achieved the best performance.

Can it actually be used?

With the current prototype implementation, GLM is several times slower than Qwen3 on the same hardware. On an RTX 4090, some configurations came close to Qwen3's training throughput, suggesting that the real performance ratio depends heavily on kernel implementation and hardware. Also, the experiments presented in the paper only go as far as pretraining a 0.6B-scale language model and looking at a single test loss. Downstream tasks, larger scales, and combinations with other architectures are all future work.

Closing

The clearest number GM showed is this: you can almost throw away dense attention without cutting language-model quality much. The fact that a sparse attention reading only 2 or 4 positions produced the lowest loss suggests that attention's role can be reinterpreted as address delivery and resolution rather than global search. How far this structure — keeping state at O(n) while reading only what it needs — can push efficiency in real systems is the next step, one that kernels and hardware will have to keep up with.

References

• Graph Machine: Towards Better Pretraining via Edges, arXiv:2609.02881