Research map / Learning theory and algorithms / Prediction and decision losses

On the Power of Learning-Augmented Search Trees

ICML 2025 · Learning theory and algorithms › Prediction and decision losses · approach: Tree ensemble optimization

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows that Treaps with composite priorities -floor(log log(1/w_x)) + U(0,1) give learning-augmented BSTs and B-Trees that achieve static optimality for arbitrary distributions, extend to working-set bounds, and are robust to prediction error.

Problem

Learning-augmented binary search trees and B-Trees that are statically optimal for arbitrary access distributions, not only Zipfian, and that remain robust to prediction errors and support dynamic (working-set) behavior.

Approach

Assign each item a composite Treap priority combining a tier -floor(log log(1/w_x)) (from frequency-based priorities) with uniform random offset U(0,1) (from randomized Treaps); this bounds expected depth by O(log(1/w_x)) for any weights, yielding static optimality, and extends to B-Treaps and a time-varying working-set priority.

Key results

• Expected depth of each item x is O(log(1/w_x)), giving total access cost O(sum_x f_x log(m/f_x)) matching static optimality up to constants.
• A priority of -floor(log log(1/p_x))-style tiers with a counterexample shows the Lin-Luo-Woodruff priority p_x can have expected access cost Omega(n), while the composite priority achieves O(log n).
• Experiments on synthetic Zipfian, adversarial, and uniform distributions (n=1000) show the proposed Treaps outperform other structures except learn-llw on Zipfian, which assumes that distribution.

Measured effects reported in the paper

Surprising findings

• Priority set exactly to access frequency can yield linear expected depth (Omega(n)) even though it is optimal for Zipfian distributions.
• Priority -floor(log2 1/p_x) + U(0,1) can have expected access time Omega(log^2 n) on some distributions, so the double-log tier is needed.

Limitations

• Working-set priority requires knowing future accesses (the working-set size uses next access), so it is not directly online.
• Experiments are limited to synthetic distributions with n up to 5000 and m up to 20000.
• Constant factors and high-probability guarantees depend on B = O(n^{1/2-delta}) conditions.

Experimental setup

Metrics: total number of comparisons (access cost)

Baselines: learn-llw learn-skiplist red-black tree AVL tree splay tree B-tree of order 3 random treap

Builds on: Treap B-Treap Lin-Luo-Woodruff learning-augmented BST

Closest papers by meaning

• Learning-Augmented Search Data Structures (ICLR 2025 · similarity 0.91)
• Scenario-Based Robust Optimization of Tree Structures (AAAI 2025 · similarity 0.86)
• Improving Decision Trees through the Lens of Parameterized Local Search (NeurIPS 2025 · similarity 0.85)
• Branches: Efficiently Seeking Optimal Sparse Decision Trees via AO* (ICML 2025 · similarity 0.85)
• Binary Search with Distributional Predictions (NeurIPS 2024 · similarity 0.84)
• Discovering Data Structures: Nearest Neighbor Search and Beyond (NeurIPS 2025 · similarity 0.84)