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 refuse anything but an inner-product index with Error.ConfigMismatch.

multiply is a sparse matrix product: every left row is walked against the index, and how many pairs it scores is known only once the walk ends, so the products come back as a ragged DenseProducts: keys, scores and their Apache Arrow offsets, all in the arena.

const products = try index.on(executor).multiply(try .of(f32, left, 768), &arena, .{ .wanted = 64 });
for (0..products.queries) |row| {
    const pairs = try products.query(row);
    accumulate(row, pairs.keys, pairs.scores);
}

offsets, keys and scores answer the whole tape at once, for a consumer that takes Arrow buffers as they are.

§ 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 values_per_key above one exists for, and the outputs are sized over documents rather than rows. The keys land as a DenseProducts, one run per query, largest score first, and a zero wanted keeps every key a query scored.

const documents = try index.on(executor).maxsim(try .of(f32, tokens, 768), tokens_per_query, 10, &arena, .{});
for (0..documents.queries) |query| {
    const ranked = try documents.query(query);
    rerank(query, ranked.keys, ranked.scores);
}

§ Attention

attend is Flash Attention folded into the walk: every key it scores enters an online softmax, with no top-k cut, and the outputs come back as wide as the keys and divided by the partition. The index stores no values, so a ValueLookup resolves each scored key to its row, as wide as the keys and stored in the index’s quantization. Its trampoline checks the kind and width every batch states, so a missing row, or one of another kind or width, refuses the call with Error.ShapeMismatch. It runs on the executor’s threads, so it must tolerate concurrent calls. That trampoline is a host function, which serves RAM and NVMe indexes; a VRAM walk calls the lookup on the device, so a VRAM index takes a ValueLookup whose callback is device-callable, set directly. The head_count query heads of grouped-query attention share one walk per token, row t · head_count + h being head h of token t, and a carry of one DenseSoftmaxState per query row, lent rather than written in the arena, folds this branch into another over the same queries. The attended rows land in the arena as the queries’ own scalar type, or as the config’s outputs_scalar.

const Cache = struct {
    rows: []const usearch.Scalar.BF16,
    fn resolve(self: *const @This(), key: usearch.Key) ?[]const usearch.Scalar.BF16 {
        const entry: usize = @intCast(key.asInteger() orelse return null);
        return self.rows[entry * 128 ..][0..128];
}
};
const attended = try index.on(executor).attend(try .of(f32, queries, 128), .of(usearch.Scalar.BF16, &cache, Cache.resolve), &arena, .{
    .head_count = 8,
    .carry = carry,
});
const first_head = try attended.row(f32, 0);