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

• URL: http://arxiv.org/abs/2603.06635v1
• Date: Tue, 24 Feb 2026 13:46:35 GMT
• Title: Graph Property Inference in Small Language Models: Effects of Representation and Inference Strategy
• Abstract summary: It remains unclear how effectively limited-capacity language models can infer formal properties of relational structures when those structures are presented in textual form.<n>We conduct a systematic study of graph-theoretic property inference in small instruction-tuned language models.<n>We find that structural performance is highly sensitive to how relational information is organized.
• Score: 0.48302896549293584
• License: http://creativecommons.org/licenses/by/4.0/
• 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. Understanding the conditions under which structured reasoning succeeds or fails is essential for applying small models in graph-based domains. 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, we find that structural performance is highly sensitive to how relational information is organized. Representations that preserve neighborhood structure consistently improve estimation stability and ordinal consistency, while multi-branch reasoning yields the most reliable aggregate gains across configurations. These results show that graph property inference in small language models depends critically on representational organization and inference design. Structural competence is therefore shaped not only by model scale, but by how relational information is encoded and how predictions are elicited. The findings identify practical levers for improving structured inference under constrained model capacity.

Related papers

• Emergent Structured Representations Support Flexible In-Context Inference in Large Language Models [77.98801218316505]
  Large language models (LLMs) exhibit emergent behaviors suggestive of human-like reasoning.<n>We investigate the internal processing of LLMs during in-context concept inference.
  arXiv  Detail & Related papers  (2026-02-08T03:14:39Z)
• Schoenfeld's Anatomy of Mathematical Reasoning by Language Models [56.656180566692946]
  We adopt Schoenfeld's Episode Theory as an inductive, intermediate-scale lens and introduce ThinkARM (Anatomy of Reasoning in Models)<n>ThinkARM explicitly abstracts reasoning traces into functional reasoning steps such as Analysis, Explore, Implement, verify, etc.<n>We show that episode-level representations make reasoning steps explicit, enabling systematic analysis of how reasoning is structured, stabilized, and altered in modern language models.
  arXiv  Detail & Related papers  (2025-12-23T02:44:25Z)
• Structure-Aware Decoding Mechanisms for Complex Entity Extraction with Large-Scale Language Models [8.15127799301814]
  This paper proposes a structure-aware decoding method based on large language models.<n>It addresses the difficulty of maintaining both semantic integrity and structural consistency in nested and overlapping entity extraction tasks.<n> Experiments conducted on the ACE 2005 dataset demonstrate significant improvements in Accuracy, Precision, Recall, and F1-Score.
  arXiv  Detail & Related papers  (2025-12-16T00:40:06Z)
• Sequences of Logits Reveal the Low Rank Structure of Language Models [22.148282143726835]
  We introduce an approach to study the low-dimensional structure of language models at a model-agnostic level.<n>We first empirically demonstrate that a wide range of modern language models exhibit low-rank structure.<n>We then show that this low-rank structure can be leveraged for generation.
  arXiv  Detail & Related papers  (2025-10-28T20:55:58Z)
• Knowledge Graph-Infused Fine-Tuning for Structured Reasoning in Large Language Models [41.59092188743925]
  It proposes a fine-tuning algorithm framework based on knowledge graph injection.<n>It builds on pretrained language models and introduces structured graph information for auxiliary learning.<n>It demonstrates better semantic consistency and contextual logic modeling in scenarios involving structural reasoning and entity extraction.
  arXiv  Detail & Related papers  (2025-08-20T04:52:12Z)
• A Markov Categorical Framework for Language Modeling [9.910562011343009]
  Autoregressive language models achieve remarkable performance, yet a unified theory explaining their internal mechanisms, how training shapes their representations, and enables complex behaviors, remains elusive.<n>We introduce a new analytical framework that models the single-step generation process as a composition of information-processing stages using the language of Markov categories.<n>This work presents a powerful new lens for understanding how information flows through a model and how the training objective shapes its internal geometry.
  arXiv  Detail & Related papers  (2025-07-25T13:14:03Z)
• Information Structure in Mappings: An Approach to Learning, Representation, and Generalisation [3.8073142980733]
  This thesis introduces quantitative methods for identifying systematic structure in a mapping between spaces.<n>I identify structural primitives present in a mapping, along with information theoretics of each.<n>I also introduce a novel, performant, approach to estimating the entropy of vector space, that allows this analysis to be applied to models ranging in size from 1 million to 12 billion parameters.
  arXiv  Detail & Related papers  (2025-05-29T19:27:50Z)
• Scaling Laws and Representation Learning in Simple Hierarchical Languages: Transformers vs. Convolutional Architectures [49.19753720526998]
  We derive theoretical scaling laws for neural network performance on synthetic datasets.<n>We validate that convolutional networks, whose structure aligns with that of the generative process through locality and weight sharing, enjoy a faster scaling of performance.<n>This finding clarifies the architectural biases underlying neural scaling laws and highlights how representation learning is shaped by the interaction between model architecture and the statistical properties of data.
  arXiv  Detail & Related papers  (2025-05-11T17:44:14Z)
• Learning to Model Graph Structural Information on MLPs via Graph Structure Self-Contrasting [50.181824673039436]
  We propose a Graph Structure Self-Contrasting (GSSC) framework that learns graph structural information without message passing. The proposed framework is based purely on Multi-Layer Perceptrons (MLPs), where the structural information is only implicitly incorporated as prior knowledge. It first applies structural sparsification to remove potentially uninformative or noisy edges in the neighborhood, and then performs structural self-contrasting in the sparsified neighborhood to learn robust node representations.
  arXiv  Detail & Related papers  (2024-09-09T12:56:02Z)
• Physics of Language Models: Part 1, Learning Hierarchical Language Structures [51.68385617116854]
  Transformer-based language models are effective but complex, and understanding their inner workings and reasoning mechanisms is a significant challenge.<n>We introduce a family of synthetic CFGs that produce hierarchical rules, capable of generating lengthy sentences.<n>We demonstrate that generative models like GPT can accurately learn and reason over CFG-defined hierarchies and generate sentences based on it.
  arXiv  Detail & Related papers  (2023-05-23T04:28:16Z)
• Autoregressive Structured Prediction with Language Models [73.11519625765301]
  We describe an approach to model structures as sequences of actions in an autoregressive manner with PLMs. Our approach achieves the new state-of-the-art on all the structured prediction tasks we looked at.
  arXiv  Detail & Related papers  (2022-10-26T13:27:26Z)
• TAGPRIME: A Unified Framework for Relational Structure Extraction [71.88926365652034]
  TAGPRIME is a sequence tagging model that appends priming words about the information of the given condition to the input text. With the self-attention mechanism in pre-trained language models, the priming words make the output contextualized representations contain more information about the given condition. Extensive experiments and analyses on three different tasks that cover ten datasets across five different languages demonstrate the generality and effectiveness of TAGPRIME.
  arXiv  Detail & Related papers  (2022-05-25T08:57:46Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.