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.

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.

We consider language modelling (LM) as a multi-label structured prediction task by re-framing training from solely predicting a single ground-truth word to ranking a set of words which could continue a given context. To avoid annotating top-k ranks, we generate them using pre-trained LMs: GPT-2, BERT, and Born-Again models. This leads to a rank-based form of knowledge distillation (KD). We also develop a method using N-grams to create a non-probabilistic teacher which generates the ranks without the need of a pre-trained LM. We confirm the hypotheses: that we can treat LMing as a ranking task and that we can do so without the use of a pre-trained LM. We show that rank-based KD generally gives a modest improvement to perplexity (PPL) -- though often with statistical significance -- when compared to Kullback–Leibler-based KD. Surprisingly, given the naivety of the method, the N-grams act as competitive teachers and achieve similar performance as using either BERT or a Born-Again model teachers. Unsurprisingly, GPT-2 always acts as the best teacher. Using it and a Transformer-XL student on Wiki-02, rank-based KD reduces a cross-entropy baseline from 65.27 to 55.94 and against a KL-based KD of 56.70.