# Linear Algebra

> USearch for Mojo

### Sparse Multiplication

`multiply` is a sparse matrix product: every pair the walk scored for each left row, in traversal order, lands in an arena as one ragged run, with one more offset than left rows, as Apache Arrow lays a ragged batch out.

```mojo
var products = index.on(executor).multiply(left, arena, DenseMultiplyConfig(wanted=64))
var offsets = products.offsets()
for row in range(left_rows):
    print(row, Int(offsets[row + 1] - offsets[row]), "pairs")
```

### 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 wanted count is over documents rather than rows.
The keys land as `multiply`'s pairs do, query `i` spanning `offsets()[i]` up to `offsets()[i + 1]`, largest score first, and a zero `wanted` keeps every key a query scored.

```mojo
var documents = index.on(executor).maxsim(tokens, tokens_per_query, 10, arena)  # DenseProducts, as multiply answers
var offsets = documents.offsets()
for query in range(documents.queries):
    print(query, Int(offsets[query + 1] - offsets[query]), "documents")
```

### Attention

`attend` is Flash Attention folded into the walk: every key it scores folds into each head's running maximum, partition and weighted value sum, with no top-k cut, and the attended rows land in the arena already divided by the partition.
The index stores no values, so a `ValueLookup` resolves every scored batch of keys to value rows, `columns` values of `scalar` apiece, the index's own width and kind, which it checks before answering any row.
A key without a row refuses the call with `Status.SHAPE_MISMATCH`, since a missing row is a wrong softmax rather than a smaller one.
A VRAM index calls its lookup inside the device walk, so there `value_lookup` must be a `__device__` function's address, read with `cudaMemcpyFromSymbol` on NVIDIA or `hipMemcpyFromSymbol` on AMD; a host function there is undefined, never refused.

```mojo
def value_rows(
    state: Address, keys: Pointer[Key, ImmUntrackedOrigin], count: c_size_t,
    scalar: ScalarKind, columns: c_size_t, rows: Pointer[Address, MutAnyOrigin],
) abi("C"):
    ...  # write one row address per key, or NULL_ADDRESS when it has none

var carry = List[DenseSoftmaxState](length=queries_count, fill=DenseSoftmaxState())
var context = index.on(executor).attend[DType.float32](
    queries, value_rows, cache_address, arena, DenseAttendConfig(head_count=8, carry=carry)
)
```

With `head_count=8`, row `t * 8 + h` of the queries is head `h` of token `t`, and the heads of one token share its walk.
A `carry` of one `DenseSoftmaxState` per query row, lent by you, folds this branch into another over the same queries, such as a recent window kept out of the index; a shorter one is refused, since the C structure carries no count for it.

`from usearch import DenseSoftmaxState, DenseProducts, DenseMaxsimConfig, …`

## ValueLookup

