LongPuzzleBench: Evaluating GUI Agents on Long-Horizon Visual Puzzles

1 INTRODUCTION

• Long-horizon visual reasoning requires tracking state changes, anticipating which actions rule out later options, and revising plans when options are lost.Existing benchmarks measure grounding, multi-step computer use, static-puzzle reasoning, or game planning, but rarely isolate whether moves are judged by the options they leave.Source: §1 · p. 1
• Long-horizon visual puzzles expose decision dependencies: a legal move that looks like progress can make a puzzle unsolvable, with the loss surfacing several moves later.The figure contrasts two legal moves from the same board: one creates an unannounced dead end, while the other preserves solvability; both outcomes are verified by exhaustive search.Source: §1 · p. 1, Figure 1 · p. 2
• LongPuzzleBench comprises 114 levels across six games and 16 objectives, with objectives chaining up to ten levels under one time budget.A human needs a median of 204 GUI actions per objective and 1,106 for one Nut and Bolt level; dead ends are not announced, and agents act through the rendered interface.Source: §1 · p. 2
• Seven of ten general-purpose agents solve no objective harder than Medium, and no agent completes Bolt Unscrew Hard, while a human solves all 16 objectives.With Native GUI Actions, GPT-6-Astra has the highest OSR at 91.7%; Code Execution CUA does not close the gap and its scores mix visual solving with algorithmic search.Source: §1 · p. 2
• Controlled diagnostics trace failures to spending capacity that keeps a puzzle solvable and favoring visible progress over future options; rules, state hints, and failure memory do not remove this limitation.Agents often interpret rejected moves at dead ends as missed clicks and, after being told the board is lost, most rebuild a dead end.Source: §1 · p. 2

2 RELATED WORK

• GUI benchmarks test multi-step completion through rendered interfaces, but their steps are checked against an instructed goal and no legal action is designed to make that goal unreachable.LongPuzzleBench instead requires reasoning about what a persistent board still allows.Source: §2 · pp. 2–3
• Static visual puzzles use unchanging images, while interactive games and puzzles add actions or delayed consequences but typically reset failed episodes or use abstract actions.ARC-AGI-3 is described as the closest setting, but it acts through abstract game actions rather than a rendered interface; game benchmarks generally target gameplay rather than self-paced puzzles with silently decisive early moves.Source: §2 · p. 3
• LongPuzzleBench combines the relevant benchmark properties, and its dead ends are unannounced, requiring agents to infer from the board that progress is impossible.Table 1 presents a structural comparison with adjacent benchmarks; its legend distinguishes yes, no, subset-only, and unreported or inapplicable entries.Source: §2 · p. 3, Table 1 · p. 3

3 LONGPUZZLEBENCH

• The benchmark contains 114 levels in six puzzle games, grouped into 16 game–difficulty objectives.Fifteen objectives chain three to ten target levels under one budget, and an unsolved level blocks advancement.Source: §3 · pp. 3–4
• The six games use different constraints on future moves, including free holes, storage, lanes, shared space, departure order, or sliding movement needed for full coverage.In Bolt Unscrew and Nut and Bolt, a move can make a level unsolvable without warning; in the other four games, poor moves can lengthen the path but cannot make the level unsolvable.Source: §3 · p. 3
• A human needed 1,106 pointer presses for one Nut and Bolt level and a median of 204 presses per objective; 14 of 16 objectives required at least 100 presses.These measures capture both within-level interaction length and sustained solving across levels.Source: §3 · pp. 3–4
• Agents receive one objective instruction and a 60-minute budget to navigate, solve, advance, and restart through the GUI, with recovery left to them.Board states can be restored exactly for controlled interventions, while board state and grading signals remain private to the evaluator.Source: §3 · p. 4
• Released levels are playtested, repaired or excluded, solver-checked where implemented, and manually confirmed solvable; comparisons fix the catalogue, runtime, and seed.The catalogue is extended between snapshots with validated levels and games.Source: §3 · p. 4

