Tree Search With Predictions
For algorithm designers, it provides a theoretically grounded and practically effective method to incorporate predictions into tree search, though limited to path-like trees.
The paper extends the learning-augmented search paradigm from sorted arrays to trees, proving that while logarithmic query bounds in prediction error are impossible for general trees, they can be achieved on trees with low pathwidth, achieving O(k log η) queries where k is pathwidth. Experiments show practical improvements over non-prediction baselines.
``Algorithms with predictions'', or ``learning-augmented algorithms'', has proved to be an extremely useful paradigm for combining machine learning with traditional algorithms. One of the textbook settings for this is searching a sorted array. Without a prediction, classical binary search takes $O(\log n)$ queries, while with a prediction we can use ``doubling binary search'' to find the target key using $O(\log η)$ queries, where $η$ is the error of the prediction measured as the absolute value of the difference between the true location and the predicted location. Since an array is just a path graph, in this paper we ask whether similar bounds can be achieved for search on even slightly more general graphs: trees. We show first that the high-level answer is ``no'': there is no search algorithm that uses $O(\log η)$ queries, where $η$ is now the graph distance between the predicted location and the true location. However, as our main result, we show that such bounds can be achieved on trees which are ``path-like'' in that they have low \emph{pathwidth}. In particular, we prove that there is a search algorithm which uses at most $O(k \log η)$ queries, where $k$ is the pathwidth of the tree. We also prove a lower bound showing that our algorithm has existentially optimal query complexity. Finally, we show experimentally, on real-life inputs, that our algorithm has query complexity which is notably better than the simple non-prediction-based algorithm.