Labeled Incidence Structures for Native Transformer Modeling of Text, Knowledge Graphs, and Hypergraphs

Mahesh Godavarti

cs.LGJul 29, 2026

Labeled Incidence Structures for Native Transformer Modeling of Text, Knowledge Graphs, and Hypergraphs

Authors: Mahesh Godavarti

Organizations: A Carrot, Inc

Abstract

Current Transformer interfaces index tokens by one or more integer coordinates, which determine their addresses inside attention. In RoPE and its multi-axis or hierarchical variants, the resulting address has the form $A(i)=R_1^{i_1}R_2^{i_2}R_3^{i_3}$ , where the exponents are integer coordinates assigned after choosing a serialized token layout. When Transformers process new or large collections of data, this addressing scheme can produce unseen offsets or coordinate combinations, push repositories toward retrieve-and-serialize pipelines, and force new entities, records, or repository items to be represented by long token strings or identifier embeddings not seen in training. We introduce labeled incidence structures (LIS), in which each participating token or value is an endpoint with content $x$ and a structural index $i$ . The index can include local position, relation role, relation instance, text unit, field, or content-derived identity. The model maps this index to a structural address $A(i)$ , so adding new tokens, facts, text units, or repository items applies the same learned address rule to structural and content coordinates rather than requiring larger integer coordinates, unseen coordinate combinations, or new identifier embeddings. Attention scores endpoints $i,j$ using $q_i^\top P_{j\to i}k_j$ , where journey consistency forces $P_{j\to i}=A(i)^{-1}A(j)$ . When $i$ has several coordinates, such as position, role, and instance, coordinate independence is equivalent to factoring $A(i)$ into one address factor per coordinate. This recovers RoPE, RoPE-2D, and HiRoPE as special cases. This allows knowledge-graph (KG) roles, fact instances, and text units to enter the attention score directly. In controlled shallow diagnostics, the LIS address interface is implemented inside ordinary Transformer attention and yields promising results across text, KG, and $n$ -ary settings.

Figures & tables

Diagnostic	Condition	Flat/Serialized	LIS	What is tested
Tiny Shakespeare	PPL, 256 $\to$ 4096 chars	4.70 $\to$ 13.36	4.81 $\to$ 4.86	text units as LIS instances
Independent KG/text	text eval, main tiers	.248–.269	.401–.445	KG-only facts to text queries
Independent KG/text	KG eval, main tiers	.280–.296	.475–.510	text-only facts to KG queries
Template-diverse KG $\to$ text	single-fact test, chain2/3	.126–.359	.923–.972	unseen names with one KG fact
Template-diverse KG $\to$ text	same-entities test, chain2/3	.030–.411	.835–.952	relation choice among distractor facts
Template-diverse KG $\to$ text	same-relation test, chain2/3	.000–.109	.038–.182	hardest entity-binding stress test

Table 1: Representative diagnostics. The plain-text row reports all-token validation PPL from train context 256 to test context 4096. KG/text rows report entity-level h@5 (hit@5) over target names. Full ablations, h@1 scores where reported, and PPL results are in Appendix F . The main tiers are memorization, transfer, and generalization.

Appendix figures & tables10 assets

Supplementary material from the paper’s appendix.

Appendix

Occurrence $v$	$\boldsymbol{\tau(v)}$	Instance $e$	Slot $s$	Address
$v_{1}$ (“Aspirin”, text)	Aspirin	$e_{1}$ (sentence)	$\texttt{POS}_{1}$	$R_{\texttt{POS}_{1}}R_{e_{1}}$
$v_{3}$ (“COX-2”, text)	COX-2	$e_{1}$ (sentence)	$\texttt{POS}_{3}$	$R_{\texttt{POS}_{3}}R_{e_{1}}$
$v_{6}$ (“inflammation”, text)	Inflammation	$e_{1}$ (sentence)	$\texttt{POS}_{6}$	$R_{\texttt{POS}_{6}}R_{e_{1}}$
$v_{7}$ (“Aspirin”, drug)	Aspirin	$e_{2}$ (hyperedge)	drug	$R_{\textsc{drug}}R_{e_{2}}$
$v_{8}$ (“COX-2”, target)	COX-2	$e_{2}$ (hyperedge)	target	$R_{\textsc{target}}R_{e_{2}}$
$v_{9}$ (“Inflammation”, disease)	Inflammation	$e_{2}$ (hyperedge)	disease	$R_{\textsc{disease}}R_{e_{2}}$

Appendix

Table 2: LIS encoding of a text sentence (instance

e_{1}

) and a 3-ary drug–gene–disease hyperedge (instance

e_{2}

). Shared content identifiers link the two structures. Text positions and hyperedge roles are both role labels.

Model	256 chars	512 chars	1024 chars	2048 chars	4096 chars
Continuous RoPE	4.70	5.99	8.23	10.71	13.36
ALiBi	4.96	4.94	4.96	4.93	4.93
Random line address	4.89	4.79	4.90	4.87	4.91
LISformer (content address)	4.81	4.74	4.85	4.83	4.86

