Fix the Match, Not the Solver: STITCH -- a Self-Supervised Compatibility Measure for Eroded Visual Puzzles

Nadav Alali; Ohad Ben-Shahar

cs.CVOct 9, 2026

Fix the Match, Not the Solver: STITCH -- a Self-Supervised Compatibility Measure for Eroded Visual Puzzles

Authors: Nadav Alali, Ohad Ben-Shahar

Organizations: Ben-Gurion University of the Negev, Israel

Abstract

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{\times}G$ patch tokens (precomputed). Tokens are projected ( $768\to 64$ ), passed through $L{=}2$ bidirectional cross-attention layers (4 heads), and scored via mean tokenwise cosine similarity ( $\sigma\in[-1,1]$ ). Only ${\sim}$ 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^{\circ}$ 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
$L_{1}$	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

{\leq}\,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{\times}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{\times}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 $\to$ B and A $\leftarrow$ 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 ( ${\sim}$ 86M) and architecture: the objective, not capacity, drives performance.

Variant	Params	MFLOPs	Top-1	Abs	Perf
Projection dimension $d_{\text{model}}$ ( $L{=}2$ )
$d_{\text{model}}{=}16$	${\sim}$ 25 K	3	77.2	.890	.742
$d_{\text{model}}{=}64^{\dagger}$	${\sim}$ 249 K	23	83.5	.964	.868
$d_{\text{model}}{=}128$	${\sim}$ 891 K	73	83.5	.965	.867
$d_{\text{model}}{=}d_{\text{ViT}}$ (no proj.)	${\sim}$ 28.3 M	2,139	80.1	.948	.834
Cross-attention layers $L$ ( $d_{\text{model}}{=}64$ )

Table 5: Head configuration ablation (JPwLEG-5, LP solver). Each block varies one hyperparameter with the other fixed at the default.

\dagger

marks the chosen configuration, the cheapest on the accuracy plateau.

Jigsaw Puzzle Solving

See all 8 papers

May 12, 2026

The Missing GAP: From Solving Square Jigsaw Puzzles to Handling Real World Archaeological Fragments

Jigsaw puzzle solving has been an increasingly popular task in the computer vision research community. Recent works have utilized cutting-edge architectures and computational approaches to reassemble groups of pieces into a coherent image, while achieving increasingly good results on well established datasets. However, most of these approaches share a common, restricting setting: operating solely on strictly square puzzle pieces. In this work, we introduce GAP, a set of novel jigsaw puzzles datasets containing synthetic, heavily eroded pieces of unrestricted shapes, generated by a learned distribution of real-world archaeological fragments. We also introduce PuzzleFlow, a novel ViT and Flow-Matching based framework for jigsaw puzzle solving, capable of handling complex puzzle pieces and demonstrating superior performance on GAP when compared to both classic and recent prominent works in this domain.

Ofir Itzhak Shahar, Gur Elkin, Ohad Ben-Shahar

Stein Faculty of Computer and Information Science Ben-Gurion University of the Negev, Israel

Jigsaw Puzzle Solving

Ask PDF

Jul 30, 2026

JigShape: Evaluating Visual-Geometric Reasoning in VLMs through Jigsaw Puzzles

Jigsaw puzzle solving requires jointly reasoning about visual content and geometric constraints, yet existing benchmarks use rectangular cuts that create ambiguous ground truth in texture-repeated regions. We introduce \ours{}, a benchmark with tab-and-blank interlocking pieces where geometric constraints provide strong local compatibility requirements that, combined with visual content, yield unambiguous ground truth. Across 95K instances at four grid densities (4

\times

4 to 16

\times

16), we find that zero-shot VLMs largely lack geometric reasoning: only one of five frontier models (GPT-5.5) exceeds random baseline on 4

\times

4 puzzles, while all others perform at chance level. While supervised fine-tuning achieves

>

97% on 4

\times

4, all models collapse on larger grids: GPT-5.5 drops from 70% to near-random on 8

\times

8, and even fine-tuned models fall below 5% on 12

\times

12. This ``scaling cliff'' suggests current architectures cannot maintain consistent constraint satisfaction as the number of pieces increases. \ours{} establishes scalable geometric reasoning as an open challenge for vision-language models.

Shawn Li, Wei Yang, Jike Zhong +11

University of Southern California · National University of Singapore · Adobe Research +3

VLM Evaluation Spatial Reasoning Benchmarks Visual Spatial Reasoning Visual Reasoning VLM Reasoning Jigsaw Puzzle Solving

Ask PDF

Sep 16, 2026

JigSync: Gauge-Resolved Synchronization for Jigsaw Reassembly under Unknown Piece Orientation

Square jigsaw reassembly requires recovering the spatial arrangement of shuffled fragments from their visual content and pairwise relationships. While recent studies have made substantial progress, existing benchmarks typically assume that all fragments are provided upright, reducing reassembly to a permutation problem. We study the generalized problem in which each fragment may also have gone through an unknown rotation. For this setting we establish a gauge-unobservability theorem: the minimum of the weighted least-squares objective is exactly invariant under a uniform global rotation of arbitrary magnitude, so no residual-based criterion can recover the global orientation. The theorem further identifies how the issue of global orientation can be resolved: an orientation anchor estimated from the content of a single fragment, lying outside its scope, suffices. To address the above, we propose JigSync, which attains 63.8% and 31.8% absolute accuracy (AA) on GAP-3 and GAP-5, respectively, the highest reported on both, while additionally recovering a rotation per piece that neither benchmark requires. We release JigSync, a degradation protocol that sweeps shape, erosion, photometry, grid size, and rotation independently.

Soham Pahari, Antik Aich Roy, Ujjwal Bhattacharya

Indian Statistical Institute, Kolkata

Jigsaw Puzzle Solving

Ask PDF

Abstract

Jigsaw Puzzle Solving

Explore similar work

The Missing GAP: From Solving Square Jigsaw Puzzles to Handling Real World Archaeological Fragments

JigShape: Evaluating Visual-Geometric Reasoning in VLMs through Jigsaw Puzzles

JigSync: Gauge-Resolved Synchronization for Jigsaw Reassembly under Unknown Piece Orientation