1 Introduction↩︎

Large language models (LLMs) are increasingly deployed in various applications with extended usage in decision-support pipelines [1]. Due to limited memory and information constraints in the training data end date, they are often complemented with retrieval-augmented generation (RAG) systems [2], [3], where the model is expected to produce responses faithful to the evidence. A core obstacle to reliability is hallucination: the model may generate statements that are unsupported by, or contradict, the given context [4].

Detection approaches emphasize that hallucinations in RAG can be exposed by measuring the mismatch between the context and the generation using internal model signals [5]. For example, probabilistic distances between prompt and response hidden-state distributions (e.g., MMD with dependence-aware resampling) provide a training-free score that increases under hallucination, and can be made comparable across variable-length sequences via p-values computed from an estimated null distribution [6]. Another line of work analyzes attention-map structure [7] and reports that certain attention heads exhibit robust hallucination signatures across datasets, which can be summarized by a topological divergence on attention-induced graphs [8].

While these methods account for diverse patterns encountered by an LLM, they mostly ignore the internal structure for most tasks. One typically has a reference distribution (e.g., embeddings of retrieved evidence or a trusted prompt) and a query distribution (embeddings of the generated response). Crucially, the operational goal is often asymmetric: we would like to tightly control false alarms when the response is well grounded in the reference, while remaining sensitive to deviations that, e.g., indicate hallucination. Asymmetry also arises when the length of the prompt and the generated response can be significantly different, making most approaches inefficient in the presence of a large context. This asymmetry is not fully captured by classical symmetric two-sample tests, which treat both samples interchangeably.

In this paper, we formalize hallucination detection and the artificial text detection problem as an asymmetric two-sample testing problem and develop a nearest-neighbor (NN) graph test tailored to this regime. Nearest-neighbor methods are attractive in high dimensions because they avoid density estimation and rely only on local geometry. The classical nonparametric NN coincidence test of Henze counts how often a point and its NN belong to the same sample across both groups, and is symmetric by design with provable strong statistical properties [9]. We propose and analyze a one-sided variant that counts NN coincidences only within the reference sample. This yields a statistic that (i) aligns with the reference-vs-query structure of hallucination detection, (ii) admits an exact finite-sample conditional mean and variance under the permutation null (given the pooled locations), and (iii) retains asymptotic normality and consistency properties analogous to the symmetric case.

Our work adopts a reference-sided counting rule, focusing only on within-reference NN coincidences. This asymmetric construction better matches operational settings such as hallucination detection, where one sample plays the role of an anchor distribution, and yields a statistic with tractable conditional moments and analogous large-sample behavior. Our theoretical analysis closely follows the framework of [9], while adapting the statistic, null moments, asymptotic calibration, and consistency argument to the asymmetric one-sided setting. We further demonstrate how such asymmetric tests can be applied to real-world LLM generation problems using hidden-state representations.

Our contributions are as follows:

• An asymmetric two-sample statistic ASK-NN. We introduce an asymmetric two-sample statistic ASK-NN based on within-reference coincidences in the k-NN graph, motivated by reference-query settings where one sample provides an anchor distribution.

• Established theoretical properties for ASK-NN. For ASK-NN statistic, we derive exact conditional mean and variance under the permutation null and obtain an asymptotically normal calibration. Our theoretical contributions continue with characterization of the limiting separation functional under fixed alternatives and show that it is minimized if and only if the two distributions coincide, implying consistency of the resulting test.

• Competitive empirical performance of ASK-NN. We evaluate the method on synthetic Gaussian benchmarks, artificial-text detection, and LLM hallucination detection, showing competitive performance against MMD, Sinkhorn, Hotelling’s \(T^2\), and symmetric k-NN baselines.

2 Related works↩︎

2.0.0.1 Graph-based and nearest-neighbor tests.