4.1 SETUP

• The evaluation tests general-purpose agents in both action settings, GUI-specialized agents with native actions, and a human reference using one episode per objective.OSR measures objective completion, while LC, FGP, LChard, LPR, H50, and PER capture level completion, progress, harder-tier performance, reached-level success, sustained level horizon, and early exits.Source: §4 · p. 4, §4.1 · pp. 4–5

4.3 CODE EXECUTION CUA MIXES VISUAL SOLVING WITH SEARCH

• Code Execution CUA does not close the gap: OSR ranges from 36.1% to 91.7%, and some high-scoring agents search over transcribed boards rather than solve visually.GPT-6-Astra reaches 91.7% OSR in both settings; the settings also differ in tool integration, so their gaps characterize each setting as a whole.Source: §4.3 · p. 6

4.4 WHERE PERFORMANCE BREAKS DOWN

• Maze Paint solver-optimal solutions grow from 8.8 to 21.7 slides per level from Easy to Hard, while Hard-level LC ranges from 10% to 100%.All ten agents clear every Easy level under Code Execution CUA, showing that easy tiers do not distinguish long-horizon performance.Source: §4.4 · p. 6, Figure 3 · p. 7
• Across agents, 65% of Code Execution CUA episodes and 52% of Native GUI Actions episodes clear all ten levels of the chained objectives.Because levels are won in catalogue order, an unsolved level forfeits all later ones; GPT-6-Sol exceeds GPT-5.6-Sol by 3.7 points in LPR but 11.7 points in OSR.Source: §4.4 · p. 6, Figure 3 · p. 7
• GPT-5.6-Luna, GPT-6-Luna, and GPT-5.6-Terra voluntarily end 62.5–75.0% of Code Execution CUA episodes and 56.2–68.8% of Native GUI Actions episodes.Since progression stays with the agent, the decision to keep playing is part of the measured capability.Source: §4.4 · p. 6

4.5 HUMANS AND AGENTS SUCCEED ON DIFFERENT PUZZLES

• On shared Nut and Bolt Nightmare states, Astra needs 65 stack-state changes versus the human’s 431, but Bolt Unscrew Hard reverses their ranking.Nut and Bolt rewards bookkeeping over an accumulating solved-stack state, while Bolt Unscrew rewards preserving capacity; the comparison uses one human trajectory per setting.Source: §4.5 · pp. 6–7
• Figure 4 contrasts Bolt Unscrew free-hole trajectories, where the agent path repeats in 10 of 12 retries, with Maze Paint move outcomes by board coverage.The figure distinguishes new-cell painting from exact-state revisits in Maze Paint.Source: Figure 4 · p. 7

5.1 MOVES THAT LOOK LIKE PROGRESS SPEND SOLVABILITY

• With one free hole left, agents fill it in three quarters of moves, deadlocking with 20 of 24 boards still attached in 10 of 12 retries.The same starting board’s verified solution instead frees three more boards and reopens a hole; 15 of 17 first moves from solvable starts with one free hole are fatal.Source: §5.1 · p. 8

5 FAILURE DIAGNOSIS: WHY DO AGENTS FAIL?

• Across the diagnostics, agents prioritize visible progress over the future options that determine whether a puzzle remains solvable.Rules describe individual moves, but solving requires predicting how move sequences affect future options.Source: §5.1 · p. 8, §5.4 · p. 9, §5.3 · p. 9

5.2 DEAD ENDS LOOK LIKE MISSED CLICKS

• State information raised recovery on certified Bolt Unscrew dead ends from 8 of 24 runs to 23 of 24, while most unprompted runs blamed execution errors.Naming the restart control added nothing; in Nut and Bolt, no model recovered under any condition.Source: §5.2 · p. 8

5.3 RECOVERY RESETS THE BOARD, NOT THE PLAN

