Learning-Augmented Priority Queues

We thank the reviewer for their feedback and suggestions. We address below their concerns.

Weaknesses

• 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.
• 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.
• 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.
• 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.
• 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.
• O1.5. The section "our results" summarizes our main contributions and experimental results.
• O2. We address all the points raised here in O1.5, O1.1 and Q1.
• 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.
• 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.
• 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).
• 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.
• 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.

Questions

• 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.
• 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.
• 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.

We thank the reviewer for their positive feedback and for the time and effort spent on our submission.

Weakness. The 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.

We thank the reviewer for their positive feedback and insightful suggestions. Below, we address the concerns and questions raised in the review.

Weaknesses

• 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.
• 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.

Question

• 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.

We express our gratitude to the reviewer for their feedback and insightful comments. We address below the weaknesses they have raised.

Weaknesses

• 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.
• "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.
• 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.