Weaving Graph over Tokens: Contextualizing Structured Sequences for LLMs

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.

Large language models usually read information as a sequence of words, from beginning to end. But many important kinds of information are better understood as connected items rather than linear text. Social networks, citation networks, molecules, maps, and knowledge bases all have this kind of structure. This raises a simple question: what if the context given to a language model were a network of relationships instead of a line of text? We introduce Weaver, a method that helps language models use connected information more directly. Existing approaches often turn a network into a long piece of text, which can hide important links, or use a separate network-processing model, which may lose useful details before the language model sees them. Weaver instead builds relationship information into the model’s attention, the part of the model that decides which pieces of information should influence each other. This helps related items in the network interact in a more structured way. Our results show that Weaver improves reasoning over structured data, especially for questions that require following links across multiple steps. This suggests that language models can better handle network-shaped information when relationships are represented directly inside the model.