Algorithms for ML Engineers

This retrieval problem builds on permission-aware SQL: first keep only rows this project and principal may retrieve, then rank those rows. That still leaves an engineering question: will ranking finish quickly after the number of allowed chunks grows from four to four million?

An algorithm is a recipe for completing a task. Complexity describes how the work or memory required by that recipe grows as its input grows. You'll count real retrieval operations before reaching for optimization folklore.

One request, one variable

A teammate asks an internal engineering assistant:

Why did the auth tests fail?

Assume SQL permission predicates, optionally reinforced by row-level security, have already returned only auth project chunks permitted for this request. Use four symbols:

These variables matter because different code grows with different parts of the request. A permission filter might reduce n. A larger embedding increases d. Returning only two citations controls k, but it doesn't automatically avoid scoring every candidate.

Count a complete scan

Start with an intentionally small, inspectable retriever. It scores a chunk by counting question words that appear in the chunk text.

chunks_checked isn't elapsed time. It's a count of the dominant repeated action: inspecting one candidate chunk. For four authorized chunks, this scan checks four. For forty thousand, it checks forty thousand. Real text work also depends on chunk length. When chunks have a configured size limit, counting candidate inspections is a useful first model. Without that bound, include words read as another growing input.

That's the core habit: identify an operation that repeats with scale, then count it.

Big-O names the growth shape

Big-O formally gives an asymptotic upper bound. In this lesson (and in common engineering slang) we use Big-O for the dominant growth class of the named operation, informally tight the way Θ is used in theory texts. Fixed multipliers and lower-order terms don't change that class. Under the bounded-chunk simplification above, scanning one extra authorized chunk adds one inspection, so candidate-scan work is O(n), read "order n" or "linear in n."

Doubling n doubles the repeated checks. The code still has overhead, such as building a set of question terms, but that overhead doesn't grow once per candidate. Big-O points to the piece that becomes dangerous at larger scale.

Don't call the whole bot "O(n)." Attach the claim to an operation: ranking authorized chunks with this bounded-length scan is O(n).

An authorized-chunk scan checks 8,000 bounded-length chunks. If the corpus doubles while the algorithm stays unchanged, about how many chunk inspections should you expect?

Answer

About 16,000. The scan is O(n) in candidate chunks, so doubling n doubles the dominant repeated work.

Vector scoring adds another input

Text overlap is only a teaching scorer. Semantic retrieval commonly represents the question and each chunk as embedding vectors, then computes a score. The NumPy lesson already gave you the mechanics of vectors and dot products; here we count their cost.

Each exact dot-product score inspects d coordinates. That ranking matches cosine only when the vectors are L2-normalized; the lab vectors below are not, so treat the score as raw dot product, not cosine similarity. Scoring all n allowed chunks therefore performs work proportional to n * d.

With four three-dimensional vectors, the score pass uses 12 coordinate multiplications. With 50,000 chunks and 768 coordinates, it uses 38,400,000 multiplications before it chooses citations. The exact ranking step is O(n * d) in time and storing all vectors is O(n * d) in memory.

Return top-k without sorting every result

Suppose the assistant will cite only k = 2 chunks. A first version can score all candidates and fully sort every result. In product code, treat k <= 0 as an empty result so heap logic never reads from an empty list.

This is correct. It also orders three losers that will never be shown. Sorting n scored candidates costs O(n log n).

A bounded min-heap stores only the top-k values seen so far. Its smallest retained score stays at the root, so a stronger candidate can replace the current weakest winner. Repairing the heap follows one path through a tree with k entries. That path has at most about log2(k) parent-child steps: three for k = 8, ten for k = 1,024. Python's heapq helpers implement that structure in the lab. With distinct scores the (score, id) key is enough; if ties matter, encode an explicit rule such as lower document ID wins (for example store (score, -doc_id) for integer IDs).

