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.
| Subjects: | Machine Learning (cs.LG) |
| Cite as: | arXiv:2603.06635 [cs.LG] |
| (or arXiv:2603.06635v2 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2603.06635 arXiv-issued DOI via DataCite |
From: Michal Podstawski [view email]
[v1]
Tue, 24 Feb 2026 13:46:35 UTC (37 KB)
[v2]
Tue, 28 Apr 2026 19:02:35 UTC (54 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。