A sufficient condition for correct retrieval

ProofIntermediate⏱ 30 minRAGretrievalthresholdcorpus sizedimension

Theory: Embedding Geometry and Similarity →

Problem

Derive the sufficient condition $\alpha>\sqrt{2\log(N/\delta)/d}$ for top-1 retrieval, and determine the embedding dimension needed to retrieve correctly from $N = 10^9$ documents at $\alpha = 0.2$ with $95\%$ confidence. Comment on the honesty of this estimate.

Write a complete argument. Every inequality you use should be one you could state precisely.

Solution

Opening this before you have a real attempt on paper is the fastest way to feel like you understand something you cannot reproduce.

Related problems

All problems

Problem	Field	Type	Difficulty	Time
Three similarities agree on the unit sphere	RAG	Proof	Foundation	15 min
Johnson–Lindenstrauss dimension arithmetic	High-Dim Probability	Numerical	Beginner	15 min
Simulate distance contrast run	Classical ML	Coding	Beginner	30 min
Measure anisotropy in an embedding space run	RAG	Coding	Intermediate	1 hour
The density of the cosine between random directions	RAG	Proof	Advanced	1 hour