PaperlayerView exact revision on arXiv

Source-linked AI summary

Are Language Models Puzzle Prodigies? Algorithmic Puzzles Unveil Serious Challenges in Multimodal Reasoning

Deepanway Ghosal, Vernon Toh Yan Han, Chia Yew Ken, Soujanya Poria

arXiv:2403.03864v3cs.CVcs.AI

TL;DR

The paper addresses the challenge of evaluating multimodal models on algorithmic reasoning over visual puzzles, beyond tasks answerable through direct image interpretation or factual knowledge. It introduces an automatically generated puzzle dataset with definitive solutions and adjustable complexity. Models consistently struggle on the tasks, and even with accurate visual guidance, high-level performance remains elusive.

  • Problem

    The paper targets evaluation of models' ability to apply algorithmic rules to novel visual-puzzle scenarios, rather than relying on stored information or direct fact recall.

    Source: §1 · p. 1

  • Method

    The authors introduce ALGOPUZZLEVQA, an ontology-based puzzle dataset generated from human-written code with definitive solutions and adjustable reasoning complexity.

    Source: §1 · p. 2

  • Results

    Models consistently struggle on ALGOPUZZLEVQA; GPT-4V in the eCoT setup achieves average accuracy of 31.7%, around 5% better than random.

    Source: §4.3 · p. 7, §5 · p. 8

  • Takeaways & Limitations

    Accurate visual guidance enhances performance in some cases, but high-level performance on the complex reasoning tasks remains elusive.

    Source: §5 · p. 8

    The puzzle suite does not cover all interesting puzzles, and the algorithmic ontology could include more fine-grained categories.

    Source: §6 · pp. 8–9

Abstract

from arXiv · show

This paper introduces the novel task of multimodal puzzle solving, framed within the context of visual question-answering. We present a new dataset, AlgoPuzzleVQA designed to challenge and evaluate the capabilities of multimodal language models in solving algorithmic puzzles that necessitate both visual understanding, language understanding, and complex algorithmic reasoning. We create the puzzles to encompass a diverse array of mathematical and algorithmic topics such as boolean logic, combinatorics, graph theory, optimization, search, etc., aiming to evaluate the gap between visual data interpretation and algorithmic problem-solving skills. The dataset is generated automatically from code authored by humans. All our puzzles have exact solutions that can be found from the algorithm without tedious human calculations. It ensures that our dataset can be scaled up arbitrarily in terms of reasoning complexity and dataset size. Our investigation reveals that large language models (LLMs) such as GPT4V and Gemini exhibit limited performance in puzzle-solving tasks. We find that their performance is near random in a multi-choice question-answering setup for a significant number of puzzles. The findings emphasize the challenges of integrating visual, language, and algorithmic knowledge for solving complex reasoning problems.

1 Introduction

The paper proposes visual algorithmic puzzles to test multimodal reasoning beyond recognizing images or recalling facts. Its automatically generated puzzles have definitive solutions and adjustable complexity, while experiments reveal substantial model challenges.

1 Introduction

  • The dataset targets algorithmic reasoning: applying logical rules to novel situations rather than relying on stored information or direct fact recall.The puzzles require minimal knowledge beyond basic mathematics, with the needed context provided in the problem.Source: §1 · p. 1
  • Puzzles combine visual configurations and cues with language describing puzzle features, rules, and the query, requiring mathematical or algorithmic reasoning.Topics range from arithmetic, set theory, and boolean logic to graph theory and optimized search.Source: §1 · pp. 1–2, Figure 1 · p. 2
  • Human-written code generates puzzles from algorithmic solutions, with varied inputs and configurations enabling scalable challenges of adjustable reasoning complexity.The framework is presented as a way to update the benchmark with increasingly complex problems.Source: §1 · p. 2
  • The algorithmic foundation gives each puzzle a definitive solution, avoiding annotation error, subjectivity, ambiguity, and biases associated with human-annotated content.The paper also reports that models show deficiencies in visual perception and algorithmic reasoning, hindering effective complex reasoning.Source: §1 · pp. 2–3

2 The Proposed Ontology

The ontology categorizes puzzle instances by visual features and by the algorithmic features needed to solve them. Its categories help describe the range and combination of skills represented in the puzzles.

2 The Proposed Ontology

  • The ontology categorizes the visual and algorithmic features present in each puzzle, providing the organizing framework for the dataset.The paper presents the categorizations in Table 1.Source: §2 · p. 3, Table 1 · p. 4

