DEV Community: Rishabh Gupta

The Algorithm Behind Every Vector Database Search — And Why It Matters for AI Engineers

Rishabh Gupta — Tue, 30 Jun 2026 14:45:00 +0000

When I built AskS1.com — a tool that lets you ask questions about the SpaceX S-1 filing and get cited answers — I spent a lot of time thinking about retrieval. How do you find the right chunks of text from a 395-page document, fast enough that someone will actually wait for the answer?

Rishabh Gupta

Jun 10

How I Built a RAG System on the SpaceX S-1 in One Weekend

#aisystemdesign

7 min read

The answer turned out to be an algorithm I'd been using without fully understanding: HNSW — Hierarchical Navigable Small World graphs. It's the engine inside Qdrant, Weaviate, Pinecone, Milvus and most modern vector databases. If you're building anything with RAG, embeddings, or semantic search, HNSW is quietly doing the hardest part for you.

This post is what I wish I'd read before building AskS1.

What's a Vector Database, and Why Do You Need One?

Before HNSW makes sense, you need the problem it solves.

Modern AI applications — RAG systems, semantic search, recommendation engines — work by converting text (or images, or audio) into vectors: arrays of floating-point numbers that represent meaning. Two pieces of text that mean similar things will have vectors that are numerically close to each other. "Starlink revenue in 2025" and "Connectivity segment financial results" will be neighbors in vector space even though they share no words.

A vector database stores these vectors and answers one question efficiently: given a query vector, which stored vectors are most similar? That's the retrieval step in RAG — embed the user's question, find the most similar chunks, feed them to the language model.

The naive approach is obvious: compare the query vector against every stored vector, rank by similarity, return the top K. This works fine at 1,000 vectors. At 1,000,000 vectors, it's too slow. At 100,000,000 vectors (the scale of production recommendation systems), it's completely infeasible.

This is the problem HNSW was designed to solve.

The Algorithm: How HNSW Actually Works

The original HNSW paper was published in 2016 by Malkov and Yashunin. The core idea is elegant enough to explain in three paragraphs.

The amber path shows HNSW search: enter at Layer 2 (A→B), drop to Layer 1 (B→E), drop to Layer 0, find the nearest neighbor (★) to the query vector (Q).

The structure. HNSW builds a multi-layer graph over your stored vectors. Each vector is a node. Nodes are connected to their nearest neighbors, but the connections are separated by scale across layers:

Layer 2 (top) — sparse, long-range connections — coarse "zoom out"
Layer 1 — medium-range connections
Layer 0 (base) — dense, short-range connections — full precision

Only a small fraction of vectors appear at the top layers. Every vector appears at Layer 0.

The search. When a query arrives, search starts at the top layer. The algorithm greedily hops toward the query — at each step, it moves to whichever neighbor is closest to the query vector. When it can't get any closer (local minimum), it drops to the next layer and repeats, starting from where it stopped. By the time it reaches Layer 0, it's already in the right neighborhood and finds the true nearest neighbors quickly.

Why this is fast. Without the hierarchy, you'd need to scan many nodes to find the right neighborhood. The hierarchy acts like a map zoom: start at country level to find the right region, zoom to city level to find the right neighborhood, then zoom to street level to find the exact address. Each zoom-in starts from a much better position than random.

The result: logarithmic complexity — O(log n) search instead of O(n). At 1 million vectors, that's roughly 20 hops instead of 1,000,000 comparisons.

The Name Unpacked

"Hierarchical Navigable Small World" is a mouthful. Each word earns its place:

Hierarchical — the multi-layer structure that gives it logarithmic complexity. Without this, you get NSW (the predecessor algorithm), which is only polylogarithmic — still too slow at scale.

Navigable — greedy routing through the graph converges to the right answer. Not all graphs have this property. The specific way HNSW constructs edges ensures that following the "closest neighbor at each step" rule actually leads you somewhere useful.

