Vector Database Watermarking

Dear Reviewer SNQH:

We sincerely appreciate your constructive comments and insightful observations. In response to your suggestions, we have supplemented our experiments and further clarified the theoretical details. If our response has addressed your concerns, we kindly ask that you consider raising your rating, for which we would be most grateful. If you have any further suggestions or concerns, we will continue to respond positively and improve our work.

Weakness 1 & Question 1.

The TVP scheme uses basic graph metrics like degree and edge length. Have the authors considered more refined measures, such as spectral properties or centrality, to improve carrier selection and theoretical grounding?

Thank you for your valuable suggestions. Currently, the TVP strategy primarily selects carrier vectors based on the fundamental structural characteristics of the HNSW graph, utilizing each node's degree and edge length to construct transparency scores. This method is efficient in implementation and has already demonstrated significant performance improvements. In fact, node degree has been widely regarded as a measure of centrality in graph theory. TVP has preliminarily embodied the concept of degree centrality and further enhanced the discrimination of “transparency” through edge length information. We fully agree with the reviewers' perspective that more refined graph theory metrics can uncover nodes' deeper structural roles within the graph, potentially providing a more robust theoretical foundation and selection precision for carrier selection. In future work, we plan to systematically incorporate these more complex graph metrics to further enhance TVP's theoretical rigor and application performance.

Weakness 2 & Question 2.

The TVP scheme's performance and the robustness of the transparency parameter (ts) under different HNSW configurations.

Thank you for your interest in the stability and generalization capabilities of TVP. We fully agree on the necessity of verifying the robustness of the method under different HNSW configurations.

Based on your feedback, we evaluated the average number of missed queries (AMQ) and average number of false queries (AFQ) introduced by TVP under various HNSW parameter settings ($M \in \{4, 8, 12, 16\}$ and $efConstruct \in \{50, 100, 150\}$), with the number of retrieved neighbors fixed at $k = 100$. The results are summarized in Table 1.

Table 1: Embedding effects of TVP under different parameter configurations

It can be seen that regardless of how the HNSW parameters change, the AMQ/AFQ values of TVP remain at a low level, indicating minimal impact on queries. This demonstrates that TVP has good adaptability to different parameter configurations. Additionally, to verify the stability of the transparency parameter ts under different HNSW configurations, we calculated the Pearson correlation coefficient between the ts value of each vector and its actual query frequency for different parameter combinations. The results are shown in Table 2.

Table 2: Pearson correlation coefficient between the ts of vectors and the number of times they are queried under different parameter configurations.

These results indicate that, under all parameter settings, ts maintains a significant negative correlation with vector query frequency (Pearson coefficients all below -0.66), suggesting that ts is a stable and generalizable transparency metric that can reliably guide carrier vector selection.

In summary, we believe that TVP continues to demonstrate consistent advantages under different HNSW parameter configurations, and its core idea (screening transparent vectors via ts) exhibits excellent robustness and generalization capabilities.

Question 3.

Experiments on other datasets.

Since “transparent” vectors (i.e., vectors with relatively low query frequencies) are common in any dataset, we speculate that the TVP method has good cross-dataset generalization capabilities.

To validate this hypothesis, we conducted extended experiments on two widely used deep learning embedding datasets: arxiv-nomic-768-normalized (derived from VIBE, representing text summaries) and deep1b (a classic large-scale image vector dataset). The experimental parameters were consistent with those in the paper. We evaluated the average missed queries (AMQ) and average false queries (AFQ) caused by different watermark embedding schemes, with experimental results shown in Tables 3 and 4.

Table 3: Experimental results on the Deep1b dataset

Table 4: Experimental results on the arxiv-nomic-768-normalized dataset

It can be observed that, on both datasets, the TVP scheme achieves significantly lower average missed query counts (AMQ) and average false positive query counts (AFQ) compared to other methods. This indicates that the strategy of prioritizing “transparent” vectors for modification can also reduce query errors on other datasets, thereby validating the cross-dataset generalization capability of our method.

Dear Reviewer ieq6:

