open question: should RTR pattern matcher report high-dim patterns that fail to merge, and let the rewriter signal failure?

Summary

The current ReshapeTransposeReshapePattern (RTR) uses a merged-shape check as a detection gate — patterns that cannot be merged to lower dimensionality are silently excluded from match results. This is correct for rewrite correctness, but it hides high-dim RTR patterns that exist in the model graph yet cannot be rewritten. The open question is whether it would be better to surface these unwritable patterns and have the pattern rewriter explicitly signal failure rather than filtering them silently at match time.

Origin: PR #463 review comment on modelkit/pattern/transpose_patterns.py:306

Context

PR #463 introduced a should_apply_rewrite() gate on ReshapeTransposeReshapePattern: after PatternMatcher.match() runs, patterns where _compute_merged_transpose() produces no dimensional change (i.e., the Transpose shape is already at low dimensionality, or cannot be merged further) are dropped before being reported. This correctly prevents false-positive detections on already-optimized models.

The merged-shape check in _compute_merged_transpose() (transpose_patterns.py:390) works by grouping consecutive input dimensions whose output positions also stay consecutive. If a high-dim RTR pattern (e.g., 6D Transpose) cannot collapse to a lower-dim equivalent, the merge result is identical to the input — and the pattern is excluded.

The problem: high-dim RTR patterns that are genuinely present in the graph but happen to be unmergeable are now invisible to both:

• The static analyzer (it never reports them as detected subgraph patterns)
• The optimizer pipeline (it never attempts a rewrite, so there is no failure feedback)

This means models with such patterns silently pass analysis without any indication that a potentially important pattern was detected but deemed unoptimizable.

Current State

• modelkit/pattern/transpose_patterns.py:390 — _compute_merged_transpose() computes the minimum-dim equivalent; if result dimension == input dimension, the RTR instance is "no-op mergeable"
• modelkit/static_analyzer/core/pattern_extractor.py — calls pattern.should_apply_rewrite(match) and drops matches returning False entirely
• The graph optimizer's RewritePipe only receives patterns that passed should_apply_rewrite() — it has no mechanism to receive or report "detected but cannot rewrite" patterns
• There is no current mechanism for the rewriter to signal back to the analyzer that a matched pattern was attempted but failed

Desired State (open — needs design decision)

Two design directions to evaluate:

Option A — Match all, rewrite some, report failures

• PatternMatcher reports all topological RTR matches (high-dim and low-dim)
• should_apply_rewrite() classification moves to the rewriter, not the detector
• The static analyzer receives the full match list; patterns where rewrite is inapplicable appear as "detected, rewrite not applicable" rather than being silently dropped
• The rewriter returns a structured result: RewriteResult(success=False, reason="cannot_merge_to_lower_dim") which the optimizer pipeline can log or surface to the user

Option B — Keep current gate, add explicit reporting for unwritable patterns

• Keep should_apply_rewrite() at detection time (no regression to current behavior)
• Add a separate pass that collects "present but unmergeable" RTR patterns and emits them as a distinct result category (e.g., PatternDetectionResult(status="unoptimizable", reason=...))
• These appear in the build report / optimization report as informational items

Questions to Resolve

1. Is there a real user-facing scenario where an unmerge-able high-dim RTR pattern is actually relevant diagnostic information? (i.e., would a user or the optimizer benefit from knowing it's there but cannot be rewritten?)
2. Does Option A risk breaking the static analyzer's "no false positives" guarantee if the rewriter result is asynchronous with detection?
3. What is the expected frequency of truly-unmergeable high-dim RTR patterns in production models? If rare, Option B may be sufficient and lower risk.
4. If rewriter failure signaling is added, what is the right feedback path — should it flow back to the optimizer pipeline, the build report (#487), or both?

Acceptance Criteria

(To be determined once design direction is chosen)

• Design decision documented (Option A, Option B, or alternative)
• If Option A: rewriter returns structured RewriteResult with success + reason; static analyzer surfaces "detected, not rewritable" entries separately from "detected and rewritten"
• If Option B: a distinct result category exists for present-but-unmergeable RTR patterns; appears in build/optimization reports
• Either option: no regression to existing "already-optimized model no false positives" behavior from PR #463
• Tests: add a test case with a high-dim RTR pattern that cannot be merged; verify it is reported correctly under the chosen design
• All existing tests pass

Technical Notes

• _compute_merged_transpose() (transpose_patterns.py:390) is the key function — its return value is the ground truth for "can this RTR be rewritten to lower dim?"
• The caller in should_apply_rewrite() currently uses: merged_shape == transpose_shape (no change → return False)
• A structured rewrite failure result would need a new return type from RewritePipe — currently the pipe either applies rewrites or skips silently
• Coordinate with build report (#487) and optimization report (#488) — "detected but not rewritable" patterns are exactly the kind of information those reports should surface

Related Files

• modelkit/pattern/transpose_patterns.py:390 — _compute_merged_transpose()
• modelkit/static_analyzer/core/pattern_extractor.py — should_apply_rewrite() gate
• modelkit/pattern/base.py — Pattern base class, SkeletonMatchResult

References

• PR #463 — "fix: Add rewrite support in SA" (origin of this question)
• #487 — Build Report (surface of "not rewritable" patterns)
• #488 — Optimization Report (optimizer feedback)