Batched Evaluation Architecture

This page documents the runtime machinery behind the user-facing batching guide: how a sequant::BatchPolicy decision is actually carried out when numerically evaluating a forest: the evaluation trees of several equations (e.g. all residual equations of a coupled-cluster method) passed to sequant::evaluate() together. It assumes the vocabulary established there (mode, batch, slice, contracted/external role, persistent/volatile, peak memory) and the cost-model architecture in Cost Model and Single-Term Optimization; neither is redefined here.

Two execution strategies

Numeric evaluation is reached through sequant::evaluate(), dispatched by BatchPolicy::scheduler (sequant::BatchScheduler) onto one of two strategies:

• ``forest_descent`` (the default): each equation in a forest is evaluated independently, one tree at a time, by the original tree-walking evaluator. Batching is realized by a custom evaluator (sequant::make_batched_custom_evaluator(), or the BatchPolicy-driven adapter sequant::make_evaluator()) installed on the node cache: when the walk reaches a node whose contracted or external mode is batchable, the custom evaluator re-enters the subtree once per slice and accumulates/scatters the partial results, instead of letting a single one-shot contraction run.

• ``ordered``: the entire forest is fused into one DAG and driven by a single, explicitly-scheduled, table-driven walk (SeQuant/core/eval/ordered_executor.hpp). Loop identity and the cell table make compatible value forms and batch loops shareable across equations, with one production per shared form at its scheduled scope.

Forest descent can already reuse ordinary cached intermediates across equations. The ordered scheduler additionally fuses compatible batch loops across the forest; the per-tree custom evaluator does not perform that fusion. Both strategies produce the same numeric result for the same BatchPolicy; the ordered scheduling pipeline is described below.

forest_descent builds no schedule or cell table. Its custom evaluator hoists values to the enclosing scope where they are reused and slices each fetched value to the current batch.

Array layout and mode frames

The runtime’s array-mode list is EvalExpr::canon_indices(). indices_annot() presents proto-free outer modes first, then proto-carrying inner composites, separated by a semicolon. A leaf evaluator must return an array in the requesting node’s canonical layout.

Labels pair operand modes within one contraction. Decisions across occurrences use positions in the canonical layout instead, because two occurrences can have different labels or permutations. A composite index such as a<i,j> contributes the array mode a over a proto-dependent range; slicing a plain i mode does not also slice that composite mode.

The ordered pipeline

Evaluating a forest under BatchScheduler::ordered proceeds through four stages, each with its own SeQuant header:

1. Loop identity (SeQuant/core/eval/dag_scope.hpp, peak_profile.hpp, lifetime_mask.hpp). Before anything is scheduled, every physical batch loop implied by the cost model’s decision needs a stable identity distinct from where it happens to sit in any one tree — the same auxiliary-index loop may appear inside several different equations. LoopKey provides that identity; compute_dag_boulevard walks the whole forest once to assign it, and from it derives value identity: two occurrences (one use-site of a node, in one equation) are recognized as the same shareable value exactly when they agree on which loop instances they are sliced by.

2. Schedule construction (ordered_schedule.hpp). build_ordered_schedule lowers the loop-identity facts into an OrderedSchedule: a tree of nested ScopeBlock objects (one per physical batch loop), each holding the build/assemble steps that belong at that nesting level. Two decisions happen here that a hand-written batched loop would otherwise have to get right by hand: escape placement — deciding, for each value, whether it is purely local to one loop iteration (built fresh every time, needing no special handling) or must be accumulated/scattered across iterations into something that outlives the loop — and pass splitting — when a producer/consumer ordering conflict would otherwise make a value depend on a not-yet-finished batch of itself, the affected values are separated into ordered sub-passes within the same loop nest rather than left to race.

3. The cell table (cell_table.hpp, cell_table_builder.hpp). Rather than let the executor infer what to read from where while it runs, the schedule is first lowered into an explicit table: one entry per distinct value-form actually resident at some scope, and one entry per read of it, naming exactly which scope produces it and who consumes it. A validator checks this table for internal consistency before any tensor operation runs, so a scheduling bug is caught as a fast, deterministic failure rather than a wrong number arrived at after an expensive run.

4. The executor (ordered_executor.hpp). Walks the cell table exactly as written: every operand of every operation is resolved through a table lookup, not by re-deriving it from the tree. This is a deliberate design choice — the executor performs no scheduling decisions of its own, only realizes ones the earlier stages already made, which keeps its own logic small relative to the scheduling machinery it depends on.

Loop identity and value identity

A value is an identity in the fused DAG, an occurrence is a use of it by a consumer at a particular operand position, and a cell is one form of a value resident at one scope. Structural node identity alone cannot identify a value under batching: identical expressions sliced by different physical loops must remain distinct.

