Exactness Is an Interface

I stopped treating scratch memory as permission to fail.

That sounds like a small API decision. It changes the architecture of a math library.

A conventional high-performance kernel often has an envelope. Inside the envelope it uses packed panels, vector instructions, tuned tiles, and a preferred accumulation type. Outside it, the implementation allocates, falls back to another path, loses precision, or refuses the shape.

The caller learns that envelope eventually. It leaks through errors, performance cliffs, target-specific output, and configuration knobs.

The design behind uor-matmul starts from a harder contract:

There is one mathematical answer. Memory and hardware only choose how the library reaches it.

That turns exactness into an interface property rather than an implementation detail.

One operation, not a family of approximations

For a matrix product, the mathematical core is familiar:

C_{ij} = \sum_{p=0}^{k-1} A_{ip} B_{pj}

Real libraries complicate that sentence immediately:

quantized weights need decoding
floating-point sums depend on reduction order
narrow integer accumulators can overflow
SIMD and scalar kernels may round differently
alpha and beta epilogues add another round of arithmetic
transposed and strided views introduce separate code paths
insufficient workspace can select a less capable algorithm

A library can expose those differences as separate behaviors, or it can absorb them under one result contract.

The uor-matmul model is:

flowchart LR
    A[Coded operand A] --> DA[Decode exactly]
    B[Coded operand B] --> DB[Decode exactly]
    DA --> X[Complete accumulation]
    DB --> X
    C0[Existing C, alpha, beta] --> X
    X --> E[Encode once]
    E --> C[Requested output type]

The codec is not part of the arithmetic. It is how an operand is represented before entering the arithmetic.

That distinction allows the same product to survive a change in weight tier, traversal, panel size, or substrate.

An optimization is not a fallback

I use a stricter definition than most libraries do:

An optimization changes how the answer is reached. A fallback changes the answer, the guarantee, or whether the operation is allowed to complete.

Suppose the caller offers a large scratch buffer. The library can pack panels and run a cache-friendly kernel.

Suppose the caller offers no scratch buffer. The library can stream through the same operation with less reuse.

Both should produce the same bytes.

flowchart TD
    O[One valid GEMM request] --> S{Scratch offered?}
    S -- suggested capacity --> K[Packed kernel]
    S -- small buffer --> B[Bounded panel traversal]
    S -- empty slice --> R[Streaming reference traversal]
    K --> X[Same exact accumulator]
    B --> X
    R --> X
    X --> Y[Same encoded bytes]

This changes the error surface.

“Not enough scratch” is no longer an error. Scratch is an offer. The library can accept the offer and choose a faster factorization, or decline it and continue through another valid factorization.

The caller does not negotiate correctness with the allocator.

Complete accumulation removes schedule from the result

Floating-point matrix multiplication is normally schedule-dependent.

The values

(a + b) + c

and

a + (b + c)

can round differently in IEEE floating point. A tiled kernel, a vector reduction, and a scalar loop may therefore return different last bits while each remains locally reasonable.

If the public contract is “behaves like this particular reduction schedule,” then portability means reproducing that schedule everywhere.

A different contract is possible:

decode each input into its exact mathematical value
accumulate the complete sum without intermediate rounding
apply the terminal expression
encode once into the requested output type

For GEMM with scaling, the target value is:

C'_{ij} = \alpha \left(\sum_{p=0}^{k-1} A_{ip}B_{pj}\right) + \beta C_{ij}

The encode operation happens after the complete expression, not after each multiply-add.

That makes the result independent of tile shape and reduction order:

\operatorname{encode}(S_{\pi_1}) = \operatorname{encode}(S_{\pi_2})

for any two valid traversals $\pi_1$ and $\pi_2$ of the same exact terms.

The implementation may still be difficult. The interface becomes simpler.

Integer overflow should not be a runtime policy

Integer kernels often expose an accumulator choice:

accumulate in the input width and wrap
accumulate in a wider fixed type
saturate
error past a depth limit
promote dynamically

That moves a proof obligation onto the caller. The caller has to know whether the selected width can hold the worst-case sum for this shape and value range.

A stronger approach derives the required accumulator width from the element type and the largest addressable reduction depth.

For signed values bounded by $B$ and reduction depth $k$ , a simple worst-case magnitude is:

|S| \le kB^2

The required bit width is therefore bounded by:

w \ge \left\lceil \log_2(kB^2 + 1) \right\rceil + 1

The extra bit carries sign.

If the library derives a complete accumulator from the machine’s representable maximum $k$ , then overflow becomes unreachable for every valid input the API can express. There is no runtime promotion ladder and no arbitrary k_max parameter.

The caller can still choose the final encoding:

wrapping into a fixed-width output
saturating into a fixed-width output
retaining a wider result

Those are output semantics, not emergency behavior inside the accumulation.

Coded operands should not create multiple truths

Quantized and compressed weights are often treated as a separate arithmetic world.

A weight code $c$ is decoded through some codec $d$ :

w = d(c)

The product is then:

S = \sum_p a_p d(c_p)

Changing the codec changes the represented weights, which can legitimately change the result. Changing the traversal used after decoding should not.

flowchart LR
    C1[Dense bytes] --> D1[Codec d1]
    C2[Packed codes] --> D2[Codec d2]
    C3[Table codes] --> D3[Codec d3]

    D1 --> M[One accumulation contract]
    D2 --> M
    D3 --> M

    M --> O[One requested output encoding]

The representation tier belongs in the object identity. Once the tier and bytes are fixed, every conforming factorization should agree on the answer.

This matters for content-addressed computation. A cached result is only portable if another machine can reproduce the same output bytes from the same addressed operands.

The API gets smaller when the proof gets stronger

A surprising effect of exactness is that the public error type can shrink.

A matrix product can fail because the requested mathematical object does not exist:

the inner dimensions do not conform
the output view aliases itself in a way that makes distinct coordinates the same cell

Those are real structural errors.

The following do not have to be errors:

the shape is large
the reduction is deep
scratch is absent
SIMD is unavailable
the host is wasm32
the inputs include the minimum representable integer
a preferred kernel cannot run

flowchart TD
    V[Construct matrix views] --> C{Product exists?}
    C -- no --> E[Structural error]
    C -- yes --> T[Build valid operation]
    T --> G[Execute chosen factorization]
    G --> O[Output]

The fallible step moves to construction. Once a valid product exists, execution does not need to negotiate an implementation envelope.

That is a better Rust API. It makes invalid states harder to express and keeps operational choices behind the abstraction that owns them.

`no_std` and zero allocation become part of the contract

It is easy to advertise a portable algorithm and quietly allocate in the wrapper.

If the library needs a Vec to pack panels, then the true contract is not no_std and zero allocation. It is “portable after an allocator is provided.”

A caller-owned scratch slice is a cleaner seam:

embedded systems can provide static memory
browsers can reuse a bounded buffer
servers can provide a large arena
an empty slice remains valid

The same call shape works across all of them.

Memory becomes explicit without becoming a correctness parameter.

The performance function may depend on offered scratch $s$ :

T = T(m,n,k,s,\text{host})

The result function should not:

R = R(A,B,C,\alpha,\beta)

That separation is the interface.

Exactness does not mean every path is fast

A streaming reference traversal can be much slower than a packed SIMD kernel. A complete floating-point accumulator can cost more than native fused multiply-add. A portable backend may be correct and still miss a latency target.

Exactness does not erase those tradeoffs.

It changes how they are presented.

The library can report which factorization ran. It can expose a workspace recommendation. It can publish benchmarks and route counters. It can let the caller force a path for measurement.

What it should not do is silently swap the meaning of the operation when the fast path is unavailable.

The caller can then make an informed product decision:

accept the portable exact path
provide more scratch
choose a different representation
batch differently
reject the operation at a higher policy layer

The math library does not need to counterfeit success with a weaker answer.

Deterministic bytes compose

The reason this matters beyond matrix multiplication is composition.

If a storage system names inputs by content, a runtime names the compiled graph, and the math kernel produces schedule-independent bytes, then the output can be addressed as a function of stable inputs rather than a particular machine run.

flowchart LR
    I[Addressed inputs] --> G[Addressed graph]
    G --> K[Exact kernel contract]
    I --> K
    K --> B[Deterministic output bytes]
    B --> A[Output address]
    A --> R[Reuse, audit, replay]

That is the bridge between numerical design and object infrastructure.

The exactness proof is not an academic accessory. It determines whether a result can move between hosts, survive a new tile schedule, and remain the same object.

A good abstraction lets hardware change without making the caller relearn the operation.

Exactness is how arithmetic earns that abstraction.