  Recent works in AI planning have proposed to combine LLMs with iterative
tree-search algorithms like A* and MCTS, where LLMs are typically used to
calculate the heuristic, guiding the planner towards the goal. However,
combining these techniques is not trivial : LM-based heuristics are quite weak,
incurring a high computational cost without a significant performance
improvement. Existing methods to learn these heuristics do not consider the
requirements of the planner, and typically need a lot of compute. Thus, in this
work, we propose a distribution to downsample training data by identifying
relevant data points to learn a performant heuristic, while constraining
computational costs. To arrive at this model, we disentangle the requirements
of the planner, in our case A* search, from that of the language model to
generalise on this task. Surprisingly, we find an overlap between their
requirements; A* requires more accurate predictions on nodes near the goal, and
LMs need the same set of nodes for effective generalisation. With these
insights, we can quantify the contribution of each node towards accelerating A*
search, and subsequently derive a training distribution for learning LM-based
heuristics. Following a recent work, we conduct our experiments on two
classical planning domains, maze navigation and sokoban, with two test splits
per domain, and two conventional loss functions. We reduce the number of
iterations required to find the solutions by upto 13x, with a wall-clock
speed-up of upto 5x.
