Skip to content

Nearest-Neighbor Audit

Quality audit — instantiates Structure-Preserving Embedding Design

Samples an embedding's neighborhoods and checks, with human judgement, whether each item's nearest host neighbors are genuinely related in the source — catching false neighbors and missing ones.

A Nearest-Neighbor Audit inspects an existing embedding by pulling each sampled item's k nearest host neighbors and asking whether they are genuinely related in the source — and, conversely, whether things that should be neighbors actually are. It is an evaluation, not a construction: it does not build a neighborhood-preserving map, it judges one already built, usually with a human in the loop reviewing whether the retrieved neighbors make sense. Its defining question, distinct from the collision probe's, is not whether distinct items stayed apart but whether proximity means what it claims to — whether the host's "nearby" faithfully reports the source's "related."

Example

A company embeds its help-desk articles so a search box can return "related articles" by nearest-neighbor lookup. The audit samples a few hundred articles and, for each, lays out its top-k neighbors for a reviewer: for a "reset your password" article, are the neighbors other authentication topics (good), or unrelated pages that merely share boilerplate like "contact support" (a false neighbor)? It also checks the reverse — a known pair of near-duplicate articles that ought to be mutual neighbors but sit far apart (a missing neighbor). Findings go into a human-readable report: false-neighbor rate by topic, notable misses, worked examples of bad neighborhoods — the artifact a team uses to decide whether the embedding is good enough to ship or needs rework. The audit changes nothing in the map; it tells you, in terms a person can act on, where the map's notion of "near" diverges from real relatedness.

How it works

Sample items and pull each one's k nearest neighbors under the host metric. Judge relatedness — against known-related anchor pairs and human review — scoring false neighbors (near but unrelated) and missing neighbors (related but far) as separate failures. Then report in human terms: a readable account of where and how proximity misleads, broken out by region of the space. It assesses a finished embedding's neighborhoods; it does not design them.

Tuning parameters

  • k — how many neighbors per item are inspected. Small k audits only the tightest matches; large k surveys the wider neighborhood but costs more review.
  • Sampling strategy — uniform versus stratified toward high-traffic or high-risk regions; targets effort where bad neighbors hurt most.
  • Relatedness oracle — human judgement, labeled anchor pairs, or held-out ground-truth links; richer oracles cost more but sharpen the verdict.
  • Error emphasis — weight false neighbors (precision) versus missing neighbors (recall); which matters depends on the downstream use.
  • Reporting grain — one global score versus a per-topic, per-region breakdown that shows where the neighborhood structure is untrustworthy.

When it helps, and when it misleads

Its strength is that it connects an embedding's geometry back to meaning, catching the failures that look fine numerically but read as nonsense to a user — and it delivers the verdict in language a non-specialist owner can act on. Its failure modes: it rests on the reviewer's or oracle's notion of "related," which is subjective and can itself be wrong; sampling can miss bad neighborhoods in regions it never draws from; and in very high-dimensional spaces neighbors are inherently less meaningful, so some noise is unavoidable.[1] The classic misuse is auditing only cherry-picked examples that flatter the embedding, or reading a good false-neighbor rate as proof the whole space is sound. The discipline that guards against this is to sample honestly — including the ugly regions — fix the relatedness standard before looking, and report where the map is weak rather than an average that hides it.

How it implements the components

Nearest-Neighbor Audit fills the neighbor-quality and human-facing components — the ones an evaluation of a finished embedding produces:

  • metric_or_neighborhood_choice — the audit operates on the host metric and neighbor definition, exercising exactly the "near" relation the embedding ships with, and can compare candidate metrics by the neighbor quality each yields.
  • anchor_correspondence_set — it uses known source-related pairs as anchors: reference correspondences that should appear as neighbors, against which false and missing neighbors are scored.
  • human_explanation_layer — its output is a human-readable account of where proximity misleads, the artifact a person uses to judge and improve the embedding.

It does not detect identity collisions (distortion_and_loss_register — Embedding Collision Probe) or verify operation and relation laws (relation_and_operation_preservation_tests — Invariant Preservation Test Suite), and it does not build the map (injection_rule — Graph Embedding); it audits the neighborhoods a finished embedding already has.

Notes

An audit reveals where proximity is untrustworthy but does not fix it — remediation (retraining, a different metric, more dimensions) belongs to the map-building mechanisms. And because the verdict rests on a human judgement of "related," two audits can disagree; fix the relatedness standard up front so the finding is about the embedding, not about who reviewed it.

References

[1] Neighbor quality is often summarized as precision@k and recall@k — of an item's k nearest neighbors, how many are genuinely related; and of its genuinely related items, how many appear among the neighbors. Framing the audit this way keeps "false neighbor" and "missing neighbor" as separate, separately-fixable failures. ↩