Language Models, Graph Searching, and Supervision Adulteration: When More Supervision is Less and How to Make More More

2025/03/13 by Arvid Frydenlund, Frydenlund, Arvid · 2 citations
Computer Science · #Advanced Graph Neural Networks #Artificial Intelligence (cs.AI) #Computation and Language (cs.CL) #FOS: Computer and information sciences #I.2.7 #I.2.8 #I.5.0 #Machine Learning (cs.LG) #Multimodal Machine Learning Applications #Topic Modeling

paper · pdf · doi:10.48550/arxiv.2503.10542

openalex publication_date 2025/03/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This work concerns the path-star task, a minimal example of searching over a graph. The graph, G, is star-shaped with D arms radiating from a start node, s. A language model (LM) is given G, s, and a target node t, which ends one of the arms and is tasked with generating the arm containing t. The minimal nature of this task means only a single choice needs to be made: which of the D arms contains t? Decoder-only LMs fail to solve this elementary task above 1/D chance due to a learned shortcut that absorbs training supervision. We show how this pathology is caused by excess supervision and we present a series of solutions demonstrating that the task is solvable via decoder-only LMs. We find that the task's minimal nature causes its difficulty, as it prevents task decomposition. Our solutions provide insight into the pathology and its implications for LMs trained via next-token prediction.

Cited by

• Beyond Multi-Token Prediction: Pretraining LLMs with Future Summaries
• Insertion Language Models: Sequence Generation with Arbitrary-Position Insertions

Related

• The Mystery of the Pathological Path-star Task for Language Models
• Less is More: Learning Graph Tasks with Just LLMs
• Graph Optimization Foundation Model: Tokenizing Graph via A Language-Model Paradigm
• Incidental Supervision: Moving beyond Supervised Learning
• Graph-oriented Instruction Tuning of Large Language Models for Generic Graph Mining