2.1 Visual Features

  • Visual categories include colour, position, shape/size, and embedded text; positional understanding is necessary for every puzzle.Some embedded text is essential, while Map Colour's embedded text is only an additional reference.Source: §2.1 · p. 3

2.2 Algorithmic Features

  • Algorithmic categories include arithmetic, boolean logic, combinatorics, graphs, optimization, search, and sets, and most puzzles require multiple categories.The ontology is limited to features used to obtain puzzle solutions; its search categories are breadth-first and exhaustive search.Source: §2.2 · pp. 3–4

3 From the Ontology to Creating ALGOPUZZLEVQA

ALGOPUZZLEVQA contains automatically generated algorithmic puzzles with adjustable inputs and difficulty, alongside verified solutions. Its 18 puzzle types cover varied tasks, while the current problems are easy to moderate and often solvable by hand.

3 From the Ontology to Creating ALGOPUZZLEVQA

  • Puzzle instances are generated automatically from human-written code that produces images and computes solutions, while authors curate and verify English puzzle templates.The algorithmic foundation gives each instance a definitive solution and avoids annotation error, subjectivity, ambiguity, and biases associated with human-annotated content.Source: §3 · pp. 4–5
  • The current problems are easy to moderate, and many can be solved by humans by hand without applying the underlying algorithm.The authors state that harder problems would make the algorithmic solution easier to find.Source: §3 · p. 5
  • The dataset contains 1,800 instances across 18 puzzles, with 100 instances per puzzle and an evaluation-only benchmark setup.Instances vary inputs, configurations, and states; the dataset's size and difficulty are described as arbitrarily scalable.Source: §3 · pp. 4–5

3.1 Some Example Puzzles in Our Dataset

  • Board Tiling asks whether the checkerboard with two removed squares can be covered by 26 dominoes; its yes-or-no answer follows a dark-light square balance condition.The general result says a mutilated board with 2*m squares is tileable exactly when it has equal numbers of dark and light squares.Source: §3.1 · p. 5, Figure 3 · p. 5
  • Colour Hue asks for the minimum tile swaps from a shuffled board to its ideal state, using selection sort to determine the answer.The puzzle treats the non-ideal state as unsorted and the ideal state as sorted.Source: §3.1 · p. 5, Figure 4 · p. 6
  • Map Colouring fixes some region colours and counts valid completions of the remaining regions using four-colour graph colouring and Algorithm X.The maps are constructed from Voronoi diagrams followed by polygon clipping.Source: §3.1 · pp. 5–6, Figure 5 · p. 6

4 Experiments on ALGOPUZZLEVQA

The experiments evaluate multimodal models on algorithmic puzzles using multiple-choice accuracy, then examine overall performance, ontology-based patterns, and the effects of guided visual context. Results show performance near random on many puzzles, with both visual perception and algorithmic reasoning presenting challenges.

4.1 Setup and Baselines

  • The evaluation uses multiple-choice accuracy, with three heuristic negative choices per instance except Board Tiling, which uses Yes/No choices.GPT-4V, Gemini, Claude, and LLaVA were prompted with zero-shot CoT; GPT-4V, Gemini, and Claude also used elaborate CoT, while Instruct-BLIP used constrained answer-choice prediction.Source: §4.1 · p. 6, §4.2 · p. 6

4.3 Main Results

  • GPT-4V eCoT achieved the highest overall average accuracy at 31.7%, only around 5% above the 26.4% overall random baseline.Performance across a significant number of puzzles and models was close to the puzzle-specific random baselines of 50% for Board Tiling and 25% for other puzzles.Source: §4.3 · p. 7, Table 2 · p. 7
  • Rubik’s Cube and Think A Dot had the highest average scores over random, while N-Queens and Colour Hue had the lowest.The paper identifies the former pair as comparatively easiest and the latter pair as hardest for the models.Source: §4.3 · p. 7
  • GPT-4V CoT reached 57% accuracy on Calendar, the highest puzzle-level score; no puzzle exceeded 60%.The paper concludes that visual algorithmic problem-solving remains challenging for large multimodal language models.Source: §4.3 · p. 7

4.4 Ontological Analysis

  • Closed models mostly performed better on colour, position, and text features, but poorer on shape and size.Across models, optimization and search were generally the most difficult algorithmic topics; GPT-4V eCoT did better on combinatorics and sets than on those topics.Source: §4.4 · p. 7, Table 3 · p. 8

