Improving Reachability on Reasoning Puzzles

Recent work has observed the accuracy collapse of large language and reasoning models on moderately large puzzles. Apriori, it is unclear if this failure is due to the inability to find an algorithm or the inability to execute a given algorithm faithfully or simply due to the large number of execution steps. Many puzzles such as Tower of Hanoi are essentially graph reachability tasks, whose graph size increases exponentially. However, symmetry and structure of these graphs allow simple low-complexity algorithms to generate the solution, compared to general-purpose algorithms for reachability that require more compositions, recursion, memory. We theoretically show that faithful execution of certain low-complexity algorithms for reachability are easier to express for small transformer models, compared to general-purpose algorithms for reachability. We empirically observe that explicitly providing such algorithmic hints to language and reasoning models leads to substantially improved performance and pushes the frontier of their accuracy collapse.