LATTICE: Constraint-Directed Scheduling, Memory Planning, and Pipeline Refinement for NPUs

Fei Ding; Gang Li; Guangzhen Yao; Minnan Pei; Peng Xiao; Peng Zhang; Runhao Liu; You Li

LATTICE: Constraint-Directed Scheduling, Memory Planning, and Pipeline Refinement for NPUs

T0 review · 3 major / 5 minor · reviewed 2026-08-04 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read LATTICE claims that on NPUs, command order, memory plan, and timing form a one-way constraint chain, and that a three-stage compiler pipeline exploiting this chain beats all baselines in every evaluated comparison.

desk verdict A well-specified NPU compiler pipeline with a strong internal story, but the headline numbers live in an unvalidated replay world and need external anchoring before I'd trust them. read the letter →

arxiv 2607.17422 v3 pith:MKHWAKFR submitted 2026-07-19 cs.NI

Runhao Liu , Minnan Pei , Fei Ding , Guangzhen Yao , You Li , Peng Xiao , Gang Li , Peng Zhang This is my paper · ORCID

classification cs.NI

keywords NPUcompilermemoryplanningcommandschedulingspillingaddressreusecriticalpathrefinementexplicitlymanagedDAG

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper argues that compiling for NPUs is a directed dependency chain: the order of commands decides how long tensors overlap in memory, and the chosen memory layout then adds new ordering constraints (address reuse) that any later timing optimization must obey. It presents LATTICE, a deterministic pipeline with three stages—memory-pressure-aware scheduling, linear repackaging with spill planning, and plan-preserving critical-path refinement—that treats the materialized memory plan as a fixed contract. On six artifact command traces labeled as derived from a Da Vinci NPU flow, LATTICE is best or tied-best in all 24 workload–metric comparisons, cutting peak memory, DDR traffic, spill count, and makespan by double-digit percentages versus the best baseline per metric. A compiler that respects this contract, the paper shows, can recover pipeline overlap without invalidating the placement.

What carries the argument

The memory-plan contract Pmem = (x*, Lambda*, Ereuse) — the fixed physical layout, the spill/reload event stream, and the address-reuse ordering edges — carried as a first-class interface between scheduling, memory planning, and timing refinement. MPAS uses a lexicographic priority key (FREE-first, then allocation size, then downstream criticality) to pick a legal order; DLR performs deterministic best-fit placement with tier-aware victim selection; CPE extracts a critical chain and swaps adjacent same-pipeline commands only if the candidate preserves the contract and passes an independent verifier.

What would settle it

Run the same six command traces on the actual NPU (or a cycle-accurate simulator of it) and compare measured peak memory, DDR traffic, spill count, and makespan against LATTICE's modeled values. Concretely, the replay assumes L1=4096, UB=1024, L0A/B=256, L0C=512 trace units and a 150+2q_e transfer cost; if real hardware timestamps differ materially from the modeled finish times, or if the trace storage units do not correspond to real tensor sizes, the claimed reductions collapse.

Watch

Extended reading notes

Core claim

The central discovery is that a legal topological order of an NPU command DAG is not memory-neutral: different legal orders change logical peaks and spill behavior by up to 81%, and a memory-feasible plan is not scheduling-free, because physical address reuse creates ordering constraints absent from the input DAG (ignoring them produced 36,399 ownership violations). LATTICE therefore coordinates three deterministic stages: MPAS reorders commands to reshape lifetime overlap before address binding; DLR binds lifetimes to tiered addresses, emits spill/reload events, and derives reuse constraints; and CPE refines only timing edges that preserve the fixed layout and event stream. Every accepted s

Load-bearing premise

All 24 wins and the 12.1% timing gain come from a deterministic replay with hand-set buffer capacities and transfer costs; if those constants do not match real NPU behavior, the results are an artifact of the model rather than the hardware.

Editorial extensions

If this is right

If LATTICE is right, compilers for explicitly managed NPU memory should export memory-planning decisions as execution semantics, not as internal details.
Legal order selection is itself a memory optimization: a compiler can reduce peak pressure before placement, so future schedulers should treat ordering as a first-class memory knob.
Plan-induced address-reuse edges are load-bearing: any post-placement timing pass must preserve them or redo planning, validating an Ignore-and-verify error check as a standard guard.
Deterministic, verifiable three-stage pipelines can replace monolithic search: the bounded CPE pass recovers 12.1% makespan without changing memory metrics, so the memory plan can be a stable contract across compiler passes.
Independent verification makes each accepted schedule executable by construction, which should be the bar for NPU compiler output.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If the contract idea transfers, register allocation in GPUs and software pipelining of DSPs—both explicitly managed and both with reuse-based anti-dependencies—could adopt a similar plan-preserving refinement stage.
The 12.1% CPE gain suggests that, once real address-reuse constraints are respected, most remaining pipeline serialization in the planner's order is removable; a testable prediction is that this slack grows with the number of decoupled engines.
A direct test: feed the same six traces to the paper's MPAS+DLR plan but relax only non-reuse resource edges on real hardware; the makespan should match LATTICE's modeled value if the replay model's transfer constants are accurate.
The paper's order-sensitivity range (21.2–81.2% in logical peak) implies that any NPU compiler that freezes a stable topological order is leaving a large memory optimization on the table; quantifying this range for production traces would tell how much headroom remains.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

