The Witness is a game with combinatorial puzzles that are challenging for both human players and AI solvers. Search-based AI solvers can require large amounts of time to solve such puzzles. We accelerate search by automatically learning a predicate that predicts whether a partial path to a Witness puzzle is completable to a solution path. We demonstrate that our learned predicate is human-explainable, which makes it amenable to proofs, and we prove a key property that allows us to use it for pruning successor states in search. Doing so accelerates search by about six times while maintaining search completeness. Conversely, given a fixed time budget per puzzle, our predicate-accelerated search can solve more puzzles of larger sizes than a baseline search using a hand-coded predicate. Finally, we empirically demonstrate how accelerating search using an automatically learned predicate can outperform two competitors, weighted A* and Levin tree search with neural networks, in terms of time and number of nodes expanded.
Figures & tables
Fig. 1: A 1×2 triangle puzzle. The green dashed line solves the puzzle since the solution path intersects the left square once and right square twice, matching the numbers of triangles in their respective squares. The red dotted line is not a solution to the puzzle.
Fig. 2: A partial search tree for solving the puzzle in Figure 1 . The dashed lines show the partial paths for solving the puzzle so far. The two vertex markers ⋆,♡ mark the start and goal vertices of the grid.
Fig. 3: Figure 1 with updated vertex labels.
Predicate
Returns True if
edge(A, B,C)
A is an edge connecting vertices B and C
square(A,B,C)
B is the number of triangles and C is the list of edges around square A
path(A,B)
B is the list of edges in path A
pathHead(A,B)
B is the vertex at the head of path A
count(A,B,C)
the number of occurrences of list A in list B is C , that is ∣A∩B∣=C
len(A,B)
the length of list A is B
TABLE I: Predicate building blocks for the background knowledge given to Popper .
if path.head is not incident to square and puzzle.triangles[square]=3 and path.edges[square]=1: incompletable=True
2
Same except two(F) .
Same except path.edges[square]=2
TABLE II: Output of Algorithm 2 : the predicate π∘ computed over a single constraint.
Speedup Metric
Aπ∗
WA*
NN
speedupt
6.38
1.11
0.02
speedupE
6.27
1.04
0.77
TABLE III: Aggregate Results.
Fig. 4: Time and expansion speedup of π∘ on Ptest .
Fig. 5: A 5×5 puzzle. The vertices are numbered to show the partial path that pruning with π∘ forces Algorithm 1 to take. The two vertex markers ⋆,♡ mark the start and goal vertices.
Fig. 6: Rounded percentage of puzzle instances solved by Algorithm 1 with pruning using πbaseline (above) and with π∘ (below).
Fig. 7: Portion of a puzzle with a partial path for the one(F) case in a red dotted line and for the two(F) case drawn in a blue dashed line.
Fig. 8: Search tree with a policy for solving the puzzle from Figure 1 .
Size
Instances
Expansions
Time (s)
2×2
135
11
0.0005
2×3
1,321
31
0.001
2×4
1,788
72
0.025
3×3
1,012
109
0.004
2×5
1,977
173
0.006
3×4
2,112
401
0.01
TABLE IV: Test-set distribution and mean baseline search costs by puzzle size.
Automated science needs agents that can work out the rules of an unfamiliar environment by interacting with it. Interactive rule-discovery puzzles offer a controlled setting for studying this ability: an agent infers hidden rules through experimentation and uses what it has inferred to reach a stated goal. We ask what limits current language models on these puzzles and whether reinforcement learning (RL) improves performance on rules held out from training. To study both, we introduce WITNESS, a 2D grid-based puzzle environment with ground-truth ASCII observations and controlled access to rules. An agentic pipeline generates games for WitnessGym, the RL training suite, and WitnessBench, comprising public validation and private test games. The validation set separately tests new compositions of trained rule primitives and primitives absent from training. Under a shared harness, the best of 18 frontier proprietary and open-weight models solves only 24% of private test level slots, with scores sensitive to the observation interface and agent configuration. Providing ground-truth rules raises Opus-5's validation RHAE-L5 (relative human action efficiency over the first five levels) from 59.9 to 97.8, whereas a 27B open-weight model gains only 2.1 points and remains limited even with the rules provided. RL on WitnessGym raises the 27B model's private test RHAE-L5 from 2.1 to 5.4 and yields a mean gain of 4.1 points on four external discovery benchmarks. Together, these results point to rule acquisition as a major difficulty for frontier models like Opus-5 while smaller models further struggle on rule-based execution, and indicate that RL on hidden-rule puzzles transfers to broader rules and real-world tasks beyond training. Benchmark is available at: https://witnessbench.ai
Guanghan Ning, Ping Liu, Linyi Li +6
Fleet AI · University of Nevada, Reno · Simon Fraser University +1
Neural solvers are built to deduce, branch, and revise intermediate states. The Lattice Deduction Transformer (LDT) appears to do exactly that. In clue-rich Sudoku, it does not: one forward pass commits essentially the entire grid (every blank cell on standard 6x6, 94-96% on augmented 9x9), turning the iterative solver into a one-shot predictor wrapped in an exact verifier. All hard-slice failures are decided before search begins, when the first pass confidently deletes a value required by the true solution. We call this first-pass poisoning. Adding learned branching, MRV, backtracking, value exclusion, and shared nogoods (CoLT) does not change which Sudoku instances are solved; it cuts repeated invalid derivations 1,497-fold. At the frozen training budget, constraint-graph attention alone matches full-CoLT accuracy, while positional tables recover only under substantially longer training, indicating an optimization and sample-efficiency advantage rather than an absolute capacity difference. The diagnosis predicts two effective interventions. Digit-permutation augmentation raises 9x9 accuracy from below 1% to 96.5 +/- 0.3 across three training seeds on a symmetry-disjoint split. Test-time union over symmetry-transformed passes raises all three hard-slice checkpoints from 72.8-78.9% to 100% without retraining. On from-scratch graph coloring, one-shot behavior disappears and search changes accuracy. In clue-rich completion, LDT-like systems are one-shot amortized predictors rather than learned search procedures: accuracy is determined by calibration and symmetry, while search primarily removes computational waste.
We introduce PuzzleJAX, a GPU-accelerated puzzle game engine and description language designed to support rapid benchmarking of tree search, reinforcement learning, and LLM reasoning abilities. Unlike existing GPU-accelerated learning environments that provide hard-coded implementations of fixed sets of games, PuzzleJAX allows dynamic compilation of any game expressible in its domain-specific language (DSL). This DSL follows PuzzleScript, which is a popular and accessible online game engine for designing puzzle games. In this paper, we validate in PuzzleJAX several hundred of the thousands of games designed in PuzzleScript by both professional designers and casual creators since its release in 2013, thereby demonstrating PuzzleJAX's coverage of an expansive, expressive, and human-relevant space of tasks. By analyzing the performance of search, learning, and language models on these games, we show that PuzzleJAX can naturally express tasks that are both simple and intuitive to understand, yet often deeply challenging to master, requiring a combination of control, planning, and high-level insight.
Sam Earle, Graham Todd, Yuchen Li +5
New York University · University of Malta · University of the Witwatersrand +1