Graph Property Inference in Small Language Models: Effects of Representation and Reasoning Strategy

Michal Podstawski

cs.LGFeb 24, 2026

Graph Property Inference in Small Language Models: Effects of Representation and Reasoning Strategy

Authors: Michal Podstawski

Organizations: NASK National Research Institute, Warsaw, Poland

Abstract

Recent progress in language modeling has expanded the range of tasks that can be approached through natural language interfaces, including problems that require structured reasoning. However, it remains unclear how effectively limited-capacity language models can infer formal properties of relational structures when those structures are presented in textual form. We conduct a systematic study of graph-theoretic property inference in small instruction-tuned language models, isolating the roles of input representation and reasoning strategy. Across a diverse set of local and global graph metrics evaluated on three models, we find that small language models fail to achieve reliable graph property estimation: normalized errors consistently exceed the intrinsic dispersion of target properties, and rank correlations remain weak across all configurations. However, the failure is structured rather than uniform. Adjacency-list encodings consistently reduce error and improve ordinal consistency relative to edge-lists, and multi-branch reasoning yields measurable aggregate gains across configurations. These results show that without task-specific fine-tuning or architectural adaptation, graph property inference in pretrained small language models remains fundamentally unreliable, but that representational organization and inference design produce consistent differences. The findings characterize the conditions under which structured inference degrades and identify which design choices yield improvements even under constrained model capacity.

Figures & tables

		NRMSE range $\downarrow$			NRMSE std $\downarrow$			Spearman $\rho$ $\uparrow$
Model	Rep.	Baseline	CoT	GoT	Baseline	CoT	GoT	Baseline	CoT	GoT
Llama-3.2-3B	Edge	0.441	0.419	0.383	1.822	1.805	1.589	0.145	0.202	0.212
Llama-3.2-3B	Adj	0.427	0.418	0.397	1.768	1.738	1.634	0.259	0.261	0.273
Phi-4-mini	Edge	0.437	0.412	0.387	2.237	1.943	1.821	0.158	0.174	0.187
Phi-4-mini	Adj	0.411	0.402	0.382	2.134	2.090	1.720	0.164	0.185	0.197
Qwen2.5-3B	Edge	0.283	0.279	0.276	1.436	1.391	1.302	0.246	0.262	0.266

Table 1: Macro-averaged performance. Lower is better for NRMSE metrics, higher is better for Spearman

\rho

	$\Delta$ NRMSE range $\uparrow$			$\Delta$ NRMSE std $\uparrow$			$\Delta$ Spearman $\rho$ $\uparrow$
Model	Baseline	CoT	GoT	Baseline	CoT	GoT	Baseline	CoT	GoT
Llama-3.2-3B	0.014	0.001	$-$ 0.014	0.054	0.067	$-$ 0.045	0.114	0.059	0.061
Phi-4-mini	0.026	0.010	0.005	0.103	$-$ 0.147	0.101	0.006	0.011	0.010
Qwen2.5-3B	0.004	0.005	0.004	0.117	0.168	0.095	0.015	0.015	0.042

Table 2: Adjacency-list advantage over Edge-list (positive values indicate improvement when using Adjacency-list).

		$\Delta$ NRMSE range $\uparrow$		$\Delta$ NRMSE std $\uparrow$		$\Delta$ Spearman $\rho$ $\uparrow$
Model	Rep.	CoT	GoT	CoT	GoT	CoT	GoT
Llama-3.2-3B	Edge	0.022	0.058	0.017	0.233	0.057	0.067
Llama-3.2-3B	Adj	0.009	0.030	0.030	0.134	0.002	0.014
Phi-4-mini	Edge	0.025	0.050	0.294	0.416	0.016	0.029
Phi-4-mini	Adj	0.009	0.029	0.044	0.414	0.021	0.033
Qwen2.5-3B	Edge	0.004	0.007	0.045	0.134	0.016	0.020

Table 3: Inference strategy improvement relative to Baseline. Positive values indicate reduction in NRMSE / increase in Spearman

\rho

Figure 1: Macro-averaged metrics across inference strategies. (a) Range-normalized error, (b) standard-deviation-normalized error with the

\text{NRMSE}_{\text{std}}=1.0

reference line, and (c) Spearman rank correlation. Solid lines denote adjacency-list encoding; dashed lines denote edge-list encoding.

Figure 2: Inference strategy improvement relative to baseline prompting. (a) Reduction in

\text{NRMSE}_{\text{std}}

(positive values indicate lower error). (b) Increase in Spearman

\rho

(positive values indicate improved rank consistency).

Small Language Models

