Fully Dynamic Embedding into $\ell_p$ Spaces

We thank the reviewer for their detailed reading of our paper. We are glad that the reviewer found our theoretical analysis "interesting" and "elegant". We address the reviewer's concerns and comments below.

how the paper contributes to the ICML community ... require rewriting ..

We have discussed these motivations in the first 3 paragraphs of the introduction.
We understand the reviewer's concerns and have revised the paper by incorporating the following text.
(To keep the paper within the page limit, we have slightly shortened the overview of techniques section and deferred the proof of non-contractivity to the appendix.)

Embeddings are a cornerstone of modern machine learning, powering models from word2vec to large language models (LLMs). These methods embed discrete data—like words or tokens—into continuous spaces, enabling geometric reasoning about semantics. Embedding-based architectures have driven advances in language understanding and generation.

Among embedding targets, $\ell_p$ spaces (especially $\ell_2$) have emerged as the standard representation space in modern ML. This is due to (a) their interpretability—distances and angles have clear geometric meaning—and (b) the fact that many key primitives are much more efficient in $\ell_p$ spaces. For example, nearest neighbor search in high dimensions is routinely performed using locality-sensitive hashing (LSH), designed specifically for $\ell_2$ and other vector norms. Similarly, fast kernel approximations, attention mechanisms, and geometric reasoning in LLMs all leverage the vector structure of $\ell_p$ spaces.

Despite their practical dominance, our theoretical understanding of embeddings remains limited. Data in domains like NLP is high-dimensional, structurally complex, and hard to formalize. Theoretical work addresses this via clean abstractions like graph metrics. Such abstractions play a role similar to that of PAC learning in classification theory: while not modeling every neural detail, they offer a principled framework for understanding fundamental capabilities and limits.

The dynamic nature of data in modern systems further motivates our work. In applications involving LLMs, the relevant context or knowledge can shift rapidly. Embedding methods must therefore adapt efficiently. Traditional techniques, however, are typically static and require expensive recomputation. Our work initiates the study of fully dynamic embeddings into $\ell_p$ spaces, a widely used metric class in ML. Modeling data changes via a dynamic graph lets us explore embeddings with provable guarantees on distortion, non-contractivity, and efficiency. While theoretical, our formulation reflects real challenges in streaming or interactive systems—where representations must update continually without compromising structure or tractability.

... empirical evaluations would be necessary ...

We have performed experiments evaluating our embeddings here: dropmefiles.com/dfsfg

We emphasize again that the main focus of our paper is providing a theoretical understanding of dynamic embeddings.

What oracle is available? ... How many edges are allowed to be appended at once?

We assume that the graph is stored in memory using a standard adjacency list representation. Edge updates (insertions or deletions) occur one at a time, and the embedding is updated immediately after each modification. That said, our algorithm and analysis are robust enough to conceptually handle small batches of updates—for instance, a polylogarithmic number of changes—without meaningfully affecting guarantees.

Current version of Theorem 1.1

While we believe our current phrasing follows standard presentation in the literature, we agree that explicitly associating Theorem 1.1 with Algorithm 1 would improve clarity.
The paper has been revised accordingly.

Could Theorem 1.2 not be generalized ...

We thank the reviewer for this excellent question! Indeed, the lower bound in Theorem 1.2 applies to any class of embeddings based on labeling—that is, embeddings where each point is mapped to a label (e.g., a coordinate vector or symbolic descriptor), and distances are computed solely from these labels. For example, points could be mapped to coordinates on a sphere, with distances measured via spherical distance.
We will apply the generalization in our revision.

If you feel our response has adequately addressed your major concerns, we would appreciate it if you possibly adjust your score accordingly.

We thank the reviewer for their careful reading of our paper. We are glad that the reviewer believes our "expositions are clear" and that "the ideas of maintaining edge-dominant trees and randomly perturbing the edge weights are interesting". We address the reviewer's concerns and comments below.

Discussion of most relevant literature ...

We thank the reviewer for this suggestion. In the current submission, our goal was to introduce the most relevant prior work directly in the Introduction as part of the motivation, and then focus the main body of the paper on our technical contributions. Given space constraints, we chose to defer the more exhaustive Related Work section to the appendix, as is common in theory papers. That said, we understand the reviewer’s concerns and have revised the paper to ensure that key citations now appear in the main text. Specifically, we now include a concise summary of relevant prior work in the fourth paragraph of the Introduction, giving a briefer description of low-stretch spanning trees (which are less central to our contributions), and adding a short discussion of online embeddings, which are thematically related.

Proofreading and typos.

We thank the reviewer for bringing this to our attention. We have corrected the noted issues in the revised version and will continue to carefully proofread the paper to catch any remaining small errors.

Negative result is less interesting.

