Graph Serializations for Reasoning LLMs: A Study Across Knowledge Extraction and Structural Reasoning

Julien Yu; Mihaela Bornea; Avirup Sil; Katrin Kirchhoff

cs.AIOct 15, 2026

Graph Serializations for Reasoning LLMs: A Study Across Knowledge Extraction and Structural Reasoning

Authors: Julien Yu, Mihaela Bornea, Avirup Sil, Katrin Kirchhoff

Organizations: Oracle

Abstract

The way a knowledge graph is serialized as text for inclusion into LLM context can substantially affect downstream LLM performance, with prior work reporting tens of percentage points variations across formats. However, existing studies consider only a limited set of representations and predate frontier reasoning models, which now offer stronger reasoning, instruction-following, and long-context capabilities. We evaluate 15 graph representation formats across nine frontier LLM configurations on ontology-based knowledge extraction and structural graph reasoning tasks. While knowledge extraction is relatively insensitive to different serialization formats, the choice of the optimal format for structural reasoning tasks significantly affects accuracy. We demonstrate that the optimal representation choice depends on model, query, and task and propose to approach graph serialization as a dynamic orchestration decision.

Figures & tables

formal semantics (RDF/OWL)	turtle , jsonld , shacl_lite
structured natural language	text2kgbench , entity_centric
	relation_indexed
tabular	markdown_table , toon
visual / diagrammatic	mermaid , dot
connectivity-focused	adjacency , edge_list , structured
prose	nl_summary , friendship

Table 1: Graph formats by semantic explicitness.

model	Text2KGBench	GraphQA	GraphQA-Hardened	GraphQA-Topology
gpt-5.4-high-reasoning	turtle $54.7$ / $1.9$	structured $100.0$ / $0.6$	—	—
gpt-5.4	mermaid $52.7$ / $3.3$	shacl_lite $93.3$ / $4.8$	nl_summary $64.2$ / $12.6$	jsonld $90.3$ / $15.3$
gpt-5.4-mini	shacl_lite $50.6$ / $2.6$	jsonld $79.4$ / $8.5$	jsonld $41.0$ / $8.4$	jsonld $58.3$ / $16.7$
o3	shacl_lite $54.9$ / $2.1$	adjacency $98.2$ / $2.4$	nl_summary $87.4$ / $11.6$	structured $90.3$ / $9.7$
claude-sonnet-4-6-thinking	jsonld $53.0$ / $2.9$	text2kgbench $97.0$ / $3.6$	text2kgbench $83.2$ / $4.2$	jsonld $95.8$ / $5.5$
claude-sonnet-4-6	jsonld $52.2$ / $2.3$	nl_summary $94.5$ / $2.4$	entity_centric $87.4$ / $13.7$	relation_indexed $84.7$ / $6.9$

Table 2: Best format per (model, benchmark) as “score/spread”. Text2KGBench: F1; GraphQA: exact-match accuracy (pp). Spread

=

max

-

min across formats (pp).

Figure 1: Score vs. input-token cost across the four benchmarks. Per-model Pareto fronts dashed.

Policy	Selector	Generator	Input tok.	Output tok.	Rel. cost	Latency	Acc. (%)
	LLM calls/query		Resources/query				Outcome
Global fixed-best	$0$	$1$	$4{,}667$	$296$	$1.00\times$	$5.3$ s	$66.67$
Task-wise router	$0$	$1$	$5{,}124$	$305$	$1.08\times$	$5.6$ s	$64.76$
MV-5 (parallel)	$0$	$5$	$27{,}231$	$1{,}573$	$5.69\times$	$9.1$ s	$71.43$
Adaptive selector	$5$	$1$	$17{,}696$	$1{,}034$	$3.71\times$	$9.4$ s	$\mathbf{76.19}$

Table 3: End-to-end policy comparison on the same 105 held-out GraphQA-Hardened questions. Counts cover the complete pipeline, and API cost is normalized to global fixed-best. The five selector scores and the five majority voting (MV-5) generations are issued in parallel when measuring latency.

Appendix figures & tables14 assets

Supplementary material from the paper’s appendix.

Appendix