Appendix

Table 3: All-token validation perplexity on Tiny Shakespeare after 5,000 training iterations on 256-character chunks. Content-derived line addresses remain approximately constant as evaluation context grows to 16 times the training length. Each row reports one run.

Scale	$d$	Layers	Heads	Batch	B step (ms)	J overhead
0.8M	128	4	4	8	42	+10.3%
85M	768	12	12	4	702	+4.4%
302M	1024	24	16	2	1215	+3.5%
680M	1536	24	16	1	1428	+2.0%

Appendix

Table 4: Training-step timing benchmark for the continuous-RoPE baseline (B) and LISformer (J). Each entry reports wall-clock milliseconds per training step, averaged over 10 timed steps after one warmup step, at context length 1024 on an NVIDIA Tesla T4.

Tier	Serialized h@5	LIS h@5	Serialized PPL	LIS PPL
memorization	.259	.445	3.59	3.10
transfer	.269	.440	3.47	3.08
generalization	.248	.401	3.83	3.48
kg_excl_mem	.184	.329	4.68	3.97
kg_excl_gen	.189	.323	4.92	4.18
txt_excl_mem	.119	.202	5.10	4.62

Appendix

Table 5: Synthetic LIS diagnostic: serialized relation-token baseline versus LIS, using embedding dimension 500, three layers, and 3,000 synthetic names.

Fact type	Name set	Serialized h@1	Serialized h@5	Serialized PPL	LIS h@1	LIS h@5	LIS PPL
base_2ary	train	.002	.130	5.38	.951	1.000	1.08
base_2ary	test	.000	.000	577	.182	.397	6.44
base_3ary	train	.001	.107	5.39	.970	1.000	1.06
base_3ary	test	.000	.000	515	.185	.413	6.44
derived	train	.003	.140	5.29	.912	1.000	1.10
derived	test	.000	.000	544	.165	.385	6.80

Appendix

Table 6: Pure KG

\to

text zero-shot diagnostic. Models use embedding dimension 60, three layers, block size 192, 100K updates, 1000 training names, and 100 unseen test names. Text and KG facts are placed in the same line during training. Evaluation conditions on KG and predicts text.

Fact type	Name set	Serialized h@1	Serialized h@5	Serialized PPL	LIS h@1	LIS h@5	LIS PPL
base_2ary	train	.000	.097	5.50	.927	1.000	1.14
base_2ary	test	.000	.000	516	.148	.310	10.37
base_3ary	train	.000	.090	5.46	.928	.999	1.14
base_3ary	test	.000	.000	517	.143	.307	10.34
derived	train	.000	.080	5.33	.919	.999	1.16
derived	test	.000	.000	506	.115	.287	12.97

Appendix

Table 7: Bidirectional mixed text–KG zero-shot diagnostic. Models use embedding dimension 60, three layers, block size 192, 100K updates, 1000 training names, and 100 unseen test names. Models are trained and evaluated in both KG

\to

text and text

\to

KG directions.

Fact type	Set	Serialized h@1	Serialized h@5	Serialized PPL	LIS h@1	LIS h@5	LIS PPL
chain2	train	.224	.907	2.28	.507	1.000	1.30
chain2	test	.095	.359	6.22	.463	.972	1.37
chain3	train	.011	.743	2.75	.063	.995	1.46
chain3	test	.002	.126	8.64	.050	.923	1.57

Appendix

Table 8: Template-diverse KG

\to

text diagnostic, single-fact setting. The model conditions on one KG fact and predicts a text realization. Scores are over target entity-name characters only.

Fact type	Set	Serialized h@1	Serialized h@5	Serialized PPL	LIS h@1	LIS h@5	LIS PPL
chain2	train	.215	.853	2.58	.483	1.000	1.39
chain2	test	.133	.411	6.23	.388	.952	1.57
chain3	train	.000	.126	15.37	.044	.962	1.64
chain3	test	.000	.030	29.83	.016	.835	1.98

Appendix

Table 9: Template-diverse KG

\to

text diagnostic, same-entities multi-fact prefix setting. The KG prefix contains the true fact and four distractors with the same entities but different relations.

Fact type	Set	Serialized h@1	Serialized h@5	Serialized PPL	LIS h@1	LIS h@5	LIS PPL
chain2	train	.025	.368	6.72	.050	.342	8.29
chain2	test	.009	.109	20.49	.023	.182	17.19
chain3	train	.000	.005	51.44	.001	.112	8.58
chain3	test	.000	.000	101.94	.001	.038	18.24

Appendix

Table 10: Template-diverse KG

\to

text diagnostic, same-relation multi-fact prefix setting. The KG prefix contains the true fact and four distractors with the same relation but different entities.