First things first: there is a real idea here. The MPAS→DLR→CPE pipeline treats the materialized memory plan as a contract that constrains later scheduling, and the memory-plan contract concept (x, Λ, E_reuse) is a genuinely useful way to separate concerns between order, placement, and timing. The two observations are not novel in the abstract—every compiler person knows ordering affects memory and address reuse creates dependencies—but the paper gives them a clean formalization and builds a deterministic pipeline on top. That's valuable.

What the paper does well: the replay logic is coherent, the ablations are well-designed (Ignore/Freeze/CPE is a nice controlled way to show the reuse constraints are necessary, not decorative), and the reported numbers are internally consistent with the stated formulas. The paper also honestly discloses the scope: trace provenance is not encoded, and the replay model abstracts away dynamic arrivals, batching, and sub-buffer phases. I appreciate that they don't overclaim the hardware connection in the body—until the abstract, where 'achieves' and 'best in all 24' silently carry a hardware claim.

The soft spot is the one the stress-test note flags, and it's load-bearing. The four headline reductions (18.3%, 20.4%, 14.1%, 16.3%) and the CPE 12.1% gain are produced by a deterministic replay with hand-set capacities (4096, 1024, 256, 256, 512), transfer cost 150+2q_e, and earliest-feasible timing. There is no calibration of these constants against any real Da Vinci NPU, no hardware measurement, and no comparison to a production compiler (so the baselines are author-instantiated inside the same backend). The 'independent verifier' checks that the generated plan is internally memory-valid and timing-valid—it doesn't verify that the replay world matches the chip. If the per-buffer sizes or transfer latencies are off by a realistic factor, the workload–metric ranking could change. That makes the empirical contribution a set of model artifacts until proven otherwise.

I want to be fair: the internal verification is solid, the deterministic design is a plus for reproducibility, and the paper explicitly limits its stated scope to replay semantics. But the abstract's language is stronger than the evidence. The fix is straightforward: release the artifact (traces, implementation, verifier, commit hash) and add at least one real-hardware or production-flow comparison, even on a subset. Then the 24-cell claim becomes checkable.

Who is this for? Researchers working on NPU compiler memory management, especially on explicitly managed scratchpads. The formalization of plan-induced constraints is worth reading now. It deserves a serious referee—send it out, but ask for a calibration experiment before acceptance.

Referee Report

3 major / 5 minor

Summary. The paper proposes LATTICE, a deterministic three-stage compiler pipeline for NPU command DAGs with explicitly managed on-chip memories. Stage 1 (MPAS) reorders commands to reshape buffer lifetimes before address binding; Stage 2 (DLR) performs tiered placement and spill/reload planning, exporting a memory-plan contract that includes physical-address reuse constraints; Stage 3 (CPE) refines pipeline timing while preserving that contract. The evaluation uses six artifact-provided command traces labeled as derived from a Da Vinci NPU flow, comparing LATTICE against four baseline policies under a deterministic replay model. The paper reports best or tied-best results in all 24 workload-metric comparisons and headline reductions of 18.3% / 20.4% / 14.1% / 16.3% in peak memory, extra DDR traffic, spill count, and modeled makespan, plus a 12.1% CPE gain over Freeze. Diagnostics with Ignore/Freeze/CPE variants are used to argue that plan-induced reuse constraints are necessary for valid execution.

Significance. If accepted at face value, the paper makes a useful conceptual contribution: it formalizes the directed dependency between command ordering, memory-plan materialization, and downstream timing refinement, and it demonstrates a concrete deterministic pipeline with internal verification. The Ignore/Freeze/CPE counterfactual is a strong and falsifiable way to show that physical-address reuse constraints are not merely bookkeeping but are required for executable schedules. The paper also ships a reproducible replay methodology with machine-checked consistency: both replay layers verify the final plans, and the reported tables are internally consistent with the stated formulas. The main weakness is external: the replay model's constants and trace provenance are uncalibrated, so the headline numerical claims are not yet anchored to real Da Vinci NPU behavior. This is a correctness-risk concern that must be addressed before the end-to-end superiority claim can be accepted.