task	question template	ref. example	in
GraphQA (11 tasks; $9$ adapted from Fatemi et al., 2024 $+\,2$ added).
node_count	“How many nodes are in the graph?”	$5$	G
edge_count	“How many edges are in the graph?”	$5$	G
node_degree	“What is the degree of node $v$ ?”	$\deg(3)\!=\!3$	G
edge_existence	“Is there an edge directly between $a$ and $b$ ? Yes/No.”	$\{0,4\}\!\to$ No	G
connectivity	“Is there a path from $a$ to $b$ ? Yes/No.”	$0\!\to\!4$ Yes	G

Appendix

Table 4: The

18

task templates (

11

GraphQA +

7

Hardened). “in”: G = GraphQA, H = Hardened, T = Topology. Topology keeps only the

4

Hardened operators with a bounded integer / 2-dp answer; reference examples use the

5

-node graph of App. H .

generator	parameters	degree distribution	edge count at $n\!=\!50$
ER $G(n,p)$	$p\!=\!\min(0.5,\,2.5\log_{10}n/n)\!\approx\!0.085$	binomial, sharp peak	$\sim\!85$
BA	$m\!=\!2$ edges per new node	power-law $P(k)\!\sim\!k^{-3}$	$\approx\!98$
SBM	$2$ communities, $p_{\text{in}}\!=\!0.55$ , $p_{\text{out}}\!=\!0.03$	bimodal	$\sim\!360$
star	$1$ hub, $n\!-\!1$ leaves	$\{1,\,n\!-\!1\}$	$49$
complete	all-to-all	$\{n\!-\!1\}$	$1{,}225$
path	$0\!-\!1\!-\!\ldots\!-\!(n\!-\!1)$	$\{1,\,2\}$	$49$

Appendix

Table 5: GraphQA-Topology generators at

|V|\!=\!50

. Density-matched comparisons across all six are not meaningful; the load-bearing contrast (§ 4 ) is BA vs. ER at

\sim\!15\%

density mismatch.

model	adjacency	dot	edge_list	entity_centric	friendship	jsonld	markdown_table	mermaid	nl_summary	relation_indexed	shacl_lite	structured	text2kgbench	toon	turtle
gpt-5.4-high-reasoning	100.0	100.0	100.0	99.4	99.4	100.0	100.0	100.0	99.4	100.0	100.0	100.0	100.0	99.4	100.0
gpt-5.4	90.9	88.5	92.1	92.7	90.3	92.7	90.3	90.3	92.7	90.3	93.3	91.5	92.7	92.7	89.1
gpt-5.4-mini	75.1	72.1	73.3	77.6	71.5	79.4	75.1	73.9	76.4	75.8	76.4	75.1	72.7	71.5	70.9
o3	98.2	97.0	95.8	98.2	95.8	98.2	97.0	97.6	98.2	97.6	97.6	97.0	97.6	95.8	97.6
claude-sonnet-4-6-thinking	93.9	95.2	95.8	97.0	95.8	97.0	93.9	95.8	96.4	96.4	93.9	96.4	97.0	93.3	93.3
claude-sonnet-4-6	93.9	94.5	92.1	92.7	92.7	94.5	93.9	92.7	94.5	93.3	93.3	93.3	93.3	93.3	93.9

Appendix

Table 6: GraphQA per-format accuracy (%; ER,

|V|\!\leq\!50

). Bold: per-model maximum.

n\!=\!165

questions per (model, format).

model	adjacency	dot	edge_list	entity_centric	friendship	jsonld	markdown_table	mermaid	nl_summary	relation_indexed	shacl_lite	structured	text2kgbench	toon	turtle
gpt-5.4	61.1	55.8	56.8	63.2	60.0	62.1	52.6	57.9	64.2	52.6	63.2	51.6	52.6	51.6	60.0
gpt-5.4-mini	37.9	35.8	32.6	35.8	39.0	41.0	34.7	34.7	40.0	33.7	40.0	34.7	33.7	33.7	34.7
o3	85.3	81.0	79.0	86.3	75.8	87.4	82.1	84.2	87.4	80.0	85.3	82.1	77.9	81.0	82.1
claude-sonnet-4-6-thinking	83.2	79.0	79.0	83.2	82.1	82.1	82.1	83.2	82.1	82.1	83.2	81.0	83.2	82.1	82.1
claude-sonnet-4-6	79.0	81.0	80.0	87.4	80.0	84.2	75.8	81.0	76.8	79.0	83.2	75.8	76.8	73.7	82.1
claude-haiku-4-5	72.6	53.7	52.6	71.6	54.7	67.4	50.5	48.4	68.4	44.2	66.3	61.1	54.7	59.0	46.3