4.5 Reasoning with Guided Vision

  • Guided vision supplies detailed image descriptions in the language context, minimizing visual-perception errors so models can focus on algorithmic reasoning.Some GPT-4V puzzle scores improved substantially, indicating a visual-perception bottleneck, but scores remained well below 100%, showing substantial algorithmic-reasoning challenges even with gold context.Source: §4.5 · pp. 7–8, Table 4 · p. 8

5 Conclusion

The paper introduces ALGOPUZZLEVQA, a dataset of puzzles requiring reasoning across vision, language, and algorithms. Its experiments find persistent difficulty for multimodal models, including when visual guidance improves performance in some cases.

5 Conclusion

  • ALGOPUZZLEVQA is a dataset of puzzles requiring multimodal reasoning over vision, language, and algorithms.Its challenges rely on applying logical algorithmic steps to novel scenarios rather than domain-specific knowledge.Source: §5 · p. 8
  • The dataset’s ontology covers visual features such as colour, position, shape, and size, alongside algorithmic features such as arithmetic, combinatorics, and optimization.Each puzzle is annotated with specific visual and algorithmic features to support analysis of the skills models lack on particular problems.Source: §5 · p. 8
  • Experiments found that models struggled to achieve satisfactory performance, and visual guidance improved performance in some cases without resolving the complex reasoning challenge.The paper emphasizes the difficulty of multimodal reasoning for algorithmic puzzle-solving.Source: §5 · p. 8

6 Limitations

The paper describes a bounded puzzle suite and identifies broader puzzle coverage and finer ontology categories as future directions. Its evaluation prompts models to produce reasoning steps and answers in natural language, while code-generating models remain for future study.

6 Limitations

  • The compiled puzzles are popular in recreational or academic settings, but the authors aim to enlarge the suite with additional puzzles.Source: §6 · pp. 8–9
  • The algorithmic ontology could be expanded to include more fine-grained categories.Source: §6 · p. 9
  • Models were prompted to generate reasoning steps and answers in natural language; code-generating models are left for future exploration.Source: §6 · p. 9

A Puzzles

  • The current suite includes 18 puzzles, and the authors note that other interesting puzzles remain beyond the compiled list.Source: §6 · p. 8, A Puzzles · p. 10

A.1 Board Tiling

Board-tiling puzzles use checkerboard color balance to determine tileability, while calendar puzzles ask models to infer a weekday from a calendar image and year information.

A.1 Board Tiling

  • A mutilated board with 2*m squares is tileable by m dominoes exactly when it has equal numbers of dark and light squares.Source: §A.1 · p. 10
  • Instances use randomly selected board dimensions from 4 to 9 and remove one or two squares according to whether the board has an odd or even number of squares.Source: §A.1 · p. 10

A.2 Calendar

  • Calendar puzzles provide a month snapshot and leap-year information, then ask for a date's weekday in the previous, same, or next year.Source: §A.2 · p. 10

A.3 Checker Move

Checker Move puzzles require rearranging colored checkers on a line under directional movement rules; the paper uses breadth-first search to derive solutions.

A.3 Checker Move

  • The puzzle starts with n−1 red or green checkers occupying n−1 positions on a grid of length n, and asks for a specified rearrangement.Source: §A.3 · p. 10
  • Green checkers move right and red checkers left; moves slide into an adjacent empty square or jump over an oppositely colored checker into an empty square.Source: §A.3 · p. 11
  • Breadth-first search under the movement rules derives solutions; the illustrated five-square instance requires 8 moves.Source: §A.3 · p. 11, Figure 8 · p. 11

A.4 Chain Link

The chain-link puzzle asks for the least time to form the longest possible circular necklace from segments by cutting closed pieces and welding open links. Its solution balances open links against closed segments, then counts the operations.

A.4 Chain Link

  • The puzzle, modified from a problem in Kordemsky (1992), seeks the least time to make the longest possible circular necklace from chain segments.Source: §A.4 · p. 11
  • 34 minutes is the minimum for the Figure 9 instance, using four cuts and seven welds.Source: Figure 9 · p. 11, §A.4 · p. 11
  • The solution cuts units from the shortest segments until open links equal or exceed the number of closed segments.Source: §A.4 · p. 11

A.5 Clock

Clock and Colour Hue puzzles turn visual configurations into questions solved with modular arithmetic or minimum-swap sorting. Their examples ask for an earlier time and the swaps needed to restore an ordered board.