We sincerely appreciate your insightful and constructive feedback. In response to your comments, we conducted a series of additional experiments and analyses, including evaluating standard ANN recall metrics (e.g., R@1), the variance and maximum value of query errors, and the compatibility of our method with vector quantization (VQ) technology. These efforts reflect our deep respect for your feedback. If our modifications meet your expectations, we would be grateful if you could consider raising your rating. If there are any further questions or concerns, we welcome your continued suggestions, and we will actively work to further improve the paper.

W1 & Q1.

Modifying vectors will result in performance degradation. Standard ANN evaluation metrics such as R@1 should be added.

We have conducted a supplementary assessment of the impact of TVP on standard ANN metrics, recording the recall rates of the vector database without watermarks and after embedding watermarks. The experimental results are shown in Table 1.

Table 1: Changes in ANN recall rates before and after TVP watermark embedding

It can be seen that the impact of TVP on all recall metrics is very limited, with minimal performance degradation. We completely understand your concern about “performance loss due to embedding.” This is a common issue faced by most perturbation-based watermarking schemes, not unique to TVP. However, unlike the “using the connectivity of the ANN graph” method, perturbation-based watermarking offers greater robustness, making it difficult for attackers to remove the watermark through simple index reconstruction. This provides a more reasonable trade-off between security and practicality.

W2 & Q2.

As mentioned in Weakness 2, it would be beneficial to provide the variance and maximum values of MQ and FQ instead of the average.

Thank you for your valuable suggestions. To conduct a more comprehensive analysis of the impact of TVP on query behavior, we conducted experiments and recorded the variance and maximum values of missed queries (MQ) and false queries (FQ) under each scheme. The results are shown in Table 2.

Table 2: Variance/Maximum Values of MQ and FQ for Different Schemes

As can be seen from the table, the fluctuations in MQ and FQ caused by TVP are significantly smaller than those caused by other methods, with both variance and maximum values being notably lower. This indicates that TVP more effectively controls query errors, not only achieving a smaller average value but also minimizing the impact in worst-case scenarios, thereby demonstrating greater stability.

W2 & Q2 Follow-up.

Although the overall impact is small, performance may degrade significantly when the modified vector becomes the top-1 nearest neighbor. Comparison results between such queries and regular queries should be provided.

Thank you for your insightful comments. We fully agree that analyzing specific queries where the Top-1 nearest neighbor is the modified vector can provide a deeper understanding of potential performance degradation.

To address this issue, we conducted an additional experiment, dividing all queries into two groups:

• M group (modified): Queries where the Top-1 nearest neighbor is the modified vector;
• U group (unmodified): Queries where the Top-1 nearest neighbor is the unmodified vector.

We then compared the recall rates (R@k) of the two groups. The results are shown in table 3.

Table 3: Nearest neighbor query performance of the two vector groups.

Although Group M shows a slight decrease in performance at R@1 (approximately 4.5%), its performance rapidly converges with Group U as k increases. It is worth noting that only 4.61% of queries belong to Group M, indicating that after adopting the “transparent vector priority” strategy, very few modified vectors become the first nearest neighbor. Therefore, even though there is a certain performance difference at R@1, its impact on the overall retrieval effectiveness remains limited.

W3 & Q3.

As mentioned in Weakness 3, bit flips can completely alter the feature information when used together with VQ techniques like product quantization. Since HNSW and VQ techniques are often used in combination, an ablation study on this case should be provided.

Thank you for pointing out the potential serious implications of bit flipping in a vector quantization (VQ) environment. This is a critical issue that has prompted us to further explore the compatibility between watermark embedding and VQ technology.

We understand your concerns as follows: In vector databases using VQ techniques such as product quantization (PQ), each subvector is typically encoded as a codeword (i.e., an index in the codebook), which corresponds to a specific centroid vector. If we directly flip the bits of these discrete indices, although the modification seems small from the perspective of Hamming distance, the large Euclidean distance between the corresponding centroids of adjacent indices will lead to significant L2 distance deviation, which may seriously affect the ANN query results. Therefore, simple bit flipping is no longer applicable in this scenario.

We agree with this view and recognize that in vector databases combining VQ technology, watermark embedding should avoid direct bit-level perturbations. We have an initial idea for this: When embedding watermarks, we can treat each dimension's codebook as a candidate set, first read the centroid vector corresponding to the current codeword, and then sort the other candidate centroid vectors in ascending order of their L2 distances from the current codeword. Among these candidates with closer distances, we can select an alternative codeword that both maps to the target watermark bit and is as close as possible to the original center vector, thereby minimizing the impact of modifications. This is a “minimum perturbation” watermark embedding strategy specifically tailored for scenarios combining VQ technology.

