acceptodds
Under review as a conference paper at ICLR 2027

WordBench: A Benchmark for Learning and Search in Algebraic Word Problems

Abstract

Mathematical discovery systems increasingly combine large language models (LLMs), reinforcement learning (RL), and formal verifiers, yet most mathematical benchmarks remain static collections of problems. We introduce WordBench, a benchmark for algebraic word problems that combines procedurally generated datasets with executable search environments and exact verification. A word problem asks whether finite symbolic expressions, or words, represent the same mathematical object under specified generators and relations. An open example is the Andrews–Curtis conjecture, where a successful certificate is a sequence of allowed presentation moves transforming a relator tuple to the trivial presentation. WordBench contains 24 families spanning rewrite and witness-construction problems, each with generative datasets, a deterministic symbolic search environment, and exact verification of submitted traces, action sequences, or algebraic objects in the Lean theorem prover. The released corpus, WordBench-Lit, contains instances, and the underlying data generators can produce fresh instances beyond this set. We benchmark classical breadth-first search, PPO agents, and LLMs under common verifier-defined success criteria. The results reveal strongly solver-dependent empirical difficulty: for example, PPO solves % of instances on Thompson's group while some open-source LLMs remain below %, whereas frontier LLMs achieve near-perfect performance on Artin–Tits and braid rewriting, where PPO remains below %. More broadly, frontier LLMs solve a large fraction of WordBench-Lit, but performance remains nonuniform across families, with Andrews–Curtis being substantially less solved. Beyond benchmark performance, WordBench's environments enable controlled experiments on search behavior, learning dynamics, and empirical relationships across mathematical problems. As a case study, we find that cross-family PPO transfer learning can solve new dataset instances not discovered by target-only training, with different source families providing complementary coverage. Together, these results position WordBench as a common verifier-facing benchmark for studying learning and search across diverse mathematical word problems.

Primary area:
datasets and benchmarks
Keywords:
AI for Mathematics, Mathematical Reasoning, Neurosymbolic Reasoning, Reinforcement Learning, Formal Methods, Lean.

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_kcPHOpenReview ↗
Rating
2(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

WordBench is a benchmark for mathematical search problems. Imagine a shuffeled Rubic's cube - finding the sequence of actions needed to solve it is an example of such a search problem. The paper uses this and 23 other problem families - totaling 13K+ challenges. The setting is based on RL - each problem is coded as an environment with specific possible actions and a verifiable final goal. It is tested on 3 types of action decision sources - BFS, shalow PPO (2 layers, width 256), and several LLMs (which pick actions out of the same setting - don't rewrite anything themselves). Results vary across the different methods, LLMs and types of problems.

Critical strengths
  • Benchmarks based on generative, verifiable problems are important both to combat benchmark contamination and to allow the benchmark level to be adaptable to new and stronger models.

  • A broad collection of math categories are being used, while maintingn the same conceptual structure an RL challenge.

Critical weaknesses
  • The treatment of PPO seems wrong. 1) Its performance is measured by reaching relevant states during exploration in training - why? Especially in a setting where you, allegedly, can easily generate new problems - why not test on newly generated challengens from the same family?. 2) 2-layer, 256 width, is not a representative modern network. It is highly likely that some of the failures should be attribnuted to the choice of specific architecture - not the PPO algorithm itself. Especially given the families where BFS considerably outperforms PPO - hints at an implementation issue. Considering these issues, I'm not entirely certain why do you need to include a PPO-only baseline at all? When math problems are attempted via a combination of LLMs + RL - it is done not via a simple PPO shallow net anyway, so what does this baseline give us? I believe DeepCubeA - which you cite - used RL but also included basic A* search. It is not common to use "naked" RL for math problems these days.

  • Data choice and analysis. Why are there such large discrepencies in the size of different families? Since they range from 30 to 1190 - how did you choose sizes? Since Astra saturates all families, except for the open AC, could you increase the challenge level as you claim to be able to? It would be a good result to show that at this level frontier models saturate the benchamrk, but then you increase, e.g., the scrambling depth and it becomes once again a useful measurement. As it stands, your data shows the opposite.

Questions for authors