Graph-based tests form a class of nonparametric two-sample tests. They rely only on the geometric structure of the pooled sample, rather than on a parametric model for the underlying distributions. In particular, they construct a graph on pooled observations, for example using nearest-neighbor graphs or minimum spanning trees (MSTs), and measure how frequently edges connect points from the same sample. Among the well-known examples are the Friedman–Rafsky test, based on the MST [10], as well as nearest-neighbor tests, such as the Henze nearest-neighbor coincidence test [9]. The latter counts the number of nearest-neighbor pairs within the samples symmetrically across both samples and establishes asymptotic normality under the null hypothesis and consistency under alternative hypotheses.

2.0.0.2 Two-sample testing and kernel methods.

The two-sample problem has a long history, with modern nonparametric methods including kernel-based tests and graph-based tests. Maximum Mean Discrepancy (MMD) is a widely used kernel two-sample statistic with strong theoretical guarantees and practical performance [11]. For dependent data, wild-bootstrap variants provide valid calibration for degenerate kernel tests [12]. Connectivity between two samples is also explored in  [10], [13], where the authors consider the number of edges in the minimum spanning tree connecting nodes from different samples. Similar ideas appear in works [14], but from a topological perspective, while with proved statistical properties [15]. These methods are directly relevant to token-sequence embeddings in LLMs, where strong local dependence violates i.i.d.assumptions.

2.0.0.3 Hallucination detection via internal signals.

A growing body of work detects hallucinations without external knowledge by extracting model-internal uncertainty or consistency cues, e.g., self-consistency over multiple generations [16], entropy-based confidence [17], and probes over hidden states [18]. In RAG, a particularly effective principle is to directly quantify the relationship between the provided context and the generated response [19]. One approach measures probabilistic distances between prompt and response hidden-state distributions and uses dependence-aware resampling (e.g., wild bootstrap) to compute calibrated p-values, yielding length-normalized hallucination scores [6]. In parallel, TOHA analyzes graphs induced by attention matrices and uses an asymmetric topological divergence between prompt and response subgraphs, reporting that a small subset of attention heads yields stable hallucination signatures across datasets and models [8].

2.0.0.4 Artificial-text detection.

Machine-generated text (MGT) detection aims to distinguish human-written texts from outputs of large language models. This task has become increasingly challenging because modern LLMs generate fluent, high-quality text, making the distributional differences between human and generated writing subtle.

Existing methods include metric-based detectors based on language-model statistics such as likelihood, entropy, rank or perturbation-based scores [20], [21], model-based classifiers trained to separate human and generated examples [22], and distributional approaches that explicitly view detection through the lens of statistical two-sample problem. In particular, recent work uses MMD-based criteria not only to measure discrepancies between human-written and machine-generated texts, but also to optimize detectors that are sensitive to such distributional differences [23].

We use this domain as a source of real-world data, where human-written and LLM-generated texts form two closely related distributions, providing a useful benchmark for evaluating the sensitivity of our two-sample statistic.

3 Methods↩︎

3.1 Hypothesis testing problem↩︎

Let \(X_1, \ldots, X_{n_1}, Y_1, \ldots, Y_{n_2}\) be independent \(\mathbb{R}^d\)-valued random vectors with the dimension \(d \ge 1\). Throughout the paper, the \(X\)-sample is treated as the reference sample and the \(Y\)-sample as the query or potentially shifted sample. The distribution of \(X_i\) has an unknown probability density function \(f(x)\), and \(Y_i\) has an unknown probability density function \(g(x)\). We consider the two-sample testing problem \(H_0: f \equiv g\) against \(H_1: f \not\equiv g\).

3.2 Nearest-neighbour based statistic↩︎

Let \[Z_i = \begin{cases} X_i, & 1 \le i \le n_1, \\ Y_{i - n_1}, & n_1 + 1 \le i \le n, \end{cases}\] where \(n = n_1 + n_2\). Then, for the pooled sample \(\{Z_i\}\), we define \(N_r(Z_i)\) to be the \(r\)-th nearest neighbor of \(Z_i\) in the full sample, and \(A(Z_i) = I(1 \le i \le n_1)\) is the indicator of the first group of points.

