On the Power of Learning-Augmented Search Trees
Authors: Jingbang Chen
Xinyuan Cao
Alicia Stepin
Li Chen
Venue: ICML 2025 poster (2025)
Keywords: learning-augmented; binary search tree; algorithm with predictions; data structure
Primary area: general_machine_learning
TL;DR: We develop robust learning-augmented BSTs and B-trees that achieve near-optimal performance for arbitrary input distribution.

Abstract: We study learning-augmented binary search trees (BSTs) via Treaps with carefully designed priorities.
The result is a simple search tree in which the depth of each item $x$ is determined by its predicted weight $w_x$.
Specifically, each item $x$ is assigned a composite priority of $-\lfloor\log\log(1/w_x)\rfloor + U(0, 1)$ where $U(0, 1)$ is the uniform random variable. By choosing $w_x$ as the relative frequency of $x$, the resulting search trees achieve static optimality.
This approach generalizes the recent learning-augmented BSTs [Lin-Luo-Woodruff ICML`22], which only work for Zipfian distributions, by extending them to arbitrary input distributions.
Furthermore, we demonstrate that our method can be generalized to a B-Tree data structure using the B-Treap approach [Golovin ICALP'09]. Our search trees are also capable of leveraging localities in the access sequence through online self-reorganization, thereby achieving the working-set property. Additionally, they are robust to prediction errors and support dynamic operations, such as insertions, deletions, and prediction updates. We complement our analysis with an empirical study, demonstrating that our method outperforms prior work and classic data structures.

On the Power of Learning-Augmented Search Trees
Jingbang Chen
Xinyuan Cao 2
Alicia Stepin 3 Li Chen
Abstract
lak & Zub, 2024; Lavastida et al., 2021), matching (Chen et al., 2022a; Dinitz et al., 2021; Aamand et al., 2022), spanning tree (Erlebach et al., 2022), and triangles/cycles counting (Chen et al., 2022b), with the goal of obtaining algorithms that get near-optimal performances when the predictions are good, but also recover prediction- worst- case behavior when predictions have large errors (Mitzen- macher Vassilvitskii, 2022).
We study learning-auge augmeenedd binary search trees (BSTs) via Treaps with carefully designed priori- ties. The result is simple search tree in which the depth of each item æ is determined by its predicted weight Wg. Specifically, each item æ is assigned a composite priority of - [log log(1 | //=)) (U((,) 1) where (0, 1) is the uniform random variable. By choosing Wa as the relative frequency of æ, the resulting search trees achieve static optimal- ity. This approach generalizes the recent learning- augmented BSTs (Lin-Luo-Woodrurff Woodruff ICML. '22], which only work for Zipfian distributions, by ex- tending them to arbitrary input distributions. Fur- thermore, we demonstrate that our method can be generalized
The problem of using learning to accelerate search trees, as in the original learned index question, has been widely studied in the field of data structures, focusing on develop- ing data structures optimal to the input sequence. Mehlhorn (1975a) showed that a nearly optimal static tree can be constructed in linear time when exact key frequencies are provided. Extensive work on this topic culminated in the study of dynamic optimality. Tango trees (Demaine et al., 2007) achieve competitive ratio of O(log log r1) while splay trees (Sleator & Tarjan, 1985) and Greedy BSTs (Lu- cas, 1988; Munro, 2000; Demaine et al., 2009) are conjec- tured to be within constant factors of optimal.
B-Tree data structure using the B-Treap approach [Golovin ICALP '09]. Our search trees are also capable of leveraging local- ities in the access sequence through online self- reorganization, thereby achieving the working-set property. Additionally, they are robust to predic- tion errors and support dynamic operations, such as insertions, deletions, and prediction updates. We complement our analysis with an empirical study, demonstrating that our method outperforms prior work and classic data structures.
Treaps, introduced by Aragon & Seidel (1989), is class of balanced BSTs distinguished by its use of randomization maintain low tree height. Each node in Treap is assigned not only a key but also randomly generated priority value. This design enables Treaps to satisfy the Heap property, ensuring that every node has lower priority than its parent. In general, Treaps use randomness to ensure a low height instead of balancing the tree preemptively. More recently, aagment Treap,
1. Introduction
Lin al. (2022) introduced demonstrating stronger guarantees compared to traditional Treaps. However, it relies on the strong assumption of the Zipfian distribution.
The development of machine learning has sparked signifi- cant interest in its potential to enhance traditional data struc- tures. First proposed by Kraska al. (2018), the notion of learned index has gained much attention since then (Kraska
Inspired by this line of work, our research is driven by a series critical questions.
et al., 2018; Ding al., 2020; Ferragina & Vinciguerra, 2020). Algorithms with predictions have also been devel- oped for an increasingly wide range of problems, includ- ing shortest path (Chen et al., 2022a), network flow (Po-
Whether more general Cearning-augmente BST exists and achieves static optimality?
'qqual contribution Univeessity of Waterloo "Georgia Institute of Technology CCarnegie Mellon University 'Independent; Part of the work by Jingbang Chen and Li Chen was done while Georgia Tech. Correspondence to: Li Chen <lichenntu @ .mmi..com>>.
Can such BST also obtain good guarantees under the dynamic settings?
Are they robust the errors caused by the prediction oracles?
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

On the Power of Learning-Augmented Search Trees
This paper addresses the questions affirmatively by develop- ing new learning-uugmenter Treaps with carefully designed priority scores, which are applicable to arbitrary input dis- tributionn in both static and dynamic settings. In the static setting, we show that our Gaaming-augmenter within a constant factor of the static optimal cost when incor- porating a prediction oracle for the frequency of each item. The proposed Treaps are robust to predicted errors, where the additional cost induced by the inaccurate prediction grows linearly with the KL divergence between the rela- tive frequency and its estimation. For the dynamic setting, where the trees can undergo changes after each access, we show that given prediction oracle for the time interval until the next access, our data structure can achieve the working- set bound. This bound can be viewed as strengthening of the static optimality bound that takes temporal locality of keys into account. Such dynamic BSTs are robust to the prediction oracle as well, where the performance de- grades smoothly with the mean absolute error between the logarithm of the generated priorities and the ground truth prioritics. Additionally, under the external memory model, our maaming-auggenttn
Specifically, we show in Theorem 2.4 that by setting the composite priority function to be
1 Wxx
- log log
+ (0,1,,
(1)
Treaps are
the expected depth of node x is O(log(1/1) w.))) The pre- dicted score w2 (0, 1), for instance, can be set as the relative frequency or probability of each item.
Our Treap-based scheme generalizes to B-Trees, where each node has B instead of 2 children. These trees are highly important external memory systems due to the behavior of cache performances: accessing a block of B entries has a cost comparable to the cost of accessing ((1) entries. By combining the B- B-Treaps (Golovin, 2009) with the composite priorities, we introduce a new that achieves similar bounds under the External Memory Model. We show in Theorem 3.1 that for any weights over elements w, by setting the priority to
B-Tree
1 - + UO,1), Wx
- -log log
(2)
BST can be naturally extended to a B-Tree version via B-Treaps. Experimental results demon- strate that the proposed Treap outperforms both traditional data structures and other even when the predictions are inaccurate.
the expected depth of node x is O(log (1/0))(1100)) (1/w))) It is natu- ral to see that our proposed data structures unify BSTs and B-Trees. For simplicity, we provide the results of B-Trees in the remaining content.
data structures,
Static Optimality of Maariing-Augmenter Search Trees. We can construct static optimal B-Trees if we set w to be the marginal distribution of elements in the access sequence. That is, if we know the frequencies f2....... fn of each element that appears in the access sequence, and let m = Σ, ft to be the length of the access sequence, then we set the score wa = fa/m m in Equation (2) and the corresponding B- Tree has a total access cost that achieves the static optimality
1.1. Overview
Gearning-Augmenti Treaps via Composite Priority Functions. The Treap is a tree-balancing mechanism ini- tially designed around randomized priorities (Aragon & Seidel, 1989). When the priorities are assigned randomly, the resulting tree is balanced with high probability. Intu- itively, this because the root is likely to be picked among the middle elements. However, if some node is accessed very frequently (e.g. 10% of the time), it's natural to assign it a larger priority. Therefore, setting the priority to be a function of access frequencies, as in Lin et al. (2022), is a natural way to obtain an algorithm more efficient on more skewed access patterns. However, when the priority is set exactly as the access frequency, some nodes would have super-logarithmic depth: if each element i is accessed times, setting priority exactly as the frequencies results in a path of size n. The total time for processing this access sequence of size ((z²) degrades to 2(n²). Partly as result of this, the analysis in Lin et al. (2022) was limited only to when frequencies are under the Zipfian distribution.
m Σ f logB
f.
Search Trees. We also consider the dynamic setting in which we continually update the priorities of a subset of items along with the sequence access. Rather than a fixed priority for each item, we allow the priorities to change as keys get accessed. The setting has wide range of applications in the real world. For instance, consider accessing data in a relational database. A sequence of access will likely access related items one after another. So even if the entries themsel get accessed with fixed frequencies, the distribution of the next item to be accessed can be highly dependent on the set of recently accessed items. Consider the access sequence
Dynamic
Building upon these ideas, we introduce a composite prior- ity function, a mixture of the randomized priority function from Aragon & Seidel (1989) and the frequency- pri- ority function from Lin et al. (2022). This takes ad advattgee of the balance coming from the randomness and manages to work without the strong assumption from Lin et al. (2022).
4,2,3, 5, 2, 4, 3,5,
versus the access sequence
5,2, 2, 1, 4, 4, 4, 4,5,,44,
2

---

On the Power of Learning-Augmentte Search Trees
Static Sequence
Robustness Prediction Inaceuracy. Finally, we show the robustness of our data structures with inaccuracies in prediction oracles. In the static case, we can directly relate the overhead of having inaccurate frequency predictions to the KI. divergences between the true relative frequencies Pz and their estimates dr- This is because our composite priority can take any estimate. So plugging in the estimates 9z gives the overall access cost
5
4
2
1
4
5
3
3
4
5
2
Search Tree
W1
Learning Oracle
d3pth(3)
([lo)(I/ws))
Wn
W priority(x)
- llo (oog(1//w,))11 U(0.1)
)
1 1x
Σ Ps log2
Dynamic
Time
Sequence
5
2
4
3
3
4
4
which is exactly the cross entropy between p and q. On the other hand, the KI. divergence between p and q is exactly the cross entropy minus the entropy of p. So we get that the overhead of building the tree using noisy estimators instead of the true frequencies is exactly times the KL divergence between p and q. We formalize the argument above in Section 2.3. We also achieve robustness results in the dynamic setting in Appendix D.2.
Search Tree Time
Search Tree at Time
d3)
5
3
W11
Learning
W122
Oracle
priority(t) -llog [o((//((\/ U(0.))
In all, our contributions can be summarized as follows:
L...
We introduce composite priorities that integrate learned advice into Treaps. The BSTs and B-Trees constructed via these priorities are within constants of the static optimal ones for arbitrary distributions (Section 2, Sec- tion 3).
((1) R
Figure 1. Sketch for static and dynamic learning augmented search trees. Since item 3 has higher frequency around time dynamic search trees adjust the priority accordingly.
When allowing updating trees along with accessing items, we design working-set priority function, and the corresponding Treaps with composite priorities can achieve the working-set bound (Section 4).
In both sequences, the item 4 is accessed the most frequently. So input-dependent search trees should place near the root. However, in the second sequence, the item accessed three consecutive times around the middle. An algorithm that's allowed to modify the tree dynamically can then mod- ify the tree to place 3 closer the root during those calls. An illustration of this is in Figure 1. Note that pay costs both when accessing the items and updating the trees. Hence, there is a trade-off off between the costs of updating items' scores and the benefits of time-varying scores.
Both static and dynamic learning-augmented search trees are robust to predictions (Section 2.3, Ap- pendix D.2).
Our experiments show favorable performance pared to prior work (Section 5).
We study ways of designing composite priorities that cause this access cost to match known sequence- sequence-dependent access costs of binary trees (and their natural generalizations to B-Trees). Here, we focus the working-ser bound, which says that the cost of accessing an item should be, at most, the logarithm of the number of distinct items until they get accessed again. To obtain this bound, we propose a new composite priority named working-set priority, based on the number of distinct elements between two occurrences of the same item accessed step i. We give the guarantees for the dynamic Treaps with the working-set priority in Theo- rem 4.4. The dynamic search Treaps further demonstrate the power of learning scores from data. While we have more data, we can quantify the dynamic environment in a more accurate way and thus improve the efficiency of the data structure.
1.2. Related Work
In recent years, there has been surge of interest in inte- grating machine learning models into algorithm designs. A new field called Algorithms with Predictions (Mitzenmacher & Vassilvitskii, 2022) has garnered considerable attention, particularly in the use of machine learning models to pre- dict input patterns to enhance performance. Examples of this approach include online graph algorithms with predic- tions (Azar al., 2022), improved hashing- methods such Count-Min (Cormode & Muthukrishnan, 2005). and searning-auggentt 2022). Practical oracles for predicting desired properties, such as predicting item frequencies in a data stream, have been demonstrated empirically (Hsu et al., 2019; Jiang et al., 2020).
k-means clustering (Ergun et al.,
3

---

On the Power of Learning-Augmented Search Trees
Capitalizing on the existence of oracles that predict the prop- erties of upcoming accesses, researchers now developing more efficient -augmeetdd data structures. Index structures in database management systems are one signifi- cant application of carming-augmente data structures. One key challenge in this domain is to create search algorithms and data structures that are efficient and adaptive to data whose nature changes over time. This has spurred interest in incorporating machine learning techniques to improve traditional search tree performance.
x is an ancestor of y in Treap without traversing the tree. Observation 2. Given any 2; E [n]. x is an ancestor of y if and only if priority, - maxx priority..
Classical results from Aragon & Seidel (1989) state that if the priorities are randomly assigned, the depth of the Treap cannot be too large. Also, Treaps can be made dynamic and support operations such insertions and deletions.
Lemma 2.2 ((Aragon & Seidel, 1989)). Let U(0, 1) be the uniform distribution over the real interval [0. 1]. If priority ~ UO, 1)". each Treap node has depth ((loga n) with high probability.
The first study on learned index structures (Kraska et al., 2018) used deep-learning models to predict the position or existence of records as an alternative to the traditional B-Tree or hash index. However, this study focused only on the static case. Subsequent research (Ferragina & Vin- ciguerra, 2020; Ding al., 2020; Wu et al., 2021) intro- duced dynamic learned index structures with provably effi cient time and space upper bounds for updates in the worst case. These structures outperformed traditional B-Trees in practice, but their theoretical guarantees were often trivial, with no clear connection between prediction quality and performance. More recently, Lin et al. (2022) proposed learning-augmented BST via Treaps that works under the Zipfian distribution.
Lemma 2.3 ((Aragon & Seidel, 1989)). Given a Treap T and some item x E [ni]. x can be inserted to deleted from T in O(depth(z)) -timme
2.1. Learning-Augmeen Treaps
In this section, present the construction of composite priorities and prove the following theorem.
Theorem 2.4 LLearning-Augmenti Priorities). Denote w = (W1, Wn) E (0, 1)" as a score associated with each item in [n] such that || = ((1)
Treap via Composite
Consider the following priority assignment of each item:
1 W.
Other related work on BSTs analyses and B-Trees under the external memory model is included in Appendix A.
priority x def
logg log2
dg
(3)
where 8. is drawn independently uniformly from (0, 1). The expected depth of any item x E [ni] is O(log2(1, (1/wz)).
2. Baarning-Augmente Binary Search Trees
In this section, we show that the widely taught Treap data structure can, with small modifications, achieve the static optimality conditions sought after in previous studies of learned index structures (Lin al., 2022; Hsu et al., 2019). We start with definitions and basic properties of Treaps.
Proof Plan. Note that the priority in Equation (3) consists
1 of two terms. We define x's tier as T2 == log, loga wa
- [priority, St = {i [n]] Tg = t) be the number of items whose tiers are equal t. We assume wlog that T2 2 0 for any Otherwise, T= < 0 implies wa S(1),, which can hold for only a constant number of items. So, we can always put them at the top of the Treap, which increases the depths of other items by a constant.
Definition 2.1 (Treap (Aragon & Seidel, 1989)). Let T be BST over [x]] and priority E R" be a priority assignment on [n]. We say (T, priority) is a Treap if priority, I priority, whenever is a descendent of y in T.
Given a priority assignment priority, one can construct a BST T such that (T. priority) is a Treap as follows. Take any x² E arg max, priority, and build Treaps on [I, - and +1"+1, n) recursively using priority. Then, we just make xx the parent of both Treaps. Notice that if priority,"" 's are distinct, the resulting Treap is unique.
The expected depth of a is the number of its ancestors. We show in Lemma 2.5 that the number of items at tier is bounded by |S.ll 20(22) Furthermore, for each tier, the ties are broken randomly due to the random offset d (0, 1). Then, as we show in Lemma 2.6, any item has O(logg [S.) ) = O(2*) ancestors with tier / in expectation. Therefore, the expected depth E [[depth(z)) can be bound by O(20 + 21 +.... + 2*=) = O(2*)) = O(log, (1 (l/lo,(1/,,)) //ww)).
Observation 1. Let priority E R", which assigns each item unique priority. There is unique BST T such that (T, priority) is Treap.
Lemma 2.5. For any integer t 2 0, |S&| = 20(")
From now on, we always assume that priority has distinct values. Therefore, when priority is defined from the context, the term Treap refers to the unique BST T. For each node I E [n], we use depth(r) to denote its depth in T, i.c., the number of vertices on the path from the root to x.
Proof. Observe that x E S₁ if and only if
I < logg logg(1 (1/wz) l + 1, and 2 < w.
< 2
Since the total score ||l||| 0(1), there are only poly(22't)) = 20(2') such items.
Given any two items x. y E [m], one can determine whether
4

---

On the Power of Learning-Augmented Search Trees
Next, we bound the expected number of ancestors of item x in every St such that S Tx-
we define Jn for any item 2; to be its frequency in X, i.e. fx == {i e [m] xx(i) = x} 1 E [r]. For simplicity, we assume that every item is accessed at least once, i.e., fx 2 1, E [n]. We prove the following result as a simple application of Theorem 2.4 by setting wz == fo m 2 [n].
access sequence X
Lemma 2.6. Let E [n] be any item and t S Ty be a non-negative integer. The expected number of ancestors of in St is at most O(log2 {S())-
Proof. First, we show that any E Ss is an ancestor of x with probability no more than 1/|5, n [x. w]]- Observation 2 says that? y must have the largest priority among items [z. y/. Thus, a necessary condition for y being z's ancestor is that y has the largest priority among items in S. n [x. y). However, priorities of items in S, [xr, y] are i.i.d. random variables of
Theorem 2.8. For any item x E [m]. we set its priority as
priority x = - logg log2
-110gg
m Jx - 6, ~00
In the corresponding Treap, each node x has expected depth ( fa)). Therefore, the total time for processing the access sequence is OgE, f logz (m/ [w)), which matches the performance of the optimal static BSTs up to a constant factor.
the form -t + (0, 1). Thus, the probability that priority, y is the largest among them is 1/15, O [z, vll.
To bound the expected number of ancestors of a in St E Jumberr of ancestors of St]
2.3. Robustness Guarantees
Σ yES.
Pr (y an ancestor of z)
In practice, one could only estimate Iu R P.. fz/ fz/m,a a e [n]. A natural question arises: how does the estimation error affect the performance? In this section, we analyze the drawbacks in performance given the estimation errors. As result, we will show that our Learning-Augmentt Treaps are robust against noise and errors.
22.
Ologg |Sa));
S. n [
2
DES.
where the second inequality comes from the fact that for a fixed value of u, there are at most two items y E Sz with [S, v]l = u (one with y S x, the other with > z). D
For each item æ E [n]]. define pa: = -fa/m m to be the relative frequency of item æ. One can view p as a probability distri- bution over [ni] such that p(x) Pa- Then we can restate the expected depth of each item in Theorem 2.8 using the notion of entropy. We define the entropy as follows and state the corollary in Corollary 2.10.
Now we are ready to prove Theorem 2.4.
Proof of Theorem 2.4. By Lemma 2.6 and Lemma 2.5, the expected depth of x can be bounded by
Definition 2.9 (Entropy). Given a probability distri- bution p over [m). define its Entropy as Ent(p) =
Eldepth(x))
El [umber of ancestors of in S,]
Σx Pe log (1)521111 (1/p=) = (lozpplog2(11p)
Ts
S O log2 |sel
<
2
S < (2*))
Corollary 2.10. In Theorem 2.8, the expected depth each item x (llogg(1/p)) and the expected total cost is O(m- Ent(p)), where Fnt(p) Σ. Pa. loga (1)2(11))) (1/pz) measures the entropy of the distribution p.
We conclude the proof by observing that
1 S Tz + and 2 S logg Wa
Now we consider the case when we cannot access the rel- ative frequency Pa- Instead, we are given pa 's estimator, 9z. and construct the lata-nug BST with qa- Sim- ilarly, we view as a data distribution over [n] such that ((x) = 92- Then we show that the total access of the treap built with gar equals the total access number m times the cross entropy of p and q in Theorem 2.13. We start with some definitions.
Tu S log, loga wz
Moreover, our proposed learning-augmentt efficient updates, where we can use rotations to do insertions, deletions, and weight changes. The following corollary follows naturally by Theorem 2.4 and Lemma 2.3.
treap supports
Corollary 2.7. The data siructure supports insertions and deletions naturally. Suppose the score of some node x changes from w to w' and a pointer to the node is given, the Treap can be maintained with O() logg(w' (w' (w'/)))) rotations expectation.
Definition 2.11 (Cross Entropy). Given two distributions q over [n], define its Cross Entropy as Ent q) = Σx Pa log, (1/gx) = (txxpl)og2(1qq.)))
Definition 2.12 (KL Divergence). Given two distributions
2.2. Static Optimality
p. q over [n]. define its KL. Divergence as DKL q) =
Ent (p, q) - Ent(p) = E., Ps logo(p=/q.)
We present a priority assignment for constructing stati- cally optimal Treaps given item frequencies. Given any
We analyze the run time given frequency estimations q.
5

---

On the Power of Learning-Augmentcr Search Trees
Theorem 2.13. Given distribution q, an estimate of the true relative frequencies distribution p. For any item x E (nl,, we draw random number og U0, 1) and set its priority as
Next, we consider the priority assignment priority,
[log2 1/pz] + òz, ~ (0,1))
Theorem 2.15. Consider the following priority assign- ment that sets the priority of each node a as priority, == -Ilog, 1/p=] + ōg Sz (O, There is distri- bution p over [n]] such that the expected access time, Ex~pldepth(z)) = (1log] n).
priority, == - logg log2
1 qr
+ dx-
In the corresponding Treap, each node has expected depth (logg(1/ (I/q=)). Therefore, the total time for processing the access sequence is (m Ent(p. (p. q)).
Proof. We assume WLOG that is an even power of 2. Define K = Z logg n. We partition [n] into K + segments , SK+1 S [n]. For i = 1.2....... K, we add 2 . n/K elements to S. Thus, S1 has n/K K elements, S₂ has n/2K, and Sx has vn/K K elements. The rest are moved to SK+1-
Proof. Define the weights w, 9- for each item E [ni]. Clearly, ||w|| = 1 and we can apply Theorem 2.4 to prove the bound on the expected depths. The total time for processing the access sequence is, by definition,
Now, we can define the distribution p. Elements in SK+1 have zero-mass. For i 1, ...,.... K, elements in S. has probability mass 2 One can directly verify that is indeed a probability distribution over [n]]
Σ fe loga TE
1 qu
0 m Σ
Ps
log2
qu
DE
O (m Ent(pp q))
In the Treap with the given priority assignment, S; forms subtree of expected height Ologg n) since [St] 2 n//3 for any
2.4. Analysis of Other Priority Assignments
........A K (Lemma 2.2). In addition, ev- ery element of S; passes through S1+1, Si42,.., Sk on its way to the root since they have strictly larger pri- orities. Therefore, the expected depth of element E S, is Q(( - i) log, n). One can lower bound the ex- pected access time (which is the expected depth) as: K
In this section, we discuss two different priority assignments. For each assignment, we design an input distribution that results in a greater expected depth than the expected depth with our priority assignment stated in Theorem 2.8. We define the distribution as p(z) = Ps= = fa/ fe/m,2 x E [n]. We use/ ʃ ス g to indicate that I is greater or equal to g up to constant factor.
Ee-pldepth(>))
Σ DES:
Pr (K i) logg n
The first priority assignment is used in Lin al. (2022). They assign priorities according to Ps entirely, i.e., priority, = Pa. x E [n]. Assuming that items are ordered randomly, and p is a Zipfian distribution, they show Statie Optimality. However, it does not generally hold-ther ex- ists a distribution p where the expected access cost for (Lin et al., 2022) is (2)). while our data structure (Theorem 2.4) achieves only Ologz n) cost.
K
K Σ 1=1
Σ p(S). (1) logg n = i=1
(K -2) (K-
llog2 n
K
2 K log, n 2 log n,
where we use p(S)) = |S 2/-1/n = 1/K and K =
@(log n). That is, the expected access time is at least ((log n).
Theorem 2.14. Consider the priority assignment that as- signs the priority of each item to be priority, := Pa, x E [n]] There is a distribution p over [n] such that the expected ac- cess time, Exz=pl (empp/dept(())) = 2(n).
3. Luagning-Augmented B-Trees
We now extend the ideas above, specifically the compos- ite priority notions, to B-Trees in the External Memory Model. The main results are shown follows. Full details are included in Appendix C. We show that the learning- augmented B-Treaps (Appendix C. obtain static optimality (Appendix C.2) and is robust to the noisy predicted scores (Appendix C.3).
Proof. We define for each item x, P. == 2(n-z+1) One
m(x+1)
could easily verify that p is distribution over [n]. In addi- tion, the smaller the item æ, the larger the priority priority Thus, by the definition of Treaps, item has depth æ. The expected access time of sampled from p can be lower bounded as follows:
Theorem 3.1 (Learning-Augmented B- B-Treap via Composite Priorities). Denote w = (w1, w.. E (0, 1)" as score associated with each element of [n] such that ||w||| = O(1) and branching factor B = Q(I 1/(-aa) n), consider the following priority assignment scheme:
Ezep [depth(=)] =
Σ Pa dzpth(z)
2(n - x +
Σ
x(n - x +1) 1) Σ
x
n(nn + 1)
n(n + 1) xE(n)
#E(M)
1 - + dz. 8n ~ UO,
2
.n3 13% ' n.
priority, a == ==Llogo logn
n(n + 1)
W.."
6

---

On the Power of Learning-Augmenter Search Trees
There is a randomized data structure that maintains a B-Tree TB over U such that
score, as the reciprocal of the square of one plus working- set size. We will show that the working-set score is locally changed and there exists data structure that achieves the working-se set property. which states that the time to access an element is a logarithm of its working-set size.
1. Each item x has expected depth O logg(1 (1/w))))
2. Insertion or deletion of item x into/from T touches ( logg(1/ww) //2))) nodes in T in expectation.
The formal definitions and the main theorems in this section are presented as follows. We include more general results for dynamic B-trees and omitted proofs in Appendix D. Definition 4.1 (Previous and Next Access prev(i, and next(i, x)). Let prev(i, be the previous access of item z at or before time i, i.e, prev(i, = max (i' S i zx(i)) = x)- Let next(i, to be the next access of item x after time i, i., next(i, = min {i' > x<(²) = z].
3. Updating the weight of item x from w to w' touches O logn(w' (w////) nodes in T in expectation.
In addition, if B = (nn)/2=0)foo for some 5 > 0, all above performance guarantees hold with high probability - 6. If we are given the frequency fx for each a and set the priority as
m logg logn fz + +6g, ~ U(0,1): 1).
priority, ==
Definition 4.2 (Working-set Size work(i, Define the working-set size work(i, x)) as the number of distinet items accessed between the previous access of item x at or before time i and the next access of item x after time i. That is,
Then the total access cost O lz logn(m/(()) achieves the static optimality.
4. Dynamic Learning-Augmenter Search Trees
work(i, def (=)(pre((i,x)) + 1), x (next(i, If x does not appear after time i, we define work(i, x) == n.
In this section, we investigate the properties of dynamic search trees that permit modifications concurrent with se- quence access. Prioritizing items that are anticipated to be accessed in the near future to reside at lower depths within the tree can significantly reduce access times. Nonethe- less, updating the B-trees introduces additional costs. The overarching goal is to minimize the composite cost, which includes both the access operations across the entire se- quence and the modifications to the B-trees. In the main content, we specifically concentrate on the study of locally dynamic B-trees, which are characterized by the restriction that tree modifications are limited solely to the adjustment of priorities for the items being accessed.
Note that this definition captures the temporal locality and diversity of user behavior around item. Although it requires knowledge of future access items, it aligns conceptually with practices in recommendation systems, where temporal con- text 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 (Wang et al., 2021). In practice, we can approximate this score using causal proxies (e.g., past-only working-set set size) or apply machine learning models to predict it based on observable access patterns.
Definition 4.3 (Working-set Score Score x)). Define the time- varying score as the reciprocal of the square of one plus working-set size. That is,
Here, we construct dynamic that achieves the working-see set property. In data structures, the working set is the collection of data that a program uses frequently over a given period. This concept is important because it helps us understand how a program interacts with memory and thus enables to design more efficient data structures and algorithms. For example, if program is sorting a list, the working set might be the elements of the list it is comparing and swapping right now. The size of the working set can affect how fast the program runs. A smaller working set can make the program run faster because it means the program doesn't it need to reach out to slower parts of memory as often. In other words, if we know which parts of data structure used most, we can organize the data or even the memory in way that makes accessing these parts faster, which can speed up the entire program.
B-trees
w(i (1 + wor
Theorem 4.4 (Dynamic Search Tree with Working-set set Pri- ority). With the working-set size work(i, x) known and the branching factor B = M1In2 1-1 n), there is a randomized data structure that maintains a B-tree T over [n] with the priorities assigned as
priority (i. 2) = = -log, log (1 + work
1).
Upon accessing the item at time i, the expected depth of item x is O(log + work(i, x)). The expected total cost for processing the whole access sequence X is the following. The data structure satisfies the working-set property.
We define the working-set size as the number of distinct items accessed between two consecutive accesses. Corre- spondingly, we design a time-varying score, working-ser
cost X, ww) =0 (nlogg
Σ (1 + work((,
7

---

On the Power of Learning-Augmenter Search Trees
In particular, B O (n1/2-6) for some the guarantees hold with probability 1 8.
3000
3000G
Total Access Cost
Remark. Consider two sequences with length X, = (1,2.... 1,2, ,, ",, 1,2,-.. : n)) X2 = ,,,2,,,-..... 2. .... n, n, ... n.) Two sequences have the same total cost if we have a fixed score. However, X2 should have less cost because of its repeated pattern.
25000
2000C
15000
10000
Given the frequency freq time-invariant priority, by Theorem 3.1, the optimal static costs are
5000
Splly
2000
6000
10000
10000
20000
cost( 1 freq) = cost(Xx freq) = O(m log, n).
Number of Accesses
Figure 2. Zipfian distribution, a 1.
But for the dynamic BSTs, with the working-set score, we calculate both costs from Theorem 4.4 as
35000
cost X1, w) Om (n + 1)), cost (2, w) On loga n + m logo 3).
30000
Total Access Cost
25000
This means that our proposed priority can better capture the timing pattern of the sequence and thus perform better than the optimal static setting.
Werrded
Finally, use the following theorem to show the robustness of the results when the scores are inaccurate.
sokey
B-trod
mender sreep
2000
6000
10000
16000
20000
Theorem 4.5 (Dynamic Search Tree with Working-set Pri- ority). Given the predicted locally changed working-ser score @(t) E (0, 1)" satisfying (1)(1 = O(1), رركs 2 1/poly(n) (n) and the brunching factor B M1n n). there a randomized data structure that maintains B-Tree over the n keys such that the expected total cost for processing the whole access sequence X, cost(X (.)), is
Number Accesses
Figure 3. Adversarial distribution.
35000
30000
Total Access Cost
23000
m
20000
cost (x,)(,W) w.w)+O +0
logg (i))(() logg #
15000
Namm-bul
10000
loam
In particular, B (n ) for some ō > 0, the guar- antees hold with probability 1 8.
3000
b-tre
mandom treep
2000
6000
10000
30000
20000
Number
5. Experiments
Figure 4. Uniform distribution.
In this section, give experimental results that compare Treap (learn-bst) with learning- augmented BST (Lin et al., 2022) (learn-llw), learning- augmented list (Fu et al., 2025) (learn-skiplist) and classical search tree data structures including Red-Black Trees (red-black), AVL Trees (avl), Splay Trees (splay), B- Trees of order 3 (b-tree), and randomized Treaps (random- treap). Experiments are conducted in a similar manner in Lin al. (2022): (1) All keys are inserted in random order to avoid insertion order sensitivity.
of each item i as fa and its relative frequency as P: = fi/ All results are based on ten independent trials.
5.1. Perfect Prediction Oracle on Frequency
We first assume that we are given a perfect prediction or- acle on the item frequency. The data follows one of three distributions: the Zipfian distribution, the distribution de- scribed in Theorem 2.14 (adversarial distribution), and the uniform distribution. We set 1000 and vary over [2000, 6000, 10000, 16000, 20000]. The z-axis represents the number of unique items, and the y-axis denotes the number of comparisons made, which measures access cost.
(2) The total access cost is measured by the total number of comparisons needed while accessing keys.
We consider a synthetic data setting, with n unique items ap- pearing in a sequence of length m. We define the frequency
8

---

On the Power of Learning-Augmentcr Search Trees
200000
500000
190000
160000
402000
160000
150000
Total
200000
130000
spllyy
b-ree
120000
0.7
0.2
0.7
KL-Divergence
KL-divergences
Figure 5. Inacourate Prediction Oracle.
Figure 6. Relationship between total cost and KL divergence be- tween true and predicted frequency using our learning augmented treaps.
Zipfian Distribution. The Zipfian distribution with pa- rameter a has relative frequencies p; = "...... where Hn, = Ei=1 is the nhth generalized harmonic number of order a. In our experiment, we set a 1. As shown in Figure 2, our Treaps outperform all other data structures except (Lin et al., 2022), which explicitly assumes Zipfian distribution.
5.3. Total Cost and KL Divergence
In Theorem 2.13, we show that in our saaming-auggented treaps, when the frequency predictor is inaccurate, the ad- ditional cost increases linearly with the KL divergence between the true and predicted frequencies. We comple- ment this theoretical result with experiments using the same setup as in Section 5.2. Specifically, we set n 5000, m = 10000 and set the KL divergence to vary over [0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7). As shown in Figure the experimental results confirm that the additional cost grows linearly with the KI. divergence.
Adversarial Distribution. the proof of Theorem 2.14, we construct a distribution with relative frequency given by 2(x-(+1)
n(n++) We prove that using the priority assignment in (Lin et al., 2022), the expected depth is (n)). As shown in Figure 3, the data structure in Lin et al. (2022) per- forms significantly worse under this adversarial distribution compared to the Zipfian case, while our Treaps maintain the best performance among all data structures.
A Acknowledgments
Uniform Distribution. We also consider uniform distri- bution, where each item has a relative frequency p: n As shown in Figure Treaps outperform all other data structures as well.
We thank Chris Lambert, Richard Peng, Mars Xiang, and Daniel Sleator for their helpful discussions and insights, and Tian Luo, Samson Zhou, and Chunkai Fu for their insights on the experimental code.
5.2. Inaccurate Prediction Oracle on Frequency
Impact Statement
We consider the scenario where our learning-augmented Treaps are constructed based on an inaccurate prediction of item frequencies. The inaccuracy of the prediction is quantified using the KI. divergence between the relative frequency and the predicted relative frequency. Specifically, we initialize a uniform distribution and optimize it toward a target distribution with a specified KL divergence level using the Sequential Least Squares Programming (SLSQP) optimizer in SciPy (Virtanen et al., 2020). The r-axis repre- sents the KL divergence, while the y-axis denotes the total access cost. We
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
References
Aamand, A., Chen. J. Y., and Indyk, P. (optimal) online bipartite matching with degree information. 2022. URL https: httpss///ppenrevie net/ net/forum? i id=NgwrhCBPTVK.
5000 and m 10000.
As shown in Figure 5, our Treaps not only outperform the investigated alternatives but also exhibit a graceful degra- dation as the difference between the predicted and actual distribution increases. Additionally, we conducted other robustness experiments on mixtures of distributions, as de- tailed in Appendix
Adelson-Velskiz M. and Landis, E. M. An algorithm for the organization information. Technical report, Joint Publications research service Washington DC, 1963.
Allen, and Munro, Self-organizing binary search

---

On the Power of Learning-Augmented Search Trees
trees. J. ACM, 25(4):526-535, 1978.
für Informatik. ISBN 978-3-95977-164411 doi: D.420...G..APROXXRNNDDO....0.... URL https://dropa: /tttss///doops..dgstthh.ddddee Document/10.4230/LII APPROO RANDOM. 2020.33.
Aragon, C. R. and Seidel, R. Randomized search trees. In FOCS, volume 30, pp. 540-545, 1989.
Azar, Y., Panigrahi, D., and Touitou, N. Online graph algorithms with predictions. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). pp. 35-66. SIAM, 2022.
Chen, J., Silwal, S., Vakilian, A., and Zhang, F. Faster fundamental graph algorithms via learned predictions. In International Conference on Machine Learning, pp. 3583-3602. PMLR, 2022a.
Bädoiu, M., Cole, R., Demaine, E. D., and Iacono, J. A unified access bound on comparison-baser dynamic dic- tionaries. Theoretical Computer Science, 382(2):86-96, 2007.
Chen, J. Y., Eden, T., Indyk, P., Lin, H., Narayanan, S., Rubinfeld, R., Silwal, S., Wagner, T., Woodruff, D., and Zhang, M. Triangle and four cycle counting with predictions in graph streams. In International Confer- ence Learning Representations, 2022b. URL https: / / //openeevveww...mmmo/. net http://wwwweeetottteeeaaaaeeeeee ftw.:middd-iinnnghhhhaa
Bender, M. A., Ebrahimi, R., Hu, H., and Kuszmaul, B. C. B-trees and cache-oblivious b-trees with different-sized atomic keys. ACM Transactions on Database Systems (TODS), -33::1333, 2016.
Cole, R. On the dynamic finger conjecture for splay trees. part ii: The proof. SIAM Journal on Computing, 30(1): 44 85, 2000.
Bose, P., Douieb, K., and Langerman, S. Dynamic opti- mality for skip lists and b-trees. In Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, pp. 106-1114 Citeseer, 2008
Cole, R., Mishra, B., Schmidt, J., and Siegel, A. On the dynamic finger conjecture for splay trees. part i: Splay sorting log n-block sequences. SIAM Journal Comput- ing. 30(1):1-43,,000
Bose, P., Cardinal, J., Iacono, J., Koumoutsos, G., and Langerman, S. Competitive online search trees on trees. In Proceedings of the 14th Annual ACM-SIAM Sympo- sium on Discrete Algorithms (SODA), pp. 1878-1891. SIAM, 2020.
Cormen, H., Leiserson, E., Rivest, R. L.,, and Stein, C. Introduction to Algorithms, 3rd Edi- lion. MIT Press, 2009. ISBN 978-0-262-03384. 8. URL http://mitpress www.ttprrss.i.....m www.mi..edubbook.. imcroduction-algoriian
Brodal, G. S. and Fagerberg. R. Lower bounds for external memory dictionaries. In SODA, volume 3, pp. 546-554, 2003.
Cormode, G. and Muthukrishnan, S.
An improved data stream summary: the count-min sketch and its applica- tions. Journal of Algorithms, 55(1):58-75, 2005.
Brown, T. B-slack trees: Space efficient b-trees. In Ravi, R. and Gørtz, I. L. (eds.), Algorithm Theory - SWAT 2014 (Lecture Notes in Computer Science, vol. 8503), volume 8503 of Lecture Notes in Computer Science, pp. 122-133. Springer, Cham, 2014. doi: 10.1007/ 11. URL attps:// http/do.ooo//// org/
Demaine, E. D., Harmon, D., Iacono, J., and Patraşcu, M. Dynamic optimality- almoott SIAM Journal on Comput- ing, 37(1):240-251, 2007.
10. 1007
Demaine, E. D., Harmon, D., Iacono, J., Kane, D., and Patraşcu, M. The geometry of binary search trees. In Proceedings of the 20th annual ACM-SIAM symposium Discrete algorithms (SODA), pp. 496-505 SIAM, 2009.
Buchsbaum, A. L.,, Goldwasser, M. H., Venkatasubrama- nian, S., and Westbrook, J. R. On external memory graph traversal. In SODA, pp. 359-860,22 2000.
Canonne, C. L. A short note learning discrete distribu- tions. arXiv preprint ar arXiv: /457, 2020.
Derryberry, J. C. and Sleator, D. D. Skip-splay: Toward achieving the unified bound in the bst model. In Work- shop on Algorithmss and Data Structures, pp. 205. Springer, 2009.
Chalermsook, P.. Chuzhoy, J., and Saranurak, T. Pinning down the Strong Wilber Bound for Binary Search Trees. In Byrka, J. and Meka, R. (eds.), Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROXRANDOM 2020), volume 176 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 33:1-33:21, Dagstuhl, Germany, 2020. Schloss Dagstuhl- Leibniz-Zenntrum
Ding, J., Minhas, U. Yu, J., Wang, C., Do. J., Li, Y., Zhang, H., Chandramouli, B., Gehrke, J., Kossmann, D., et al. Alex: an updatable adaptive learned index. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, pp. 969-984, 2020.
10

---

On the Power of Learning-Augmented Search Trees
Dinitz, M., Im, S., Lavastida, T., Moseley, B., and Vassil- vitskii, S. Faster matchings via learned duals. Advances in Neural Information Processing Systems, 34:10393- 10406, 2021.
Iacono, Alternatives splay trees with (log n) worst- case access times. In Proceedings of the Twelfth Annual ACM-SIAM Symposium Discrete Algorithms, pp. 516- 522, 2001.
Ergun, J. C., Feng, Z., Silwal, S., Woodruff, D., and Zhou, S. auggennee SkS-means clustering. In In- ternational Conference on Learning Representations, httpl/ewweeeeeeeeeeeeeeeeeeeeeee net. forum?
Iacono, J. Key-independent optimality. Algorithmica, 42 (1):3-10, 2005.
2022. URL
Iacono, J. In pursuit of the dynamic optimality conjecture. In Space-Efficieee Data Structures, Streams, and Algorithms, pp. 236-250. Springer, 2013.
id=X8cLTHeXYyX.
Erlebach, T., de Lima, M. S., Megow, N., and Schlöter, query policies for mini- mum spanning tree with uncertainty. arXiv preprint NrXiv:2206.15211, 2022.
Jagadish, H., Narayan, P., Seshadri, S., Sudarshan, S., and Kanneganti, R. Incremental organization for data record- ing and warehousing. In VLDB, pp. 16-25, 1997.
Fagerberg, R., Hammer, D., and Meyer, U. On optimal balance in b-trees: What does it cost to stay in per- feet shape? In 30th International Symposium on Algo- rithms and Compulation (ISAAC 2019). Schloss Dagstuhl- Leibniz-7Zentrum fuer Informatik, 2019.
Jermaine, C., Datta, A., and Omiecinski, E. novel index supporting high volume data warehouse insertion. In VLDB, volume 99, pp. 235-246, 1999.
Jiang, T., Li, Y., Lin, H., Ruan, Y., and Woodruff, D. P. Learning-augmented data stream algorithms. ICLR, 2020.
Ferragina, P. and Vinciguerra, G. The pgm-index: a fully- dynamic compressed learned index with provable worst- case bounds. Proceedings of the VLDB Endowment, 13 (8):1 (8):1162-1175 2020.
Karpinski, M., Larmore, L. L., and Rytter, W. Sequential and parallel subquadratic work algorithms for construct- ing approximately optimal binary search trees. In SODA, pp. 36 41. Citeseer, 1996.
Ferragina, P., Lillo, F., and Vineiguerra, G. Why are learned indexes so effective? In International Conference on Machine Learning, pp. 312--312.. PMLR, 2020.
Kraska, T., Beutel, A., Chi, E. H., Dean, J., and Polyzotis, N. The case for learned index structures. In Proceedings of the 2018 international conference on management of data pp. 489-504, 2018.
Fu, C., Nguyen, B. G., Seo, J. H., Zesch, R. S., and Zhou, S. Learning augmented search data structures. In The Thir- teenth International Conference on Learning Represen- tations, 2025. URL https: pestps://opentee http:///ppeeeeeeeeeeeeeee .etee/eeiinneee/eeeee forum? dididd444 rbQQoWE3.
Lavastida, T., Moseley, B., Ravi, R., and Xu, C. Learnable and Distance-Rohine Predictions for Online Matching, Flows and Load Balancing. In Mutzel, P., Pagh, R., and Herman, G. (eds.), 29th Annual European Symposium on Algorithms (ESA 2021). volume 204 of Leibniz International Proceedings in Informatics (LIPles), pp. 59:1-59:17, Dagstuhl, Germany, 2021. Schloss Dagstuhl Leibniz- Zentrum für Informatik. ISBN 978- 3-95977-204-44 doi: 10.42300 waw.s
Golovin, D. Uniquely represented data structures with applications to privacy. PhD thesis, Carnegie Mellon University, 2008
Golovin, D. B-treaps: A uniquely represented alternative to b-trees. In Automata, Languages and Programming: 36th International Colloquium, ICALP 2009, Rhodes, Greece, July 5-12, 2009, Proceedings, Part I 36, pp. 487-499. Springer, 2009.
URL http::///oroes..dgettual.ddeeede http:/hh..deeetttttttteee (wtumeent/10.420/LPPPP. ESA. 2....022.11................ 2021.52 .59.
Lin, H., Luo, T., and Woodruff, D. Learning augmented binary search trees. In International Conference on Ma- chine Learning, pp. 13431-13440. PMLR, 2022.
Guibas, J. and Sedgewick, R. A dichromatic framework for balanced trees. In 19th Annual Symposium Foun- dations of Computer Science (sfes 1978), pp. 8-21. IEEE, 1978.
Lucas, J. M. Canonical forms for competitive binary search tree algorithms. Rutgers University, Department of Com- puter Science, Laboratory for Computer ..... 1988.
Hsu, C.-Y., Indyk, P., Katabi, D., and Vakilian, A. Learning- based frequency estimation algorithms. In International Conference on Learning Representations, 2019.
Margaritis, G. and Anastasiadis, S. V. Efficient range-based storage management for scalable datastores. JEEE Trans- actions on Parallel and Distributed Systems, 25(11):2851- 2866, 2013.
Hu, T. and Tucker, A. Optimum binary search trees. Tech- nical report, WISCONSIN UNIV MADISON MATHE- MATICS RESEARCH CENTER, 1970.

---

On the Power of Learning-Augmentted Search Trees
Mehlhorn, K. Best possible bounds for the weighted path length of optimum binary search trees. In Barkhage, H. (ed.), Automata Theory and Formal Languages, 2nd GI Conference, Kaiserslautern, May 20-23, 1975, vol- ume 33 of Lecture Notes in Computer Science, pp. 31-41. Springer, 1975a.
Wang, S., Cao, L., Wang, Y., Sheng, Q Z., Orgun, M. A., and Lian, D. survey session-based recommender systems. ACM Comput. Surv,, 54(7), July 2021. ISSN 0360-0300. doi: 10.1145/346541.. URL https:// doi woi.org/1000 10100.1114344655
Wu, J., Zhang, Y., Chen, S., Wang, Chen, Y., and Xing, C. Updatable learned index with precise positions. Proceed- ings of the VLDB Endowment, (48)):1766-12) 2021.
Mchlhorn, K. Nearly optimal binary search trees. Acta Informatica, 5(4):287-295, 1975b.
Mitzemmacher, M. and Vassilvitskii, S. Algorithms with predictions. Commun. ACM, 63-7):33-35, June 2022. ISSN 0001-0782, doi: 10. 10.1145/3528087. URL https: //doi www.o//g......o...... 114. 111.1..115/35580088
Yao, F. Speed-up in dynamic programming. SIAM Jour- nal Algebraic Discrete Methods, 3(4):532-540, 1982.
Yi, K. Dynamic indexability and the optimality of b-trees. Journal of the ACM (JACM), 59(4): 2012.
Munro, J. I. On the competitiveness of linear search. In Eu- ropean symposium algorithms, pp. 338-345. Springer, 2000.
Neil, P., Cheng, E., Gawlick, D., and O'Neil, E. The log-structured merge-tree (Ism-tree), Acta Informatica, 33:351-385, 1996.
Polak, A. and Zub, M. Learning- augmented maximum flow. Inf. Process. Lett., 186(C), August 2024. ISSN 0020- 0190. doi: 10. 1...0166/..pl..224116444 //doi.
URL https:
1016 ipl. 2024. 106487.
Rosenberg, A. and Snyder, L. Time-and space-optimality in b-trees. ACM Transactions Database Systems (TODS), 6(1) 1981.
Safavi, R. and Seybold, M. P. B-treaps revised: Write efficient randomized block search trees with high load. 19th Algorithms and Data Structures Symposium (WADS 2025), 2023. URL axxixpreprintarxxv:22000 04722.
Sleator, D. D. and Tarjan, R. E. Self-adjusting binary search trees. Journal of the ACM (JACM), 32(3):652-686, 1985.
Virtanen, P., Gommers, R., Oliphant, T. F., Haberland, M.,
Reddy, T., Cournapeau, D., Burovski, E., Peterson, P., Weckesser, W., Bright, J., der Walt, S. J., Brett, M., Wilson, J., Millman, K. J., Mayorov, N., Nelson, A. R. J., Jones, E., Kern, R., Larson, E., Carey, C. J., Polat, i., Feng, Y., Moore, E. W., VanderPlas, J., Laxalde, D., Perktold, J., Cimrman, R., Henriksen, I., Quintero, F. A., Harris, R., Archibald, A. M., Ribeiro, A. H., Pedregosa, F., van Mulbregt, P., and SciPy 1.0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17:261-272, 2020. doi: 10. 10.10888441592-09-06666
Vitter, J. S. External memory algorithms and data structures: Dealing with massive data. ACM Computing surveys (CsUR), 33(2)2209-271, 2001.
12

---

On the Power of Learning-Augmented Search Trees
A. Other Related Works
Beyond Worst-Case Analyses of Binary Trees. Binary trees are among the most ubiquitous pointer-based data structures. While schemes without re-balancing do obtain (logg n) time bounds the average case, their behavior degenerates to (()) on natural access sequences such as 1, 2, 3, ......... n. To remedy this, many tree balancing schemes with (logg n)) time worst-case guarantees have been proposed (Adelson- Adelson-Vellkii & Landis, 1963; Guibas & Sedgewick, 1978; Cormen et al., 2009).
Creating binary trees optimal for their inputs has been studied since the 1970s. Given access frequencies, the static tree of optimal cost can be computed using dynamic programs or clever greedies (Hu & Tucker, 1970; Mehlhorn, 1975b; Yao, 1982; Karpinski et al., 1996). However, the cost of such computations often exceeds the cost of invoking the tree. Therefore, a common goal is to obtain a tree whose cost is within a constant factor of the entropy of the data, multiple schemes do achieve this either on worst-case data (Mehlhorn, 1975b), or when the input follows certain distributions (Allen & Munro, 1978).
A major disadvantage of static trees is that their cost on any permutation needs to be 22 log2 n). On the other hand, for the access sequence 1, 2, 3,...... n. repeatedly bringing the next accessed element to the root gives a lower cost O(n). This prompted Allen and Munro to propose the notion of organiiign binary search trees. This scheme was extended to splay trees by (Sleator& & Tarjan, 1985). Splay trees have been shown to obtain many improved cost bounds based on temporal and spatial locality (Sleator & Tarjan, 1985; Cole et al., 2000; Cole, 2000; Iacono, 2005). In fact, they have been conjectured to have access costs with a constant factor of optimal on any access sequence (lacono, 2013). Much progress has been made towards showing this over the past two decades (Demaine et al., 2009; Derryberry & Sleator, 2009; Chalermsook et al., 2020; Bose et al., 2020).
From the perspective of designing learning-augmented data structures, the dynamic optimality conjecture almost goes contrary to the idea of incorporating predictors. It can be viewed as saying that learned advice do not offer gains beyond constant factors, at least in the binary search tree setting. Nonetheless, the notion of access sequence, as well as access- sequence-dependen bounds, provides useful starting points for developing settings. In this paper, we choose focus on bounds based temporal locality, specifically, the working-set bound. This is for two reasons: the spatial locality of an element's next access is significantly harder to describe compared to the time until the next access; and the current literature on spatial locality-based bounds, such as dynamic finger tends to be much more involved (Cole et al., 2000; Cole, 2000). We believe an interesting direction for extending our composite scores is to obtain analogs of the unified bound (lacono, 2001; Bădoiu et al., 2007) for B-Trees.
cnadiction-dependedd search trees in online
B-Trees and External Memory Model. Parameterized B-Trees (Brodal & Fagerberg, 2003) have been studied to balance the runtime of read versus write operations, and several bounds have been shown with regard to the blocks of memory needed to be used during operation. The optimality is discussed in both static and dynamic settings. Rosenberg & Snyder (I (1981) compared the B-Tree with the minimum number of nodes (denoted as compact) with non non-compact B- B-Trees and with time-optimal B-Trees. Bender et al. (2016) considers keys have different sizes and gives a cache-oblivious static atomic-key B- B-eree achieving the same asymptotic performance as the static B-Tree. When it comes to the dynamic setting, the trade-off between the cost of updates and accesses is widely studied (O' (O'Neil et al., 1996; Jagadish et al., 1997; Jermaine et al., 1999; Buchsbaum et al., 2000; Yi. 2012). Bose et al. (2008) studied the dynamic optimality of B-Trees and presented self-adjusting B-Tree data structure that is optimal up constant factor when B is constant.
B-Treap were introduced by Golovin (2008; 2009) as way to give an efficient history-independeen search tree in the external memory model. These studies revolved around obtaining O(log n2) worst-case costs that naturally generalize Treaps. Specifically, for sufficiently small B (as compared to n), Golovin showed a worst-case depth of O log n) with high probability, where B= 12(1n 1/1-a) ri). The running time of this structure has recently been improved by Safavi & Seybold (2023) via two-layer design.
The large node sizes of B-Trees interact naturally with the external memory model, where memory is accessed in blocks of size B (Brodal& & Fagerberg, 2003; Vitter, 2001). The external memory model itself is widely used in data storage and retrieval (Margaritis& & Anastasiadis, 2013), and has also been studied in conjunction with learned indices (Ferragina et al., 2020). Several previous results discuss the trade-off between update time and storage utilization (Brown, 2014; Fagerberg et al., 2019).
13

---

On the Power of Learning-Augmented Search Trees
B. Proofs of Treaps
In this section, we formally prove the properties of traditional treaps Section 2 and the static optimality of our learning- augmented BST in Section 2.2.
Lemma 2.2 (Araaon & Seidel, 1989)). Let (0, 1) be the uniform distribution over the real interval [o, 1]. If priority (0, 1)", each Treap node a has depth (log, n) with high probability.
Proof. Notice that dz)th(z),, the depth item x in the Treap, the number of ancestors of in the Treap. Linearity of expectation yields
E dl [z)]
E [1y an ancestor of s}]
vE(n)
Σ
Pr (y is an ancestor of x)
v (xc
Σ
Pr
priority,
max priority:
yE(n
Σ
=logg n).
y +
vEnn
Theorem 2.8. For any item x E [n]]. we set its priority as
priority, = -010 logg log2
m
f + 8r og ~ U0, 1).
In the corresponding Treap, each node has expected depth (m/ Therefore, the total time for processing the access sequence is OlE, Ja (z))), which matches the performance of the optimal static BSTs up constant factor.
Proof.
Given item frequencies, we define the following w assignment:
fr
W2
E [n].
(4)
m
One can verify that ||w|| = 0(1). By Theorem 2.4, the expected depth of each item æ is O(log, (m/ ff)))))
C. Learning-Augmented B-Trees
We now extend the ideas above, specifically the composite priority notions, to B-Trees in the External Memory Model. We show that the learning-un auggeened B- B-Treaps (Appendix C.1) obtain static optimality (Appendix C.2) and is robust to the noisy predicted scores (Appendix C.3). This model is also the basis of our analyses in online settings Appendix D.
C.1. Learning-Augmenteed B- B-Treaps
We first formalize this extension by incorporating our composite priorities with the B- E-Treap data structure from (Golovin, 2009) and introducing offsets in priorities.
Lemma C.1 (B-Treap. (Golovin, 2009)). Given the unique binary Treap (T, priority,) over the set of items [n] with their associated priorities, and target branching factor B uniformly from (0, 1), such as Lookup, Insert, and Delete of an item to touch O log n) nodes in TB in expectation.
n) for some O. Assuming priority, are drawn maintain B- Tree T. called the B-Treap, uniquely defined by T. This allows operations
In particular, if B (222/266 for some 8 all above performance guarantees hold with high probability.
The main technical theorem is the following:
14

---

On the Power of Learning-Augmented Search Trees
Theorem C.2 (Learning-Augmentn B-Treap via Composite Priorities). Denote w (w1,'. ". w,, E (0, 1)2h as a score
associated with each element of [n] such that ||w]| O(1) and a branching factor 12(1n 12(1n1/(110) 1/11-a) randomized data structure that maintains B- Tree T over such that
n), there is a
1. Each item has expected depth O Jogg(1/wg))
2. Insertion or deletion of item x into/from T touches O logg (1/w())))) nodes in T in expectation.
3. Updating the weight of item x: from w to we touches O p /w]l) nodes TB in expectation.
We consider the following priority assignment scheme: For any and its corresponding score was we always maintain:
1
priority == -logg logg
+ U(,,11
We
In addition, B (2-6626)) for some 6 0, all above performance guarantees hold with high probability 1 5.
The learnin--uggeened B- B-Treap is created by applying Lemma C.1 to a partition of the binary Treap T. Each item æ has a priority in the binary Treap T, defined as:
priority, - -- log2 logn
da oz U), for all U.
Wx.
We then partition the binary Treap I based on each item's tier. The tier of an item is defined as the absolute value of the integral part of its priority, i.e., Tx
der llog log (1/ (1/w=)J.
Proof of Theorem C.2. To formally construct and maintain B we follow these steps:
1. Start with a binary Treap (T' priority..) with priorities defined using equation (5).
2. Decompose T into sub-trees based on each item's 's tier, resulting set of maximal sub-trees with items sharing the same tier.
3. For each T; apply Lemma C.I maintain B- B-Treap 7:55
4. Combine all the B-Treaps into single B-Tree, such that the parent of root(T?) is the B-Tree node containing the parent of ro.
Now, let's analyze the depth of each item v. Keep in mind that any item in the same B-Tree node shares the same tier. Therefore, we can define the tier each B-Tree node as the tier of its items.
Suppose F1, .2.... are the B-eree nodes we encounter until we reach The tiers of these nodes are in non-inereasing order, that is, Tx; 2 Tai11 for any We'll define C₁ the number of items of tier I for any As per the definition (refer equation (5)), we have:
C = O(B2), for all
Using Lemma C.1 and the fact that B O(C)/2), 1, find that the number of nodes among of tier is O logg Ct) = 0(2 /a) with high probability. As a result, the number of nodes touched until reaching is, with high probability:
002 -0
(0 log
1
Wi
This analysis is also applicable when performing Lookup, Insert, and Delete operations on item œ.
The number of nodes touched when updating an item's weight can be derived from first deleting and then inserting the item.
15

---

On the Power of Learning-Augmented Search Trees
C.2. Static Optimality
In this section, we show that with our priority assignment, the geaniig--uugented B-Treaps are statically optimal. Let ax1), (2)..... ................................ (m)) represent an access sequence of length We define the relative frequency of each item as der HiE ml =(0==)) A static B-Tree statically optimal the depth of item æ is: Px
dæpth(x) = (108.B ) for all [m]] par
As corollary of Theorem C.2, we show that if we are given the relative frequency Pes the Garning-augmenter B-Treaps def
with our priority assignment achieves Static Optimality with weights Wy Px--
Corollary C.3 (Static Optimality for B-Treaps). Given the relative frequency P2 of each item x E [pi], and a branching factor B -2( n),, there exists a randomized data structure that maintains a B-Tree T over [n] such that each item
has an expected depth of O(lgg 1/Pa). That TB achieves Static Optimality, meaning the total number nodes touched O OOOPT in expectation, where:
OPT
dal
Σ #E(N]
Pz log
1 Pr.
(6)
Furthermore, B -(nn/2-5) for some 8 >> 0, all above performance guarantees hold with high probability.
C.3. Robustness Guarantees
In practice, would not have access to the relative frequency Pa. Instead, we will have inaccurate prediction dz- Let and q be the probability distribution over [n] such that p(x)) Pr: q(x) = yz- In this section, we will show that B-Treap performance is robust to the error. Specifically, we analyze the performance under various notions of error in the prediction. The notions listed here are the ones used for learning discrete distributions (refer to (Canonne, 2020) for comprehensive discussion).
Corollary C.4 (Kullback Leibler (KL) Divergence). If we are given a density prediction q such that dx (p: q) E. Pa In(px/q:) S e, the total number of touched nodes is
o (OPT
cm In B
Proof.
Given the inaccurate prediction g. the total number of touched nodes in T is
o Σ m pr loga
Σ m Pr log
+ m
Σ Pr
log
Pr
Pr
dkz(p:))
OOOTT static
+
In
Corollary C.5 (x2). we we are given a density prediction such that (p: = Ex -qx)2 /g S 6, the total number of touched nodes is
(
cm In B
Proof. The corollary follows from Corollary C.5 and the fact dxz (p: q) S x²(pp)) S..
Corollary C.6 (Loo Distance). If we are given density prediction such that ||p gl1o0 the total number of touched nodes is
(OPT m log + en))
16

---

On the Power of Learning-Augmentted Search Trees
Proof. For item with its marginal probability smaller than 1/1000n, its expected depth in the B-Treap is O(log n) using either Ps or Or its score. If item x's marginal probability is least 1 1/1000n, the Loc distance implies that
Pz
Pe
Pa
1000 + En)
P3
Pz
(1000m))
Therefore, item æ's expected depth in the B-Treap with score q is roughly
O
[ogg
1
+
logg
Pe 0
1 logg
+
log + en)
Pr.
Un
Pr.
The corollary follows.
Corollary C.7 (L2 Distance), If we are given a density prediction q such that ||p qll S the total number of touched nodes is
O (OPTH log (c))
Proof. This claim follows from Corollary C.6 and the fact ||p- alloo I 1p- Sc
Corollary C.8 (Total Variation). If we are given a density prediction q such that drv (p, q) = 0.5llp - -/11 S e, the total number of touched nodes is
O (OPTHO + m mogog(11 cen)
Proof. This claim follows from Corollary C.6 and the fact |p al I 1p 4111 2c.
Corollary C.9 (Hellinger Distance). If we are given density prediction q such that du (p. q) 0.5|| /p vgll2 S the total number of touched nodes
O (OPT + m log + en))
Proof. This claim follows from Corollary C.6 and the fact 1pp - allo0 S 2/2dd S 22.2.
D. Dynamic Learning-Augmmnteed Search Trees
In this section, we investigate the properties of dynamic B-trees that permit modifications concurrent with sequence access. Prioritizing items that anticipated to be accessed in the near future reside at lower depths within the tree significantly reduce access times. Nonetheless, updating the B-trees introduces additional costs. The overarching goal is to minimize the composite cost, which includes both the access operations across the entire sequence and the modifications to the B-trees. We specifically concentrate on the study of locally dynamic B-trees, which are characterized by the restriction that tree modifications are limited solely to the adjustment of priorities for the items being accessed.
In Appendix D.I, we give the total cost guarantees for any locally dynamic B-trees. Appendix D.2, we establish the robustness guarantees in the context of imprecise priority scores, which may be given from learning oracle. In Appendix D.3, we demonstrate that the dynamic surning--uggment set size - the number of distinct items requested between two consecutive accesses achieves the working set property. Full details are included in the appendix. Finally, in Appendix D.4, we analyze the general dynamic B-trees with general time-varying priorities.
B-trees with specific priority based on the working
D.I. Locally Dynamic B-trees
Our objective is to maintain a data structure that minimizes the total cost of accessing the sequence S given the time-varying score w(i) E (o, 1)", i E (m] associated to each item. Here, we focus on the dynamic B-trees that update the priorities of only the items being accessed at any given moment, leaving the priorities of all other items unchanged. We refer to these as locally dynamic B-trees.
17

---

On the Power of Learning-Augmented Search Trees
Given n items, denoted [n] = (., ,n), and a sequence of access sequence X (e(T),...,,f( where x(i) [n]. At time [m]] there exists some time-dependent score Wij associated with each item E [n]. Let w(i)) wi,n) (".,,
E (0, 1 be the time-varying score vector. The score w(t) is defined to be locally changed if it only differs from the previous score vector at the index of the item being accessed. In other words, at each time i E f1,2, ... .n), we have Wi.j = 1,j for any a =r)). The locally dynamic B-Treap is then defined as a B- B-Treap whose priorities are updated according to the locally changed score. For any vector w, we write log w as the vector taking the element-wise log on w. give the guarantees in Theorem D.I.
Theorem D.I (Locally-Dynamic B-Treap with Given Priorities), Given the locally changed scores w((i E (0, 1)", E [m]] satisfying w O(1) and a branching factor B = 12(In" n), there is a randomized data structure that maintains B-Tree T over [n] such that when accessing the item x(1) at time i, the expected depth of item x(i) is O(logn we ). The expected total cost for processing the whole access sequence X is
(000) | n + Σ logn
cost cost(X, x, _)) -0
=00
w1,z(()
Moreover, if B ( for some 8 > 0, the guarantees hold with probability 1 8.
5.
The proof is an application Theorem C.2, where the priority function dynamically changes as time goes on, rather than the Static Optimality case where the priority is fixed beforehand.
Proof of Theorem D.I. Initially, we set the priority for all items to be 1, and insert all items into the Treap. For any time i [m]. for j E [n] such that W;-1. o way we set
priority," (9) = - log 1 + 615 dig ~ UO,, 1).
Wa,j
Since [|w((t]] O [m], by Theorem C.2, the expected depth of item s(i) is O(logB w.,r(r) The total cost for processing the sequence consists of both accessing æ(1) and updating the priorities. The expected total cost for all the accesses is
logg W1,2(1)
Then will calculate the cost update the Treap. Since the priority of an item only changes when it is accessed. Updating the priority of (i) from w;-1,x(() to Wi,((s) has cost
o ( [ogn wi-1.a(i)
wix(())
Hence we can bound the expected total cost for maintaining the Treap by
m72
W1- ((x(
o n logg n +
log
W7 (),0(()
i=2
m
=0 n log n +
log (),
Together the expected total cost is
O logg n +
log wi,(()
The high probability bound follows similarly as Theorem C.2.
18

---

On the Power of Learning-Augmented Search Trees
D.2. Robustness Guarantees
We have shown that given time-varying scores associated with each item w(i), there exists a B-Tree that gives us the total cost in terms of the scores. In this section, we address scenarios in which precise score w(i) not accessible. Utilizing learning oracle that predicts the logarithm of the score, demonstrate that the total cost incorporates additive term corresponding to the mean absolute error (MAE) of the logarithm of the scores Σ log Wi,a(s) log Wi,( We predict the logarithm of the score instead of itself to better capture the scale of it.
Theorem D.2 (Locally Dynamic B- B-Treap with Predicted Scores). Given the predicted locally changed scores i(i)) E (0,1)" 1)" 1-1 n), there is a randomized data structure
satisfying (1]01 = O(1), mii 2 1/poly(n) and a branching factor = Qi(nn that maintains a B-Tree over the n keys such that the expected total cost for processing the whole access sequence is
cost( (X, 1)) cost( X, w) +0
Σ logg ((,((() logg w.z(ol
Moreover, if B (n11/2-6) ( for some 0, the guarantees hold with probability 6.
Proof. We apply Theorem D.I with the predicted score wi)) and get the expected total loss is
m
1
cost(X,, () 0 n log n
logB (i,((()
<cost(X, + +0 m log Wi,r(1)
log Wi
m
=cos((X, (X,xX,,) w) +
Σ
log (),a(()) - log wia
D.3. Working Set Property
In data structures, the working set is the collection of data that a program frequently given period. This concept is important because it helps us understand how a program interacts with memory and thus enables us to design more efficient data structures and algorithms. For example, if a program is sorting a list, the working set might be the elements of the list it is comparing and swapping right now. The size of the working set can affect how fast the program runs. A smaller working set can make the program run faster because means the program doesn't need to reach out to slower parts of memory as often. In other word, we know which parts of a data structure are used most, we can organize the data or even the memory way that makes accessing these parts faster, which can speed up the entire program.
In this section, construct dynamic learning- auggeetee B B-treaps that achieve the working set property. We define the working-set set size as the number of distinct items accessed between two consecutive accesses. Correspondingly, we design vire-ngrying score, working-sed set score, as the reciprocal of the square of one plus working-set size. We will show that the working-set score is locally changed and there exists a data structure that achieves the working-sel property, which states that the time to access an element is logarithm of its working-set size. The formal definition of the working-set size and the main theorems in this section are presented as follows.
Definition D.3 (Previous and Next Access prev(i, x) and next(i, x)). Let prev(i, x)) be the previous access of item æ at or before time i.c, prev(i, 2) = max (i' < il x(1') =} Let next to be the next access of item æ after time i, i.c. next(i, .)) min (i' (r') = x)
Definition D.4 (Working-set Size x)) Define the working-sel Size work(i, be the number of distinct items accessed between the previous access of item or before time i and the next access of item after time i. That is,
work(i, def (x(ppre((i, 1),... (inext(i,x)))
If x does not appear after time i, we define work(i, x)) n.
19

---

On the Power of Learning-Augmented Search Trees
Theorem D.5 (Dynamic B-Treaps with Working-set Priority). With the working-sel size work(i, x) known and the branching factor B -2(1n 1.1 n.), there is randomized data structure that maintains B-Tree T over [n] with the priorities assigned
priority(i, x) = -log, log - work(1, x)){ (1
U(0,
Upon accessing the item time i, the expected depth of item is O(log work(i, x)). The expected total cost for processing the whole access sequence X is
m
cost X,
,est(X,,iiont priority) =0 log
Σ
log work(i,
In particular, if (nn0/2nn))))))) for some å 0, the guarantees hold with probability 1 6. 6.
1, .n)) X2 Remark. Consider two sequences with length m, X1 = 21,2,--. ... n, 1,2, 2, ......... n, ...... ,,,,, 1,, 2, 2. n. n. ,T). Two sequences have the same total cost if we have a fixed score. However, X2 should have less cost because of its repeated pattern. Given the frequency freq as time-invariant priority, by Corollary C.3, the optimal static costs
cost( (x,, freq)= = cost 22, freq) = Omm logg n).
But for the dynamic B-Trees, with the working-set score, calculate both costs from Theorem D.5
cost (X1, () (m log 1)), cost (2, = Om log n + m log 3).
This means that our proposed priority can better capture the timing pattern of the sequence and thus can even do better than the optimal static setting.
The main idea to prove Theorem D.5 is to show that (1) the working-set size is locally changed and (2) the corresponding priority satisfies the regularity conditions in Theorem D.1. To complete the proof, we introduce the interval-set size interval .). See Figure as an illustration.
Definition D.6 (Interval-set Size interval(i,z)). Define the Interval-set Size interval(i, to be the number of distinct items accessed between time i and the next access of item after time i. That is,
interval(i, .) = (xii + 1), ... =(nnxt(i,
If x does not appear after time i, we define interval(i,
Furthermore, we define the working-set set score as follows.
Definition D.7 (Working-set Score wi, Define the time-varying priority as the reciprocal of the square of one plus working-set size. That is,
w(1,x)) = (1+ + work(i, x))²
Next, we will show that the interval set priority is O(1) for any time i E [m] in Lemma D.8. The proof has three steps. Firstly, the interval-set size at time is always permutation of [n). Secondly, for any i E [m]] x E [n]. the working-set size is always no less than the interval-set size. Therefore, for any E [m]]the l norm of working-set score vector wii) def (w(i, 1),... wi, m)) can be upper bounded by E/-1/ j)² = O(1).
Lemma D.8 (Norm Bound for Working-set Score), Fix any timestamp i [m]]
Σ wii 0(1).
20

---

On the Power of Learning-Augmentte Search Trees
3
4
6
7
8
prev(l,x)
next((,
X(I)
3
2
3
...
interval(i. x) = [xx( 1), .. xxnex(((tx
3
1
1
3
2
1
3
2
2
1
1
interval x): # of distinct elements
3
work [=(prre(i. X) 1),, TM X (nextt(i x))]
work(l, x):# of distinct elements
3
3
3
2
3
3
3
3
2
2
3
3
2
Figure 7. An example of n 3, X = 1,,,,,, For any i, work(i) permutation of [n]] interval(i, x) 2 work(i, interval(i, 2) changes only when az) (highlighted in orange).
Proof. We first show that at any time E [m]] the interval-set size permutation of [n]. By definition, interval x) the number of items y such that next(i, y) $ next(i, 2:). Let TT, Ty be a permutation of all items [n] in the order of increasing next(i, Then for any item interval(i, is the index of x in æ. So the of the reciprocal of squared interval(i, is upper bounded by
(1 [1+ = 0(1)
+ interval (i)
Secondly, recall that prev(i, and hence for any i E [m], [m]. work(i, interval(i, x)). So have the upper bound for working-set score as follows.
((,
(1 work(i,
1 j=1
(1 + interval (i, j))²
0().
Since we have shown the working-set has constant I norm and in each timestamp, only update item's priority. We are ready to prove and show the efficiency of the corresponding B- B-Treap.
Proof of Theorem D.5. By Lemma D.8, we know ||<( O(1), for all i [m]] Also by definition of work(i, x)) for any E [n], work(i - 1,x) F work(i, .) only when z1i) = So for each time i, at most one item (i.e., xz1)) changes its priority. So we apply Theorem D.1 with wa, = (ii x), [mm]. E [ni]. and get the total cost
=
0 nnlog + Σ logs work(i,
Furthermore, we use the following theorem to show the robustness of the results when the scores are inaccurate, This is a direct corollary Theorem D.2.
Theorem D.9
B-Tre B-Treaps with Predictions). Given the predicted locally changed working-see set score w(i) E (0, 1)" satisfying [ū(() O(1), Wig 2 1/poly(n) and the branching factor B 22(nn' n), there
21

---

On the Power of Learning-Augmentce Search Trees
randomized data struclure that maintains B-Tree over the keys such that the expected total cost for processing the whole access sequence X is
logg Wi,z(0) logg (roctol)
cost (x cost(X w) )
In particular, if B On some ò 0, the guarantees hold with probabillity 1 6.
D.4. General Results for Dynamic B-Trees
In this section, we give the results for general dynamic B-trees. We first construct the dynamic B-Treaps and give the guarantees when we have access to the real-time priorities for each item in Appendix D.4.1. Then analyze the dynamic B-trees given the estimation the time-varying priorities in Appendix D.4.2. We use the same notation in Appendix D.
D.4.1. DYNAMIC B-TREAP WITH GIVEN PRIORITIES
Theorem D.10 (Dynamic B-Treap with Given Priorities). Given the time-varying scores w(i) E (0,1)", i [m] satisfying [|)(i)]]1 = (1) and branching factor B = 12In 1.1 n), there a randomized data structure that maintains a B-Tree TB over [n] such that when accessing the item z(i) time i, the expected depth of item æ(i) is Ollgg wi.ct))) The expected
total cost for processing the whole access sequence X is
cost w) = =0 log n2 +
log
log
log
Wi,a(()
Wi,i
Wi- 1,
2=
In particular, B 12222226) for some O, the guarantees hold with probability 6.
Proof. Initially, we set the priority for items to 1, and insert all items into the Treap. For any time i [m], for E [v]]
such that W;-1,j j Wi.j we set
priority, -log log _ + 6ij, 0zg ~ U(0,)) 1).
Wi,j
Since [|w(t)]l1 O(1), [m], by Theorem C.2, the expected depth of item s(i) is O(log w;,nt)) ). The total cost for processing the sequence consists of both accessing æ(i) and updating the priorities. The expected total cost for all the accesses is
log
wiz(()
Then we will calculate the cost to update the Treap. Updating the priority of j from w1-1. to WAy has cost O() (W1=((5-// Hence we can bound the expected total cost for maintaining the Treap by
Wi Wi-1.
O
n logg n +
log
Wij
Together the expected total cost is
o
log n +
log
log Wi.j
log wi-15
(i.z(i)
The high probability bound follows similarly as Theorem C.2.
Remark. The total cost for processing the access sequence has three terms. The first two terms are the same as in the static optimality bound, while the third term is incurred from updating the scores. Hence, here a trade-off between the costs of updating items and the benefits from the time- vare-iarying scores. Morcover, the locally-dynamic B-trees can avoid the high cost of keeping updating the scores because only one score is changed per time.
22

---

On the Power of Learning-Augmented Search Trees
D.4.2. DYNAMIC B-TREAP WITH PREDICTED PRIORITIES
In this section, give the guarantees for the dynamic B-Treaps with predicted priorities learned by machine learning oracle. Similar as in Appendix D.4.2, we here predict log, ws.5 to better capture the scale of the scores. And we will find that the total cost using the B-Trees using the predicted scores is equal to the cost using the accurate priorities plus an additive error that is linear the mean absolute error of prediction scores:
logg Wi,j
log
Wis
Theorem D.11 (Dynamic B-Treap with Predicted Scores). Given the predicted time-varying scores ((i)) E (0, 1)" satisfying [i(1) (1). Wis 2 1/poly(n) and branching factor B M2(n - n), there is a randomized data structure that maintains a B-Tree over the n keys such that the expected total cost for processing the whole access sequence X is
cost X, w) cost(X X, w) +0
logn logn Ws.j
Wi.
In particular, if B O(nnnnnn)nnpppnn some ò 0, the guarantees hold with probabiliiyy 1 6. 6.
Proof. We apply Theorem D.10 with score w, and get the expected depth of xxi) is
o 0
logg Wi.j
1
The expected total cost is
77
72
cost(X (X () =0 n nnlog n
log (),)(())
log Wi.j
log Wl 1..
2=2 j=1
=cost(X, [, w)) +0
Σ
m
log
1
log (1,2(()
(1,w(())
1 n m
+0
logg wi.j
log
log wi.j
log Wi.j
i=1 j=1 Wis
m x0
=cost w) +0
log wi.
log Wi.
E. Additional Experiments on Inaccurate Prediction Oracle
F. Mixture of Distributions
consider a setting where the actual data follows mixture two distributions while the frequency predictor provides only single distribution. Specifically, we assume that the predicted frequency follows the adversarial distribution, whereas the actual access sequence generated by a mixture of distributions: with probability w, the item follows the adversarial distribution and with probability 1 it follows the Zipfian distribution (Figure 8a, Figure 8c, Figure 8e) uniform distribution (Figure 8b, Figure 8d, Figure 8f). We set n 1000 and vary over [2000, 6000, 10000, 16000, 20000). The axis represents the number of unique items, and the y-axis denotes the number of comparisons made, which measures access cost. We compare our Treaps against Splay trees and randomized Treaps. Our experiments show that our Treaps outperform both alternatives, even when 75% the data comes from an unknown distribution (either Zipfian or uniform). Furthermore, as the prediction quality decreases, the performance our Treaps remains stable, demonstrating their robustness.
23

---

On the Power of Learning-Augmente Search Trees
leamning-aug random-trzap sp ay
learning-aug random-treap treap splay
20000
102a1 Pccess Lost
1otal ACCeSS Lestt
25320
09300
20000
15:00
20000
18000
Number Accesses
Number of Accesses
Zipfian mix, 25%
(b) Uniform mix, 25%
leaminng-ett sug random trzap
learning-aug random- treap splay
sp ay
(ocal ACCesS LOST
25300
tocal ACC e55 Lost
13000
10:000
3002
uSS Number Accesses
AKG
Number of Accesses
Ziplian mix, 50%
(d) Uniform mix, 50%
10000
leamiin--aug aug random trapp sp
25000
learning-oug random treap splay
lotal ACCeSS LOST
25320
(otal ACcess LOst
25000
21388
33000
10000
3000
A13I
MB00
M40
mett
ARC
Number of Accesses
Number of Accesses
(e) Zipfian mix, 75%
(1) Uniform mix, 75%
Figure 8, Error rates under mixture distributions. Left column: Zipfian mixing; Right column: uniform mixing.
24


Reviews:
[{"review_id": "VPsfvHSC4r", "reviewer": "Reviewer_HPYf", "summary": "Authors propose the following kind of binary search trees:\nreceiving prediction about the frequencies of all items,\ntheir algorithm produces a tree which achieves static optimality\n(up to a constant factor) and its cost smoothly deteriorates\nwith prediction error.\nThey extend their result to B-trees.\nAuthors also propose predictions of working set size to produce\na dynamic B-tree, where $B \\geq \\omega(\\log n)$, which satisfies\nworking-set bound and its cost smoothly deteriorates with prediction\nerror.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your comments! We will address your concern as follows.\n\n**Robustness and Bad Predictions**\n\nWe 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.\n\nUsing 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]). \n\nHowever, 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$. \n\nIn 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.\n\n\n**Worst-case Bound**\nIn 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. \n\nWe will revise Line 310 as follows to clarify this point:\n\n>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.\n\n\n**Branching Factor**\nThe 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.\n\n\n[1] Mitzenmacher, Michael, and Sergei Vassilvitskii. \"Algorithms with predictions.\" Communications of the ACM 65.7 (2022): 33-35.\n\n[2] Zeynali, Ali, Shahin Kamali, and Mohammad Hajiesmaili. \"Robust Learning-Augmented Dictionaries.\" International Conference on Machine Learning. PMLR, 2024.\n\n[3] Lin, Honghao, Tian Luo, and David Woodruff. \"Learning augmented binary search trees.\" International Conference on Machine Learning. PMLR, 2022.", "claims_and_evidence": "Their claims are rigorously proved. However, have some troubles\nunderstanding the claims about the robustness of their data structures.\nI wonder whether there might be a misunderstanding on my side and authors\ncan explain that.\nLooks to me that the statements of their theorem do not imply that\ntheir tree is never worse (even with very bad predictions) than a balanced\ntree built without any information about the input sequence.\nE.g., they seem to claim that their tree has $O(\\log n)$ worst-case depth (line 310),\nbut I do not see how does Thm 2.13 claim this.", "methods_and_evaluation_criteria": "methods and evaluation criteria look reasonable.", "theoretical_claims": "I did not check any proof completely, but the arguments look reasonable.", "experimental_designs_or_analyses": "Authors replicate experiments from the previous theoretical work. I find\nthis enough for a mainly theoretical paper.", "relation_to_broader_scientific_literature": "Topic of this paper are relevant and fits well within existing\nliterature on learning-augmented algorithms.\nIn particular, BST is a prominent problem and deserves study in\nthe learning-augmented setting.", "essential_references_not_discussed": "I am not aware of any omissions.", "other_strengths_and_weaknesses": "Strengths:\n\n* authors study an important problem which is not yet understood in the\nlearning-augmented setting.\n\n* authors remove a restrictive assumption of previous works which\nrequired the input sequence coming from a zipfian distribution.\n\n* apart from static optimality, the authors make a step towards dynamic\nsetting, evaluating the performance of their data structure in terms of the\nworking-set bound.\n\nWeaknesses:\n\n* at this moment, it is not clear to me whether their static BST\nis robust, i.e., does not pay much more than m*log(n) regardless of the\nquality of the predictions.\n\n* their dynamic data structure requires a large branching factor\n  (omega(log n)), i.e., it is far from a binary tree", "other_comments_or_suggestions": "A suggestion:\nyou seem to call robustness what other papers in the area call\nsmoothness or dependence on prediction error. Might be better\nto use the same terminology as other works.", "questions_for_authors": "Can you please explain the behavior of your data structures (both static and\ndynamic) with very bad predictions?\n\nLooking at Theorem 2.13, if the real frequency of some element was a constant\n(0.1, let's say) and the predicted frequency was exp(-n),\nthen the bound of Thm 2.13 on the access cost of your data structure\nwould be m*n while any balanced tree pays at most m*log(n). I.e., with very\nbad predictions, your tree seem to be much worse than a balanced tree built\nwithout any information about the input sequence, and is not \"robust\",\nin the sense commonly used e.g. in the survey of Mitzenmacher and\nVassilvitskii which you cite in your paper.", "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": "igU3nQ4jrC", "reviewer": "Reviewer_AYCV", "summary": "The paper uses learned predictions to enhance the performance of classical data structures. Specifically, it presents learning-augmented binary search trees (BSTs) and B-Trees that leverage predictions about item access frequencies. Building on the work of Lin et al. [ICML’22], which proposed augmenting treaps (BSTs where nodes are arranged by key and randomized priorities) and B-treaps (their non-binary generalization) by replacing random priorities with predicted frequencies, this paper introduces a composite priority scheme. In particular, it assigns priorities as a function of predicted frequencies combined with random noise. This modification allows the structure to achieve static optimality more broadly, beyond the special cases addressed by Lin et al.\nIn the second part, the authors extend their approach to design a data structure that achieves the working-set bound, thus capturing temporal locality in access patterns. The paper also establishes robustness guarantees, showing that the performance of the proposed structures degrades gracefully under prediction errors. Finally, experimental results are presented to support the theoretical findings and to highlight the practical benefits of the proposed data structures over classical baselines.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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:\n\n\n1. 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. \n\n    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.\n\n    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.\n\n\n2. 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*.\n\n    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..\n\n\n3. 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.", "claims_and_evidence": "Yes, the main claims of the paper are supported by detailed proofs and are presented in a clear and convincing manner. The authors carefully prove the static optimality bounds, robustness guarantees, and working-set bound, each supported. The use of KL divergence to quantify the impact of prediction error is particularly interesting and aligns with standard measures in learning-augmented algorithm literature.\n\nIn addition, the paper includes experimental results that support the theoretical findings and demonstrate empirical improvements over both classical and previously proposed learning-augmented baselines. Although the experimental evaluation is somewhat limited in scope and focused on synthetic data, it still provides consistent evidence in support of the proposed methods.\n\nOverall, the paper’s claims are well-supported, logically coherent, and grounded in both theory and empirical validation.", "methods_and_evaluation_criteria": "Yes, the proposed methods and evaluation criteria are appropriate for the problem. The paper focuses on enhancing classical data structures using predictions, and the evaluation is based on standard theoretical metrics such as expected depth, working-set bound, and robustness with respect to prediction error (measured via KL divergence), all of which are meaningful in the context of search trees.\n\nThe experimental evaluation, while limited to synthetic datasets, is consistent with the theoretical goals of the paper. The selected access distributions are standard for illustrating both static and dynamic behaviors of the proposed data structures. However, the inclusion of more diverse or real-world access patterns could improve the empirical component.", "theoretical_claims": "Yes, I reviewed the proofs, including the analysis supporting the static optimality bounds, the robustness guarantees based on KL divergence, and the working-set bound in the dynamic setting. The arguments appear sound and are based on standard techniques in the analysis of search trees and learning-augmented algorithms. The proofs are clearly written, and I have not found any issues.", "experimental_designs_or_analyses": "Yes, I reviewed the experimental results presented in the paper. The experiments are based on synthetic access patterns generated from standard distributions. The performance metric used (average search depth) is well-aligned with the theoretical objectives studied in the paper. One limitation is that no explanation, discussion, or analysis of the experimental results is included in the main paper; this material is deferred to the appendix. As a result, there is a little disconnect between the theoretical development and the empirical evaluation, which weakens the overall presentation.", "relation_to_broader_scientific_literature": "The paper contributes to the growing literature on learning-augmented data structures, where algorithmic performance is improved through predictions. It builds directly on the recent work of Lin et al. [ICML 2022], who introduced the idea of using predicted access frequencies to assign priorities in treaps. This paper advances this line of work by introducing a composite priority scheme (combining predictions and random noise), which achieves static optimality more broadly across arbitrary frequency distributions. \n\nThe paper also situates itself within the broader field of self-adjusting and adaptive data structures, connecting classical ideas such as treaps, working-set bounds, and temporal locality with prediction-based techniques. The use of KL divergence to capture robustness under prediction error is interesting and aligned with recent trends in learning-augmented algorithm analysis, where \"smooth\" degradation with respect to prediction quality is a central theme.", "essential_references_not_discussed": "When discussing optimal static trees, the classic work of Knuth [Acta Informatica, 1971] may be cited. Additionally, two recent works on learning-augmented skip lists, which also explore topics such as static optimality, are Zeynali et al. [ICML 2024] and Fu et al. [ICLR 2025] (only the second one is mentioned briefly in the context of experiments).", "other_strengths_and_weaknesses": "The paper presents a conceptually clean and technically solid contribution, combining classical data structure theory with modern learning-augmented algorithmic techniques. The integration of prediction-driven priority schemes into search trees and B-trees is interesting and improves the prior work of Lin et al. [ICML'22] in a meaningful way. That said, the empirical component is weakly integrated with the rest of the paper. A more cohesive and thorough treatment of the experimental results would strengthen the paper, especially for an ICML audience. This is particularly relevant given the practical importance of B-trees in real-world systems, including database indexing and file system implementations.", "other_comments_or_suggestions": "- Line 024, the BST of Melhorn does not work with \"estimates\" of key frequencies; it assumes exact frequencies provided. \n- I did not identify any typos or presentation issues; the paper is generally well-written and clean in terms of language quality and spelling.", "questions_for_authors": "1- The learning-augmented data structures presented in this paper achieve static optimality and the working-set property. However, these properties have already been established for classical data structures that do not rely on predictions, most notably splay trees. Could you clarify whether your data structures offer any notable theoretical advantages over splay trees?\n\n2- What is the maximum depth of a node in your data structure? Is it possible that it gets linear depth under a highly skewed frequency distribution? In Line 096, you criticize the structure proposed by Lin et al. for having \"super-logarithmic depth\" in some cases, and this seems to be established in Theorem 2.14, where you demonstrate that assigning predicted frequencies directly as priorities (as in Lin et al.) results in linear depth and cost. How does this result compare to Proposition 2.2 in Zeynali et al. [ICML 2024]?\n\n3- The structure proposed by Lin et al. [ICML 2022] appears to be deterministic, whereas your approach is randomized. Is there any known lower bound or negative result suggesting that deterministic data structures cannot achieve static optimality under prediction error?", "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": {"ethical_review_concerns": "NA"}}, {"review_id": "wUfS0NDqJI", "reviewer": "Reviewer_tuW9", "summary": "This paper is concerned with learning-augmented search trees. Given a dataset of a sequence of requested keys, the recent work by Lin et al. 2022 constructs a learning-augmented search tree as a treap where the \"priority\" $p(x)$ of each key $x$ is set to be equal to the frequency $f_x$ of the key in the sequence. For simplicity, we will assume that the keys are being drawn from a distribution $p$, and that the empirical frequency in the sequence is exactly equal to the probability of each key. A classical lower bound result due to Mehlhorn 1975 shows that for any tree, the expected cost to access a key drawn from the distribution is at least $\\Omega(H(p))$, where $H(p)$ is the Shannon entropy of $p$. If $p$ is the Zipfian distribution, then the treap constructed by Lin et al. 2022 attains this optimal cost. However, their construction was not known to be competitive against the static optimal tree for general distributions. In fact, one of the results of the authors (Theorem 2.14) constructs a distribution for which the cost is indeed suboptimal.\n\nThe first main result in the paper is a construction of a treap corresponding to a different priority assignment to the keys. The authors set $p(x) = \\log\\log p_x + \\delta_x$, where $\\delta_x$ is uniformly random in $(0,1)$. The authors show (Theorem 2.8) that this priority assignment results in a treap, for which the expected cost of accessing a new key meets the lower bound above for every distribution. Furthermore, even if we only have access to estimates $q_x$ of $p_x$ that are noisy, and build a treap according to the priority function using these noisy estimates, the authors show that the expected cost of accessing a key only increases by the KL divergence between $p$ and $q$. This is a natural characterization of the robustness of their construction.\n\nThe next results in the paper are an extension of the above results from binary trees to arbitrary B-trees that have an arity of $B>2$. The authors establish similar results (Theorem 3.1) as the binary case for B-trees as well.\n\nThe authors also consider a dynamic setting where the priority function (and hence the maintained treap) is allowed to be changed as we see new keys. In this setting, the authors show a way of constructing dynamic priority functions, such that the resulting dynamic treap attains a \"working-set bound\", which is a natural benchmark for dynamic data structures.\n\nFinally, the authors perform experiments on synthetic data, comparing their treap data structure to other learning augmented search trees, as well as classical data structures, and show that their data structure compares much better to these other methods.\n\n## update after rebuttal\nI thank the authors for their response. The clarifications are useful, and should be appropriately addressed in the revision. I maintain that both the theoretical contributions and practical applications deem the paper worthy of being accepted, and will hence maintain my score.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n\n1. 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. \n\n    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. \n\n\n\n2. 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. \n\nWe will revise Line 310 as follows to clarify this point:\n\n>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.", "claims_and_evidence": "The claims and evidence appear convincing to me.", "methods_and_evaluation_criteria": "To the best of my knowledge, yes.", "theoretical_claims": "I only glanced over the proofs, and did not verify calculations line-by-line. They appear correct to me, and the progression in the overall analysis checks out to me. In particular, I could not really understand the calculations in the section on the dynamic setting, because this section is quite technically involved, and not really written in an accessible way.", "experimental_designs_or_analyses": "I did not find any glaring discrepancies in the experiments. They appear sound to me.", "relation_to_broader_scientific_literature": "The study of data structures is fundamental in computer science, and at its core, the paper proposes a new way of building a randomized tree data structure which is optimal in the sense of building a static tree for accessing keys drawn from a distribution. This is a worthwhile contribution. The work also has relevance in the context of building data structures in a manner inspired by machine-learned predictions, which is also highly relevant in present contexts.", "essential_references_not_discussed": "Please consider discussing and citing \"Binary Search with Distributional Predictions\" by Dinitz et al. (https://arxiv.org/abs/2411.16030) which appeared at NeurIPS 2024. That work seems quite relevant with the topic of this paper.", "other_strengths_and_weaknesses": "As mentioned above, the paper proposes a new way of building a randomized tree data structure which is optimal in the sense of building a static tree for accessing keys drawn from a distribution. This is a worthwhile contribution. More specifically, the paper strictly improves upon the past result of Lin et al. 2022---while their construction of the treap was competitive against the statically optimal tree only for the Zipfian distribution, the present construction is competitive against the statically optimal tree for all distributions. Moreover, the present construction has nice robustness properties (smooth degradation in terms of KL divergence), and also extends to B-trees. The study considered in the dynamic setting also appears novel, and could inspire similar future research. Finally, the experimental results do appear promising, and show the practical gains in using the proposed treap.\n\nWhile the technical contributions seem undeniable, I do however feel that the paper could be written better. For example, I felt that the introduction was quite dense. In its present form, a lot of jargon is stated without having defined/described certain concepts. As a nitpicking example, it is not clear to me why the abstract itself has a precise form of the priority function (Note that this is assuming the reader is familiar with the notion of a priority function). My general complaint is that a lot of technical sentences are written without easing the reader into what the words in the sentence mean/without setting up background/motivation. I would suggest going through the exercise of placing yourself in the shoes of an uninitiated reader, and going through the paper--this might suggest necessary modifications. Another piece of feedback is that the section on dynamic treaps is very hard to read technically, and doesn't really offer the reader with much insight. I would really encourage the authors to consider writing this section in a more accessible manner.", "other_comments_or_suggestions": "1) Correct me if I am wrong, but it seems like the guarantee in Theorem 2.8 of each node $x$ having expected depth $O(\\log(m/f_x))$ holds for any worst-case sequence of keys (even if they are not drawn iid from a distribution). It might be worth mentioning this somewhere after the Theorem.\n\n2) Maybe I missed it, but I don't think there is clear mention of the fact that the optimal static cost (as established by Mehlhorn 1975) is on the order of the Shannon entropy of the distribution. You mention in Theorem 2.8 that the cost of your treap is $O(\\sum_x f_x \\log(m/f_x))$ matches the optimal static BST cost, but you haven't really stated anywhere what the static optimal BST cost is (unless I missed it) for the reader to really understand why this cost this optimal.", "questions_for_authors": "1) Could you please comment on the robustness properties of the treap constructed in Lin et al. 2022? I think the paper warrants a discussion/comment about this, either in the section where you do the robustness analysis of your treap, or at any other place where you cite Lin et al. 2022\n\n2) I am likely failing to see something simple, but could you elaborate on why your $O(\\log(1/w_x))$ bound on the depth from Theorem 2.4 translates to an $O(\\log n)$ bound? This would mean that $w_x \\ge 1/n$---why is this true? You mention this in lines 309-310 in the section where you analyze alternate priority functions.", "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": "F3fwDZENjc", "reviewer": "Reviewer_R8jP", "summary": "This paper examines the integration of external predictions into classic binary search trees (BSTs) and B-Trees via Treaps. Prior attempts to build such a data structure only had guarantees for Zipfian distributions and were shown to be provably bad on certain sequences of inputs. In this work, the authors propose a composite priority functions to balance nodes according to predicted access frequencies and proved optimality in the static setting and guarantees with respect to working sets in the dynamic setting when the tree is allowed to adapt to the input sequence. Experiments were also done to empirically evaluate the newly proposed method, showing improving over existing solutions.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful comments! We address the questions and concerns as follows.\n\n**Robustness**\nIf 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)$. \n\n\n**Predictions for Dynamic Settings**\nThank you for highlighting this point! We will include a paragraph in the revision regarding the prediction of working-set scores.\n\n> 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.\n\n\n**Clarification on Proof Plan**\nThe 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$.\n\n**B-tree Update**\nAt 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].\n\n[1] Wang, Shoujin, et al. \"A survey on session-based recommender systems.\" ACM Computing Surveys (CSUR) 54.7 (2021): 1-38.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "I checked the proofs in the main paper", "experimental_designs_or_analyses": "I checked the experimental section in the main paper", "relation_to_broader_scientific_literature": "This work contributes to the field of learning-augmented algorithms in particular the development of data structures with predictions.", "essential_references_not_discussed": "Not that I am aware of", "other_strengths_and_weaknesses": "# Strengths\n\n- The proposed composite priority scheme enabled the authors to obtain guarantees for arbitrary input distributions, beyond just Zipfian.\n- The proposed method has nice provable guarantees such as static optimality, dynamic adaptability, and error robustness.\n- Experiments were also done to empirically evaluate the newly proposed method, showing improving over existing solutions.\n# Weaknesses\n\n- Typically, in the learning-augmented literature, the \"robustness\" guarantee is ideally asymptotically similar to the setting without predictions. The authors gave a robustness bound in terms of KL divergence between the true frequencies and predicted frequencies. I was hoping the authors can discuss and relate their bound with the setting without predictions.\n- While I can imagine how to get frequency predictions for the static setting, it is unclear how one can obtain the predictions needed for the dynamic setting to work well. I hope that the authors can point me to a discussion that I might have overlooked or mention what explanation they will add in their revision.", "other_comments_or_suggestions": "- Typo: On Page 2, paragraph on Static Optimality of Learning-Augmented Search Trees, \"... Equation Equation (2)...\" should be \"... Equation (2)...\"", "questions_for_authors": "- Clarification: In the proof plan on Page 4, the expected depth of x refers to the number of its ancestors, not just in S_t, right? If so, in the proof of Theorem 2.4 on Page 5, what about the ancestors of x outside of S_t? What am I misunderstanding?\n- I might have missed it but could you describe how the B-tree is being updated in the dynamic setting?", "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": {"ethical_review_concerns": "NIL"}}]

Author rebuttal:

Meta-review: The paper shows that the performance of binary search trees and specifically treaps can be improved by using predictions about the frequencies of all items, achieving static optimality up to a constant factor. Though reviewers observed that the statements do not provide the usual guarantees of robustness in learning-augmented algorithms, KL divergence provides a meaningful quantification of the quality of advice and thus reviewers agree that the contributions of the paper are valuable.
Decision: Accept (poster)