Linear Algebra

§ Sparse Multiplication

Three verbs, multiply, maxsim and attend, treat the index as a sparse operand rather than as a kNN store, each folding its arithmetic into the graph walk instead of materializing a match list. All three read logits rather than distances, so they run on an inner-product index alone.

multiply is a sparse matrix product, reporting every pair the traversal scored rather than only the nearest. How many pairs a walk scores is known only once it ends, so the call returns them as DenseProducts read in place from an arena: one run of pairs per left row, in traversal order, and required counting every pair scored before a non-zero wanted cut any.

let products = try index.on(executor).multiply(left, arena: arena, config: DenseMultiplyConfig(wanted: 64))
for pair in products[0] { print(pair.key, pair.distance) }

§ Late Interaction

maxsim is late interaction: 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 a valuesPerKey above one exists for, and the outputs are sized over documents rather than rows. The call returns the same DenseProducts as multiply, one ragged run per whole query with its documents largest score first, and a zero wanted keeps every document the query scored.

let documents = try index.on(executor).maxsim(tokens, rowsPerQuery: tokensPerQuery, wanted: 10, arena: arena)
for document in documents[0] { print(document.key, document.distance) }

§ Attention

attend is softmax attention over every key the graph walk scores, folded as Flash Attention folds key tiles, with outputs already divided by the partition. Row t · headCount + h of the queries, outputs and carry is head h of token t, so the query heads of grouped-query attention share the index’s one key-value head and one walk per token. The index stores no values: a ValueLookup names, for every scored key, its row of a values RowsView as wide as the keys and stored in the index’s own quantization. A key without a row, or values of another width or scalar kind than the library reads, refuses the call with shapeMismatch, since a missing row is a wrong softmax rather than a smaller one. A VRAM index walks on the device and resolves values through a device function, which a Swift closure cannot be, so attend refuses it with device. The lookup runs on the executor’s threads together, so it must be @Sendable and safe for concurrent use. The outputs land in the arena as rows of the scalar kind as: names, and a carry of one DenseSoftmaxState per query row folds this branch into another over the same queries.

let lookup = ValueLookup(values: RowsView(valueCache)) { key in rowOf[key] }
let context = try carry.withUnsafeMutableBufferPointer { carry in
    try index.on(executor).attend(
        queries, lookup: lookup, as: Float.self, arena: arena,
        config: DenseAttendConfig(headCount: 8, carry: carry))
}