Unlike the clean and pixel-aligned complete pieces of standard jigsaw benchmarks, real-world puzzle fragments lose their boundary regions to erosion, destroying the signal that classical compatibility measures (CMs) rely on. We first re-establish, via oracle experiments, that the CM, not the solver, is the performance bottleneck: with a perfect CM, even a simple greedy solver achieves perfect reconstruction. This motivates STITCH, a self-supervised CM that sidesteps missing boundaries by comparing frozen ViT patch tokens from piece interiors via a lightweight cross-attention head (~249K trainable parameters), trained without manual annotation. Plugged into unchanged compatibility-based solvers, STITCH reaches .992/.954 Abs/Perf on JPwLEG-5 (+.629 Perf over the best prior method), nearly saturating the benchmark. On a new ImageNet 7x7 benchmark, it outperforms all alternatives, including inpaint-then-match pipelines built on modern generative models. Importantly, performance remains robust across erosion levels and generalizes to puzzles with over 40% missing pieces without retraining. Trained on the recent GAP datasets of irregular, heavily eroded fragments, the same CM recipe enables compatibility-based solvers to surpass recent learning-based solvers on GAP-3 and GAP-5. Since this leap in performance is achieved by a pluggable CM module, the takeaway is clear: fix the match, not the solver.
Figures & tables
Figure 1: Architecture overview. Both pieces are canonicalized so facing edges align to a fixed position (Sec. 4.2 ). A frozen MAE ViT-B/16 extracts G×G patch tokens (precomputed). Tokens are projected ( 768→64 ), passed through L=2 bidirectional cross-attention layers (4 heads), and scored via mean tokenwise cosine similarity ( σ∈[−1,1] ). Only ∼ 249 K parameters are trained.
Figure 2: Canonicalization by relative position. A piece (center) is transformed according to where it sits relative to its partner: left – identity; right – horizontal flip; above – transpose; below – 90∘ CW rotation. Each transform brings the piece’s facing edge to its rightmost column.
Figure 3: Qualitative results on JPwLEG (STITCH + genetic solver). JPwLEG-3 ( left , 48 px gap) and JPwLEG-5 ( right , 12 px gap). Red frames mark misplaced pieces, which occur only on near-uniform dark pieces ( left ) and repetitive stained-glass panels ( right ), where interior content is interchangeable.
Figure 4: Oracle ceiling (JPwLEG-5). Abs (top) and Perf (bottom) for each solver with its original CM (gray), STITCH (green), and a perfect oracle (gold). All solvers reach 1.00 with the oracle. STITCH closes most of the gap.
Greedy
Genetic
LP
CM
Top-1
Abs
Perf
Abs
Perf
Abs
Perf
SSD
38.5
.43
.09
.43
.13
.47
.16
L1
42.5
.46
.11
.50
.23
.54
.26
PBC
36.6
.41
.08
.40
.11
.44
.13
MGC
38.1
.48
.12
.45
.16
.48
.19
Edge2Vec
50.8
.56
.17
.70
.44
.74
.49
Table 1: Averaged over 2 000 test puzzles and 5 runs, SEM ≤0.01 . All STITCH-vs-baseline gaps are significant at p<.001 under paired, corrected two-sided tests (Supp).
JPwLEG-3
JPwLEG-5
Method
Abs
Perf
Abs
Perf
Deepzzle ( 2020 )
.738
.523
.219
.000
SD 2 RL ( 2023a )
.816
.597
.403
.051
PDN-GA ( 2023b )
.813
.582
.443
.061
JPDVT ( 2024 )
.713
–
.041
.000
ERL-MPP ( 2025b )
–
–
.527
.186
Table 2: Comparison with prior work on JPwLEG. Best in bold , second-best underlined , unavailable entries – . All prior methods are learning-based solvers. Ours is a modular CM plugged into a genetic solver ( Sholomon, David, and Netanyahu 2013 ) .
Figure 5: Erosion robustness (ImageNet 7×7 ). Top-1 vs. erosion (px). Learned CMs (STITCH, Edge2Vec) trained once at 4 px. STITCH (red) remains nearly flat while all baselines degrade sharply.
MGC
Edge2Vec
STITCH
k
Abs
Perf
Abs
Perf
Abs
Perf
0
.42
.12
.91
.78
.97
.91
5
.27
.00
.85
.39
.97
.82
10
.21
.00
.76
.10
.94
.66
15
.18
.00
.66
.03
.89
.54
20
.18
.00
.62
.01
.87
.53
Table 3: Missing pieces (ImageNet 7×7 , LP solver, 4 px erosion). k pieces removed at test time, CMs not retrained. Best per row in bold .
Figure 6: Qualitative results on GAP (STITCH + genetic solver). GAP-3 ( left ) and GAP-5 ( right ). Red frames mark misplaced fragments. All others are placed correctly despite the irregular, heavily eroded shapes.
GAP-3
GAP-5
Method
Abs
Perf
Abs
Perf
JigsawGAN ( 2021 )
.453
.046
.180
.000
DiffAssemble ( 2024 )
.505
.164
.219
.000
JPDVT ( 2024 )
.112
.000
.039
.000
PuzLM ( 2025 )
.148
.000
.078
.000
FCViT ( 2025 )
.607
.252
.204
.000
Table 4: Irregular fragments (GAP-3/5). STITCH is trained on GAP ( 2026 ) and plugged into unchanged solvers. Baselines as originally published, with two accuracy measures matching Abs and Perf. Best in bold , second-best underlined , – unavailable. Greedy-solver, Top-1, and neighbor accuracy in the Supp.
Figure 7: Cross-attention on JPwLEG-5. Outer columns show anchor A and candidate B, inner columns the attention between them (A → B and A ← B), aggregated over all heads and query tokens in the last layer. Top ( green ): on pieces with rich pictorial content, attention concentrates on the facing edges and STITCH ranks B first. Bottom ( red ): on near-textureless pieces, attention finds no structure to key on and the true neighbor is missed.
Figure 8: Backbone comparison (JPwLEG-5, LP solver). Six frozen backbones positioned by solver-level Perf ( x ) and CM-level Top-1 ( y ), with area proportional to parameter count. MAE ViT-B/16 dominates both axes despite matching DINOv2 , CLIP , and supervised ViT-B/16 in size ( ∼ 86M) and architecture: the objective, not capacity, drives performance.
Variant
Params
MFLOPs
Top-1
Abs
Perf
Projection dimension dmodel ( L=2 )
dmodel=16
∼ 25 K
3
77.2
.890
.742
dmodel=64†
∼ 249 K
23
83.5
.964
.868
dmodel=128
∼ 891 K
73
83.5
.965
.867
dmodel=dViT (no proj.)
∼ 28.3 M
2,139
80.1
.948
.834
Cross-attention layers L ( dmodel=64 )
Table 5: Head configuration ablation (JPwLEG-5, LP solver). Each block varies one hyperparameter with the other fixed at the default. † marks the chosen configuration, the cheapest on the accuracy plateau.