Learning-Augmented Priority Queues
Authors: Ziyad Benomar
Christian Coester
Venue: NeurIPS 2024 poster (2024)
Keywords: learning-augmented algorithms
algorithms with predictions
priority queue
shortest paths
Dijkstra
Primary area: machine_learning_for_other_sciences_and_fields

Abstract: Priority queues are one of the most fundamental and widely used data structures in computer science. Their primary objective is to efficiently support the insertion of new elements with assigned priorities and the extraction of the highest priority element.  
In this study, we investigate the design of priority queues within the learning-augmented framework, where algorithms use potentially inaccurate predictions to enhance their worst-case performance.
We examine three prediction models spanning different use cases, and we show how the predictions can be leveraged to enhance the performance of priority queue operations. Moreover, we demonstrate the optimality of our solution and discuss some possible applications.

Learning-Augmented Priority Queues
Ziyad Benomar ENSAE, Ecole Polytechnique,
Christian Coester
Department of Computer Science
FairPlay joint team ziyad. benomar@ensae..
University of Oxford, UK
christian.coester @ cs.csooo ox.ac.uk
Abstract
Priority queues are one of the most fundamental and widely used data structures in computer science. Their primary objective is efficiently support the inser- tion of new elements with assigned priorities and the extraction of the highest priority element. In this study, we investigate the design of priority queues within the -agriing-egmmeteed framework, where algorithms use potentially inaccurate predictions enhance their worst-case performance. We examine three prediction models spanning different use cases, and we show how the predictions can be leveraged enhance the performance of priority queue operations, Moreover, we demonstrate the optimality of our solution and discuss some possible applications.
Introduction
Priority queues essential abstract data type in computer science [Jaiswal 1968 Brodal 2013 whose objective is to enable the swift insertion of new elements and access or deletion of the highest priority element. Their applications span wide range of problems within computer science
and beyond. They play crucial role in sorting (Williams) 1964 Thorup 2007]. in various graph algorithms such Dijkstra's 's shortest path algorithm [Chen al. [007]] or computing minimum spanning trees [Chazelle 2000], in operating systems for scheduling and load balancing [Sharma al., 2022], networking protocols for managing data transmission packets [Moon al. 2000], in
discrete simulations for efficient event processing based on occurrence time [Goh and Thng 2004
and in implementing hierarchical clustering algorithms [Day and Edelsbrunner 1984 Olson
1995
Various data structures can be used to implement priority queues, each offering distinct advantages and tradeoff' [Brodal] 2013) However, it is established that priority queue with elements cannot guarantee ollog r2) time for all the required operations [Brodal and Okasaki, [996]. This limitation can be surpassed within the learning augmented framework [Mitzenmacher and Vassilvitskii 2022).
where the algorithms can benefit from machine-learned or expert advice to improve their worst-case performance. We propose this work -ugmented implementations of priority queues in three different prediction models, detailed in the next section.
1.1 Problem definition
A priority queue is a dynamic data structure where each element is assigned key from totally ordered universe (U1, <), determining its priority. The standard operations of priority queues are:
(i) FindMin(): returns the element with the smallest key without removing it,
(ii) ExtractMin(): removes and returns the element with the smallest key,
(iii) Insert(a, u): adds a new element z to the priority queue with key u,
(iv) (eyr,, e): decreases the key of an element x to v.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

The elements of the priority queue can be accessed via their keys in ((1) time using a MashMap. Hence, the focus is on establishing efficient algorithms for key storage and organization, facilitating the execution of priority queue operations. For any key u E U and subset V C U, we denote by r(u, V) the rank of in V, defined as the number of keys in V that are smaller than or equal to u,
r(u, V) = # (o E V : e S u)
The difficulty lies in designing data structures offering adequate tradeoffs between the complexities of the operations listed above. This paper explores how using predictions can allow us to overcome the limitations of traditional priority queues. We examine three types of predictions.
Dirty comparisons. In the first prediction model, comparing two keys (u, v) E 222 is slow or costly, However, the algorithm can query prediction of the comparison (u < v). This prediction serves as rapid or inexpensive, but possibly inaccurate, method of comparing elements of U, termed a dirty comparison and denoted by (u 2 v). Conversely, the true outcome of (u < v) referred to as a clean comparison. For all u E 2 and V S U, we denote by nuu, V) the number of inaccurate dirty comparisons between u and elements of V.
nu, V) = # (v E 20) + 1(u u)}
This prediction model was introduced in [Bii and Coester 2023] for sorting, but it has a broader significance in comparison-basee
problems, such search BBrgstrro and Kosaraju 1993 Nowak
2009
Tschopp et al. 2011]. ranking [Wauthier et al. 2013 Shah and Wainwright [2018] Heckel et al.
Haghiri et al. 2017 [0188] Ghoshdastidar Particularly. it has great theoretical impor- tance for priority queues. which have been extensively studied in the comparison-be based framework Gonnet and Munro 1986 Brodal and Okasaki 1996 Edelkamp and Wegener 2000]. Comparison- based models are often used, for example, when the preferences are determined by human subjects. Assigning numerical scores in these cases is inexact and prone to errors, while pairwise comparisons are absolute and more robust [David] 1963]. Within such setting, dirty comparisons can be obtained by a binary classifier, and used to minimize human inference yielding clean comparisons, which are time-consuming and might incur additional costs.
2018 and the design of comparison-based ML algorithms
ct al. 2019 Perrot et al. 2020 Meister and Nietert 2021].
Pointer predictions. In this second model, upon the addition of new key u to the priority queue Q, the algorithm receives prediction (red(u, Q) E Q of the predecessor of which is the largest key belonging to Q and smaller than u. Before u is inserted, the ranks of u and its true predecessor in Q are equal, hence we define the prediction error as
iu, Q) Ir(u, Q) r(Pred(u, 2)
In priority queue implementations, HashMap preserves a pointer from each inserted key to its corresponding position in the priority queue. Consequently, Pred(u, Q) provides direct access to the predicted predecessor's 's position. For example, this prediction model finds applications in scenarios where concurrent machines have access to the priority queue (Sundell and Tigas 2005| Shavit and Lotan 2000 [inden and Jonsson| 2013). Each machine can estimate, within the elements it has previously inserted, which one precedes the next element it intends to insert. However, this estimation might not be accurate, as other concurrent machines may have inserted additional elements.
Rank predictions. The last setting assumes that the priority queue is used in a process where finite number N of distinct keys will be inserted, i.c., the priority queue is not used indefinitely, but N is unknown to the algorithm. Upon the insertion of any new key u, the algorithm receives a prediction R(u:) of the rank of u, among all the N keys {ug]SE(N). Denoting by R(us) = r(w., (us))E(N)) the true rank, the prediction error of uz is
Au4) [R(u.) - R(()))
The same prediction model was explored in (McCauley al. 2024 for the online list labeling problem. Bai and Coester (0033 investigate a similar model for the sorting problem, but in an offline setting where the N elements to sort and the predictions are accessible the algorithm from the start.
Note that N counts the distinct keys added with Insert or DecreaseKey operations. An arbitrarily large number of DecreaseKey operations thus can make N arbitrarily large although the total number

---

of insertions is reduced. However, with a lazy implementation of DecreaseKey, we can assume without loss of generality that N is at most quadratic in the total number of insertions. Indeed, is possible to omit executing the DecreaseKey operations when queried, and only store the new elements' keys to update. Then, at the first Extract operation, all the element's ss keys are updated by executing for each one only the last queried DecreaseKey operation involving it. Denoting by the total number of insertions, there are at most & ExtractMin operations, and for each of them, there are at most k DecreaseKey operations executed. The total number of effectively executed DecreaseKey operations is therefore O(k2). In particular, this implies that a complexity of Ollog N) is also logarithmic in the total number of insertions.
1.2 Our results
We first investigate augmenting binary heaps with predictions. To leverage dirty comparisons, we first design randomized binary search algorithm to find the position of an element in a sorted list L. We prove that it terminates using (log [[] dirty comparisons and Ollog (uu, L)) clean comparisons in expectation. Subsequently. we use this result to establish insertion algorithm in binary heaps using (log log n) dirty comparisons and reducing the number of clean comparisons to (log log nu, 2)). However, ExtractMin still mandates O(log n) clean comparisons. In the two other prediction models, binary heaps and other heap implementations of priority queues appear unsuitable, the positions of the keys are not determined solely by their ranks.
Consequently, in Section B] we shift to using skip lists. We devise randomized insertion algo- rithms requiring, in expectation, only Ollog iu, 2)) time and comparisons in the pointer prediction model, Ollo rı) time and Olog (7, 2)) clean comparisons in the dirty comparison model, and Ollog log N + log max 1 (u=)) time and Ollog | 7/ (u.) comparisons in the rank prediction model, where we use in the latter an auxiliary van Emde Boas (vEB) tree [van Emde Boas et al. (dl]] Across the three prediction models, FindMin and ExtractMin only necessitate O(1) time, and the complexity of DecreaseKey aligns with that of insertion. Finally, we prove in Theorem 3.4 the optimality of our data structure. Table 1.2 summarizes the complexities of our learning- augmented priority queue (LAPQ) in the three prediction models compared to standard priority queue implementations. The complexity of FindMin is O(1) for all the listed priority queues.
Priority queues
ExtractMin Ologn n)
Insert
DecreaseKey O n)
Binary Heap
O log n)
Fibonacci Heap (amortized)
Ologn n)
Skip List (average)
0(1)
Ollog n.
LAPQ with dirty comparisons (average)
0(1)
Ollog m(u, 2)
LAPQ with pointer predictions (average)
O(1)
Olog 77 Q)
LAPQ with rank predictions (average)
O(1)
Ollog maXie(n] (u))
Table I: Number of comparisons per operation used by different priority queues.
data structure enables additional operations beyond those of priority queues, such as the maximum priority queue operations FindMax, ExtractMax, and IncreaseKey with anal- ogous complexities, and removing arbitrary key u from the priority queue, finding its predecessor or successor in expected (1) time.
Our
Furthermore, we show in Section 4.1 that it can be used for sorting, yielding the same guarantees as the saarning-augmentrr sorting algorithms presented in (Bai and Coester 2023) for the positional predictions model with displacement error, and for the dirty comparison model. In the second model, our priority queue offers even stronger guarantees, as it maintains the elements sorted at any time even if the insertion order is adversarial, while the algorithm of [Bai and Coester 2023 requires random insertion order to achieve a sorted list by the end within the complexity guarantees. We also priority queue can be used to accelerate Dijkstra's 's algorithm.
show how the cearning-augment
Finally, in Section 5 we compare the performance of our priority queue using predictions with binary and Fibonacci heaps when used for sorting and for Dijkstra's 's algorithm on both real-world city maps and synthetic graphs. The experimental results confirm our theoretical findings, showing that adequately using predictions significantly reduces the complexity of priority queue operations.
3

---

1.3 Related work
In this section, we briefly discuss related works on learning-augmennn algorithms and priority queues. For more extensive review of related work, please refer to Appendix A
Learning-aughn augmented algorithms. Learning-augmentee algorithmss, introduced in [Lykouris and Vassilvtiskii] 2018 Purohit al., 2018), have captured increasing interest over the last years, as they allow breaking longstanding limitations in many algorithm design problems. Assuming that the decision-maker is provided with potentially incorrect predictions regarding unknown parameters of the problem, learning-ause augmented algorithms must be capable of leveraging these predictions if they are accurate (consistency), while keeping the worst-case performance without advice even if the predictions are arbitrarily bad or adversarial (robustness). While many fundamental online problems were studied in this setting (see Appendix A the design of data structures with predictions remains relatively underexplored. The seminal paper by (Kraska et al. [2018) shows how predictions can be used optimize space usage. Another study by [Lin et al. [022] demonstrates that the runtime of binary search trees can be optimized by incorporating predictions of item access frequency. Recent papers have extended this prediction model to other data structures, such as dictionaries (Zeynali et al. 2024] and skip lists [Fu et al.) [024]. The prediction models we study in the current paper deviate from the latter, and are more related to those considered respectively in [[Bii and Coester 2023] for sorting, and [McCauley et al. 2024 for online list labeling. An overview of the growing body of work on learning- Learning-augmenntn amented algorithms (also known as algorithms with predictions) is maintained at [Lindermayr and Megow 2022].
Priority queues implementations. Binary heaps, introduced by Williams 1964] are one of the first efficient implementations of priority queues. They allow all the operations (log n) time, where n is the number of items in the queue. A first improvement was introduced with Binomial heaps [Vuillemin| 1978), reducing the amortized time of insertion to O(1). A breakthrough came later with Fibonacci heaps [Fredman and Tarjan| 1987]. which allow all the operations in constant amortized time, except for Extract which takes Olog n)) time. However, Fibonacci heaps are known to be slow in practice [Larkin et al., 2014), and other implementations with weaker theoretical guarantees such as binary heaps are often preferred. Another possible implementation uses skip lists [Pugh] 1990]. which are probabilistic data structures, guaranteeing in expectation constant time for Fin and ExtractMin, and Ollg n) time for Insert and Decreasekey.
2 Heap priority queues
common implementation of priority queues uses binary heaps, enabling all operations in O(log n) time. Binary heaps maintain balanced binary tree structure, where all depth levels are fully filled, except possibly for the last one, to which we refer in all this section as the leaf level. Moreover, it satisfies the heap property, i.e., any key is smaller than all its children. To maintain these two structure properties, when a new element is added, it is first inserted in the leftmost empty position in the leaf level, and then repeatedly swapped with its parent until the heap property is restored.
2.1 Insertion in the comparison- model
Insertion in binary heap can be accomplished using only O(log I) comparisons, albeit Oloo n) time, by doing a binary search of the new element's 's position along the path from the leftmost empty position in the leaf level to the root, which is sorted list of size O (log n). To improve the insertion complexity with dirty comparisons, we first tackle the search problem in this setting.
Search with dirty comparisons. Consider a sorted list (UI,..... . 2k) and a target u, the position of u in L can be found using binary search with Ologg k) comparisons. Extending ideas from Bai and Coester (2023) and [Lkkorii and Vassilvtiskii [2018). this complexity can be reduced using dirty comparisons. Indeed, we can obtain an estimated position F(u, L) through binary search with dirty comparisons, followed by an exponential search with clean comparisons, starting from F(u, L) to find the exact position r(u, L.). However, the positions of inaccurate dirty comparisons can be adversarially chosen to compromise the algorithm. This can addressed by introducing randomness to the dirty search phase. We refer to the randomized binary search as the algorithm that proceeds

---

similarly to the binary search, but whenever the search is reduced to an array {ri,..., 2/ instead of comparing u to the pivot Um with index = =++ - it compares to pivot with an index chosen uniformly at random in the range {i+ (+t.......
Theorem 2.1. A dirty randomized binary search followed by clean exponential search finds the target's 's position using (log k) dirty comparisons and Ollog n(u, L)) clean comparisons in expectation.
Randomized insertion in a binary heap. In a binary heap 2, any new element is always inserted along the path of size (log n) from the root to the leftmost empty position in the Icaf level. If all the inaccurate dirty comparisons are chosen along this path, then the insertion would require
Ollog (u, 2)) clean comparisons by Theorem 2.1 This complexity can be reduced further by
randomizing the choice of the root-leaf path where inserted, as explained in Algorithm |
Algorithm 1: Randomized insertion in binary heap
Input: Binary heap Q with randomly filled positions in the leaf level, new key
L + keys path from a uniformly random empty position in the leaf level to the root; F(u, L) outcome of a dirty randomized binary search of in L;
3 r r(u, L) + outcome of the clean exponential search of u in L starting from index F(u, L); Insert in the chosen leaf empty position, then swap it with its parents until position r(u, L);
Theorem 2.2. The insertion algorithm] 7 requires O n) time, O(log log n) dirty comparisons and Oloo log n(u, Q)) clean comparisons in expectation.
2.2 Limitations
The previous theorem demonstrates that accurate predictions can reduce the number of clean compar- isons for insertion in binary heap. However, for the ExtractMin operation, when the minimum key, which is the root of the tree, is deleted, its two children are compared and the smallest is placed in the root position, and this process repeats recursively, with each new empty position filled by comparing both of its children, requiring necessarily O(log n) clean comparisons in total to ensure the heap priority remains intact. Improving the efficiency of ExtractMin using dirty comparisons would therefore require bringing major modifications to the binary heap's ' structure.
Similar difficulties arise when attempting to enhance ExtractMin using dirty comparisons or the other prediction models in different heap implementations, such as Binomial or Fibonacei heaps. Consequently, we explore in the next section another priority queue implementation, using skip lists, which allows for an easier and more efficient exploitation the predictions.
3
Skip lists
A priority queue can be implemented naively by maintaining a dynamic sorted linked list of keys. This guarantees constant time for ExtractMin, but O(n) time for insertion. Skip lists (see Figure I offer a solution to this inefficiency, by maintaining multiple levels of linked lists, with higher levels containing fewer elements and acting as shorteuts to lower levels, facilitating faster search and insertion in expected O (log n)) time. In all subsequent discussions concerning linked lists or skip lists, is assumed that they are doubly linked, having both predecessor and successor pointers between elements.
The first level in skip list is an ordinary linked list containing all the elements, which we denote by uI,..., Un. Every higher level is constructed by including each element from the previous level independently with probability p, typically set to 1/2. For any key v; in the skip list, we define its height h((1)) as the number of levels where it appears, which is an independent geometric random variable with parameter p. A number 2h(u;) of pointers are associated with v, giving access to the previous and next element in each level e E [h((v)),, denoted respectively by Prev(u;, E) and Nexi(w;, f). Using a MashMap, these pointers can be accessed ((1) time via the key value v;. For convenience, we consider that the skip list contains two additional keys up -oo and un+1 co, corresponding respectively to the head and the NIL value. Both have height equal to the maximum height in the queue h(vo) h(v,+1) maxiee) h(e)).
5