major comments (3)

[Section V-A and Table II] The central empirical claim—'best or tied-best in all 24 workload–metric comparisons' and the headline reductions of 18.3% / 20.4% / 14.1% / 16.3%—is computed entirely inside a deterministic replay whose parameters are hand-set and uncalibrated. Table II fixes L1=4096, UB=1024, L0A/B=256, L0C=512 trace units, and transfer cost 150+2q_e. Section V-A explicitly states that source network, tensor shapes, chip SKU, and compiler version are not encoded. Since all methods are evaluated under the same replay, relative policy comparisons may be internally meaningful, but absolute metrics (DDR traffic, spill counts, makespan in modeled cycles) and even some relative rankings can be sensitive to these constants. The abstract and conclusion should either report these as 'within the LATTICE replay model' or provide a sensitivity analysis (e.g., sweep capacities and transfer cost and show rankings ar
[Section V-A (baseline fidelity)] The 'best evaluated external method' comparison in Figure 6(b) relies on command-level policy instantiations of HMCOS, COSMA, MAGIS, and EDA. The manuscript states that these instantiations preserve the 'defining policy decisions' from the published methods, but no evidence is provided that the implemented instantiations reproduce the original methods' behavior on these traces. If an instantiation is weaker than the original, the reported relative improvements over 'best external' are inflated. The authors should validate the instantiations against original code or published results, or explicitly restrict claims to 'LATTICE versus our instantiations.' This is load-bearing because the 24-comparison claim depends on the baselines being faithful.
[Section V-A (trace provenance)] The paper relies on six artifact-provided command DAGs 'labeled as derived from a Da Vinci NPU flow,' but the provenance details are absent. This would be a minor issue if the paper's claims were limited to algorithmic insights on synthetic traces; however, the abstract and conclusion assert end-to-end gains. Because the traces' origin and preprocessing are not specified, readers cannot assess how representative the workloads are. Please add provenance documentation (even if anonymized) or further soften the empirical claims to be conditional on the artifact.

minor comments (5)

[Abstract and passim] The phrase 'by 18.3% lower' is grammatically awkward; use 'by 18.3%' or '18.3% lower.' This appears in the abstract and Section VI-A.
[Section V-A, last paragraph] The sentence 'Because the source network, tensor shapes, chip SKU, and compiler version are not encoded, we report the artifact’s native storage units and modeled cycles' is an honest limitation, but it should be surfaced prominently in the abstract or introduction, not only in the evaluation setup.
[Section VI-A] The claim 'LATTICE is best or tied-best in all 24 workload–metric comparisons' is central, yet no table enumerates all 24 cells. Consider adding a supplemental table with per-workload metric values for every method so the claim is directly checkable.
[Section IV-E] The verifier is described as 'independent,' but it is part of the same artifact. This is not a flaw, but 'independent' may overstate the separation; consider 'separate' or 'automated' to avoid implying it is a third-party verifier.
[Section V-B] The transfer cost model '150 + 2q_e' is introduced without motivation. Even if calibration is out of scope, a brief justification or citation would help readers understand why this form was chosen.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the reported gains are empirical outcomes of a disclosed deterministic replay model, not quantities forced by construction or by self-citation.

full rationale

LATTICE's derivation chain is algorithmic rather than definitional. MPAS selects a legal order via Eq. (17), DLR constructs a fixed memory-plan contract via Eqs. (18)-(22), and CPE accepts only strict makespan improvements that preserve the Stage-2 plan; none of the reported reductions (18.3%, 20.4%, 14.1%, 16.3%, 12.1%) is defined as the value of a fitted parameter or as a renamed input. The replay constants in Table II (capacities, transfer cost 150+2q_e) are disclosed, fixed, and described in trace units and modeled cycles, so no quantity is fit to make the 24 comparisons come out favorably. The 'independent verifier' checks internal consistency of the replayed plan—ownership handoffs, capacity, acyclicity, spill/reload validity—rather than assuming LATTICE's superiority; the Ignore/Freeze diagnostics demonstrate necessity of reuse constraints by producing 36,399 verifier-detected violations. The central weakness is external fidelity: Section V-A explicitly states that source network, tensor shapes, chip SKU, and compiler version are not encoded, and the model abstracts dynamic arrivals, continuous batching, and multi-core compilation. That is a correctness/fairness threat about whether 'modeled makespan' and 'extra DDR traffic' reflect real Da Vinci NPU behavior, not a circularity in the derivation. Baselines are reimplemented in a common backend; this raises comparability concerns, but the comparison is still an empirical evaluation under a stated common model rather than an equivalence-by-construction. Load-bearing arguments do not reduce to self-citation: the paper's own prior work appears only in related-work context (e.g., [35]) and no uniqueness theorem or external authority is imported to force the design choice.

Assumptions & free parameters 4 free parameters · 5 assumptions · 0 invented entities

The central results rest on an unvalidated architecture/replay model and six non-public traces; the paper itself discloses the main abstractions (Section V-B), but the network/SKU/compiler provenance is withheld. No physical constants or new entities are introduced; the memory-plan contract is a software abstraction, not an evidence-bearing entity.

free parameters (4)

On-chip tier capacities = L1=4096, UB=1024, L0A=256, L0B=256, L0C=512 (trace units)
Table II. These constants define how often spills and reuse constraints occur; no hardware SKU is identified, so they are arbitrary inputs to the replay model.
Spill/reload added-transfer cost = 150 + 2 q_e modeled cycles (MTE3/MTE2)
Table II. This hand-chosen latency directly affects the makespan and the DDR-traffic/spill tradeoff reported as headline results.
CPE search envelope = 2 passes, at most 4 candidate moves, one deterministic seed
Table II/Algorithm 3. The 12.1% makespan gain over Freeze is measured under this bounded local-search budget; a larger or differently chosen budget could change the result.
Trace-provided command latencies c_v = not listed; artifact-provided modeled cycles
Section V-A. Latencies are part of the artifact and are not tied to a measured SKU; they are accepted as inputs to the replay and directly shape makespan comparisons.

assumptions (5)

domain assumption The target NPU behaves as a Da Vinci-derived core with explicitly managed L1/UB/L0A/B/C buffers, MTE2 for loads/reloads, MTE3 for stores/spills, single-issue pipelines, and unrestricted cross-pipeline overlap.
Invoked throughout Section II-A and Table II; all plan-induced constraints and timing results are defined relative to this model.
domain assumption The six artifact traces are representative of Da Vinci NPU command streams.
Section V-A says traces are 'artifact-provided' and 'labeled as derived' but source network, tensor shapes, chip SKU, and compiler version are not encoded; representativeness is assumed for all claims.
domain assumption Earliest-feasible timing over the augmented graph is a valid performance proxy.
Section V-B defines modeled makespan this way and explicitly abstracts dynamic arrivals, continuous batching, sub-buffer access phases, and multi-core effects; the headline numbers inherit this abstraction.
domain assumption The input E_prec DAG captures all precedence needed for correct command execution.
Section III-A defines the problem over the given DAG; if the artifact omitted hardware-level ordering constraints, MPAS/CPE could produce invalid orders that the replay would miss.
standard math Kahn traversal with lexicographic priority produces a topological order, and DLR's best-fit placement maintains disjoint address intervals while pinned operands are protected.
Algorithm 1 and Section IV-C rely on standard data-structure facts for the correctness claims.

how reviews work

0 comments

Cite this review

Pith. "Pith review of LATTICE: Constraint-Directed Scheduling, Memory Planning, and Pipeline Refinement for NPUs." pith.science (2026). https://pith.science/paper/MKHWAKFR

@misc{pith2026260717422,
  author       = {Pith},
  title        = {Pith review of: LATTICE: Constraint-Directed Scheduling, Memory Planning, and Pipeline Refinement for NPUs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MKHWAKFR}},
  note         = {Machine review of arXiv:2607.17422}
}

