Retrieval with Multiple Query Vectors through Anomalous Pattern Detection

Technical Summary: Retrieval with Multiple Query Vectors through Anomalous Pattern Detection

Problem Formulation
Classical vector retrieval systems typically operate under a single-query paradigm, where a single embedding vector is used to retrieve the most similar vectors from a database based on proximity metrics (e.g., cosine similarity, Euclidean distance). However, complex reasoning and retrieval tasks often involve multiple query vectors that capture different aspects of a user's intent (e.g., a paragraph where each sentence represents a distinct constraint or feature). Existing approaches to multi-query retrieval often aggregate these vectors into a single embedding via heuristics or treat them independently, thereby discarding valuable inter-query relationships. Furthermore, standard distance-based metrics may fail to capture complex, nonlinear, and context-dependent relationships inherent in high-dimensional embeddings, particularly those from Large Language Models (LLMs).

This work addresses the challenge of retrieving relevant database vectors given a set of multiple query vectors $Q = \{q_1, q_2, \dots, q_M\}$, without requiring the number of vectors to be retrieved to be specified a priori.

Methodology
The authors propose a retrieval framework grounded in anomalous pattern detection. The core hypothesis is that the set of query vectors shares a specific "anomalous pattern"—a subset of vector dimensions where the values jointly deviate significantly from the distribution observed in the database $D$. The most relevant database vectors are those that exhibit this same joint anomalous pattern.

The approach extends deep scanning algorithms (McFowland, Speakman, and Neill 2013; Cintas et al. 2021, 2022) to the retrieval setting through a two-step process:

1. Identify Anomalous Dimensions: Given the query set $Q$, the algorithm identifies a subset of vector dimensions $O^*_S$ that best capture the distinguishing characteristics of the queries.

   • The method assumes the anomalous pattern corresponds to values that are particularly low (in the lower $\alpha$-tail) compared to the database distribution.
   • It standardizes dimensions using z-scores ($z_{ml} = \frac{q_{ml} - \mu_l}{\sigma_l}$), where $\mu_l$ and $\sigma_l$ are the mean and standard deviation of dimension $l$ across the database $D$.
   • A non-parametric scan statistic (specifically the Berk–Jones statistic) is used as a scoring function $F(S)$ to maximize the anomaly score over subsets of dimensions.

2. Retrieve Database Vectors: Using the identified dimensions $O^*_S$, the algorithm scans the database $D$ to retrieve the subset of vectors $R^*_S$ that exhibit the same joint anomalous pattern in those specific dimensions.

Unlike traditional methods, this approach does not rely on fixed distance thresholds or a pre-specified retrieval count $K$. Instead, the size of the retrieved set is dynamically determined by the anomaly scoring process.

Experimental Setup and Results
The authors evaluated the method on four diverse datasets:

• Image: MNIST and Fashion-MNIST (flattened and projected to 30 dimensions via UMAP).
• Text: Persona (LLM embeddings of sentences agreeing with specific personas) and Ailuminate (LLM embeddings of prompts regarding hazard categories).
• Tabular: A medical dataset regarding breast cancer (31 numerical features).

The method was compared against two adapted KDTree baselines:

• KDTree pre: Averages all query vectors into a single vector before retrieval.
• KDTree post: Retrieves vectors for each query independently and merges the results.

Key Findings:

• Impact of Query Set Size: Across most datasets, increasing the number of query vectors ($M$) from 1 to 8 led to significant improvements in both precision and recall. Gains diminished when increasing $M$ beyond 8.
• Performance by Dataset:
  • Persona (LLM Text): The proposed method achieved near-perfect precision and recall (close to 1.00) for $M=64$, significantly outperforming both KDTree variants (which reached ~0.70–0.80).
  • Tabular Data: The method achieved higher precision (1.00) than baselines (0.90) but lower recall (~0.77 vs ~0.90).
  • Fashion-MNIST: The method showed higher recall but lower precision compared to baselines.
  • MNIST: No significant difference was observed between the proposed method and baselines, though absolute performance was high for all.
• Retrieval Size: The proposed method dynamically determines the retrieval set size. In ablation studies, when KDTree was forced to retrieve a similar number of vectors as the proposed method, the proposed method still maintained a slight edge in precision and recall for the Tabular and Persona datasets.

Significance and Claims
The paper positions this work as a novel step toward robust multi-query retrieval. The authors claim that defining relevance through an anomaly scoring function rather than traditional distance-based measures allows for the capture of complex, nonlinear relationships that fixed metrics miss.

The study modestly frames its contributions as a "first step" in this direction. The authors acknowledge limitations, including the use of fixed classes of interest per dataset and reliance on KDTree as a baseline rather than more sophisticated vector search methods (e.g., optimized vector similarity search). They note that the method performed best on LLM text embeddings compared to reduced-dimensional image embeddings and tabular data, suggesting a need for future investigation into the generalizability across different data types and embedding architectures. The work does not claim to solve all multi-query retrieval challenges but demonstrates that leveraging anomalous patterns in query sets can yield superior retrieval performance in specific contexts, particularly with LLM embeddings.