Small World — any two nodes in the graph can be reached from each other in a small number of hops, regardless of graph size. This is the same "six degrees of separation" phenomenon studied in social network theory — Milgram's famous experiment. HNSW deliberately engineers this property into its graph structure.

Why Previous Approaches Failed

It helps to understand what HNSW replaced:

Brute-force / flat search — compare the query against every vector. O(n) — too slow at scale. Still used for tiny collections where speed doesn't matter.

kd-trees — the classic algorithm for nearest neighbor search in low-dimensional spaces. Works well up to maybe 20 dimensions. Above that, the "curse of dimensionality" kicks in: the tree structure degrades and you end up scanning most of the tree anyway. Modern embedding models produce 384 to 1536-dimensional vectors — kd-trees are useless here.

Locality-sensitive hashing (LSH) — hash similar vectors to the same bucket, search within the bucket. Works, but requires tuning many parameters and tends to need high memory for good recall.

NSW (non-hierarchical) — the direct predecessor to HNSW. Good idea, but polylogarithmic complexity: as the dataset grows, each search requires evaluating an increasingly large number of nodes. HNSW's hierarchy adds a second log factor that brings it to true logarithmic scaling.

The Parameters You'll Actually Configure

When you use a vector database like Qdrant, you don't implement HNSW — you configure it. Three parameters matter:

M — the number of connections per node per layer. Higher M means better recall (more neighbors to navigate through) at the cost of more memory and slower index build time. Qdrant's default is 16, which works well for most embedding dimensions.

efConstruction — the candidate list size during index building. Higher values build a better quality index at the cost of build time. Default is 100.

ef — the candidate list size during search. This is the one you actually tune at query time. Higher ef means HNSW explores more candidates before returning results — better recall, slightly slower. If your RAG system is missing relevant chunks, increasing ef (or the equivalent limit parameter in your vector database client) is the first thing to try.

In AskS1, the retrieve() function passes limit=15 to Qdrant's query_points(). HNSW finds 15 candidates, then a re-ranking step applies a penalty to summary pages and returns the top 5. Increasing the limit to 20-25 would give HNSW more candidates to work with — potentially improving the quality of retrieved chunks at marginal latency cost for an 871-chunk collection.

One More Idea Worth Understanding: The Neighbor Selection Heuristic

The paper introduces a heuristic for selecting which nodes to connect during index construction that's worth understanding if you're working with clustered data.

The naive approach connects each new node to its M closest existing neighbors. This works most of the time, but fails on highly clustered data: if all your nearest neighbors are in the same cluster, you have no long-range connections to other clusters. The retriever gets stuck.

HNSW's heuristic (Figure 2 in the paper, also shown below) deliberately selects diverse neighbors — it prefers candidates that extend connectivity in new directions, even if they're not the absolute closest. The result is a graph that maintains global connectivity across clusters.

This matters for RAG specifically. In a filing like the SpaceX S-1, chunks about "Starlink revenue" form a dense cluster. So do chunks about "governance" and "risk factors." Without cross-cluster connectivity, a query about "Elon Musk's voting power and its revenue implications" might only retrieve governance chunks, missing the revenue context entirely. HNSW's heuristic makes cross-cluster retrieval work.

Reading the Paper

The HNSW paper is accessible without a deep algorithms background if you read it selectively. The sections worth your time:

Abstract — the entire algorithm in 15 lines
Section 1 — why naive search fails; no math required
Section 3 — the zoom-out/zoom-in intuition; the best explanatory section
Figure 1 — the layered structure, visually
Figure 2 — the neighbor selection heuristic
Algorithm 5 — the actual search procedure, only 8 lines
Section 4.1 — what M, mL, and efConstruction actually control

Skip Section 2 (prior work survey), Algorithms 1-4 (implementation detail), and the experiments section (the finding is just "HNSW wins"). The math-heavy parts aren't necessary for understanding how to use it.

Total reading time at this depth: 45-60 minutes.

Why This Matters for AI Engineers

