VRSD: Rethinking Similarity and Diversity for Retrieval in Large Language Models

• URL: http://arxiv.org/abs/2407.04573v2
• Date: Thu, 14 Nov 2024 18:01:10 GMT
• Title: VRSD: Rethinking Similarity and Diversity for Retrieval in Large Language Models
• Authors: Hang Gao, Yongfeng Zhang,
• Abstract summary: Vector retrieval algorithms are essential for semantic queries within the rapidly evolving landscape of Large Language Models. This paper introduces a novel approach that characterizes both constraints through the relationship between the sum vector and the query vector. We present the algorithm Vectors Retrieval with Similarity and Diversity, VRSD, which features a clear optimization objective and eliminates the need for preset parameters.
• Score: 43.53494041932615
• License:
• Abstract: Vector retrieval algorithms are essential for semantic queries within the rapidly evolving landscape of Large Language Models (LLMs). The ability to retrieve vectors that satisfy both similarity and diversity criteria substantially enhances the performance of LLMs. Although Maximal Marginal Relevance (MMR) is widely employed in retrieval scenarios requiring relevance and diversity, variations in the parameter $\lambda$ lead to fluctuations that complicate the optimization trajectory in vector spaces. This obscures the direction of improvement and highlights the lack of a robust theoretical analysis regarding similarity and diversity constraints in retrieval processes. To address these challenges, this paper introduces a novel approach that characterizes both constraints through the relationship between the sum vector and the query vector. The proximity of these vectors ensures the similarity constraint, while requiring individual vectors within the sum vector to diverge in their alignment with the query vector satisfies the diversity constraint. We first formulate a new combinatorial optimization problem, selecting k vectors from a candidate set such that their sum vector maximally aligns with the query vector, and demonstrate that this problem is NP-complete. This result underscores the inherent difficulty of simultaneously achieving similarity and diversity in vector retrieval, thereby providing a theoretical foundation for future research. Subsequently, we present the heuristic algorithm Vectors Retrieval with Similarity and Diversity, VRSD, which features a clear optimization objective and eliminates the need for preset parameters. VRSD also achieves a modest reduction in time complexity compared to MMR. Empirical validation confirms that VRSD significantly outperforms MMR across various datasets.

Related papers

• MUVERA: Multi-Vector Retrieval via Fixed Dimensional Encodings [15.275864151890511]
  We introduce MUVERA (MUlti-VEctor Retrieval Algorithm), a retrieval mechanism which reduces multi-vector search to single-vector similarity search. MUVERA achieves consistently good end-to-end recall and latency across a diverse set of the BEIR retrieval datasets.
  arXiv  Detail & Related papers  (2024-05-29T20:40:20Z)
• A unified consensus-based parallel ADMM algorithm for high-dimensional regression with combined regularizations [3.280169909938912]
  parallel alternating multipliers (ADMM) is widely recognized for its effectiveness in handling large-scale distributed datasets. The proposed algorithms serve to demonstrate the reliability, stability, and scalability of a financial example.
  arXiv  Detail & Related papers  (2023-11-21T03:30:38Z)
• RGM: A Robust Generalizable Matching Model [49.60975442871967]
  We propose a deep model for sparse and dense matching, termed RGM (Robust Generalist Matching) To narrow the gap between synthetic training samples and real-world scenarios, we build a new, large-scale dataset with sparse correspondence ground truth. We are able to mix up various dense and sparse matching datasets, significantly improving the training diversity.
  arXiv  Detail & Related papers  (2023-10-18T07:30:08Z)
• Federated Conditional Stochastic Optimization [110.513884892319]
  Conditional optimization has found in a wide range of machine learning tasks, such as in-variant learning tasks, AUPRC, andAML. This paper proposes algorithms for distributed federated learning.
  arXiv  Detail & Related papers  (2023-10-04T01:47:37Z)
• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  Clustered multi-task compressive sensing is a hierarchical model that solves multiple compressive sensing tasks. The existing inference algorithm for this model is computationally expensive and does not scale well in high dimensions. We propose a new algorithm that substantially accelerates model inference by avoiding the need to explicitly compute these covariance matrices.
  arXiv  Detail & Related papers  (2023-09-30T15:57:14Z)
• Multivariate Representation Learning for Information Retrieval [31.31440742912932]
  We propose a new representation learning framework for dense retrieval. Instead of learning a vector for each query and document, our framework learns a multivariate distribution. We show that it can be seamlessly integrated into the existing approximate nearest neighbor algorithms.
  arXiv  Detail & Related papers  (2023-04-27T20:30:46Z)
• Factorization of Multi-Agent Sampling-Based Motion Planning [72.42734061131569]
  Modern robotics often involves multiple embodied agents operating within a shared environment. Standard sampling-based algorithms can be used to search for solutions in the robots' joint space. We integrate the concept of factorization into sampling-based algorithms, which requires only minimal modifications to existing methods. We present a general implementation of a factorized SBA, derive an analytical gain in terms of sample complexity for PRM*, and showcase empirical results for RRG.
  arXiv  Detail & Related papers  (2023-04-01T15:50:18Z)
• Complexity Measures for Multi-objective Symbolic Regression [2.4087148947930634]
  Multi-objective symbolic regression has the advantage that while the accuracy of the learned models is maximized, the complexity is automatically adapted. We study which complexity measures are most appropriately used in symbolic regression when performing multi- objective optimization with NSGA-II.
  arXiv  Detail & Related papers  (2021-09-01T08:22:41Z)
• Accurate and fast matrix factorization for low-rank learning [4.435094091999926]
  We tackle two important challenges related to the accurate partial singular value decomposition (SVD) and numerical rank estimation of a huge matrix. We use the concepts of Krylov subspaces such as the Golub-Kahan bidiagonalization process as well as Ritz vectors to achieve these goals.
  arXiv  Detail & Related papers  (2021-04-21T22:35:02Z)
• High-Dimensional Quadratic Discriminant Analysis under Spiked Covariance Model [101.74172837046382]
  We propose a novel quadratic classification technique, the parameters of which are chosen such that the fisher-discriminant ratio is maximized. Numerical simulations show that the proposed classifier not only outperforms the classical R-QDA for both synthetic and real data but also requires lower computational complexity.
  arXiv  Detail & Related papers  (2020-06-25T12:00:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.