Setting	Fact type	Set	$B$ h@5	$B_{\ell}$ h@5	$J$ h@5	$B$ PPL	$B_{\ell}$ PPL	$J$ PPL
single-fact	chain2	train	.907	.970	1.000	2.28	1.42	1.30
single-fact	chain2	test	.359	.925	.972	6.22	1.58	1.37
single-fact	chain3	train	.743	.994	.995	2.75	1.50	1.46
single-fact	chain3	test	.126	.912	.923	8.64	1.66	1.57
same-entities	chain2	train	.853	.973	1.000	2.58	1.91	1.39
same-entities	chain2	test	.411	.872	.952	6.23	2.35	1.57

Appendix

Table 11: Template-diverse KG

\to

text diagnostic with a serialized content-addressing control.

B_{\ell}

uses the same serialized input format as

B

, but resets positions by segment and adds a content-derived segment angle.

J

is the native LIS model with role/slot addresses and content-derived fact addresses.

Explore similar work

Sep 26, 2025cs.LG

Rotary Position Encodings for Graphs

We study the extent to which rotary position encodings (RoPE), a recent transformer position encoding algorithm broadly adopted in large language models (LLMs) and vision transformers (ViTs), can be applied to graph-structured data. We find that rotating tokens depending on the spectrum of the graph Laplacian efficiently injects structural information into the attention mechanism, boosting performance in synthetic and real-world graph learning tasks. This approach, coined Wave-Induced Rotary Encodings (WIRE), enjoys intriguing theoretical properties: it recovers regular RoPE on grids, and depends asymptotically on the graph effective resistance. Unlike bias-based relative position encodings, WIRE is compatible with linear attention.

Isaac Reid, Arijit Sehanobish, Cederik Höfs +7

University of Cambridge · Google DeepMind · Independent Researcher +3

Positional Encoding Transformer Architectures Graph Laplacians

Ask PDF

May 21, 2026cs.LG

Lost in Tokenization: Fundamental Trade-offs in Graph Tokenization for Transformers

Transformers have become a central architecture for graph learning, but their application to graphs requires first choosing a tokenization: a graph-to-token map that determines which structural information is exposed at the input. In this work, we show that this choice is a fundamental component of transformer expressivity. We examine three tokenizations that serve as building blocks for many existing graph tokenizations: spectral, random-walk, and adjacency tokenizations. We prove that different tokenizations induce distinct depth regimes: the same graph computation may be realizable by a shallow transformer under one tokenization, while requiring substantially larger depth under another. For example, we prove that random-walk tokenization is lossy for any walk length, making it impossible in general to recover the graph from it, and that while spectral tokenization is lossless, it is ill-conditioned for local tasks. We further show that although both random-walk and spectral tokenizations are derived from adjacency information, it is impossible for a limited-depth transformer to convert between tokenization families in general. In particular, we establish lower bounds and impossibility results showing that unfavorable tokenizations may preclude the efficient recovery of more suitable structural representations. Finally, we complement our theory with controlled experiments on synthetic and real-world tasks, validating the predicted separations and showing that different tasks favor different structural views, and combining complementary tokenizations allows the transformer to leverage distinct signals from each representation.

Maya Bechler-Speicher, Gilad Yehudai, Gil Harari +3

Meta AI · John A. Paulson School of Engineering and Applied Sciences, Harvard University · Google Research +2

Multiplex Graph Transformers Transformer Architectures Trade-Off

Ask PDF

May 11, 2026cs.LG

Teaching LLMs to See Graphs: Unifying Text and Structural Reasoning

Using Large Language Models (LLMs) to process graph-structured data is an active research area, yet current state-of-the-art approaches typically rely on multi-step pipelines with Graph Neural Network (GNN) encoders that compress rich textual attributes into solitary tokens, creating a significant semantic bottleneck. In this paper, we introduce the Graph Transformer Language Model (GTLM), a novel architecture that enables pretrained LLMs to natively process graph topologies while entirely eliminating this compressive bottleneck. GTLM is exceptionally parameter-efficient: by injecting graph-aware attention biases directly into the LLM's attention modules, it introduces only 0.015% additional parameters relative to the base model. We theoretically prove that our bidirectional attention prefix preserves node permutation equivariance while maintaining exact backward compatibility with the pretrained base model. Extensive evaluations demonstrate that a 1B-parameter GTLM matches or exceeds the performance of 7B-parameter state-of-the-art models on standard Text-Attributed Graph benchmarks, while significantly surpassing baselines on GraphQA. Finally, we demonstrate that GTLM attention heads implicitly learn to simulate message passing, explaining its superior performance on algorithmic tasks. This paradigm shift enables true algorithmic reasoning within LLMs and provides a scalable foundation for next-generation GraphRAG and relational deep learning.

Dario Vajda

Faculty of Computer and Information Science University of Ljubljana

Multiplex Graph Transformers Graph-Llm Integrations Graph-Based Retrieval Augmented Generation Relational Deep Learning Reasoning Skills Bottlenecks+1

Ask PDF