ONNX Runtime PR #32038: Why Overlapping Fusion Candidates Produced an Invalid Graph


ONNX Runtime PR #32038 fixes a graph transformer that could accept a second fusion candidate containing nodes already claimed by an earlier fusion.

The first fusion had not physically removed its nodes yet. It had only placed them in a deferred removal list.

A later traversal could therefore see those same nodes, assign one of them a different role, construct another fused operator from the wrong inputs, and schedule one node for removal twice.

The local pattern still looked recognizable. Its ownership state made it invalid.

The intended fusion pattern

MatMulIntegerToFloatFusion looks for a quantized matrix multiplication followed by conversion and scaling.

A simplified form is:

A ───────────────┐
                 │
B ────────→ MatMulInteger
                 │
                 ▼
                Cast ──────────────┐
                                   │
A scale ──┐                        │
          ├─→ Mul ─────────────→ Mul ──→ output
B scale ──┘

The first Mul combines the two scale values.

The second Mul applies that scale product to the floating-point result of MatMulInteger → Cast.

The transformer replaces this subgraph with one contrib operator:

A
B
A scale
B scale
zero points, if present
bias, if present
        │
        ▼
MatMulIntegerToFloat
        │
        ▼
      output

For a candidate to be valid, its Mul parent must be the node that combines the two scale inputs.

A parent being a Mul is not sufficient by itself.

The regression graph created an accidental second match

The added test constructs two quantized matrix multiplication paths.

The first one has the expected scale multiplication:

scale_product =
    Mul(scale_1, scale_2)

first_result =
    Mul(
        Cast(MatMulInteger_1),
        scale_product
    )

A second path then consumes that result:

output =
    Mul(
        Cast(MatMulInteger_2),
        first_result
    )

The final Mul has:

one Cast parent

and

one Mul parent

That is enough to resemble the fusion pattern structurally.

The problem is the identity of its Mul parent.

first_result is not a multiplication of two scale values. It is the fully scaled result of the first quantized matrix multiplication.

Its inputs are:

Cast(MatMulInteger_1)

and

scale_product

Those are not the two scale inputs required by the second fusion.

Deferred deletion left claimed nodes visible

The old transformer walked a topological list and collected every successfully matched node in nodes_to_remove.

It did not remove those nodes after each fusion.

The general sequence was:

find candidate
        ↓
create fused node
        ↓
append old nodes to removal list
        ↓
continue scanning original graph
        ↓
remove all scheduled nodes

Deferring deletion can simplify graph traversal. The list being traversed does not change underneath the current loop.

It also creates an obligation: once a candidate has been accepted, its nodes must no longer be available to another candidate in the same pass.

The old implementation did not record that reservation separately.

After the first fusion was created, these nodes were scheduled for deletion:

MatMulInteger_1
Cast_1
scale_product
first_result

They still existed in the graph while the loop examined the final Mul.

The final Mul found:

Cast_2
→ valid-looking MatMulInteger parent

first_result
→ valid-looking Mul parent

The matcher proceeded even though first_result already belonged to the first accepted fusion.

The second fused node received the wrong scale inputs

When creating MatMulIntegerToFloat, the transformer took the two inputs of mul_node_right and used them as the fused operator’s scale inputs.

For a normal match, that is correct:

mul_node_right inputs:
    A scale
    B scale

For the overlapping match, mul_node_right was first_result.

Its inputs were instead:

Cast_1 output

scale_product output

The second fused operator would therefore be constructed as though those two values were its independent scale inputs.

The first candidate had changed the logical meaning of that node before the node was physically removed. The second candidate relied only on the still-visible graph shape.

The resulting transformation also placed first_result in the removal list twice:

first fusion:
    first_result is its outer Mul

second fusion:
    first_result is its scale-side Mul

The same graph node had acquired two incompatible roles.

The fix reserves nodes as soon as a fusion is accepted

The merged implementation adds two collections:

InlinedVector<NodeIndex> nodes_to_remove;
InlinedHashSet<NodeIndex> node_indices_to_remove;

The vector retains the eventual removal sequence.

The set represents ownership during candidate discovery.

Before accepting another candidate, the transformer checks its four central nodes:

if (node_indices_to_remove.contains(matmulinteger_node.Index()) ||
    node_indices_to_remove.contains(cast_node.Index()) ||
    node_indices_to_remove.contains(mul_node_right.Index()) ||
    node_indices_to_remove.contains(mul_node.Index())) {
  continue;
}

A candidate sharing any of those nodes with an earlier accepted fusion is skipped.

For the regression graph:

first fusion accepted
        ↓
first_result index enters claimed-node set
        ↓
second candidate identifies first_result as mul_node_right
        ↓
set membership check succeeds
        ↓
second fusion skipped

The final Mul remains in the graph and consumes the output of the first fused operator.

That is the valid transformed form:

MatMulIntegerToFloat_1
        │
        ▼
   first_result
        │
        ├──────────────┐
                       ▼
MatMulInteger_2 → Cast_2 → Mul → output

One valid pattern is fused. The overlapping candidate remains unfused.

Node indices also make deferred removal safer

The previous removal vector stored references to Node objects:

InlinedVector<std::reference_wrapper<Node>>

That representation assumes every referenced node remains alive until its entry is processed.

A duplicated entry breaks that assumption.

Once the first entry removes the node, another stored reference to the same object may no longer refer to live node storage.

The patch stores stable node identities instead:

InlinedVector<NodeIndex>

At deletion time, it resolves each identity through the graph:

Node* node = graph.GetNode(node_index);
ORT_ENFORCE(
    node != nullptr,
    "Node scheduled for removal was already removed.");

This does not replace the overlap check. It protects a different boundary.