• No retry completed under any memory condition (0/126), and 79% returned to the source dead end despite different memory variants choosing different first moves in 20 of 24 sources.All 24 agent-written summaries attributed failure to execution or missing observations, and none identified exhausted free holes or proposed a different plan.Source: §5.3 · p. 9

5.4 KNOWING THE RULES IS NOT PLANNING WITH THEM

• The rule card doubled correctly stated rules from 43% to 88%, but completion rose only from 50% to 60%; seven sessions stating every rule still left levels unsolved.Across three models, the card added about nine LC points on average, with large variation across objectives.Source: §5.4 · p. 9

6 CONCLUSION

• Preserving future options is a central challenge for visual puzzle agents, and evaluation should require keeping plans viable through completion over many consequential moves.LongPuzzleBench evaluates this through self-paced GUI puzzles where early decisions constrain later moves and agents must recognize and recover from dead ends.Source: §6 · p. 10

AI USE STATEMENT

• AI tools polished language, grammar, and phrasing only; the authors state they did not generate research ideas, experimental conclusions, or scientific findings.The authors take full responsibility for the manuscript’s content.Source: AI USE STATEMENT · p. 10

ETHICS STATEMENT

• The work uses locally run browser puzzles and in-game human reference actions, with no human subjects, sensitive personal data, or real-world high-risk deployment.The authors identify no ethical concerns requiring further discussion.Source: ETHICS STATEMENT · p. 10

REPRODUCIBILITY STATEMENT

• Comparisons within an evaluation snapshot fix the catalogue, runtime, and seed; the benchmark code, game suite, and harness are available in the linked repository.Appendix D.1 gives the shared diagnostic design, while Appendices B.1–B.4 specify protocol, agents, metrics, and token usage.Source: REPRODUCIBILITY STATEMENT · p. 10

APPENDICES

• The appendices list extended main results and diagnostic studies, including per-objective results, human–agent trajectory comparison, and the RQ1–RQ4 analyses.Appendix A covers benchmark details; Appendix B covers evaluation protocol and metrics.Source: A Benchmark Details · p. 15, C Extended Main Results · p. 15, D Diagnostic Studies · p. 15

A.1 GAMES, OBJECTIVES, AND PROGRESS POTENTIALS

• Table 3 defines each game–difficulty pair as one objective, with level counts following difficulty order and completion conditions applying to each level.The games use different native controls, and their private progress potentials are game-specific.Source: Table 3 · p. 15, §A.1 · pp. 15–16

A.2 CONSTRUCTION, VALIDATION, AND REFRESH

• The suite is built from visual references and validated through GUI playtests, solver checks where implemented, and manual confirmation that every released level is solvable.A solver verifies all 30 Maze Paint levels; refresh limits repeated exposure to a fixed catalogue but does not establish freedom from contamination because familiar mechanics or layouts may remain.Source: §A.2 · p. 16

A.3 BENCHMARK CHARACTERIZATION STATISTICS

• The human completed all 16 objectives; dead-end certification is available for Bolt Unscrew and Nut and Bolt, but other games’ states are not annotated as dead ends.The human made 99 restarts and 55 undos across nine objectives; dead-end delays are lower bounds because transfers between settled-board snapshots can be missed.Source: §A.3 · pp. 16–17, Table 4 · p. 16

A.4 CRITERIA FOR THE BENCHMARK COMPARISON

• The comparison criteria distinguish rendered-state puzzles, delayed consequences, dead ends, agent-owned recovery, and native GUI actions, properties that LongPuzzleBench combines only in part.LongPuzzleBench has dead ends in Bolt Unscrew and Nut and Bolt, covering 7 of 16 objectives; its self-paced play does not test latency-sensitive control.Source: §A.4 · p. 17, Figure 6 · p. 18

B.1 EPISODE PROTOCOL

• Episodes run for up to 3,600 seconds with no action limit, and success requires evaluator-observed wins on every target level.The clock includes navigation, play, waits, inference, and retries; voluntary exits before completion count as failures, while specified external failures are unscored.Source: §B.1 · p. 18

