NNG-Based Secure Approximate k-Nearest Neighbor Query for Large Language Models

Heng Zhou, Yuchao Wang (), Yi Qiao and Jin Huang ()
Additional contact information
Heng Zhou: School of Computer Science and Technology, Xidian University, Xi’an 710071, China
Yuchao Wang: School of Computer Science and Technology, Xidian University, Xi’an 710071, China
Yi Qiao: School of Computer Science and Technology, Xidian University, Xi’an 710071, China
Jin Huang: Beijing Academy of Blockchain and Edge Computing, Beijing 100080, China

Mathematics, 2025, vol. 13, issue 13, 1-27

Abstract: Large language models (LLMs) have driven transformative progress in artificial intelligence, yet critical challenges persist in data management and privacy protection during model deployment and training. The approximate nearest neighbor (ANN) search, a core operation in LLMs, faces inherent trade-offs between efficiency and security when implemented through conventional locality-sensitive hashing (LSH)-based secure ANN (SANN) methods, which often compromise either query accuracy due to false positives. To address these limitations, this paper proposes a novel secure ANN scheme based on nearest neighbor graph (NNG-SANN), which is designed to ensure the security of approximate k-nearest neighbor queries for vector data commonly used in LLMs. Specifically, a secure indexing structure and subset partitioning method are proposed based on LSH and NNG. The approach utilizes neighborhood information stored in the NNG to supplement subset data, significantly reducing the impact of false positive points generated by LSH on query results, thereby effectively improving query accuracy. To ensure data privacy, we incorporate a symmetric encryption algorithm that encrypts the data subsets obtained through greedy partitioning before storing them on the server, providing robust security guarantees. Furthermore, we construct a secure index table that enables complete candidate set retrieval through a single query, ensuring our solution completes the search process in one interaction while minimizing communication costs. Comprehensive experiments conducted on two datasets of different scales demonstrate that our proposed method outperforms existing state-of-the-art algorithms in terms of both query accuracy and security, effectively meeting the precision and security requirements for nearest neighbor queries in LLMs.

Keywords: large language models; secure nearest neighbor query; nearest neighbor graph; locality-sensitive hashing (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/13/13/2199/pdf (application/pdf)
https://www.mdpi.com/2227-7390/13/13/2199/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:13:y:2025:i:13:p:2199-:d:1695471

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().