A.5 Clock

  • The Clock puzzle shows a current analog time and asks when an event occurred or will occur after a stated interval.The example asks for the time three minutes before the shown clock time; its gold answer is 9:19.Source: §A.5 · pp. 11–12, Figure 10 · p. 12
  • Modular arithmetic determines the Clock puzzle’s answer from the displayed time and the stated hours-and-minutes offset.The clock has hour and minute hands and no seconds hand in the example.Source: §A.5 · pp. 11–12, Figure 10 · p. 12

A.6 Colour Hue

  • The Colour Hue puzzle asks for the minimum swaps needed to restore a shuffled colour board, treating its flattened ideal and shuffled states as sorted and unsorted arrays.The ideal board interpolates colours between four fixed corner tiles; selection sort determines the minimum swaps.Source: §A.6 · p. 12, Figure 11 · p. 12

A.7 Map Colouring

The Map Colouring puzzle uses four-colour constraints on generated maps, fixing some regions and counting valid completions. Maps are represented as graphs and solved exhaustively with Algorithm X.

A.7 Map Colouring

  • The example map has eight unique completions after regions 1–10 are fixed, with regions 11–15 left to colour.Adjacent regions share a boundary of non-zero length, and adjacent regions must differ in colour.Source: Figure 12 · p. 12
  • The four-colour theorem states that four colours suffice to colour any planar map so adjacent regions have different colours.Source: §A.7 · p. 12
  • Maps are generated as clipped Voronoi regions, represented by region nodes and adjacency lists, then exhaustively coloured using Algorithm X.Some region colours are fixed, and the remaining valid assignments are counted.Source: §A.7 · pp. 12–13

A.8 Maze Solving

These subsections describe puzzle-generation procedures and answer formats across search, state-transition, and spatial-reasoning tasks, plus multiple-choice distractor and model-query settings. Many instances use exact algorithmic solutions or are sampled from known solution paths.

A.8 Maze Solving; A.9 Move Box

  • Maze instances use randomized depth-first search to create paths, then breadth-first search finds an optimal route for questions about path length or turns; Move Box asks for minimum pushes.The maze question is randomly selected from turn-count or visited-cell questions; the box-moving puzzle is solved with breadth-first search.Source: §A.8 · p. 13, §A.9 · p. 13, Figure 14 · p. 13

A.10 N-Queens

  • N-Queens instances show N−2 queens from a backtracking-generated solution and ask for the Manhattan distance between the remaining two queens.For N=8, 9, and 10, the stated solution counts are 92, 352, and 724; alternative placements, when present, yield the same distance.Source: §A.10 · pp. 13–14, Figure 15 · p. 14

A.11 Number Slide

  • Number Slide questions vary the number of moves and ask about reachable boards or row and column sums; breadth-first search computes the answers.Boards are random arrangements on 3×3, 4×4, or 5×5 grids; the example is a 4×4 board with a one-move minimum top-row sum of 22.Source: §A.11 · p. 14, Figure 16 · p. 14

A.12 Rotting Fruit

  • Rotting Fruit asks for the earliest time all fruit becomes rotten, a grid-propagation problem solvable by breadth-first search.Each minute, fresh fruit adjacent to rotten fruit becomes rotten; the example’s gold answer is three minutes.Source: §A.12 · pp. 14–15, Figure 17 · p. 15

A.13 Rubik’s Cube; A.14 Think A Dot

  • Rubik’s Cube asks for a colour count after a move sequence, while Think-a-Dot asks for visible disk colours after sequential ball drops.The cube’s notation specifies clockwise face turns; the toy algorithm tracks disk flips, row states, and wall positions.Source: §A.13 · p. 15, Figure 18 · p. 15, §A.14 · p. 15

A.15 Tower of Hanoi; A.16 Water Jugs

  • Tower of Hanoi instances select configurations at most six moves apart along an optimal solution; Water Jugs instances use breadth-first search to retain reachable goals.The example Hanoi configurations require two moves, while water-jug questions ask the minimum pours under empty-or-full stopping rules.Source: §A.15 · pp. 15–16, Figure 20 · p. 16, §A.16 · pp. 16–17

A.17 Wheel of Fortune; A.18 Wood Slide

  • Wheel of Fortune asks which prize aligns with an arrow after rotation; Wood Slide selects board configurations at most five moves apart along an 83-move optimal solution.Wheel answers use rotational mechanics; Wood Slide asks for the minimum moves between selected configurations.Source: §A.17 · p. 17, Figure 22 · p. 17, §A.18 · p. 17

B Negative Choice Generation for MCQA; C Model Configurations

Related papers

Loading 2403.03864v3…