B.2 ACTION SETTINGS AND AGENTS

• Native GUI Actions restrict agents to coordinate-based inputs, whereas Code Execution CUA permits code between inputs; setting comparisons reflect each full agent system.The settings also differ in tool-integration latency, and GUI-specialized models use a different harness; agents are prohibited from accessing hidden game state or external game information.Source: §B.2 · pp. 18–20

B.3 METRIC DEFINITIONS

• Completion metrics credit observed wins and partial progress, while level pass rate measures the fraction of episodes reaching each target level.Metrics are averaged equally across objectives within games and then across the six games; hard-tier completion excludes Truck Escape, which has a single tier.Source: §B.3 · pp. 20–21
• The 50% level horizon uses eight ten-level objectives; behavioral metrics track premature exits and setting mismatches, while NGAR measures native GUI actions in code-enabled episodes.The horizon is undefined if no target level is reached; NGAR is not reported for Native GUI Actions because every accepted action is native by construction.Source: §B.3 · p. 21

B.4 COMPUTE AND COST

• The 384 episodes used 5.65 billion input tokens and 30.7 million output tokens across 45,997 requests, for an estimated cost of USD 868.The estimate divides into USD 571 for Native GUI Actions and USD 297 for Code Execution CUA; 97.7% of input tokens were cache hits.Source: §B.4 · p. 21

C.1 PER-OBJECTIVE RESULTS

• Kimi-k3’s setting differences vary by objective: Code Execution CUA yields 100% LC on Maze Paint Medium and Color Connect Hard, versus 30% and 40% with Native GUI Actions, but Rush Hour Hard falls from 60% to 0%.Figure 7 reports level completion (%) per objective for the human reference and ten general-purpose backbones in both settings; its groups are ordered by LChard.Source: §C.1 · p. 21, Figure 7 · p. 22
• DeepSeek 4.1 Flash completes Bolt Unscrew Easy and Color Connect Hard only with code, but Nut and Bolt Medium only without it.The reported completion comparisons are 100% against 87.5% and 70% for the first two objectives, and 100% against 66.7% for Nut and Bolt Medium.Source: §C.1 · p. 22
• Figure 7 compares level completion (%) per objective for the human reference and ten general-purpose agents across Code Execution CUA and Native GUI Actions.The difficulty labels are E/M/H for Easy/Medium/Hard, X for Extreme, N for Nightmare, and D for Default.Source: §C.1 · p. 21, Figure 7 · p. 22

C.2 BEHAVIORAL SOURCES OF THE GAP BETWEEN SETTINGS

• 92 of 160 objectives are solved with Code Execution CUA versus 84 with Native GUI Actions, with more levels solved in 38 pairs and fewer in 17.Gains came mainly from episodes that timed out or exited under Native GUI Actions; losses came mostly from voluntary exits under Code Execution CUA.Source: §C.2 · p. 23
• 68.0 s versus 94.0 s is the median time per matched level for Code Execution CUA and Native GUI Actions, respectively.On levels using GUI calls only, calls and inputs are unchanged (1.00) and time falls only slightly (0.94), indicating little speedup from the JavaScript interface alone.Source: §C.2 · p. 23, Table 8 · p. 23
• 20.1% of Code Execution CUA calls issue 56.3% of its executed inputs, often by computing and replaying a sub-plan.A program-generated call issues 13.3 inputs on average, versus 5.8 for a Native GUI Actions batch; board searches and replay loops are recurring patterns.Source: §C.2 · pp. 23–24
• 10 of 11 Native GUI Actions timeouts that Code Execution CUA completes occur when the former episode had reached its last level within 13.2 minutes of the deadline.The Code Execution CUA episodes finish in a median 1,093 s with 94 calls against 268, and 9 of 11 devote at least 20% of calls to computation.Source: §C.2 · p. 24
• Restarts rise from 2.4 to 3.6 per episode under Code Execution CUA, while exits also account for losses and gains across backbones.GPT-5.6-Luna exits in 11 of 16 Code Execution CUA episodes and solves 12 fewer levels than with Native GUI Actions; DeepSeek 4.1 Flash restarts 22 times on Nut and Bolt Medium and times out.Source: §C.2 · p. 24
• Tool latency does not explain the gains: median tool time per call is 0.63 s versus 0.30 s, and model time is 6.9 s versus 6.2 s.Operation-error patterns do not consistently favor either setting, although Kimi-k3’s invalid Maze Paint swipes fall from 20.7% to 2.5%.Source: §C.2 · p. 24

