Consolidate remaining v2 design issues around semiring backend contracts

[shinaoka]

cc @tensor4all-meta

Summary

This issue consolidates the remaining design-v2 questions after the recent placement cleanup. The main unresolved theme is how custom semiring backends should relate to primitive vocabulary, trait contracts, and general execution engines.

Remaining issues

1. Custom semiring backend minimum contract is still inconsistent

Two different contracts are described today.

• primitive-catalog.md treats tensor-structural operations like permute, reshape, broadcast, and diagonal as tensor-layer views / metadata transforms, so the backend-facing strict minimum is close to BatchedGemm + ReduceSum (with diagonal-related behavior depending on whether diagonal stays in the tensor layer).
• tenferro-internal-design.md instead puts Transpose, Reshape, and BroadcastInDim into SemiringOpKind / SemiringOps, which makes them part of the required semiring contract.

These are materially different obligations for custom backends. The design needs one source of truth.

2. Compile-cache identity rules are still inconsistent

computegraph-design.md says compiled programs are cached using GlobalValKey-based structure, which includes InputKey.
tensor-api-pseudocode.md says the cache key is based on normalized graph topology and should ignore concrete InputKey / DiffPassId values so repeated differentiate calls hit the same cache entry.

This needs an explicit decision:

• either tenferro owns a second normalized compile-cache layer above computegraph
• or computegraph itself changes its cache contract

Without that, higher-order AD cache behavior is underspecified.

3. StdTensorOp is not fully a single source of truth yet

There are still mismatches between the vocabulary and the lowering tables. Examples:

• direct StdTensorOp::Add / Mul / DotGeneral style descriptions vs StdTensorOp::Semiring(SemiringOpKind)
• Cholesky described as custom-call in one place and direct stablehlo.cholesky in another
• LuFullPivot / StdTensorOp::CustomCall shown in later sections even though they are not present in the main enum definition

The enum definition, lowering table, and extensibility story should be unified.

Current idea

A cleaner direction is to separate Tenferro primitives from the traits that execute them.

Proposed layering

1. Primitive descriptors

   • Keep a primitive vocabulary crate/module that only describes operations and their planning/execution descriptors.
   • Examples: semiring core descriptors, scalar descriptors, linalg descriptors, transfer descriptors.

2. Executor traits

   • Define small family-specific traits that know how to plan/execute those descriptors.
   • Backends implement these traits, not a single giant monolithic backend trait.

3. General engines

   • Build generic interpreters / engines that consume primitive descriptors and dispatch through the executor traits.
   • Einsum becomes one such engine. Standard tensor execution could become another.

4. Backend implementations

   • CPU / CUDA / custom algebra backends only implement the trait families they actually support.

Why this looks promising

This is close to what origin/main already does for semiring execution:

• Semiring defines the algebra
• TensorSemiringCore<Alg> is the required semiring execution contract
• TensorSemiringFastPath<Alg> is the optional optimization contract
• EinsumBackend<Alg> is just the composition of those traits
• tenferro-einsum is the general engine that interprets einsum plans through those traits

That pattern is attractive because backend authors implement capabilities, while high-level algorithms live in reusable engines.

Design questions to resolve next

• Should design-v2 explicitly adopt the origin/main descriptor + plan/execute pattern as the reference model?
• For custom semiring backends, what is the true required core: only contraction/reduction primitives, or also tensor-structural view-like ops?
• Should diagonal / trace behavior stay in the semiring core, or be normalized away earlier?
• Should the standard backend story also move from Backend<Op> toward capability-family traits plus one or more general engines?

Suggested resolution order

1. Fix the custom semiring minimum contract
2. Fix compile-cache identity semantics
3. Make StdTensorOp + lowering tables a single source of truth
4. Then decide how far the primitive-descriptor / executor-trait / engine split should become the v2 architectural pattern

[shinaoka]

Resolution summary (from brainstorming session 2026-04-04)

All four issues have been resolved. Detailed architecture is captured in #21.

1. Custom semiring backend minimum contract ✅

Decision: batched_gemm + reduce_sum is the minimum backend contract. Transpose/Reshape/BroadcastInDim are handled by common infrastructure (algebra-independent).

• SemiringOpKind retains Transpose/Reshape/BroadcastInDim as graph vocabulary (needed by einsum builder for Fragment construction)
• But custom algebra backends never execute these — they are handled by the common infrastructure in the StableHLO→low-level IR compilation and execution pipeline
• Operand trait is pure algebra: add, mul, dot_general, reduce_sum
• Structural ops (transpose, reshape, broadcast) are provided by a separate TensorData trait with generic implementations — custom algebra authors don't implement these
• v1's TensorSemiringCore + TensorSemiringFastPath pattern is reused

2. Compile-cache identity ✅

Decision: tenferro Engine owns a normalized compile-cache layer above computegraph.

• computegraph-rs cache stays GlobalValKey-based (used for CSE/dedup, needs InputKey distinction) — unchanged, AD-agnostic preserved
• tenferro Engine adds a second cache that normalizes away concrete InputKey/DiffPassId values, replacing them with anonymous slot indices
• Cache key = graph topology (op types + connectivity), not concrete input identity
• Two graphs with identical structure but different DiffPassId → cache hit

3. StdTensorOp single source of truth ✅

Decision: StdTensorOp is flat (no Semiring(SemiringOpKind) wrapping), mirrors StableHLO 1:1.

Specific fixes:

• StdTensorOp::Add / Mul / DotGeneral as direct flat variants (not wrapped in SemiringOpKind)
• StdTensorOp implements SemiringOps trait by mapping flat variants to trait methods
• SemiringOpKind exists only inside SemiringOp<T> (custom algebra), separate from StdTensorOp
• Cholesky → stablehlo.cholesky (direct op, exists in StableHLO spec)
• Svd, Qr, Eigh, Solve → CustomCall (not in StableHLO spec)
• LuFullPivot → CustomCall("getc2") (no dedicated variant)
• StdTensorOp::CustomCall { target, n_inputs, n_outputs } added to enum
• Source of truth chain: primitive-catalog.md → StdTensorOp enum → StableHLO lowering table

4. Descriptor + plan/execute as v2 pattern ✅

Decision: Yes. v1's family-trait pattern (SemiringCore + SemiringFastPath) is the v2 reference model, sitting behind a generic execution engine that interprets a low-level IR.

See #21 for the full 2-level IR architecture.