---

HEAD
Figure 1: skip list with keys 01 <... < 2g E U.
Since the expected height keys in the skip list is 1/p, deleting any key only requires a constant time in expectation, by updating its associated pointers, along with those of its predecessors and successors in the levels where appears. In particular, FindMin and ExtractMin take O(1) time, and DecreaseKey can be performed by deleting the element and reinserting it with the new key, yielding the same complexity as insertion. Furthermore, by the same arguments, inserting new key next to given key in the skip list can be done in expected constant time.
Therefore, implementing efficient Insert and DecreaseKey operations for skip lists with predictions is reduced to designing efficient search algorithms to find the predecessor of a target key in the skip list, i.c., the largest key v in the skip list that smaller than u. all the following, we denote by Q skip list containing keys S S Un E UI and u E U the target key. As explained in Appendix C.1 we can assume without loss of generality that the keys (u, U1,..., vn) are pairwise distinct. In the following, we present separately for each model an insertion algorithm leveraging the predictions.
3.1 Pointer prediction
Given a pointer prediction vy = Pred(u, Q), we describe below an algorithm for finding the true predecessor starting from the position of the key Vy. then inserting u. We assume the algorithm that By S If by > then the algorithm can be easily adapted by reversing the search direction.
Algorithm 2: Expsearchlnnsettinn( Q, új u)
Input: Skip list Q, source by E Q, and new key E U
w. + Dj:
> Bottom-Up search
while Next(w, h(w)) do
w & Next(w, h(w)):
Ct h(w);;
Top-Down search
5 while f 500 do while Next(w, E) < do t Noxt(w, E);
f-t-1 1;
Insert next W:;
Algorithm iss inspired by the classical exponential search in arrays. The first phase consists of bottom-up search, expanding the size of the search interval by moving to upper levels until finding key E satisfying < u Next(w, h(w)). The second phase conducts a top-down search from level haw)) downward, refining the search until locating the position of u. It is worth noting that the classical search algorithm in skip lists, denoted by Search( Q, u), corresponds precisely to the top-down search, starting from the head of the skip list instead of w.
Theorem 3.1. Augmented with pointer predictions, skip list allows FindMin and ExtractMin expected O(1) time, and Insert(u u) in expected Ollog Tu, Q)) time using Algorithm 2

---

3.2 Dirty comparisons
We devise in this section a search algorithm using dirty and clean comparisons. Algorithm 3 first estimates the position of u with dirty top-down search starting from the head, then performs clean exponential search starting from the estimated position to find the true position.
Algorithm 3: Insertion with dirty and clean comparisons
Input: Skip list Q, new key u E U
ii <- Search Q, u) with dirty comparisons;
ExpSearchInserttinn Q úũ u) with clean comparisons;
The dirty search concludes within (log n) steps, and Theorem 3.1 guarantees that the exponential search terminates within (log r( 2) r(u, 2) steps. Combining these results and relating the distance between u and vi in Q to the prediction error ry(u, Q). we derive the following theorem.
Theorem 3.2. Augmented with dirty comparisons, skip list allows FindMin and ExtractMin in O(1) expected time, and Inscrt(u) with Algorithm in (log n) expected time, using Ollog n) dirty comparisons and Olog ru, Q)) clean comparisons in expectation.
3.3 Rank predictions
In the rank prediction model, each Insert(u) request accompanied by prediction R(w) of the rank of u among all the distinct keys already in, or to be inserted into the priority queue. If the predictions are accurate and the total number N of distinct keys to be inserted is known, the problem reduces to
designing priority queue with integer keys in [N]. taking as keys the ranks [R)) This problem
can be addressed using a van Emde Boas (vEB) tree over [N] [van Emde Boas et al. 1976]. which
requires (log log N) time for insertion, deletion, finding the minimum maximum, and finding the predecessor or successor of any element, guaranteeing in particular Olog log N) time for all priority queue operations. More details on its structure can found in Appendix C.5
To leverage rank predictions, we use an auxiliary vEB tree T along with the skip list Q. All the insertion and deletion operations are made simultaneously on T and Q. However, the priorities used in T are the predicted ranks {R( (u:) JEEN] Whenever a new key u; to be added, Algorithm inserts it first in T at position R(w.), gets its predecessor é in T, i.e., the element in T with the largest predicted rank smaller than or equal R(u4), then uses á as a pointer prediction find the position of un in Q If the predecessor is not unique, the algorithm chooses an arbitrary one.
Algorithm 4: Insertion with rank prediction
Input: Skip list Q, vEB tree T on [N], new element u, E U. prediction R(u.) [N] Insert uq in T with key R(u:); v + predecessor of u, in T;
ExpSearchlnssrtionn Q, u u:);
We explain in Appendix C.5 how the data structure be adapted when N is unknown and the rank predictions are not necessarily in [N], and we prove the following theorem, giving both the runtime and comparison complexities of the priority queue operations using this data structure.
Theorem 3.3. If R(u,) = (NN for all i E [N), then there is a data structure allowing FindMin and ExtractMin in ((1) amortized time, and Insert Oloog log N + log max4e[N] 17 (u,)) amortized time using (log max A (u:)) comparisons in expectation.
In contrast to other prediction models, the complexity of inserting u, is not impacted only by ^ (u.). but by the maximum error over all keys [u)])- This occurs because the exponential search conducted in Algorithm I starts from the key w E Q. whose emror also affects insertion performance. similar behavior is observed in the online list labeling problem [McCauley et al., 2024), where the bounds provided by the authors also depend the maximum prediction error for insertion.
7

---

With perfect predictions, the number of comparisons for insertion becomes constant, and its runtime (log log ). is not clear if the runtime of all the priority queue operations can be reduced to ( with perfect predictions. Indeed, the problem in that case is reduced to priority queue with all the keys in [ The best-known solution to this problem a randomized priority queue, by Thorup [2007], supporting all operations in O( Ololog log N) time. However, in our approach, we use vEB trees beyond the classical priority queue operations, as we also require fast access to the predecessor of any element. A data structure supporting all these operations solves the dynamic predecessor problem, for which vEB trees are optimal Pātraşşu and Thorup 2006]. Reducing the runtime of insertion below Ollog log N) would therefore require omitting the use of predecessor queries.
3.4 Lower bounds
As explained earlier, ExtractMin requires only (L1) expected time in skip lists. Furthermore, we presented insertion algorithms for the three prediction models and provided upper bounds on their complexities. The following theorem establishes lower bounds on the complexities of MxtractMin and Insert for any priority queue augmented with any of the three prediction types.
Theorem 3.4. For each of the three prediction models, the following lower bounds hold.
(i) Dirty comparisons: no data structure Q can support ExtractMin with ((1) clean compar- isons and Insert(u) with o(log (u, 2)) clean comparisons in expectation.
(ii) Pointer predictions: no data structure Q can support ExtractMin with O(1) comparisons and Insert(u) with ollog ij(u, u, 2) comparisons in expectation.
(ii) Rank predictions: no data structure can support ExtractMin with O(1) comparisons and Insert(u;) u.) with o(log max]e[N] 1) (u:) comparisons in expectation, for all i E [N.
These lower bounds with Theorems 3.2 and 3.1 prove the tightness of our priority queue in the dirty comparison and the pointer prediction models. In the rank prediction model, the comparison complexities proved in Theorem 3.3 are optimal, whereas the runtimes are only optimal up to an additional Olog log N) term. In particular, they are optimal if the maximal error is at least 2(log N).
4 Applications
4.1
Sorting algorithm
Our
priority queue can used for sorting a sequence A (ai...., ap), by first inserting all the elements, then repeatedly extracting the minimum until the priority queue is empty. We compare below the performance of this sorting algorithm to those of [Bai and Coester 2023
Dirty comparison model. Denoting by T 17,,, A), Bai and Coester 2023 prove sorting algorithm using (n log n) time, (n log nt) dirty comparisons, and O log(n: + 2)) clean com- parisons. Theorem 3.2 yields the same guarantees with our learning-auge augmented priority queue. Moreover, our learning- augmented priority queue is skip list, maintaining elements in sorted order at any time, even if the elements revealed online and the insertion order is adversarial, while in [Bai and Coester 2023), it crucial that the insertion order is chosen uniformly at random.
Positional predictions. In their second prediction model, they assume that the algorithm is given offline access predictions (R(a:) of the relative ranks (R(a,) of the elements to sort, and they study two different error measures. The rank prediction error n, = [R(a,) ) Ra.)) matches their definition of displacement error, for which they prove a sorting algorithm in O log(n +2) time. The same bound can be deduced using our results in the pointer prediction model. Further discussion on this claim can be found in Appendix
Online rank predictions. If n. is unknown to the algorithm, and the elements a1...., along with their predicted ranks are revealed online, possibly an adversarial order, then by Theorem 3.3
the total runtime of our priority queue for maintaining all the inserted elements sorted at any time On log log n + n log max; r and the number of comparisons used is On log max, v.)). ). No analogous result is demonstrated in Bai and Coester 2023 in this setting.

---

