- 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
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 :)
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: )!
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:
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 (%):
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:
None of these come from arbitrary sampling, and the appendix will give the generation configurations.