Just brute force your embeddings

Posted by JohnBerryman 3 days ago

Counter34Comment14OpenOriginal

Comments

Comment by emschwartz 4 days ago

This works especially well if your embedding model was trained to perform well with quantized embeddings. Binary + hamming distance = incredibly fast.

This post is from 2024 but I wrote about using this technique in https://emschwartz.me/binary-vector-embeddings-are-so-cool/

Comment by dimatura 3 hours ago

I remember similar observations for an earlier use case in computer vision, loop closure and place recognition for visual SLAM algorithms. In this case the goal was to find a needle (or needles) in a big haystack of visual descriptors (in some sense, proto-embeddings for small image patches or in some cases, whole images). Several approaches used hierarchical data structures for the NN search such as k-mean trees. But linear search - especially with binary descriptors, also became popular as a fast and simple alternative.

Comment by softwaredoug 4 days ago

Hamming w/xor+popcount is the only thing I can make numpy do faster than float32 dot products :)

int8s, float16s are all fairly slow. I suppose it’s because BLAS does float32/64 very fast.

Comment by emschwartz 4 days ago

Yeah that makes sense. I took the optimizations of my hamming distance library to a bit of an insane level. I wrote this about the first round https://emschwartz.me/unnecessary-optimization-in-rust-hammi... The second round brought the best result down to 0.8 nanoseconds per comparison on x86 with SIMD (for a batch of 1000).

Separately, I’m a huge fan of your writing about search! It’s been very helpful while I’ve been building https://scour.ing.

Comment by softwaredoug 4 days ago

Thank you! <3

Comment by Ellis_dev 3 days ago

The 1M-document numbers are a great reality check. I’d happily start with the NumPy version and only reach for a vector DB once it actually hurts.

Comment by fmajid 2 days ago

Similarly, COST, configuration that outperforms a single thread:

https://www.usenix.org/system/files/conference/hotos15/hotos...

Comment by sputknick 2 days ago

I don't understand what he means by "brute force your embedding". Does this mean "don't calculate your embedding ahead of time, just generate them as you need them?

Comment by iamflimflam1 2 days ago

Looking at the linked article.

He is suggesting that you don’t need a vector database.

Comment by behnamoh 2 days ago

I 'member this is what Karpathy used in his restaurant menu app, and John Carmack said this is the way. I also agree that embeddings are overkill for the majority of tasks.

Comment by blt 2 days ago

Nothing new under the sun, the same thing has been happening since the "big data" keyword became popular in the 2010s.

Comment by johnfn 2 days ago

384 is a tad small. How does it perform on 1k/2k/4k..?

Comment by firasd 2 days ago

Yes! I'm working on an MCP server called Liveclip (not released yet) and we just store embeddings as text in SQLite.. it works over ~40MB of text, 1450 SCOTUS opinions

start=$(date +%s); curl -s -X POST "https://[urlredacted].workers.dev/mcp" -H "Content-Type: application/json" -H "Accept: application/json, text/event-stream" -d '{"jsonrpc":"2.0","id":1,"method":"tools/call","params":{"name":"table_search_similar","arguments":{"key":"scotus_2010s","col":"M","query":"endangered fish"}}}' 2>&1 | grep '^data:' | sed 's/^data: //' | jq; end=$(date +%s); echo "elapsed: $((end-start))s" { "result": { "content": [], "structuredContent": { "has_more": true, "headers": { "A": "author_name", "B": "category", "C": "per_curiam", "D": "case_name", "E": "date_filed", "F": "federal_cite_one", "G": "absolute_url", "H": "year_filed", "I": "scdb_id", "J": "scdb_decision_direction", "K": "scdb_votes_majority", "L": "scdb_votes_minority", "M": "text" }, "offset": 0, "ok": true, "rows": [ { "A": "Justice Thomas", "B": "dissenting", "C": "False", "D": "Florida v. Georgia", "E": "2018-06-27", "F": "", "G": "https://www.courtlistener.com/opinion/4511641/florida-v-geor...", "H": "2018", "I": "", "J": "", "K": "", "L": "", "M": "Florida asks this Court to cap Georgia’s use of water in\nthe Apalachicola-Chattahoochee-Flint River Basin (Basin).\nFlorida claims that such a cap would allow additional\nwater to flow into the Apalachicola River and Bay, which\nwould benefit Florida by alleviating certain ecological\nharms. To prevail under our precedents, Florida must\npresent clear and convincing evidence that its proposed\ncap will benefit Florida more than it harms Georgia. See\nColorado v. New Mexico, 459 U.S. 176, 187 (1982) (Colo-\nrado I ). The Special Master applied this balance-of-harms\nstandard and, after presiding over a 1-month trial involv­\ning 40 witnesses and more than 2,000 exhibits, found that\nFlorida had not met its burden. Because that finding\nis well supported by the evidence, I would have over-\nruled Florida’s objections to the Special Master’s Report\n(Report) and denied Florida’s request for relief. I respectfully\ndissent.\n I\n The Court’s recitation of the facts focuses o", "_match": true, "_row": 1189 },

elapsed: 12s (on my laptop)

Comment by aitchnyu 4 days ago

Umm, is pgvector relevant to this usecase?