Crate fuel_graph 

fuel-graph

Lazy computation graph for Phase 6 of the fuel ML framework.

Role

Phase 6 transitions fuel from eager execution to a lazy computation graph with an autonomous router. This crate holds the minimal vocabulary that makes that transition possible:

• Op — a closed enum describing every operation that can appear in a graph node. New ops are added here and consumed by every backend.
• Graph — an arena of Nodes. Nodes are immutable once added and referenced by index. The arena grows; it never shrinks.
• NodeHandle — a cheaply-cloneable handle to a (graph, node_id) pair. Users build computations by calling methods on NodeHandle; each method appends a node to the underlying graph and returns a new handle.

Execution is deliberately not implemented here. A separate executor — fuel-dispatch’s PipelinedExecutor, dispatching to the per-backend kernels (fuel-cpu-backend, fuel-cuda-backend, fuel-vulkan-backend) — walks a Graph and produces concrete outputs. (The retired fuel-reference-backend textbook walker was the original executor; the CPU backend’s bit-stable kernels are the correctness oracle now.)

Scope of the MVP

This is the first landing of the graph types. It is deliberately minimal:

• Four float dtypes: f32, f64, bf16, f16. Integer dtypes will be added alongside the reference backend’s integer op coverage, not speculatively here.
• A small starter Op catalog: Const, Add, Mul, MatMul, Transpose, Relu, Sqr, Exp. More ops are added as validation tests for them land.
• Unfused backward autograd: NodeHandle::backward walks the forward graph in reverse, applies per-op gradient rules, and emits new graph nodes for the gradient of every leaf. Fused backward and symbolic graph rewriting are deferred to Phase 6d.
• No fusion, no planner. Those belong to later sub-phases of Phase 6.
• Thread-safe. The graph is wrapped in Arc<RwLock<_>> so that fuel_graph::NodeHandle — the lazy build handle — and any handle that embeds it are Send + Sync. Borrow access goes through read().unwrap() / write().unwrap().

Modules

grad

Symbolic autograd (Phase 6d Track 2).

jit

Kernel-seam JIT — the Fuel-side projection + structural matcher (kernel-seam-interop §5; fkc-fusion-patterns §3/§3a). The frozen grammar types (OpTag, OpAttrs, PatternNode) live in fuel_kernel_seam_types and are re-exported here; this module holds the two parts that need the graph: the Op -> OpTag projection op_to_tag and the structural matcher match_region (the declarative-fusion engine behind PatternKind::Declarative).

opt

Graph-level, backend-agnostic optimization passes.

registry

FusedOpRegistry — metadata side. Phase 7.6 step 1 (skeleton).

run

Run extraction + the transient lower_run view + the fewness gate.

runtime_fused

Runtime fused-op registration — the Tier-2 sidecar (docs/specs/runtime-fused-op-registration.md).

scan

unroll_scan: materialize a bounded crate::Op::Scan into real primitive nodes on demand. Used as (a) the FKC/Spec-B numeric oracle and (b) the fallback lowering for a backend without a scan kernel. NOT registered as anyone’s .decompose — Op::Scan is a bare primitive that stays terminal in the base map.

Structs

BranchBuilder

Accumulates the arms of an in-construction Op::Branch (phi/merge) node before finalize_branches validates them and emits the node. Created by Graph::open_branch.

GradMap

Map from forward-graph node IDs to the IDs of their accumulated backward-graph gradient nodes, returned by NodeHandle::backward.

Graph

The graph arena. Stores every node added during a computation-building session. Nodes are append-only and indexed by NodeId.

GraphId

Process-unique identifier for a Graph, minted monotonically by Graph::new. Exists so affinity diagnostics can name which graphs disagree; it is not a stable address, an index, or anything to persist.

Node

A single node in the graph: an operation and the IDs of its inputs. The node also caches its output shape and dtype so downstream builders can validate without walking back through the graph.

NodeHandle

