Thank you for your thoughtful comments! We address the questions and concerns as follows.

Robustness If no prediction is available, we can naturally set the "predicted frequency" to be $1/n$. In this case, the access cost becomes $O(\log n)$.

Predictions for Dynamic Settings Thank you for highlighting this point! We will include a paragraph in the revision regarding the prediction of working-set scores.

The working-set size (Definition 4.2) captures the temporal locality and diversity of user behavior around item $x$. Although it requires knowledge of future access items, it aligns conceptually with practices in recommendation systems, where temporal context is used to model user intent and predict relevance. For example, session-based recommendation often considers the diversity of items within a user's recent session [1]. In practice, we can approximate this score using causal proxies (e.g., past-only working-set size) or apply machine learning models to predict it based on observable access patterns.

Clarification on Proof Plan The priority score of $x$ consists of the tier $\tau_x$, which is an integer, and $\delta_x \in (0,1)$. Consequently, all ancestors of the node $x$ must have tier less than or equal to $\tau_x$, and thus are part of the set $S_t$ for $t\leq \tau_x$. In other words, there are no ancestors of $x$ outside the sets $S_t$.

B-tree Update At each time step, we first compute the working-set score of the current item, then remove the item from the B-tree, and finally re-insert the node into the B-tree with the updated score accordingly. Note that B-Treaps support insertions and deletions efficiently [Lemma C.1].

[1] Wang, Shoujin, et al. "A survey on session-based recommender systems." ACM Computing Surveys (CSUR) 54.7 (2021): 1-38.

Thank you for your comments! We sincerely apologize for the various writing issues and will make every effort to improve them, particularly in the sections on the dynamic setting and the introduction. We will also cite the article you recommended and clearly state the static optimal BST cost to help readers better understand the context. Your writing suggestions are very helpful, and we truly appreciate you pointing them out. We address your questions as follows.

1. The robustness in [Lin et al.] is defined as follows. If the frequency predictor satisfies $\frac{1}{\delta}f_i\leq \hat{f_i} \leq \delta f_i$ for some constant $\delta>0$, then the corresponding Treap with predicted score has an additive constant error compared to the optimal.

   If we use the same definition, our data structure also achieves an additive constant error in access cost relative to the optimal. However, our notion of robustness provides a stronger guarantee - even when the predicted frequency does not satisfy this assumption. In particular, we still obtain an upper bound on the access cost measured by the KL divergence.

2. In Line 310, our intention was to illustrate that there exists a distribution under which the BSTs in Lin et al. have an $\Omega(n)$ access cost, whereas our data structure achieves $O(\log n)$. We apologize for the unclear wording, which may have led to the misunderstanding that our method always guarantees $O(\log n)$ worst-case access cost.

We will revise Line 310 as follows to clarify this point:

However, it does not generally hold - there exists a distribution $p$ where the expected access cost for Lin et al. is $\Omega(n)$, while our data structure achieves only $O(\log n)$ cost.

Thanks for your thoughtful comments! We would like to begin by sincerely thanking you for pointing out the related work that we had overlooked. We will make sure to include proper citations in the updated version of the paper. Below, we address the three specific questions you raised:

1. Splay trees are conjectured to be dynamically optimal, which requires no prior knowledge. Therefore, it is very likely that no BST with/without learning-augmented can beat them in the theoretical bound. However, it is important to note that the runtime guarantees of splay trees are amortized. In particular, accessing a single item $x$ may still take linear time, which could be prohibitive in many scenarios.

   Furthermore, there are no "splay trees" in the B-tree area under the external-memory setting. This makes our approach more applicable in such settings.

   Our experiment results also show that splay trees have a higher access cost across most datasets. In this way, our work contributes to the study and understanding of static and dynamic optimality in search trees and could serve as a useful step toward a better understanding of splay tree optimality.

2. When the frequency distribution is highly skewed, some items may have an exponentially small frequency. This can result in depths as large as $O(n)$. However, the data structure still achieves static optimality.

   In contrast, for the data structure proposed by Lin et al., Theorem 2.14 shows a frequency distribution where the depth is $\Omega(n)$. This aligns with the consistency results of $\Omega(n/\log n)$ given in Proposition 2.2 of Zeyanali et al..

3. Exploring lower bounds for deterministic data structures in the learning-augmented setting is indeed an interesting and important direction. However, to the best of our knowledge, there are currently no established results in this area. We agree that this is a valuable question for future work.

Thanks for your comments! We will address your concern as follows.

Robustness and Bad Predictions

We use the word robustness to describe how the performance of our data structure degrades smoothly with respect to the prediction error - measured by KL divergence in the static setting and mean absolute error in the dynamic setting.

Using the robustness definition in [1, 2] - i.e., the competitive ratio under the worst-case prediction - our data structure is $O(n)$-robust in the static setting (Proposition 2.3 in [2]).

However, the data structure achieves $O(\log n)$-robustness if we ensure that each predicted score is at least $1/n^C$ for a large constant $C>0$. In practice, this can be achieved by modifying the predictor to guarantee it, for example, by taking a maximum of the predicted score and $1/n$.

In the dynamic setting, assuming the predicted scores satisfy $\tilde{w}_{i,j}\geq 1/\text{poly}(n)$ as in Theorem 4.5, the data structure achieves $O(\log n)$-robustness.

Worst-case Bound In Line 310, our intention was to illustrate that there exists a distribution under which the BSTs in [3] have an $\Omega(n)$ access cost, whereas our data structure achieves $O(\log n)$. We apologize for the unclear wording, which may have led to the misunderstanding that our method always guarantees $O(\log n)$ worst-case access cost.

We will revise Line 310 as follows to clarify this point:

However, it does not generally hold - there exists a distribution $p$ where the expected access cost for [3] is $\Omega(n)$, while our data structure achieves only $O(\log n)$ cost.

Branching Factor The branching factor arises from B-treaps. If we want to construct a BST in the dynamic setting, the analysis proceeds in the same way, without involving the branching factor.

[1] Mitzenmacher, Michael, and Sergei Vassilvitskii. "Algorithms with predictions." Communications of the ACM 65.7 (2022): 33-35.

[2] Zeynali, Ali, Shahin Kamali, and Mohammad Hajiesmaili. "Robust Learning-Augmented Dictionaries." International Conference on Machine Learning. PMLR, 2024.

[3] Lin, Honghao, Tian Luo, and David Woodruff. "Learning augmented binary search trees." International Conference on Machine Learning. PMLR, 2022.