A preprint on automated theorem proving reports that learned search policies solved up to 46% more problems than the leanCoP baseline on three benchmark collections, while reaching proofs in an order of magnitude fewer transition steps under a fixed budget. The evaluation covered M2k, MPTP2078-bushy and TPTP v9.2.1 FOF problems under a shared experimental setup.
A learned guide for a formal search
The study asks whether one imitation-learned policy can transfer across problems and work zero-shot on unseen problems — meaning the same policy is applied to a new problem rather than tailored to that case. The system is learning how to steer a proof search while operating inside a defined proof calculus.
At each stage, the policy chooses from valid proof edits in a transition system, the set of allowed moves used to build a structured proof record called a tableau. Those moves produce valid partial tableaux, and a terminal state marked as closed is a checkable closed tableau. Whether the search finds a proof, however, remains a property of the policy or procedure, not of the interface alone.
The choices are scored by a graph neural network, a model designed to work with linked, graph-like structures. The paper compares three learned policies: πmarkov, πdfs and πid. They expose increasingly restrictive action or memory interfaces, creating different balances between search freedom, retention of baseline solutions and the number of steps used.
Training began with closed tableaux from πleanCoP. In proof cloning, the model learned to predict the demonstrated action at each state using supervised cross-entropy loss. In proof aggregation, each new round retrained the scorer on successful proof trajectories found by the current policy. The reported evaluations came after five aggregation iterations.
The comparison used M2k, MPTP2078-bushy and TPTP v9.2.1 FOF problems under a fixed calculus, transition interface and option profile. Each run had a limit of 1,000 transition steps and a 120-second guard, while evaluation was deterministic and used seed 0.
Coverage came with trade-offs
On MPTP cut,comp(7) with early stopping, the policies separated into distinct trade-offs. πdfs solved 363 problems and found 94 solutions the baseline had not found. πmarkov solved 305 and had the shortest successful runs, averaging 11.9 transition steps, but it lost 27 baseline solutions. πid solved 340, lost only one baseline solution and averaged 158.7 steps.
Allowing training to continue to convergence changed the balance. πdfs reached 396 solved problems, including 118 new ones, while losing three baseline solutions and averaging 26.6 steps. πmarkov reached 339 solved, 59 new and one lost at 11.3 steps. πid reached 345 solved, 65 new and one lost at 155.0 steps.
On the same MPTP profile, all three converged policies cleared the baseline from the first aggregation iteration and then levelled off. The reported curve suggests that later rounds produced fewer additional solutions as remaining problems fell outside the gathered proof patterns or the available budget.
What the numbers leave open
Extended fitting also made the scorer fit its demonstrations more closely: mean training accuracy was 0.975 with five-epoch stopping and 0.995 after retraining to a 100% target or 200-epoch cap. These are training figures, and the analysis reports no held-out validation set, so they are not a direct measure of transfer to unseen problems.
The strongest caveat is the information supplied to the learner. The imitation signal labels only successful proof paths; undo actions and states that never appear on those paths are unlabeled. That leaves open whether training on failed search traces could improve decisions about when to undo or backtrack.
The headline comparison is bounded by the experiment’s design. The policies were tested under fixed step and time limits on the named corpora, and the reported analysis gives no uncertainty interval, denominator or repeated-run variability for the 46% figure. The study therefore describes observed benchmark coverage and search effort under those conditions, rather than establishing performance beyond them.
A preprint with code
The document is identified as arXiv:2608.26009v1, dated 26 Aug 2026, and is a preprint. It also provides code at https://github.com/fredrrom/connections. Taken together, the results point to a way of learning search control inside a checkable proof interface, while illustrating that coverage, proof retention and search length vary with the structure allowed by each policy.
Paper data and sources
Original title: Imitation Learning for Connection-Tableau Construction
Authors: Fredrik Rømming, Mantas Bakšys, Martin S. Fixman, Sean B. Holden
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-26
DOI: Not available
Original paper · Full text