Appendix

Table 7: GraphQA-Hardened per-format accuracy (%;

|V|\!\in\!\{35,50,75\}

). Bold: per-model maximum.

n\!=\!95

questions per (model, format). gpt-5.4-high-reasoning excluded from this full-format comparison.

model	adjacency	dot	edge_list	entity_centric	friendship	jsonld	markdown_table	mermaid	nl_summary	relation_indexed	shacl_lite	structured	text2kgbench	toon	turtle
gpt-5.4	84.7	79.2	75.0	81.9	77.8	90.3	77.8	79.2	84.7	76.4	90.3	83.3	81.9	77.8	75.0
gpt-5.4-mini	48.6	50.0	52.8	48.6	50.0	58.3	54.2	54.2	47.2	52.8	41.7	55.6	52.8	48.6	50.0
o3	90.3	90.3	80.6	86.1	80.6	88.9	86.1	90.3	84.7	87.5	87.5	90.3	87.5	88.9	84.7
claude-sonnet-4-6-thinking	93.1	90.3	93.1	91.7	93.1	95.8	93.1	91.7	94.4	91.7	93.1	91.7	93.1	91.7	94.4
claude-sonnet-4-6	80.6	83.3	80.6	80.6	77.8	81.9	80.6	80.6	83.3	84.7	81.9	81.9	83.3	81.9	81.9
claude-haiku-4-5	77.8	66.7	66.7	79.2	72.2	75.0	73.6	68.1	80.6	65.3	79.2	68.1	73.6	65.3	63.9

Appendix

Table 8: GraphQA-Topology per-format accuracy (%;

|V|\!=\!50

, six generators). Bold: per-model maximum.

n\!=\!72

questions per (model, format). gpt-5.4-high-reasoning excluded from this full-format comparison.

model	best	acc.	second	acc.	worst	acc.	spread
gpt-5.4	jsonld	41.8	turtle	40.0	adj.	13.6	28.2
gpt-5.4-mini	jsonld	30.9	turtle	29.1	nl_sum.	6.4	24.5

Appendix

Table 9: Tolerance accuracy (%) on 110 questions over retrieved Wikidata subgraphs. Spread is the within-model maximum minus minimum across all 15 formats.

model (year)	best fmt	F1	$\Delta$ vs. Vicuna 2023
Vicuna-13B, 2023	text2kgbench	$30.0$	—
Alpaca-LoRA-13B, 2023	text2kgbench	$25.0$	$-5.0$
gpt-5.4-high-reasoning	turtle	$54.7$	$+24.7$
gpt-5.4	mermaid	$52.7$	$+22.7$
gpt-5.4-mini	shacl_lite	$50.6$	$+20.6$
o3	shacl_lite	$\mathbf{54.9}$	$+24.9$

Appendix

Table 10: Fuzzy F1 on dbpedia_webnlg at threshold

0.60

(Hopcroft–Karp). The

2023

baselines ( Mihindukulasooriya et al., 2023 , Tab. 2) use a greedy

1

1

matcher; the

\Delta

column is context, not an encoding-choice effect.

model	edge_list	entity_centric	jsonld	markdown_table	mermaid	nl_summary	relation_indexed	shacl_lite	structured	text2kgbench	toon	turtle
gpt-5.4-high-reasoning	52.8	53.4	54.5	53.2	54.5	53.6	53.1	53.8	54.0	54.2	53.1	54.7
gpt-5.4	50.6	51.8	49.9	49.4	52.7	50.3	50.0	51.9	49.8	50.2	49.9	50.3
gpt-5.4-mini	48.7	50.2	48.1	49.3	49.7	49.6	49.0	50.6	49.2	49.9	49.8	48.0
o3	53.6	54.0	53.6	53.4	52.8	53.1	53.7	54.9	53.3	53.8	53.5	54.0
claude-sonnet-4-6-thinking	50.1	50.2	52.9	50.9	50.7	50.2	51.1	51.4	50.4	50.9	51.0	51.3
claude-sonnet-4-6	50.3	51.2	52.2	50.3	50.7	50.0	50.6	52.0	50.6	51.3	50.6	50.8

