Improving Small Language Model Reasoning With A* Search

Test-Time Scaling via A* Search

The method improves reasoning in resource-constrained models by treating inference as a tree search problem. Instead of relying on external reward models or distillation from larger teacher models, the system uses the language model's own self-critique to generate a heuristic value for each node in the search tree. By calculating a cost function based on these self-critique scores, the algorithm effectively prunes low-confidence or hallucinated branches, allowing the model to prioritize paths that lead to correct solutions.

Implementation and Efficiency

To apply this technique, the model generates a root node and iteratively expands branches using a prompt that includes the current reasoning step and a request for a self-critique score on a scale of 0 to 100. The search algorithm traverses the tree by selecting the node with the lowest cost, as defined by the A* heuristic. Experiments on the GSM8K and MATH 500 datasets using a 34B parameter Qwen model demonstrate that this approach provides a 3 to 4 percentage point increase in accuracy compared to other test-time scaling methods when normalized for token count and runtime. This confirms that the gains are derived from improved search efficiency rather than simply increasing the compute budget.