Is the critism about soft judges (e.g. LLMs) or the concept of a perfect final answer doesn't determine (or check) the path to achieving that answer? If it's the second, your setup obviously solves the issue by construction - but doesn't measure the performance of any of the methods regarding this question.

There are some (presumably) AI leftovers. E.g.: "but timeouts are not theorems" Many entries have duplicate years in the bibliography.

5 comments
AuthorsOpenReview ↗

Response to Reviewer kcPH (1)

Thanks for the direct critique. It pushed us to run several of the experiments below, and the paper is better for it.

PPO evaluation and generalization. We count PPO by the instances it solves during training because WordBench is about solution discovery. For an open problem such as Andrews–Curtis, a valid solution found during training settles that instance, and there is nothing to gain from finding it again at test time; Shehper et al. evaluate the same way. That said, your point about generalization is a fair one, so we also evaluated the final PPO policies on the released instances and on fresh instances generated with new seeds and deduplicated against WordBench-Lit, counting a success only on a single attempt. Testing success rates (%), averaged over three seeds:

FamilyReleased instancesFresh instances
Free-group word99.987.5
Small-overlap monoid word100100
Baumslag–Solitar BS(1,2)100100
Gröbner normal form99.876.8
Thompson's group F96.178.0
Heisenberg collection93.575.0
Whitehead free group92.329.7
Small-cancellation word99.825.8
Makanin word equations77.616.8
Coxeter type A51.221.3
Subgroup membership34.55.8
Free-group conjugacy22.54.8
Graph-product word13.61.0

The picture is mixed. PPO generalizes well on six families and poorly on the rest, which is the gap between discovery during training and generalization to unseen problems. Fresh-instance testing covered 17 families; the table leaves out Burau B4 search, braid rewriting, KBMAG and knot equivalence, where PPO solves almost nothing on either set. The other families have no fresh instances to test, either because their instance space is already exhausted under the current PPO configuration (e.g., instances must be solvable within the trained horizon) or because there is no generator (e.g., Rubik's cube). The appendix will spell this out.

PPO architecture. Fair point, and we agree that shallow PPO isn't a state-of-the-art approach to mathematical reasoning. We keep it because it is cheap, runs unchanged on every environment, and is not as weak as it looks: on Thompson's group F (updated Table 2), PPO-10M reaches 99.1% against 2.4% for Qwen3-235B, 2.2% for DeepSeek V3.2 and 6.8% for Kimi K3, and on Whitehead free group 97.9% against 29.0%, 32.6% and 56.6%.

Whether the small network is the bottleneck still deserved a direct test. We trained two larger architectures with the same PPO algorithm, environments, rewards and budget: a residual LayerNorm MLP (1024 × [1024, 1024, 1024]) and a 4-layer transformer over the observation tokens, each with about 6.5M parameters against 0.32M for the 2×256 baseline. Overall results across the 23 retained families (%):

ArchitectureTraining coverageTesting success rate
Baseline MLP, 2×256 (3 seeds)49.4 ± 1.743.9 ± 1.4
Residual MLP (3 seeds)48.7 ± 1.542.5 ± 1.9
Transformer (1 seed, preliminary)48.310.4

More parameters do not help overall in this setting, although the residual MLP does improve some families, including Andrews–Curtis. We also checked for an implementation issue. A local rerun of a recorded configuration lands within the spread of its three seeds, and at a matched budget our PPO solves the same range of Miller–Schupp presentations as the implementation of Shehper et al. (see our reply to cZ3m, Q4). On search, the comparison you suggest is now in the paper as well: besides BFS we report greedy best-first search, an A*-style best-first search on g + h, beam search and MCTS (reply to cZ3m, "Other search baselines"). We will add a per-family analysis. The environments are open to stronger methods, including LLMs combined with RL and other search algorithms as you suggest, and we see those as valuable next steps.

Dataset sizes. Each size has a specific reason:

  • Andrews–Curtis (1,190): uses the full Miller–Schupp dataset (n ≤ 7, |w| ≤ 7), consistent with prior work by Shehper et al.
  • Rubik's cube (1,000): uses distance-20 states from the established Cube20 dataset.
  • Kaplansky group rings (30): includes all 30 cyclic orders (n = 2, …, 31) supported within the configured 64-step episode horizon.
  • Finite permutation action (59): fully enumerates the alternating group A₅, which contains 60 elements, with the identity excluded to yield 59 nontrivial evaluation instances.
  • Path-RAAG (64): includes all distinct instances generated within the configured bounds.

None of these come from arbitrary sampling, and the appendix will give the generation configurations.

AuthorsOpenReview ↗

Response to Reviewer kcPH (2)

Increasing the challenge level. We ran exactly this experiment, and the curve comes back: see our reply to cZ3m, Q5.

Q1: Solution verification. Both, and WordBench handles both. A solution is a sequence of actions that is replayed in the environment and, for every accepted trace, also checked in Lean, so a correct final answer reached through an invalid step is rejected. Because the domain is verifiable, no LLM judge is involved anywhere, and the evaluation measures the solvers rather than the verifier.

Q2: Editing. Thank you for catching these. The revision rewrites that sentence and fixes the duplicated years in the bibliography.

We have also summarized all the changes in our general comment to the AC and reviewers, which might be a quicker overview of everything new. We hope these results address your concerns, and we would be grateful if you would consider increasing your score. Thanks again for the careful read :)