The statistic ASK-NN to be studied is: \[\label{eq:T95n95def} T_n = \sum_{i = 1}^{n} \sum_{r=1}^k A(Z_i) A(N_r(Z_i)).\tag{1}\] Thus, \(T_n\) counts the number of reference points whose \(k\) nearest neighbors in the pooled sample are also reference points, as it equals \(\sum_{i = 1}^{n_1} \sum_{r=1}^k A(N_r(Z_i))\). Our goal is to examine the properties of \(T_{n}\) and compare them with those of the version proposed by Henze \(T^{\mathrm{full}}_n = \sum_{i = 1}^{n} \sum_{r=1}^k A(Z_i) A(N_r(Z_i)) + (1 - A(Z_i))(1 - A(N_r(Z_i)))\). We will show that \(T_n\) has properties that are largely similar to those of the original, while requiring a smaller amount of computation, as evident from Table 1 for \(n_1 \ll n\).

3.3 Distribution under \(H_0\)↩︎

If \(H_0\) holds, we can represent the random sequence \(Z_1, \ldots, Z_n\) using the permutation distribution, similarly to [9]. \(Z_1, \ldots, Z_n\) are i.i.d random \(d\)-dimensional vectors. Additional random variables \(U_{n1}, \ldots, U_{nn}\) have distribution: \[\begin{gather} \mathbb{P}(U_{nj} = u_j; 1 \le j \le n) = \\ = \begin{cases} \binom{n}{n_1}^{-1}, & \text{if} \sum_{i=1}^{n} I(u_i = 1) = n_1, \\ 0, & \text{otherwise}. \end{cases}, \end{gather}\] where \(u_j \in \{1, 2\}\) are all possible values of \(U_{nj}\). These variables represent the sample type of \(Z_j\): \(X\) or \(Y\)-type correspondingly. For \(1 \le i \neq j \le n, 1 \le r \le k\) we introduce events \[A_{ij}^{(r)} = [Z_j = N_r(Z_i)],\] \[B_j = [U_{nj} = 1].\]

Here we study only one sample type (\(U_{nj} = 1\)), therefore, the test becomes asymmetric.

Under \(H_0\), \(T_n\) defined in 1 has the same distribution as \[\tilde{T}_n = \sum_{i,j = 1}^{n} \sum_{r=1}^k I\left(B_i\right) I\left(B_j\right) I\left(A_{ij}^{(r)}\right).\] Given \(Z_i = z_i\) we denote: \[a_{ij}^{(r)} = a_{ij}^{(r)}(z_1, \ldots, z_n) = I(A_{ij}^{(r)} | Z_1 = z_1, \ldots, Z_n = z_n).\] \[a_{ij}^+ = \sum_{r=1}^k a_{ij}^{(r)} \quad (a_{ij}^+ \in \{0, 1\})\] All \(a_{ij}^+\) together form an adjacency matrix of the k-nearest-neighbour graph on points \(z_1, \ldots, z_n\). \[L_n = \sum_{i, j = 1}^{n} a_{ij}^+ I(B_i) I(B_j).\]

For convenience, let \(d_j^{(k)} = \sum_{i=1}^{n}a_{ij}^+\), \(c_n^{(k)} = \frac{1}{nk}\sum_{j = 1}^{n}\left(d_j - k\right)^2\), \(v_n^{(k)} = \frac{1}{nk}\sum_{i, j = 1}^{n}a_{ij}^+a_{ji}^+\) (same notation is used in [9]). Now we can formulate the one-sided analog of Proposition 2.1 from [9]:

Now we derive a new asymptotic distribution under \(H_0\).

Then, using the fact above (or using Theorem 4.1.1 from [24] with notations given in the proof of Prop. 1), we obtain the next result:

The result above delivers the distribution of \(T_n\) under \(H_0\). It allows us to derive the p-values for \(T_n\) given its asymptotical normality and analytical expressions for its mean and variance.

3.4 Consistency↩︎