C.3 HUMAN–AGENT TRAJECTORY COMPARISON

• Figure 8 compares Astra’s state transitions with the human’s and tracks boards removed in Bolt Unscrew Hard level 4; the trajectory analysis uses shared puzzle-state variables.The Figure 8 caption states that human and Astra succeed on different puzzles; Table 9 covers visible level 4 and move totals or gestures across other games.Source: §C.3 · pp. 24–25, Figure 8 · p. 25, Table 9 · p. 25

D.1 COMMON DESIGN AND VALIDITY RULES

• Matched diagnostic conditions share the restored state, objective, screenshot, trajectory prefix, interface, and continuation limit, with only the intervention differing.Valid stops, timeouts, ineffective actions, repeated failures, and noncompletion remain outcomes; infrastructure failures are replaced, and repeated actions within a trajectory are not treated as independent samples.Source: §D.1 · p. 26

D.2 RQ1: PROGRESSION AND MOVE-LEVEL MEASURES

• 63.7–80.0% of the completion deficit comes from unreached levels across the ten backbones.Conditional completion after reaching a level ranges from 75.5% (GPT-6-Luna, 37/49) to 99.1% (GPT-6-Astra, 109/110); because levels are won in order, stalling can forfeit later levels.Source: §D.2 · p. 26, Figure 9 · p. 26
• GPT-5.6-Terra leads Qwen3.8 Flash after 15 minutes, 53.6% against 31.5% LC, but finishes lower, 61.3% against 67.2%.Terra ends every unsuccessful episode voluntarily at a median 17.2 minutes, while Qwen3.8 Flash keeps playing.Source: §D.2 · p. 26, Figure 9 · p. 26
• GPT-6-Astra and GPT-6-Sol revisit earlier Maze Paint states in 1.0% and 1.3% of observations, while the three most-revisiting agents complete 50.0–66.7% of levels.GLM-5.3-Flash revisits rarely (7.1%) yet completes 43.3%, with slower play reaching the deadline; Figure 4c bins move counters by prior-state coverage.Source: §D.2 · p. 27, Table 11 · p. 27
• 55 of 73 Bolt Unscrew moves made with one free hole deadlock the board, as do 15 of 17 first moves from one-hole level starts.A fatal move’s stated rationale predicts a release in 28 of 55 cases; the analysis compares free holes, boards exited, and deadlock certificates against a certified solution path.Source: §D.2 · p. 27
• The same-state Maze Paint intervention compares a legal positive-extra-cost move with a legal shortest-path move, while verifying that both successors remain solvable.Three states are tested three times with each of Sol, Terra, and Luna, yielding 27 paired units and 54 continuations compared on same-level completion.Source: §D.2 · pp. 27–28

D.3 RQ2: CERTIFIED DEAD-END TAKEOVER