Additionally, we believe that since bit flipping is not applicable to VQ-encoded vectors, conducting ablation experiments in this environment is not meaningful and may lead to misunderstandings. We will explicitly highlight the limitations of the bit flipping strategy in the discussion section of the paper and will explore watermark design tailored to VQ scenarios as an important direction for future research.

Once again, thank you for raising this forward-thinking and insightful question.

Q4.

If the watermark code S is chosen according to the original cryptographic value distribution, wouldn’t it be possible to skip the modification step?

Thank you for your insightful question. We understand that you mean: if the pre-selected watermark code $S$ happens to match the distribution of values naturally extracted from the vector database, then perhaps we can skip the modification step and directly use $S$ as the “natural watermark” of the original database.

This approach does indeed have potential in certain application scenarios, particularly in data integrity verification. For example, data owners could record $S$ after its initial extraction and use it in the future to verify whether the database has been modified. However, in the copyright authentication scenario we are focusing on, this approach has limitations: the naturally extracted $S$ is typically a string of meaningless random bits lacking semantic or structural meaning, and thus cannot fulfill the functions of identifying ownership or conveying copyright information. Therefore, the modification process remains a necessary step for embedding specified watermark information.

Nevertheless, your question has inspired us to explore a potential optimization direction: introducing additional parameters to guide the original distribution toward the target watermark, thereby reducing the number of vectors requiring modification. We will further investigate this approach in future work.

Dear Reviewer ir5J:

We appreciate your insightful and valuable comments. We have carefully considered each comment and responded to them individually, and sincerely hope that our responses have adequately addressed your concerns. If so, we would be grateful if you could raise your score. If not, please let us know your further concerns, and we will continue to respond positively to your comments and improve our submission.

Weakness 1 & Limitation 1.

The allocation of space in the paper is problematic.

Thank you for your comment. We will rearrange the length of each section to ensure that the core content of each section is presented more clearly and concisely. In particular, for the sections on the “Random Selection (RS)” method and Preliminaries, we plan to streamline the content of Section 3.1 Approximate Nearest Neighbor (ANN) and Section 3.2 Hierarchical Navigable Small World (HNSW), moving more background information to the appendix. Additionally, we will explore the possibility of merging the RS and TVP schemes into a single section to free up more space in the main text for presenting more comprehensive ablation experiment results. Furthermore, we will ensure that there is no repetition between the main text and the appendix. Once again, thank you for your careful review.

Weakness 2 & Question 2.

The experimental validation is insufficient, as the experiments were conducted on only a single dataset.

We thank your valuable suggestions regarding the generalization of the experiment.

Since “transparent” vectors (i.e., vectors with relatively low query frequencies) are common in any dataset, we speculate that the TVP method has good cross-dataset generalization capabilities.

To validate this hypothesis, we conducted extended experiments on two widely used deep learning embedding datasets: arxiv-nomic-768-normalized (derived from VIBE, representing text summaries) and deep1b (a classic large-scale image vector dataset). The experimental parameters were consistent with those in the paper. We evaluated the average missed queries (AMQ) and average false queries (AFQ) caused by different watermark embedding schemes, with experimental results shown in Tables 1 and 2.

Table 1: Experimental results on the Deep1b dataset

Table 2: Experimental results on the arxiv-nomic-768-normalized dataset

It can be observed that, on both datasets, the TVP scheme achieves significantly lower average missed query counts (AMQ) and average false positive query counts (AFQ) compared to other methods. This indicates that the strategy of prioritizing “transparent” vectors for modification can also reduce query errors on other datasets, thereby validating the cross-dataset generalization capability of our method.

Weakness 2.

Moreover, the two baseline methods used for comparison were not specifically designed for vector datasets, which introduces a certain degree of unfairness.

Since watermarking in vector databases is still an emerging topic, there are currently no mature baseline methods specifically designed for this scenario. Therefore, we selected high-quality methods that are representative of the database and dataset watermarking fields in recent years as comparison objects.

These methods were originally designed for other data models and did not take into account the structural characteristics (e.g., index structure) and usage scenarios (e.g., ANN queries) of vector databases. Therefore, they may not achieve optimal performance in our experimental setup.