`usearch_value_lookup_t`: resolves [`count`](https://www.unum.cloud/docs/usearch/mojo/executors.md#count) keys to one value-row address each, [`columns`](https://www.unum.cloud/docs/usearch/mojo/retrieval-and-streaming.md#columns) values of `scalar` apiece - the index's own width and kind - alive until the call returns; a `NULL_ADDRESS` row refuses the call.

```mojo
comptime ValueLookup = def(
    Int,
    Pointer[Key, ImmUntrackedOrigin],
    UInt,
    ScalarKind,
    UInt,
    Pointer[Int, MutAnyOrigin]
) abi("C") thin -> None
```

Called with the `value_lookup_state` the verb was handed, once per scored batch and concurrently from
the executor's threads. A lookup whose rows hold another kind or width answers `NULL_ADDRESS` for
every key rather than handing the engine rows it would misread.

A VRAM index calls it inside the device walk instead, so there it must be the address of a
`__device__` function, as `cudaMemcpyFromSymbol` reads it, with its state and rows in memory that
device reads. Nothing tells the two kinds apart, so a host function there is undefined, never refused.

## DenseSoftmaxState

The online-softmax carry of one query row - `usearch_dense_softmax_state_t`.

```mojo
struct DenseSoftmaxState
```

Flash Attention's running maximum and partition. 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 runs a caller could supply half of. Carrying them folds one attention call into another
over the same queries.

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

Conforms to: `Copyable`, `Deinitable`, `ImplicitlyCopyable`, `Movable`, `RegisterPassable`, `TrivialRegisterPassable`

## __init__

Zeroes both, which is what an unfolded first branch starts from.

```mojo
def __init__() -> Self
```

## DenseProducts

The ragged output of [`multiply`](https://www.unum.cloud/docs/usearch/mojo/executors.md#multiply) and [`maxsim`](https://www.unum.cloud/docs/usearch/mojo/executors.md#maxsim) - `usearch_matches_tape_view_t` - read in place from its arena: query `i` spans pairs `offsets()[i]` up to `offsets()[i + 1]` of `keys()` and `scores()`.

```mojo
struct DenseProducts[origin: MutOrigin]
```

- `origin` (comptime): The arena the pairs live in, which this result borrows.

- `arena` `Pointer[Arena, origin]`: The arena holding the pairs.
- `generation` `Int`: The arena's call these pairs came from, so a read after a later call is refused.
- `view` `MatchesTapeViewArguments`: The keys, products and offsets, as the engine wrote them.
- `queries` `Int`: Left-hand rows the call multiplied, or queries it scored.
- `pairs` `Int`: Pairs written across every query.
- `required` `Int`: Pairs the walks scored, or keys the queries scored for [`maxsim`](https://www.unum.cloud/docs/usearch/mojo/executors.md#maxsim), before `wanted` cut any; above `pairs` means some lists were truncated.

Conforms to: `Deinitable`, `Movable`

## offsets

One more offset than queries, as Apache Arrow lays a ragged batch out.

```mojo
def offsets(ref self) -> Span[UInt, origin_of(self)]
```

Raises: [`Error`](https://www.unum.cloud/docs/usearch/mojo/errors.md#Error) with [`UNINITIALIZED`](https://www.unum.cloud/docs/usearch/mojo/errors.md#UNINITIALIZED) once a later call rewound the arena, or [`DEVICE`](https://www.unum.cloud/docs/usearch/mojo/errors.md#DEVICE) over VRAM.

## keys

Each pair's indexed entry, borrowed from the arena this result reads.

```mojo
def keys(ref self) -> Span[Key, origin_of(self)]
```

Raises: [`Error`](https://www.unum.cloud/docs/usearch/mojo/errors.md#Error) with [`UNINITIALIZED`](https://www.unum.cloud/docs/usearch/mojo/errors.md#UNINITIALIZED) once a later call rewound the arena, or [`DEVICE`](https://www.unum.cloud/docs/usearch/mojo/errors.md#DEVICE) over VRAM.

## scores

Each pair's product, positionally paired with `keys()`.

```mojo
def scores(ref self) -> Span[Float64, origin_of(self)]
```

Raises: [`Error`](https://www.unum.cloud/docs/usearch/mojo/errors.md#Error) with [`UNINITIALIZED`](https://www.unum.cloud/docs/usearch/mojo/errors.md#UNINITIALIZED) once a later call rewound the arena, or [`DEVICE`](https://www.unum.cloud/docs/usearch/mojo/errors.md#DEVICE) over VRAM.

## DenseMaxsimConfig

The knobs of `usearch_dense_maxsim_t`; zeroed or absent ones derive what the C interface derives.

```mojo
struct DenseMaxsimConfig[stats_origin: MutOrigin = MutUntrackedOrigin]
```

- `stats_origin` (comptime): The lent telemetry slot's origin, inferred where one is lent.

- `expansion_factor` `Int`: The breadth of the candidates; zero derives.
- `stats` `Optional[Pointer[DenseTraversalStats, stats_origin]]`: Receives this call's traversal telemetry, fully overwritten; absent skips reporting.

Conforms to: `Copyable`, `Deinitable`, `ImplicitlyCopyable`, `Movable`

## __init__

Names only the knobs that differ from the derived ones.

```mojo
def __init__(
    out self,
    *,
    expansion_factor: Int = Int(0),
    stats: Optional[Pointer[DenseTraversalStats, stats_origin]] = Optional()
)
```

- `expansion_factor`: The breadth of the candidates; zero derives.
- `stats`: Receives this call's traversal telemetry; absent skips reporting.

## DenseMultiplyConfig

The knobs of `usearch_dense_multiply_t`; zeroed or absent ones derive what the C interface derives.

```mojo
struct DenseMultiplyConfig[stats_origin: MutOrigin = MutUntrackedOrigin]
```

- `stats_origin` (comptime): The lent telemetry slot's origin, inferred where one is lent.

- `wanted` `Int`: Pairs kept per left row, the first ones its walk scored; zero keeps every pair.
- `expansion_factor` `Int`: The breadth of the candidates, which widens the emitted pattern; zero derives.
- `stats` `Optional[Pointer[DenseTraversalStats, stats_origin]]`: Receives this call's traversal telemetry, fully overwritten; absent skips reporting.

Conforms to: `Copyable`, `Deinitable`, `ImplicitlyCopyable`, `Movable`

## __init__

Names only the knobs that differ from the derived ones.

```mojo
def __init__(
    out self,
    *,
    wanted: Int = Int(0),
    expansion_factor: Int = Int(0),
    stats: Optional[Pointer[DenseTraversalStats, stats_origin]] = Optional()
)
```

- `wanted`: Pairs kept per left row, the first ones its walk scored; zero keeps every pair.
- `expansion_factor`: The breadth of the candidates, which widens the emitted pattern; zero derives.
- `stats`: Receives this call's traversal telemetry; absent skips reporting.

## DenseAttendConfig

The knobs of `usearch_dense_attend_t`; zeroed or absent ones derive what the C interface derives.

```mojo
struct DenseAttendConfig[carry_origin: MutOrigin = MutUntrackedOrigin, stats_origin: MutOrigin = MutUntrackedOrigin]
```

- `carry_origin` (comptime): The lent softmax states' origin, inferred where any are lent.
- `stats_origin` (comptime): The lent telemetry slot's origin, inferred where one is lent.

- `head_count` `Int`: The query heads sharing the index's key-value head; it must divide the rows, and zero means one.
- `carry` `Span[DenseSoftmaxState, carry_origin]`: The softmax states, one per query row; empty skips them.
- `expansion_factor` `Int`: The breadth of the candidates; zero derives. Wider candidates walk further, folding more of the tail.
- `score_scale` `Float32`: The logit scale, conventionally the inverse square root of the head width; zero derives it.
- `stats` `Optional[Pointer[DenseTraversalStats, stats_origin]]`: Receives this call's traversal telemetry, fully overwritten; absent skips reporting.

Conforms to: `Copyable`, `Deinitable`, `ImplicitlyCopyable`, `Movable`

## __init__

Names only the knobs that differ from the derived ones.

```mojo
def __init__(
    out self,
    *,
    head_count: Int = Int(0),
    carry: Span[DenseSoftmaxState, carry_origin] = Span(),
    expansion_factor: Int = Int(0),
    score_scale: Float32 = Float32("0"),
    stats: Optional[Pointer[DenseTraversalStats, stats_origin]] = Optional()
)
```

- `head_count`: The query heads sharing the index's key-value head; zero means one.
- `carry`: The softmax states, one per query row; empty skips them.
- `expansion_factor`: The breadth of the candidates; zero derives.
- `score_scale`: The logit scale; zero derives it from the index's frozen geometry.
- `stats`: Receives this call's traversal telemetry; absent skips reporting.