Appendix

Table 11: Text2KGBench per-format Fuzzy F1 (%) at threshold

0.60

(Hopcroft–Karp). Bold: per-model maximum.

n\!=\!2{,}014

questions per (model, format).

Statistic	min	median	mean	max
Concepts	$8$	$14$	$14$	$20$
Relations	$18$	$38$	$36$	$68$
Avg. rendered tokens	$327$	$622$	$602$	$1{,}188$

Appendix

Table 12: Text2KGBench ontology size and rendering statistics across the 19 dbpedia_webnlg ontologies. Tokens averaged over all representation formats per ontology.

model	regime	fixed	ceiling	$\Delta$ pp	sig
gpt-5.4	GraphQA	$93.3$	$\mathbf{95.8}$	$\mathbf{+2.5}$	**
gpt-5.4	Hardened	$64.2$	$\mathbf{80.0}$	$\mathbf{+15.8}$	**
gpt-5.4	Topology	$90.3$	$\mathbf{97.2}$	$\mathbf{+6.9}$	**
gpt-5.4-mini	GraphQA	$79.4$	$\mathbf{87.9}$	$\mathbf{+8.5}$	**
gpt-5.4-mini	Hardened	$41.0$	$\mathbf{70.5}$	$\mathbf{+29.5}$	**
gpt-5.4-mini	Topology	$58.3$	$\mathbf{80.6}$	$\mathbf{+22.3}$	**

Appendix

Table 13: Oracle headroom per model (paired-BCa

95\%

CI;

n_{\mathrm{boot}}\!=\!2{,}000

). Bold

\mathbf{**}

: lower CI bound

>\!0

per-format mean accuracy ( $n\!=\!105$ )	%
entity_centric	$68.57$
nl_summary	$66.67$
jsonld / shacl_lite	$65.71$
adjacency	$62.86$
friendship	$59.05$
dot / mermaid	$58.10$

Appendix

Table 14: Selector headline (

n\!=\!105

queries). Left: calibration-set per-format mean accuracy (the prior the selector uses at test time). Right: selector summary at

b\!=\!5

. Breakdowns in Tab. 15 – 16 .

task	betweenness	local	max_clique	neigh_deg	graph	kcore	kth_shortest
	_top1	_clustering	_size	_ge	_diameter	_size	_path
fixed-best %	$60.0$	$40.0$	$33.3$	$73.3$	$93.3$	$100.0$	$66.7$
selector %	$73.3$	$60.0$	$53.3$	$86.7$	$93.3$	$100.0$	$66.7$
in-cand. ceiling %	$86.7$	$73.3$	$73.3$	$86.7$	$93.3$	$100.0$	$66.7$
$\Delta$ pp (sel. $-$ fxd.)	$\mathbf{+13.3}$	$\mathbf{+20.0}$	$\mathbf{+20.0}$	$\mathbf{+13.3}$	$\phantom{+0}0.0$	$\phantom{+0}0.0$	$\phantom{+0}0.0$
residual ceiling gap pp	$+13.3$	$+13.3$	$+20.0$	$\phantom{+0}0.0$	$\phantom{+0}0.0$	$\phantom{+0}0.0$	$\phantom{+0}0.0$

Appendix

Table 15: Per-task selector vs. fixed-best ( nl_summary ) at

b\!=\!5

;

n\!=\!15

questions per task. In-candidate ceiling: per-question best within the

5

-format slate (upper bound on any slate-restricted selector). Gains concentrate on the four non-saturated tasks; no task regresses.

