The Math Was Fine. My Buffer Wasn’t.

I ran into a strange failure: the operation was mathematically valid, the matrices conformed, and the output existed.

The library could still refuse to compute it because I had not supplied enough scratch memory.

I understood why. Fast matrix kernels like packed panels, tuned tiles, vector instructions, and temporary workspaces. The scratch buffer was how the caller helped the implementation reach the good path.

What bothered me was that the buffer had become permission for the operation itself.

The same multiplication could succeed on one machine, fall back to a different numerical behavior on another, or fail entirely in a constrained runtime—even though the mathematical request had not changed.

That was the point at which I stopped treating scratch memory as part of correctness.

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

There is one mathematical answer. Memory and hardware may change how the library reaches it, but not what the operation means.

The caller should not have to know the kernel’s envelope

A matrix product begins with a familiar equation:

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

A production implementation quickly adds conditions around it. Inputs may be quantized. Integer accumulators can overflow. Floating-point reductions depend on order. SIMD and scalar paths may round differently. Transposed and strided views create separate kernels. alpha and beta add an epilogue. A preferred path may need more workspace than the caller can provide.

Over time, those implementation details leak into the API. Users learn that one shape needs a particular accumulator, one target produces slightly different bits, and one memory configuration is “unsupported.”

The interface becomes a map of the current kernel collection.

I wanted the opposite direction: define the operation once, then make every valid execution path conform to it.

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 representation codec is allowed to determine which values the operands contain. It is not allowed to create a second arithmetic contract after decoding.

That separation is what lets a dense operand, packed code, or table-backed representation flow through one definition of the product.

Scratch is an offer, not a requirement

The practical test for this idea was simple: what should happen when the scratch slice is empty?

A conventional API may report “insufficient workspace.” Under the stricter contract, the operation still exists. The library should choose a traversal that uses less temporary memory, even if it is slower.

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]

A large buffer may enable packed panels and better cache reuse. A small one may reduce the tile size. An empty slice may force a streaming traversal.

Those are performance choices.

They should all arrive at the same encoded result.

This changes the meaning of the workspace recommendation. The library can tell the caller, “Give me this much memory for the preferred path.” The caller can decide whether the speed is worth the space. Neither side has to renegotiate whether the multiplication is valid.

That is a much cleaner boundary for no_std, browsers, embedded targets, and servers sharing one API.

Floating-point scheduling should not leak into identity

The hardest part is floating point.

In ordinary IEEE arithmetic:

$$(a + b) + c$$

may not equal:

$$a + (b + c)$$

A scalar loop, a tiled kernel, and a vector reduction can therefore return different final bits while each remains locally reasonable.

If the public contract is “reproduce this particular reduction schedule,” then every backend has to imitate that schedule forever. A new tile shape or SIMD width becomes a semantic change.

The alternative is to define the mathematical expression independently of the schedule:

1. decode each input into its exact represented value
2. accumulate the full sum without intermediate rounding
3. apply the complete terminal expression
4. encode once into the requested output type

For the scaled product:

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

the encoding occurs after the complete expression, not after every multiply-add.

Then two valid traversals $\pi_1$ and $\pi_2$ can differ internally while still satisfying:

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

That is expensive compared with simply exposing native reduction behavior. It also buys a much stronger interface: scheduling, tiling, and SIMD width stop changing the object the caller receives.

For content-addressed computation, those last bits are not cosmetic. Different bytes mean different outputs and different addresses.

Overflow should not become a surprise policy decision

Integer kernels have their own version of this leak.

A library may accumulate in the input width and wrap, promote to a larger fixed type, saturate, reject deep reductions, or switch strategies at runtime. The caller is then responsible for knowing whether a particular shape and value range fit the chosen accumulator.

A stronger design derives the accumulator width from the input type and the largest reduction depth the API can represent.

For signed values bounded by $B$ and reduction depth $k$:

$$|S| \le kB^2$$

A sufficient width satisfies:

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

The final bit carries sign.

