反复横跳, Side-step

Attention takes its vocabulary from the dictionary: query, key, value. It drops the dictionary's one strict rule. A hash map returns the value whose key equals the query, or nothing. Attention returns every value, weighted by a softmax over how well each key matches. Lower the softmax temperature and the weights pile onto the best match, which turns attention back into a lookup, for the nearest key instead of an identical one.

A semantic ID is a hash that is supposed to collide, since similar items should share a prefix. When two items end up with the same full code, the RecSys notes reach for the fixes from the hash-table note. TIGER appends one more digit, which is separate chaining with the position in the chain written into the ID. LC-Rec reassigns the last level under a uniform constraint, which is what a better-spread hash function buys. The GRID note compares the two and finds TIGER's digit slightly ahead.

The MoE note meets the same problem under another name. When too many tokens pick one expert, “that expert becomes a queue while other experts sit idle”, so each expert gets a fixed capacity, like a bucket with a size limit.

LightGCN has no weight matrices inside its layers. Layer k is the normalized adjacency matrix raised to the k-th power, applied to the starting embeddings. If those embeddings were one-hot, the score between a user and an item would be exactly a weighted count of the walks between them. A walk of length 3, user → item → user → item, reads as “someone who liked what you liked also liked this”. That is collaborative filtering, derived from the exam fact.

The RecSys note came first, two months before the graph-theory chapter. The final-exam note adds the warning that matters here: ordinary multiplication, not Boolean, because the counts are the signal.

Generating a semantic ID token by token is a walk down a trie of every valid ID. At each step, constrained beam search runs the prefix search from the data-structures note and keeps a candidate only if its path exists. The GRID note then reports the twist: constrained and unconstrained beam search score about the same, and skipping the trie is faster and cheaper.

A top-1 mixture-of-experts layer is a multiplexer whose select lines are computed from the input and trained by gradient descent. The difference is where the work happens. A hardware mux has all of its inputs computed and wired in, and passes one of them through. An MoE layer runs only the expert it selects, which is the point of the design. Top-2 routing, as in Mixtral, has no mux equivalent: it blends two experts by their gate weights.

Both are the same loop: count, merge one pair, repeat. They work from opposite ends of the frequency table. Huffman merges the two rarest symbols, so rare symbols sink deep into the tree and get long codes. BPE merges the most frequent adjacent pair, so common strings collapse into single tokens.

Both are compression, too. BPE was published in 1994 as a data-compression algorithm and moved into machine translation about twenty years later. GPT-2 runs it on UTF-8 bytes, the encoding in your character-encoding note from December.

std::reduce may regroup a sum because it assumes the operation is associative. Floating-point addition is not: every partial sum is rounded, to 24 significant bits in fp32 and 8 in bf16. An inference engine that splits a reduction differently at small batch sizes gets slightly different logits from the trainer, even with identical weights. PPO's ratio between the two should be exactly 1, and sometimes it isn't. The mismatch note calls the result “an incorrect form of importance sampling”.

The std::reduce note and your first RL note were added in the same commit, on 13 Nov 2025. Ten months later they meet here, with the IEEE 754 layout from your computer-organization note two days after that.

Same Bellman. Richard Bellman's principle of optimality, that an optimal path is made of optimal sub-paths, drives both notes. Edge relaxation is a Bellman backup with costs instead of rewards, min instead of max, and no discount. Bellman–Ford sweeps every edge n − 1 times; value iteration sweeps every state until nothing changes.

The negative-cycle check has a counterpart too. A cycle with negative total cost has no shortest path, and a loop with positive total reward has no finite value when γ = 1. Discounting with γ < 1 is how RL keeps those values finite.

The critical-path method and backpropagation share a skeleton: one sweep over a DAG in topological order to compute values, then one sweep in reverse to send information back. Only the arithmetic changes. Earliest times use max and +, latest times use min and −, and backprop uses + and × on local derivatives.

The match goes one step further. Lengthen an activity by a day and the project length L* grows by a day if the activity is on a critical path, and not at all otherwise. That is a derivative of 1 or 0, and the key activities are exactly the edges where it is 1.