A handle to a node in a shared graph. Cheap to clone. Carries the graph reference so builder methods have everything they need to append a new node.

NodeId

A node ID in the arena. Stable for the lifetime of the Graph.

NodeRemap

The old → new NodeId mapping produced by compact.

Run

A maximal straight-line, single-device op-sequence between two decision points — the dispatch / command-buffer-capture unit.

ScanPredicate

Phase-1 placeholder for Op::Scan’s early_exit field. The FIELD is defined now so the enum shape is final (one 03-ir MAJOR bump); the data-dependent early-exit MECHANISM is Phase 2. It is never Some on any live Phase-1 path; if a realize/lowering path sees Some, that path returns a clear Err (a surfaced Phase-2 gap), never a panic.

Enums

Op

The closed enum of operations a graph node can represent.

PadMode

Fill mode for Op::Pad. Only PadMode::Constant is implemented in the v1 cut; the other variants are accepted at the IR level so the enum is forward-stable, but the executor returns a clean error until they ship.

QuantType

Quantization block format for the QMatMul fused op (crate::registry::FusedOpParams::QMatMul). Matches the GGML/GGUF block layouts; each variant implies a fixed bytes-per-block and elements-per-block. Only variants for which a backend has a fused dequant-in-kernel matmul are currently exposed.

ScanEmit

What a Op::Scan emits. All stacks the per-step body_y over the bound (slot 0); Final returns only the final carry (slot 1). The op always produces the 2-slot bundle; emit selects the builder’s default projection. (Op::Reduce is Op::Scan { emit: Final } conceptually — no separate variant.)

ScanRole

Which body hole a Op::ScanPlaceholder stands in for. Carry is the per-step recurrent carry (always index 0 in v1’s single-carry model); Elem is the per-step slice of xs[index].

StorageClass

How a node’s storage is shared and how long it lives — its storage class ([03-ir §“Storage classes and sessions”]). A node is a structural fact and does not need storage to exist; when storage is attached, its class governs sharing and lifetime so one optimized graph can serve many concurrent sessions (weights shared, session state SessionId-keyed, activations per-realize scratch).

Constants

FEWNESS_THRESHOLD

The fewness-gate threshold: branch points must be at most ~5% of reachable nodes. Deliberate-fork branching stays this sparse; per-op branching does not.

Functions

branch_density

Branch density: the share of reachable nodes that are decision points (Op::Branch nodes), over root.

branch_density_multi

Multi-root variant of branch_density.

branches_in_topo_order

The reachable Op::Branch decision points over roots, in topological order of their reconverge_at merge points — the order the runtime route picker (Picker 2) resolves them in, so that coupled upstream decisions are committed before a downstream branch is reached (06-runtime §“Resolution order matters when decisions are coupled”).

build_rope_tables

Build a constant tensor of the given shape and dtype filled with value (expressed as f64 and converted to the target dtype). Used by backward rules that need a scalar-valued broadcast, for example MeanAll’s 1/n factor expressed as “divide by an n-filled const.”

build_rope_tables_with_inv_freq

build_rope_tables with the inverse frequencies supplied directly rather than derived from a single base.

compact

Required compaction of the append-only arena (PR-B4).

derive_view_output_layout

Compute the output Layout of a metadata-only view op from its input layout + the op variant. Returns Err if the op variant isn’t a view op (caller’s contract — typically guarded by Op::is_view_op).

device_alternating_order

Device-overlap topological reorder of a run list (Step E Phase C, PR C3 — the auto-overlap pass). Returns a permutation of 0..runs.len() (indices into runs) that is a valid topological reordering — every run still appears after all the runs it depends on — chosen so independent cross-device sub-DAGs DISPATCH so they overlap: the longest compute chunk of each device is enqueued/recorded BEFORE the host-blocking cross-device drain that feeds the join.

effective_roots

