Hierarchical Retrieval: The Geometry and a Pretrain-Finetune Recipe
Authors: Chong You
Rajesh Jayaram
Ananda Theertha Suresh
Robin Nittka
Felix X. Yu
Sanjiv Kumar
Venue: NeurIPS 2025 poster ()
Keywords: Information Retrieval
Hierarchical Retrieval
Dual encoders
Primary area: general_machine_learning

Abstract: Dual encoder (DE) models, where a pair of matching query and document are embedded into similar vector representations, are widely used in information retrieval due to their simplicity and scalability. However, the Euclidean geometry of the embedding space limits the expressive power of DEs, which may compromise their quality. This paper investigates such limitations in the context of hierarchical retrieval (HR), 
where the document set has a hierarchical structure and the matching documents for a query are all of its ancestors. We first prove that DEs are feasible for HR as long as the embedding dimension is linear in the depth of the hierarchy and logarithmic in the number of documents. 
Then we study the problem of learning such embeddings in a standard retrieval setup where DEs are trained on samples of matching query and document pairs. Our experiments reveal a lost-in-the-long-distance phenomenon, where retrieval accuracy degrades for documents further away in the hierarchy. To address this, we introduce a pretrain-finetune recipe that significantly improves long-distance retrieval without sacrificing performance on closer documents. We experiment on a realistic hierarchy from WordNet for retrieving documents at various levels of abstraction, and show that pretrain-finetune boosts the recall on long-distance pairs from 19% to 76%. Finally, we demonstrate that our method improves retrieval of relevant products on a shopping queries dataset.

Hierarchical Retrieval: The Geometry and a Pretrain-Finetune Recipe
Chong You
Rajesh Jayaram
Ananda Theertha Suresh Sanjiv Kumar
Robin Nittka
Felix Yu
Google (cyou,rkjayee theertha, wen
Abstract
Dual encoder (DE) models, where pair of matching query and document are embedded into similar vector representations, are widely used in information retrieval due to their simplicity and scalability. However, the Euclidean geometry the embedding space limits the expressive power of DEs, which may compromise their quality. This paper investigates such limitations in the context of hierarchical retrieval (HR), where the document set has a hierarchical structure and the matching documents for a query for HR as long as the embedding dimension linear in the depth of the hierarchy and logarithmic the number documents. Then we study the problem of learning such embeddings in standard retrieval setup where DEs are trained on samples of matching query and document pairs. Our experiments reveal fost-in-the-long: distance phenomenon, where retrieval accuracy degrades for documents further away in the hierarchy. To address this, we introduce a pretrain enetraiin-inetuee recipe that significantly improves long-dia miisddittnce retrieval without sacrificing performance on closer documents. We experiment on a realistie hierarchy from WordNet for retrieving documents at various levels of abstraction, and show that pretrain- finetuee boosts the recall on long-distance pairs from 19% 76%. Finally, we demonstrate that our method improves retrieval of relevant products shopping queries dataset.
all of its ancestors. We first prove that DEs are feasible
Introduction
Information retrieval (23] the task finding the most relevant documents within large database in response to a user query. Dual Encoder (DE) is one of the most popular modeling architectures for information retrieval due to their simplicity and scalability. It functions by encoding each query and each document by vector representation, e.g., by using deep neural network [16 9 (36]. Then, similarity between a query and document is calculated using their Euclidean distance or inner
product, enabling scalable retrieval through approximate nearest neighbor search [19 17 [0].
This paper considers Hierarchical Retrieval (HR), particular case of information retrieval where the set of documents is organized into (hidden) hierarchical structure. To motivate our retrieval task on a hierarchy, consider the keyword targeting problem in online advertising where ad platforms aim to display ads based on the relevance of the associated keywords to a user's 's query. While many notions of relevance exist, a particularly important case, known as Phrase Match (2 4. defines relevant keywords as those that are semantically more general than the user's query. This definition motivates the modeling of advertiser keywords as a hierarchy, where higher level keywords are semantically more general than the lower level keywords (see Figure Left). Then, Phrase Match may be expressed as the problem of retrieving not only the keyword that matches exactly the meaning of user query, but also all those at higher level in the hierarchy. Motivated by Phrase Match,
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Relevant
Footwear
100
Rolevant
Relevent
Sandals
Sports shoes
60
Standes
/f Relevant
Bunning shoes
40
Pictcih fineure (0u5)
Kot' sancels
Query
Nirforurning
Gueryddsummet distance
Figure 1: (Left) A illustrative example of document set that forms hierarchy. Given a query, e.g. "Kid's ' sandals", the goal is to retrieve all its ancestors in the hierarchy. (Middle) An abstraction of this hierarchy using DAG where the edges are represented solid arrows. For each node of the graph, the goal of Hierarchical Retrieval (HR) is to retrieve all v such that e is reachable from u. (Right) The lost-in-the-long sos--i--hhellog-distteee disttnnne phenomenon of Dual Encoders (DEs) trained for HR on the WordNet DAG. Documents further away from the query in the hierarchy are more difficult to retrieve. We introduce a pretrain-fineee
recipe to drastically improve long-distance retrieval.
define HR as the retrieval problem on a hierarchy that can be described by a direct acyclic graph (DAG, Figure Middlee) Then, the goal retrieve, for each node u, all nodes reachable from u with a directed path. In particular, we assume that the DAG is unobserved, which is the typical case in information retrieval where the model learned on data set of matching query-document pairs.
Why is Hierarchical Retrieval hard? DEs solve information retrieval tasks by finding embeddings such that relevant document is closer in distance to the query than an irrelevant one. For HR, this distance measure needs to be asymmetric. For example, "Kid's sandals" the query then "Sandals" is considered relevant keyword, but the inverse is not true: if "Sandals" is the query then "Kid's sandals" not relevant keyword. This makes asymmetric DE a natural choice, where the same node is embedded differently by query encoder Q() and document encoder D().
However, asymmetric DEs can still be limited for HR due to the properties of the Euclidean geometry (21] To illustrate this, consider the query "Kid's s sandals" for which a DE needs to place the two document embeddings D("Sandals") and ("Kid'ss shoes")) in close proximity to each other, since they need to be both close to Q"''i''s sandals"). On the other hand, for the query "Kid's running shoes", a DE needs to place the aforementioned two document embeddings far apart since only one of them is close to Q(" running shoes").. This apparent inconsistency leads to the critical question:
Ql: Does there exist Dual Encoders that solve Hierarchical Retrieval?
We will provide an affirmative answer to QI, establishing the feasibility of DEs for HR.
Nonetheless, the existence of such DEs does not mean that they can be learned from data. In practice, the following question is of great importance:
Q2: Can we learn (from train data) Dual Encoders that solve Hierarchical Retrieval?
We show through experimental evidence that if the embedding dimension of DE is sufficiently high, then the answer to Q2 positive as well. This result justifies DE as a feasible architecture for HR. Lost in the long distance? While the answer to Q2 is positive with a high embedding dimension, practical retrieval systems have memory and latency requirement hence low embedding dimension desirable and critical. Towards improving the practice of DEs for HR, we examine cases where learned embeddings fail due pest-in-the-logg lane-loon-diiacce phenomenon. This phenomenon states that documents further away from the query in the underlying hierarchy more difficult retrieve, hence compromises the quality of the retrieval (see Figure Right). To mitigate this, we introduce a pretrain-finelume recipe, where a dataset focusing solely on long-distance pairs. Such recipe enhances
insufficient embedding dimension, and discover intriguing
pretrained DE is finetuned the practicality of DEs for HR by improving long-distance retrieval capabilities.
We summarize the contribution of this paper follows.
Dual Encoders are feasible for Hierarchical Retrieval. We formally establish that asymmetric DES are feasible for solving HR. Specifically, with a constructive algorithm that maps an arbitrary DAG to a set of asymmetric embeddings, we prove that such embeddings solve the associated HR task with a high probability. This holds as long as the dimension of the embedding space is larger than threshold determined by the underlying hierarchy (Section

---

Dual Encoders can be learned from training data to solve Hierarchical Retrieval. The con- structive algorithm above requires the DAG as input. On the other hand, information retrieval tasks often do not directly provide the DAG but require learning embeddings from training dataset of matching
pairs. Next, we conduct an experimental study of this learning problem, starting from synthetic tree-structured hierarchies for gaining insights. We verify that the learned DEs successfully solve HR with a sufficiently high embedding dimension (Section 4).
A Tretrain-Finetune recipe improves the training of Dual Encoders for Hierarchical Re- trieval. We reveal the wow-in-the-long-diitnnce phenomenon under toy setup with a synthetic tree-structured hierarchy. Critically, we show that the standard approach based on rebalancing the sampling of short vs. long distance pairs in the training dataset fails to solve the problem. This highlights the importance of our pretrain-fineture recipe, where a pretrained DE further finetuned on long-distance pairs gains enhanced long-distance retrieval capabilities without compromising the quality on short-distance documents (Section 5). Finally, the effectiveness of this recipe extends beyond the toy setup to real datasets, including 1) WordNet, a large lexical database of English, and 2) ESCI, a shopping queries dataset (Section 6)
1.1 Related Work
Graph embedding. Graph embedding broadly refers to methods that learn a set of node embeddings that preserves certain properties of the graph (35]. While Euclidean embedding a natural choice, the symmetric nature of the distance metric makes it problematic for handling graphs with directed edges, such as DAGs. To address the issue, numerous works have explored ideas going beyond Euclidean embeddings, c.g., by representing each node with geometric region [31 32
II
29 or a probability
30 14 to better model the hierarchical structures. However, such embedding models are not suited for retrieval due to lack of an efficient nearest neighbor search that hinders their applicability to large scale data, Another work more related to ours is [25], where asymmetric embeddings are used to capture the asymmetry and transitivity of the DAG. However, the focus of (25) is on computing embeddings on a given graph. In contrast, retrieval applications often do not have access to the underlying graph, and embeddings are learned from a dataset of matching query-document pairs.
distribution 33 6. These ideas may be coupled with non-Euclidean metries 24
Pretrain-finetune. The paradigm of pretraining and finetuning, where a model is first trained on a large, general-purpose dataset then adapted to downstream tasks with finetuning procedure, a cornersoone of modern machine learning [3 27 77 For information retrieval, this paradigm demonstrates effectiveness for improved DE quality, particularly for sparse or noisy downstream recipe adapts this paradigm by treating the retrieval of long- distance matches downstream task, which we demonstrate to be effective in addressing the loss-in-the-lowe toatte-ooondddtnnee challenge in HR.
data 8 Our gvetraining-finetuiin
2 Problem Setup
Hierarchical Retrieval (HR). Let Q = |i be a collection of n queries and D = {my } be
a collection of m documents, respectively. For each E [1.....,n]] n), let 5(q:) S D be the set that contains all documents that are the most relevant the query 9:- The goal of information retrieval is to return a ranked list of the documents in D for each qi, with the top ones being those in S(z))
This paper considers HR, a particular case of information retrieval where the document set is associated with a hierarchy. Let us assume that each query has an exact match document, c.g., for a query "Sandals for kids", the document "Kid's 's sandals" from the document set illustrated in Figure | is considered an exact match. Then, the relevant document set S(q.) contains both its exact match and all its descendants in the hierarchy. Formally, HR is defined as follows.
Definition 2.1 (Hierarchical Retrieval (HR)). Assume that there is a directed acyelic graph (DAG), denoted as G = (V,E), E), associated with the document set D, i.e., with V> D and C V x V. Also, assume that there is a E' Q + D. where E(q,) is referred to as the exact match to g:- Then, HR refers to information retrieval with the relevant documents given by S(q.) = {x E D x is reachable from }()))} for each i E {I,..., nn].
Dual Encoders (DEs). DEs are embedding models that map the query and document to the same embedding space, where the inner product may be used to measure relevance. A DE is composed of query encoder, denoted as [- 0,)) Q + R. and a document encoder, denoted as fz 0x)= D + gd, where 0g and O₂ are parameters to be learned from data.
3