AuthorsOpenReview ↗

Response to Reviewer kcPH (3)

Dear Reviewer kcPH,

Since today is the last day of the discussion period, we wanted to follow up briefly. We know this is a busy week, and we would be very grateful if you could take a look at our responses above and at the revised PDF, where every change is marked in blue: )!

Reviewer_FGMkOpenReview ↗
Rating
2
Confidence
1
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

an algebraic word problems bench that can be used in RL envs for llms.

Critical strengths

The paper proposes carefully crafted questions for llms to explore in a traditional rl formulation.

Critical weaknesses

The bechmark is already well-solved for top-tier LLMs, the futural application/direction proposed in the paper is limited thereafter.

Questions for authors

How well is the generalization for the dataset to some other similar logic fields, e.g. BFS/DFS problems in some industrail scenarios? I think such evidence should be very strong for the paper.

1 comment
AuthorsOpenReview ↗

Response to Reviewer FGMk (1)

Thanks for the review!

Q1: Saturation for top-tier LLMs. That is true of the released set, and it is why we built harder levels, at 2x to 256x the released difficulty with 128k output tokens for every model (details in our reply to cZ3m, Q5):

  • Astra solves 1 of 100 graph-product and 6 of 100 braid instances at 256x.
  • Opus 5.5 solves 4 of 100 on graph product at 64x.
  • DeepSeek V3.2 is at 0 from 32x on most families.

In other words, the generators that produced WordBench-Lit can also produce instances that frontier models fail on. Every level is certified solvable, and the levels can be pushed deeper as models improve.

Q2: Generalization to other fields. WordBench targets AI for mathematics on purpose, because there every answer can be checked exactly. Nothing in the interface is specific to algebra, though: any problem with states, moves and a checkable goal fits it, and the search methods we now compare (BFS, greedy best-first, best-first on g + h, beam search, MCTS) are standard in many fields. Industrial instances themselves are outside the scope of this paper, though we see them as a natural next step for the community. Hope this helps :)

Reviewer_cZ3mOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

WordBench is a benchmark of 24 algebraic word-problem families (Thompson's group F, braid groups, Andrews–Curtis, Rubik's cube, Gröbner bases, among others), each packaged as a deterministic search environment with a procedural instance generator, a replay-based verifier, and a Lean formalization. The released corpus, WordBench-Lit, has 13,324 instances. The authors benchmark BFS, PPO agents, and five LLMs under a common verifier-defined success criterion. The headline finding is that difficulty is strongly solver-dependent: PPO reaches 99.1% on Thompson's F while open-source LLMs stay below 10%, whereas on Artin–Tits and braid rewriting frontier LLMs are near-perfect and PPO is below 1%. Overall: BFS 62.4%, PPO-10M 52.9%, Astra 94.8%, Opus 5.5 88.2%; Andrews–Curtis remains the least solved (Astra 45.9%). A cross-family PPO transfer case study is also included.

