Beyond Theorem Proving: Formulation, Framework and Benchmark for Formal
  Problem-Solving
Authors: name: Qi Liu, name: Xinhao Zheng, name: Renqiu Xia, name: Xingzhi Qi, name: Qinxiang Cao, name: Junchi Yan

As a seemingly self-explanatory task, problem-solving has been a significant
component of science and engineering. However, a general yet concrete
formulation of problem-solving itself is missing. With the recent development
of AI-based problem-solving agents, the demand for process-level verifiability
is rapidly increasing yet underexplored. To fill these gaps, we present a
principled formulation of problem-solving as a deterministic Markov decision
process; a novel framework, FPS (Formal Problem-Solving), which utilizes
existing FTP (formal theorem proving) environments to perform process-verified
problem-solving; and D-FPS (Deductive FPS), decoupling solving and answer
verification for better human-alignment. The expressiveness, soundness and
completeness of the frameworks are proven. We construct three benchmarks on
problem-solving: FormalMath500, a formalization of a subset of the MATH500
benchmark; MiniF2F-Solving and PutnamBench-Solving, adaptations of FTP
benchmarks MiniF2F and PutnamBench. For faithful, interpretable, and
human-aligned evaluation, we propose RPE (Restricted Propositional
Equivalence), a symbolic approach to determine the correctness of answers by
formal verification. We evaluate four prevalent FTP models and two prompting
methods as baselines, solving at most 23.77% of FormalMath500, 27.47% of
MiniF2F-Solving, and 0.31% of PutnamBench-Solving.