The effective root set for a run/density walk: the caller’s roots plus every Op::Branch node participating in the reachable computation. A finalized Op::Branch is typically orphaned — nothing downstream reads it (the reconverge_at node reads arm 0 directly, per PR-A1’s runnability invariant), so it would never be found by a plain forward walk. We therefore scan the whole arena and seed any Branch whose reconverge_at (or any arm exit) is already reachable; seeding it pulls its candidate arms into the walk. Run to a fixpoint so a Branch reached only through another Branch’s arm is also covered.

extract_runs

Extract the runs of the graph reachable from root, in topological order of their entries.

extract_runs_multi

Multi-root variant of extract_runs — the reachable set is the union over roots (mirrors topo_order_multi) plus the arms of every reachable Op::Branch. A Branch’s non-arm-0 arms are read only by the Branch node itself (arm 0 is the runnability fallback the reconverge_at node reads directly, per PR-A1), so seeding the walk from the Branch nodes pulls every candidate route into the reachable set.

infer_storage_class

The op-inferred storage class for a node, before any explicit override (see StorageClass and Graph::storage_class):

lower_picked_route

Route-aware lowering (Phase C PR-C1) — the generalization of lower_runs_arm0. The flat executable dispatch order that follows the chosen arm at each Op::Branch (per picked, defaulting to arm 0 for any branch the picker did not resolve) and skips every non-chosen arm’s run.

lower_picked_route_streaming

Streaming route-aware lowering (Step E Phase C, PR C1) — the incremental form of lower_picked_route. Instead of taking a fully-resolved PickedRoute up front, it walks the run partition in topological order and resolves each branch lazily, the first time the walk reaches one of its arm-entry runs, by calling resolve(branch). It emits only the chosen arm’s runs (skipping the non-chosen arms), exactly like lower_picked_route — but the arm decision happens at the frontier, not before the walk.

lower_run

The transient executable view of a single run: its ordered member NodeIds, ready to be recorded into a command buffer (Phase C).

lower_runs_arm0

The arm-0 single-route lowering (Phase A PR-A4, architect- approved temporary fix). The flat executable dispatch order that follows arm 0 through every Op::Branch — the pre-run, arm 0’s run, then the post-run — and skips every non-arm-0 arm’s run.

passes_fewness_gate

Whether the graph passes the fewness gate over root (branch density strictly below FEWNESS_THRESHOLD).

primitive_shape

The single source of truth for primitive-Op shape+dtype inference. Given a primitive Op (its params live on the variant) plus its input shapes and dtypes, returns the (output_shape, output_dtype) the op produces. Reads params off the Op, not off OpAttrs. Never panics: a malformed op/shape, a leaf/bookkeeping op with no pure inference, or a higher-order/basis-gap op is an honest Err.

topo_order

Compute the topological order of every node reachable from root.

topo_order_multi

Compute the topological order of every node reachable from ANY of the given roots. Each node appears in the output exactly once; the order still satisfies the dependency-before-dependent property, so walking it and caching results as you go computes every input before any node that depends on it.

walk_picked_route_streaming

The callback core of the streaming lowering — the form the compiler thread drives so resolution and emission genuinely interleave (the thread compiles + dispatches each chosen run as the walk reaches it, rather than first materializing a flat order). resolve(branch) yields the chosen arm index at the frontier; emit(&[NodeId]) receives each kept run’s members in topological order. lower_picked_route_streaming is the Vec-collecting wrapper over this (used by the byte-identity test); the executor’s compiler thread passes an emit that compile_one’s + sends each node.

Type Aliases

PickedRoute

A resolved route through the multi-path graph: for each Op::Branch decision point (keyed by the Branch node’s NodeId) the arm index the runtime route picker (Picker 2) chose. Arm i is the branch’s inputs[i] (arm-0 = inputs[0] = the cost-vector winner).

SharedGraph

A shared, mutable graph. Builders clone this cheaply and hand it to every derived tensor so that all tensors in one computation point to the same arena.