• The RQ2 takeover study compares ordinary context, truthful state information, and state information plus the restart-button label from matched checkpoints.It includes 24 certified dead-end and 12 solvable checkpoints for the original study; follow-up trials span Bolt Unscrew and Nut and Bolt across three models.Source: §D.3 · pp. 28–29
• Timely restarts improve on 21 of 24 paired dead-end checkpoints and verified recovery improves on 15, with neither outcome declining on any checkpoint.Seven of eight recoveries under A occur after the response window, compared with one of 23 under B and none of 22 under C.Source: §D.3 · p. 28, Table 13 · p. 29, Table 14 · p. 29
• 34 of 45 recovered B/C continuations recur at the certified dead end, 29 after positive progress from the restored board.The median recurrence occurs 128.8 seconds and eight accepted actions after recovery, with 148.5 seconds remaining; the 11 without recurrence also remain unfinished.Source: §D.3 · p. 29
• Across 153 dead-end takeovers, same-level completions remain 0, although state information raises verified recovery in Bolt Unscrew from 7/18 under A to 16/18 under B.The increase remains at 16/18 under C, which adds the restart-button label; all 81 follow-up dead-end continuations remain incomplete.Source: §D.3 · p. 29, Table 15 · p. 29

D.4 RQ3: MATCHED RETRIES WITH MEMORY

• The matched-retry design contrasts cleared history, native history with a restart summary, and equal-capacity history with a structured agent-written failure account.The original Sol panel covers 24 source failures; the follow-up uses six fixed source failures with Sol, Terra, and Luna.Source: §D.4 · pp. 29–30
• 0/24 retries complete in each original memory condition, and follow-up completion is 0/18 in M0, M1, and M2.M2−M1 mean best-progress difference is +0.041 but ranges from −0.091 to +0.409; the data support a null completion effect and unstable endpoints, not a ranking.Source: §D.4 · p. 30
• All 24 M2 failure summaries cite execution or observation problems, and none identifies exhaustion of free holes as the cause.Fifteen summaries resume the failed plan, while none proposes a different plan; source histories sometimes end before the deadlock frame.Source: §D.4 · p. 30

D.5 RQ4: RULE CARD AND WORKFLOW CONTROL

• The original study crosses rule-card presence with workflow control across all 16 objectives, while the follow-up tests four conditions on six objectives across three models.K1 supplies legal interactions and constraints but no level-specific solution; P1 delegates game entry and evaluator-verified advancement while leaving puzzle moves to the agent.Source: §D.5 · p. 30
• RQ4 uses LC as its primary outcome and reports matched effects within objectives, with the follow-up also reporting variation across 18 model–objective units.Figure 10a shows paired LC effects for the rule card and workflow control at each level of the other factor.Source: §D.5 · p. 30, Figure 10 · p. 31
• Under P1, the rule card raises final rule correctness from 52.3% to 81.3% and LC from 62.5% to 65.4%.Without the card, most rules ever stated correctly are first stated after the initial probe; the follow-up measures completion only.Source: §D.5 · p. 30
• Workflow control reduces model actions by 29.4 per session under K0 and 19.1 under K1, but its K×P interaction on LC is +1.0 points.The interaction has standard deviation 19.3 and range [−40, +40], so the controller transfers workflow without a uniform completion gain.Source: §D.5 · pp. 30–31, Table 16 · p. 31

• Every Table 2 completion metric is derived from Table 18 using the game-macro average; unvisited target levels count as zero for LC and FGP.Source: E COMPLETE PER-OBJECTIVE RESULTS · p. 32
• Values are rounded to one decimal place, and |Lo| denotes the number of target levels.Source: E COMPLETE PER-OBJECTIVE RESULTS · p. 32, Table 18 · p. 32
• PER and SMR use all episodes as denominators, while Native counts visual-observation and GUI-input steps and Other counts remaining model-action steps for Code Execution CUA.Source: Table 17 · p. 32
• Table 18 lists each objective’s outcome for every agent and setting, while Table 17 supplies counts underlying Table 2’s aggregate metrics.Source: Table 18 · p. 32, E COMPLETE PER-OBJECTIVE RESULTS · p. 32
• Table 18 marks outcomes as solved (S), premature exit (P), or setting mismatch (M); LC, FGP, and NGAR are percentages, with NGAR applying only to Code Execution CUA.Source: Table 18 · p. 32