Now we turn our attention to a one-sided analog of Theorem 4.1 from [9] that describes what happens if \(f \ne g\).

Now we prove a special case of inequality for this asymmetric separation measure \(\tilde{D}\):

After that the statistical test is defined similarly (see Theorem 4.4 from [9]), aside from different formulas for \(m(n_1, n_2)\) and \(U_{n_1, n_2}\): \[m(n_1, n_2) = \frac{n_1(n_1 - 1)}{n - 1},\] \[\begin{gather} U_{n_1, n_2} = k\frac{n_1(n_1-1)n_2}{(n-1)(n-2)(n-3)} \times \\ \times \left((n_1 - 2)C_n + (n_2-1)\left(1+V_n-\frac{2k}{n-1}\right)\right) \le \\ \le k\frac{n_1(n_1-1)n_2}{(n-1)(n-2)(n-3)} \times \\ \times \left((n_1 - 2)(\mathcal{C} + 1)^2 + 2(n_2 - 1)\right) = O_{\mathcal{P}_{f,g}}(n), \end{gather}\]

where \(C_n\), \(V_n\), \(\mathcal{C}\) are defined in (3.1), (3.2), (2.5) from [9], respectively. Using this we can derive (4.8) from [9]. The last inequality in the proof of Theorem 4.4 from [9] now follows from Theorem 2, (4.8) from [9], Proposition 3 and the fact that, as \(n \rightarrow \infty, n_1/n \rightarrow \tau\), \[\lim\left(n^{-1}m(n_1, n_2)\right) = \tau^2.\]

The proposed test is defined similarly as in Remark 5.1 from [9]:

4 Experiments↩︎

4.1 Baselines and evaluation protocol↩︎

4.1.0.1 Baselines.

We compare the proposed test ASK-NN against representative baselines from several families of two-sample tests: Hotelling’s \(T^2\) test (t-test) as a classical parametric mean-based test; the original Henze’s 1-NN graph symmetry test (Symmetric) [9]; the unbiased Maximum Mean Discrepancy with RBF-kernel, label shuffling and median bandwidth heuristic (\(\mathrm{MMD}_{u}B\)) as a kernel-based two-sample test [25]; and Sinkhorn Divergency (SD) as the entropy-regularized optimal transport version [26]. For the SD baseline, we use a small entropic regularization coefficient to stabilize the computation and compute the statistic efficiently via Sinkhorn iterations, while preserving a close approximation to the unregularized OT distance. For the \(\mathrm{MMD}_{u}B\), SD and t-test baselines, p-values are obtained by the same label-shuffling procedure [27].

4.1.0.2 Monte Carlo evaluation.

For each configuration, we estimate power as the empirical rejection rate over \(R\) independent Monte Carlo repetitions at the significance level \(\alpha = 0.05\). Error bars indicate normal-approximation \(95\%\) Monte Carlo confidence intervals, \[\hat{p} \pm 1.96 \sqrt{\frac{\hat{p}(1-\hat{p})}{R}},\] where \(\hat{p}\) is the empirical rejection rate and \(R\) is the number of repetitions.

4.2 Computational complexity↩︎

4.2.0.1 Implementation details.

To study practical computational scaling, we benchmark all methods on synthetic Gaussian inputs. For each configuration, we generate two samples of size \(N\) in dimension \(d\) and measure wall-clock runtime of the statistic computational only, excluding data generation. We consider dimensions \(d \in \{128, 1024\}\) and vary the total sample size from \(512\) to \(32768\) on a powers-of-two grid. Experiments are performed on an NVIDIA A100 GPU after 10 warm-up iterations. Runtime is reported as the median over repeated 20 executions.

4.2.0.2 Results.

Figure 1 presents the observed runtime scaling of the proposed ASK-NN statistic and competing baseline statistics. ASK-NN exhibits substantially slower runtime growth than the kernel-based \(MMD_{u}\) statistic and the SD baseline. Moreover, ASK-NN remains applicable at larger sample sizes than these baselines, which become memory-limited earlier due to their higher memory requirements.

