Predicate-Guided Generation for Mathematical Reasoning

Jiajun Chen, Yik-Cheung TamEMNLP 2025

TL;DR

This paper introduces Prolog-MATH, a new dataset of mathematical problems paired with executable Prolog programs, designed to improve the logical reasoning capabilities of Large Language Models (LLMs). They propose a novel two-stage pipeline and a predicate-aware reward function for reinforcement learning, significantly boosting the accuracy and coverage of LLM-generated mathematical solutions.

What Problem Does This Paper Address?

LLMs have shown promise in solving math word problems by generating step-by-step reasoning traces (Chain-of-Thought or CoT). However, these traces are often informal, lack formal semantics, and are not directly executable, making verification difficult. While some approaches generate executable code (e.g., Python), these can be less suited for declarative, compositional reasoning. This paper addresses the need for a structured, verifiable, and executable representation for mathematical reasoning that can be effectively learned by LLMs. They aim to bridge the gap between natural language problem-solving and formal logic.

Methods

The core of the paper is a two-stage pipeline for generating Prolog programs from math problems and their CoT explanations:

  1. Predicate Extraction (Stage 1): An LLM (like Deepseek-V3) is used to predict relevant mathematical predicates (atomic reasoning steps) based on the problem and its CoT. These predicates are then validated and stored.
  2. Program Generation (Stage 2): Another LLM uses the suggested predicates, the problem statement, CoT, and potential answer types to generate a complete Prolog program.

To improve performance on problems the initial pipeline fails, they employ Reinforcement Learning (RL), specifically Group Relative Policy Optimization (GRPO). A key innovation here is the predicate-aware reward function. Unlike standard binary rewards (correct/incorrect), this function provides a more nuanced score based on:

  • Symbolic correctness of the final answer.
  • Structural quality of the generated program (e.g., penalizing unused predicates).
  • Alignment with the suggested predicates from Stage 1.

This reward function encourages not only correct solutions but also compositional and reusable code.

Datasets

  • MATH Dataset: The paper uses the MATH dataset (Hendrycks et al., 2021) as the backbone for its problems and CoT explanations.
  • Prolog-MATH Dataset: This is a newly curated dataset introduced in the paper. It consists of math word problems paired with executable Prolog programs generated by their pipeline. It spans diverse answer types, including complex numbers, equations, intervals, and matrices, going beyond simpler numeric outputs.

Key Insights and Ideas

  • Prolog as a Reasoning Language: The paper strongly advocates for Prolog as a suitable language for mathematical reasoning due to its declarative nature, support for logical inference, and formal verification capabilities.
  • Predicate-Guided Generation: Suggesting relevant predicates before full program generation acts as a powerful guidance mechanism, improving the LLM's ability to construct correct and structured code.
  • Predicate-Aware Reward: The novel reward function is crucial. It allows for more interpretable credit assignment and encourages the LLM to learn not just what to solve, but how to solve it using logical building blocks, promoting reusability.
  • Scalability of GRPO: The GRPO approach with the predicate-aware reward shows significant improvements even when applied to smaller LLMs (e.g., 3B parameters), demonstrating its effectiveness and efficiency.
  • Generalization Across Models: The method shows consistent coverage improvements across various LLM architectures and sizes, highlighting its broad applicability.

Key Results

  • The two-stage pipeline achieves 81.3% solution coverage on the MATH training set.
  • GRPO training with the predicate-aware reward further increases coverage to 97.4% on problems initially missed.
  • The predicate-aware reward function provides a +9.7% coverage improvement compared to a binary reward function on failed problems.
  • Larger and specialized models achieve the largest gains with GRPO, but even smaller models show substantial improvements.
  • Models trained on Prolog-MATH achieve 36.8% accuracy on the MATH-500 test set, outperforming CoT-trained models (33.2%).
  • Human verification indicates high quality: 96% of two-stage pipeline problems and 90% of GRPO-generated programs were mathematically correct.

Limitations and Future Work

  • Incomplete Coverage: While 97.4% is high, 100% coverage is not yet achieved.
  • Syntax Errors: LLMs occasionally produce Prolog code with syntax errors, which can negatively impact generation accuracy. The authors suggest constrained decoding techniques (like VLLM with BNF specifications) as a future direction.
  • Domain Expansion: Future work aims to extend the approach to other mathematical domains and potentially other reasoning tasks.
  • Model Size: GRPO experiments were primarily conducted on models up to 8B parameters; exploring larger models is a future avenue.
  • Imperfect CoT Guidance: Errors in the original CoT can sometimes lead to plausible but incorrect intermediate steps in generated Prolog programs, particularly in number theory and geometry. Future work will focus on stronger logical constraints in predicate design to mitigate this.

Summary updated

BibTeX
@inproceedings{chen2025predicate,
  author = {Jiajun Chen and Yik-Cheung Tam},
  title = {{Predicate-Guided Generation for Mathematical Reasoning}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2025},
}
Figure