Linear Algebra

§ Sparse Multiplication

multiply, maxsim and attend read the walk as arithmetic rather than as retrieval. All of them need an inner-product index, since a product, a maximum over logits, and a softmax are all things only those kinds score.

multiply reports every pair the traversal scored rather than only the nearest: an approximate A × Bᵀ, dense in and sparse out. A walk computes many times the products it reports and each of them is exact, so the caller stops recomputing what the index already knew. How many pairs a walk scores is known only once it ends, so they come back ragged, with Apache Arrow offsets around them:

products = index.on(pool).multiply(rows, 0, arena)  # 0 keeps every pair; a bound keeps the first ones
offsets = np.asarray(products.offsets)  # (rows + 1,): left row `i` spans offsets[i] to offsets[i + 1]
columns = np.asarray(products.keys)  # (pairs, 16): which indexed entry each pair names
scores = np.asarray(products.scores)  # (pairs,): the exact products
products.required  # pairs scored before the bound cut any
row_keys, row_scores = products.query(0)  # one left row's pairs, for each of the len(products) rows

§ Late Interaction

maxsim scores multi-row queries against multi-vector documents, where every query row takes its best match within a key and those maxima sum to that key’s score. A document is one key holding its token rows, which is what values_per_key above one exists for, and the result is the ragged run multiply answers, one run of documents per query, largest first. A zero wanted keeps every document a query scored.

tokens = DenseIndex.init_ram(dimensions=128, metric=DenseMetric.INNER, values_per_key=32)
...
documents = tokens.on(pool).maxsim(query_tokens, 32, 10, arena)  # 32 token rows per query, up to 10 documents each
offsets = np.asarray(documents.offsets)  # (queries + 1,): query `i` spans offsets[i] to offsets[i + 1]

§ Attention

attend is Flash Attention folded into the walk: every key the walk scores folds into each head’s running maximum, partition and weighted value sum, with no top-k cut, so the long tail it scores brings the result toward exact dense attention. The index holds one layer’s keys for one key-value head and no values, so row_of names the row of values each scored key reads, the rows as wide as the keys and stored in the index’s quantization. Grouped-query heads share one walk per token: with head_count=8, row t * 8 + h of the queries is head h of token t.

carry = np.zeros((len(queries), 2), dtype=np.float32)
row_of = {key: row for row, key in enumerate(context_keys)}.get  # a scored Key in, its row of `values` out
outputs = index.on(pool).attend(queries, values, row_of, arena, head_count=8, outputs_dtype=Scalar.BF16, carry=carry)

A row_of answering None, or a row outside values, refuses the call with ShapeMismatchError, since a missing row is a wrong softmax rather than a smaller one; so do values of another width or scalar type, which values_dtype= names when the buffer cannot. It re-enters Python from the library’s threads, so it runs under the GIL. A VRAM walk resolves values on the device, where no Python callable runs, so attend with a VRAM arena raises DeviceError. The attended rows come back already divided by the partition, as a DenseVectors over the arena.

Ask for the carry to recombine this branch by partial-softmax rescaling with another over the same queries, such as attention sinks, a dense recent window, or a second index of one context. Keep the recent window out of the index, inserting a token once it leaves the window, so the two branches never count a key twice. Each of its rows holds one query’s largest logit and the softmax denominator taken against it; a maximum without its partition is a number nothing can rescale, which is why they travel as one row rather than as two arrays.