Small language models are compact neural language systems designed to deliver useful text and reasoning capabilities with limited compute, memory, and energy.

See all 269 papers

Apr 20, 2026

Generalization Boundaries of Fine-Tuned Small Language Models for Graph Structural Inference

Small language models fine-tuned for graph property estimation have demonstrated strong in-distribution performance, yet their generalization capabilities beyond training conditions remain poorly understood. In this work, we systematically investigate the boundaries of structural inference in fine-tuned small language models along two generalization axes - graph size and graph family distribution - and assess domain-learning capability on real-world graph benchmarks. Using a controlled experimental setup with three instruction-tuned models in the 3-4B parameter class and two graph serialization formats, we evaluate performance on graphs substantially larger than the training range and across held-out random graph families. Our results show that fine-tuned models maintain strong ordinal consistency across structurally distinct graph families and continue to rank graphs by structural properties on inputs substantially larger than those seen during training, with distinct architecture-specific degradation profiles. These findings delineate where fine-tuned small language models generalize reliably, providing empirical grounding for their use in graph-based reasoning tasks.

Michal Podstawski

NASK National Research Institute Warsaw, Poland

Supervised Fine-Tuning Small Language Models Language Model Generalization

Ask PDF

May 2, 2026

Evaluating LLMs on Large-Scale Graph Property Estimation via Random Walks

With the rapidly improving reasoning abilities of Large Language Models (LLMs), there is also a rising demand to use them in a wide variety of domains. This brings about the need to carefully evaluate the limits of the capabilities of these models with various tests and benchmarks. Graph structures are ubiquitous in real-world data, and are often used to represent and analyze relationship patterns within data. Many benchmarks have already been proposed in the graph literature to test the reasoning ability of LLMs to follow and execute graph algorithms. However, due to the limited context length of LLMs, these benchmarks consist of very small graphs. In real-world data, the size of graphs can be significantly larger, and in many cases, not fully accessible. In this paper, we examine a class of problems that arises with very large graphs having limited accessibility. We propose a large graph benchmark dataset, EstGraph, and introduce four distinct tasks designed to estimate large graph properties. We evaluate the reasoning abilities of LLMs on these tasks using a wide variety of graph datasets. In addition, we provide task-specific prompt constructions based on random walk sampling of large graphs (up to millions of nodes) that effectively convey sufficient information to LLMs within the limits of context length.

Sunil Kumar Maurya, Xin Liu

University of Tokyo Tokyo, Japan · AIST Tokyo, Japan

LLM Evaluation LLM Reasoning with Graphs Graph Reasoning LLM Reasoning

Ask PDF

Sep 10, 2026

GTA: Graph Theory Agent and Benchmark for Algorithmic Graph Reasoning with LLMs

Large Language Models (LLMs) are increasingly asked to reason over structured data such as graphs, yet how reliably they can carry out multi-step graph algorithms in language remains unclear. Existing evaluations tend to use simple tasks on small graphs, to score code generation rather than reasoning over the graph itself, or to fix a single input format. We introduce Graph Theory Bench (GT Bench), a benchmark covering 24 classical graph problems in 44 task-structure settings, with over 100,000 examples across four representations: natural language, structured language, adjacency list, and adjacency matrix. Evaluating eight LLMs on GT Bench shows that accuracy is strongly tied to the input representation, that the best representation shifts with graph density, size, and topology as well as with the model, and that this sensitivity persists, attenuated, in the strongest reasoning models. Building on these observations, we propose the Graph Theory Agent (GTA), which pairs a preference-trained representation selector with plan-and-decompose scaffolding around a frozen executor LLM. GTA lifts Phi-4 from 53.5% to 69.1% on the benchmark's easy split and from 33.0% to 41.5% on its hard split, outperforming eight prompting and agent baselines, and transfers without retraining to GraCoRe and NLGraph. Code for benchmark generation and evaluation: https://github.com/xzx34/GTA. The project homepage is available at https://xzx34.github.io/gta/.

Zixiang Xu, Yanbo Wang, Chenxi Wang +6

University of Southern California · University of California, Los Angeles · Mohamed bin Zayed University of Artificial Intelligence +2

LLM Reasoning with Graphs LLM Agents Graph Reasoning Algorithmic Reasoning

Ask PDF

Abstract

Small Language Models

Explore similar work

Generalization Boundaries of Fine-Tuned Small Language Models for Graph Structural Inference

Evaluating LLMs on Large-Scale Graph Property Estimation via Random Walks

GTA: Graph Theory Agent and Benchmark for Algorithmic Graph Reasoning with LLMs