Arithmetic Reasoning with LLM: Prolog Generation & Permutation

Xiaocheng Yang, Bingsen Chen, Yik-Cheung TamNAACL 2024 · DOI

TL;DR

This paper proposes using Large Language Models (LLMs) to generate Prolog code for solving arithmetic reasoning problems, outperforming traditional Chain-of-Thought (CoT) methods. They introduce a new dataset, GSM8K-Prolog, and a data augmentation technique called PROPER, which leverages Prolog's non-sequential nature to improve LLM robustness.

What Problem Does This Paper Address?

Large Language Models (LLMs) have shown impressive capabilities in various tasks, including arithmetic reasoning, often by generating step-by-step "Chain-of-Thought" (CoT) explanations. However, CoT can be prone to cascading errors as each step relies on the previous one. This paper addresses this by proposing a shift from generating explicit arithmetic steps to generating symbolic logic programs in Prolog. The idea is that an external, deterministic Prolog interpreter can then execute these programs, avoiding LLM-induced calculation errors and leveraging Prolog's inherent strengths in symbolic manipulation.

Methods

The core of the paper's method involves using LLMs to generate Prolog code from natural language math problems. This approach relies on the LLM's ability to extract relevant facts and rules from the problem description and translate them into Prolog predicates. The generated Prolog code is then executed by a Prolog interpreter to obtain the final answer.

A key innovation is the PROPER (Prolog Permutation) technique. Prolog's logic programming nature means that the order of facts and rules doesn't affect the outcome. PROPER leverages this by creating permuted versions of the ground truth Prolog code as data augmentation. This helps LLMs learn to extract predicates more robustly, regardless of their order, and improves their ability to handle the non-sequential structure of Prolog.

Datasets

The authors introduce the GSM8K-Prolog dataset, a new benchmark for arithmetic reasoning with Prolog. This dataset was created by semi-automatically generating Prolog code solutions for problems from the existing GSM8K benchmark using OpenAI's Text Completion API and then manually correcting them. They also used the GSM-HARD dataset, which modifies GSM8K with larger numbers to increase difficulty, for evaluation.

Key Insights and Ideas

  • Prolog as a robust alternative to CoT: Generating Prolog code and using an external interpreter offers a more reliable way to solve arithmetic problems than LLMs generating step-by-step calculations, as it offloads the computation to a deterministic system.
  • Non-sequential nature of Prolog is a strength: Unlike sequential CoT, Prolog's order-independent predicates allow for more flexible and robust learning, especially when augmented with permutation.
  • Data augmentation via permutation is effective: PROPER significantly improves LLM performance by exposing them to different orderings of Prolog predicates, making them less sensitive to input variations and better at capturing the underlying logic.
  • Model-agnostic improvement: The benefits of Prolog generation and PROPER are observed across different LLMs (Llama-2, CodeLlama, Mistral), suggesting it's a generalizable approach rather than being tied to a specific model's inherent reasoning capabilities.

Key Results

  • Prolog generation consistently outperformed the CoT baseline across Llama-2, CodeLlama, and Mistral models on both GSM8K and GSM-HARD datasets.
  • On GSM8K, Prolog generation achieved an average accuracy improvement of 10.9% over CoT.
  • This gap widened to 22.6% on the more challenging GSM-HARD dataset, highlighting Prolog's superiority for complex arithmetic.
  • The PROPER data augmentation technique further boosted accuracy, with a permutation ratio of 1:2 (two permuted samples per original) showing significant gains, especially for Llama-2 and CodeLlama. For instance, Llama-2 saw a 9.5% accuracy increase with this ratio.
  • CodeLlama, pre-trained on code, showed a particularly large performance gain when switching from CoT to Prolog generation.

Limitations and Future Work

  • Corpus Size: The authors acknowledge that the current corpus size might be a limitation, and a larger, more diverse Prolog dataset could lead to even better results.
  • Model Scaling: The impact of scaling LLMs beyond 7B parameters on Prolog generation performance remains an open question.
  • Interpreter Limitations: The reliance on the PySwip library restricts solvable questions to those with integer answers. Future work could explore other interpreters to handle a wider range of numerical outputs.
  • Python vs. Prolog: While Python generation achieved higher accuracy on GSM8K, the authors hypothesize that with sufficient Prolog training data, Prolog generation could match or exceed Python's performance due to its symbolic reasoning strengths.
  • Checkpoint Selection: The paper suggests that choosing checkpoints based on validation accuracy rather than validation loss is crucial for optimal performance, especially when using methods like PROPER, as validation loss can sometimes be misleading due to subtle data leakage.

Summary updated

BibTeX
@inproceedings{yang2024arithmetic,
  author = {Xiaocheng Yang and Bingsen Chen and Yik-Cheung Tam},
  title = {{Arithmetic Reasoning with LLM: Prolog Generation \& Permutation}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2024},
  doi = {10.18653/v1/2024.naacl-short.61},
}
Figure