Graph Machine architecture uses dynamic sparse routing to handle large state efficiently

Replacing 75% of dense Transformer layers with GM sparse layers, the model matches or slightly improves loss while retrieving only 2-4 tokens per head.

PaperIndependentcs.LGarXiv:2609.02881v1 ↗

Lintai Hou

Research Digest·4 September 2026·2 min read

Read the paper →

The authors introduce the Graph Machine (GM), an architecture that maintains an O(n)-sized state and accesses it via sparse, dynamic routing using edges—pointer-like objects updated by a referral mechanism. They replace 75% of the dense Transformer layers in Qwen3-0.6B with GM sparse layers and pretrain from scratch on 15.7B tokens. With only 2 of 4,096 tokens retrieved per KV head per sparse layer, loss degrades only slightly; with 4 tokens, the best model marginally improves loss over the dense baseline.

What they did

The authors propose the Graph Machine (GM) architecture, which maintains a state of size O(n) and accesses it through sparse, dynamic routing via edges—pointer-like objects updated differentiably by a referral mechanism resembling pointer chasing. They replace 75% of the dense Transformer layers in Qwen3-0.6B with GM sparse layers and pretrain from scratch on 15.7B tokens. The baseline is a standard dense Transformer of the same size and training data.

Key findings

With only 2 of 4,096 tokens retrieved per KV head in each sparse layer, loss degrades only slightly compared to the dense baseline.
With 4 tokens retrieved, the best model achieves marginally improved loss over the dense baseline.
The GM architecture preserves O(n) complexity in its sparse layers without restricting the potentially accessible state size to O(1). a - The referral mechanism allows dynamic routing unlike static sparse attention.

Why it matters

This work demonstrates that a large fraction of dense attention can be replaced with sparse, dynamic access with minimal loss degredation, potentially enabling more efficient sequence models that can handle longer contexts without quadratic complexity.

Caveats

The experiments are limited to a single model size (Qwen3-0.6B) and relatively short pre training (15.7B tokens). The improvement over baseline is marginal, and it is unclear how the approach scales to larger models and longer sequences. The replacement ratio (75%) is fixed; the optimal proportion of GM layers might vary with task and scale.

Analysis

The Graph Machine contributes to the line of research seeking to reduce the quadratic complexity of attention while preserving the ability to access a large memory. Unlike methods like sparse transformers or linear attention that restrict access patterns statically, GM learns dynamic routing via differentiable edge updates. This is reminiscent of pointer networks and memory-augmented networks. The results are preliminary but suggest that the approach is viable for pre training, though more extensive evaluation on downstream tasks and at larger scales is needed.