You’re in a Staff ML Engineer interview at Pinterest and the interviewer asks:
“Your LSH index is missing 30% of true neighbors. You doubled the number of hash tables and recall barely moved. What’s actually happening?”
Don’t say: “I’d add more tables and tune the number of hash functions.” You just described the knob, not the failure. Interview over.
Here’s what’s really going on.
LSH doesn’t retrieve neighbors. It bets on collisions.
Recall per query is roughly 1 − (1 − p₁ᵏ)ᴸ, where p₁ is the collision probability for a true neighbor, k is the hash functions concatenated per table, and L is the table count.
Notice what L can and can’t do:
L is a linear lever. Double it → double the memory, double the candidate set, double the query cost. You buy recall with latency.
k is an exponential lever. If k is too high, p₁ᵏ collapses toward zero, and you’d need exponentially many tables to compensate. Adding L to fix a bad k is arithmetic against geometry. You lose.
But the deeper failure is the one nobody mentions:
