PuzLM: Solving Jigsaw Puzzles with Sequence-to-Sequence Language Models

Conference: ECCV2026
Paper: ECCV Paper
Area: Visual Reasoning / Jigsaw Reassembly
Keywords: square jigsaw puzzles, discrete representations, sequence-to-sequence, border tokens, autoregressive prediction

TL;DR

PuzLM turns image pieces into symbolic sequences through lightweight border tokenization, then uses a standard encoder-decoder model to predict each piece's grid position, achieving 92.2% absolute accuracy and 87.1% perfect accuracy on ImageNet 3x3.

Background & Motivation

Square jigsaws lack the interlocking contours of toy puzzles: every piece has the same geometry, so adjacency must primarily be inferred from image content. Traditional methods compare boundary colors or learn pairwise compatibility, then assemble the global layout through search, optimization, or reinforcement learning. Recent approaches introduce vision Transformers, diffusion models, and vision-language models, but generally entangle visual appearance and structural relationships in continuous features. Even when reconstruction succeeds, this makes it difficult to determine whether the solver relies on local pixel agreement or statistical patterns spanning pieces and positions.

PuzLM controls this information interface: the frontend still reads images, but the backend receives only discrete identifiers from a fixed vocabulary. It neither describes images in natural language nor asks a conversational model to explain them; instead, it directly reformulates reassembly as supervised sequence mapping. Each input unit describes the border structure of an image piece, while each output unit identifies the grid position assigned to that piece. The central question is therefore whether this coarse symbolic interface preserves enough assembly information, rather than whether an image code can reconstruct the original appearance faithfully.

This choice is particularly relevant to eroded boundaries and missing pieces: precise pixel seams can become unreliable, making global relationships potentially more useful than fine details. Discretization can merge irrelevant photometric variation, but it can also discard information needed to distinguish similar pieces, so its superiority cannot be assumed. The authors consequently evaluate both task performance and tokenization choices to examine how compactness, spatial ordering, and modeling capacity interact. Core Idea: encode piece borders as structurally consistent symbolic sequences, then combine global encoder context with incremental decoder position predictions to solve puzzles without giving the solver direct pixel access.

Method

Overall Architecture

The input is an unordered collection of pieces belonging to a square grid of known size, and the output is a one-to-one assignment of pieces to grid positions. Positions use zero-based raster order; the output sequence follows the input piece order, rather than listing pieces in destination order. The pipeline consists of "Border Symbolization," "Canonical Serialization," and "Autoregressive Position Prediction," with BART as the default solver backbone. The frontend converts visual content into symbols, while the backend infers positions from all symbols, establishing an explicit information boundary between them.

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    Pieces["Unordered square pieces"] --> Tokenize["Border Symbolization<br/>PCA and k-means"]
    Tokenize --> Serialize["Canonical Serialization<br/>Lexicographic order and separators"]
    Serialize --> Predict["Autoregressive Position Prediction<br/>Encoder and decoder"]
    Target["Ground-truth position sequence"] -.->|Training supervision only| Predict
    Predict --> Layout["Position index for each piece<br/>Rearrange into the puzzle"]

During training, the PCA projection and cluster centers are learned from training pieces, after which puzzle and ground-truth position sequences supervise the solver. At inference, the projection, vocabulary, and solver parameters remain fixed; neither ground-truth positions nor prior pixel reconstruction is required. The supervision edge distinguishes training from inference and does not imply that correct positions are available as test-time clues.

Key Designs

1. Border Symbolization: retain assembly structure instead of reconstructing all appearance

Each image piece is divided into \(B\times B\) small patches; each flattened patch is projected with PCA and represented by the index of its nearest k-means center. This identifier denotes a cluster, not an original color value or a word with predefined natural-language meaning. A patch's identifier depends on the fixed projection and cluster centers, not on neighboring tokens or its position in the sequence. Context-independent encoding allows similar local patterns to reuse the same symbol across pieces, without the frontend first entangling neighborhood relationships in a visual representation. The solver then learns task-relevant relationships through its own embedding layer, rather than receiving PCA vectors or the pixel appearance of cluster centers directly. However, "no direct pixel access" does not mean "no visual information": tokens are still derived from images and can retain quantized appearance cues.

After constructing the patch grid, the method keeps only its perimeter and traverses it clockwise to form a super-token, a short sequence representing one puzzle piece. This does not compress the entire piece into another single vocabulary identifier; it preserves several border tokens in a fixed internal spatial order. With \(B=4\), a piece originally contains 16 patches, of which 12 boundary patches are retained and 4 interior patches are removed. Borders typically contain adjacency information, whereas interior texture increases length and can introduce variation that is not useful for assembly. This explains both why image reconstruction quality is not the tokenizer selection criterion and why finer granularity need not improve accuracy. Figure 5 shows that performance is best around \(B=4\) and declines with further subdivision, rather than increasing monotonically with representational precision.

2. Canonical Serialization: give the same set a stable external order

The collection of pieces has no inherent order, but a Seq2Seq model requires a linear input sequence. PuzLM sorts pieces lexicographically by their super-tokens and inserts a dedicated [SEP] between neighboring pieces. Lexicographic comparison uses symbolic sequences, not correct spatial locations, so this is not sorting by the answer before presenting the input. It reduces representational variation caused by random input permutations and exposes the model to a more consistent input structure. Clockwise traversal instead preserves local orientation within each piece; the two choices normalize between-piece and within-piece order, respectively. Separators explicitly identify where one piece ends and the next begins, instead of relying solely on fixed length to imply boundaries.

For \(N\) pieces with \(b\) retained boundary tokens per piece, the total input length is:

\[ b=\max(1,4B-4),\qquad T(N)=bN+(N-1). \]

These relationships follow the boundary definition and sequence-length explanation on pages 5-6, independently of the corrupted sequence equation in the extracted text. With the default \(B=4\), a complete 3x3 puzzle uses 108 border tokens and 8 separators, totaling 116 input tokens. A 5x5 puzzle uses 300 border tokens and 24 separators, totaling 324 input tokens; both lengths are examples calculated from the formula. Linear input storage in the number of pieces does not imply linear Transformer attention computation. Sorted pieces must also retain their correct position labels: the supervised target order must change with the input, rather than retaining indices from the original random arrangement.

3. Autoregressive Position Prediction: condition every decision on all inputs and previous assignments

The encoder first applies bidirectional self-attention to the full symbolic input, establishing global relationships across borders and pieces. The decoder then emits position indices incrementally, conditioning each step on encoder outputs and the previously generated position prefix. Inputs belong to a visual-token vocabulary, whereas outputs belong to a grid-position set and have a different length, making the encoder-decoder formulation a natural match for the task. The default 3x3 task produces only 9 position indices, rather than regenerating a visual-symbol sequence of length 116. Prediction operates over the full permutation space without requiring a preselected classification list of a small number of candidate arrangements. This distinguishes it from some early self-supervised puzzle approaches that restrict the task to 1000 permutations.

Previous outputs inform the model which positions have already been assigned, helping subsequent decisions remain globally consistent. However, the paper reports that training naturally discourages invalid configurations such as duplicate assignments; it does not introduce specialized decoding constraints that guarantee a bijection. Avoiding conflicts should therefore be interpreted as learned behavior, not a mathematical guarantee that every output is a valid permutation. Inference selects positions with stepwise argmax and does not require an additional visual matching module or specialized puzzle search procedure. The paper also compares T5, Pegasus, LSTM, and GRU, showing that the framework is not tied to a BART-specific interface, although global attention and capacity affect performance. These comparisons support the architectural choice, but the available main text does not precisely attribute the gains to any particular kind of language pretraining knowledge.

A Worked Example

Consider an image shuffled into a 3x3 puzzle; the following indices illustrate the input-output convention and are not a measured example from the paper. With \(B=4\), each piece becomes 12 boundary tokens, and lexicographic sorting produces a 116-token input including separators. Suppose the first sorted piece originally occupied position 7 and the second occupied position 0; the target sequence then begins [7, 0, ...]. Here, 7 places the first piece in the middle of the last row, while 0 places the second in the top-left corner; it does not mean "place the seventh piece first." After predicting the first index, the decoder uses that index and all inputs to predict the second, continuing until each piece has a position. The original pieces are finally rearranged using these assignments; images are needed for frontend tokenization and final visual rearrangement, but not as continuous visual inputs to the solver.

If a piece is missing, the paper replaces all its corresponding tokens with a dedicated mask token and retains the same prediction protocol. The model still predicts a position sequence, but evaluation includes only non-missing pieces and does not require generating the absent image content. The missing-piece experiment therefore measures layout recovery from incomplete evidence, not image restoration or texture completion.

Loss & Training

Tokenization uses unsupervised PCA and k-means, whereas position prediction is supervised by known correct puzzle layouts. Section 3.5 uses cross-entropy between predicted and true positions; the following is standard autoregressive notation for that stated objective, not a copied equation from the paper:

\[ \mathcal{L}_{\mathrm{CE}}=-\sum_{t=1}^{N}\log p_{\theta}(y_t\mid X,y_{<t}). \]

Here, \(X\) is the canonically serialized puzzle-symbol sequence, and \(y_t\) is the correct position of the \(t\)th input piece. The input ordering must align with target positions; training does not reconstruct piece-content tokens from position identifiers. At test time, the ground-truth prefix is replaced by previously generated predictions, and argmax selects the next position. Consequently, early mistakes can influence subsequent assignments, and the main text does not provide a dedicated backtracking correction strategy.

The default configuration uses BART, \(B=4\), and 4096 visual tokens; Table 5 independently confirms the vocabulary size. The cache renders the PCA dimension as 210, potentially losing superscript formatting, so its precise value cannot be established from that rendering alone. The authors place the full optimizer setup, training duration, pretrained initialization details, and cost analysis in supplementary material that is not included in the supplied main-text cache. Accordingly, this note does not supply learning rates, training hardware, or end-to-end speed, and does not conflate tokenization cost with the cost of the full solver.

Key Experimental Results

Main Results

Absolute accuracy (Abs.) measures the fraction of correctly placed pieces, while perfect accuracy (Perf.) measures the fraction of puzzles with every evaluated piece correctly placed. A complete puzzle with even one misplaced piece does not count as perfect; all table values are percentages, and the two metrics are not interchangeable. ImageNet 3x3 uses ordinary images; JPwLEG uses MET artwork images with artificially eroded piece boundaries in 3x3 and 5x5 configurations.

Dataset and condition	Method	Abs. (%)	Perf. (%)	Source location
ImageNet 3x3, full permutation space	JPDVT	83.3	68.7	Table 2, page 11
ImageNet 3x3, full permutation space	FCViT	90.6	78.9	Table 2, page 11
ImageNet 3x3, full permutation space	PuzLM	92.2	87.1	Table 2, page 11
JPwLEG-3, eroded boundaries	FCViT	96.9	87.9	Table 4, page 11
JPwLEG-3, eroded boundaries	PuzLM	91.9	84.5	Table 4, page 11
JPwLEG-5, eroded boundaries	VLHSA	66.9	19.0	Table 4, page 11
JPwLEG-5, eroded boundaries	PuzLM	72.1	32.5	Table 4, page 11

On ImageNet 3x3, PuzLM improves perfect accuracy over FCViT by 8.2 percentage points, not by a relative 8.2%. On JPwLEG-5, it improves perfect accuracy over VLHSA by 13.5 percentage points, but remains below FCViT on JPwLEG-3. The prose on page 12 reports PuzLM's JPwLEG-3 perfect accuracy as 87.9%, conflicting with 84.5% in Tables 4 and 5; this note uses the two mutually consistent tables and preserves the discrepancy.

Ablation Study

The following JPwLEG-3 tokenization ablations come from Table 5 on page 13, with other settings following the default configuration.

Config	Abs. (%)	Perf. (%)	Specific change
PuzLM	91.9	84.5	Full model
w/o PCA	81.1	67.0	Remove PCA projection
w/o border	72.2	50.3	Include interior tokens instead of retaining only borders
w/o lex. order	67.6	35.0	Replace lexicographic order with random order
w/o clockwise	86.9	80.8	Replace clockwise traversal with raster scanning
w/o sep. token	84.7	79.0	Remove separators between pieces

Removing lexicographic order reduces perfect accuracy from 84.5% to 35.0%, a 49.5-percentage-point drop and the largest change in this ablation set. Including interior tokens also reduces perfect accuracy to 50.3%, showing that more visual content need not improve relational representations, although this ablation changes both content and sequence length. Table 5 also reports fewer than 1M tokenizer parameters and encoding time below 1 ms; these are not BART's parameter count or the end-to-end time to solve a puzzle.

Key Findings

Missing-piece results are from Table 3 on page 11, evaluated on ImageNet 3x3 using only the remaining pieces.

Missing pieces	JPDVT Abs. (%)	JPDVT Perf. (%)	PuzLM Abs. (%)	PuzLM Perf. (%)
1/9	72.0	41.5	86.0	71.3
2/9	61.8	21.4	73.8	45.1
3/9	54.1	14.9	61.2	23.7

Both methods degrade as more pieces disappear, and PuzLM is better in all three settings, but this does not establish that it can recover the missing image content. Figure 5 shows trade-offs in granularity, PCA dimension, and vocabulary size; the cache does not provide reliably transcribable curve coordinates, so only trends are retained here. Section 4 finds statistical structure that only partly resembles natural language through entropy, Zipf, and Heaps analyses; this is descriptive evidence, not a causal demonstration of model effectiveness.

Highlights & Insights

• Optimize the representation interface rather than merely enlarge the visual model: border tokens expose more stable local patterns. Gains arise from task-relevant discretization and serialization, not simply from language models being inherently capable of puzzle solving.
• Separate internal spatial order from external canonical order: clockwise traversal retains boundary geometry, while lexicographic sorting reduces input-set permutation variation. Table 5 shows the latter is especially important, suggesting a transferable design for other set-to-sequence tasks.
• Measure combinatorial consistency with perfect accuracy: any misplaced piece affects this metric, making its improvement more informative about complete layout recovery than average piece accuracy alone. It remains an outcome measure, not direct observation of the reasoning mechanism.

Limitations & Future Work

• Symbolization does not eliminate vision: this is a reader's qualification of the paper's framing. Quantized labels still derive from pixels, and a fixed vocabulary cannot eliminate shifts in token frequencies, relationships, or scene distributions.
• Validity is not guaranteed: the method relies on autoregressive training to reduce duplicate positions and reports no specialized permutation constraint. Future work could test whether explicitly excluding used positions improves validity and perfect accuracy, but that experiment is not reported here.
• Scalability evidence is bounded: the main text emphasizes 3x3 and 5x5 puzzles, with larger-puzzle and cross-dataset experiments assigned to unavailable supplementary material. Linear input length does not establish performance at arbitrary scale, with unknown orientations, or on real irregular fragments.
• Reproduction gaps and numerical conflicts remain: JPwLEG-3 prose conflicts with the tables, PCA dimensionality is ambiguously rendered, and detailed training settings are absent from this cache. Table 5's tokenization speed also does not justify an end-to-end efficiency claim.

Related Work & Insights

• FCViT, paper reference [19]: Kim et al.'s 2025 work predicts fragment coordinates with a vision Transformer. PuzLM instead uses discrete inputs and autoregressive outputs, but still trails it on JPwLEG-3, so it does not universally replace visual features.
• JPDVT, paper reference [23]: Liu et al.'s CVPR 2024 work uses diffusion vision Transformers for masked jigsaws. PuzLM retains its position-generation protocol through mask symbols and achieves higher layout accuracy with missing pieces.
• VQ-VAE and TiTok, paper references [27] and [55]: the former introduces discrete latent representations, while the latter emphasizes compact image tokenization. This paper illustrates that an encoding suitable for image reconstruction need not suit piece reassembly; task-relevant information should guide interface selection.
• Self-supervised jigsaws, paper reference [26]: Noroozi and Favaro's ECCV 2016 work uses puzzles as a pretext task for visual representation learning. PuzLM targets puzzle reassembly itself and reports no downstream representation transfer, so self-supervised learning is not its primary category.

Rating

• Novelty: 4/5. Combines task-specific border quantization with standard Seq2Seq modeling into a clear symbolic reassembly interface.
• Experimental Thoroughness: 4/5. Complete, eroded, and missing-piece tasks support multiple ablations, but larger-scale evidence and reproduction details require supplementary material.
• Writing Quality: 3/5. The problem and modules are clear, but the "purely symbolic" claim needs qualification and the JPwLEG-3 prose contains a conflicting result.
• Value: 4/5. Offers useful representation design for structured visual reassembly without establishing a breakthrough in general visual reasoning or model compression.