4.2 Dijkstra's shortest path algorithm
Consider run of Dijkstra's algorithm on a directed positively weighted graph G with n nodes and m edges. The elements inserted into the priority queue are the nodes of the graph, and the corresponding keys are their tentative distances to the source, which are updated over time. During the algorithm's s execution, at most m + 1 distinct keys {d, [m+11] are inserted into the priority queue. Given online predictions (R(d:)) (e(dd))))(m++ ve[m+11 of their relative ranks (e(())))((++) the total runtime using our priority queue augmented with rank predictions is
(m log log + m log max [R(d.) - R(d))).
(c(m++]
In contrast, the shortest path algorithm Lattanzi et al. 2023) (which also works for negative edges) has linear dependence on similar error measure. Even with arbitrary error, our guarantee is never worse than the Om log runtime with binary heaps. Using Fibonacci heaps results in an O(n log n + m) runtime, which is surpassed by our sparse graphs where Fibonacci heaps perform poorly in practice, even compared binary heaps, as supported by our experiments.
priority queue in the case of log if predictions of high quality. However, it is known that
of log log
5 Experiments
In this section, we empirically evaluate the performance of our Gaaning-augmentee priority queue (LAPQ) by comparing it with Binary and Fibonacci heaps. We use two standard benchmarks for this evaluation: sorting and Dijkstra's 's algorithm. For the sorting henchmark, we also compare our results with those from Bai and Coester [2023] For Dijkstra's algorithm, assess performance on both real city maps and synthetic random graphs. In all the experiments, each data point represents the average result from 30 independent runs. Additional experiments and a detailed discussion on the prediction models and the obtained results can be found in Appendix The code used for conducting the experiments is available at gtgghuu..om//iyaad Benomar/Learning www.umeeed-prrortteteeeeeee
Sorting. We compare sorting using our LAPQ with the algorithms of Bai and Coester 2023 under their same experimental settings. Given sequence A (01,..., a. evaluate the complexity of sorting it with predictions in the class and the decay setting. In the first, A is divided into e classes ((fx-1, bx]) where 0- to f S ... S le n are uniformly random thresholds. The predicted rank of any item a, with fg S i tx+1 is sampled uniformly at random within (tg, tx+1]- In the decay setting, the ranking is initially accurate but degrades over time. Each time step, one item's 's predicted position is perturbed by 1, either left right, uniformly at random.
In both settings, we test the LAPQ with the three prediction models. First, assuming that the rank predictions are given offline, we use pointer predictions as explained in Appendix [.] In the second case, the elements to insert along with their predicted ranks are revealed online in a uniformly random order. Finally, we test the dirty comparison setting with the dirty order (a, 2 a,)) = (i(a.) < R(a,)).
172
LAP
15.
King
Di der Sione
Nevry
Figure 2: Sorting in the class setting
Figure 3: Sorting in the decay setting
Figures
and show the obtained results respectively in the class and the decay setting for E T 10 In the class setting with offline predictions, the LAPQ slightly outperforms the Double-Hooue and Displacement sort algorithms of Bai and Coester (2023), which were shown to outperform classical sorting algorithms. In the decay setting, the LAPQ matches the performance

---

of the Displacement sort, but is slightly outperformed by the Double-Hoover sort. With online predictions, although the problem is harder, LAPQ's performance remains comparable the pre- vious algorithms. In both settings, the LAPQ with offline predictions, online predictions, and dirty comparisons all yield better performance than binary or Fibonacci heaps, even with predictions that are not highly accurate.
Dijkstra's algorithm. Consider graph G EV with n nodes and m edges, and source node E V. In the first predictions setting, we pick a random node á and run Dijkstra's 's algorithm with $ as the source, memorizing all the keys D = (di.... ......))) inserted into the priority queue. In subsequent runs of the algorithm with different sources, when key d; is be inserted, we augment the insertion with the rank prediction R(d.)- r(d,, D)). We call these key rank predictions. This model aims at exploiting the topology and uniformity of city maps. As computing shortest paths from any source necessitates traversing all graph edges, keys inserted into the priority queue- paaeeapartaalala sums of edge lengths-and are likely to exhibit some degree of similarity even if the algorithm is executed from different sources. Notably, this prediction model offers an explicit method for computing predictions, readily applicable in real-world scenarios.
In the second setting, we consider rank predictions of the nodes in G. ordered by their distances s. As Dijkstra's 's algorithm explores a new node I E V, it receives a prediction f(z) of its rank. The node is then inserted with key d;, to which we assign the prediction R(d.) f(æ). Unlike the previous experimental settings, we initially have predictions of the nodes' ranks, which we extend to predictions of the keys' ranks. Similarly to the sorting experiments, consider class and decay perturbations of the node ranks.
In the context of searching the shortest path, rank predictions in the class setting can be derived from subdividing the city into multiple smaller areas. Each class corresponds to a specific area, facilitating the ordering of areas from closest to furthest relative to the source. However, comparing the distances from the source to the nodes in the same class might be inaccurate. On the other hand, the decay setting simulates modifications to shortest paths, such as rural works or new route constructions, by adding or removing edges from the graph. These alterations may affect the ranks of a limited number of nodes, which corresponds to the time steps in the decay setting.
We present below the experiment results obtained with the maps of Paris and London. More experiments with additional city maps and synthetic graphs are in Appendix [F] The city maps were obtained using the Python library Osmmx [Boeing, 2017]. Figures I and respectively illustrate the results in the class and the decay settings with node rank predictions. In both figures, for each city, we present the numbers of comparisons used for the same task by binary and Fibonacci heap, and the number of comparisons used when the priority queue is augmented with key rank predictions.
9539
London
9559. 18400
London: 128924,ee 300512
(Hcompaatsoooshh
(heompartoons
105
15-
53-
00
11
(Aclasscsión
(Helaxses Vi
(Hiimestops)/n
(#timestepsänn
Figure 4: Shortest path, class predictions
Figure 5: Shortest path, decay predictions
In both settings, the performance of the LAPQ substantially improves with the quality of the predictions, and notably, key rank predictions yield almost the same performance as perfect node rank predictions, affirming intuition on the similarity between the keys inserted in runs of Dijkstra's algorithm starting from different sources.
References
Keerti Anand, Rong Ge, and Debmalya Panigrahi. Customizing ml predictions for online algorithms. In International Conference on Machine Learning, pages 303-313. PMLR, 2020.
10

---

Antonios Antoniadis, Themis Gouleakis, Pieter Kleer, and Pavel Kolev. Secretary and online matching problems with machine learned advice. Advances in Neural Information Processing Systems, 33: 7933-7944, 2020.
Antonios Antoniadis, Christian Coester, Marek Eliás, Adam Polak, and Bertrand Simon. Learning- augmented dynamic power management with multiple states via new ski rental bounds. Advances in Neural Information Processing Systems, 144167144-66720 2021.
Antonios Antoniadis, Joan Boyar, Marek Eliás, Lene Monrad Favrholdt, Ruben Hoeksma, Kim Larsen, Adam Polak, and Bertrand Simon. Paging with succinct predictions. In International Conference on Machine Learning, pages 952-968. PMLR, 2023a.
Antonios Antoniadis, Christian Coester, Marek Eliáš, Adam Polak, and Bertrand Simon. Online metric algorithms with untrusted predictions. ACM Transactions on Algorithmss, 19(2):1-34, 2023b.
Xingjian Bai and Christian Coester. Sorting with predictions. Advances in Neural Information Processing Systems, 36, 2023.
Etienne Bamas, Andreas Maggiori, and Ola Svensson. The primal-dual method for learning aug- mented algorithms. Advances in Neural Information Processing Systems, 33:20083-20094 2020.
Nikhil Bansal, Christian Coester, Ravi Kumar, Manish Purohit, and Erik Vee. Leaning-augmented weighted paging. In Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 67-89. SIAM, 2022.
Dmitry Basin, Edward Bortnikov, Anastasia Braginsky, Guy Golan-Gueta, Eshcar Hillel, Idit Keidar, and Moshe Sulamy. Kiwi: key-value map for scalable real-time analytics. Proceedings of the 22Nd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pages 357-369, 2017.
MossmmadHosseenn Bateni, Prathamesh Dharangutte, Rajesh Jayaram, and Chen Wang. Metric clustering and mst with strong and weak distance oracles. arXiv preprint arXiv:2310. (.V.::33../586,,, 2023.
Ziyad Benomar and Vianney Perchet. Advice querying under budget constraint for online algorithms. Advances in Neural Information Processing Systems, 36, 2024a.
Ziyad Benomar and Vianney Perchet. Non-clairvoyant scheduling with partial predictions. In Forty-first International Conference on Machine Learning. 2024b.
Ziyad Benomar, Chaima Ghribi, Elie Cali, Alexander Hinsen, and Benedikt Jahnel. Agent-based modeling and simulation for malware spreading in d2d networks. AAMAS '22, page 91-99, Richland, SC, 2022a. International Foundation for Autonomous Agents and Multiagent Systems. ISBN 978 1781432332166
Ziyad Benomar, Chaima Ghribi, Elie Cali, Alexander Hinsen, Benedikt Jahnel, and Jean- Sha-Philippe Wary. Multi-agent simulations for virus propagation in D2D 5G+ networks. 2022b.
Ziyad Benomar, Evgenii Chzhen, Nicolas Schreuder, and Vianney Perchet. Addressing bias in online selection with limited budget of comparisons. arXiv preprint arXiv:2303.0999 39000090000....... 2023.
Aditya Bhaskara, Ashok Cutkosky, Ravi Kumar, and Manish Purohit. Logarithmic regret from sublinear hints. Advances in Neural Information Processing Systems, 34:28222-28232, 2021.
Geoff Boeing. Osmnx: New methods for acquiring, constructing, analyzing, and visualizing complex street networks. Computers, environment and urban systems, 65:1 15:1226139, 2017.
Ryan S Borgstrom and S Rao Kosaraju. Comparison-basee based search in the presence of errors. In Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, pages 130-136. 1993.
Gerth Stølting Brodal. Worst-case efficient priority queues. In Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA *96, page 52-58, USA, 1 1996. Society for Industrial and Applied Mathematics. ISBN 0898713668.

---

Gerth Stølting Brodal. A survey on priority queues. In Cffcc-Efficiett Data Structures, Streams, and Algorithms: Papers in Honor of J. lan Munro on the Occasion of His 66th Birthday, pages 150-163. Springer, 2013.
Gerth Stølting Brodal and Chris Okasaki. Optimal purely functional priority queues. Journal of Functional Programmingg 6(6):839-88) -577839977777 1996.
Gerth Stølting Brodal, George Lagogiannis, and Robert E Tarjan. Strict fibonacci heaps. In Pro- ceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 1177-1184, 2012.
Bernard Chazelle. A minimum spanning tree algorithm with inverse-ackermann type complexity. Journal of the ACM (JACM), 47(6))1028-1060 2000.
Justin Chen, Sandeep Silwal, Ali Vakilian, and Fred Zhang. Faster fundamental graph algorithms via learned predictions. In International Conference Machine Learning, pages 3583-3602. PMLR,
2022.
Mo Chen, Rezaul Alam Chowdhury, Vijaya Ramachandran, David Lan Roche, and Lingling Tong. Priority queues and dijkstra's algorithm. 2007.
Jakub Chikedowski, Adam Polak, Bartosz Szabucki, and Konrad Tomasz Zolna. Robust learning- augmented caching: An experimental study. In International Conference Machine Learning, pages 1920-1930. PMLR, 2021.
Nicolas Christianson, Junxuan Shen, and Adam Wierman. Optimal robustness coanssttess-cooissteeyy tradeoffs for augmene-e metrical task systems. International Conference on Artificial Intelligence and Statistics, pages 9377-9399. PMLR, 2023.
Clark Allan Crane. Linear lists and priority queues as balanced binary trees. Stanford University, 1972.
Herbert Aron David. The method of paired comparisons, volume 12. London, 1963.
William HE Day and Herbert Edelsbrunner. Efficient algorithms for agglomerative hierarchical clustering methods. Journal of classification, 1(1):7-24, 1984.
llaas Diakonikolas, Vasilis Kontonis, Christos Tzamos, Ali Vakilian, and Nikos Zarifis. Learning online algorithms with distributional advice. In International Conference Machine Learning, pages 2687-2696. PMLR, 2021.
Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Faster matchings via learned duals. Advances neural information processing systems, 34:10393-10406. 2021.
Franziska Eberle, Felix Hommelsheim, Alexander Lindermayr, Zhenwei Liu, Nicole Megow, and Jens Schlöter. Accelerating matroid optimization through fast imprecise oracles. arXiv preprint arXiv:2402.02774, 2024.
Stefan Edelkamp and Ingo Wegener. On the performance of weak-heapsort. In Annual Symposium on Theoretical Aspects of Computer Science, pages 254-266. Springer, 2000.
Bennett Eisenberg. On the expectation of the maximum of iid geometric random variables. Statistics & Probability Letters, 78(2):135-144 2008
Michael L Fredman and Robert Endre Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM (JACM), 34(3):596-615 1987.
Chunkai Fu, Jung Hoon Seo, and Samson Zhou. Learning-augmented skip lists. arXiv preprint 1PX1:22402.10457, 2024.
Anna Gambin and Adam Malinowski. Randomized meldable priority queues. In International Conference on Current Trends in Theory and Practice of Computer Science, pages 344-349. Springer, 1998.
12

---

Tingjian Ge and Stan Zdonik. A skip-list approach for efficiently processing forecasting queries. Proceedings of the VLDB Endowment, 1(1):984-995, 2008.
Debarghya Ghoshdastidar, Michaël Perrot, and Ulrike von Luxburg. Foundations of comparison based
hierarchical clustering. Advances in neural information processing systems, 32, 2019.
Catherine Gloaguen and Elie Cali. Cost estimation of fixed network deployment over urban territory. Annals of Telecommunications, 73:367-380, 2018.
Catherine Gloaguen, Frank Fleischer, Hendrik Schmidt, and Volker Schmidt. Fitting of stochastic telecommunication network models via distance measures and monte- monte-carlo tests. Telecommunica- tion Systems, 31:353-377, 2006.
Rick Siow Mong Goh and lan Li-Jin Thng. Dsplay: An efficient dynamic priority queue structure for discrete event simulation. In Proceedings the SimTecT Simulation Technology and Training Conference. Citeseer, 2004.
Sreenivas Gollapudi and Debmalya Panigrahi. Online algorithms for rent-or-buy buy with expert advice. In International Conference on Machine Learning, pages 2319-2327. PMLR, 2019.
Gaston H Gonnet and J Ian Munro. Heaps heaps. SIAM Journal Computing, 15(4):964 971, 1986.
Siavash Haghiri, Debarghya Ghoshdastidar, and Ulrike von Luxburg. Comparison-basee nearest neighbor search. In Artificial Intelligence and Statistics, pages 851-859. PMLR, 2017.
Siavash Haghiri, Damien Garreau, and Ulrike Luxburg. Comparison- based random forests. In International Conference on Machine Learning, pages 1871-1880. PMLR, 2018.
Reinhard Heckel, Max Simchowitz, Kannan Ramchandran, and Martin Wainwright. Approximate ranking from pairwise comparisons. In International Conference on Artificial Intelligence and Statistics, pages 1057-1066. PMLR, 2018.
Yih-Chun Hu, Adrian Perrig, and David B Johnson. Efficient security mechanisms for routing protocolsa. In Ndss. Citeseer, 2003.
Sungjin Im, Ravi Kumar, Aditya Petety, and Manish Purohit. Parsimonious learning-augmented caching. In International Conference on Machine Learning, pages 9588-9668 PMLR, 2022.
Narendra Kumar Jaiswal. Priority queues, volume 50. Academic press New York, 1968.
Tim Kraska, Alex Beutel, Ed H Chi, Jeffrey Dean, and Neoklis Polyzotis. The case for learned index structures. In Proceedings of the 2018 international conference on management of data, pages 489-504, 2018.
Daniel H Larkin, Siddhartha Sen, and Robert E Tarjan. A back-to-basie empirical study of priority queues. In 2014 Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments (ALENEX), pages 61-72. SIAM, 2014.
Alexandra Anna Lassota, Alexander Lindermayr, Nicole Megow, and Jens Schlöter. Minimalistic predictions to schedule jobs with online precedence constraints. In International Conference on Machine Learning, pages 18563-18583. PMLR, 2023.
Silvio Lattanzi. Ola Svensson, and Sergei Vassilvitskii. Speeding up bellman ford via minimum violation permutations. In International Conference on Machine Learning. ICML 2023, 2023.
Rhyd Lewis. A comparison of dijkstra's algorithm using fibonacci heaps, binary heaps, and self- balancing binary trees. arXiv preprint arXiv:2303.10034 2023.
Honghao Lin, Tian Luo, and David Woodruff. Learning augmented binary search trees. In Interna- tional Conference on Machine Learning, pages 13431-13440. PMLR, 2022.
Jonatan Lindén and Bengt Jonsson. A saiplist-based concurrent priority queue with minimal memory contention. In Principles of Distributed Systems: 17th International Conference, OPODIS 2013, Nice, France, December 16-18, 2013. Proceedings 17, pages 206-220. Springer, 2013.
13

---

Alexander Lindermayr and Nicole Megow. Algorithms with predictions.
https: //
algorithms www.t--eedediiiioe.... www.eiiiiinniiitu....o. 1o 2022.
Thodoris Lykouris and Sergei Vassilvtiskii. Competitive caching with machine learned advice. In International Conference on Machine Learning, pages 3296-3305. PMLR, 2018
Jessica Maghakian, Russell Lee, Mohammad Hajiesmaili, Jian Li, Ramesh Sitaraman, and Zhenhua Liu. Applied online algorithms with heterogeneous predictors. In International Conference on Machine Learning, pages 23484-234977 PMLR, 2023.
Samuel McCauley, Ben Moseley, Aidin Niaparast, and Shikha Singh. Online list labeling with predictions. Advances in Neural Information Processing Systems, 36, 2024.
Michela Meister and Sloan Nietert. Learning with comparison feedback: Online estimation of sample statistics. In Algorithmic Learning Theory, pages 983-1001 PMLR, 2021.
Nadav Merlis, Hugo Richard. Flore Sentenac, Corentin Odic, Mathieu Molina, and Vianney Perchet. On preemption and learning in stochastic scheduling. International Conference on Machine Learning, pages 24478-24516, PMLR, 2023.
Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. Communications of the ACM, 65(7))33-335 2022.
Sung- Whan Moon, Jennifer Rexford, and Kang G Shin. Scalable hardware priority queue architectures for high-speed packet switches. IEEE Transactions on computers, 49(11):1215-1227 2000.
Robert Nowak. Noisy generalized binary search. Advances in neural processnnonnprocssiinng systems, 22, 2009.
Clark F Olson. Parallel algorithms for hierarchical clustering. Parallel computing, 2113):1313-1325, 1995.
Mihai Pătraşcu and Mikkel Thorup. Time-space trade-offs for predecessor search. In Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, pages 232-240, 2006.
Michaël Perrot, Pascal Esser, and Debarghya Ghoshdastidar. Near-optimal comparison based cluster- ing. Advances in Neural Information Processing Systems, 33:19388-1999 19399, 2020.
William Pugh. Skip lists: probabilistic alternative to balanced trees. Communications of the ACM, 33(6):668-6)) 676, 1990.
Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ml predictions. Advances in Neural Information Processing Systems, 31, 2018
Robert Rönngren and Rassul Ayani. A comparative study of parallel and sequential priority queue algorithms. ACM Transactions on Modeling and Computer Simulation (TOMACS), 7(2):157-209 1997.
Karim Ahmed Abdel Sadek and Marek Elias. Algorithms for caching and MTS with reduced number of predictions. In The Twelfth International Conference on Learning Representations, 2024. URL
htttps://operreviez httpr/arrrrreeeeeeefououuuuaaaa htt.:/oorrmmmddduuiissttttet
Nihar B Shah and Martin Wainwright. Simple, robust and optimal ranking from pairwise compar- isons. Journal of machine learning research, 18(199):1-38, 2018.
Avinash Sharma, Dankan Gowda, Anil Sharma, S Kumaraswamy. MR Arun, et al. Priority queueing model- based iot middleware for load balancing. In 2022 6th International Conference on Intelligent Computing and Control Systems (ICICCS), pages 425-4344 IEEF, 2022.
Nir Shavit and Itay Lotan. Skiplist-based concurrent priority queues. In Proceedings 14th Inter- national Parallel and Distributed Processing Symposium. IPDPS 2000, pages 263-268. IEEE, 2000.
14

---

Yongho Shin, Changyeol Lee, Gukryeol Lee, and Hyung-Char Chan An. Improved Baaming-augmentt algorithms for the multi-option ski rental problem via best-possible competitive analysis. arXiv preprint FrXiv:2302.06332. 2023.
Sandeep Silwal, Sara Ahmadian, Andrew Nystrom, Andrew McCallum, Deepak Ramachandran, and Seyed Mehran Kazemi. Kwikbucks: Correlation clustering with Sheap-weak and expensive-strong signals. In The Eleventh International Conference Learning Representations, 2023, URL htttp:://ppenrevier.. net/ htt./formmmmi dor.miidd-
Häkan Sundell and Philippas Tsigas. Fast and lock-free concurrent priority queues for multi-thread systems, Journal of Purallel and Distributed Computing, 65(5):609-627, 2005.
Mikkel Thorup. Equivalence between priority queues and sorting. Journal of the ACM (JACM), 54 (6):28-es es, 2007.
Dominique Tschopp. Suhas Diggavi, Payam Delgosha, and Soheil Mohajer. Randomized algorithms for comparison-based search, Advances in Neural Information Processing Systems, 24, 2011.
Peter van Emde Boas Preserving order in a forest in less than logarithmic time and linear space. Information processing letters, 6(3):80-88) 82,000222111 1977.
Peter Emde Boas, Robert Kaas, and Erik Zijlstra. Design and implementation of efficient priority queue. Mathematical systems theory, 10(1):99-127, 1976.
Jean Vuillemin. A data structure for manipulating priority queues. Communications of the ACM, 21 (4::309-315, 1978.
Fabian Wauthier, Michael Jordan, and Nebojsa Jojic. Efficient ranking from pairwise comparisons. In International Conference on Machine Learning, pages 109-117. PMLR, 2013.
J. W. J. Williams. Algorithm 232: Heapsort. Communications of the ACM, 7(6):347-348, 1964.
Ali Zeynali, Shahin Kamali, and Mohammad Hajiesmaili. Robust (eaming-augmentie dictionaries. arXiv preprint 07X6672402.09687, 2024.
Deli Zhang and Damian Dechev. A lock-free priority queue design based on multi-dimensional linked lists, IEEE Transactions Parallel and Distributed Systems, 27(3):63-6666, 2015.
15

---

Learning-Augmented Priority Queues
Appendix
A Extended related work
Searning-augmenter algorithms Dearning-augmentte algorithms, introduced in [Lykouris and Vassilvtiskij] 2018 Purohit et al., 2018). have captured increasing interest over the last years, as they allow breaking longstanding limitations many algorithm design problems. Assuming that the decision-maker is provided with potentially incorrect predictions regarding unknown parameters of the problem, they are accurate (consistency), while keeping the worst-case performance without advice even if the predictions are arbitrarily bad or adversarial (robustness). Many fundamental online problems
algorithms must be capable of leveraging these predictions
were studied in this setting, such ski rental [Gollapudi and Panigrahi, 2019/Anand Annad al. 2020
Bamas et al. 2020 Diakonikolas et al., 2021 Antoniadis et |0.1 Maghakkan et al. 2023) Shinn
et al. 2023 scheduling [Purohit al. [2088] Merlis et al. [2033]
Lassota et al.] [023 Benoman
and Perchet 2024b), matching (Attoniadis et al. 20.0 et al.
[202]] Chen et al. 2022]. and
caching Lokkuuis and Vassilvtiskii 2018 Chlkedowski et al. 2021 Bansal al. [2022 Antoniadis
cet al. 2023b a Christiaanoo et al. 2023]. Data structures can also be improved within this framework.
However, this remains underexplored ored compared to online algorithms. The seminal paper by Kraska
ct al.
2018 shows how predictions can be used to optimize space usage. Another study by [Lin
al. 2022] demonstrates that the runtime of binary search trees can be enhanced by incorporating predictions of item access frequency. Recent papers have extended this prediction model to other data structures, such as dictionaries Zeynali et al. 2024) and skip lists (Fu et al. 2024]. The prediction models we study deviate from the latter, and are more related to those considered respectively in [Bai and Coester [023] for sorting, and [McCauley et al. 2024) for online list labeling. An overview of the growing body of work on learning- augmented algorithms (also known as algorithms with
predictions) maintained at [Lindermayr and Megow 2022
Dirty comparisons
The dirty and clean comparison model is also related to the prediction querying model, gaining a growing interest in the study of learning-augmented algorithms, where the decision- maker decides when to query predictions and for which items [Im et al. 2022] [Benomar and Perchet
2024a Sadek and Elias 2024]. particular, having free-weak and costly-strong oracles has been studied in (Silwal et al. 2023] for correlation clustering, in [Bateni et al. [2023) for clustering and computing minimum spanning trees in metric space, and in [berle et al. 2024) for matroid optimization. Another related setting involves the algorithm observing partial information online, which it can then use decide whether query costly hint about the current item. This has been explored in contexts such as online linear optimization [Bhaskara et al.) 2021 and the multicolor secretary problem [Benomar et al. 2023
Priority queues Binary heaps, introduced by Williams 1964), are one of the first efficient im- plementations of priority queues. They allow FindMin in constant time, and the other operations in O(log n.) time, where n is the number of items in the queue. Shortly after, other heap-based implementations with similar guarantees were designed, such as leftist heaps [Crane 1972 and randomized meldable priority queues [aambin and Malinowski 1998). A new idea was introduced in (Vuillemin 1978 with Binomial heaps, where instead of having single tree storing the items, binomial heap is collection of (log n) trees with exponentially growing sizes, all satisfying the heap property. They allow insertion in constant amortized time, and O n) time for ExtractMin and DecreascKey. A breakthrough came with Fibonacci heaps [Fredman and Tarjan 1987] which allow all the operations in constant amortized time, except for ExtractMin, which takes O n) time. It was shown later, in works such as [Brodal 1996 Brodal et al.] 2012), that the same guaran- tees can be achieved in the worst-case, not only amortized time. Although they offer very good theoretical guarantees, Fibonacci heaps are known to be slow in practice [Larkin al. 2014 Lewis
16

---

2023], and other implementations with weaker theoretical guarantees such as binary heaps are often preferred, We refer the interested reader to the detailed survey on priority queues by Brodal 2013).
Skip lists A skip list [Pugh] 1990] is a probabilistic data structure, based on classical linked lists, having shortcut pointers allowing fast access between non-adjacent elements. Due to the simplicity of their implementation and their strong performance, skip lists have many applications (Hu et al., 2003] Ge and Zdonik, [2088] Basin al. 2017]. particular, they can be used implement priority queues [Rönngren and Ayani 1997]. guaranteeing in expectation a constant time for FindMin and Mx,ractMin, and Olog a) time for Insert and DecreaseKey. They show particularly good performance compared to other implementations in the case of concurrent priority queues, where multiple users or machines can make requests to the priority queue (Shavit and Lotan 2000 Lindén and Jonsson| 2013
Zhang and Dechev 2015).
B
Heap priority queues
B.1 Exponential search and randomized binary search
The insertion algorithm we propose for binary heaps combines the classical exponential search and our randomized adaptation of the binary search algorithm. We provide brief overview of the exponential search and its runtime, followed by an analysis of the runtime upper bound for our randomized binary search algorithm.
Exponential search. The exponential search of a target in a sorted list L = (VI,.... Uk) starting from index í E [k] consists in first comparing u to us, and if v; < u then u is compared to U1+1, 11+22 Ui+4,... until an integer E is found satisfying U/-2" < u S 0442r-1, a binary search is then conducted between indices + 2 and i + 2 to find the position of u. If the first comparison shows instead that u < Ut, then u is compared to 1;-1, 2;-2, U;-4..... Denoting by j the true position of u in L, the exponential search terminates in O i - jI) time.
Randomized binary search (RBS). Consider sorted list L = (Vi...., Uk) E Uh and target U. When the search of u in L is reduced the sub-list (Vs,.... ... Uj). RBS samples an index
È Uniform (fi (fi+T ["
(1)
if u vy then algorithm terminates, if u U2 then the search is reduced to the sub-list (oi,... Ut-1) 1). otherwise is reduced to (#'+1....,,)) 0y)) This process iterates until the obtained sub-list has a size of the position of is then immediately deduced by comparing it to the single element in the sub-list.
Lemma B.1. RBS in a list of size k terminates in Olog k) time with probability 1.
Proof. Let us denote by S, the size of the sub-list which the search reduced after t steps, and T = min(t 2 1 : S. = 1}. For convenience, we consider that S. = 1 for all t > T. It holds that So = n, and for all 2 1, S. j - + > then
S max(j f,6 و - i- 1 0
= s
On the other hand, if S, then S 1. We deduce that S S max(1, S. with probability hence S, < max(1, (3 for all & 1. Therefore, holds almost surely that
T < [log4/3 k1
B.2 Proof of Theorem 2.1
Proof. The algorithm described in Theorem 2.1 runs RBS with dirty comparisons obtaín an esti- mated position F(u, L) of u in L, then it conducts a clean exponential search starting from F(u, L) to find the exact position r(u, L). Lemma B.I guarantees that the dirty RBS uses O(log k) comparisons, while the clean exponential search terminates in expectation after Olog [r(u, L) F(u, I.)) compar- isons. Therefore, for demonstrating Theorem 2.1 it suffices to prove that Bllog (r, L.) - F(u, L)]] = Olog (uu, L)).
17

---

To lighten the expressions, we write instead of n/u, L) in the rest of the proof. Let (do. (1. and Je) the indices delimiting the sub-list of which the RBS is reduced after steps for all 1. 2 1. Denoting by 1* + 1 the first step where a dirty comparison is inaccurate, it holds that F(u, L.; r(u, I.) E [ ). Indeed, the first L" dirty comparisons are accurate, thus the estimated
and the true positions of in I. are both in ( }. Therefore, [r(u, L) F(u, L.] S S-- 1, where S = - is + 1 the size of the sub-list delimited by indices (4t, Je). which yields
log ru,, L) F(u, L) S log(S:-).
(5)
We focus in the remainder on bounding E [log S,- ]]. For this, we use a proof scheme similar to that of Lemmas A.4 and A.5 in Bai and Coester [2023]
B[ S.,) )1 B[[log(S,.)]]
Σ m21
m Pr( (og(.))) m)
2
$ log(n) + 1)
Σ
m PPr[[og(Ss-]] =m),
(6)
m [o](n+1)]
and for all m 2 1, we have that Pr([lo((S:-)) m) Pr(St- E (2m-1,2tm)
Pr(S: E (2th-1 ,2th 1pmm1,2"1,0 t²)
Pr(S, E (2" Pr(l = t" Sr E (2m-1,2"")
In the sum above, for any t 2 I, the probability that is the probability that the next sampled pivot index & is in the set Fuu, L) = (u E L: 1uu 2 v) + 1 < v)}, which has cardinal r7. Thus
Pr(t= t" 1 = Pr(4, E F(u, 8i) = #(F n (i., (i.,.....el)
jct)
$ 7
S
S.
It follows that
Pr([log(S:)]] = =m) S
1
Pr(S, E (2m--1 2
2m-1
"
E
F 1: (2m-1 2n]]]
2m-1
37
2
where the last inequality an immediate consequence of the identity S S S1+1 proved in Lemma B.I, which shows in particular that S < S,/2, i.e. the after at most 3 steps, the size of the search sub-list is divided by two, hence (S:), falls into the interval (2m-1 2m] at most three times. Substituting into (6) gives
Ellog S.. log(1) + 1) 3n
2m-1
m= (1)+
log
log(n + 1 3n O
r
O(log v)
Therefore, by (5), the expected number of comparisons used during the clean exponential search is at most O ru, L) L]] O(log n), which concludes the proof.
18