LoopKey identifies a physical loop. An index space only constrains which loops can match: two loops over the same space can be distinct and have different combine roles.

compute_dag_boulevard identifies loops before values. It merges occurrence positions that must share a loop, both along parent/child edges and across trees, and refuses a merge that would join two positions of one occurrence, mix contracted and external loops, put a reader of a complete value inside the reduction it awaits, or violate nesting constraints. A value’s key then combines its structural identity with the loops slicing or reducing it and its operands’ keys; without slicing, it is just the structural identity.

The optimizer records on each node the modes it slices and the loops it opens; these are shared by every occurrence of the node. Two occurrences can still be sliced differently in different equations, so the ordered scheduler also records each occurrence’s home: the enclosing loops that slice its own result modes (occurrence_home()). Value identity tells apart occurrences with different homes. Forest descent instead uses the intersection over occurrences (sliced_modes()), and its per-batch scratch shares a node only among occurrences that put the batch mode, the batched external modes and the axes of the enclosing loops at the same result positions: two equal nodes binding different physical indices to an enclosing loop’s axis hold different slices.

Placement, escapes, and pass splits

The builder realizes a chain per loop instance, honoring the recorded outer/inner constraints. Loops that never co-occur on a home-sliced value form independent nests. Dependency edges from occurrences topologically order builds and nested blocks; external requirements of an inner block propagate outward to the level that can satisfy them.

The ordered driver’s optional mode_order ranks index spaces from outermost to innermost. It only breaks ties left by the recorded nesting constraints; there is no cost search over nest orders.

Legality classifies a value relative to each loop as LoopLocal, Reduction, or LoopCarried. A reduction is a property of the value’s own node. The other two are decided per occurrence, against the recorded loop instances: an occurrence whose enclosing loops include the instance that slices the value’s position reads it in lockstep, per batch; one they do not reads it assembled (OccurrenceRole). A value with a lockstep occurrence is LoopLocal and a BuildStep in its home block; if it also has assembled readers it escapes from that block as well, and those readers follow the block in their own block’s order. A value with no lockstep occurrence is LoopCarried. A reduction or loop-carried value escapes through the block’s outputs: AccumulateSum for reduction, AccumulateScatter for carried result modes. Multiple escapes form a chain, with raw production at the deepest site and forwarding at shallower sites. An escape can skip an interposed loop on which the value is invariant.

A consumer requiring a completed loop-carried value, or a completed reduction while it is inside that reduction’s loop, or a loop-local value assembled over a loop instance while it is itself produced inside that instance, moves to a later pass.

Passes must also leave every block level orderable. The steps of a level are its builds and the blocks nested in it (at root: the root builds and each nest’s pass blocks), and a block stands for everything produced inside it, so the steps of one pass can need each other in a cycle although no value does: a build that reads what the inner block completes while a reader of that build sits inside the block, or two nests whose blocks each read a completed value of the other. The pass levels are refined until no such cycle is left: each round finds the cycles among the steps of one pass and moves the consumers on them to a later pass than the operands they read there.

A nest containing multiple passes becomes ordered sibling blocks, run in pass order; a later pass reads the earlier pass’s assembled value. The nest’s inner levels are ordered once, with all passes present, and then forked per pass, so only dependencies between two steps of one pass order them. Values needed across a split are materialized, not recomputed. Unsupported cases raise sequant::Exception.

Cell forms, reads, and lifetimes

A TableCell is one form of a value: the scope it lives at, the positions it is sliced on, the loops over which it is still a partial sum, and how it is produced (leaf, build, or sum/scatter assembly). A consumer reads the deepest form whose residency encloses it.

Each operand occurrence is a separate Read, so a consumer using one value twice reads it twice. A read names its source cell and how to slice it. A cell invariant on an enclosing loop is built on the first batch and reused until a loop it depends on advances. Only unbound, non-volatile values at the persistent-to-volatile frontier persist across evaluations.

How long a cell lives is not counted; it is read off the schedule (ReleasePlan, release_plan.hpp). A cell lives for one epoch, from its production until the loop that re-produces it advances. Within an epoch that loop’s block runs its steps and then its outputs once, and every read of the cell happens at one of those positions, directly or somewhere inside the nested block that is the step there. The cell is released when the last position holding a read of it is done, whether that step ran, was skipped, or replayed its reads once per batch of loops nested in it. The schedule’s results are kept for the caller.

validate_cell_table checks the table for consistency before any tensor operation runs: every read has a visible source of the right form, assemblies close the right partial or scattered form, no cell resident inside a loop goes unread, and no value is built twice at one scope. It does not check array ranges; the dry-run backend does.

Executing the table