Vector databases are now a standard component in AI engineering — RAG pipelines, semantic search, recommendation systems, and anything using embeddings routes through one. Understanding HNSW doesn't mean you'll implement it (you won't — Qdrant, Weaviate, and others handle that). But it tells you:

Why limit in your vector database query is actually a recall parameter, not just a count
Why retrieval quality degrades on clustered data and what to do about it
Why building a 10-million-vector index takes a long time but search is fast
What tradeoffs you're making when you adjust M and efConstruction

The algorithm was published in 2016. It's been powering production systems for almost a decade. If you're building with vector databases in 2026, it's worth spending an hour understanding what's actually happening when you call query_points().

Claude Haiku vs Local Models: The Real Tradeoff

Rishabh Gupta — Tue, 16 Jun 2026 07:33:46 +0000

27.6 seconds vs 2.8 seconds. That gap isn't a benchmark footnote — it's the difference between a product people use and one they abandon.

I was building AskS1.com, a RAG system for querying the SpaceX S-1. The generation step — taking retrieved chunks and producing a cited answer — needed to be fast enough that someone would actually wait for it. I benchmarked five models to find out which one earned that spot: Claude Haiku, and four 7-14B local models running on a Mac Mini M4 via Ollama.

The overall numbers looked like a rounding error. The category breakdown told a different story.

How I Evaluated

15 questions across three categories, same retrieved context for every model.

Factual recall — can the model extract a specific number correctly?

"What is SpaceX's total revenue for 2025?"
"How many Starlink subscribers does SpaceX have as of Q1 2026?"
"What is SpaceX's total debt as of Q1 2026?"

Multi-step reasoning — does the model connect information across sections and form a judgment?

"Why is SpaceX's AI segment consuming 62-76% of capex but generating 
only 17% of revenue? Is this a concern?"
"Why can't Elon Musk be removed as CEO without his own approval?"
"How does SpaceX's vertical integration give it an advantage?"

Structured output — can the model follow formatting instructions precisely?

"Summarize SpaceX's three business segments in a markdown table 
with columns: Segment, Revenue, Operating Income, Key Product."
"List the top 5 risk factors in order of severity."
"Summarize Elon Musk's compensation structure in exactly 4 bullets."

One factual question was a deliberate curveball — "What RL algorithm does DeepSeek use?" — unrelated to SpaceX entirely, testing whether models would admit "I don't know" or hallucinate an answer just because the context was about a tech company.

Scoring

Two methods for two question types.

Factual recall — scored against ground-truth figures pulled directly from the filing. Exact numbers, keyword matching — does the answer contain the correct revenue figure, subscriber count, debt number.

Reasoning and structured output — scored 1-5 by Claude Sonnet as an LLM judge, evaluating coherence, accuracy, and instruction-following. These don't have single correct answers — "is this sustainable?" requires judgment, not pattern matching.

The Results

Model	Overall	Factual	Reasoning	Structured	Latency
claude-haiku	4.7	5.0	4.8	4.4	2.8s
phi4:14b	4.5	4.4	4.5	4.6	27.6s
qwen2.5:14b	4.4	4.4	4.2	4.6	26.9s
mistral:7b	4.4	4.4	4.0	4.6	9.0s
deepseek-r1:14b	4.3	4.4	3.8	4.6	102.8s

A 0.2-4.4 point spread on a 5-point scale looks like noise. It isn't — it's three different stories stacked on top of each other.

Where the Gap Actually Lives

Structured output: local models win. Every local model scored 4.6, ahead of Haiku's 4.4. Following "exactly 4 bullets" or "markdown table with these columns" doesn't require deep reasoning, and the local models were if anything slightly more literal about compliance.

Reasoning: this is where the real gap is. Haiku scored 4.8. deepseek-r1:14b scored 3.8 — a full point lower, despite taking 102.8 seconds per question, 37x Haiku's latency. These questions asked models to connect numbers across sections and form a judgment — "ARPU is declining but revenue is growing — is this sustainable, and why?" This is where size and training quality actually show up. Interestingly, phi4:14b (4.5) and qwen2.5:14b (4.2) — both 14B — outperformed deepseek-r1:14b (3.8) despite being the same size class. Reasoning quality isn't just a parameter-count story.

Factual recall: one question did almost all the damage. Four of five factual questions, every model scored a perfect 5.0. The entire gap traces to one question — "How many Starlink subscribers does SpaceX have as of Q1 2026?" All four local models answered "10,300 thousand (or 10.3 million)" — numerically correct, but the "10,300 thousand" phrasing tripped the keyword scorer. Haiku said "10.3 million" cleanly and scored full marks. Not a knowledge gap. A units-formatting quirk that cost 2.3 points on one question out of fifteen.

So the honest summary: for structured tasks, local models are competitive or better. For reasoning, there's a real gap, and it scales with model quality more than raw size. For factual recall, the "gap" was mostly an artifact of how I scored one question.

(And for the DeepSeek curveball — Haiku, phi4, qwen2.5, and deepseek-r1 all correctly said "I don't know." mistral:7b confidently described "DeepSeak, a spacecraft navigation autonomous docking system developed by SpaceX" — a system that does not exist. A small reminder that "I don't know" is sometimes the only correct answer, and not every model knows that.)

The Cost Angle

Estimating cost per query for both:

Claude Haiku — roughly 2,900 input tokens (context + system prompt + question) and ~400 output tokens per query comes to about $0.004 per query.

Mac Mini M4 electricity — 27.6 seconds at ~25W draw works out to about $0.00006 per query — roughly 65x cheaper than the API call, in pure electricity terms.

Neither number matters at the scale of a side project. The Mac Mini is "free" because I already own it. The API cost is "free" because it's a fraction of a cent. Cost only becomes the deciding factor at high query volume — thousands of requests per day, where $0.004 × 10,000 = $40/day starts to add up against hardware you already paid for once.

So When Do Local Models Make Sense?

Not "Haiku wins, always." Local models make sense when:

Privacy matters — documents that can't leave your machine
Offline access is required — no network dependency
Volume is high enough that per-query API cost compounds meaningfully
Latency tolerance is high — batch processing, overnight jobs, anything where 27 seconds vs 2.8 seconds doesn't matter to a human waiting

For AskS1.com — a public tool where someone types a question and waits — 2.8 seconds is the only viable answer. But for the private Google Drive knowledge base I built on the same Mac Mini, the calculus flips entirely: nothing leaves my machine, nobody's waiting in real time, and the documents are mine. Local models there aren't a compromise — they're the right tool.

Full results

How I Built a RAG System on the SpaceX S-1 in One Weekend

Rishabh Gupta — Mon, 08 Jun 2026 00:18:32 +0000

SpaceX filed a 389-page S-1 on May 20, 2026. I read the news, opened the SEC EDGAR filing, and immediately hit the same wall everyone hits — 389 pages of dense legal and financial disclosure, no search, no way to ask a direct question and get a cited answer.

The summaries floating around were useful for headlines. Useless for anything specific. "SpaceX is profitable" tells you nothing about which segments are driving it, what the margin trajectory looks like, or what governance risks the company is flagging. For that, you need the actual text, with a page reference you can verify.

So I built AskS1.com. Here's what that actually involved — including the parts that didn't work.

Why RAG, Not Just Upload to Claude

The obvious approach is uploading the PDF to Claude or ChatGPT and asking questions. It works, mostly. But it has three problems.

First, the SpaceX S-1 was filed after most model training cutoffs. For specific figures the model has no training data — it either says "I don't know" or hallucinates a plausible number. I benchmarked this: asking Claude directly about SpaceX's 2025 revenue without context produces a confident wrong answer.

Second, a 395-page document (after amendments) strains context windows. Models start losing details from the middle of the document when they're trying to hold everything at once. Important disclosures on pages 80-200 get deprioritized for content near the beginning and end.

Third, citations are vague. "According to the filing" isn't useful when you're trying to verify a specific governance claim before an IPO.

RAG solves all three. You precompute the embeddings once, retrieve only the relevant chunks at query time, and the model sees focused context rather than 395 pages of noise.

Why Not Fine-Tune

Before settling on RAG, I considered fine-tuning a smaller model on the filing content. The results from my own benchmarking — fine-tuning Mistral-7B on 25 SpaceX Q&A pairs — ruled it out quickly.

Fine-tuning on a document teaches the model to reproduce facts it has seen during training. Ask it a question that maps closely to a training example and it answers well. Ask it anything slightly outside that distribution — a follow-up question, a cross-reference between sections, a question phrased differently — and it hallucinates confidently. The model has memorized, not understood.

RAG sidesteps this entirely. The model never sees the filing during training. At query time, relevant chunks are retrieved and injected as context. The model reads those chunks and answers from them. It's closer to open-book exam than memorization — and for a 395-page legal document with dense cross-references, open-book is the right approach.

Fine-tuning also has a practical problem for this use case: when SpaceX files an amendment — which they did twice within two weeks — the fine-tuned model is immediately stale. Re-ingesting a RAG pipeline takes under 5 minutes. Re-fine-tuning a model takes hours and compute budget.

The Architecture

SpaceX S-1 PDF (395 pages → 871 chunks)
    ↓ pdfplumber — extract text page by page
    ↓ sliding window chunker — 400 words, 100 overlap
    ↓ all-MiniLM-L6-v2 — embed chunks → 384-dim vectors
    ↓ Qdrant Cloud — store 871 vectors + page metadata

User question
    ↓ all-MiniLM-L6-v2 — embed query
    ↓ cosine similarity → top 15 candidates
    ↓ re-rank — penalize summary pages
    ↓ Claude Haiku — generate cited answer
    ↓ ±8 page range citation

Four components. Each does one thing.

Two separate models — intentional design. all-MiniLM-L6-v2 handles embeddings only. Claude Haiku handles generation only. Embedding models are optimized for semantic similarity — small, fast, deterministic, 384 dimensions. Generation models are optimized for instruction following and text quality. Using the same model for both would mean either a slow embedding step or a weak generation step. Keeping them separate is standard RAG practice and worth being explicit about.

Why Qdrant. Qdrant's free tier is generous enough for a single filing (871 chunks, 384 dimensions). The HNSW index makes similarity search fast at this scale. Local Qdrant works for development — Qdrant Cloud for production without managing infrastructure.

395 pages → 871 chunks. Average 2.2 chunks per page after the sliding window. Total vectors stored: 871 × 384 dimensions. Each chunk stores text, page number, and end page in the payload — retrieved alongside the vector for citation generation.

The Chunking Decision

400 words per chunk with 100-word overlap. Why these numbers?

Smaller chunks (200 words) lose context for multi-sentence financial disclosures. A revenue figure appears on one line; the explanation — segment breakdown, YoY comparison, key drivers — spans the next five sentences. Split at 200 words, you retrieve the number without the context.

Larger chunks (800 words) reduce retrieval precision. You retrieve more text than you need and dilute the relevant signal with adjacent content.

The 100-word overlap ensures no fact gets cut at a chunk boundary without appearing in an adjacent chunk. Any sentence that spans two chunks will be fully retrievable from either side.

Why Claude Haiku for Generation

I benchmarked five models on 15 SpaceX S-1 questions — factual recall, multi-step reasoning, and structured output — with RAG context injected each time:

Model	Overall	Latency
Claude Haiku	4.7/5	2.8s
phi4:14b (local)	4.5/5	27.6s
qwen2.5:14b (local)	4.4/5	26.9s
mistral:7b (local)	4.4/5	9.0s
deepseek-r1:14b (local)	4.3/5	102.8s

The quality gap between Haiku and local 14B models is 0.2 points. The latency gap is 10x. For a web product where users are waiting for an answer, Haiku wins decisively.

One interesting finding: structured output scores were nearly identical across all models (4.4-4.6). The differentiation came entirely from factual accuracy and reasoning — where Haiku's training data and instruction following consistently outperformed locally-run open models.

The Challenges

The summary pages problem.

The executive summary (pages 1-24) mentions every major topic at a high level — consistently scoring highest in semantic similarity for almost any query, even when detailed content existed 100+ pages later.

Fix: retrieve 15 candidates, then apply a 0.15 penalty to chunks from pages under 25. Most substantive disclosures live deeper in the filing. Penalizing the summary section keeps retrieval focused on the narrative sections where specific claims and governance details actually appear.

The page citation problem.

The most challenging aspect was generating accurate page citations. The core issue: the SEC EDGAR filing only exists as HTML, which I converted to PDF using Chrome's print function. Chrome's HTML reflow during rendering means the text layer in the PDF doesn't always align with what you see visually.

What I tried first — standalone number regex

The first attempt looked for standalone numbers at the bottom of each page. Failed immediately — financial tables, footnote numbers, and reference counts appear throughout the page content including near the bottom. Too many false positives to be reliable.

What I tried second — Chrome's N/313 footer regex

Chrome adds N/313 page indicators in the footer during printing. I wrote a regex to extract it.

In theory this pattern is unique and can't appear elsewhere in the filing. In practice it was unreliable — the footer text wasn't always cleanly captured by pdfplumber's text extraction, so the regex frequently missed pages.

What I tried third — WeasyPrint HTML→PDF conversion

WeasyPrint converts HTML to properly paginated PDF where the text layer and visual layer are aligned by design. This would have eliminated the problem entirely. Failed on macOS — requires GTK libraries (libgobject, pango, cairo) that don't install cleanly on macOS without significant dependency management. Abandoned after an hour of dependency hell.

What I tried fourth — paged.js

A JavaScript library specifically designed for CSS-based HTML pagination. More macOS-friendly than WeasyPrint. The 11.8MB HTML filing with separately hosted image assets made this impractical — the converted PDF would be missing all images and the pagination would differ from the original rendering anyway.

What actually works — position-based extraction

The winning approach uses pdfplumber's coordinate system directly. Instead of parsing text, it looks for a standalone digit in the bottom 10% of the page, centered between 20–80% of the page width.

This reliably catches the printed page number without depending on text extraction of footer lines. Citations display a ±8 page range to account for any remaining rendering uncertainties.

Demo card caching

The /api/demo route is intentionally cached by Next.js. The three demo questions are fixed, the underlying data doesn't change between ingestion runs, and the answers are expensive to generate — hitting both Qdrant and the Claude API on every page load would add latency for no benefit. Cached results mean the landing page loads fast every time.

The filing is a moving target.

SpaceX filed two amendments after the original S-1 — S-1/A #1 on June 1 and S-1/A #2 on June 3 — with updated financials and the IPO price range ($135/share). The RAG pipeline re-ingests any filing version in under 5 minutes. When Anthropic and OpenAI file their S-1s later this year, the same pipeline handles them.

Conversation Memory

The app maintains conversation history across turns. Follow-up questions work without re-explaining context — "which segment is most profitable?" after asking about revenue breakdown uses the prior exchange. History is passed as the Anthropic messages array, capped at the last 10 exchanges to keep context window usage bounded.

Stack

Frontend: Next.js 14 on Railway. Migrated from a Streamlit prototype — easier to keep the same platform than migrate.
Vector storage: Qdrant Cloud. Free tier covers a single filing comfortably. HNSW index, no infrastructure to manage.
Generation: Anthropic API (Claude Haiku). Chosen on latency and quality benchmarks above.
Embeddings: @xenova/transformers running all-MiniLM-L6-v2 in Node.js. Runs entirely locally — no embedding API calls at query time, which reduces latency and cost per query. Ingestion is separated from retrieval; embeddings are computed once and pushed to Qdrant Cloud.
Domain: Cloudflare. AskS1.com at ~$10/year.

What's Next

Anthropic and OpenAI S-1s are expected soon. AskS1 will be there when they file.