For k >= 2, maintaining the heap costs O(n log k) after scoring, with O(k) selection memory. For k = 1, one running maximum gives O(n) selection.^{[1]Reference 1Introduction to Algorithms (3rd ed.)https://mitpress.mit.edu/9780262033848/introduction-to-algorithms/}

Important limit: the heap improves selection, not exact vector scoring. If scores came from embeddings, you still paid O(n * d) to produce them. Engineers get into trouble when they speed up a cheap tail step and claim they fixed an expensive upstream step.

You replace a full sort with a top-10 heap, but still score 50,000 vectors of dimension 768. Which cost remains O(n * d)?

Answer

The exact vector-scoring pass. The heap reduces selection to O(n log k) and O(k) retained values, but it does not remove the 38.4 million coordinate products.

Spot a quadratic trap

Linear work doubles when the input doubles. Quadratic work grows far faster because each item is compared with many other items.

A tempting "cleanup" step might compare every retrieved chunk against every other retrieved chunk to remove near-duplicates. For n chunks it evaluates n * (n - 1) / 2 pairs, which is O(n^2).

At n = 1,000, a request-time pairwise pass makes 499,500 comparisons. That's a concrete failure case: a harmless-looking loop can consume the latency budget before generation begins.

If the requirement is only exact duplicate removal, a set changes the operation. It remembers texts already seen instead of comparing every pair.

This set-based path uses expected O(n) membership checks under normal hash-table behavior. Hashing still reads each text, so unbounded string length remains part of the real cost. It doesn't solve semantic near-duplicate detection. Requirements determine the algorithm: don't silently replace "similar meaning" with "identical string" just to obtain a better complexity label.

The same square shape appears later in attention

This course will teach Transformer internals later. For now, carry one preview: scaled dot-product attention computes a matrix from queries and keys, commonly written as Q @ K.T, so a self-attention sequence with t token positions has t * t score cells.^{[2]Reference 2Attention Is All You Need.https://arxiv.org/abs/1706.03762}

You don't need to understand the model yet to recognize the growth shape.

Doubling tokens quadruples cells. Read this as a per-layer / per-head order of magnitude for a dense float32 score grid of one sequence during prefill, before multi-head batching, fused kernels, or KV-cache decode optimizations. This doesn't yet model a complete language model or serving memory. It's a simple transfer of your new algorithm skill: when you see an all-pairs matrix, ask whether an input is being squared.

A dense attention score grid grows from 256 to 512 token positions. How does its cell count change?

Answer

It grows from 256^2 to 512^2, so the grid has four times as many cells. This is the O(t^2) all-pairs warning sign.

Measure scale and install a budget guard

Big-O tells you the shape, not whether today's workload meets a service objective. A useful engineer does both:

1. Count expected work to spot dangerous growth.
2. Benchmark the real implementation on representative data and hardware.
3. Reject or reroute requests whose predicted work exceeds the supported budget.

This first guard uses a count rather than a made-up millisecond conversion.

The rejected case doesn't justify weakening authorization or returning arbitrary evidence. It shows exact ranking over that many authorized candidates no longer fits this budget. Possible next experiments are a stricter legitimate filter, an offline-created index, or an approximate nearest-neighbor index evaluated for recall.

One later option is HNSW, a hierarchical proximity-graph approach to approximate nearest-neighbor search. It trades exact scoring of every vector for graph-guided candidate exploration, so any latency gain must be evaluated beside retrieval recall on real questions.^{[3]Reference 3Efficient and Robust Approximate Nearest Neighbor Using Hierarchical Navigable Small World Graphs.https://arxiv.org/abs/1603.09320} That's a Vector DB Internals topic, not a shortcut you need to implement in this foundation exercise.

Build it: an authorized exact top-k retriever

Now assemble the lesson into a small baseline you could test before adding an index:

• Authorization happens first.
• Every authorized vector is scored exactly.
• A bounded heap retains only k citations.
• The function reports score work so a caller can enforce a budget.

This exact version is your correctness baseline. It has a clean contract: only authorized rows can appear, returned results are exact among those rows, and the score cost is visible. Once a benchmark says the baseline is too slow, you know which behavior an optimized version must preserve.

Practice with numbers

Work these without code first. Build intuition for growth.

1. A project has n = 2,500 authorized chunks, each with d = 384 coordinates. How many coordinate multiplications does an exact dot-product scan perform?
2. A full sort orders 10,000 scored results even though the assistant returns k = 5. Which part does a bounded heap reduce, and which part remains unchanged?
3. A near-duplicate cleanup compares each of 200 chunks with every later chunk. How many comparisons occur?
4. An attention preview changes prompt length from 256 tokens to 1,024 tokens. By what factor does the number of score cells grow?
5. Your guard allows one million coordinate multiplications. Does exact scoring fit for n = 4,000, d = 256?

Solution sketches

1. 2,500 * 384 = 960,000 coordinate multiplications.
2. The heap reduces selecting the best five values from full-sort work to bounded top-k work. It doesn't remove the exact score pass that produced all 10,000 values.
3. 200 * 199 / 2 = 19,900 comparisons.
4. Token length grows by 1,024 / 256 = 4, so square score-cell count grows by 4 * 4 = 16.
5. No. 4,000 * 256 = 1,024,000, which exceeds the one-million budget.

A working complexity checklist

Three rules carry into every later AI system chapter:

1. Name the operation and its growing inputs before stating a complexity.
2. Keep a smallest-correct baseline so optimization can be checked for correctness.
3. Couple latency work with product requirements: authorization, citation quality, and recall don't disappear when a faster algorithm arrives.