Compared with the symmetric nearest-neighbor statistic, ASK-NN shows similar scaling behavior, with slightly lower runtime than this baseline. Hotelling’s \(T^2\) test exhibits nearly constant runtime in the explored regime, likely because its computation is dominated by fixed GPU overheads rather than arithmetic cost.

Overall, these experiments suggest that nearest-neighbor-based two-sample statistics offer better practical scalability than kernel-based alternatives, while ASK-NN preserves this advantage and remains computationally competitive with the symmetric nearest-neighbor baseline.

4.3 Synthetic data↩︎

4.3.0.1 Gaussian benchmarks.

Similar to [11], we evaluate all tests on two high-dimensional Gaussian two-sample problems. In the mean-shift setting, we sample \(X \sim \mathcal{N}(0, I_d)\) and \(Y \sim \mathcal{N}(\mu_\delta, I_d)\), where \(\mu_\delta = \delta \mathbf{1}_d / \sqrt{d}\). This choice keeps the Euclidean norm of the mean difference fixed, \(\|\mu_\delta\|_2 = \delta\), independently of the dimension \(d\). In the scale-shift setting, we sample \(X \sim \mathcal{N}(0, I_d)\) and \(Y \sim \mathcal{N}(0, \sigma^2 I_d)\), where \(\sigma\) controls the variance difference. We evaluate dimensions ranging from \(2\) to \(2500\). For the mean-shift experiments, we use 20 logarithmically spaced values of \(\delta\) in \([0.05, 50]\). For the scale-shift experiments, we use 20 logarithmically spaced values of \(\sigma\) in \([1, 10]\). For each configuration, we estimate power as the fraction of repetitions in which the null hypothesis is rejected at level \(\alpha = 0.05\). In all experiments, we draw \(n_1=n_2=250\) samples from each distribution.

4.3.0.2 Results.

Figure 2 demonstrates empirical power under the mean-shift and variance-shift alternatives.
In the mean-shift setting, MMD and Hotelling’s \(T^2\) test achieve the highest rejection rates. This is consistent with the structure of the alternative: Hotelling’s \(T^2\) test directly targets differences in means, while MMD with a characteristic RBF-kernel is sensitive to the induced difference between the two Gaussian distributions. The proposed ASK-NN does not outperform the considered baselines in this setting, but attains nontrivial empirical power, confirming that the statistic remains sensitive to mean-shift alternatives.

In the variance-shift setting, the ranking changes substantially: the proposed asymmetric test achieves the strongest performance among all considered methods and remains highly powerful across the full range of dimensions. MMD is the closest competitor and also performs robustly, whereas the Sinkhorn divergence baseline is substantially weaker in higher dimensions. Henze’s original symmetric 1-NN graph test loses power almost completely, highlighting the advantage of the proposed asymmetric construction for detecting variance changes in high dimensions.

4.4 Real problem of Artificial text detection↩︎

4.4.0.1 Experimental setup.

We further evaluate the proposed test on artificial-text detection datasets. We use the RAID dataset [28] and consider the subset corresponding to GPT-4 generations in the abstracts domain. For each sample size, we draw two independent samples of texts: one from the human-written subset and one from the GPT-4-generated subset. Texts are embedded using the multilingual-e5-large sentence encoder [29], and the resulting embedding samples are compared using the considered two-sample tests. This setup evaluates whether the tests can detect the distributional difference between human-written and machine-generated texts in a semantic embedding space.

Since the original asymptotic calibration of the proposed statistic is not sufficiently well-calibrated in this setting, we also evaluate a label-shuffling variant of our test, denoted Asymmetric (LS), where \(p\)-values are obtained by permuting labels in the pooled sample.

4.4.0.2 Results.

Figure 3 reports Type II and Type I errors across sample sizes. The results show that human-written and GPT-4-generated texts are well separated in the multilingual-e5-large embedding space, with most criteria achieving low Type II error at moderate sample sizes.