However, this result itself highlights a critical issue: existing watermarking methods are difficult to directly apply to vector databases, and their performance in this scenario has obvious shortcomings. This phenomenon indirectly validates the necessity and innovation of our work, namely: there is an urgent need to design specialized watermarking methods tailored to the unique structure and application scenarios of vector databases, which is precisely the core contribution of the TVP and other schemes proposed in this paper.

Question 1.

May I ask if the phrase “Presenting RS” summarized in the Contributions section is a typo? The main technical contribution of this paper should be the TVP strategy.

Thank you for your careful correction. “Presenting RS” was indeed a typo. The main technical contribution of this paper should be the TVP strategy. We will correct this in the revised version.

Dear Reviewer Ncy6:

We sincerely appreciate the insightful and constructive feedback provided by the reviewers, which has been crucial in helping us improve the quality of our work. We are particularly grateful for your recognition of the originality and potential impact of this paper. As you pointed out, this work presents the first dedicated scheme and evaluation metrics, laying the foundational framework for vector database watermarking, which may open up a new research direction.

In response to your valuable suggestions, we have made the following revisions: we have provided formal definitions of watermarks and threat models (see responses to Questions 1 and 2), and expanded the experimental evaluation to two additional large-scale datasets to further demonstrate the generality and effectiveness of our method (see response to Question 3 and the newly added Tables 1-2).

We hope these modifications adequately address your concerns. We sincerely hope you will consider increasing your score, as your support is crucial for advancing this research direction.

W1 & Q1.

Can you provide a precise definition of a watermark?

Thank you for raising this important question. Below, we provide the formal definition of watermarks in vector databases. We will incorporate this definition into the revised manuscript if deemed appropriate.

1. Watermarking Algorithms

The watermark $W \in \\{0, 1\\}^L$ is a binary string that can be embedded into digital carriers for copyright verification. $\mathcal{D} = \\{V^1, V^2, \cdots, V^n\\}$ is a vector database containing $n$ $d$-dimensional vectors. A watermarking scheme for vector database $\mathcal{D}$ consists of the following two algorithms:

• Embedding Algorithm: $\mathsf{Em}(\mathcal{D}, W, \theta_1) \rightarrow \mathcal{D}_w$
  Input: the original database $\mathcal{D}$, the watermark $W$, and the embedding parameter $\theta_1$ (which includes encryption parameters and adjustment parameters for controlling embedding impact and robustness).
  Output: the watermarked database $\mathcal{D}_w$.