---

B.3 Proof of Theorem 2.2
Proof. Consider binary heap Q containing n elements, with positions randomly filled in the leaf level. Even with this randomization, Q is still balanced, and the length of any path from an empty position in the leaf level to the root has size ( n.). Denoting by L the random insertion path chosen in Algorithm[] [ constructing I. and storing it requires (log n) time and space. By Theorem 2.1 the randomized search in Algorithm| 1 uses Ollog log n) dirty comparisons, and the exponential search uses an expected number of O llg (7u, L)]) clean comparisons. Inserting u and then swapping it up until its position does not use any comparison and requires a Ollog n) time. Therefore, to prove the theorem, it suffices to demonstrate that lEllog 17 L)] (log log r7( 2)).
We assume that the key be inserted can be chosen by an oblivious adversary, unaware of the randomization outcome. This means that the internal state of Q remains private at any time. Let F(u, 2) {u Q 1(u 2 v) * 1(u < 8)}, which has a cardinal of 17(u, 2). Enumerating the binary heap levels starting from the root, each level E except for the last one, denoted fmax. contains exactly 2 elements vi...., 12--1. . key of in level é has a probability 1/2"-1 of belonging to
Denoting by ę
I(vf E F(u, 2)), the expected number of keys in belonging to F(u, Q) is
Eln(u, L) = Emaz 2
Emax
2
2
Given that Eier Ei=1
5 (u. 2 < 2 (oog(((u 1)1 - 1, the expression above is maximized under this constraint for the instance ? = 1l S [log(n(u, Q) + 1)1). Therefore,
2
Ein(u, L) - Σ 2
= (,(, Q) + +)]
Finally, Jensen's inequality and the concavity of log yield Bllog L)] S log E/n(u, L)] = Olog log n(u, 2))
which gives the result.
C
Skip lists
C.1
Unique keys in the priority queue
The keys of the priority queue can be considered pairwise distinct by grouping elements with the same key together in a collection, for example, a HashSet. This collection can be accessible in O(1) time via the key using HashMap. When a new item with priority is to be inserted, the algorithms first checks if the key u is already in the priority queue, if that is the case then x is simply added to the collection corresponding to u in ((1) time. Otherwise, the key must first be inserted into its correct position.
With such implementation, when ExtractMin operation is called, if multiple elements correspond to the minimum key, then the algorithm can for example retrieve an arbitrary one of them, of the first inserted one, depending the use case.
C.2 Expected maximum of i.i.d. geometric random variables
Before presenting the insertion algorithms in the three prediction models, we present an upper bound from (Eisenberg] 2008) on the expected maximum of i.i.d. geometric random variables with parameter p. This Lemma will be useful in the analysis of our algorithms, as the heights of elements in the skip list are i.i.d. geometric random variables. The following Lemma is an immediate consequence of
Lemma C.1 (Eiseebergg] 2008)). If XI...., are i.i.d. random variables following a geometric random distribution with parameter then, denoting by 1 - p, it holds that
1 m
E mmaa X,] < 1 + xE[m]
Olog m).
log (1/g)
k
k=1
19

