Visual Search, Embeddings, and Re-Identification

“Find images like this” can mean four different requests. The same product. The same individual. The same style. The same semantic category. Each one creates different positive and negative pairs.

Before training an embedding, define which differences should disappear and which must remain visible. That definition is not a modelling detail that can be settled later. It decides what the index is for, who ends up inside the gallery, and what happens to the person the system returns.

The same query image can demand different neighborhoods. Instance retrieval asks whether this is the same object. Semantic search asks what else belongs in the same visual or conceptual family. Re-identification asks whether this is the same entity, seen again, somewhere else. That third question carries the privacy risk listed in its column.

What the risk costs has been priced. On 3 September 2024 the Dutch Data Protection Authority fined Clearview AI €30,500,000, with orders subject to a penalty for non-compliance of up to €5.1 million. The regulator described the product without any of the vocabulary of this lesson: “Customers of Clearview can provide camera images to find out the identity of people shown in the images. For this purpose, Clearview has a database with more than 30 billion photos of people. Clearview scrapes these photos automatically from the Internet. And then converts them into a unique biometric code per face.”

Read that as an architecture and it is the ordinary re-identification pipeline of this lesson. Enrol a gallery. Embed each face into a vector. Search the vector. What separates it from the product catalogue in the first column is that the gallery was assembled by scraping, and that its entries are people who never enrolled. The decision, taken on 16 May 2024, lists the GDPR articles breached: 5(1)(a), 6(1), 9(1), 12, 14, 15 and 27. Clearview did not object, and is therefore unable to appeal against the fine.

30 billion enrolled faces is not a scale achievement in this column. It is the number of people whose biometric code sits in a gallery they were never asked about.

Large systems usually separate fast approximate search from expensive verification.

Scale here has been measured. The 2017 paper behind Faiss reported GPU k-selection running at up to 55% of theoretical peak, and nearest-neighbor search 8.5 times faster than the prior GPU state of the art. Four Maxwell Titan X cards built a ten-nearest-neighbor graph over 95 million YFCC100M images in 35 minutes. The same four cards connected a billion vectors in under twelve hours. That is the first stage only. The decision still comes later.

Step five is where the pipeline stops being a ranking problem, and it is the step that gets skipped. Detroit police arrested Robert Williams in January 2020. A face-recognition search had been run on a blurry surveillance still, and it returned, in his counsel's account, “a possible match to an expired driver's license photo of Mr. Williams”. A possible match is a candidate. It is the output of stage two — before filtering, before reranking, before anyone decides or abstains. It was not treated as one. Officers “used Mr. Williams' photo to construct a photo lineup array”, and the arrest followed.

His civil-rights suit, Williams v. City of Detroit, was filed on 13 April 2021 and terminated on 28 June 2024, when the stipulated order of voluntary dismissal with prejudice was signed. The settlement wrote step five into police policy in one sentence: “Under the agreement, police will be required to back up face recognition results with independent and reliable evidence linking a suspect to a crime before making any arrest.”

The engineering lesson is exact. A high-recall retriever is designed to return plausible candidates. It is doing its job when it returns a wrong one. Everything that turns a candidate into a decision — corroboration, threshold, abstention — lives in a later stage. When that stage is missing the pipeline does not fail loudly. It just hands the top-1 result to whoever asked.

Use a set of measures rather than one global similarity threshold. Each measure asks a different question. The open-set false accept rate is the one most easily left unmeasured, until somebody outside the team measures it for you.

In July 2018 that is what happened to a live commercial system. Jacob Snow, of the ACLU of Northern California, built the test himself, and the method is small enough to state in full: “we built a face database and search tool using 25,000 publicly available arrest photos”, then searched that gallery with public photos of all 535 members of Congress using Amazon Rekognition. “We used the default match settings that Amazon sets for Rekognition” — a confidence threshold of 80%. The search returned 28 false matches. They were not evenly distributed: “Nearly 40 percent of Rekognition's false matches in our test were of people of color, even though they make up only 20 percent of Congress”.

Amazon did not dispute the count. On the AWS News Blog on 27 July 2018, Dr. Matt Wood restated it: “They found 28 incorrect matches out of 535, using an 80% confidence level; this is a 5% misidentification (sometimes called ‘false positive’) rate and a 95% accuracy rate.” His objection was to the dial rather than the arithmetic. The 80% default, he wrote, is “far too low” for public-safety use. “We recommend 99% for use cases where highly accurate face similarity matches are important”. At that setting “our misidentification rate dropped to zero despite the fact that we are comparing against a larger corpus of faces (30x larger than the ACLU test)” — a collection of 850,000 faces.

Hold the two readings side by side. Same model, same gallery construction, one query set of 535. 28 false accepts at one threshold, zero reported at another, on a gallery more than thirty times the size. The false accept rate is not a property of the embedding that evaluation discovers. It is a number the product sets. And the value it ships with — the default — is the one the world will measure it at.

Move from how the data is defined to how the threshold behaves. Two of these steps have external answers already written for them, and it is cheaper to read those than to rediscover them.

Step one, defining forbidden matches, is not only a product judgement. The AI Act prohibits “the placing on the market, the putting into service for this specific purpose, or the use of AI systems that create or expand facial recognition databases through the untargeted scraping of facial images from the internet or CCTV footage;” That is Article 5(1)(e) of Regulation (EU) 2024/1689. The Parliament adopted it on 13 March 2024 by 523 votes to 46 with 49 abstentions. It was published in the Official Journal on 12 July 2024. The prohibitions apply from 2 February 2025, and breach carries fines of up to €35,000,000 or, for an undertaking, up to 7% of total worldwide annual turnover, whichever is higher. Recital 43 gives the reason: “because that practice adds to the feeling of mass surveillance and can lead to gross violations of fundamental rights, including the right to privacy”. Some galleries are forbidden before a single metric has been chosen.

Steps two and four are where slicing earns its place, and the largest published slice study says what to expect. NIST published it in December 2019, as Part 3 of the Face Recognition Vendor Test. The scale of the evaluation is stated in one sentence: “Together these datasets allowed us to process a total of 18.27 million images of 8.49 million people through 189 mostly commercial algorithms from 99 developers.” The finding sits in the executive summary, under the heading “WHAT WE FOUND”: “Across demographics, false positives rates often vary by factors of 10 to beyond 100 times.” False negatives, by contrast, varied by factors usually below 3.

Two things follow for the audit. First, a single aggregate false accept rate can hide a hundredfold difference between the groups it averages over. That is why step two builds slices and step four fills them with identities absent from the gallery. Second, the spread is a property of particular algorithms rather than of the task. A 2023 GAO report, citing the same NIST work, records that “For a small number of the one-to-many algorithms, differences in false positives across demographic groups were undetectable.” It is measurable, it varies by vendor, and it is therefore something an audit can select on.

A marketplace wants visually similar listings without collapsing distinct sizes, brands, or counterfeit cues. Write the specification the way the records above would have needed it. Name the forbidden matches. Write the threshold as a number. Decide in advance what happens below it.