The executor resolves each declared read against the cell registry and applies the read’s slices. A read the release plan marks as the last use of a non-persistent cell, made once per epoch of that cell, takes the value over, which makes in-place accumulation safe. Each batch clears the cells bound to that loop, executes the block’s steps, and folds outputs into their assembly cells (summing partials, or scattering blocks into the destination); after each step and each output it releases the cells whose last reader that position holds. When the loop closes, the assembled cell becomes visible to the next link of its escape chain. Persistent cells are published to the cache’s PersistentValueStore and restored from it on later evaluations, in which case their productions are skipped.

A correctness caveat for sparse backends

Some numeric backends (TiledArray in particular) screen individual result tiles against a norm bound (typically a Cauchy-Schwarz bound) computed for the full contraction. Evaluating only a fraction of a batched reduction and comparing each partial result against that same full-contraction bound can wrongly discard tiles that would have survived the complete sum — silently dropping a real contribution. The executor therefore accepts a scope guard factory (instantiated once per batch loop, released via RAII as nested loops close) whose job is to scale such a screening threshold down for the duration of each batched block, so a partial sum is screened against a bound appropriate to its own, smaller size rather than the full one. Any backend/executor integration that batches over a screened or otherwise sparsity-aware backend must supply a correct scope-guard factory; omitting it does not fail loudly — it silently returns a slightly-wrong numeric result.

Dry runs and diagnostics

The sizing backend in SeQuant/core/eval/backends/dryrun/ stores descriptors instead of tensors and checks shared-label ranges on every operation. sequant::eval::dryrun::meter() drives the same evaluate entry point as a real run and reports the realized peak and work, checking the runtime’s scheduling and accounting rather than the optimizer’s per-product estimate. It assumes real double-precision data. Every slice, permutation and phase change it makes is priced as a copy, also where a backend (TiledArray, for one) keeps a lazy view that holds no memory of its own, so for batched schedules the metered peak is a conservative estimate of what such a backend keeps resident. It is not a bound on process memory either way: transients inside a production and the backend’s own temporaries are not modeled.

SeQuant/core/eval/ordered_dump.hpp provides environment-gated dumps of each pipeline stage; Evaluation Trace Analysis explains how to read evaluation traces.

Schedule documents

A schedule document (SeQuant/core/eval/schedule_document.hpp) is one JSON document that describes a batched schedule for inspection and for steering later runs. It has a pinnable roots section, which records the choices the optimizer made for each root and can be fed back to reproduce them, a read-only dag section, which describes the ordered schedule built from those choices, and an optional run section, which carries what an evaluation measured. The optimizer side lives in SeQuant/core/optimize/schedule_pin.hpp: opt::schedule::record_root captures a root, and a PinSession or RecordSession set on OptimizeOptions::pinned or OptimizeOptions::recording replays pinned choices or collects the recorded ones during optimization. Recording or pinning a Sum makes the optimized Sum carry canonical dummy labels (each summand is optimized on its canonicalized clone). A term’s key is its canonical form, so it is independent of the dummy labels and of the factor order the caller used, but not of the external index labels: a root must be spelled with the same external labels on every run that pins it. fingerprint_of summarizes the binarized forest a document was recorded for, and check_fingerprint, run after binarization and before the DAG stages, throws when a loaded document’s fingerprint no longer matches the live forest’s. eval::schedule::record_dag (SeQuant/core/eval/schedule_dag_record.hpp) builds the dag section from a rich schedule, its legality and the volatility predicate the evaluation runs with (a value’s persistent is the cell table’s own flag); given a cost model it also prices every value (its home-relative slab and its full size). The ordered entry points in ordered_executor.hpp take an optional RunRecord* out-parameter that is filled with the run section: per value, the bytes the backend measured for what each production, leaf fetch or seeding left in the value’s cell. size_audit_table sets the two side by side, per value and as a peak: both peaks are the same liveness sweep over the dag section, one priced by the model and one by the run, so a mis-sized value or a peak the model misses shows up as a ratio rather than as a number without a reference. The sequant-schedule command-line tool validates, diffs and renders documents.

Current scope

The ordered pipeline does not: choose the fusion of loop instances optimally where producer/consumer connectivity allows more than one valid choice (a valid, but not necessarily optimal, choice is recorded); reorder loop nesting across index spaces for cost (the realized nesting honors recorded constraints and the caller’s mode_order ranking); make a cost-aware choice between materializing and recomputing a value across a forced pass split (a pass split always materializes); or share a transient value across multiple reads (an unrecorded intermediate is recomputed inside every production tree that needs it). A scatter assembly writes along one position of its output; one needing several positions throws. None of this affects correctness — every one of these is a possible future efficiency improvement, not a currently-missing correctness guarantee — but they bound how much benefit ordered scheduling can currently realize relative to a hypothetical, fully cost-optimal fusion.