Weaving Graph over Tokens: Contextualizing Structured Sequences for LLMs

Abstract

Generative Graph Language Models (GLMs) must reconcile topology with causal language modeling. Linearization obscures multi-hop connectivity, while encoder-based methods bottleneck token-level reasoning during generation. Viewing context modeling as a form of message passing, we introduce **Weaver**, an encoder-free framework that extends the attention mechanism of decoder-only LLMs to enable graph reasoning. Weaver maps graph distances into rotary positional embeddings so that structurally connected nodes become proximate in attention space, propagating information over graph topology as if it were sequential context. To achieve this, we combine: 1) a masking mechanism for causal tokens with graph structures; 2) a unified geometric encoding that couples sequential position and graph distance in joint rotary embeddings (Graph-over-Tokens RoPE); and 3) a design principle to prioritize local information to resolve positional ambiguity under graph symmetries. On zero-shot benchmarks, Weaver achieves state-of-the-art performance among generative GLMs, with gains of up to 30\% over prior generative methods on heterophilic graphs, while matching specialized discriminative models on citation networks---all within a unified decoder-only framework.