mlsanityData to 14 Oct 2026

The Mystery of the Pathological Path-star Task for Language Models

arXiv 2410.13779 ↗First posted 17 Oct 2024cs.CL cs.LGcited by 8

Not on the map. Why?

Abstract (arXiv)

The recently introduced path-star task is a minimal task designed to exemplify limitations to the abilities of language models (Bachmann and Nagarajan, 2024). It involves a path-star graph where multiple arms radiate from a single starting node and each node is unique. Given the start node and a specified target node that ends an arm, the task is to generate the arm containing that target node. This is straightforward for a human but surprisingly difficult for language models, which did not outperform the random baseline. The authors hypothesized this is due to a deficiency in teacher-forcing and the next-token prediction paradigm. We demonstrate the task is learnable using teacher-forcing in alternative settings and that the issue is partially due to representation. We introduce a regularization method using structured samples of the same graph but with differing target nodes, improving results across a variety of model types. We provide RASP proofs showing the task is theoretically solvable. Finally, we find settings where an encoder-only model can consistently solve the task.

Key facts. Cited by 8 papers in the map (data through 14 Oct 2026). Builds on 33 of its 43 references that are in the map. First posted on arXiv 17 Oct 2024.

Builds on

33 of 43 references.

References · 33

  1. 2017Attention Is All You Needcited by 60,361
  2. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,399
  3. 2020Language Models are Few-Shot Learnerscited by 32,419
  4. 2023Mamba: Linear-Time Sequence Modeling with Selective State Spacescited by 4,718
  5. 2019XLNet: Generalized Autoregressive Pretraining for Language Understandingcited by 2,811
  6. 2023Sparks of Artificial General Intelligence: Early experiments with GPT-4cited by 2,592
  7. 2019fairseq: A Fast, Extensible Toolkit for Sequence Modelingcited by 1,488
  8. 2015Scheduled Sampling for Sequence Prediction with Recurrent Neural Networkscited by 803
  9. 2015Sequence Level Training with Recurrent Neural Networkscited by 576
  10. 2017Non-Autoregressive Neural Machine Translationcited by 463
  11. 2023The Reversal Curse: LLMs trained on "A is B" fail to learn "B is A"cited by 407
  12. 2023The Impact of Positional Encoding on Length Generalization in Transformerscited by 327
21 more
  1. 2023On the Planning Abilities of Large Language Models : A Critical Investigationcited by 312
  2. 2023Think before you speak: Training Language Models With Pause Tokenscited by 264
  3. 2019Transformer Dissection: A Unified Understanding of Transformer's Attention via the Lens of Kernelcited by 213
  4. 2023What Algorithms can Transformers Learn? A Study in Length Generalizationcited by 199
  5. 2018Deterministic Non-Autoregressive Neural Sequence Modeling by Iterative Refinementcited by 195
  6. 2021Thinking Like Transformerscited by 184
  7. 2024The pitfalls of next-token predictioncited by 160
  8. 2022Transformer Language Models without Positional Encodings Still Learn Positional Informationcited by 150
  9. 2022Why Exposure Bias Matters: An Imitation Learning Perspective of Error Accumulation in Language Generationcited by 108
  10. 2020Glancing Transformer for Non-Autoregressive Neural Machine Translationcited by 103
  11. 2020Fully Non-autoregressive Neural Machine Translation: Tricks of the Tradecited by 99
  12. 2024Why are Sensitive Functions Hard for Transformers?cited by 74
  13. 2022On the Relation between Sensitivity and Accuracy in In-context Learningcited by 72
  14. 2022Simplicity Bias in Transformers and their Ability to Learn Sparse Boolean Functionscited by 70
  15. 2023PaSS: Parallel Speculative Samplingcited by 49
  16. 2024Reverse Training to Nurse the Reversal Cursecited by 49
  17. 2018Semi-Autoregressive Neural Machine Translationcited by 48
  18. 2022Sub-Task Decomposition Enables Learning in Sequence to Sequence Taskscited by 41
  19. 2020Probabilistically Masked Language Model Capable of Autoregressive Generation in Arbitrary Word Ordercited by 28
  20. 2021Sensitivity as a Complexity Measure for Sequence Classification Taskscited by 28
  21. 2023Zero-shot Approach to Overcome Perturbation Sensitivity of Promptscited by 11

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 1; 2025: 6; 2026: 1.

8 papers.

  1. 2025Roll the dice & look before you leap: Going beyond the creative limits of next-token predictioncited by 29
  2. 2025Multi-Token Prediction Needs Registerscited by 16
  3. 2024The Belief State Transformercited by 12
  4. 2025Insertion Language Models: Sequence Generation with Arbitrary-Position Insertionscited by 11
  5. 2025Autoregressive Language Models are Secretly Energy-Based Models: Insights into the Lookahead Capabilities of Next-Token Predictioncited by 8
  6. 2025Looking beyond the next tokencited by 5
  7. 2026Discrete Diffusion Models Exploit Asymmetry to Solve Lookahead Planning Taskscited by 4
  8. 2025Language Models, Graph Searching, and Supervision Adulteration: When More Supervision is Less and How to Make More Morecited by 3