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

arXiv: https://arxiv.org/abs/2410.13779 · HTML: https://mlsanity.com/paper/2410.13779/

## 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 (most cited first, 30 of 33)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Mamba: Linear-Time Sequence Modeling with Selective State Spaces](https://mlsanity.com/paper/2312.00752/) (2023)
- [XLNet: Generalized Autoregressive Pretraining for Language Understanding](https://mlsanity.com/paper/1906.08237/) (2019)
- [Sparks of Artificial General Intelligence: Early experiments with GPT-4](https://mlsanity.com/paper/2303.12712/) (2023)
- [fairseq: A Fast, Extensible Toolkit for Sequence Modeling](https://mlsanity.com/paper/1904.01038/) (2019)
- [Scheduled Sampling for Sequence Prediction with Recurrent Neural Networks](https://mlsanity.com/paper/1506.03099/) (2015)
- [Sequence Level Training with Recurrent Neural Networks](https://mlsanity.com/paper/1511.06732/) (2015)
- [Non-Autoregressive Neural Machine Translation](https://mlsanity.com/paper/1711.02281/) (2017)
- [The Reversal Curse: LLMs trained on "A is B" fail to learn "B is A"](https://mlsanity.com/paper/2309.12288/) (2023)
- [The Impact of Positional Encoding on Length Generalization in Transformers](https://mlsanity.com/paper/2305.19466/) (2023)
- [On the Planning Abilities of Large Language Models : A Critical Investigation](https://mlsanity.com/paper/2305.15771/) (2023)
- [Think before you speak: Training Language Models With Pause Tokens](https://mlsanity.com/paper/2310.02226/) (2023)
- [Transformer Dissection: A Unified Understanding of Transformer's Attention via the Lens of Kernel](https://mlsanity.com/paper/1908.11775/) (2019)
- [What Algorithms can Transformers Learn? A Study in Length Generalization](https://mlsanity.com/paper/2310.16028/) (2023)
- [Deterministic Non-Autoregressive Neural Sequence Modeling by Iterative Refinement](https://mlsanity.com/paper/1802.06901/) (2018)
- [Thinking Like Transformers](https://mlsanity.com/paper/2106.06981/) (2021)
- [The pitfalls of next-token prediction](https://mlsanity.com/paper/2403.06963/) (2024)
- [Transformer Language Models without Positional Encodings Still Learn Positional Information](https://mlsanity.com/paper/2203.16634/) (2022)
- [Why Exposure Bias Matters: An Imitation Learning Perspective of Error Accumulation in Language Generation](https://mlsanity.com/paper/2204.01171/) (2022)
- [Glancing Transformer for Non-Autoregressive Neural Machine Translation](https://mlsanity.com/paper/2008.07905/) (2020)
- [Fully Non-autoregressive Neural Machine Translation: Tricks of the Trade](https://mlsanity.com/paper/2012.15833/) (2020)
- [Why are Sensitive Functions Hard for Transformers?](https://mlsanity.com/paper/2402.09963/) (2024)
- [On the Relation between Sensitivity and Accuracy in In-context Learning](https://mlsanity.com/paper/2209.07661/) (2022)
- [Simplicity Bias in Transformers and their Ability to Learn Sparse Boolean Functions](https://mlsanity.com/paper/2211.12316/) (2022)
- [PaSS: Parallel Speculative Sampling](https://mlsanity.com/paper/2311.13581/) (2023)
- [Reverse Training to Nurse the Reversal Curse](https://mlsanity.com/paper/2403.13799/) (2024)
- [Semi-Autoregressive Neural Machine Translation](https://mlsanity.com/paper/1808.08583/) (2018)
- [Sub-Task Decomposition Enables Learning in Sequence to Sequence Tasks](https://mlsanity.com/paper/2204.02892/) (2022)

## Built on by (most cited first, 8 of 8)

- [Roll the dice & look before you leap: Going beyond the creative limits of next-token prediction](https://mlsanity.com/paper/2504.15266/) (2025)
- [Multi-Token Prediction Needs Registers](https://mlsanity.com/paper/2505.10518/) (2025)
- [The Belief State Transformer](https://mlsanity.com/paper/2410.23506/) (2024)
- [Insertion Language Models: Sequence Generation with Arbitrary-Position Insertions](https://mlsanity.com/paper/2505.05755/) (2025)
- [Autoregressive Language Models are Secretly Energy-Based Models: Insights into the Lookahead Capabilities of Next-Token Prediction](https://mlsanity.com/paper/2512.15605/) (2025)
- [Looking beyond the next token](https://mlsanity.com/paper/2504.11336/) (2025)
- [Discrete Diffusion Models Exploit Asymmetry to Solve Lookahead Planning Tasks](https://mlsanity.com/paper/2602.19980/) (2026)
- [Language Models, Graph Searching, and Supervision Adulteration: When More Supervision is Less and How to Make More More](https://mlsanity.com/paper/2503.10542/) (2025)

## 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.