---

C.3 Pointer prediction model
Proof of Theorem 3.7 The key w found at the end of the algorithm is the processor of u in Q.
Inserting next to w only requires expected ((1) time. Thus, we demonstrate in the following that
Algorithm 2 starting from a key Vj E 2, finds the predecessor of u in Ollog r(w;)) - r(u)l) expected time, where r(e) denotes the rank r(u, Q) of in Q. In particular, for v Pred(u, 2), obtain the claim of the theorem.
We assume in the proof that Uj < i.e. the exponential search goes from left to right. Let h" h"(y,, u) be the maximum height of all elements in Q between u and vi
h" (1/, u) max(h(v) u Q such that U/ 2 25 u)
The number of elements between 8i and u, with vi included, is Ir(u) - r(v;) ) 1, and the heights of all the elements in Q are independent geometric random variables with parameter p. thus Lemma C.I gives that B[h" (uy, u)] = Ollog [r(u)- r(w;))).
The key w" found at the end of the Bottom- Up search is the last element, going from ūj to u, having height of h" (1y, Indeed, in the Bottom-Up search, whenever the algorithm reaches new key, moves to the maximum level to which the key belongs, the height of w" is therefore necessarily the maximum height of all the keys between by and w", i.c. h(w*) = h [ey, w*). Since the Bottom- Up search stops at key w", then Next(u' (w", .hw=()))) )) > u, which means that there is no key in Q between w" and u having height more than h(w") 1.
The number of comparisons made in this phase is therefore at most the number of comparisons needed to reach level h" (1z, u) + starting from 1 using the Bottom-Up search. We consider the hypothetical setting where the skip list is infinite to the right, the expected number of comparisons to reach level h [wy, u) + 1, in this case, an upper bound
the expected number of comparisons needed in the Bottom-Up phase of Algorithm 2 as the algorithm also terminates if the end of the skip-list is reached. Let (()) be the expected number of comparisons made in the bottom-up search to reach level l in an infinite skip list. After each comparison made in the bottom-up search, it is possible to go at least one level up with probability p. while the algorithm can only move horizontally to the right with probability 1 This induces the inequality
T(O) 1 pT - p)T(().
which yields
1 T(E 1 T(f)
p
Given that T(1) = 0, we have for l 2 1 that T(e) < 8-1 and we deduce that the expected
p
EJa" [1,"(u,)")
number of comparisons made by the algorithm during the Bottom-Up search is at most O(log (r(;)) - ru))).
P
In the Top-Down search described in the second phase, the path traversed by the algorithm is exactly the inverse of the Bottom-Up search from the predecessor of u to w². The same arguments as the analysis of the first phase give that the Top-Down search terminates after Ollog (r(e,) r(4))) comparisons in expectation, which concludes the proof.
C.4 Dirty comparison model
Proof of Theorem rate
3.2 Let Flu, Q) the set of keys in Q whose dirty comparisons with u are inaccu-
Flu, Q) (u e 1uu 2 v) + 1(u < v)}
The prediction error 77(u, Q) defined (2) is the cardinal F(u, Q). Let
h (F 2)) max(hiv) : E F(u, 2))
be the maximal height of elements in F(u, Q). The search algorithm Search( Q u) with dirty comparisons starts from the highest level at the head of the skip list, and then goes down the different levels until finding the predicted position of u. This is the classical search algorithm skip lists, and it is known to require (logg)) comparisons to terminate. This can also be deduced from the
20

---

analysis of the exponential search described in Algorithm 2 as it corresponds to the Top-Down search starting from the head of the skip list.
Before level het (F(u, 2) is reached in Search( w), all the dirty comparisons are accurate. De- noting by of the last key in 2 visited in level higher than (F[(,,, 2)) during this search, and v" = Next(ee Q, v', ht (F(u, 2) it holds that both keys V and w are between e' and v", and there is no key in between o' and v" with height more than h" (F(u,, 2)) 1.
In particular, the maximal key height between v and w is at most h (F(,,, 2)) We showed the proof of Theorem 3.1 that the number of comparisons and runtime of ExppSerchInsertioon Q, 1j u) linear with the maximal height of keys in Q that are between v and u. Using this result with i instead of bj gives that ExpSearchInsertionn Q, tù, u) finds the position of using Olh 2)) clean comparisons. Finally, since lt" (F(u, Q)) is the maximum of a number 77 Q) of i.i.d. geo- metric random variables with parameter p, Lemma C.T gives that
Eihh (F(u, 2)) O(log nuu, 2))
which proves the theorem.
C.5 Rank prediction model
To leverage rank predictions, explained in Section 3.3 tree van Emde Boas 1977].. We describe in the following the structure complexity of vEB trees on [M], and we explain how they can be adapted in the case where N is unknown.
we use auxiliary van Emde Boas (vEB)
C.5.1 Van Emde Boas (yEB) trees
A vEB tree over an interval {i+ 1,....iit m) has root with ym children, each being the root of
smaller vEB tree over a sub-interve fitkym+1,... 2++ (k++1) (0++1)mmm for some k {0, ....... /m- 1}. The tree leaves are either empty or contain elements with the corresponding key, stored together in collection, and internal nodes carry binary information indicating whether or not the subtree they root contains at least one element. Denoting by (mm) the height of a vEB tree of size m, it holds that (m) = H H(mm), which yields that H (mm) = O(log log m), enabling efficient implementation of the operations listed below in Ollog log m) time:
Insert(ar, k): insert a new element x with key k E [m] in the tree, Delete(x, k): Delete the element/key pair (x. k).
Predecessor(k)) return the element in the tree with the largest key smaller than or equal to
Successor(H) (k)): return the element in the tree with the smallest key larger than or equal to ExtractMin() (): removes and returns the element with the smallest key.
Other operations such as FindMin, FindMax, Lookup(k) supported in O(1) time. These runtimes, however, require knowing the maximal key value m from the beginning, as it is used for constructing Tm.
C.5.2 Dynamic size vEB trees
If the maximal key value R is unknown, we argue that the operations listed above can be supported in amortized Olog log R) time. Given a vEB tree Tm of size m, a new key E {m +m++b I,..., 2m} is to be inserted, we construct empty vEB tree T2m of size 2m in (m) time, then repeatedly extract the elements with minimal key from Tm and insert them in T2m with the same key. Each Extract operation in Tm and insertion in T2m. requires (log log m) time. Therefore, constructing Te... and inserting all the elements from Tm takes (mm log log m) time.
This observation can be used to define vEB with dynamic size. First, we construct a vEB tree with an initial constant size Rg. If at some point the size the vEB tree is m > Ro and a new key > m is to be inserted, then we iterate the size doubling process described before until the size of the vEB tree is at least ls. any time step, denoting by the maximal key value inserted the vEB tree, and letting > 1 such that 2 Ro < R < 2 Ro. the size of the tree has been doubled up this step i
21

