# Linear Algebra

> USearch for Zig

### 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.

```zig
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.

```zig
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`.

```zig
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);
```

`const usearch = @import("usearch");`

`const ValueLookup = @import("usearch").ValueLookup;`

`const DenseProducts = @import("usearch").DenseProducts;`

## DenseSoftmaxState

The online-softmax carry of one query row - Flash Attention's running maximum and partition.

```zig
pub const DenseSoftmaxState = extern struct
```

Mirrors `usearch_dense_softmax_state_t`.

The two are one concept: a maximum without its partition is a number nothing can rescale, so
they share an element rather than travelling as two arrays a caller could supply half of.

- `maximum_score` `f32`: The largest logit seen so far - the recurrence's `m`.
- `partition` `f32`: The sum of exponentials taken against that maximum - the recurrence's `l`.

## DenseMultiplyConfig

Optional settings of [`DenseIndex.multiply`](https://www.unum.cloud/docs/usearch/zig/metrics.md#multiply).

```zig
pub const DenseMultiplyConfig = struct
```

- `wanted` `usize`: Bound on pairs kept per left row, the first ones its walk scored; zero keeps every pair.
- `expansion_factor` `usize`: The breadth of the candidates, which widens the emitted pattern; zero derives.
- `progress` `ProgressCallback`
- `progress_steps` `usize`: Reports the call makes at most, the last at completion; zero derives to ten.
- `stats` `?*DenseTraversalStats`

## DenseAttendConfig

Optional settings of [`DenseIndex.attend`](https://www.unum.cloud/docs/usearch/zig/metrics.md#attend).

```zig
pub const DenseAttendConfig = struct
```

- `head_count` `usize`: The query heads sharing the index's key-value head, and with it one walk per token: row `t · head_count + h` is head `h` of token `t`. It must divide the rows; zero means one.
- `carry` `?[]DenseSoftmaxState`: The softmax state, one per query row, lent rather than written in the arena; null skips it.
- `outputs_scalar` `Scalar`: The scalar type the attended rows land as; `.unknown` takes the queries' own.
- `expansion_factor` `usize`: The breadth of the candidates; zero derives. Wider candidates walk further, folding more of the tail.
- `score_scale` `f32`: The logit scale, conventionally the inverse square root of the head dimensionality; zero derives it from the index's frozen geometry.
- `progress` `ProgressCallback`
- `progress_steps` `usize`: Reports the call makes at most, the last at completion; zero derives to ten.
- `stats` `?*DenseTraversalStats`

## DenseMaxsimConfig

Optional settings of [`DenseIndex.maxsim`](https://www.unum.cloud/docs/usearch/zig/metrics.md#maxsim).

```zig
pub const DenseMaxsimConfig = struct
```

- `expansion_factor` `usize`: The breadth of the candidates; zero derives.
- `progress` `ProgressCallback`
- `progress_steps` `usize`: Reports the call makes at most, the last at completion; zero derives to ten.
- `stats` `?*DenseTraversalStats`

## DenseMultiply

One [`DenseIndex.multiply`](https://www.unum.cloud/docs/usearch/zig/metrics.md#multiply), as a [`Deferred`](https://www.unum.cloud/docs/usearch/zig/executors.md#Deferred) holds it.

```zig
pub const DenseMultiply = struct
```

- `left` `RowsView`
- `config` `DenseMultiplyConfig`
- `stamp` `Arena.Stamp`: The call the borrowed arena serves, which every view over the outputs carries.
- `products` `usearch_matches_tape_view_t`
- `written` `usize`
- `required` `usize`
- `outcome` `Outcome`

## DenseAttend

One [`DenseIndex.attend`](https://www.unum.cloud/docs/usearch/zig/metrics.md#attend), as a [`Deferred`](https://www.unum.cloud/docs/usearch/zig/executors.md#Deferred) holds it.

```zig
pub const DenseAttend = struct
```

- `queries` `RowsView`
- `value_lookup` `ValueLookup`
- `config` `DenseAttendConfig`
- `stamp` `Arena.Stamp`: The call the borrowed arena serves, which every view over the outputs carries.
- `outputs` `usearch_rows_view_t`
- `outcome` `Outcome`

## DenseMaxsim

One [`DenseIndex.maxsim`](https://www.unum.cloud/docs/usearch/zig/metrics.md#maxsim), as a [`Deferred`](https://www.unum.cloud/docs/usearch/zig/executors.md#Deferred) holds it.

```zig
pub const DenseMaxsim = struct
```

- `queries` `RowsView`
- `rows_per_query` `usize`
- `wanted` `usize`
- `config` `DenseMaxsimConfig`
- `stamp` `Arena.Stamp`: The call the borrowed arena serves, which every view over the outputs carries.
- `matches` `usearch_matches_tape_view_t`
- `written` `usize`
- `required` `usize`
- `outcome` `Outcome`

## ValueLookup

Where [`attend`](https://www.unum.cloud/docs/usearch/zig/metrics.md#attend) reads value rows, as the C interface carries it: a `usearch_value_lookup_t` and the state forwarded into it.

```zig
pub const ValueLookup = struct
```

Build one with [`ValueLookup.of`](#of).

- `callback` `?ValueLookupFunction`
- `state` `?*anyopaque`

## of

Wraps `resolve` in a trampoline generated per call site, which answers one key's value row of `Element`, or null where it has none.

```zig
pub fn of(
    comptime Element: type,
    context: anytype,
    comptime resolve: fn (@TypeOf(context), Key) ?[]const Element,
) ValueLookup
```

Pass `{}` for a lookup needing no context, and a
single-item pointer otherwise.

A row must be as wide as the keys, stored in the index's quantization, and alive until the
call is final. The trampoline checks the scalar and columns each batch states, so a null
row, or one of another kind or width, refuses the call with [`Error.ShapeMismatch`](https://www.unum.cloud/docs/usearch/zig/errors.md#ShapeMismatch). It runs
concurrently from the executor's threads.

The trampoline is a host function, so it serves RAM and NVMe handles only: a VRAM walk calls
`callback` on the device, so a VRAM handle needs a device-callable one set directly.

## DenseProducts

The ragged output of [`DenseIndex.multiply`](https://www.unum.cloud/docs/usearch/zig/metrics.md#multiply) or [`DenseIndex.maxsim`](https://www.unum.cloud/docs/usearch/zig/metrics.md#maxsim) in an arena, laid out as Apache Arrow does: query `i` spans pairs `offsets[i]` up to `offsets[i + 1]` of [`keys`](https://www.unum.cloud/docs/usearch/zig/retrieval-and-streaming.md#keys) and [`scores`](#scores).

```zig
pub const DenseProducts = struct
```

Mirrors `usearch_matches_tape_view_t`.

It reads the arena, so every read is refused once that arena serves another call or is freed.

- `stamp` `Arena.Stamp`
- `view` `usearch_matches_tape_view_t`
- `queries` `usize`: Left-hand rows the call multiplied, or queries it scored.
- `written` `usize`: Pairs written across every query.
- `required` `usize`: Pairs scored across every left row, or keys across every query for a [`maxsim`](https://www.unum.cloud/docs/usearch/zig/metrics.md#maxsim), before `wanted` cut any.

## query

The pairs of one left row in traversal order, or one query's keys largest first for a [`maxsim`](https://www.unum.cloud/docs/usearch/zig/metrics.md#maxsim), refusing a `position` past `queries` with [`Error.InvalidArgument`](https://www.unum.cloud/docs/usearch/zig/errors.md#InvalidArgument), a stale view with [`Error.Uninitialized`](https://www.unum.cloud/docs/usearch/zig/errors.md#Uninitialized), and device memory with [`Error.Device`](https://www.unum.cloud/docs/usearch/zig/errors.md#Device).

```zig
pub fn query(
    self: DenseProducts,
    position: usize,
) Error!QueryMatches
```

## offsets

The `queries + 1` offsets, refused as [`query`](#query) refuses a stale view or device memory.

```zig
pub fn offsets(self: DenseProducts) Error![]const usize
```

## keys

Every pair's indexed key, end to end, refused as [`query`](#query) refuses a stale view or device memory.

```zig
pub fn keys(self: DenseProducts) Error![]const Key
```

## scores

Every pair's product, positionally paired with [`keys`](https://www.unum.cloud/docs/usearch/zig/retrieval-and-streaming.md#keys), refused as [`keys`](https://www.unum.cloud/docs/usearch/zig/retrieval-and-streaming.md#keys) is.

```zig
pub fn scores(self: DenseProducts) Error![]const Distance
```

## residency

Where the pairs live, which the host reads only as `.ram` or `.nvme`.

```zig
pub fn residency(self: DenseProducts) Residency
```