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 gives an asymptotic upper bound: it describes how work grows once the input becomes large. Fixed multipliers and lower-order terms don't change the growth 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).

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 similarity score. The NumPy lesson already gave you the mechanics of vectors and dot products; here we count their cost.

Each exact dot product inspects d coordinates. 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.

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.

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. This doesn't yet model a complete language model, optimized kernels, 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.

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.

What to remember

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.

Mastery check

Key concepts

• Complexity describes growth of one named operation, not an entire product.
• Exact vector retrieval over authorized candidates performs O(n * d) scoring work.
• Bounded top-k selection reduces unnecessary ordering but doesn't remove exact scoring.
• All-pairs loops are a quadratic danger sign in retrieval cleanup and later token processing.
• A budget guard converts complexity reasoning into an observable system decision.

Evaluation rubric

• Foundational: Counts scan checks and explains why doubling authorized chunks doubles exact scan work.
• Intermediate: Implements exact vector scoring plus bounded top-k selection and distinguishes O(n * d) scoring from O(n log k) selection.
• Advanced: Identifies a quadratic request-path trap, replaces it only when requirements allow, and defines a work budget before proposing approximate retrieval.

Follow-up questions

Common pitfalls

Optimizing before defining the operation

• Symptom: Team says "use a faster retriever" without knowing whether filtering, scoring, or selection consumes time.
• Cause: No input variables or repeated operations were named.
• Fix: Report authorized candidate count, embedding dimension, returned k, and measured time for each stage.

Returning unauthorized evidence faster

• Symptom: Global vector search is fast, but its candidates include chunks outside the requesting project's permissions.
• Cause: Optimization bypassed the authorization boundary introduced in the SQL lesson.
• Fix: Treat authorization as part of correctness. Any indexed design must preserve the same allowed-result contract.

Claiming top-k solved full retrieval

• Symptom: Full sort was replaced by a heap, but latency barely changes.
• Cause: Selection was cheap compared with producing every embedding similarity score.
• Fix: Track score work and selection work separately. Optimize the dominant measured step.

Hiding quadratic work in cleanup

• Symptom: Request time spikes after adding deduplication or reranking among many candidates.
• Cause: A nested loop silently added all-pairs comparisons.
• Fix: Count pairs for realistic n before shipping. Narrow the requirement or move expensive analysis out of the request path.