We respectfully disagree with this assessment. As we explain in the paper, the negative result serves an important role: it demonstrates the tightness of the assumptions underlying our positive result. While the lower bound builds on prior ideas, our version extends the result to a more general setting, in particular to embeddings with low expected distortion that are non-contractive with high probability. This generalization is not only technically meaningful, but also conceptually clarifying—it helps justify the constraints and guarantees we adopt in our main algorithmic result.

... relies heavily on prior work.

While our construction draws on prior work on tree embeddings, we do not view this reliance as a weakness. On the contrary:

• Our analysis of vector embeddings uncovers nontrivial properties of the tree embeddings used in dynamic settings—properties that, to the best of our knowledge, have not been explicitly documented before. Given the technical depth of the underlying work, these observations are subtle and require careful reasoning.
• In addition, our paper establishes a conceptual and technical connection between dynamic tree embeddings and vector embeddings into ℓₚ spaces, which had not previously been explored in this context. While such a connection may seem plausible in hindsight, it is far from obvious, especially given the nontrivial obstacles highlighted in the "Low-distortion trees" paragraph of Section 1.2.
• Finally, we note that prior constructions—such as low-stretch spanning trees—are themselves composed of incremental innovations on existing techniques. In this spirit, our work adds new insights and extends the applicability of known ideas to a new and natural problem setting.

If you feel that our response has adequately addressed your major concerns, we would appreciate it if you possibly adjust your score accordingly.

We thank the reviewer for their thoughtful and constructive review. We appreciate the positive assessment that our results are "significant contributions to the field" and that "The clarity and precision of the theoretical analysis are well".

Below, we respond to the reviewer’s specific concerns:

... the distinction between the static and dynamic settings ...

Thank you for the suggestion. We have revised paragraph 4 of the Introduction to further clarify this. In short, static settings assume the input data is fixed, whereas in the dynamic setting, the data changes over time via updates. In our model, these updates take the form of insertions and deletions of edges in the underlying graph, which is the standard model used in dynamic graph theory. The goal is to maintain a good output—here, a low-distortion embedding—even as the input graph evolves.

The use of $\ell_p$ spaces ...

In practice, $\ell_2$ embeddings are a standard representation in many ML tasks—including word2vec, LLMs, kernel-based models, and LSH-based nearest-neighbor search—due to their interpretability and computational efficiency. These embeddings underpin similarity search, clustering, and classification across numerous applications. By focusing on $\ell_p$ spaces, we aim to provide theoretical tools directly aligned with this widely used embedding paradigm.

... empirical results ...

We have performed experiments evaluating our embeddings here: dropmefiles.com/dfsfg

We emphasize however that the main focus of our paper is providing a theoretical understanding of dynamic embeddings, akin to the role that PAC learning theory plays in understanding classification. Just as PAC models offer deep insights into learning even when they abstract away the full complexity of modern neural networks, our model—though idealized—helps clarify the possibilities and limitations of embedding dynamic structures.

... including pseudocode

We have aimed to provide pseudocode or detailed algorithmic descriptions for all major components in the main body—particularly for Algorithm 1. Additionally, we have now included pseudocode in the appendix for the lower bound construction used in the proof of Theorem 1.2, to further aid readability.

... exploration of other dynamic graph problems, such as dynamic shortest path problems ...

We thank the reviewer for this suggestion and have expanded on this in Appendix A.

If you feel that our response has adequately addressed your major concerns, we would appreciate it if you possibly adjust your score accordingly.

We thank the reviewer for their thoughtful and detailed review. We are particularly grateful for the positive assessment that the paper is "well written" and that the problem is "of fundamental importance to many communities." We're also glad that the reviewer appreciated the elegance and care in our technical approach, particularly the reduction to dynamic tree embeddings.

Below we respond to the specific points raised:

Maybe discussing the applications where implicit embeddings would make sense?

Thank you for this helpful suggestion. In many practical settings, maintaining explicit embeddings is either infeasible or unnecessary. For example:

• In large-scale systems, memory constraints often prevent storing the entire embedding, and only pointwise access to node embeddings is needed at query time.
• Many downstream tasks—like nearest neighbor search, link prediction, or routing—only require on-demand access to distances or individual coordinates, not the full embedding at once.

In such scenarios, implicit embeddings provide a flexible and scalable alternative, and our work offers strong theoretical guarantees for maintaining them efficiently in dynamic settings.

Section Embedding in Page 4, I think you have messed up rho with d' — please double check.

Thank you for catching this. You are correct; the equations should say $d'(\rho(u), \rho(v))$ instead as we are calculating the distance of the embedded points in the embedding space. We have revised the paper accordingly.

If you feel that our response has adequately addressed your major concerns, we would appreciate it if you possibly adjust your score accordingly.