If the implementation chooses a complete accumulator from the machine’s representable maximum $k$, intermediate overflow becomes unreachable for every valid request the interface can express.

The caller can still choose how the completed value is encoded—wrapping, saturating, or retaining a wider output. Those are explicit output semantics, not an emergency rule triggered halfway through accumulation.

That distinction makes review much easier. The arithmetic does not silently change because the reduction happened to be large.

Quantized inputs should not create a second truth

Compressed and quantized operands are often treated as a separate mathematical universe.

A code $c$ is decoded by a codec $d$:

$$w = d(c)$$

and the product becomes:

$$S = \sum_p a_p d(c_p)$$

Changing the codec changes the represented weights and can legitimately change the answer. Changing the traversal 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 input object’s identity. Once the bytes and codec are fixed, every conforming execution path should agree on the result.

This matters beyond numerical neatness. A cached output is only portable when another machine can reproduce the same bytes from the same addressed operands.

Stronger guarantees can make the API smaller

One surprising result of this approach is that the public error surface shrinks.

A product may genuinely be invalid because the inner dimensions do not conform or because an output view aliases itself in a way that makes distinct coordinates refer to the same cell.

Those are structural failures. The requested mathematical object does not exist under the supplied views.

The following do not have to be execution errors:

• the reduction is deep
• the shape is large
• scratch is absent
• SIMD is unavailable
• the target is wasm32
• a preferred kernel cannot run
• an input contains the minimum representable integer

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]

Fallibility moves toward construction. Once the library has a valid product, execution chooses a factorization rather than negotiating a new validity envelope.

That is a better Rust API because invalid states become harder to express and target-specific contingencies remain behind the abstraction that owns them.

no_std has to be true below the wrapper

It is easy to advertise portability while quietly allocating inside the convenient path.

If the implementation always creates a Vec to pack panels, then the real contract is not allocation-free. It is “works after somebody supplies an allocator.”

A caller-owned scratch slice makes the memory boundary explicit:

• an embedded target can use static storage
• a browser can reuse a bounded buffer
• a server can provide a large arena
• an empty slice remains valid

Performance may depend on the offered capacity $s$:

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

The result should not:

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

That separation is the interface I was looking for. Memory controls speed, not mathematical meaning.

Exactness does not make every path fast

The streaming path may be dramatically slower than a packed SIMD kernel. A complete floating-point accumulator may cost more than native fused multiply-add. A portable backend can be correct and still miss a product’s latency target.

The contract does not erase those tradeoffs. It makes them visible in the right place.

The library can report which path ran, recommend a workspace size, expose route counters, publish benchmarks, and let a caller force a factorization for measurement. A higher policy layer may decide that the slow exact path is unacceptable for a particular request.

Try the empty-buffer test

If you own a numerical API, run the same valid operation with:

• the suggested scratch size
• a small scratch buffer
• an empty scratch buffer
• a deliberately impossible input

The first three should change the route or the cost, not the mathematical result. The last one should fail for a reason that belongs to the operation—not because the fast kernel ran out of room.

What the math library should not do is counterfeit success with a weaker answer because the fast path was unavailable.

That gives the caller a real choice: provide more scratch, choose another representation, batch differently, accept the slower path, or reject the operation at the product boundary.

The arithmetic remains the same underneath each choice.

Why I care about the final bytes

This design started as a question about a scratch buffer. It ended up being about object identity.

If inputs are content-addressed, the graph is addressed, and the kernel’s output is independent of reduction schedule, then the result can be named as the output of stable objects rather than as “whatever this machine happened to produce.”

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 the larger object system.

The proof is not an academic ornament around a fast kernel. It determines whether a result can move between machines, survive a new tile schedule, and remain the same object.

The question I use now is simple: did an implementation choice change the speed, or did it change the operation I thought I had requested?

A good interface lets hardware and memory change without forcing the caller to learn a new mathematics. That is the deal I want from an exact kernel: make the implementation work harder before making the caller change the question.