• Extraction Algorithm: $\mathsf{Ex}(\mathcal{D'}, \theta_2) \rightarrow W’$
  Input: a database $\mathcal{D'}$ that may have been modified and extraction parameters $\theta_2$ (which includes decryption parameters and recovery parameters for ensuring accurate watermark extraction).
  Output: the extracted watermark $W’$.

Watermarking schemes have two major pursuits: low embedding impact and high robustness. The evaluation criteria of these two properties for vector database watermarking are presented below.

2. Embedding Impact

The embedding algorithm $\mathsf{Em}(\cdot)$ selects a set of vectors—called the carrier vector set $\mathbf{C_V} \subseteq \mathcal{D}$ —whose elements may be modified to encode the watermark. These modifications may affect ANN queries. To quantify this impact, we introduce two metrics (detailed definitions in sections 5 and 7) :

Average Missed Query (AMQ): Number of true neighbors lost after embedding.
Average False Query (AFQ): Number of incorrect neighbors newly introduced after embedding.

Lower AMQ and AFQ values indicate smaller embedding impact and higher transparency.

3. Robustness

After obtaining the watermarked database \mathcal{D}\_w\, an attacker may attempt to remove the watermark by modifying the data, thereby tampering with the database to \mathcal{D}'\, which may cause errors in watermark extraction. The robustness of the watermark can be evaluated using the bit error rate (BER):

$$\text{BER} \triangleq \frac{\sum_{i=1}^L W_i \oplus W_i'}{L}$$

The lower the BER, the higher the robustness against adversarial interference.

Our proposed TVP scheme fits within this framework: it selects carrier vectors with minimal query impact , thereby minimizing AMQ and AFQ. Simultaneously, it ensures robust extraction under common perturbations, achieving low BER.

W1 & Q2.

Define threat model and explain the meaning of "not too strong" in Section 3.3.

We appreciate your interest in the threat model and would like to clarify its definition here.

The core threat we focus on is watermark removal attacks, where attackers attempt to destroy watermarks by deleting or disturbing part of the vector, thereby evading ownership verification. The essence of such attacks is not to crack a certain encryption mechanism, and their effectiveness does not depend on the attacker's computing resources. Therefore, the statement in the threat model that “the attacks are usually not too strong” does not refer to limitations on the attacker's computational power, but rather to limitations on the intensity of the attacker's attacks.

Attackers are also users of the vector database, so while attempting to remove the watermark, they must also maintain the database's availability. If overly intense attack methods are employed, it may result in severe degradation of approximate nearest neighbor (ANN) query results, rendering the database virtually unusable.

We have demonstrated the relationship between attack intensity and query errors in Appendix D (Figure 9): when the proportion of vectors deleted or altered by attackers reaches 50%, query errors also approach 50%. This indicates that once attackers exceed a certain modification threshold, the database's functionality becomes unsustainable. Therefore, we reasonably assume that attackers will not employ overly strong attacks, forming the fundamental premise of our threat model.

To eliminate ambiguity, we will revise the description of the threat model in the paper. Specifically, we will clarify that “not too strong” refers to attack intensity restrictions, rather than computing power restrictions. Based on our experimental results, we will also suggest a rough upper bound for attack intensity—for example, modifying more than 30% of vectors may already lead to unacceptable query degradation. This revision will enhance the rigor and clarity of our threat assumptions.

W2 & Q3.

Experiments on other datasets.

We thank you for your valuable suggestions regarding the generalization of the experiments.

Since “transparent” vectors (i.e., vectors with relatively low query frequencies) are common in any dataset, we speculate that the TVP method has good cross-dataset generalization capabilities.

To validate this hypothesis, we conducted extended experiments on two widely used deep learning embedding datasets: arxiv-nomic-768-normalized (derived from VIBE, representing text summaries) and deep1b (a classic large-scale image vector dataset). The experimental parameters were consistent with those in the paper. We evaluated the average missed queries (AMQ) and average false queries (AFQ) caused by different watermark embedding schemes, with experimental results shown in Tables 1 and 2.

Table 1: Experimental results on the Deep1b dataset

Table 2: Experimental results on the arxiv-nomic-768-normalized dataset

It can be observed that, on both datasets, the TVP scheme achieves significantly lower average missed query counts (AMQ) and average false positive query counts (AFQ) compared to other methods. This indicates that the strategy of prioritizing “transparent” vectors for modification can also reduce query errors on other datasets, thereby validating the cross-dataset generalization capability of our method.

Additionally, we note that on both datasets, TabularMark performs very similarly to the random selection (RS) method, with little difference between the two in terms of AMQ and AFQ.

Weakness 2.

Is the TVP scheme applicable to other ANN indexes?

We believe that the Transparent Vector Priority (TVP) concept has good generalizability, not only applicable to HNSW but also extendable to other mainstream ANN index structures (such as IVF, NSG, LSH, etc.), simply by redefining the transparency parameters according to the specific characteristics of the index.

To verify the universality of transparent vectors, we tested the frequency distribution of vector queries across multiple index structures and used the Gini coefficient to measure their imbalance. A higher Gini coefficient indicates a more uneven query frequency distribution. The experimental results are shown in Table 3.

Table 3: Gini coefficient of vector query frequency under different ANN index structures.

As shown in the table above, the Gini coefficients for other index structures are all higher than those for HNSW, indicating that the distribution of vector query frequencies is more uneven in these structures. This confirms that the transparent vector phenomenon is widely present in various index structures and not limited to HNSW.

Therefore, the “transparent vector priority” approach can be adopted in different index structures to minimize query errors caused by watermark embedding.

This aligns with reviewer ieq6's perspective: “Although the paper states that the method is limited to HNSW, it appears to be applicable to other indexing structures as long as the method for determining the transparency parameter is modified.” In the future, we will further explore how to design appropriate transparency parameters for other index structures, thereby extending the TVP concept to a broader range of index structures.

Dear Reviewer 7c4a:

We appreciate your insightful and valuable comments. We have carefully considered each comment and responded to them individually, and sincerely hope that our responses have adequately addressed your concerns. If so, we would be grateful if you could raise your score. If not, please let us know your further concerns, and we will continue to respond positively to your comments and improve our submission.

Weakness & Question 1.

1. Is the TVP scheme applicable to other ANN indexes?

We believe that the Transparent Vector Priority (TVP) concept has good generalizability, not only applicable to HNSW but also extendable to other mainstream ANN index structures (such as IVF, NSG, LSH, etc.), simply by redefining the transparency parameters according to the specific characteristics of the index.

To verify the universality of transparent vectors, we tested the frequency distribution of vector queries across multiple index structures and used the Gini coefficient to measure their imbalance. A higher Gini coefficient indicates a more uneven query frequency distribution. The experimental results are shown in Table 1.

Table 1: Gini coefficient of vector query frequency under different ANN index structures.

As shown in the table above, the Gini coefficients for other index structures are all higher than those for HNSW, indicating that the distribution of vector query frequencies is more uneven in these structures. This confirms that the transparent vector phenomenon is widely present in various index structures and not limited to HNSW.

Therefore, the “transparent vector priority” approach can be adopted in different index structures to minimize query errors caused by watermark embedding.

This aligns with reviewer ieq6's perspective: “Although the paper states that the method is limited to HNSW, it appears to be applicable to other indexing structures as long as the method for determining the transparency parameter is modified.” In the future, we will further explore how to design appropriate transparency parameters for other index structures, thereby extending the TVP concept to a broader range of index structures.

Question 2.

2. Methods for identifying low-impact vectors and the potential of TVP concepts in different data management systems.

In any vector database, a direct method for identifying low-impact (i.e., “transparent”) vectors is to count their query frequencies. However, this method incurs excessive computational overhead in large-scale systems. To efficiently identify low-impact vectors, we need to deeply understand the internal mechanisms of various index structures. For example, in HNSW, edge nodes have lower query frequencies, while in PQ, quantization errors and cluster density may influence query probabilities.

Based on these structural characteristics, we can design more efficient heuristic strategies to estimate vector impact without enumerating queries. This is a challenging yet worthwhile direction for further research.

More broadly, the TVP approach can be viewed as a general data perturbation strategy applicable to other data management systems: prioritizing the modification of low-impact data without significantly affecting critical system performance (such as accuracy or availability). To systematically promote this strategy, we propose a general three-step framework:

1.Impact Quantification: Define system-specific impact metrics (e.g., query frequency, access heat, node centrality);
2.Low-Impact Target Identification: Combine statistical or structural heuristics to identify low-impact data units;
3.Targeted Modification: Implement minimized modifications under system constraints to reduce side effects.

We believe this framework has good general applicability and plan to explore its implementation in more data systems in future work.

Limitation 1.

3. Robustness against sophisticated attacks was not discussed in detail.

We appreciate your comments on the stability assessment. We have conducted various adaptive attack experiments targeting TVP, including subtle perturbation injection (referred to as “adaptive modification attacks” in the paper), and quantified the extraction performance using BER (bit error rate). Due to space limitations, the results of these experiments are presented in Figure 10 of Appendix D.

We will move these experimental results to the main text in the revised version based on your review comments. Once again, we sincerely appreciate the reviewers' valuable feedback.

Limitation 2.

4. Modifications to low-frequency but semantically critical vectors may introduce unforeseen minor impacts.

We appreciate your forward-thinking question, which has helped us further consider the applicability of TVP in extreme scenarios.

We fully acknowledge that in certain specific application scenarios, modifying vectors with low query frequencies that possess unique semantic meanings or carry critical information may result in minor but unforeseen impacts.

However, this issue is not unique to TVP but rather a common challenge shared by most data perturbation-based watermarking schemes. There is inherently a trade-off between security and usability.

To address this issue, this paper not only proposes the “Transparent Vector Priority” concept to minimize impact but also provides adjustable parameters for the extent of data modification to further control potential distortion.

In the future, we plan to integrate multi-dimensional information such as semantic labels and task sensitivity to further identify vectors that are “low-impact” in both the “access frequency” and “semantic importance” dimensions, thereby enhancing the controllability of TVP.