A* execution traces take 1B–3B models from near-zero to beating baselines
Supervised fine-tuning on traces from a classical search algorithm, plus RL with A*-informed process rewards. The smallest models benefit most, which is the interesting part.
Work on A* post-training combines supervised fine-tuning on execution traces from the A* search algorithm with reinforcement learning against A*-informed process reward models. Llama-3.2 models in the 1B–3B range go from near-zero accuracy to outperforming baselines.
Near-zero to outperforming is a large move, and the size range is the reason to care. Small models are where deployment economics are decided — on-device, high-volume, latency-bound. A technique that lifts a 1B model into usefulness changes more products than one that improves a frontier model at the margin.
The mechanism is a nice illustration of an old idea returning. A* is a fully understood classical algorithm with an explicit, inspectable search procedure. Using its execution traces as supervision hands the model a worked example of systematic search rather than asking it to induce the strategy from outcomes. The reward model then scores the process, not only the answer.
The limitation is scope, and the paper is clear about it. A* applies where a state space, a successor function and an admissible heuristic can be defined — planning, pathfinding, structured puzzles. Most tasks people want reasoning for have none of those. The result is strong evidence that small models lack procedure rather than capacity; it is not a general reasoning method.
Read alongside the RL-efficiency work, the theme is that supervision quality has been the bottleneck, not scale.
arXiv — Learning to Reason Efficiently with A* Post-Training → · arXiv — Efficient LLM Reasoning via Variational Posterior Guidance with Efficiency Awareness →