ML Interview Prep · 159

Glossary

The technical terms of this track, with short definitions (and the Persian term where available). Each term links to the lesson where it is introduced.

A/A test: An A/B test with two identical arms. At level $\alpha = 0.05$ it should reject about 5% of the time; more rejections show a bug in the setup or the analysis. Introduced in: Lesson 9
A/B test: A randomized experiment that shows two versions of a product to random groups of users and compares a primary metric with a statistical test. Introduced in: Lesson 9
activation checkpointing: Storing only the input of each layer in the forward pass and recomputing the rest in the backward pass. It saves memory for about 33% more compute. Introduced in: Lesson 12
AdamW: Adam with decoupled weight decay: the update $\hat m/(\sqrt{\hat v} + \varepsilon)$ from running moments of the gradient, and a separate step $\theta \leftarrow (1 - \gamma\lambda)\theta$ outside the division. Introduced in: Lesson 7
agent: An LLM in a loop that can act: it writes a tool call, the system runs the tool, and the observation is appended to the context, until a final answer or a limit. Introduced in: Lesson 15
all-gather: A collective in which every GPU starts with one chunk and ends with all $p$ chunks. Introduced in: Lesson 12
all-reduce: A collective after which every GPU holds the sum of the vectors of all GPUs. It is a reduce-scatter followed by an all-gather; the ring algorithm sends about $2n$ bytes per GPU. Introduced in: Lesson 12
amortized cost: A bound on the total cost of a sequence of operations: one operation can be slow, but any sequence of $m$ operations costs at most $m \cdot c$ in total, so the average cost per operation is at most $c$ . Example: list.append is amortized $O(1)$ . Introduced in: Lesson 1
arithmetic intensity: FLOPs divided by bytes moved, $I$ . An operation is compute-bound when $I$ is above the ridge point $F/\text{BW}$ of the hardware and memory-bound when it is below. Introduced in: Lesson 12
AUC: The area under the ROC curve. It equals $P(S^+ > S^-) + \tfrac12 P(S^+ = S^-)$ for the scores of a random positive and a random negative, so it measures ranking, not calibration. Introduced in: Lesson 6
backtracking: Search that builds a solution one choice at a time: choose, explore the rest recursively, then undo the choice and try the next one. Used when you must list all solutions. Introduced in: Lesson 4
bagging: Training many models (usually deep trees) on bootstrap samples and averaging them. It lowers the variance; a random forest also samples features at each split to decorrelate the trees. Introduced in: Lesson 9
beam search: A decoding rule that keeps the $n_b$ best prefixes (the beam) by total log-probability at each step, and returns the finished hypothesis with the best length-normalized score. Introduced in: Lesson 8
bf16: A 16-bit floating-point format with the 8 exponent bits of fp32 and 8 significant bits. It has the range of fp32, so it needs no loss scaling, but it is coarse: the gap near 1 is $2^{-7}$ . Introduced in: Lesson 7
bias correction: Dividing Adam's moment estimates by $1 - \beta_1^t$ and $1 - \beta_2^t$ . The moments start at zero, so without this the early steps would use estimates that are too small. Introduced in: Lesson 7
bias–variance decomposition: For squared loss, expected test error = noise + bias² + variance. Bias is the error of the average model; variance is how much the model changes with the training sample. Introduced in: Lesson 9
binary heap: A complete binary tree stored in a list, where each parent is not larger than its children (min-heap). The minimum is at the root; push and pop cost $O(\log n)$ . Introduced in: Lesson 2
binary search: A search that halves the range where the answer can be at every step. On a monotone predicate (False, …, False, True, …, True) it finds the first True in $O(\log n)$ questions. Introduced in: Lesson 2
bits per byte: The total loss of a text in bits divided by its number of bytes, $T\mathcal L/(n_{\text{bytes}}\ln 2)$ . It does not depend on the tokenizer. Introduced in: Lesson 11
BM25: A lexical retrieval score that sums, over the query terms in a chunk, the inverse document frequency times a saturated term frequency normalized by the chunk length. Introduced in: Lesson 15
Bradley–Terry model: A model of pairwise preferences: $P(y_w \succ y_l \mid x) = \sigma(r(x, y_w) - r(x, y_l))$ . Reward models for RLHF are trained with its negative log-likelihood. Introduced in: Lesson 11
breadth-first search (BFS): Graph search with a queue as the bag. It visits nodes in order of their number of edges from the start, so it finds shortest paths in unweighted graphs in $O(V + E)$ . Introduced in: Lesson 3
byte-pair encoding (BPE): A tokenizer that starts with the 256 byte values and repeatedly merges the most frequent pair of neighbouring tokens into a new token, until the vocabulary has the wanted size. Introduced in: Lesson 7
candidate generation: The first stage of a funnel, also called retrieval: it picks a few hundred candidates from the whole catalog and optimizes recall. Introduced in: Lesson 14
canonical key: A value that is equal exactly for the members of one group, used as a dict key for grouping. For anagrams: the sorted letters of a word, or the tuple of its 26 letter counts. Introduced in: Lesson 1
causal mask: The mask that lets token $i$ attend only to keys $j \le i$ , by setting the scores of $j > i$ to $-\infty$ before the softmax. Introduced in: Lesson 8
chunked prefill: Splitting long prompts into chunks and mixing one chunk with many decode tokens in each step, so a long prefill does not cause a TPOT spike. Introduced in: Lesson 13
classifier-free guidance: Training a diffusion model with the condition dropped in about 10–20% of the examples, then sampling with $\tilde\varepsilon = \varepsilon_\theta(x_t) + w\,(\varepsilon_\theta(x_t, c) - \varepsilon_\theta(x_t))$ . A guidance scale $w > 1$ trades diversity for fidelity to $c$ . Introduced in: Lesson 10
Cohen's kappa: Agreement between two raters beyond chance: $\kappa = (p_o - p_e)/(1 - p_e)$ , with $p_o$ the observed and $p_e$ the chance agreement. Introduced in: Lesson 15
compute-optimal: The model size and token count that give the lowest loss for a fixed compute $C \approx 6ND$ . Chinchilla found about 20 tokens per parameter. Introduced in: Lesson 11
continuous batching: Scheduling at the level of decode steps: a finished sequence leaves the batch at once and a waiting request joins at the next step. It removes head-of-line blocking. Introduced in: Lesson 13
cross-encoder: A reranker that reads the query and one chunk together in one transformer. It is more accurate than a bi-encoder, but costs one forward pass per pair, so it reranks only the top candidates. Introduced in: Lesson 15
CUPED: Controlled experiments using pre-experiment data: subtract the part of the metric that the user's pre-experiment value predicts. It reduces the variance, and so the needed $n$ , by the factor $1 - \rho^2$ . Introduced in: Lesson 14
data parallelism: Each GPU holds the whole model and processes a different part of the batch; the gradients are averaged with an all-reduce. Introduced in: Lesson 12
decision table: A table prepared before a research talk with one row per design choice: the alternatives, the evidence for the choice, its cost or risk, and what would change it. Introduced in: Lesson 16
decode: The second phase of generation: one forward pass per new token, reading all weights and the KV cache. It is memory-bound at small batch sizes. Introduced in: Lesson 8
decontamination: Removing benchmark test items (and near-duplicates of them) from the training data, so that evaluation scores are not inflated. Introduced in: Lesson 11
dependency injection: Passing the outside dependencies of code (a clock, a fetch function) as arguments, so that tests can replace them with fakes. Introduced in: Lesson 5
depth-first search (DFS): Graph search with a stack (or recursion) as the bag. It follows one path as far as possible before it backs up; used for connectivity, cycles and topological order. Introduced in: Lesson 3
Dijkstra's algorithm: Single-source shortest paths with non-negative edge weights: take the closest unfinished node from a priority queue and relax its edges. Cost $O((V + E)\log V)$ with a binary heap. Introduced in: Lesson 3
DPO: Direct preference optimization: a classification loss on preference pairs with the implicit reward $\beta \log(\pi_\theta(y \mid x)/\pi_{\text{ref}}(y \mid x))$ . It needs no reward model and no sampling during training. Introduced in: Lesson 11
dynamic programming (DP): Solving a problem from the answers of smaller subproblems that repeat. Each subproblem, described by a few numbers called the state, is solved once and stored. Introduced in: Lesson 4
edit distance: The smallest number of single-letter insertions, deletions and substitutions that turn one string into another (Levenshtein distance). The DP takes $O(mn)$ time. Introduced in: Lesson 4
exposure bias: The mismatch of a model trained with teacher forcing: at sampling time it conditions on its own outputs, which it never saw in training, so errors can compound. Introduced in: Lesson 10
fast and slow pointers: Two pointers that move 1 and 2 nodes per step through a linked list. They find the middle in one pass and detect a cycle (Floyd's algorithm). Introduced in: Lesson 1
feature store: A system that keeps one definition of each feature for training and serving, with point-in-time correct joins. It prevents training–serving skew and leakage. Introduced in: Lesson 14
FID: Fréchet inception distance: the distance between Gaussians fitted to Inception features of real and generated images. It measures realism and diversity; lower is better. Introduced in: Lesson 15
flow matching: A generative model that joins each noise sample to a data sample by a straight line, learns the average velocity at each point, and generates by integrating an ODE. Introduced in: Lesson 10
funnel: The multi-stage design of recommendation, search and ads: cheap retrieval with high recall over millions of items, then expensive ranking of a few hundred candidates. Introduced in: Lesson 14
goodput: In training: the fraction of the elapsed time spent on useful training steps. In serving: the requests per second that meet the latency targets. Introduced in: Lesson 12
gradient accumulation: Adding the gradients of $K$ micro-batches before one optimizer step, to train with a batch that does not fit in memory. Each micro-batch loss must be divided by $K$ . Introduced in: Lesson 7
gradient boosting: Gradient descent in function space: each round fits a small tree to the pseudo-residuals $r_i = -\partial L/\partial F(x_i)$ and adds it, with a small learning rate, to the model. Introduced in: Lesson 9
gradient check: Comparing an analytic gradient with the central difference $(L(\theta + \varepsilon e_j) - L(\theta - \varepsilon e_j))/(2\varepsilon)$ in float64. A relative error below about $10^{-6}$ means the gradient is correct. Introduced in: Lesson 6
gradient clipping: Rescaling all gradients together by $\min(1, c/\|g\|_2)$ when their global norm $\|g\|_2$ is above $c$ . It keeps the direction and caps the step. Introduced in: Lesson 7
greedy algorithm: An algorithm that makes a sequence of locally best choices and never revisits them. It is correct only when an exchange argument shows that the greedy choice is safe. Introduced in: Lesson 2
grouped-query attention (GQA): Attention in which $n_h$ query heads share $n_{kv} < n_h$ key/value heads, in groups of $n_h/n_{kv}$ . It shrinks the KV cache by the factor $n_h/n_{kv}$ . Multi-query attention (MQA) is the case $n_{kv} = 1$ . Introduced in: Lesson 8
GRPO: Group relative policy optimization: sample $G$ responses per prompt and give each the advantage $(r_i - \operatorname{mean}(r))/\operatorname{std}(r)$ . The group mean replaces the value model as the baseline. Introduced in: Lesson 11
Gumbel-max trick: With $g_i = -\log(-\log u_i)$ and independent $u_i \sim \text{Uniform}(0, 1)$ , $\arg\max_i (z_i + g_i)$ is an exact sample from $\operatorname{softmax}(z)$ . Introduced in: Lesson 8
hash map: A map from keys to values with average $O(1)$ insert and lookup (Python's dict). It remembers what you have seen, so one lookup replaces a search. Introduced in: Lesson 1
hash table: The data structure behind a hash map: each key is stored in a slot chosen by its hash. When many keys share slots (a collision), one operation can cost up to $O(n)$ . Introduced in: Lesson 1
He initialization: Initializing the weights of a ReLU layer with variance $2/n_{\text{in}}$ , so that the second moment of the activations stays the same from layer to layer. Introduced in: Lesson 10
head-of-line blocking: Waiting of new requests until a whole static batch has finished, because the longest request holds the batch. Introduced in: Lesson 13
HNSW: Hierarchical navigable small world: an approximate nearest-neighbour index built as a layered graph of near neighbours. Introduced in: Lesson 14
inertia: The k-means objective $J = \sum_i \|x_i - \mu_{c_i}\|^2$ : the sum of squared distances of the points to their assigned centers. Introduced in: Lesson 6
interval scheduling: The problem of choosing the largest set of non-overlapping intervals. Sorting by end time and taking each interval that starts after the last end taken is optimal. Introduced in: Lesson 2
invariant: A statement about the state of an algorithm or a class that is true before and after every step or method call. It explains why the code is correct. Introduced in: Lesson 1
inverse propensity scoring (IPS): Weighting each click at position $k$ by $1/\theta_k$ , the inverse probability that the position is examined, so that the weighted click rate estimates relevance without position bias. Introduced in: Lesson 14
inverted dropout: Dropout that zeroes each activation with probability $p$ in training and scales the others by $1/(1-p)$ , so that nothing changes at evaluation time. Introduced in: Lesson 10
iso-FLOP curve: The final loss as a function of model size $N$ along a line of fixed compute $C$ , with $D = C/(6N)$ tokens. It is U-shaped, and its minimum is the compute-optimal model. Introduced in: Lesson 11
Kahn's algorithm: A topological sort that repeatedly removes a node with in-degree 0. If fewer than $V$ nodes come out, the graph has a cycle. Cost $O(V + E)$ . Introduced in: Lesson 3
KV cache: The stored keys and values of all earlier tokens. Each decode step computes $q, k, v$ only for the new token and attends over the cache, which is exact because of the causal mask. Introduced in: Lesson 8
label smoothing: Training on the target $(1-s)\,\text{onehot} + s/K$ for $K$ classes instead of the one-hot vector. It stops the logits from growing without bound. Introduced in: Lesson 10
latent diffusion: Running the diffusion process in the latent space of a pretrained autoencoder instead of on pixels, which makes training and sampling much cheaper. Introduced in: Lesson 15
lazy deletion: Pushing a new (distance, node) pair into the heap instead of a decrease-key, and skipping old, stale pairs when they come out. Introduced in: Lesson 3
lazy refill: Computing the tokens that a bucket gained since its last update only when a request arrives, so no timer thread is needed. Introduced in: Lesson 5
leakage: Information in the training data or features that is not available at prediction time, for example a feature recorded after the outcome, or a scaler fitted before the split. It makes offline scores too good. Introduced in: Lesson 9
least privilege: Giving each tool or agent only the permissions its task needs, so that a successful prompt injection can do little harm. Introduced in: Lesson 15
least recently used (LRU) cache: A cache of at most $C$ keys that evicts the key used longest ago. A dict plus a doubly linked list in order of use gives $O(1)$ get and put. Introduced in: Lesson 5
Little's law: In a stable system, the mean number of requests in the system equals the arrival rate times the mean time in the system: $L = \lambda W$ . Introduced in: Lesson 13
LLM-as-judge: Using an LLM to grade or compare outputs. It is cheap but biased towards the first position, longer answers and its own outputs, so its agreement with human labels must be checked. Introduced in: Lesson 11
Lloyd's algorithm: The standard k-means method: assign each point to its nearest center, move each center to the mean of its points, and repeat. $J$ never increases, but the result is only a local optimum. Introduced in: Lesson 6
log-sum-exp trick: Computing $\log \sum_j e^{z_j}$ as $m + \log \sum_j e^{z_j - m}$ with $m = \max_j z_j$ , so that no exponential overflows. The stable softmax uses the same shift. Introduced in: Lesson 6
logit: An unnormalized score. Softmax turns a vector of logits $z$ into probabilities $p_k = e^{z_k}/\sum_j e^{z_j}$ . Introduced in: Lesson 6
longest increasing subsequence (LIS): The longest subsequence whose values strictly increase. The $O(n \log n)$ method keeps, for each length, the smallest last value and updates it with binary search. Introduced in: Lesson 4
LoRA: Low-rank adaptation: freeze the weight $W_0$ and train $\Delta W = (\alpha/r)\,BA$ with $B \in \mathbb{R}^{d \times r}$ , $A \in \mathbb{R}^{r \times k}$ and $r \ll \min(d, k)$ . $B = 0$ at the start, so training starts exactly at the pretrained model. Introduced in: Lesson 11
loss scaling: Multiplying the loss by a factor $S$ before the backward pass and dividing the gradients by $S$ after it, so that small fp16 gradients do not underflow to zero. Introduced in: Lesson 7
lower bound: The first position in a sorted list $a$ with $a_i \ge x$ (bisect.bisect_left): the first place where $x$ could be inserted. Introduced in: Lesson 2
machine epsilon: The gap between 1 and the next larger number of a floating-point format: $2^{-7}$ for bf16, $2^{-10}$ for fp16, $2^{-23}$ for fp32. Introduced in: Lesson 7
McNemar's exact test: A test of two systems on the same questions that uses only the discordant questions: the number won by one system is $\text{Binomial}(b + c, 1/2)$ under $H_0$ . Introduced in: Lesson 15
mean reciprocal rank (MRR): The mean over queries of $1/(\text{rank of the first relevant result})$ , with 0 when no relevant result is shown. Introduced in: Lesson 14
memoization: Recursion plus a cache: look a state up before computing it, and store the result after. With $S$ states and $W$ work per state the cost is $O(S \cdot W)$ . Introduced in: Lesson 4
minimum detectable effect (MDE): The smallest effect $\delta$ that an A/B test is sized to detect. With $\alpha = 0.05$ and 80% power, a conversion test needs about $n \approx 16\,p(1-p)/\delta^2$ users per arm. Introduced in: Lesson 9
mixed precision: Running matrix products in 16-bit numbers (bf16 or fp16) while the master weights, the optimizer state and long sums stay in fp32. Introduced in: Lesson 7
mode collapse: The typical failure of a GAN: the generator covers only part of the data distribution. Introduced in: Lesson 10
model FLOPs utilization (MFU): The fraction of the peak FLOP/s of the hardware that the model's useful FLOPs really use. Large tuned training runs reach about 40%. Introduced in: Lesson 11
model states: The parameters, gradients and optimizer states of a model. With mixed-precision Adam they take about $16\Psi$ bytes for $\Psi$ parameters. Introduced in: Lesson 12
monotonic deque: A double-ended queue with sorted values, used on a sliding window: pop smaller values from the back and expired indices from the front. It gives the maximum of every window in $O(n)$ . Introduced in: Lesson 2
monotonic stack: A stack whose items stay sorted. Each new item pops the items it answers (for example, all smaller items for "next greater element"), so every index is pushed and popped at most once: $O(n)$ in total. Introduced in: Lesson 2
NDCG@k: Normalized discounted cumulative gain: $\text{DCG@}k = \sum_{i=1}^k (2^{\text{rel}_i} - 1)/\log_2(i+1)$ , divided by the DCG of the ideal order. It rewards relevant items near the top. Introduced in: Lesson 14
negative downsampling: Keeping all positives and only a fraction $w$ of the negatives in training data. The predicted odds must then be multiplied by $w$ to recover calibrated probabilities. Introduced in: Lesson 14
normalized entropy (NE): The average log loss divided by the entropy of the background rate $p$ : $\text{NE} = \text{log loss}/(-[p\ln p + (1-p)\ln(1-p)])$ . Below 1 means better than always predicting $p$ . Introduced in: Lesson 14
out-of-bag (OOB) error: The error of a bagged model on each training point, computed only with the models whose bootstrap sample did not contain it (about $e^{-1} \approx 37\%$ of them). It is an almost free test estimate. Introduced in: Lesson 9
p-value: The probability, computed under the null hypothesis $H_0$ , of a test statistic at least as extreme as the one observed. It is not the probability that $H_0$ is true. Introduced in: Lesson 9
PagedAttention: Storing the KV cache in fixed-size blocks (16 tokens by default in vLLM) with a block table per sequence, as in virtual memory. It wastes less than one block per sequence. Introduced in: Lesson 13
pass@k: The probability that at least one of $k$ sampled answers is correct. The unbiased estimate from $n$ samples with $c$ correct is $1 - \binom{n-c}{k}/\binom{n}{k}$ . Introduced in: Lesson 11
perplexity: $\exp(\text{mean cross-entropy per token})$ . A model with perplexity $P$ is as unsure as a uniform choice among $P$ tokens. It compares only models with the same tokenizer. Introduced in: Lesson 11
pipeline bubble: The idle time of a pipeline at the start and end of each step. For GPipe with $p$ stages and $m$ micro-batches it is the fraction $(p-1)/(m+p-1)$ of the step. Introduced in: Lesson 12
pipeline parallelism: Splitting the layers of a model into $p$ stages on different GPUs and passing micro-batches from stage to stage. Introduced in: Lesson 12
population stability index (PSI): A drift statistic: bin a feature by reference quantiles and compute $\sum_i (q_i - p_i)\ln(q_i/p_i)$ . Rule of thumb: below 0.1 stable, above 0.25 a large shift. Introduced in: Lesson 14
pre-norm: The transformer block layout that normalizes the input of each sublayer: $x + \operatorname{Attn}(\operatorname{Norm}(x))$ , then $x + \operatorname{FFN}(\operatorname{Norm}(x))$ . It trains more stably than post-norm. Introduced in: Lesson 8
prefill: The first phase of generation: one forward pass over the whole prompt that fills the KV cache. It is compute-bound. Introduced in: Lesson 8
prefill/decode disaggregation: Running prefill and decode on separate GPU pools, each tuned for its own bottleneck, and sending the KV cache from one to the other. Introduced in: Lesson 13
prefix caching: Reusing the KV blocks of a prompt prefix (a system prompt, earlier chat turns) that an earlier request already computed, so its prefill is skipped. Introduced in: Lesson 13
prefix sums: The array $P$ with $P_0 = 0$ and $P_{j+1} = P_j + a_j$ . The sum of $a_i, \dots, a_{j-1}$ is then $P_j - P_i$ , one subtraction instead of a loop. Introduced in: Lesson 1
pretraining: The first stage of LLM training: next-token prediction with cross-entropy on trillions of tokens of text. Most of the model's knowledge comes from it. Introduced in: Lesson 11
product quantization (PQ): Compressing a vector by splitting it into $m$ sub-vectors and storing each as a 1-byte cluster id, so it takes $m$ bytes. Introduced in: Lesson 14
pruning: Stopping the exploration of a branch as soon as its partial solution cannot be completed or cannot beat the best solution found. Introduced in: Lesson 4
pseudo-polynomial: Polynomial in the numeric value of an input (for example a target amount $A$ ), but exponential in its number of bits. Knapsack and subset-sum DP tables are pseudo-polynomial. Introduced in: Lesson 4
QLoRA: LoRA on top of a base model stored in 4-bit NF4. It fine-tunes a 65B model on one 48 GB GPU. Introduced in: Lesson 11
rate limiter: A component that decides, for each request of a client, whether to allow or reject it, so that no client exceeds its allowed rate. Introduced in: Lesson 5
ReAct: The agent pattern in which each step has a short reasoning, a tool call and an observation. Introduced in: Lesson 15
recall@K: The share of the relevant items that appear among the top $K$ results, averaged over users or queries. Introduced in: Lesson 14
reciprocal rank fusion (RRF): Merging ranked lists (for example lexical and dense) by the score $\sum_{\text{lists}} 1/(k + \text{rank})$ , which needs no score calibration. Introduced in: Lesson 15
reduce-scatter: A collective after which GPU $i$ holds chunk $i$ (of size $n/p$ ) of the sum of all $p$ vectors. Introduced in: Lesson 12
relax: To relax the edge $u \to v$ : if $\text{dist}[u] + w(u, v) < \text{dist}[v]$ , set $\text{dist}[v]$ to the smaller value. Introduced in: Lesson 3
reliability diagram: A plot of the observed frequency of positives against the predicted probability, in bins. A calibrated model lies on the diagonal. Introduced in: Lesson 9
research talk: A presentation of your research to a mixed audience in an interview loop. It should state the main result early, explain the key idea with one picture, and defend each design choice. Introduced in: Lesson 16
retrieval-augmented generation (RAG): A design in which the system searches a document collection and puts the best chunks into the prompt before the model answers, so the model can use fresh or private knowledge and cite it. Introduced in: Lesson 15
RL with verifiable rewards (RLVR): Reinforcement learning on tasks where a program checks the answer (math, code tests), so the reward is 1 for a correct answer and 0 otherwise. Introduced in: Lesson 11
RLHF: Reinforcement learning from human feedback: train a reward model on human preferences, then optimize the policy with PPO against it, with a KL penalty to a reference model. Introduced in: Lesson 11
RMSNorm: A normalization that divides each token's vector by its root mean square and multiplies by a learned gain: $x / \sqrt{\operatorname{mean}(x^2) + \varepsilon} \odot g$ . Unlike LayerNorm, it does not subtract the mean. Introduced in: Lesson 8
roofline: The bound $t \ge \max(\text{FLOPs}/F,\ \text{bytes}/R)$ for every resource with rate $R$ . The largest term names the resource that limits the step. Introduced in: Lesson 12
RoPE: Rotary position embedding: rotate pairs of coordinates of the query and the key by angles proportional to the position. The score then depends only on the relative position $i - j$ . Introduced in: Lesson 8
sample-ratio mismatch: A split of users between the arms that differs from the planned ratio by more than chance allows. It points to a bug in assignment or logging, and the test result cannot be trusted. Introduced in: Lesson 9
sentinel node: A dummy node at the end of a linked list (for example head and tail). It removes special cases, because every real node then has a neighbour on both sides. Introduced in: Lesson 5
service-level objective (SLO): A latency target that the service must meet, usually as a percentile (for example TTFT p99 below 1 s). Introduced in: Lesson 13
sliding window: A range $[i, j)$ that grows on the right and shrinks on the left, and reuses the work of the last range. It is correct when the window condition is monotone: it stays true (or false) as the window grows. Introduced in: Lesson 1
speculative decoding: A small draft model proposes $\gamma$ tokens and the target model checks them in one forward pass. A rejection-sampling rule keeps the output distribution exactly that of the target model. Introduced in: Lesson 13
stack: A last-in, first-out list: append and pop at the same end in $O(1)$ . It keeps the items that are still open, like unmatched brackets. Introduced in: Lesson 2
STAR: A structure for behavioral answers: Situation, Task, Action, Result, plus a short Reflection. Most of the time goes to the Action. Introduced in: Lesson 16
statistical power: The probability $1 - \beta$ that a test rejects $H_0$ when a true effect of a given size exists. Introduced in: Lesson 9
SUTVA: The stable unit treatment value assumption: a user's outcome does not depend on the assignment of other users. Social networks and two-sided marketplaces break it. Introduced in: Lesson 9
tensor parallelism: Splitting each weight matrix of a layer over $t$ GPUs (Megatron), with two all-reduces of activations per layer in the forward pass and two in the backward pass. It needs fast links (NVLink). Introduced in: Lesson 12
time per output token (TPOT): The time between streamed output tokens, about one decode step. Also called inter-token latency. Introduced in: Lesson 13
time to first token (TTFT): The time from a request to the first output token: queueing plus prefill. Introduced in: Lesson 13
token bucket: A rate limiter with capacity $b$ and refill rate $r$ tokens per second. A request takes tokens if enough are present; in any window of length $T$ it allows at most $b + rT$ requests. Introduced in: Lesson 5
top-p (nucleus) sampling: Sampling from the smallest set of tokens whose total probability is at least $p$ (the nucleus), after renormalizing. The set adapts to the shape of the distribution. Introduced in: Lesson 8
topological order: An order of the nodes of a directed graph in which every edge $u \to v$ has $u$ before $v$ . It exists if and only if the graph is a directed acyclic graph (DAG). Introduced in: Lesson 3
trie: A prefix tree that stores strings: each edge adds one character, so each node is a prefix. Insert and search of a word of length $L$ cost $O(L)$ . Introduced in: Lesson 3
two pointers: A pattern that moves two indices through sorted data (or a linked list). Each step uses the order to rule out one element, so the scan is $O(n)$ instead of $O(n^2)$ . Introduced in: Lesson 1
two-tower model: A retrieval model with a user tower $u_\theta(x)$ and an item tower $v_\phi(y)$ whose dot product is the score. Item vectors are computed in advance and searched with an approximate nearest-neighbour index. Introduced in: Lesson 14
uniform symmetric quantization: Mapping weights to $n$ -bit integers with scale $s = \max|w|/(2^{n-1} - 1)$ : $q = \operatorname{round}(w/s)$ , $\hat w = sq$ . The error is at most $s/2$ inside the range. Introduced in: Lesson 13
union-find: A structure that keeps a partition of elements into disjoint sets, with find(x) (the representative of the set of $x$ ) and union(a, b). With union by rank and path compression, each operation is almost $O(1)$ amortized. Introduced in: Lesson 3
warmup: Raising the learning rate from a small value to its peak over the first steps of training, before the decay. Introduced in: Lesson 7
warmup–stable–decay (WSD): A learning-rate schedule that warms up, stays at the peak, and decays only in the last 10–20% of the steps, so a run can be extended from a checkpoint of the stable phase. Introduced in: Lesson 10
weight decay: Shrinking every weight towards zero a little at each step. In AdamW it is not the same as an L2 term in the loss, because Adam divides gradients by $\sqrt{\hat v}$ . Introduced in: Lesson 7
whatever-first search: Erickson's name for one generic graph search loop: take a node from a bag, mark it if new, and put its neighbours in the bag. A stack gives DFS, a queue gives BFS, a priority queue gives Dijkstra. Introduced in: Lesson 3
Young's checkpoint interval: The checkpoint interval $\tau^* = \sqrt{2\delta M}$ that minimizes lost time, for checkpoint cost $\delta$ and mean time between failures $M$ of the job. Introduced in: Lesson 12
ZeRO: Sharding of the model states over the $N_d$ data-parallel GPUs: stage 1 shards the optimizer states, stage 2 also the gradients, stage 3 also the parameters. FSDP is PyTorch's ZeRO-3. Introduced in: Lesson 12