Critical strengths
  1. The contribution is a research platform rather than a static problem set: a generator, an environment, and a verifier are provided for every family, so the benchmark can be regenerated and extended rather than memorized. This is the right design for studying whether AI systems can do rigorous mathematics with every step checked, and the topic is timely and important.

  2. The solver-dependent difficulty pattern is genuinely informative. PPO and LLMs succeed on nearly disjoint sets of families (Thompson's F vs. Artin–Tits, braids, Rubik), an empirical observation that a single-method benchmark could not have produced.

Critical weaknesses
  1. The paper's two selling points, exact verification and Lean grounding, are contradicted by its own appendix. (a) Verification is not uniform. Appendix G.19 states that the Burau matrix-equality family is scored by matching a submitted Boolean against a stored label, without recomputing the matrix. This makes it a two-way classification task on which BFS trivially reaches 100% by expanding both SUBMIT actions, yet Table 1 and Table 5 still list it as a rewrite task. (b) The Lean claim overreaches. The abstract says traces are verified "in the Lean theorem prover", but Appendix E.2 says submitted solutions were not compiled as Lean proofs, and G.12 and G.21 say the Lean decoder is not aligned with the environment interface for some families. No table states which families have end-to-end Lean replay or how many reported solutions were actually checked. Since these two properties are what distinguish WordBench from existing suites, this gap goes to the core of the contribution.

  2. Baseline fairness. BFS is given only 500 expanded nodes on Artin–Tits versus 100k elsewhere, so the reported 0% there is a budget artifact rather than evidence about the problem. No MCTS, A*, or beam-search baselines are included even though the cited prior work (DeepCubeA, AC-Solver) uses search plus learning, and there is no comparison to Shehper et al.'s numbers on what appears to be the same Miller–Schupp dataset. The LLM prompts are not provided, so the LLM-vs-PPO contrasts cannot be attributed to reasoning ability rather than to the observation encoding.

A further concern is saturation and reproducibility: Astra is at 100% on 21 of 24 families and no harder split is offered; LLM results use provider-default sampling with no seeds at a cost of roughly $10k, so they cannot be reproduced. Because instances are guaranteed solvable by construction, the paper also needs to rule out shortcuts through the generation rules or data distribution, and to show that difficulty can be scaled.

Questions for authors
  1. For each of the 24 families, which have end-to-end Lean replay of accepted traces, and how many of the solutions reported in Table 2 were actually compiled in Lean? (Clarification; this materially affects my assessment.)
  2. Please re-score or remove the Burau matrix-equality family given the label-matching verifier in G.19, and confirm that no other family is scored against stored labels.
  3. What happens to BFS on Artin–Tits with the same 100k-node budget used for the other families?
  4. Can you provide the full LLM prompts, and a comparison with Shehper et al. on the shared Miller–Schupp instances?
  5. How do you propose to scale difficulty beyond WordBench-Lit, given that frontier models already saturate most families? (This is partly a suggestion for future work, but a concrete plan would affect my view of the benchmark's longevity.)

Overall I like the direction. If the per-family Lean status is made explicit, the verifier is made consistent across families, and the baselines are run at equal budgets, I would be glad to raise my score. At present the claims in the abstract and the implementation described in the appendix do not match.

5 comments
AuthorsOpenReview ↗

Response to Reviewer cZ3m (1)

Thank you so much for such a careful reading of the appendix! Honestly, most of the experiments below came straight out of this review, and the three changes you asked for (explicit per-family Lean status, a consistent verifier, and equal-budget baselines) are all done.

Q1: End-to-end Lean replay. All 23 retained families now have it, and every accepted trace behind the updated Table 2 was compiled: 69,788 traces from all five LLMs and all PPO seeds, with zero failures. Each family has a Lean checker that replays a solution under the environment's rules, plus a sorry-free soundness theorem showing that an accepted solution implies the family's mathematical statement, such as equality in the presented group or AC-equivalence to the trivial presentation. Each trace then becomes its own kernel-checked theorem, using only the standard axioms. To make sure the Lean checkers really match the Python environments, we compared the two on 366,708 differential-test cases and found no disagreement. This also settles the decoder mismatch described in Appendices G.12 and G.21: the new checkers follow the environment interface itself, and the appendix text will be corrected accordingly.

FamilyStatement proved for each accepted traceTraces compiled
Andrews–CurtisAC-equivalence to the trivial presentation1,671
Artin–Titsequality in the Artin group1,970
Baumslag–Solitar BS(1,2)the word is 1 in the presented group3,770
Braid word rewritingequality in the braid group1,724
Burau B4 searchβ(w) = β(w⋆) for the submitted word w920
Coxeter type Aequality in the type-A Coxeter group3,351
Finite permutation actionthe target is in the orbit of the start1,896
Free-group conjugacythe two words are conjugate in the free group2,849
Free-group subgroup membershipmembership in the generated subgroup3,337
Free-group wordequality in the free group3,978
Graph-product wordequality in the right-angled Artin group3,027
Gröbner normal formf − r lies in the ideal and r is irreducible7,894
Heisenberg collectionequality in the Heisenberg group4,731
Kaplansky group ringsnonzero α, β with αβ = 0 in F₂[Cₙ]1,876
KBMAG rewritingsame element of D₈ or Q₈, target is the normal form2,387
Knot equivalencethe two braids are conjugate in B₄4,077
Makanin word equationsa non-erasing substitution solves the equation3,967
Path-RAAG wordequality in the RAAG793
Rubik's cubethe goal is in the orbit under the face-turn group1,837
Small-cancellation wordthe word is 1 in the presented group3,366
Small-overlap monoid wordequality in the presented monoid3,967
Thompson's group Fthe word is 1 in Thompson's group F2,692
Whitehead free groupan automorphism maps u to v3,708
Total69,788

Three of these statements are slightly weaker than Table 1, and the paper will say so. For knot equivalence we prove braid conjugacy, which implies isotopy of the closures, instead of formalizing isotopy directly. For Gröbner normal form, Lean checks that f − r lies in the ideal generated by G and that r is irreducible, while the Gröbner-basis property of G is checked in Python. For Thompson's group F, Lean proves through a normal-form certificate that the scrambled word times the solution is the identity in the two-relator presentation of F; the faithfulness of the tree-pair representation used by the environment is not formalized.

Q2: Burau matrix-equality. Good catch, and this is now resolved: the family is removed from the benchmark and from every result. It was originally designed to let RL agents explore rewriting before deciding matrix equality, but as you point out, methods such as BFS can skip the rewrite search entirely. Before removing it we double-checked the data. All 500 stored labels agree with an exact recomputation of the Burau matrix, and the LLM grader had always recomputed the matrix instead of reading the label. No other family is scored against stored labels: the 23 that remain are rewrite or witness-construction problems, each verified by replaying the solution path.

AuthorsOpenReview ↗

Response to Reviewer cZ3m (2)

Q3: BFS on Artin–Tits at 100k nodes. Short answer: it still solves 0 of 1,000, and the reason turned out to be more interesting than the budget. The original 500-node limit came from cost, since the family has 30,464 actions. With our original implementation, BFS took 12.2 hours for 500 nodes on one CPU, which projects to about 102 days for 100k nodes. So we wrote a successor function that enumerates only the applicable moves instead. It agrees with the environment on 1,048,576 random state–action pairs and is about 100 times faster, which made the full budget feasible.

Within 100k expansions, BFS reaches only depth 2 to 3, while known solutions have median length 21. Greedy best-first search with word length as the heuristic solves all 1,000 instances, with a median of 21 expansions. The 0% therefore comes from the branching of uninformed search, not from the budget.

Along the way we found and fixed a crediting bug in our BFS code: successes on Artin–Tits and on free-group conjugacy were not being credited. BFS now solves all 500 conjugacy instances (0% in the submission), and the updated Table 2 will use the corrected BFS.

Q4: LLM prompts. Yes. The revised appendix will list the full prompt for all 23 families. They share one system prompt, which differs only in the horizon and the range of action IDs, followed by a common note on indexing and invalid moves. Here is the Andrews–Curtis example (horizon 64, 14 actions), verbatim.

System prompt:

Solve the mathematical task below. You have no tools or intermediate environment feedback.
Return one complete action sequence in execution order as your final JSON object
{"actions":[0,1,...]}. You may reason before it. Use at most 64 actions;
every action must be an integer in 0..13. Replay stops on termination or
the step limit. If the input is already solved, an empty list is allowed
only for tasks that do not require explicit submission. Do not return
alternative candidate answers. If asked to continue because a response
reached its token limit, continue the same attempt and eventually return
the complete action list.

Common user prompt prefix:

All positions and action IDs below are zero-based. Positions refer to
the current state after previous actions. An invalid move leaves the
state unchanged and still uses one step. Signed generator -i denotes
the inverse of generator i. Free reduction means repeatedly cancelling
adjacent inverse pairs; perform it automatically only when the task
explicitly says so.

User prompt (Andrews–Curtis):

Task: Apply Andrew–Curtis moves to reach the trivial presentation
(all relators are single generators).
Step 1/64.
Generators: x1, x2
R1: x1^-1 x2 x1 x2^-1 x2^-1
R2: x1^-1 x2
Choose action_id in 0..13.
Success requires two singleton relators with distinct absolute
generator IDs {1,2}. Every accepted move freely and cyclically reduces
the relators (repeatedly cancel inverse first/last letters). A move
whose freely reduced intermediate relator exceeds 36 letters is ignored.
Success terminates automatically.

Q4: Comparison with Shehper et al. Thanks for suggesting this, it turned out to be a really nice sanity check of our environment. Their greedy search, run with their settings on our Andrews–Curtis environment, solves exactly the 533 presentations they report, with certificates identical move for move. Their BFS count of 278 also reproduces exactly once cyclic reduction is enabled, as in their released code.

For PPO, we trained our baseline (two hidden layers of width 256, our reported hyperparameters) on the shared 1,190 presentations for 10⁸ environment interactions with five seeds, and read off the replay-verified count at 8×10⁷ interactions, the budget of their five-seed study:

  • Shehper et al. (MLP with two hidden layers of width 512): 323 to 354 presentations across five seeds (mean 334.4, i.e. 28.1%; best 29.7%).
  • Ours: 213 to 366 presentations across five seeds (mean 299.0, i.e. 25.1%; best 30.8%). At 10⁸ interactions the range is 215 to 366 (mean 302.2).

All five of their runs fall inside our range, so the solve rates are consistent.

AuthorsOpenReview ↗

Response to Reviewer cZ3m (3)

Q5: Scaling difficulty beyond WordBench-Lit. We see this as the key question for the benchmark's longevity, so we ran it in full. We built new levels at 2x to 256x the released difficulty by increasing word length, scramble depth or rewrite depth, with 100 instances per level. Each instance is certified solvable by its generator certificate and deduplicated against WordBench-Lit. We then evaluated the two strongest models on WordBench-Lit, Astra and Opus 5.5, together with DeepSeek V3.2, each with a 128k output-token budget. Solved out of 100 (Astra / Opus / DeepSeek):

Family8x16x64x256x
Graph-product word98 / 90 / 0100 / 63 / 075 / 4 / 01 / 0 / 0
Braid word rewriting100 / 98 / 5100 / 88 / 090 / 49 / 06 / 0 / 0
Coxeter type A100 / 98 / 45100 / 96 / 198 / 86 / 080 / 13 / 0
Artin–Tits98 / 79 / 084 / 34 / 0n/an/a
Thompson's group F100 / 98 / 0100 / 92 / 0n/an/a
Heisenberg collection100 / 97 / 36100 / 97 / 8100 / 93 / 0n/a
Finite permutation action100 / 100 / 8100 / 99 / 099 / 95 / 0n/a
Makanin word equations100 / 98 / 82100 / 98 / 59100 / 95 / 48n/a

The drop is steep. On graph-product word, Astra falls from 98 at 8x to 1 at 256x, and Opus from 90 to 0. On braid rewriting, Astra goes from 100 to 6 and Opus from 98 to 0. DeepSeek reaches 0 already at lower levels on several families.

Classical search doesn't simply take over at these depths either, which we found reassuring. Greedy best-first search, capped at 30 CPU minutes per instance, solves every sampled instance up to 64x on seven of the eight families, but only 9 of 29 sampled instances beyond 64x. At those depths Astra still solves 60 of 100 braid instances at 128x and 80 of 100 Coxeter instances at 256x.

Scaling is family-dependent, and we will be explicit about where it is limited. Artin–Tits and Thompson's group F stop at 16x because of environment and prompt limits, and Heisenberg collection stays easy as depth grows. We will release the levels as WordBench-Hard with their generator configurations and results, and they can be pushed further as models improve.

Other search baselines. Beyond BFS, we added greedy best-first search, best-first search on g + h (g is the path length and h a size heuristic such as word length), beam search of width 1,000, and MCTS (UCT). The first three use 100k expanded nodes per instance; MCTS uses up to 100k tree nodes or 30 CPU minutes. Following Shehper et al., we expected greedy best-first to be strong, and it is: it solves every evaluated instance in 17 of the 23 families, including Artin–Tits, braid rewriting, KBMAG and Thompson's group F, where PPO or the LLMs struggle. MCTS, run on fixed samples of every family, solves every sampled instance in 16 families but does worse on hard ones such as Andrews–Curtis (16/50) and Artin–Tits (0/10). Both results point the same way: which families are hard depends on the solver, and there is room for learning and reasoning methods to improve. These results will go into the appendix.

Reproducibility. We will release the prompts, model identifiers, effort settings, token budgets, all raw model responses and the grader, and replaying every LLM answer independently reproduces the updated Table 2 with zero disagreements. Temperature was left at the provider default and closed APIs do not expose seeds, but anyone can rerun the open-weight models (Qwen3, DeepSeek V3.2, Kimi K3). To gauge sampling noise, we ran five attempts on a matched subset of 1,805 rows (on an earlier environment release): pass@1 and pass@5 differ by only 0.8 points for Astra and 1.6 points for Opus.

Shortcuts. We checked for these explicitly. Every harder level comes with two trivial baselines, a uniform random policy and length-decreasing greedy descent, and at the deepest levels they solve 0 to 2 of 100 instances, with one exception: greedy descent on Heisenberg (64). The checks did find real shortcuts, and we report them. On Burau matrix equality, answering YES exactly when the exponent sum is zero scored 95 to 99%, one more reason to drop that family. Textbook algorithms solve graph product (RAAG reduction followed by sorting) and Heisenberg (collection) at every level, so their deep levels test long execution rather than search.

To summarize: the per-family Lean status is now explicit (Q1), the verifier is consistent across families (Q2), and the baselines run at equal budgets (Q3, Q4). We hope this addresses your concerns, and we'd be grateful if you would consider raising your score. Thanks again, this review made the paper a lot better :)

Comments on the paper

1 comment
AuthorsOpenReview ↗

Response to AC and reviewers

We thank the AC and reviewers for their feedback. In response to the reviews, we conducted additional experiments and addressed the main concerns regarding verification, baseline comparisons, benchmark difficulty, and PPO evaluation. We have uploaded a revised PDF that includes all of these results, with every change marked in blue. Table 2 is updated with the audited reruns described below (PPO from three seeds on the final environments with every certificate replayed, and the LLM columns from the runs whose traces we compiled in Lean), and the Table 2 numbers we cite in these responses are the updated ones. We summarize the key updates below:

  • Verification and soundness: We confirmed end-to-end Lean verification across all 23 retained families, compiling all 69,788 accepted traces behind the updated Table 2 with zero failures (Section 3.3 and Appendix F). We also removed the Burau matrix-equality family and corrected the baseline results.
  • Scaling difficulty: We generated harder instances at difficulty levels up to 256× the original settings. Even the strongest-performing models on WordBench-Lit show substantial performance degradation on several families, demonstrating that WordBench can continue to challenge frontier models as they improve (Section 5.2 and Appendix L).
  • Additional baselines: We evaluated greedy best-first search, best-first search on g + h, beam search, and MCTS (Appendix I), reproduced the search results of Shehper et al. exactly on our environment, and ran a matched-budget PPO comparison with them (Appendix J).
  • PPO evaluation: We additionally evaluated final-policy testing performance, generalization to freshly generated instances, and larger network architectures (Appendix K). These experiments clarify the distinction between solution discovery and policy generalization.
  • Prompts: The full LLM prompts for all 23 families are in Appendix M.

We believe these additions strengthen WordBench as a benchmark for mathematical reasoning and search across diverse problems and methods.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.