---

times to cover all the keys. The total time for resizing the vEB tree is at most proportional to
2 Ro log log(2 Ro) Ro)
Σ 2d
Ro log log R
1=0
- 2' Ro log log l
x 2R log log It
Therefore, if N is the total number of elements inserted into the vEB tree and R the maximum key value, we can neglect the cost of resizing by considering that each insertion requires an amortized time of (((1 - N if R O(N), then all the operations run in Oloo log N) amortized time.
Rt log log R). The runtime of all the other operations is Ollo log R). In particular,
C.5.3 Priority queue with rank predictions
Consider the setting where is unknown and all the predicted ranks, revealed online, satisfy R(u,) O(N). The priority queue we consider is skip list Q with auxiliary dynamic vEB tree T. For insertions, we use Algorithm 4 For ExtractMin, we first extract the minimum Umin from Q in ((1) time, then we delete it from the corresponding position R( ((min)) ) in T in (log log N) time. Deleting an arbitrary key u from Q can be done in the same way, by removing it from Q in expected 0(1) time and then deleting from the position R(()) in T in Oloog log N) time. Thus, as in the other prediction models. DecreaseKey can be implemented by deleting the element and reinserting it with the new key, which requires the same complexity as insertion, with an additional Ollog log N) term.
We will prove that the priority queue described above yields the claim of Theorem 3.3 We assume that the keys ....... UN are inserted in this order. For all t E [N], we denote by Q T the set of keys in the skip list and the set of integer keys in the dynamic vEB tree right after the insertion of uy with the keys in Q' or T Note that, due to eventual deletions, the sizes of Q' and T can be smaller than I.
Following the definition of the rank in (T. for all i, 2,L E [N], we denote by r(u, Q') the rank of u; in Q', and r( r(R(u:), T³) the rank of R(us) in T The following lemma shows that the absolute difference between the two previous quantities for any given i, t at most twice the maximal rank prediction error.
Lemma C.2. For any subset I c [N], it holds for all i E that
Ir(u,,uuhee (uslse)) - r (R(u)), (R(u,) < max 17 (uz) JE[N]
Proof. Let
tEl max [r(ue, (uybse)) r( (R(u.), (R(s)))))))
A, max [C[M]
(7)
and let C [N] for which this maximum is reached. We assume without loss of generality that I = [m]. For all [N], let
-- = {ugJsEts
=
max |r(u;, - (f()))((()))+))) sE(s]
To simplify the expressions, we denote by r = r(u, ②³) and P. = r)((((() T.) for all (s, i) E [N]2. We will prove that A A. for all E (m,.... .J. By definition of A., it holds that
A. 2 A for all 8, it remains to prove the other inequality. It is true for m by definition and m. Now let s E (m,..., N 1} and assume that A A., i.c. there exists i < s such that |r? - P = A.. Assume for example that P. = r? A..
If Ua+1 < Ui then s+1 < ++1 and r ++1 = rf + 1. By definition of A., it holds that
petl < r A. 2 0+1 - + A. = + + = Ff
22

---

This implies necessarily that R(u,+1) I R(us), and therefore
= s+1 p 13 + 1 r. + 1+ A. =
+
which gives that A ++1 2 p1 +1 = A..
If Ug++ Uie then ++1 r and pT+ + p.. thus A -
2 P. p--- -r A..
If Us+1 = u, then
s+1 = n = r3 + 1. On the other hand, if R(u,+1) s R(u;) then s+1
pe+1 otherwise F F7 In both cases, it holds that
A 1 2 max P r4th 1t1
Pat =
( 1) (r]
A.
The same proof can used for the case where r = p + A.. Therefore, we have for all s e [m...... .N that A. = A. In particular, for s = N, observing that r(u, ².²) = R(u;) for all
i [N]. we obtain
A. max R(u,) - r ((A(u.), RE[N]
Let us denote by Vmmx max 1f A (u,) the maxinuum rank prediction error. We will prove the following that
Ei [N] R(u,) r r(R(),), Jー S 2
With the assumption that the keys [u:]e[N] are pairwise distinct, the ranks (R(u)))E[[) form permutation of [N].
Given that R((x)) - R(uu)) S Trmex for all k E [N], it holds for any i, E [N] that
A(w,) & R(uu)) = R(u,) T I R(us) + A
R(u,) < R(u,) 2m
hence, given that TN [[((u;)) and by definition
① of the rank r ((((us); TN), we have
r(Nl(us), = # E [N] R(u, < R(u;)}
S # E [N] R(u,) R(u,) 2n
# E [N]
R(u:) م
(9)
= min(N, R(w:) + 2
- R(mx) + 2
(10)
where Equation i [N] that
9
holds because (R(())) is permutation of [N]. Similarly, have for all
R(uy) R(u+) 2mmax
R(ug) A S R(ws) 7max
R(u,) < R(uu).
and it follows for all i E [N] that
r(fi(ui), TN)
#1 [N] R((,y) A(v+)}
2 #li E [N] R(u,)) S R(u;) - 21
= #(k E [N] & R(u;)) 2
=max (0, R(u,) 2
R(uu)) - 2
(LI
From 10 and
we deduce that
Vi [N] R(4,) - r(f((u)). < 2m
Combining this with and yields the wanted result.
23

---

Proof of Theorem 3.3
Proof. When a new key u, is to inserted, it is first inserted in the dynamic vEB tree T with integer key R(u)), and its predecessor w in T is retrieved. These first operations require Ollo log N) time. The position of u, in Q' is then obtained via an exponential search starting from w. which requires (log (u, Q*) r(ū, 2*)l) expected time by Theorem 3.1 Finally, inserting u in the found position takes expected (11) time.
For any newly inserted element, by accounting for the potential future deletion time via Extract the moment of insertion, we can ensure that all ExtractMin operations require constant amortized time. This approach results in only an additional (log log N) time for insertions.
Therefore, to prove Theorem 3.3
we only need to show that log [r(u,, Q+) r(ū; 2
(log maX (u:)). Since is the predecessor of u, in T it holds that r(N(,,), T) (r(R (), r R( T) + 1}. the first case occurs if R(us)
R(w)) and the second if
R(u,) R(w). Using this observation and Lemma C.2 it follows that
Ir(u, 2²) - r(w 2¹)
$ |r(u, ②') - (((()) T3) + (() +r((),
Ir(1))) (((orr(
S 4 max > (1,) 11, JE[N]
and it follows that log |r(,, @²) - r(w, Q*) = OOlog max]e[N][]]] (7) which concludes the proof.
D Lower bounds
priority queue can be used for sorting a sequence A (a<)ve(x) Ut" by first inserting all the elements in the priority queue, then repeatedly extracting the minimum until the priority queue is empty. In settings with dirty comparisons or positional predictions, the number of comparisons required by this sorting algorithm is constrained by the impossibility result demonstrated in Theorem 1.5 of Bai and Coester (2023). We use this impossibility result to prove the lower bounds stated in Theorem 3.4
D.1 Impossibility result for sorting with predictions
We begin in this section by summarizing the setting and the impossibility result demonstrated in Theorem 1.5 Bai and Coester 2023 for sorting with predictions.
Positional predictions In the positional prediction model, the objective is to sort sequence A = (a; (E))) given prediction R2 [n)] of R2 r(a;, A) for all E [n)]. This model differs from our rank prediction model that the sequence and the predictions π = (R; (ie are given offline to the algorithm. Two different error measures are considered in Bai and Coester [2023] but we restrict ourselves to the displacement error vi²² ir(a;, A) R.,, which is the same as rank prediction error all the following, consider that a fixed permutation of [n]. i.e. the predicted ranks are pairwise distinct. For all & 1, consider the following set of instances
cand R, n²) = u
log(n +2) S n
The authors of Bai and Coester 2023 prove that, if S & O(logn), then algorithm sort every instance from cand n with o(nE) comparisons. However, in their proof, they demonstrate a stronger result: no algorithm can sort every instance from I,, (Rt, {) with o(ng) comparisons, where I, (R, {) is the subset of cand R, n²) defined by
I, I,, (R, E) = {A E ut"
max + < {
(12)
8E[n]
24

---

Dirty comparisons in the dirty comparison model, the authors prove analogous result by reduction to the positional prediction model. More precisely, any permutation R on [r]] defines unique dirty order 2 on A given by a 2 aj = R₂ Rg and maX4e[1] "h S maxsg[a] m/ where 7/1 = (a,, A) = # j E [n] (a: <aj) + (a: < aj)). We deduce that
In ( {A uu max log(n: / + 2) { iEin]
(13)
Hence, given the dirty order there is no algorithm that can sort every instance with maXie(n] log(n; + 2) S in o(nE) time.
In the following, use these lower bounds on sorting to prove our Theorem 3.4
D.2 Pointer prediction model
For any permutation π of [rz] and i E [n]. we denote by A = farmnnaae HEM This first elementary Lemma uses ideas from the proof of Theorem 1.3 in Bai and Coester [2023]
Lemma D.I. A permutation π of [ni] satisfying Ra(1) S... S Rz(n) can be constructed in O(n)
time, and it holds for all i E nn) that
(r(e=(), A)-1) r() ATD) 1 ST(i-))
n + RT(1) Ra((-1)-
Proof. The elements of A can be sorted in non-decreasing order of their predicted ranks R2 within O(n) time using bucket sort. Hence, we obtain the permutation
For all i E (2...., n), Ir(an())A4 1F-1) (() 45-1 }]l is the number of elements in A whose ranks are between those of a=(1) and dz(1-1)- This is at most the number of elements in A whose ranks are between those of (x()) and (n(i-1), which is Ra(s) R1(--))- We deduce that
Ir(a=()) (() A7)1 < [T(()) RT(1-1)
< [T7()) - Ri(OO + [Ra(i-1) Rx(i-1)l+ (Bx(0) Ro(i-1)
( + nm/l) + Rm(()) R
where we used the triangle inequality and that Rm(s) 2 Rx(1-1).
We move now to the proof of our lower bound in the pointer prediction model, by reducing the problem of sorting with positional predictions to the design of a Cearnin--augmente priority queue with pointer predictions.
D.2.1 Proof of Theorem
Proof. Assume that there exists an implementation of a priority queue Q augmented with pointer predictions, supporting ExtractMin with O(1) comparisons and the insertion of any new key u with ollog fu, 2)) comparisons. This means that, regardless of the history of operations made on Q, the number of comparisons used by ExtractMin is most constant C, and for any key u such that log(r)(u, Q) +2) I E requires at most E(E) comparisons, where e(-) is a positive function satisfying lime -oo E(E) = 0. We will show that the existence of such priority queue contradicts the impossibility result of sorting with positional predictions.
1, inserting
Let 1 < < O(lgg n), R a fixed permutation of [n]. and an arbitrary instance from the set I, (R, E) defined in (12) Let I be the permutation satisfying the property of Lemma D.I] and consider the sorting algorithm which inserts the elements of A in Q the order given by म. then extracts the minimum repeatedly until Q is emptied. Let denote by Q³ the state of the Q after i insertions.
Upon the insertion of a the algorithm uses Prod(ax()) Qi-1) = az(i-1) as a pointer prediction. By (3) the error of this prediction is
Tan()), Ø²-1) (r(an()) ALT) r(xx AT
25

---

where A = {arts))ee and by Lemma D.1 we have that
(((x(()) -²-1) 1/ + (a(()) Ro(O) Rx(1-1)-
(14)
R is permutation of [n), hence Rxx()= = (1 + 1 by definition of æ. Moreover, A E (E),,, thus max(log(777 2), log (17(3) + 2)) _ ç. and it follows that
log( - + 2) < log log(V + (s) + 3)
< log ( + log log(n +
- 2
where the second inequality is a consequence of log(a + 3) 6 log(a) + log(3) for all a, B 2 2. Therefore, all the insertions into Q require at most (2f =(2E)) comparisons, and the total number of comparisons T used sort most
T S n (25 e(EE) C)
= ng E2E))
+ &
= =(nE)
This means that any instance in I, (5) can be sorted using o(nE) comparisons, which contradicts the lower bound on sorting algorithms augmented with positional predictions.
D.2.2 Rank prediction and dirty comparisons model
In the rank prediction model, the total number of inserted keys is N = n. Denote by 7/: = 7: a, A) for all i E in]. If there is data structure Q not satisfying the lower bound of Theorem 3.4 for positional predictions, then we can use it for sorting A. Let < 5 S O(log n). Similarly to the proof for pointer predictions, if R is permutation of [n). using Q for sorting any instance A E In, (S) requires most 7 = o(nE) comparisons, which contradicts the lower bound learning-augmenter sorting algorithms.
The same arguments, combined with 13 give the result also for the dirty comparison model.
E
Applications
E.1
Sorting
In the case where the algorithm is given offline access to the sequence A = an) to sort and to the rank predictions (R(a:))sejn) we argue that pointer predictions can be used to sort the sequence within O(Eie(m) log(n, 2)).
With offline rank predictions, by Lemma D.1 the algorithm construct permutation æ of [x] satisfying M((r() S .... < ()))) and we showed the proof of Theorem 3.4 in (14), that inserting the elements of A into the priority queue in the order given by then taking each inserted element (r(s) as pointer prediction for the following one ax(i+1)- yields pointer prediction error of
man()) @²-1) 1 + ()(()) + Ru(o Rm(t-1)
for all i E m.. By Theorem 3.1 the runtime for inserting ar(() using this pointer prediction is Olog ((( 11-1)) The total time for inserting all the elements into the priority queue is
26

---

therefore at most proportional to
log (()())) -²-1)+ + 2) -
Σ
log(n (1 + nalo Ra(() -Ra(i-1) + +
im2
log(() +2 + (Ma(()) + +2) + +(ax()) - Rx((-11 + 2))
(og((1((111) + 22 + log(Ta(()) + + log ( - Rz + 2))
S 2
Log(T=(3 + + Σ (Rz()) Roi(i-1)
S 2
log (Tg( + + (2) +n
i=1
0
Σ iEin]
log(n A +2)
The third inequality results from inequation log(a 1000+++970 +++) S log a- 1ot.log.+40 3-g for all a, 3, > 2 2. and the subsequent inequality follows from log(a + 1) S for all a 2 0. Finally, complete the sorting algorithm, the minimum is repeatedly extracted from the priority queue until is it empty, and each ExtractMin only takes (1) time in the skip list.
E.2 Dijkstra's algorithms
We give in this section more details on the complexity of Dijkstra's 's algorithm using our priority queue augmented with rank predictions.
Consider any priority queue implementation, having a time complexity Tiusert for insertion, MixtractMin for extracting the minimum, and T DecreaseKey for decreasing the key of an element. There are two possible implementations of Dijkstra's algorithm with priority queues. The first one only uses the operations Insert and ExtractMin, and the maximum number of inserted elements is 1, which yields a complexity of (mmTinsert + miT ExtractMin. The second implementation, using also the DecreaseKey operation, yields a complexity of O(n(Tinsert + TExtractMin) + m DeTTeaccceeeey ).
Recalling that the number of edges at most n² using a binary heap in any of both implementations gives total runtime of (m log n)). On the other hand, using a Fibonacci heap in the second implementation yields runtime of On log n + m).
In the rank predictions model, we consider that the priority queue only uses Insert and ExtractMi operations, hence we use the first implementation. Denoting by [deltefm) the m distinct keys that are inserted, these keys are only revealed online to the priority queue. If they tions (R(d:)); of their ranks, then each insertion requires Ollog log m + log(maxee]m+a) [R(d.) R(d,)]+ 2)) amortized time and (log max +1] [{((,)) - R( d2 )) comparisons, while extractions only require constant amortized time each. The total runtime is therefore
accompanied by predic-
(m log log + m log max [R(d.) R(d.)))
(E[m+1]
and the total number of comparisons is O(m (o( [R(da) R(())))).
F
Additional experiments
F.1
Sorting
The problem of sorting with similar prediction models have been studied in Bai and Coester 2023 hence we numerically compare sorting using our
priority queue (LAAP)) with their sorting algorithms. To run their algorithms, used the code provided by Bai and Coester
27

---

2023 in their paper. We give here additional experimental results for the class and the decay setting, for smaller values of n.
1000
18000
LARQ puoiicion
(Ncompurisons))
101
10'
10a
10/
0.0
0.2
0.8
1.0
0.0
0.2
0.4
0.6
0.6
1.0
0.0
0.4
0.6
0.8
(Aclasses
(#classes)Mn
(#classos
Figure 6: Sorting with rank predictions in the class setting, for {1000, 10000, 100000).
EAPO
(fcomparioonsh)
8-
10.0
Double Doudl-lllnne
7.5
Baury
50
2.5
0.4
(
(ftimestees)/(in./n
(ftimesttess((e//))
Figure 7: Sorting with rank predictions in the decay setting, for n E (1000, 10000, 100000).
F.2 Dijkstra's algorithm
Considering the same experimental setting presented in Section 5 Figures Band9show the obtained results for the cities Brussels, Paris, New York, and London, which have. The numbers of nodes n and edges m in each city graph are indicated in the figures.
Brussels: 1380 2580
Parts: 9559,m 18400
New York: -5326.m 138547
London:
128924, 300612
LAfC mokerce
(#comparisonsl)
12
Piamert
14
00
05
04
00
64
66
0.8
1.0
65
66
06
05
(#classcsVVe
(Pclassesila
(Rolassos)nn
(#olassosiVn
Figure 8: Dijkstra's algorithm on city maps with class predictions
Brussels: At 13 25801
Paris: - 9559 uu 18400
New York: a - 55326, as 139547
London: x 128924. as 300012
14-
(Ncommpatioom W
10
(ftimestepsjdn
[#timesteps
(Ptimesteps
(*timesteps@a
Figure 9: Dijkstra's algorithm city maps with decay predictions
28

---

Simulations on Poisson Voronoi Tesselations We also evaluate the performance of Dijkstra's algorithm with our LAPQ on synthetic random graphs. For this, we use Poisson Voronoi Tessellations (PVT), which are commonly used random graph model for street systems Gloaguen et al. 2006).
Gloaguen and Cali 2018), Benomar al. [022a
PVT's are random graphs created by sampling an integer N from Poisson distribution with parameter 2 1. Subsequently, N points, termed "seeds," are uniformly chosen at random within a two-dimensional region I, typically [0, 1j2. A Voronoi diagram is then generated based on these seeds.
This process results in a planar graph where edges represent the boundaries between the cells of the Voronoi diagram, and the nodes their intersections. For I [0, 1]2 , the expected number of nodes this construction is n.
Figure TO provides visualization of PVT with 100.
Figure 10: PVT with 100
We present the results in the class and the decay settings respectively in Figures IT and 12 Similar to previous experiments with Dijkstra on city maps, these figures illustrate how the number of compar- isons decreases when the LAPQ is augmented with node rank predictions or with the corresponding dirty comparator. We compare them with the number of comparisons induced by using a binary or Fibonacci heap, as well as with the number of comparisons of the LAPQ augmented with key rank predictions.
PVT. N = 1000
PVT. -=
=5000 5000
PVT: 10000
20-
16-
L.AQ diry compartenne
LAPQ nnk prodetom:
(#comparisons))
14
Binary
heap
13
12
8-
10
6
0.0
0.2
04
0.6
1.0
0.0
0.2
0.4
0.6
0.8
0.0
0.2
0.6
1.0
(#classes)/n
(#classes)/n
(#cllases)/n
Figure 11: Dijkstra's algorithm on Poisson Voronoi Tesselation with class predictions
PVT: 1000
PVT: 5000
PVT: 10000
LARO protcion
LAPQ ougaabo
LAPQ rech prdlsann
(fccomaarioons)
Disay hoap
Ritsee boup
8-
7-
3-
15
(#timestops//a
(#timesteps)//
(#timesteps)/a
Figure 12: Dijkstra's algorithm Poisson Voronoi Tesselation with decay predictions
The same observations regarding the performance improvement can be made, as in the previous experiments with city maps. However, in PVT tessellations, the performance of the LAPQ with key rank predictions surpasses even that of perfect node rank predictions. This due to the PVTS' having more uniform structure across space.
29

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract indicates the scope of the paper: cearning-augment algorithms, and describes the particular problem consider
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: We discuss the difficulties we faced for designing dearning-augmenter binary heap. For leaming-augmented skip-lists, we discuss the limitations and possible improvements in the rank prediction model.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
30

---

Answer: [Yes]
Justification: for each theoretical result, all the needed assumptions are stated. The full proofs are provided in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proof' in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: we give full details on our data structure implementation, and all the details (instances, libraries) needed for reproducing the results precised in the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
31

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
The full implementation of the learning-augment priority queue is given in
the supplementary material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/
oolicy for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
//nips.ccpublle wwwppppgpuuiiieeeep /etii///uuide//oeeuuubiiiii SroodeSubiissi.e ssiiiiolcccy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The setting is fully described in the experiments section.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: standard deviations are reported all the figures.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for
example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
32

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Our figures show the number of comparisons used in each experiment. The computer resources are not relevant.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental rums well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics htttps://neurpp::::: http://ewerrppscccpp.leeeeeeeeee wttpblic//thissuuutiiee
Answer: [Yes]
Justification:
Our paper respects the Code of Ethics or NeurIPS.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No. they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
This paper presents foundational/theorrtical work in the field of learning- augmented algorithms. We do not feel that any potential societal consequences of our work must be specifically highlighted.
Justification:
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
33

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question: Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer:[NA]
Justification: learning-augeen augmented algorithms, in general, pose no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We partially use existing open source code, which we clearly cite.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in package should be provided. For popular datasets, paperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
34

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do not release any new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not include such experiments.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not include such experiments.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
35


Reviews:
[{"review_id": "jkIIztaLxY", "reviewer": "Reviewer_ZmGR", "summary": "The paper considers designing data structures for priority queues that accept predictions / advice to improve the time complexity of common queue operations. The paper considers three different models of predictions - (i) dirty comparisons : cheap but possibly inaccurate comparisons are available. Goal is to utilize these cheap dirty predictions to reduce the reliance on expensive true comparisons; (ii) pointer predictions : predicted position of the predecessor of a key in the queue. (iii) rank predictions : predicted rank of the key in the universe of all keys.\n\nThe paper considers two priority queue implementations. (i) A binary heap is a simple structure that supports all priority queue operations in time O(log n). In particular, since inserting a new element involves inserting it at the correct position in a root-to-leaf path of length log n, it can be done via O(log log n) comparisons (but O(log n) time). The authors show that by using dirty comparisons instead insertion can be performed in O(log n) time using O(log log n) dirty comparisons and O(log log \\eta) clean comparisons (in expectation) where \\eta denotes the prediction error. The algorithmic ideas here are rather standard and unsurprising.\n(ii) The second implementation considers skip lists - a probabilistic data structure that supports insertion in expected O(log n) time (and ExtractMin in O(1) time). In presence of predictions, the authors provide a new insertion algorithm that reduces the expected insertion time ( or #clean comparisons) to O(log \\eta) where \\eta is the corresponding error measure. Similar results are obtained for rank predictions.\n\nFinally, the paper shows almost tight lower bounds in all models.", "questions": "N/A", "limitations": "Yes", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The algorithms are very clean and easy to follow. The paper is well-written and the main ideas are readily accessible.\n- Priority queues are a fundamental data structure and improving their performance via learning augmentation is a good contribution - e.g. prior results on learning augmented sorting are now simple applications.", "weaknesses": "Algorithmic techniques introduced are rather unsurprising and are mostly a collection of well known ideas", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive feedback and for the time and effort spent on our submission.\n\n**Weakness.** \nThe intuitions behind some algorithmic ideas are indeed inspired by previous work, and we highlighted these connections as much as possible to make the paper and algorithms easier to understand. Given the efficiency of our algorithms, we believe that their simplicity can also be viewed as a strength rather than a weakness, although we understand the reviewer's perspective as well. However, the paper introduces several novel ideas. For instance, we demonstrate how to effectively use a van Emde Boas (vEB) tree to reduce the problem with rank predictions to the design of a priority queue within a finite universe, and how to handle the prediction errors in the subsequent analysis adequately.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "B4UsnyNCs8", "reviewer": "Reviewer_7XCi", "summary": "The authors in this paper propose a learning-augmented priority queue data structure which takes advantage of the inaccurate predictions to facilitate the operations. Three different prediction models including dirty comparisons, pointer predictions, and rank predictions have been explored and discussed. The authors provide theoretical guarantees as well as empirical analysis in the paper, showing the superiority of their method.", "questions": "I have listed my concerns and questions in the [Strengths And Weaknesses] section.", "limitations": "I have listed my concerns and questions in the [Strengths And Weaknesses] section.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1) The authors propose an interesting learning-augmented data structure by taking advantage of the predictions even when the predictions are not accurate. For the implementation wise, skip listed is used to overcome the inefficiency of the sorted linked list.\n\n2) In addition, the authors have explored three different predictions and provide theoretical analysis to each one.\n\n3) The authors have also discussed the potential applications of the proposed learning-augmented data structure and compared the performance with the SOTA method.\n\n4) The authors have conducted numerical experiments and compared the performance with the SOTA method to show the superiority of the proposed learning-augmented priority queue.", "weaknesses": "1) For the comparison, the authors have compared their proposed priority queue with two traditional heaps. I found there is an advanced learning-augmented data structure in ref1, I am wondering how the proposed method would compare with that learning-based data structure.\n\n2) Is there a threshold of the \"inaccurate\" prediction? For example, if after some threshold, will this proposed data structure be crashed?\n\n3) It would be great if the authors could give more details about the experiments such as what is the scale of the experiments and how the model is set up.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We express our gratitude to the reviewer for their feedback and insightful comments. We address below the weaknesses they have raised.\n\n### Weaknesses\n* **Comparison with prior learning-augmented algorithms.** We are uncertain about the specific data structure the reviewer is referring to and would appreciate a more precise reference. In any case, our work is the first to implement learning-augmented priority queues, making it difficult to compare directly with other data structures unless they support the same operations. However, we have compared the performance of our data structure for sorting, which is one possible application among many others, with previous learning-augmented sorting algorithms (Double-Hoover and Displacement Sort) as detailed in Sections 4 and 5. \n* **\"Threshold of inaccurate predictions\".** Could the reviewer give more clarifications on this question, in particular what is meant by \"crashed\"? Note that $\\log \\eta$ is at most $\\log n$, hence the complexity of our learning-augmented priority queue is always at most that of a standard priority queue not using predictions, up to a constant factor.\n* **Details about the experiments.** For sorting, Figure 2 is obtained with $n=10^5$ as mentioned in the corresponding caption. For Dijkstra's algorithm, the number of nodes $n$ and the number of edges $m$ are indicated on each figure. More details about the setup, as well as additional experiments with different scales for both sorting and Dijkstra's algorithm can be found in Appendix G. If the paper is accepted, we will use the additional page to expand the experiments section with supplementary material from the appendix.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tb2UOHjCrO", "reviewer": "Reviewer_unQV", "summary": "The paper studies various beyond worst-case models for priority queues, a fundamental data structure. A learning-augmented viewpoint is taken and the authors comprehensively study three different natural prediction models: dirty/clean comparisons where some comparisons between items maybe in correct, pointer predictions that allow us to index into the predecessor of an element in a data structure, and rank predictions where the rank of an element among a set of elements is noisily given. \n\nFor each prediction model, the authors improve upon classical algorithms which implement priority queues. For example with pointer predictions, one can insert elements in time proportional to the log of the error, compared to the classical $O(\\log n)$ time (using skip lists). A similar result is shown for rank predictions, where a clever idea of reducing rank predictions to pointer predictions using an auxiliary vEB tree. Results for other settings such as sorting using predictions is also given as corollaries of their priority queue data structures, which matches and extends prior work.\n\nThe authors complement their upper bound with lower bounds, showing that for instance that in their dirty/clean comparison model, they obtain the optimal number of clean comparisons used for the extract min operation.", "questions": "What does 'randomly filled positions in the leaf level' mean in algorithm 1? Does it mean the leaf elements are randomly permuted?", "limitations": "No societal impact.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The problem is quite motivated: it is known that in the worst case we cannot have all desired operations of a priority queue fast. So beyond worst case models are certainly relevant.\n- The authors study three very natural models of predictions and give sounds justifications of their predictions.\n- The randomized pivot idea in Theorem 2.1 is nice\n- Section 3.3 makes a nice connection about using rank predictions to reduce the problem to integer keys (or bounded universe size), for which there often are better algorithms for. This idea could potentially have other application. It also gives some indication that rank queries maybe more powerful than pointer queries, since the authors use ranks to simulate pointers. \n- The authors improve upon or match results for sorting with predictions studied in previous works.\n- The experiments demonstrate that the, with appropriate predictions, the algorithms outperform worst case behavior", "weaknesses": "- The 'our results' section is a bit disorganized. It would be nice to have a clear table for the different prediction models, showing the prior worst-case bounds and then the bounds for the learning-augmented algorithms, for each of the operations. This would make it easier to quickly understand the improvements in each case, especially since different underlying data structures are used for different prediction models, and the number of results is large.\n- There is a bit of context switching in section 3 since every subsection deals with a new prediction model. Maybe it would be better to not focus on binary heaps in section 2 as much, since the skip lists seem to be the main focus anyways.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive feedback and insightful suggestions. Below, we address the concerns and questions raised in the review.\n\n### Weaknesses\n* **Table of results.** We will include a table, as suggested by the reviewer, summarizing the complexities of the operations using standard and learning-augmented priority queues. This would indeed make it easier to understand the improvements.\n* **Transitions in Section 3.** If the paper is accepted, an additional page will be allowed in the main body. This will provide us with enough space to create smoother transitions between the subsections that address the different models.\n\n### Question\n* In a classical heap, the leaf level is filled from left to right. In our algorithm, whenever a new depth level is reached, denoting by $k$ the number of positions it contains ($k=n+1$), a uniformly random permutation $\\sigma$ of $[k]$ is chosen. The leaf positions are then filled according to the order specified by $\\sigma$. This is equivalent to choosing uniformly at random an empty position for each insertion operation.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "jAPf9VnPnb", "reviewer": "Reviewer_KF5a", "summary": "The study investigates the integration of learning-augmented frameworks into the design of priority queues, focusing on enhancing worst-case performance using potentially inaccurate predictions. It examines three specific prediction models—dirty comparisons, pointer prediction, and rank prediction—applied within priority queues based on skip lists for sorting and Dijkstra algorithms. The research demonstrates how these predictive models can effectively optimize priority queue operations. Furthermore, it establishes the optimality of \nthe proposed solution and explores potential real-world applications of the findings.", "questions": "Q1: Could you provide more specific algorithms that utilize priority queues and indicate under what conditions the original design might experience degradation during basic operation execution? This question pertains to the motivation behind this study.\n\nQ2: Could you provide a more detailed explanation of the class / decay setting (O5)? Particularly, regarding the class setting, as (#classes)/n increases, the number of partitions increases, leading to fewer comparisons. What is the basis for such experimental settings?\n\nQ3: Where does the trade-off lie in your algorithm? Is there a need to allocate additional space for the prediction models? It seems you have omitted necessary discussions on space complexity and have not observed memory usage in your experiments.", "limitations": "none", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "S1: The mathematical proof process of the paper is highly rigorous, demonstrating strong \ncredibility.\nS2: The methods proposed in the paper significantly reduce the number of data item \ncomparisons during the internal execution of basic operations in priority queues, thus \npossessing the potential to pique the interest of researchers in related fields.", "weaknesses": "O1: Writing Quality and Readability Issues\nO1.1 Poor logical flow and transitions: Before discussing the learning-enhanced framework, the limitations and necessity of traditional priority queue methods are not sufficiently explained, leading to unnatural logical transitions. For instance, after stating in line 21, \"However, it is established that a priority queue with n elements cannot guarantee o(log n) time for all the required operations,\" there should be a more detailed explanation of why this is a significant limitation. Similarly, after line 158's statement, \"To improve the \ninsertion complexity with dirty comparisons, we first tackle the search problem in this setting,\" the paper jumps directly into technical implementation without a clear bridging sentence explaining why this approach can improve complexity.\n\nO1.2 Lengthy sentences unsuitable for academic writing: Some sentences are overly lengthy, which does not meet the standards of academic writing. For example, in line 163, \"Indeed,....\"\n\nO1.3 Dense concepts with insufficient explanation: The paper introduces many concepts but fails to adequately explain some important ones. Although many specific examples of priority queue applications are provided, these details could be more credibly summarized and \nsimplified to make the paper more concise. Detailed explanations of application cases might belong in the \"Background\" section rather than the \"Introduction.\"\n\nO1.4 Figures not referenced or adequately explained in the text: The paper contains only three figures, but they are not referenced in the text. For instance, Figure 1 on skip lists is neither clearly explained in the text nor supplemented with detailed captions. Additionally, \nthe figure does not illustrate the dynamic process of finding and deleting the minimum value in a priority queue using a skip list.\n\nO1.5 Lack of summaries and overviews: There is no summary of the innovations, contributions, or experimental results in the Introduction section.\n\nO2: Lack of detailed motivation and innovation overview. The paper does not provide a detailed introduction to the motivation behind the work or summarize its innovative aspects. Although the authors point out the limitation of priority queues in guaranteeing O(logn) \noperations in the worst case on line 21, they do not explain in which application scenarios this limitation occurs. Appendix A also fails to discuss whether related works have addressed this issue and what shortcomings remain.\n\nO3: Dependence on previous work with insufficient innovation. This paper builds on a previous work \"Xingjian Bai and Christian Coester. Sorting with predictions. Advances in Neural Information Processing Systems, 36, 2023.\", requiring readers to have prior knowledge of the previous paper to understand much of its content. However, this paper lacks innovative aspects compared to the previous one, merely combining several prediction algorithms (Dirty Comparison, rank prediction, pointer prediction) with priority queues.\n\nO4: Insufficient comparative analysis of algorithm bounds. While the authors provide numerous bounds for their algorithms in the main text and appendices, these proofs are convincing but lack comparison with related works and original priority queues regarding \nthese bounds. The intrinsic relationship between the designed algorithms and these bounds is not clearly explained. I suggest that the authors provide a comparative table to illustrate the advantages of various bounds more clearly and detail how their algorithms ensure these bounds during the algorithm introduction.\n\nO5: Issues in the experimental section. The experimental section introduces important settings, such as class/decay setting, without prior explanation. These settings are suddenly presented in the experimental part with vague explanations, requiring readers to refer to \ncited articles mentioned in O3 for understanding. As key experimental variables, these settings should be formally defined and described. The authors also fail to explain the specific application scenarios corresponding to these settings and their differences.\n\nO6: Experimental setup issues. The experimental setup has significant issues. Merely using the number of comparisons as a metric is inadequate. The authors should also record the error metrics for the three algorithms mentioned in Section 1.1 in their experiments, \nincluding the number of dirty comparisons, pointer prediction errors, and rank prediction errors. Furthermore, the experiments should compare various methods regarding actual execution time and memory usage in sorting and Dijkstra algorithms. I recommend that the \nauthors refer to relevant experimental metrics used in research papers from the learned index field.\n\nO7: Unsubstantiated claims about adversarial insertion order. In line 110, the authors mention that their proposed method has advantages under adversarial insertion orders, but they neither explain which application scenarios would encounter this situation nor provide \nexperimental results to validate this claim.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback and suggestions. We address below their concerns.\n### Weaknesses\n* **O1.1. (Limitations of standard priority queues, line 21)** The lack of $o(\\log n)$ time priority queues is an impossibility result, hence a limitation. We are not quite sure what type of detailed explanation the reviewer is requesting.\n* **O1.1. (Sentence in line 158)** Immediately before that sentence, in the same paragraph, we explain that a heap can use a binary search algorithm for insertion. Having a better search algorithm, using predictions, would therefore immediately improve the insertion complexity.\n* **O1.2.** We kindly disagree regarding line 163. That sentence is not overly complex, and we do not think this constitutes a weakness in the paper.\n* **O1.3.** Could the reviewer specify which concepts they would like us to explain more? The list of applications in the first paragraph illustrates their ubiquity, but the details are not important.\n* **O1.4.** We will add explicit references to Figures 1 and 2 in the text. Figure 1 is merely an illustration of a skip list and corresponds to the description above it. Figure 2 includes a clear caption and corresponds to the discussion to its left. As noted in line 357, a detailed discussion of Figures 3 and 4 is included in Appendix G, which we could not include in the main body of the paper due to space limitations.\n* **O1.5.** The section \"our results\" summarizes our main contributions and experimental results.\n* **O2.** We address all the points raised here in O1.5, O1.1 and Q1.\n* **O3.** The paper does not require any prior knowledge of the previous work by Bai and Coester for comprehension. We study, among others, the dirty comparison model they have introduced. However, we formally define the model and explain its relevance for priority queues. In Section 4, we demonstrate how their results can be derived as corollaries of ours. For sorting, we also employ their experimental setup to compare with their sorting algorithms, which only proves the efficiency of our priority queue. We use their results only to prove the lower bound in the pointer prediction model.\n* **O4.** The complexities of priority queues are detailed in the related work, and are recalled multiple times throughout the paper (lines 85, 149, 156, 198, ...). However, as suggested by the reviewer, we will add a table in the section \"our results\" to summarize the different bounds.\n* **O5.** The motivation behind these settings is not discussed in sufficient detail due to space limitations. Their relevance to Dijkstra's algorithm is addressed in Appendix G. If the paper is accepted, we will use the additional page to provide more detailed information on the motivation (see also our reponse to Q2 below).\n* **O6.** The prior work of Bai and Coester, which we can compare to, used number of comparisons as performance metric. This has the advantage that results are replicable independent of hardware and implementation details. Therefore, we opted to use the number of comparisons as performance metric as well. In particular, this allowed us to use a simple Python implementation for our algorithms, whereas for the algorithms by Bai and Coester we used their existing C++ implementation. The prediction error in the three models is correlated to the number of classes in the class setting, and to the number of timesteps in the decay setting. Thus, the x-axis in the figures represents the amount of perturbation in the predictions. The works in the learned index field that we are aware of have a much stronger experimental focus, whereas our paper's primary focus is theoretical. Many other experiments are possible, which could be part of a separate study.\n* **O7.** The bounds we establish for sorting hold for any insertion order, even if chosen by an adversary. This contrasts with the algorithm of Bai and Coester, which requires a random insertion order. So our algorithms are defined in a strictly broader setting. Application scenarios of the broader setting we capture are any situations where a sorted order must be maintained while items are added (and possibly deleted) over time, rather than being known upfront. Validating this claim experimentally would not make sense, as the algorithms of Bai and Coester cannot process such inputs.\n\n### Questions\n* **Q1.** Regardless of the use case, the priority queue operations with a binary heap always require $\\Theta(\\log n)$ comparisons. In a skip-list, insertion always requires expected $\\Theta(\\log n)$ comparisons. The motivation of the paper is to use predictions to reduce these complexities.\n * **Q2.** The formal description of both settings is given in the experiments section (line 337). In the context of sorting, items often have grades that provide a partial ordering. For instance, students might have GPA grades A,B,C,..., and our goal is to determine their precise ranking. The decay setting models situations where an initial ordering of items may have evolved over time. The perturbation of the ordering depends on the time elapsed between the initial ranking and the current time step. The relevance of both settings for Dijkstra's algorithm is given in Appendix G (line 986). If the paper is accepted, we will use the extra page to expand this discussion in the experiments section.\n* **Q3.** As is common in the literature on algorithms with predictions, we treat the ML models delivering the predictions as a black box. Their space consumption depends on the implementation of the model. The expected space occupied by a skip list is $O(n)$, and in the case of rank predictions, an additional $O(N)$ space is needed to store the vEB tree.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper presents mechanisms for improving the known worse-case performance of priority queues via augmentation through learning.  The learning mechanisms presented are not new but putting them together to show performance improvement beyond the theoretical bound for three classes of problem presented is novel and is expected to have positive impact on the research community.
Decision: Accept (poster)