Research map / Bandits and online learning / Online convex optimization and games

Learning-Augmented Priority Queues

NeurIPS 2024 · Bandits and online learning › Online convex optimization and games · approach: Learning-augmented online algorithms · 2 citations (OpenAlex)

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.

Designs learning-augmented priority queues (skip-list based, with binary-heap variant) that use dirty comparisons, pointer predictions, or rank predictions to beat worst-case O(log n) insertion and extraction bounds, with matching lower bounds via reduction from learning-augmented sorting.

Problem

Standard priority queues cannot support all operations in o(log n) time, and comparison-based costs are high when comparisons are expensive; the paper asks how predictions of comparisons, predecessors, or ranks can reduce insertion and extraction costs.

Approach

Augment skip lists (and binary heaps for insertion) with three prediction types: noisy binary comparison predictions searched with randomized binary search, predecessor pointers used for exponential search from a predicted position, and rank predictions mapped into an auxiliary dynamic van Emde Boas tree to locate a start point. Extract Min becomes O(1) and insertion cost scales with the predictio

Key results

• Randomized binary search with dirty comparisons uses O(log k) dirty and O(log eta) clean comparisons in expectation.
• Skip list with pointer predictions inserts in expected O(log eta-vector) time; with dirty comparisons in O(log n) time using O(log eta) clean comparisons; with rank predictions in O(log log N + log max error) amortized time.
• Lower bounds show these insertion complexities are optimal in the dirty comparison and pointer prediction models, via reduction to sorting lower bounds.

Measured effects reported in the paper

Surprising findings

• Fibonacci heaps perform poorly in practice, even worse than binary heaps in the experiments.

Limitations

• Binary-heap extract-min still needs O(log n) clean comparisons, so heaps are not improved beyond insertion.
• Rank-prediction insertion cost depends on the maximum prediction error over all keys, not just the inserted key's error.
• Runtime with rank predictions is not known to be optimal below O(log log N) additive term.

Experimental setup

Metrics: runtime number of comparisons

Baselines: binary heap Fibonacci heap skip list Double-Hoover sort Displacement sort

Builds on: skip lists binary heaps learning-augmented sorting with dirty comparisons learning-augmented sorting with positional predictions van Emde Boas trees

Closest papers by meaning

• Quantifying the Cost of Learning in Queueing Systems (NeurIPS 2023 · similarity 0.83)
• Sorting with Predictions (NeurIPS 2023 · similarity 0.82)
• Algorithm for Contextual Queueing Bandits with Rate-Optimal Queue Length Regret (NeurIPS 2026 · similarity 0.82)
• Non-clairvoyant Scheduling with Partial Predictions (ICML 2024 · similarity 0.81)
• SkipPredict: When to Invest in Predictions for Scheduling (NeurIPS 2024 · similarity 0.81)
• Polynomial Time Learning Augmented Algorithms for NP-hard Permutation Problems (ICML 2025 · similarity 0.81)