read the original abstract

General-purpose NPUs execute fine-grained command DAGs across heterogeneous compute and memory-transfer engines backed by finite, explicitly managed on-chip memories. This execution model creates a directed dependency between scheduling and memory planning: different legal topological orders induce different lifetime overlap, placement opportunities, and spill behavior, while a materialized layout introduces physical-address reuse constraints absent from the input precedence DAG. Command order therefore shapes the feasible memory plan, and the realized plan in turn defines the legal space for subsequent timing refinement. We present LATTICE, a deterministic constraint-directed compiler pipeline. Memory-Pressure-Aware Topological Scheduling reshapes lifetime geometry before address binding; Deterministic Linear Repackaging materializes tiered placement, spill/reload events, and plan-induced reuse constraints; and Critical Path Enhancement recovers pipeline parallelism while preserving the selected memory plan. Every accepted schedule passes independent memory and timing verification. Across six artifact-provided command traces labeled as derived from a Da Vinci NPU flow, LATTICE achieves the best or tied-best result in all 24 evaluated workload-metric comparisons. Relative to the best evaluated baseline for each workload and metric, it reduces peak memory, extra DDR traffic, spill count, and modeled makespan by 18.3% lower, 20.4% lower, 14.1% lower, and 16.3% lower, respectively. Plan-preserving CPE further reduces makespan by 12.1% over Freeze while leaving placement and memory traffic unchanged, establishing the static memory plan as a verifiable scheduling contract between memory planning and pipeline optimization.