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

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.

With the rapid advancement of large language models (LLMs), classic graph learning tasks have greatly benefited from LLMs, including improved encoding of textual features, more efficient construction of graphs from text, and enhanced reasoning over knowledge graphs. In this paper, we ask a complementary question: How can graphs help LLMs? We address this question from three perspectives: 1) graphs provide an up-to-date knowledge source that helps reduce LLM hallucinations, 2) graph-based prompting techniques-such as Chain-of-Thought (CoT), Tree-of-Thought (ToT), and Graph-of-Thought (GoT)-enhance LLM reasoning capabilities, and 3) integrating graphs into LLMs improves their understanding of structured data, expanding their applicability to domains such as e-commerce, code, and relational databases (RDBs). We further outlook some future directions including designing sparse LLM architectures based on graphs and brain-inspired memory systems.

Large language models (LLMs) increasingly rely on external knowledge to improve factuality, yet many knowledge sources on the Web, such as scholarly indexes and product catalogs, are organized as heterogeneous graphs. Reasoning over such graph-structured knowledge poses two key challenges: (1) navigating structured, schema-defined relations requires precise function calls beyond similarity-based retrieval, and (2) answering complex questions often demands multi-hop evidence aggregation through iterative information seeking. We study how LLMs can learn these interaction capabilities and transfer them to unseen domains. We propose GraphDancer, a reinforcement learning (RL) framework that teaches LLMs to navigate graphs by interleaving reasoning and function execution. To improve RL for moderate-sized LLMs, we introduce a graph-aware curriculum that schedules training by the structural difficulty of questions using an easy-to-hard biased sampler. We evaluate GraphDancer on the multi-domain GRBench benchmark, training only on Academic and Biomedical graphs. Testing covers held-out questions from these domains as well as unseen E-commerce, Literature, and Legal graphs. With either Qwen2.5-3B-Instruct or Qwen3-14B as the backbone, GraphDancer outperforms graph-agent baselines using the same backbone across all evaluation domains. These results indicate that the learned graph exploration and reasoning capabilities transfer across domains. On average across unseen domains, GraphDancer with a 14B backbone also outperforms baselines powered by the closed-source models GPT-4.1-mini and GPT-5-nano. Trajectory analyses further show that GraphDancer retrieves answer-bearing evidence more often and achieves higher accuracy when such evidence is found, while substantially reducing invalid-protocol outcomes.