---

Following standard practice in information retrieval, we assume that the HR training dataset is com-
posed of matching query-document pairs. That is, there is a collection of pairs {(q(k) x 2²()) ) S Q x D that satisfies r²(h) (k)( for each k = 1...., NN. The parameters 0g and 0₂ of a DE may
be learned from minimizing the following softmax loss on the training dataset:
L(0 0z)
1 N
Σ CE
D(O2)"
fg 00)) ) 1x
where
D
(x 02), fa....,.,,(x))) 02)) RdxN
(2)
is a matrix containing all document embeddings as columns. In above, 1 E IR is a vector with the k-th entry being and all other entries being and T is hyper-parameter that is fixed to be 20 in all our experiments. CE means the cross-entropy loss and a() represents the softmax function.
Our ultimate objective is to understand whether a DE from optimizing Equation ① solves the HR problem. The answer will necessarily depend on multiple factors including the specificity of G, the architecture of fg( 0g) and fa 0z), and the optimization algorithm, etc, signficantly complicating the study. In the following, we start with a study of the geometry of HR which is agnostic to the choice of model architecture and optimization procedure.
3 The Geometry of Dual Encoders for Hierarchical Retrieval
This section studies the following problem: Is there collection of query and document embeddings that solves the HR? An affirmative answer to this question asserts the existence of embeddings that solve HR, which is necessary condition for the minimizer of Equation [I] to solve HR.
To answer this question, we start with considering the special case when the embedding dimension large the size of the document set. Here, one may simply take æ; 1 as the embedding for each 2j- Subsequently, we set the query embedding for each qj as qi = L). zy. It can be verified that (g:.r) take value if S(4), and O otherwise, i.e., these embeddings solve HR.
Algorithm A constructive algorithm for Hierarchical Retrieval Ji
1: Input: A query set Q = =g
document set = {æ,}y and relevant document sets
(S(q)) C DD
2: Sample { C Rd ii.d from the standard Gaussian distribution.
3: For each j. take x
| 2
4: For each i, take q,
gi where qi = -Ejestad Z.
Ta
5: Output: Query embeddings (q: )i= and document embeddings (ær (m,)
The construction above is feasible only when the embedding dimension d is allowed to be very large. Towards deriving tighter bound, we consider another construction where the document embeddings are drawn from Gaussian distribution, in lieu of the one-hot embeddings, see Algorithm | We will use that random embeddings are with high probability sufficiently uncorrelated to each other to show that this construction provides a solution to HR with much relaxed requirement on d. This is stated formally below.
Theorem 3.1. Consider the HR problem in Definition 2.1 and fix any E (0, 1/2). Assume that the hierarchy G satisfies (((g)) s, vi [ri] for some integer Then there exists dimension d with d = (max(x log m. 1/2 log m));
threshold rr and a collection of embeddings {q, ) {z, ) Rdd, such that for all E [m]] and j e [m] the following holds:
Case I: If dj S(g)), then (qi, σ2) 2
Case 2: 1f d, $ S(q.) then (qi, σ.)) 5
'This is universal threshold r that separates the matching documents from no-matching ones for all queries. In practice, it often sufficient have gependdd threshold.

---

