Language Models, Graph Searching, and Supervision Adulteration: When More Supervision is Less and How to Make More More
Not on the map. Why?
Abstract (arXiv)
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.
Key facts. Cited by 3 papers in the map (data through 14 Oct 2026). Builds on 162 of its 211 references that are in the map. First posted on arXiv 13 Mar 2025.
Builds on
162 of 211 references.
References · 162
- 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,399
- 2020Language Models are Few-Shot Learnerscited by 32,419
- 2013Efficient Estimation of Word Representations in Vector Spacecited by 4,375
- 2022Large Language Models are Zero-Shot Reasonerscited by 4,374
- 2023Lost in the Middle: How Language Models Use Long Contextscited by 3,455
- 2019XLNet: Generalized Autoregressive Pretraining for Language Understandingcited by 2,811
- 2023Sparks of Artificial General Intelligence: Early experiments with GPT-4cited by 2,592
- 2020Shortcut Learning in Deep Neural Networkscited by 1,969
- 2021Structured Denoising Diffusion Models in Discrete State-Spacescited by 1,719
- 2022Fast Inference from Transformers via Speculative Decodingcited by 1,653
- 2019fairseq: A Fast, Extensible Toolkit for Sequence Modelingcited by 1,488
- 2021Scaling Language Models: Methods, Analysis & Insights from Training Gophercited by 1,202
38 more
- 2022Measuring and Narrowing the Compositionality Gap in Language Modelscited by 1,075
- 2022Language Models as Zero-Shot Planners: Extracting Actionable Knowledge for Embodied Agentscited by 1,035
- 2023Accelerating Large Language Model Decoding with Speculative Samplingcited by 1,006
- 2021Show Your Work: Scratchpads for Intermediate Computation with Language Modelscited by 886
- 2023Reasoning with Language Model is Planning with World Modelcited by 861
- 2024Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Headscited by 843
- 2023Large Language Models Can Be Easily Distracted by Irrelevant Contextcited by 841
- 2019SpanBERT: Improving Pre-training by Representing and Predicting Spanscited by 834
- 2015Scheduled Sampling for Sequence Prediction with Recurrent Neural Networkscited by 803
- 2021Did Aristotle Use a Laptop? A Question Answering Benchmark with Implicit Reasoning Strategiescited by 743
- 2024A Survey on Large Language Models for Code Generationcited by 658
- 2024Parameter-Efficient Fine-Tuning for Large Models: A Comprehensive Surveycited by 656
- 2023Eliciting Latent Predictions from Transformers with the Tuned Lenscited by 623
- 2023Instruction Tuning for Large Language Models: A Surveycited by 623
- 2015Generating Sentences from a Continuous Spacecited by 612
- 2024GSM-Symbolic: Understanding the Limitations of Mathematical Reasoning in Large Language Modelscited by 550
- 2023Are Emergent Abilities of Large Language Models a Mirage?cited by 523
- 2023Faith and Fate: Limits of Transformers on Compositionalitycited by 503
- 2017Non-Autoregressive Neural Machine Translationcited by 463
- 2023The Reversal Curse: LLMs trained on "A is B" fail to learn "B is A"cited by 407
- 2019Are Transformers universal approximators of sequence-to-sequence functions?cited by 406
- 2022PlanBench: An Extensible Benchmark for Evaluating Large Language Models on Planning and Reasoning about Changecited by 382
- 2024Better & Faster Large Language Models via Multi-token Predictioncited by 360
- 2022Selection-Inference: Exploiting Large Language Models for Interpretable Logical Reasoningcited by 334
- 2023The Impact of Positional Encoding on Length Generalization in Transformerscited by 327
- 2023On the Planning Abilities of Large Language Models : A Critical Investigationcited by 312
- 2023Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspectivecited by 294
- 2023Physics of Language Models: Part 3.1, Knowledge Storage and Extractioncited by 270
- 2023Think before you speak: Training Language Models With Pause Tokenscited by 264
- 2024To CoT or not to CoT? Chain-of-thought helps mainly on math and symbolic reasoningcited by 263
- 2024Chain of Thought Empowers Transformers to Solve Inherently Serial Problemscited by 260
- 2022Reasoning with Language Model Prompting: A Surveycited by 252
- 2023Can Language Models Solve Graph Problems in Natural Language?cited by 252
- 2023Large Language Models as Commonsense Knowledge for Large-Scale Task Planningcited by 231
- 2020ProphetNet: Predicting Future N-gram for Sequence-to-Sequence Pre-trainingcited by 222
- 2022Towards Understanding Chain-of-Thought Prompting: An Empirical Study of What Matterscited by 222
- 2022Neural Networks and the Chomsky Hierarchycited by 217
- 2024Repeat After Me: Transformers are Better than State Space Models at Copyingcited by 216
50 most cited of 162 All 162 (JSON)
Built on by
Citing papers per year: 2025: 2; 2026: 1.
3 papers.