The proposed asymmetric statistic is also sensitive to this distributional difference and reaches low Type II error as the sample size increases. However, the original version requires careful calibration in this setting, as its Type I error may deviate from the nominal significance level on real text embeddings. To address this issue, we additionally evaluate a label-shuffling calibration of our approach (ASK-NN (LS)). As the results show, this variant keeps Type I error close to the nominal level across the considered sample sizes, while retaining strong power.

The comparison between the original and label-shuffling variants indicates that the main challenge in this setting is calibration rather than lack of signal: our proposed statistic captures the human-vs-generated difference, while resampling provides reliable Type I error control.

4.5 Real problem of LLM Hallucination Detection↩︎

4.5.0.1 Experimental setup.

We evaluate the proposed test in an applied hallucination detection task following the experimental protocol of [6]. The task is motivated by RAG, in which hallucinated responses are expected to exhibit weaker or structurally different relationships with the provided context. Motivated by this, each prompt-response pair is represented by the token-level hidden states of an LLM, and hallucination detection is formulated as a two-sample problem comparing the hidden-state distributions of prompt and response tokens. For a prompt-response pair \(S = (P, R)\), token-level LLM hidden states define two empirical samples, \(X_P=\{h_i^P\}_{i=1}^{m}\) and \(Y_R = \{h_j^R\}_{j=1}^{n}\), corresponding to prompt and response tokens. We compute the proposed asymmetric graph-based statistic for the prompt and response hidden-state samples (\(X_P, Y_R\)) and use it as a hallucination score.

We evaluate our approach and the baselines on a subset of the benchmark considered by [6]: long-form QA dataset MS MARCO and summarization CNN/DM + Recent News from RAGTruth [30], and conversational QA benchmark CoQA [31], using two open-source LLMs: Mistral-7B-Instruct-v0.1 and LLaMA-2-7B-chat.

4.5.0.2 Results.

Table 2 shows ROC-AUC scores for hallucination detection on three datasets and two LLMs. The proposed asymmetric statistic achieves the best or second-best result in five out of six settings. For Mistral-7B, it matches the best performance on MS MARCO and CNN/DM + Recent News, achieving ROC-AUC scores of \(0.72\) and \(0.62\), respectively, and remains close to the strongest method on CoQA. For LLaMA-2-7B, the proposed method obtains the best results on MS MARCO and CoQA, and is second-best on CNN/DM + Recent News.

Compared to the MMD-based criterion, our approach improves performance on most datasets and model backbones, suggesting that the proposed statistic captures prompt-response mismatch in hidden-state space more effectively in this application. The gains are particularly clear for LLaMA-2-7B, where the proposed method outperforms MMD on all three datasets. Overall, these results indicate that our approach transfers well to a practical hallucination detection scenario, beyond the controlled synthetic alternatives considered above.

5 Conclusion↩︎

We introduced an asymmetric multivariate two-sample test based on directed 1-nearest-neighbor coincidences. Unlike symmetric graph-based tests, the proposed statistic treats one sample as a reference distribution and measures how its local neighborhood structure changes when a query sample is introduced. We derived exact finite-sample conditional moments under the permutation null, established asymptotic normality, and proved consistency under fixed alternatives.

Experiments on synthetic benchmarks, artificial-text detection, and LLM hallucination detection show that the proposed statistic is not only theoretically tractable and meaningful on controlled Gaussian alternatives, but also remains competitive on real embedding-based tasks.

Several directions remain open. First, the asymptotic calibration can be inaccurate for real hidden-state embeddings, where dependence, anisotropy, and high dimensionality are substantial; permutation or block-resampling calibration may provide more robust alternatives. Second, extending the theory to dependent token-level samples and high-dimensional regimes would make the method better aligned with LLM applications and improve hallucination detection in practical RAG systems.

References↩︎

---

1. Code is available at: https://anonymous.4open.science/r/asymmetrical-multivariate-two-sample-test-21F0/↩︎