310
Handkrafled
Handrrafte Learned
100
Dimeroon
Omerrsion
50
20
10
10
11
W
(a) Varying H for W
(b) Varying W for H
Figure 2: Comparing learned (i.e., from optimizing Equation (1) vs handcrafted (i.e., from running Algorithm 1 DEs for HR task defined on a W, H-tree. For each (H, W) pair, we experiment with an increasing sequence of embedding dimensions d until the retrieval successful, and report that dimension the y-axis. Successful retrieval means that recall is above 95% on the evaluation set. Dotted lines are least squares fittings of the Handcrafted.
Moreover, the vectors (= (an [05))=1 can be constructed to satisfy these properties in time Ö(md- nsd) with high probability.
asserts that the required embedding dimension on the order specified in Equation (3) This order is logarithmic in m, implying that small dimension can be sufficient for handling large document set. For a fixed and m, this order is linear 8, the maximum number of relevant documents per query, which in practice is usually much smaller than m. For instance, when G is a perfect tree with edges pointing from each child node to its parent node, becomes the number of levels of the tree and is the order of log(m); plugging this into Equation
Theorem 3.1
(3) we obtain M = ((log m)²). which again scales benignly with m. Finally, Equation (3) is independent of n, the number of queries. This is because the theorem only requires to handle subset of queries hir, C (1.....n) n for which their relevant document sets are distinct from each other, i.e., S(q.) * S(g,), v( C T and + j. For HR, the size of such T is upper bounded by m according to Definition 2.1
The construction procedure in Algorithm requires knowing the sets (m((:))im1....... In practice, these sets are often not directly observed. Instead, often the case that the training dataset composed of set of matching query- establishes the correctness of such embeddings, Algorithm D may not be applicable in practice. Instead, the embeddings often learned by optimizing proper training loss such as Equation ( Understanding if such learned embeddings solve the HR problem the subject of the next section.
pairs, Section 2 Hence, while Theorem 3.]
Comparing Theorem 3.1 with Prior Work [15). Our Theorem 3.1 relates to [15 which also
establishes logarithmic bounds on embedding dimensions. However, [5] addresses a different problem. The focus of 15] is multi-label classification, for which their Theorem 2.1 establishes a bound for representing the multi-label set. In contrast, our Theorem 3. specifically addresses HR. proving the existence of asymmetric query and document embeddings in Euclidean space that satisfy the specific mncsstrr-retrieval property. That being said, [15]'s ss result may be applied to HR by associating their multi-label set with hierarchy. With this specification, their result states the following (informally):
There a dimension d d O(s log m) such that for dj E S(g)) has 2;)) > 2/3, and for d, $ S(q)), it has (g: Φz) < 1/3.
Comparing to this result which has a fixed gap 1/3 between matching and no-matching pairs, ours in Theorem 3.1 holds for an arbitrary gap of 2e, hence is more general.
Towards Learning Dual Encoders for Hierarchical Retrieval
This section studies whether learned DEs from optimizing Equation (I) can solve HR. To understand the effect of depth and size of the hierarchy, this section focuses on synthetic, tree-structured hierarchies. Experiments on real hierarchies from practical data are provided in Section 6
toy setup. We consider perfect trees, where each non-leaf node has the same number child nodes and all tree leaf nodes are at the same level. A perfect tree is described by two parameters, namely
5

---

0.6
over all
0.4
ovaral
dst
det
02
0.-
0.
0.01
dat
0.0
0
25
50
75
109
125
150
175 20c
0
25
50
75
303
125
150
175
200
25
75
100
125
150
175 200
Vain stepe 120
Tain stops / 120
Train staps/ 300
(a) Regular sampling of train data
(b) Re-halanced train data
(c) cetraininng-inntuniin
Figure 3: Recall on query- document pairs at varying distances 10, (denoted qd dist in the legend). We train DEs with
dimensional embeddings via optimizing Equation (T) on a tree with H = 4 and W 5. (a) Regular training data. The recall for (g.x) pairs with distances 1 and 2 are low. (b) Re-balanced training data, where (g, pairs with a distance of or are up-sampled. The recall for such pairs are significantly improved the cost of a drastic decrease in recall for pairs with distance O. (c) Pretrain on regular data for 10k steps then finetune on long distance pairs for another 10k steps. Recalls at all distances are close 100% near 15k steps. In particular, the overall recall (i.e., averaged over the 3 distances) improves to 97%, compared to 66% in (a) and 70% in (b).
the number of child nodes for each non-leaf node (i.e., the width W), and the number of levels (i.e., the height H). We use H, W-tree to refer to perfect tree with width W and height H.
Given an H, W Wreeee, we consider HR problem where both the query set Q and the document set D> have a one-to-one correspondence to the set of all nodes of the tred Then, the hierarchy associated with D is naturally described by a DAG with edges pointing from each child node its parent node. Hence, the relevant document set Sg)) for a query q E Q contains the document that corresponds to the same node in the tree as g. as well as all nodes reachable from it. We consider solving this HR problem by bookup-table DE, a standard choice for studying embedding models [12] 266 [S]. In such DE, the encoders fy and fa are lookup tables with one embedding associated with each g E Q and E 'D respectively.
We sample training data using the following procedure. First, query q is sampled by drawing node with equal probabilities from all nodes of the tree. Then, we obtain a matching document to by sampling a node with equal probabilities from the of all of its matching documents. Training is conducted by optimizing Equation ( with gradient descent. Evaluation is conducted on data sampled using the same procedure described above. We use the standard recall metrie, which is the percentage of (q. r) pairs in the evaluation set for which is one of the k documents that have the largest inner product score with 9, with & = [S(g]] being the total number of relevant documents for q. We are interested in the smallest embedding dimension (i.e., d) sufficient for successful retrieval. To obtain this dimension, for each (H, W), we experiment with an increasing sequence of d and terminate the process when the evaluation recall metric is >95%.
Results. In Figure 2] report the dimension d needed for a successful retrieval function of (H, W). Towards that, we vary H for a fixed W = 2 on the left, and vary W for a fixed // = on the right. Both cases show that a reasonably large d is sufficient even for H up to 10 and W up to 30.
We further compare such learned embeddings with handcrafted ones from Algorithm [ From Theorem 3.J] the handcrafted embeddings solve HR with d = O(s s logm). For H, W Wttrees, we have 8 H, m HWI), which gives = O(H2 log W). This aligns well with our simulation results which we report in Figure 2 For example, in Figure [a we perform a line fitting in the log-log space and obtain slope of 2.29, whereas the slope derived from = O (H2 log W) is In Figure 2b perform a line fitting in the space of log(W) and obtains slope of 16.5, whereas the slope derived from d = ( log W) is 16. Finally, Figure 2 shows that that learned embeddings achieve successful retrieval with much smaller d compared to our handcrafted embeddings.
5 Improving Dual Encoders for Hierarchical Retrieval
With the establishment that standard training of DEs solves HR, this section takes one step further and asks the following practical question: Can we improve our training algorithm to minimize the dimension required for solving HR? We approach this by examining the failure cases of learned
Excluding the root node since if it were included then all queries should trivially retrieve it.

---

embeddings from standard training when the dimension is insufficient. This leads us to discover a common failure case called the lost-in-thee tastin-the-long-e taee-lon-ddittncee phenomenon. In addressing this issue, we present pretrain-finetune recipe that leads to an improved retrieval quality.
5.1 Last-in-the-Long-Diiss
We again consider HR on a H, W-tree as described in Section 4 but focus on a particular case where standard training of DE fails to retrieve relevant documents. In particular, we consider the case of
H = 4. W 5, and d = 3. Towards understanding this failure case, we introduce the notion of distance between a matching pair (g. z²). defined as the difference between the level of the tree nodes corresponding to g and I. For example, a distance of O means that and a correspond to the same node, and distance of means that x: corresponds to the parent node of q.
For the tree with H = 4, W = 5, any query that corresponds to a leaf node has 3 matching documents with distance 0, and 2, respectively (recall that the root node does not correspond to any query / document). We evaluate recall for query-document pairs at these three distances separately, and report results in Figure Ba It can be seen that the learned embeddings achieve almost perfect retrieval for pairs with a distance O, but do not work well for pairs with distance I and 2. We refer to the phenomenon that matching documents at longer distances to the query tend be lost in retrieval as lost-in-the-lone wawtt---oo---diiancee...
Failure of re- re-baaanced sampling. A tempting approach to alleviate lost-in-the-long- line--sttnne is to re- re-balance the training set, so that more pairs of longer distances are included. To test this, we consider two sampling distributions:
Regular sampling which refers to the sampling procedure described in Section 4 For H 4,
W = 5, distances 0, 1, and 2 pairs are sampled with probabilities 38%, 35%, and 27% respectively. -eavy-Tail sampling, where pairs with distances 0, 1, and 2 are sampled with probabilities 0%, 50%, and 50%, respectively.
By mixing regular and heavy-tail sampling with ratio of p : 1- p. we may create training datasets with controllable ratio between short and long distance pairs. In Figure 3bb we report the result with P 0.03. It can seen that the recall for pairs with distance 1 and 2 are significantly improved and reaches a level of beyond 80% towards the end of training. However, this comes at the cost of significant recall degradation on distance pairs. Finally, this tradeoff cannot be fixed by tuning p. as illustrated in Figure (see Appendix) which contains further results with varying in (0.01, 0.1, 0.3).
5.2
Main Algorithm: A Pretrain-Finetune Recipe
We introduce a pretrain-finetune recipe to address the challenge of cost-i-thhe-lng-distee This approach simply means that the DE is first pretrained on standard training set, then finetuned on a long- long-distance dataset. Notably, the finetuning stage requires long- long-distance data only and does nor require tuning the ratio of short vs long distance pairs as hyperparameter.
We conduct an experiment with pretraining and finetuning using data from regular and heavy-tail sampling, respectively, and report the results in Figure 3cl. We observe that in the finetuning stage, the retrieval quality for pairs with distance and quickly improves and reaches nearly 100% at 15,000 train step. Notably, at this point the recall for distance 0 pairs remains close to 100%, and the overall recall (i.c.. averaged over pairs of all distances) is 97%, far exceeding the regular data sampling (which has 66% recall) or re-balanced data sampling (which has 70% near 17000 steps). Finally, after 15,000 steps the quality of distance 0 pairs starts to decline. This is expected since the finetuning stage does not have any training data with distance O. However, this quality degradation does not compromise the practicality of our approach since one can apply early stopping during the finetuning stage by monitoring the model quality on a validation set.
Discussion on data requirement. In applying the pretrain- finetune recipe, a practical question is how to construct the long-distance dataset for finetuning when the underlying hierarchy, and thus the query-document distances, unobserved as is typical in many retrieval applications. The key point is that our recipe does not require precise path lengths or knowledge of the full DAG. Instead, only requires practical proxy for distance that can be used to partition the training data into short-distance and long-distance subsets. This proxy is often readily available from the data or the problem definition itself. For instance, in our shopping dataset experiment (see Section (b. we treat Exact query- preyuct matches as the -hort-distance set for pretraining and Substitute matches as
7

---

Table Quality of DE for HR on WordNet. Regular sampling refers to first sampling a query then a document uniformly at random from the set of all matching documents. Rebalanced means a mixture of data from regular sampling with a proportion p and a heavy-tail data of proportion -p where long-disin dingddittncc pairs upsampled proportionally first pretraining on regular sampling data then finetuning on heavy-tail data. Quality is measured by averaged recall test set. Our method (i.e., pretrain-fineture enables good retrieval quality for query-document pairs at all distances.
their distance. Pretrain-finetune (ours) refers to
Query-document distance
Method
2
3
8
Min
Overall
Embedding dimension 16:
Regular sampling
100.0
62.8
46.6
33.9
20.9
11.9
7.2
2.9
1.0
1.0
43.0
Pretrain-finetumm finetune (Ours)
100.0
57.1
46.4
47.9
50.2
53.6
53.1
47.3
32.0
32.0
60.1
Embedding dimension 32:
Regular sampling
100.0
90.8
79.2
62.3
46.4
31.8
20.1
14,8
8.4
8.4
61.8
Tretrain-finetune (Ours)
100.0
77.3
76.5
80.4
83.5
84.2
84.3
80.1
67.3
67.3
87.3
Embedding dimension 64:
Regular sumpling
100.0
93.9
86.9
76.8
60.2
46.8
36.1
28.8
19.4
19.4
71.4
Rebalanced (p=0.01)
0.6
46.9
69.7
67.2
56.3
44.7
39.4
34.9
36.6
0.6
41.8
Rebalanced (p=0.03)
49.6
69.4
64.2
52.1
43.2
37.7
31.8
32.7
2.8
40.7
(Ours)
100.0
90.8
91.6
92.7
92.6
91.8
90.9
87.3
75.7
75.7
92.3
the long-distance set for finetuning. In other scenarios, this partition could be based on whether a document is a direct parent versus a more remote ancestor known but partial hierarchy. Finally, human annotation can be another viable path towards obtaining such a dataset, which is significantly casier task than annotating the full DAG. This flexibility allows our pretrain -inettune recipe to be applied in a wide range of practical settings where the full hierarchy is not explicitly given.
Finally, our recipe implicitly assumes that there is sufficient short- data to learn meaningful initial representation during pretraining. If this data is extremely sparse, pretraining may be ineffective, and mixed training approach might indeed perform better.
Experiments on Real Data
In this section, we experiment with the pretrain- pretrain-finetune recipe on two real datasets, namely WordNet and ESCL. On WordNet, which is large lexical database of English, our method improves the retrieval of hypernmms that are several levels more general than the query. On ESCI, which is shopping queries dataset where each query has both exact matching products and substitute products, our method enables a single DE retrieve both categories higher recall.
6.1 WordNet Experiments
WordNet [22 is large lexical database of English where the nouns, verbs, adjectives, and adverbs are grouped into synsets that represent synonyms. The set of synsets is equipped with a binary hypernym relation, e.g., "chair" is the hypernym of "armchair". This relation may be described by DAG with nodes corresponding to synsets and edges pointing from synset to its hypernym synset.
In our experiments, Q to be the same as D. For each query E Q the matching documents S(q) include itself, its hypernyms, and hypernyms of all hypemymms, etc. For example, matching documents for the query "cat" include "cat", "feline", "carnivore". "placental", etc. In practice, we make a slight modification to this definition by restricting to (q. d) pairs with distance of at most 8. Here, the distance between two synsets is defined as the length of the shortest path that connects them in the hypernym DAG.
use the 82, noun synsets
document set D. We take the query set
Unless specified otherwise, we use the following regular sampling procedure to generate training and evaluation data. First, a query q is sampled uniformly random among all 82,115 synsets. Then, a document is sampled uniformly at random from the set of all matching documents q.
Lost-in-the-long-ee distanne We train lookup-table DE by optimizing Equation II) using SGD for 50k iterations on 10M matching pairs from regular sampling. We use learning rate 0.5, momentum 0.9, and batch size 4096. To evaluate the learned DE, we use the recall metric defined as the percentage of (g. æ) pairs for which x is one of the & documents that have the largest inner product score with g, with & [S(g)]. We use validation set of size 10k to pick the best checkpoint. Then,

---

Table 2: Spearman correlation score p Hyperlex for DE trained on WordNet. We used 5- dimensional embeddings to be consistent with prior work. Our method (i.e. pretrain-finetuet obtains the best correlation score.
Method
OrderEmb
WN-Basic
WN-Euclidean
Regular sampling
Pretrain- finetune (ours)
2
P
0.195
0.240
0.389
0.350
0.415
we report in Table I the recall computed on test set of size 10k, including an overall recall that is averaged over all pairs in the test set, and recall on slices with different -dccmmdtnmn distances (i.e.. O, I, ... 8). For varying dimension of the embedding space in {16, 32, 64), we observe that quality degrades rapidly as function of the distance between the query and document. A similar qualitative behavior is also observed in [8
Rebalanced data sampling is insufficient. The lost-in- pee-lonn-distaane phenomenon may be attributed to the distribution of data from regular sampling, which is bi-
Peicenaage Samploo
ased towards pairs with short distances (see Figure (4). A natural choice use heavy-tail sampling of the train- ing dataset, which works as follows. First, a query q is sampled uniformly at random from all synsets. Then, the matching document for is sampled with a probability proportional to the distance between the document and q.
cons
c.00
0000
Query DCC distance
We create a rebalanced dataset where each batch has p x 4096 pairs from regular sampling and (1 - p) x 4096 from
Figure 4: Distribution of regular sam- pling and heavy-tail data over varying query -heummt distances on WordNet.
heavy-tailed data. Results with p 0.01 or = 0.03 for embedding dimension 64 are reported in Table [ It can be seen that rebalanced data improves the retrieval quality on long distance pairs but at the cost of compromising quality on short distance pairs, aligning with the observation in Section 5
Our wvetrain-finetume recipe offers solution. We pretrain the DE on data from normal sampling. then finetune on the heavy-tail dataset. During finetuning, we reduce the learning rate to 1,000 times smaller and increase the temperature Equation (T) from 20 to 500; an ablation study on these two prper-pprammters is provided in Appendix E In both of the two stages, we pick the best checkpoint on the validation set. The results Table demonstrate significant retrieval quality improvement for long distance document, leading to much higher overall recall. We further provide an example of the retrieved documents for selected queries in Table These examples show that regular sampling finetune recipe fixes many such errors.
tends to miss the long distance pairs and the
Hypernymy my evaluation. We supplement our evaluation by using HyperLex [34], dataset for evaluating how well a model captures the Here, we evaluate our DE models learned WordNet using regular sampling well as the pretrain- finetune recipe. We also compare with results from previous papers and report the results in Table 2 This result confirms the effectiveness of the nnetrain-finetun recipe.
relation between concept pairs.
6.2 Experiment on ESCI Shopping Dataset
ESCI (8 is a public Amazon search dataset, containing 2.6 million manually labeled query-produc relevance judgements in four categories, namely, Exact, Substitute, Complement, and Irrelevant. For our experiment, we focus on Exact, where the product is relevant for the query and satisfies all query specifications, and Substitute where the product is somewhat relevant and fails fulfill some aspects of the query. We consider the task of retrieving, given a user query, both Exact and Substitute documents by a 3
Training and evaluation data. ESCI comes with a train vs test data splitting. We take the Exact and Substitute pairs from the train split as our training sets, denoted as Eusin and Stain respectively.
'This task may not fit exactly the HR problem definition. However, the similarity to HR is that a Substitute match may be considered as having longer distance to the query than an Exact match, leading to the same lost-in-long dong-distance challenge HR.

---

80
Recallikk
60
RecalloN
60
40
jo on Treining Pretrain-Finetune
40
Joint Training PretrainnFineetue
(a) Results on Exact
(b) Results Substitule
Figure 5: Quality of Exact (left) and Substitute (right) retrieval on the ESCI dataset using a single DE. By first pretraining on Exact then finetuning on Substitute matches, our pretrain-finetune recipe performs better than naively joint training on Exact and Substitute matches.
Fuain and Suain contain 1.3 million and 0.4 million matches, respectively. We sample 5k Exact and 2k Substitute pairs from the test split for evaluating our model. These two sets are denoted as Eist and Stest, respectively. To evaluate our model, we use
Recall@k (4g d) T d among the top-k matches for g)
where T is either Eus Swst In words, it is the percentage of (q, x) pairs in the set T with the property that the inner product score between &f and x is among the & largest ones across all x E 'D.
Here, D is all products provided as part of ESCI and has size of approximately million.
We use the SentencePiece tokenizer, Transformers for the encoder models in DE, and the Lazy Adam optimizer 3 Details are provided in Appendix B
Methods and Results. naive approach for this task is Joint Training, where DE is trained on the
union of Exain and Swain- We compare this with our vetrain-finetune recipe, where DE is pretrained on Emain then finetuned on Smain- The results are presented in Figure on Exact matches (Left) and Substitute matches (Right). It shows that the pretrain-finetue recipe performs better than joint training in terms of recall @k k for varying values of & E {100, 1000, 10000).
7 Conclusion
This paper studies the theory and practice of dual encoders (DE) for hierarchical retrieval (HR), the task where the document set is organized into a hierarchy. Through geometric analysis, we first validated rigorously that DEs capable of solving the HR problem despite the constraints from the Euclidean geometry. We then demonstrated through experiments that such DEs can be found in practice via standard DE training. Towards improving the practical performance of DE, introduced a iretrainffinetun recipe which addresses the challenge associated with long-distance pairs. Finally, the effectiveness of this recipe is verified real datasets including WordNet and ESCI shopping queries.
References
[1] Amazon Ads. 2024-12-15.
Accessed:
[2]
Ads. [twpah/eeeooooooooaoee/////aaeaa
20meaning Accessed: 2024-12-15.
[3] Lazy Adam. http:///www.nnnrrrrooooaaaaoaaod optimizzes//iiiieeo Laazyddd Accessed: 2025-1-24.
[4] Mierosoft Ads. Accessed: 2024-12-15.
[5] Kaikai An, Ce Zheng, Bofei Gao, Haozhe Zhao, and Baobao Chang. Coarse-to-fine dual en- coders are better frame identification learners. Findings of the Association for Computational Linguistics: EMNLP 2023, pages 13455-13466, 2023.
10

---

[6] Ben Athiwaratkun and Andrew Gordon Wilson. Hierarchical density order embeddings. In International Conference on Learning Representations. 2018.
[7] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models few-shot learners. Advances in neural information processing systems, 33:1 13:1177-1901, 2020.
[8] Wei-Cheng Chang, X Yu Felix, Yin-Wen Chang, Yiming Yang, and Sanjiv Kumar. Pre-training tasks for embedding- based large-scale retrieval. In International Conference on Learning Representations, 2020.
[9] Wei-Cheng Chang, Yu Felix X, Yin-Wen Chang, Yiming Yang, and Sanjiv Kumar. Pre-training tasks for embedding- based large-scale retrieval. In International Conference on Learning Representations, 2020.
[10] Felix Chern, Blake Hechtman, Andy Davis, Ruiqi Guo, David Majnemer, and Sanjiy Kumar. Tpu-knn: K nearest neighbor search at peak flop/s. Advances in Neural Information Processing Systems, 5589558115, 2022.
[11] Tejas Chheda, Purujit Goyal, Trang Tran, Dhruvesh Patel, Michael Boratko, Shib Sankar Dasgupta, and Andrew Mccallum, Box embeddings: An open-source library for representation learning using geometric structures. In Proceedings of the 2021 Conference Empirical Methods in Natural Language Processing: System Demonstrations, pages 203-211, 2021.
[12] Bhuwan Dhingra, Christopher Shallue, Mohammad Norouzi, Andrew Dai, and George Dahl. Embedding text hyperbolic spaces. Proceedings of the Twelfth Workshop on Graph-Bass Methods for Natural Language Processing (TextGraphs- 12), pages 59-69, 2018.
[13] Jeff Donahue, Yangqing Jia, Oriol Vinyals, Judy Hoffman, Ning Zhang, Eric Tzeng, and Trevor Darrell. Decaf: A deep convolutional activation feature for generic visual recognition. In International conference on machine learning, pages 647-655. PMLR, 2014.
[14] Octavian Ganea, Gary Bécigneul, and Thomas Hofmann. Hyperbolic entailment cones for learning hierarchical embeddings. In International conference on machine learning, pages 1646-1655. PMLR, 2018
[15] Chuan Guo, Ali Mousavi, Xiang Wu, Daniel N Holtmann-Rice Satyen Kale, Sashank Reddi, and Sanjiv Kumar. Breaking the glass ceiling for embedding- baasdd based classifiers for large output spaces. Advances in Neural Information Processing Systems, 32, 2019.
[16] Jiafeng Guo, Yixing Fan, Qingyao Ai, and W Bruce Croft. deep relevance matching model for ad-hoc retrieval. Proceedings of the 25th ACM international on conference on information and knowledge management, pages 55 64, 2016.
[17] Ruiqi Guo, Philip Sun, Erik Lindgren, Quan Geng, David Simcha, Felix Chern, and Sanjiv Kumar. Accelerating large-scale inference with anisotropic vector quantization. In International Conference on Muchine Learning, pages 3887-3896. PMLR, 2020.
[18] Yuan He, Zhangdie Yuan, Jiaoyan Chen, and Ian Horrocks. Language models as hierarchy encoders. arXiv preprint arXiv:2401.11374, 2024.
[19] Jeff Johnson, Matthijs Douze, and Hervé Jégou. Billion-scale similarity search with gpus. IEEE Transactions on Big Data, 7(3):535-544) 2019.
[20] Beatrice Laurent and Pascal Massart. Adaptive estimation of a quadratic functional by model selection. Annals of statistics, pages 1302-1338, 2000.
[21] Aditya Menon, Sadeep Jayasumana, Ankit Singh Rawat, Seungyeon Kim, Sashank Reddi, and Sanjiv Kumar. In defense dual-encoders for neural ranking. In International Conference on Machine Learning, pages 15376-15400. PMLR, 2022.
[22] George Miller. Wordnet: a lexical database for english. Communications of the ACM, 38(11):39-41 1995.
11

---

[23] Bhaskar Mitra, Nick Craswell, et al. An introduction to neural information retrieval. Foundations and Trends()) in Information Retrieval, 13(1):1-126, 2018.
[24] Maximillian Nickel and Douwe Kiela, Poincaré embeddings for learning hierarchical represen- tations. Advances in neural information processing systems, 30, 2017.
[25] Mingdong Ou, Peng Cui, Jian Pei, Ziwei Zhang, and Wenwu Zhu. Asymmetric transitivity pre- serving graph embedding. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pages 1105-1114, 2016.
[26] Maulik Parmar and Apurva Narayan. Hyperbox: A supervised approach for hypernym discovery using box embeddings. In Proceedings of the Thirteenth Language Resources and Evaluation Conference, pages 6069-6076, 2022.
[27] Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. Exploring the limits of transfer learning with unified text-to-text transformer. Journal of machine learning research, 21(140):1-65 2020.
[28] Chandan K Reddy, Lluís Marquez, Fran Valero, Nikhil Rao, Hugo Zaragoza, Sambaran Bandy- opadhyay, Amab Biswas, Anlu Xing, and Karthik Subbian. Shopping queries dataset: A large-scale esci benchmark for improving product search. arXiv preprint arXiv:2206.066 06588, 2022.
[29] Benjamin Rozonoyer, Michael Boratko, Dhruvesh Patel, Wenlong Zhao, Shib Sankar Dasgupta, Hung Le, and Andrew McCallum. Learning representations for hierarchies with minimal support. The eiiht Annual Conference on Neural Information Processing Systems, 2024.
[30] Alexandru Tifrea, Gary Becigneul, and Octavian-Fugen Ganea. Poincare glove: Hyperbolic word embeddings. International Conference on Learning Representations, 2018.
[31] Ivan Vendrov, Ryan Kiros, Sanja Fidler, and Raquel Urtasun. Order-embeddings of images and language. arXiv preprint arXhv:1511.0636// 2015.
[32] Luke Vilnis, Xiang Li, Shikhar Murty, and Andrew Mecallum. Probabilistic embedding of knowledge graphs with box lattice measures. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguisties (Volume Long Papers), pages 263-272, 2018.
[33] Luke Vilnis and Andrew McCallum. Word representations via gaussian embedding. 2015.
[34] Ivan Vulié, Daniela Gerz, Douwe Kiela, Felix Hill, and Anna Korhonen. Hyperlex: A large-scale evaluation of graded lexical entailment. Computational Linguistics, 43(4):781-835, 2017.
[35] Mengjia Xu. Understanding graph embedding methods and their applications. SIAM Review, 63(4):825-855 001,88555533.000 2021.
[36] Wayne Xin Zhao, Jing Liu, Ruiyang Ren, and Ji- Ji-Rong Wen. Dense text retrieval based on pretrained language models: A survey, ACM Transactions Information Systems, 42(4):1-60, 2024.
12

---

A Proof of Theorem 3.1
We now present the proof that our construction of embeddings solves the dual encoder embedding construction task. In what follows, write r= indicate the containment [x: y x y). and we assume n = m without loss generality.
Proof of Theorem 3.7] We begin by drawing standard Gaussian vectors .1,............................. .,, (0, Ia) E Rd (we will later normalize them). Next, we set q Vis. Ejes, Ty (here we abuse notation and think
of S; C [m]] to be the corresponding indices). Note that, by stability of Gaussian random variables and independence of the æj' "s, it follows that each coordinate of is distributed independently as standard normal distributed (i.e. (O, 1)). By standard x² concentration (e.g. Lemma [20]). for any single Gaussian vector g and value À > 0, if g (0, Ia) is vector of i.idd standard Gaussian variables, we have |1191|3 -d d s 2v 2λ with probability least 1 1 2 2 Setting À log and taking (llogn) n) with a sufficiently large constant, we have
Pr
|19112
s 5 n 2 n-
We can thus condition 12 d + dlg and l1 + 5 5 occurring for all i [n). which holds with probability at least 1 2n by union bound over the 2n vectors. Call this event &
Let be the edge set of the HR problem, namely, (1,j) j E S.. To further analyze construction, first define the event Eg that for all (i,j) & E, we have (g xz)ب < 100 n. Also define the event & that for all (i, E E we have K2 (EEss Tt, xz)l < 100yds log
We first analyze Pr [E2] If (1,5) $ E, then and x, are independent Gaussian vectors, thus by Gaussian stability we have
1/2
Kg,, 2,y1 ~ lgl- ||5yl12 s IglVd 1+ (lg(())
S Iglvd(11+ + 100)
where g ~ (0, 1) and we took d = 2(log n)) Via the density function of a Gaussian, we have Pr [gl ||اح||2 l|2 > 100g/l < 1/n". Thus, by a union bound over at most n² pairs, we have Pr [2] > 1 1/n2. For Eg, note that for any E [n]] with j E S;, the vector Eies,y 2, is distributed like (0, VSS. Ia): namely each coordinate is i.i.d. Gaussian distributed with variance |S;| - Thus
Σ MESU
Tt, Fy
~ / S. 1. 12, < Iglv/d(1 + 100))
where again g N/00 Following the same argument as above yields Pr [Ea] 1 n
In what follows, let
max(s, } and set dimension d = Cy log for sufficiently large constant C. Conditioned on ε,, Eg, we claim that the vectors .e..lll,.,,,,, #n/l|z,nlz satisfy the desired properties with threshold 4/5 For one, if j E St we have
q1 q1/llqq/le 11...l........................ 0n/llqul1e. F1 /
1
[|2,112 +
Σ
It: 2t
||
||
1/
S.
WES.
2
2
4
200
log
(5)
5d
100
ds log
3d
3
9/7
3
3/5
13

---

08
0.6
0144
overall
overal
0.2
0.0
25
50
100
125
150
175
200
0
25
50
75
303
125
150
175
200
25
50
75
100
125
150 175 200
Vain stwpo:
Fain Steps 130
Tran steps- 100
(a) p = 0.01
(b) 0.1
(c) p
Figure 6: Effect of re-balanced training data with varying ratio between the regular and the heavy-tail data on retrieval quality.
Table 3: Retrieved synsets for selected queries with 64-dimensional embeddings. For each of the three queries considered here, we list the relevant documents in the row "Groundtruth" with an ascending order in their distance to the query. For "Regular sampling" and "Pretrain- finetnneefttue"" we list top-k documents in ascending order of k. Documents retrieved but not in the groundtruth are underscored.
Query "car"
Groundtruth
feline reline Feline
carnivore carnivore chordate
placental placental vertebrati
mammal mammall animal
vertehraze wildeat placental
chordate domestic cat mammaal
animal veriehrate camivvree
organismm canine siiblea
Regular sampling
cal cal
Pretrain- finctune
Query "recline"
Groundiruth
rocliner recliner
amnchair amchair amchair
chair scar
scall chuir choir
Furmiture furnishing furnishing
Gurnishing: fumiture fumiiuue
instrumentality article instrumentalltt
artifact ware ortffac
whole toy dog cleaning
Regular sampling
Pretrain-finene
recliner
Query "motoris"
Groundtruth
motorist motorist matocist
driver operator operator
caussll agent plysical cacity
physical entity
Regular sampling
Pretrain finetune
driver
causall agent
Where used the bounds d. Next, for case two, when j & S,, using the events E,, Eg, we have
K
9:
| | Ka, 2z)ي S 1 d dlog
1
3 2d
VCy S r/2
150
(6)
|
|
Finally, note for runtime, needs only generate O(m) d-dimensional Gaussian vectors, and then compute each ga which takes Ö(sd) time each, thus the total time Ö(md nsd) as desired.
Where we took C > (2 4- 150)² which completes the proof as r/2 < r
B Implementation Details on ESCI Dataset
Here we provide additional details for experiments on ESCI. We use the SentencePiece model to tokenize the queries and products which fed standard 8-layer Transformers the architecture for the encoder models in DE. For the Transformer, we use model dimension 512, 8 attention heads, two-layer MLP with GELU activation and hidden dimension 4096 as the feedforward network. The output embeddings from the Transformer are mean-pooles and projected to 128 dimensions, followed by normalization to the unit l, sphere the final embedding. The model is trained with the Lazy Adam optimizer [ with a warmup stage of 2000 steps to a learning rate of le-4, followed by a linear decay to le-6 at step 50000.
C Additional Experiments for the Toy Setup in Section 4
In Figure 6
we provide additional results complementing Figure 3b These results reconfirm that rebalanced sampling cannot effectively solve the lost-in-the-long-dieee distance issue.
14

---

Overall
qd dist
80
qd dist 2
Recall (%)
dist 4
60
qd dist
40
qd dist 8
0
20
40
60
100
Train steps/ 100
Figure 7: Retrieval quality at varying query-document distances on WordNet, using hyperbolic embeddings of dimension 16. The peak performance is recall 45.4% obtained at step 49. This recall is higher than that with the Euclidean embeddings of the same dimension with standard training, which is at 43.0% (see T). demonstrating the superiority of hyperbolic spaces. Nonetheless, is worse compared to our
recipe, which has a recall of 60.1%.
D Comparison with Hyperbolic Embeddings on WordNet
For hierarchical relations, hyperbolic space is popular choice for addressing the shorteomings of the Euclidean space (24). Unfortunately, practical large-scale retrieval systems cannot widely adopt hyperbolic embeddings, due lack of efficient approximate k-nearest neighbor search algorithms in hyperbolic spaces. Nonetheless, for the purpose of scientifically understanding the capability of hyperbolic geometry for solving the HR problem, here implement hyperbolic embeddings and perform experiments on the WordNet dataset.
Specifically, train 16-dimensional hyperbolic embeddings on the same 10M normal sampling data as Section [6] Among many options for implementing hyperbolic embeddings, we use the reparameterization form in [12), using a learning rate of 0.01. All other training details are the same as those for Euclidean embeddings.
We evaluate the recall for query-document pairs at varying distances and report the results in Figure 7 We see that hyperbolic embeddings struggle obtain good balance between pairs with short vs long distances. Specifically, the model first learns to retrieve pairs with short distances, i.e. with distance and 2. As starts to retrieve longer distance pairs, the quality on the short distance pairs drops rapidly. The best overall recall (i.e., averaged over all distances) is 45.4% obtained at step 49, This recall better than that a DE trained on the same data, which 43.0% (see Table showing the superiority of embedding in hyperbolic space. However, it is still worse than our pretrain-finetune approach, which obtains a recall of 60.1%.
Ablation Studies for Finetuning on WordNet
In this section, we study the effect of hyper-parameters in our pretrain-finetune recipe for the WordNet experiments presented in Section 6 In particular, the results in Table T obtained with finetuning learning rate that is 0.001 times the one used during pretraining, and temperature that is increased from 20 during pretraining to 500 when finetuning. Here, we vary the choice of this learning rate multiplier and temperature during finetuning, and present the results in Figure g
For varying learning rate multiplier (see Figure Sal. we observe that the recall on long distance pairs improves as this multiplier is increased from a very small number of le-7 up to le-3. Crucially, we observe that the recall on short distance pairs not significantly affected, despite the fact that such pairs are not included in the finetuning data. However, when this multiplier is further increased from le-3, the model performance starts to deteriorate both short and long distance pairs.
In terms of temperature (see Figure 8b). we see that the best recall is obtained with a temperature of around 500. Both much smaller and much larger values of temperature lead to quality loss.
15

---

100
100
80
00
qd dast
qué dist
Rocall (%)
60
qdi
Recall (%)
60
qd d'st
qd. dist
10
qd
dist
20
0-
Learcing roto millippier
'lomperatane:
(a) Effect of Learning Rate
(b) Effect of Temperature
Figure 8: Effect of learning rate and temperature during the finetuning stage of the pretrain-finetune recipe for HR on WordNet.
Finally, Figure 8 shows that the model quality in terms of recall is not sensitive the choice of these two hyper-parameterss, making our method practically easy to tune.
16

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The claims in the abstract and introduction (1) feasibility of dual encoders for hierarchical retrieval, (2) empirical validation via learned embeddings, and (3) pretrain- finetune recipe that mitigates performance issues for long-distance pairs-are all rigorously supported by theory and experiments detailed in the main paper (see Sections 3-6).
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings. is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The paper discusses limitations such the dependency on embedding di- mension for success (Section 4), the failure mode of standard training for mingdiistance pairs (Section 5.1), and the risk of degrading performance on short-distance retrieval during fine-tuning. These are acknowledged and addressed with empirical findings and mitigation strategies.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limmtations" section in their paper.
The paper should point out any strong assumptions and how robust the results to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
17

---

3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: The main theoretical result (Theorem 3.1) includes all assumptions (c.g.. bounded size of relevant document set per query) and provides a complete constructive proof in Appendix A. The theorem is carefully motivated and used justify design decisions in experiments.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
The paper includes sufficient information for reproducing its results: synthetic data generation is described (Section 4), datasets (WordNet and ESCI) are public (Section 6), and implementation details (e.g., model architecture, optimization settings) are provided in Appendix C. Evaluation metries and sampling procedures are clearly explained. Guidelines:
Justification:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided instructions for how to replicate the results, access to a hosted model (e.g.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
detailed
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
18

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification:
We do not provide open access to the code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. cc/
sow.ssbbiisioooocoooiooooooo for more details. public/guie httee//uudde//eeebbiiieeeee
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed reproduce the results. See the NeurlPS code and data submission guidelines (https
tripps.cc/uublic//
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The paper provides sufficient experimental details. Section 4 outlines the syn- thetic setup including structures and sampling methods; Section 6 provides information on WordNet and ESCI datasets. Appendix C gives model architecture, optimization settings, tokenizer, training steps, and learning rates for ESCI experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: The paper does not report confidence intervals, variance, or statistical signifi- cance tests for the experimental results. Trends and improvements (e.g., recall) are clear and consistent across conditions.
19

---

Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: The paper provides a reasonable description of compute used. Section and Appendix C mention model size (8-layer Transformers with 512 hidden dimensions), batch size (4096), number of steps (up to 50k), and training procedures (e.g., learning rate schedules). While exact hardware details (e.g., GPU model, number of GPUs) are not specified, the scale of the experiments modest and consistent with common academic setups.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [NA]
Justification: The research does involve sensitive data, human subjects, biometric infor- mation, or real-world deployment that would invoke ethical concerns or require adherence a formal code of ethics. The work focuses on synthetic and public benchmark datasets (WordNet and ESCI) for algorithmic research in retrieval.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
20

---

The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: The paper discusses real-world applications in advertising (Phrase Match in online ads) and product search (Amazon ESCI) where hierarchical retrieval directly applicable (Section 1, Section 6.2). While no dedicated "societal impact" section is included, the implications of better retrieval systems are clearly articulated in motivating examples, and no negative societal impacts are anticipated from this line of work.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymeett of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
The paper does not propose or deploy models in high-risk domains such as healthcare, legal, financial, or safety-critical systems. The research is focused on information retrieval using public datasets (WordNet and ESCT) and does not require safeguards for fairness, robustness, privacy, or misuse prevention in its current scope.
Justification:
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
21

---

12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justificatiin: The datasets used in this Work-WordNeel and ESCI (Amazon Shopping Queries)-are both publicly available. WordNet is distributed under a permissive license (Princeton WordNet License), and ESCI is publicly released benchmark dataset as noted in [28]. These datasets are used in accordance with their respective terms, and unlicensed or proprietary assets are used.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, wwwprswipeeataeeeeeeeeeeepp thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [No]
Justification: This work does not introduce new dataset, model, or benchmark. All assets used (WordNet, ESCI, synthetic hierarchies) are pre-existing and publicly available. The primary contributions are theoretical analysis, algorithmic design (pretrain-finetune recipe), and empirical evaluation.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve any human participants, crowdsourced annotations, interviews, surveys, behavioral experiments.
Guidelines:
22

---

The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [Yes]
Justification: This study does not involve human subjects research and therefore does not require IRB approval.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: the core method development in this research does not involve LLMs as any important, original, or non-standard components
Guidelines:
The answer NA means that the core method development in this research does not involve L.LMs as any important, original, non standaandard components.
Please refer to our LLM for what should or should not be described.
23


Reviews:
[{"review_id": "Rs0nCzPt5L", "reviewer": "Reviewer_Dn6e", "summary": "This paper studies dual encoder (DE) models for information retrieval in the specific context of Hierarchical Retrieval (HR), where documents are organized in a hidden hierarchy, and a query should retrieve all of its ancestor nodes. The authors first provide theoretical guarantees that DEs are capable of solving HR if the embedding dimension scales appropriately with the depth and size of the hierarchy. They then identify a practical challenge -- retrieving distant ancestors becomes harder (termed the \"lost-in-the-long-distance\" problem). To address this, they propose a pretrain-finetune strategy: first training on standard data and then fine-tuning on long-distance query-document pairs. Experiments on synthetic trees, WordNet, and ESCI demonstrate improved performance, particularly for long-distance retrieval. The work bridges theoretical insight with practical system challenges and offers an algorithmic tweak to improve DEs on hierarchically structured data.", "questions": "- Why is there no comparison with hyperbolic embedding models (e.g., Poincare and hyperbolic embeddings), which also aim to solve hierarchical representation issues? These seem like direct competitors.\n- Can the authors elaborate on why the pretrain-finetune strategy works better than rebalancing? Is there an intuitive or theoretical justification?\n- How sensitive is the performance to the specifics of the fine-tuning stage (e.g., temperature, learning rate, early stopping)? Could you add ablations?\n- The theoretical results (Theorem 3.1) rely on access to S(q) sets. Can you discuss or experiment on how noisy estimation of these sets might affect the embedding quality?\n- Could you provide retrieval time and latency comparisons with other methods, particularly for large datasets? This would help validate the practical relevance.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n- Provides a constructive theoretical proof showing DE feasibility for HR under certain embedding dimension assumptions.\n- Empirical findings consistently validate the theoretical results across synthetic and real datasets.\n- Identifies and articulates a realistic failure case (lost-in-the-long-distance) that affects DEs in HR tasks.\n- Introduces a practical and simple pretrain-finetune training recipe to address the failure case.\n- Experimental results show strong improvements in recall for distant matches, especially in the WordNet dataset.\n\nWeaknesses:\n- Lack of baselines: The paper omits comparison with hyperbolic or other hierarchical embedding models (e.g., Poincare embeddings), which are directly motivated by similar geometric considerations.\n- The pretrain-finetune strategy is intuitive and potentially ad hoc. There is limited analysis on why it helps, beyond empirical results.\n- The novelty of the proposed algorithmic contribution (pretraining then fine-tuning) is limited -- it is a common ML technique and might be seen as an incremental tweak.\n- The theoretical analysis is insightful but assumes knowledge of the matching sets {S(q)}, which are not available in practical settings; this limits the practical relevance of Theorem 3.1.\n- Some claims, like DEs outperforming handcrafted embeddings in low dimensions (Fig. 2), are underexplored and not connected back to theory.\n- The ESCI experiment is a stretch from the core problem setting (HR), and the analogy to \"long-distance\" is loosely defined and not justified.", "was_revised": true, "final_justification": "Resolved issues:\n- Authors provided direct comparisons with hyperbolic embedding models\n- Authors clarified the rationale behind the pretrain–finetune approach vs. rebalancing and provided sensitivity analyses.\n- Authors explained that inference latency remains unchanged, preserving DE scalability.\n\nUnresolved issues:\n- The algorithmic novelty remains modest; the pretrain–finetune approach is conceptually simple and common in ML.\n- Theorem 3.1 still relies on impractical assumptions (exact S(q) sets), limiting its direct applicability.\n- Baseline coverage, while improved, could be broader and more systematically analyzed.", "rebuttal": "We sincerely thank the reviewer for the detailed and insightful feedback. We appreciate the accurate summary of our work and the challenging questions, which will help us improve the paper significantly. We address the noted weaknesses and questions below.\n\n**Comparison with Hyperbolic Models** \n\nHyperbolic models are not our direct competitors. While they are indeed well-suited for hierarchical data, as we note in Section 1.2, they are \"NOT suited for retrieval due to a lack of an efficient nearest neighbor search that hinders their applicability to large scale data\". Our goal was to investigate the capabilities and limitations of the widely-used Euclidean dual encoder (DE) architecture and provide a practical method to improve it without sacrificing its key advantage: scalability via efficient ANN search. We will revise Section 1.2 to make this motivation clearer and to better contextualize our work against these important baselines.\n\nThat said, we are happy to include additional experimental results with Hyperbolic models to situate our method into a broader context for interested readers. \n- On HyperLex (see Table 2), Poincare embedding obtained a Spearman’s rho of 0.512 according to ref. [24], which is better than our method (with rho = 0.415). \n- On WordNet (see Table 1), we conducted an additional experiment with Poincare embedding using the reparameterization approach in ref. [12] for embedding dimension = 16. We obtained an overall recall of 45.4% which is better than standard training of DEs (43.0%), but is worse than our pretrain-finetune approach (60.1%). To obtain more insights into the behavior of Poincare embeddings, we plotted the recall at varying distances between query and document, and observed that the model struggles to obtain a good balance between pairs with short vs long distances. That is, the model first learns to retrieve pairs with short distances, i.e. with distance 0 and 2. As it starts to retrieve longer distance pairs, the quality of the short distance pairs drops. \nWe will include these results in the revised version.\n\n**Novelty of the Pretrain-Finetune Recipe**\n\nWhile pretrain-finetune paradigm is common in ML, it is used primarily in the context of pretraining a large model followed by adapting such a model to a particular downstream task. It has never been used to address the lost-in-the-long-distance issue. \nWe see our primary contributions not as the invention of this paradigm, but as: (1) discovering and articulating the \"lost-in-the-long-distance\" phenomenon as a key failure mode for DEs in hierarchical retrieval , and (2) identifying that this recipe offers a simple and effective solution, especially when contrasted with the more intuitive but much less effective rebalancing strategy.\n\n**Intuition on Pretrain-Finetune Recipe vs Rebalancing**\n\nOur experiments show that rebalancing improves long-distance recall at the severe cost of short-distance performance (Figure 3b , Table 1). We hypothesize this is because the model is forced to solve a difficult trade-off between two distinct objectives simultaneously. Our two-stage recipe decouples these objectives. Pretraining first grounds the embeddings in the local, short-distance structure. The finetuning stage then gently adjusts these embeddings to accommodate the global hierarchy, improving long-distance recall while preserving the already-learned local structure (Figure 3c). \n\n**Practicality of Theorem 3.1**\n\nThe theorem's purpose is to provide a formal existence proof that answers our first key question, \"Q1: Does there exist Dual Encoders that solve Hierarchical Retrieval?\". By proving feasibility, it motivates the subsequent empirical investigation into whether such embeddings can be learned from data, which is the practical focus of Sections 4-6.\n\n**Retrieval time and latency** \n\nAt inference time, the model is a standard DE. Therefore, there is no change in retrieval latency compared to a conventionally trained model, which is a key practical advantage. The computational difference is in the training, which is a two-stage process. We will clarify this in the paper.\n\n**Ablations**\n\nIn response to this great comment, we conducted sensitivity analysis on the effect of learning rate and temperature during finetuning for our HR on WordNet experiments. \n- For varying learning rates, we observe that the averaged recall across all distances are within 1% difference for a wide range of learning rate choices in the range of 1e-4 to 3e-3 (main results in the paper are reported for 1e-3). \n- For varying temperatures, we observe that the averaged recall across all distances are within 1% difference for a wide range of temperature choices in the range of 500 to 2000 (main results in the paper are reported for 500). \n\nWe will include this discussion and the corresponding plots in the revised version."}, {"review_id": "ITvA0YKZ50", "reviewer": "Reviewer_XaUt", "summary": "The paper studies a new model of \"hierarchical retrieval\" and dual encoder design and training for it. In normal retrieval, the dual encoder is trained with positive example {(q,d+)} to predict relevant docs for a query. This paper extends this to the case where queries form a somewhat hierarchical structure, or rather a DAG. If there is an edge from q1->q2 in the DAG, docs relevant for q1 must also be relevant to q2. The motivation seems reasonable in that we often want to select, and refine relevance matches.\n\nThe paper first studies an entirely toy dataset and simple tree-structured DAG, and studies simple random guassian and learn embeddings. The paper projects and matches the dimensionality needed to get 95% recall. The paper also studies the depth and imbalance of DAG in synthetic settings, and offers ideas on how to adjust the training. The paper then studies wordnet dataset and relations between word categories and trains a model that achieves reasonable accuracy for it.\n\nWhat is not clear is how this applies to the e-commerce scenarios that motivate the problem in intro. If I had a shopping catalog with more complex documents with their own multi-modal embeddings, and weak signal, with multiple docs matched per query category, how does this pipeline extend and scale?", "questions": "-  Can this formulation extend to product catalogs and multi-modal docs and nebulous query intent. What if the DAG is over precisely stated query categories, but the queries are slightly variants of categories.\nupdate: Authors state this is possible. Concrete proof might be beyond the scope of this paper.\n\n- Are there alternate ways of training for this problem and how does this approach compare? For example, would treating DAG as flat structure and using extreme multi-label classification work?\nupdate: Authors state that XMLC are impractical, however XMLC methods have been proved to be practical and are deployed at millisecond-latency at scale.", "limitations": "na", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- Interesting new variant of standard relevance problem \n- good set of toy experiments that set up for the real problem\n- A good answer for small real world datasets\n\nWeakness\n- Unclear whether this formulation can take on and scale to real-world problems\n- Are there alternate ways of training for this problem and how does this approach compare?", "was_revised": true, "final_justification": "Updated the review. Disagree with on one of the rebuttal points, reflected that in update. Score unchanged.", "rebuttal": "We thank the reviewer for the positive feedback and for finding our problem variant \"interesting\" and our experiments well-designed. \n\n**Extending to Complex, Real-World Scenarios**\n\nThis is an excellent question that gets to the heart of practical applicability. Our approach is highly adaptable precisely because the dual encoder (DE) architecture is modular. The core of our contribution is the pretrain-finetune training recipe, which is agnostic to the specifics of the encoders. In our work, we use lookup tables for the WordNet experiments and modern Transformer-based text encoders for the ESCI shopping dataset. For a multi-modal product catalog, these encoders could be readily replaced with architectures that process both text and images (e.g., CLIP-style models) without changing the fundamental training strategy: pretrain on \"exact\" or \"primary\" matches, then finetune on \"substitute,\" \"broader,\" or other \"long-distance\" matches. The ESCI experiment is a direct step toward showing this real-world applicability.\n\n**Alternate Training Formulations**\n\nWe thank the reviewer for this insightful question about alternate training formulations. It is indeed possible, as the reviewer suggests, to frame our Hierarchical Retrieval (HR) task as an Extreme Multi-Label Classification (XMLC) problem by \"flattening\" the document hierarchy and treating each document as an independent label.\nHowever, this approach could be suboptimal as many common XMLC methods are not well-suited for the practical constraints of large-scale retrieval systems, for reasons beyond just the loss of the hierarchical structure. \n\n- Modern retrieval systems require millisecond-level latency. Alternate XMLC methods, such as One-vs-All (OVA) makes a prediction by running the query through a unique classifier for every document in the corpus. The linear cost of this operation is too slow for any real-time application. \n\n- Moreover, real-world document collections are constantly growing. With our embedding-based approach, adding a new document is trivial: we generate its embedding and add it to the ANN index without retraining the model. In contrast, adding a new document (i.e., a new \"label\") to a tree-based or OVA-based XMLC model is far more complex and would likely require significant retraining or model restructuring.\n\nTherefore, while one could apply XMLC methods by flattening the hierarchy, this would not only discard the crucial hierarchical information that our method is designed to capture but would also likely lead to a system that is too slow and inflexible for a practical retrieval setting. We chose our approach because it both models the hierarchical relationships and aligns with the high-performance architecture of modern retrieval systems."}, {"review_id": "uJAlyC42Iu", "reviewer": "Reviewer_hWtC", "summary": "This paper studies hierarchical retrieval (HR), where documents are organized in a hierarchical structure and the goal is to retrieve all ancestors of a query in the hierarchy. The authors first prove that dual encoders are theoretically feasible for HR when the embedding dimension is linear in hierarchy depth and logarithmic in document count. They then identify a \"lost-in-the-long-distance\" phenomenon where retrieval accuracy degrades for documents further away in the hierarchy. To address this, they propose a pretrain-finetune recipe that first pretrains on regular data then finetunes on long-distance pairs. Experiments on demonstrate that this approach significantly improves long-distance retrieval performance.", "questions": "1. Generalization: How does the pretrain-finetune recipe perform on hierarchies with different structural properties (e.g., varying branching factors, irregular depth)? What are the key hierarchy characteristics that determine success?\n\n2. Computational analysis: What is the computational overhead of the two-stage training compared to standard approaches? How does the method scale with hierarchy size and depth?", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Quality:\n\nStrengths: Rigorous theoretical analysis with constructive proof establishing feasibility bounds; systematic experimental validation from synthetic to real data; comprehensive evaluation across multiple metrics and datasets\n\nWeaknesses: No statistical significance/cost analysis\n\nClarity:\n\nStrengths: Well-motivated problem with clear real-world applications; excellent progression from theory to synthetic experiments to real applications; clear mathematical exposition with intuitive explanations\n\nSignificance:\n\nStrengths: Highlights a practical failure mode for DEs and offers a simple fix requiring no model changes.\n\nWeaknesses: Limited scope of evaluation (only hierarchical retrieval tasks); unclear generalization to other asymmetric retrieval problems;  unclear impact for very large corpora or LLM-based encoders\n\nOriginality:\n\nStrengths: First formal margin bound linking hierarchy depth to DE dimension\n\nWeaknesses: Pretrain/finetune idea is incremental relative to curriculum or hard-negative mining", "was_revised": false, "final_justification": "", "rebuttal": "We are very grateful to the reviewer for the thorough review and the positive assessment of our paper's quality, clarity, and originality. We appreciate that you found our theoretical analysis \"rigorous\" and our contribution of identifying a failure mode and offering a simple fix to be significant. \n\n**Generalization to Different Hierarchies**\n\nWhile our synthetic experiments use perfect trees for controlled analysis, our main real-world experiment is on WordNet, which is a large, complex, and irregular directed acyclic graph (DAG), not a simple tree. The fact that our method yields significant improvements on WordNet (e.g., boosting recall on long-distance pairs from 19% to 76%) demonstrates its effectiveness on real-world, non-uniform hierarchies.\n\n**Computational Overhead** \n\nAt inference time, our method has zero overhead. The final model is a standard dual encoder, and its retrieval latency is identical to that of a model trained via a single-stage process. The overhead exists only during training, as our method involves two stages. On WordNet, pretraining takes 50k training steps while finetuning only takes 700. On ESCI, pretraining and finetuning takes 30k and 50k training steps, respectively.\n\n**Statistical Significance** \n\nWe acknowledge in our paper checklist that we did not report error bars or formal statistical significance tests. We agree this would strengthen the paper. However, we would like to point out that the performance improvements shown are very large and consistent across multiple datasets and embedding dimensions. For example, in Table 1 (d=64), our method improves the minimum recall from 19.4% to 75.7% and the overall recall from 71.4% to 92.3%. We believe these substantial gaps provide strong evidence for the effectiveness of our approach.\n\n**Novelty of Pretrain-Finetune**\n\nWhile pretrain-finetune paradigm is common in ML, it is used primarily in the context of pretraining a large model followed by adapting such a model to a particular downstream task. It has never been used to address the lost-in-the-long-distance issue. \nWe see our primary contributions not as the invention of this paradigm, but as: (1) discovering and articulating the \"lost-in-the-long-distance\" phenomenon as a key failure mode for DEs in hierarchical retrieval, and (2) identifying that this recipe offers a simple and effective solution, especially when contrasted with the more intuitive but much less effective rebalancing strategy."}, {"review_id": "qUR5x5k0PS", "reviewer": "Reviewer_zvXP", "summary": "The paper considers hierarchical retrieval where query and documents are organized in a DAG. The paper proves that hierarchical retrieval can be learned with dual encoder through a constructive algorithm, then identified a lost-in-the-long-distance problem under a standard retrieval learning procedure. After that a pretrain-finetuning method is proposed to fix the problem. Two datasets are considered and goo results are shown. However, there are also some concerns on the proposed approach.", "questions": "1. How to apply the method without distances on the DAG as input?\n2. Any intuition why the proposed pretraining-finetuning works better?\n3. discuss the requirements for pretraining-finetuning", "limitations": "limitation discussion is not complete, for example, one apparent limitation is that the proposed pretraining-finetuning method may not work well if the number of exact match data point is limited.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strong points: \n1. The paper is well organized and informative. While the proposed pretrain-finetuning procedure is simple, the process of developing it is informative and I learned something new from it. \n2. The paper proves that dual encoders are feasible to solve hierarchical retrieval as long as the embedding dimension is large enough. \n3. A simple pretrain-finetuning is proposed to fix the lost-in-the-long-distance problem and good empirical results are shown.\n\nWeak points:\n1. It is claimed that the algorithm does not require DAG as input, however, the main algorithm in Section 5.2 requires the distance on the DAG as input. In real-world applications, without the DAG, how can one get the distances?\n2. It is unclear why pretrain-finetuning would fix the lost-in-the-long-distance problem? Why it is better than mixed training? Is there any intuition on this? \n3. There are prerequisites for pretrain-finetuning to work better than mixed training, but it is not discussed at all in the paper. For example, one simple case where there are only a few data point for exact match, so that the model is under-trained when pre-training only on the exact match data, I would imaging pretrain-finetuning to be worse than mixed training. It would be better to discuss when pretrain-finetuning works better.", "was_revised": true, "final_justification": "my concerns are addressed", "rebuttal": "We thank the reviewer for the thoughtful review and for finding our paper \"well organized and informative”, the feasibility proof valuable, and the empirical results compelling. \n\n**How to Apply the Method without DAG Distances**\n\nThis is an excellent point, and we apologize for the lack of clarity. The key point, which we will clarify in the revision, is that our recipe does not require the full DAG or precise path lengths. It only requires a proxy for distance that allows us to partition the training data into two sets: a \"short-distance\" (or \"easy\") set for pretraining, and a \"long-distance\" (or \"hard\") set for finetuning. This proxy can be readily available in practice or easy to obtain:\nOn the ESCI shopping dataset, the dataset's labels directly provide this split: we treat \"Exact\" matches as short-distance and \"Substitute\" matches as long-distance.\nIn some applications, one may be able to use a simple heuristic (e.g., direct parent-child links vs. all other ancestors) to create the finetuning set.\nHuman annotation of the training dataset into short vs long distance pairs is another option and such a binary annotation is significantly easier to obtain than constructing the full DAG.\n\n**Intuition for Why Pretrain-Finetune Works Better** \n\nAs our experiments show, mixed/rebalanced training forces the model to learn two different structures simultaneously—the local structure of exact matches and the global structure of distant ancestors. This creates a difficult optimization trade-off, where improving on one often comes at the expense of the other (as seen in Figure 3b and Table 1).\nOur two-stage recipe decouples these objectives. The pretraining stage grounds the model by learning robust embeddings for the local, short-distance structure. The finetuning stage then acts as a gentle adjustment, adapting these well-formed embeddings to the more challenging long-distance pairs without catastrophically forgetting the initial structure.\n\n**On Prerequisites and Limitations**\n\nThis is a valid concern and an important limitation. Our recipe implicitly assumes that there is sufficient \"short-distance\" data to learn a meaningful initial representation during pretraining. If this data is extremely sparse, pretraining may be ineffective, and a mixed training approach might indeed perform better. We thank the reviewer for this insight. We will explicitly add this to our section 5.2, stating that the effectiveness of our recipe depends on having a reasonable amount of data for the initial pretraining stage."}]

Author rebuttal:

Meta-review: The paper studies hierarchical retrieval (HR) with dual encoders (DEs). It (i) provides a constructive feasibility result relating HR solvability to embedding dimension (linear in depth, logarithmic in corpus size), (ii) empirically identifies a “lost-in-the-long-distance” failure mode where distant ancestors are under-retrieved, and (iii) proposes a simple pretrain-finetune recipe that substantially improves long-distance recall while preserving near-distance performance. Experiments span synthetic trees, WordNet, and an e-commerce (ESCI) setting.

Review synthesis:
- Positives (broadly shared): clear writing and problem framing; a useful theoretical existence result; well-designed empirical study that isolates a practical failure case; simple training recipe with strong gains on long-distance recall; retention of DE latency/scalability at inference.
- Concerns (initial): limited baselines (notably hyperbolic/hierarchical embeddings), modest algorithmic novelty (recipe might appear ad hoc), practicality of the theorem (assumes access to sets/distances), and questions about real-world scalability and alternative formalisms (e.g., XMLC).
- After rebuttal: Authors added comparisons to hyperbolic models, provided sensitivity analyses (LR/temperature), clarified that inference latency is unchanged, and articulated when/why the two-stage recipe can outperform rebalancing. Several reviewers increased or maintained borderline-accept scores; remaining concerns focus on modest novelty and the practicality limits of the theorem.


Remaining weaknesses:
- Novelty: The training recipe is incremental conceptually, though well-motivated and effective.
- Theory–practice gap: The feasibility theorem relies on information (exact sets/distances) that may be unavailable; its role is primarily existential.
- Scope: Results are concentrated on HR; broader generalization (to other asymmetric retrieval tasks, very large corpora, and multi-modal encoders) is argued but not fully demonstrated.
- Alternatives: XMLC and other pipelines are not systematically benchmarked at scale; one reviewer notes their practicality at ms-latency.

**Camera-ready suggestions**:

Integrate the new hyperbolic baselines and distance-stratified plots; clearly position them w.r.t. DE scalability and ANN search.

Expand sensitivity/stability analyses (learning rate, temperature, fine-tuning steps) and report statistical significance/error bars where feasible.

Make explicit the data prerequisites (how to obtain short/long partitions; failure modes when “short-distance” data is scarce).

Clarify the theorem’s role (existential) and discuss how approximate distance proxies affect learning.

Add a concise discussion/experiment contrasting against a representative XMLC baseline at realistic scale/latency, or justify its omission with concrete system constraints.
Decision: Accept (poster)