Transformers Can Navigate Mazes With Multi-Step Prediction

Despite their remarkable success in language modeling, transformers trained to predict the next token in a sequence struggle with long-term planning. This limitation is particularly evident in tasks requiring foresight to plan multiple steps ahead such as maze navigation. The standard next _single_ token prediction objective, however, offers no explicit mechanism to predict multiple steps ahead—or revisit the path taken so far. Consequently, in this work we study whether explicitly predicting multiple steps ahead (and backwards) can improve transformers’ maze navigation. We train parameter-matched transformers from scratch, under identical settings, to navigate mazes of varying types and sizes with standard next token prediction and MLM-\(\mathcal{U}\), an objective explicitly predicting multiple steps ahead and backwards. We find that MLM-\(\mathcal{U}\) considerably improves transformers’ ability to navigate mazes compared to standard next token prediction across maze types and complexities. We also find MLM-\(\mathcal{U}\) training is 4\(\times\) more sample efficient and converges 2\(\times\) faster in terms of GPU training hours relative to next token training. Finally, for more complex mazes we find MLM-\(\mathcal{U}\) benefits from scaling to larger transformers. Remarkably, we find transformers trained with MLM-\(\mathcal{U}\) outperform larger transformers trained with next token prediction using additional supervision from A* search traces. We hope these findings underscore the promise of learning objectives to advance transformers’ capacity for long-term planning. The code can be found at https://github.com/facebookresearch/maze_navigation_MLMU