band $b$	selector acc.	$\Delta$ vs. nl_summary	$95\%$ paired-BCa CI	mid- $p$ McNemar; $b/c$	sig.
$b\!=\!2$ (default)	$75.24\%$	$+8.57$ pp	$[+0.95,+15.24]$	$0.021;\;12/3$	$\mathbf{**}$
$b\!=\!5$ (headline)	$\mathbf{76.19\%}$	$\mathbf{+9.52}$ pp	$[+1.90,+16.19]$	$0.013;\;13/3$	$\mathbf{**}$

Appendix

Table 16: Diversification-band ablation on the same

105

queries. Both bands are paired-BCa significant;

16/105

picks flip between

b\!=\!2

and

b\!=\!5

, the other

89

are decided by the LLM’s argmax irrespective of

b

paper configuration	model identifier	inference control	temperature	original-panel access window
gpt-5.4	openai.gpt-5.4-2026-03-05	default reasoning	0	May 13–15, 2026
gpt-5.4-high	openai.gpt-5.4-2026-03-05	reasoning_effort=HIGH	0	May 13–23, 2026
gpt-5.4-mini	openai.gpt-5.4-mini-2026-03-17	default reasoning	0	May 13–15, 2026
o3	openai.o3-2025-04-16	default reasoning	0	May 13–19, 2026
claude-sonnet-4-6	anthropic.claude-sonnet-4-6	thinking off	0	May 18–25, 2026
claude-sonnet-4-6-thinking	anthropic.claude-sonnet-4-6	extended thinking	1	May 18–25, 2026

Appendix

Table 17: Model identifiers, inference controls, and access windows for the original benchmark panel. gpt-5.4-high is the same dated checkpoint as gpt-5.4 , with HIGH reasoning effort enabled.

LLM Reasoning with Graphs

Large language model reasoning with graphs uses structured relationships to support multi-step inference, evidence retrieval, and planning.

See all 211 papers

Structure Tax: How Structured Output affects LLMs Performance
Oct 8, 2026Vineet Kumar, Kanishka, Bhuvanesh MandoraStructured Output Generation Structured Reasoning in Language Models
PayPal Artificial Intelligence PayPal, Bengaluru India
Position: How can Graphs Help Large Language Models?
May 4, 2026Xiyuan Wang, Yi Hu, Yanbo Wang +2LLM Grounding Knowledge Augmentation for Language Models
Institute for Artificial Intelligence, Peking University, Beijing 100871, China · School of Computer Sciences, Beijing University of Posts and Telecommunications, Beijing 100876, China
GraphDancer: Training LLMs to Explore and Reason over Graphs via Curriculum Reinforcement Learning
Jan 24, 2026Yuyang Bai, Zhuofeng Li, Ping Nie +3LLM Reasoning with Graphs RL for Language Model Reasoning
Texas A&M University · University of Waterloo · Lambda +1

Oct 8, 2026J/K move · Enter open · S save

Structure Tax: How Structured Output affects LLMs Performance

Vineet Kumar, Kanishka, Bhuvanesh Mandora

PayPal Artificial Intelligence PayPal, Bengaluru India

Structured Output Generation Structured Reasoning in Language Models LLM Reliability

Open paper AskPDF arXiv

Deploying large language models in production often requires constraining outputs to structured formats such as JSON or XML, and prior work treats the resulting accuracy loss as an inherent

structure tax'. We re-examine this claim by evaluating a battery of models, datasets and schemas, measuring task accuracy, confidence calibration, and hidden-state geometry. The tax turns out to depend on schema design rather than on structure per se: reasoning-first field ordering matches or exceeds free-form accuracy, while answer-first ordering causes steep drops, particularly in smaller models. Format sensitivity scales inversely with a task's own structural constraints, and schemas that preserve reasoning order also improve calibration with CKA showing greater separability between correct and incorrect representations in middle transformer layers. Our findings indicate that properly designed structured formats can match or exceed free-form performance, reframing the critical question from

whether to structure' to `how to structure' for optimal reasoning preservation.

Abstract

LLM Reasoning with Graphs

Explore similar work

Structure Tax: How Structured Output affects LLMs Performance

Position: How can Graphs Help Large Language Models?

GraphDancer: Training LLMs to Explore and Reason over Graphs via Curriculum Reinforcement Learning