The set prevents legitimate control flow from scheduling overlapping removals.

The index lookup turns any future violation of that invariant into an explicit failure instead of continuing through an invalid stored reference.

What the regression test establishes

The new test builds the chained overlap directly.

Before transformation, it contains:

2 MatMulInteger nodes
2 Cast nodes
3 Mul nodes

After transformation, it expects:

1 MatMulIntegerToFloat
1 remaining MatMulInteger
1 remaining Cast
1 remaining Mul

Those counts establish both sides of the intended decision.

The first candidate must still fuse.

The second candidate must remain intact rather than becoming a corrupted second fusion.

The graph transformer framework also resolves the graph after a modification. A transformation that leaves invalid producer-consumer relationships therefore cannot pass solely because the operator counts look plausible.

What the test does not establish

The added test uses the structural transformer helper rather than a baseline-versus-optimized inference comparison.

It does not execute both graphs and compare their numerical outputs.

It also does not build the optional bias form:

scaled result
        ↓
       Add
        ↓
      output

Nor does it explicitly exercise provider-specific logic such as the DML large-tensor branch.

These are limits on the regression matrix, not evidence of a defect in the merged change.

The test reproduces the overlap that motivated the patch, confirms that only the independent candidate is fused, and requires the resulting graph to resolve successfully.

The ownership rule behind the fix

A graph rewrite does more than recognize shapes.

Once it accepts a match, it claims the participating nodes and promises to replace their combined behavior with a new node.

Physical deletion can occur later. Exclusive ownership cannot.

The restored sequence is:

find local candidate
        ↓
check that none of its nodes are already claimed
        ↓
create replacement
        ↓
reserve every replaced node immediately
        ↓
continue scanning
        ↓
remove reserved nodes by identity

A deferred graph rewrite must reserve matched nodes when the rewrite is accepted, not when deletion eventually occurs.

That is the overlap boundary repaired by ONNX Runtime PR #32038.

Sources

https://github.com/microsoft/onnxruntime/pull/32038

https://github.com/microsoft/onnxruntime/commit/0e3af8f08c8f12a2d35d2070cfdf11e424b9f959

https://github.com/microsoft/onnxruntime/blob/b1f76d586aaf545ccb92198934fa49553a806a1c/onnxruntime/core/optimizer/matmul_integer_to_float.cc

https://github.com/microsoft/onnxruntime/blob/0e3af8f08c8f12a2d35d2070cfdf11e424b9f959/onnxruntime/core/optimizer/matmul_integer_to_float.cc

https://github.com/microsoft/onnxruntime/blob/0e3af8f08c8f12a2d35d2070cfdf11e424b9f959/onnxruntime/test/optimizer/graph_transform_test.cc

https://github.com/microsoft/onnxruntime/blob/0e3af8f08c8f12a2d35d2070cfdf11e424b9f959/onnxruntime/test/unittest_util/graph_transform_test_builder.cc

https://github.com/microsoft/onnxruntime/blob/0e3af8f08c8f12a2d35d2070cfdf11e424b9f959/onnxru

Popular posts from this blog

AMD Is Trying to Turn Kernel Diversity Into One Software Asset

The first broad integration was rolled back, but the direction of the software stack is difficult to ignore The GPU software race is often described as a contest over who can write the fastest kernel. That is only part of the problem. A company may have several teams capable of producing high-performance matrix-multiplication kernels. Some may work through template libraries. Others may use compiler-generated code, handwritten assembly, or model-specific optimization stacks. The existence of those kernels does not automatically create one coherent platform. They still need to be: discovered validated matched to the correct problem given the correct arguments launched through a stable runtime and delivered through a reliable software package Recent public code changes inside AMD’s software ecosystem showed an attempt to connect these layers more directly. The central idea was to allow hipBLASLt’s GEMM selection system to choose kernels created by multiple internal kernel technologi...
Read more

PyTorch #188031 — Why Did Forward Use 64-Bit Indexing While Backward Still Used uint32_t?

PyTorch Spatial Softmax, Part 1 of 3 — An asymmetric indexing contract and the patch that aligned it A recent PyTorch change fixed a 64-bit indexing problem in the spatial softmax backward path. The bug was not in the softmax formula itself. It was in the width of the integer used to calculate memory locations. For the same large tensor, the forward path already selected either 32-bit or 64-bit indexing based on the input size. One backward path, however, continued to calculate sizes, strides, and offsets using uint32_t . That created a possible split in behavior: Forward → 64-bit address calculation → accesses the intended elements Backward → 32-bit address calculation → offset wraparound → gradients read from or written to different locations A tensor could therefore complete the forward pass correctly while the corresponding backward kernel could no longer represent every address in that tensor. The changes described in PyTorch #188031 were later landed in PyTorch’s main branch. S...
Read more

NVIDIA CUTLASS #3017 — Why load() and store() Mapped the Same Tile Coordinate to Different Addresses

CUTLASS #3017, Part 1 of 3 — An asymmetry in address calculation and the patch that fixed it In February 2026, while reading through NVIDIA CUTLASS’s RegularTileIterator<layout::PitchLinear> implementation, I noticed an odd asymmetry. load() and store() accepted the same tile coordinate, yet they calculated the corresponding memory address differently. The difference was a single line. load() divided the contiguous coordinate by kElementsPerAccess . store() did not. When each memory access handled only one element, the difference remained invisible. But in vectorized paths, where a single access handles multiple elements, the same logical tile coordinate could resolve to two different physical addresses. I reported the issue as CUTLASS Issue #3017. The missing division was later added to store() in PR #3049. CUTLASS and tile iterators CUTLASS is NVIDIA’s open-source library for high-performance CUDA linear algebra. It provides C++ template abstractions for composing GPU ope...
Read more