Enhancing LLM Reasoning Through Prolog: A Breakthrough in Symbolic Logic Processing

This article details why I built a prolog code interpreter for dynamic natural language rule definition applied to natural language scenarios. It works by converting the natural language rules into prolog, converting the scenario into a prolog query in the context of the prolog program, getting the prolog answer, and interpretation back to natural language.

Using an exerpt from a natural language rules example regarding airline passengers, payments, and checked baggage fees.

    - Passengers: Each reservation can have at most five passengers. The agent needs to collect the first name, last name, and date of birth for each passenger. All passengers must fly the same flights in the same cabin.
    - Payment: each reservation can use at most one travel certificate, at most one credit card, and at most three gift cards. The remaining amount of a travel certificate is not refundable. All payment methods must already be in user profile for safety reasons.
    - Checked bag allowance: If the booking user is a regular member, 0 free checked bag for each basic economy passenger, 1 free checked bag for each economy passenger, and 2 free checked bags for each business passenger. If the booking user is a silver member, 1 free checked bag for each basic economy passenger, 2 free checked bag for each economy passenger, and 3 free checked bags for each business passenger. If the booking user is a gold member, 2 free checked bag for each basic economy passenger, 3 free checked bag for each economy passenger, and 3 free checked bags for each business passenger. Each extra baggage is 50 dollars.        

[QUESTION]: Verify that a reservation with the following three passengers: Alice Johnson (born 1985-07-07), Bob Smith (born 1986-08-08), and Carol Danvers (born 1987-09-09) who are all booked on flight AA101 in Economy cabin, uses 0 travel certificates, 1 credit card, and 3 gift cards and that for a silver member traveling in Economy, booking total of 5 checked bags, Return the combined query to check for valid passengers, valid payment, and the proper baggage fee.

[INFO] Executing Prolog query: validate_passengers(
    [ passenger('Alice','Johnson','1985-07-07','AA101',economy),
      passenger('Bob','Smith','1986-08-08','AA101',economy),
      passenger('Carol','Danvers','1987-09-09','AA101',economy)
    ],
    PassResult
),
validate_payments(
    [ payment(credit_card, cc1),
      payment(gift_card, gc1),
      payment(gift_card, gc2),
      payment(gift_card, gc3)
    ],
    user,
    PayResult
),
free_checked_bags(silver, economy, FreeBags),
extra_bag_cost(Price),
ExtraBags is 5 - FreeBags,
BaggageFee is ExtraBags * Price,
BaggageFee =:= 150.

[INFO] Prolog results: [{'PassResult': 'True', 'PayResult': 'True', 'FreeBags': 2, 'Price': 50, 'ExtraBags': 3, 'BaggageFee': 150}]

[FINAL ANSWER] 
The reservation for the passengers Alice Johnson, Bob Smith, and Carol Danvers on flight AA101 in the Economy cabin is valid. The payment method used, which includes one credit card and three gift cards, also meets the requirements. Additionally, as a silver member traveling in Economy, you can check 2 bags for free. Since a total of 5 bags are being checked, there is an additional cost for 3 extra bags, which amounts to $150. Everything regarding the reservation, payment, and baggage fees is in proper order.        

Large Language Models (LLMs) have demonstrated remarkable capabilities across numerous domains, yet their reasoning abilities—particularly with complex logical rules—remain an area for improvement. Recent innovations combining LLMs with Prolog, a logic programming language, represent a significant advancement in artificial intelligence reasoning capabilities. This integration offers a powerful new approach to processing and reasoning about natural language rules, potentially transforming how machines understand and apply human logic.

The Power of Prolog for Logical Reasoning

Prolog, short for "Programming in Logic," was specifically designed for symbolic reasoning and logical inference. Unlike procedural programming languages like Python or Java, Prolog is declarative, meaning it focuses on what needs to be computed rather than how to compute it. This fundamental distinction makes Prolog particularly well-suited for representing and processing rules expressed in natural language.

Prolog operates on a knowledge base composed of facts and rules, using a reasoning mechanism called backtracking that automatically explores possible solutions. This approach aligns naturally with how humans express logical relationships and conditions in everyday language, making it an ideal intermediary between human-expressed rules and machine reasoning.

The English-to-Prolog-to-English Pipeline

The integration of Prolog with LLMs creates a powerful pipeline for reasoning about natural language rules:

1. Rule Extraction: LLMs process natural language text and identify logical rules and facts
2. Prolog Codification: These rules are translated into Prolog code snippets that represent the logical relationships
3. Execution: A Prolog interpreter evaluates the code to determine logical conclusions
4. Translation: Results are converted back into natural language responses that address the original query

For example, when presented with natural language statements like "Every human is mortal" and "Socrates is a human," the LLM can convert these into Prolog rules such as mortal(X) :- human(X) and human(socrates). The Prolog interpreter can then answer queries like "Is Socrates mortal?" through logical deduction rather than pattern matching or statistical prediction.

A Novel Approach to Natural Language Reasoning

The use of Prolog as an intermediary reasoning tool represents a significant departure from how LLMs typically operate. While Chain of Thought (CoT) prompting has improved LLM reasoning, it still relies on the model's autoregressive architecture, which enforces sequential solution generation and limits backtracking capabilities.

Prolog-based reasoning substantially enhances performance across various reasoning tasks. Their paper "Reliable Reasoning Beyond Natural Language" introduces a neurosymbolic approach where LLMs extract and encode problem information as logical code statements, then use Prolog to conduct explicit deductive reasoning. This method significantly improves performance on mathematical reasoning benchmarks like GSM8k and on complex non-linear reasoning problems that even advanced models like GPT-4 struggle to solve using text-only approaches.

Prolog vs. Python Interpreters: Complementary Tools for Different Problems

While Python interpreters have been successfully used with LLMs for mathematical problem-solving, Prolog offers distinct advantages for rule-based reasoning:

Python Interpreters for Mathematics

Python interpreters enable LLMs to handle arithmetic operations by generating executable code for calculations. This approach works well for numeric computations but doesn't naturally extend to logical reasoning about rules and relationships.

Prolog Interpreters for Logical Rules

Prolog, by contrast, excels at representing and reasoning about logical rules, relationships, and constraints. Its declarative nature makes it potentially easier for LLMs to generate valid code without needing to specify precise control flow.

Prolog-based arithmetic problem-solving consistently outperforms CoT approaches across multiple LLMs. Their work demonstrates that LLMs can focus on extracting facts and rules while relying on Prolog to handle the logical deduction process.

Performance Improvements and Benefits

The integration of Prolog with LLMs yields several significant benefits:

1. Enhanced Reasoning Accuracy: Dramatic improvements in reasoning performance, particularly for complex logical problems. On math word problems, GPT-4 with Prolog achieved 100% accuracy compared to just 12.5% using standard CoT methods.
2. Explainability: The Prolog reasoning process produces traceable logical steps, making it easier to understand how conclusions are reached.
3. Handling Complex Non-Linear Reasoning: Prolog enables LLMs to solve problems requiring complex non-linear reasoning that traditional text-only approaches struggle with.
4. Resilience to Cascading Errors: By separating rule extraction from logical inference, this approach reduces the risk of cascading errors that can occur in sequential reasoning.

The Future of Neurosymbolic AI

This approach represents an important step toward neurosymbolic AI, combining the statistical learning capabilities of neural networks with the logical reasoning strengths of symbolic systems. The Thought-Like-Pro framework, for instance, leverages imitation learning to imitate the Chain-of-Thought process verified and translated from reasoning trajectories generated by a Prolog logic engine.

As researchers continue to develop these hybrid approaches, we may see increasingly sophisticated reasoning capabilities emerge. The ability to handle complex logical relationships expressed in natural language could enable more powerful intelligent systems capable of understanding and applying human-defined rules in domains ranging from legal reasoning to medical diagnosis.

Conclusion

The integration of Prolog interpreters with LLMs represents a significant breakthrough in artificial intelligence reasoning. By leveraging Prolog's specialized capabilities for logical inference, this approach addresses core limitations in how LLMs reason about rules expressed in natural language. Demonstrate remarkable performance improvements on tasks that have proven challenging for traditional approaches.

As this technology matures, we may see applications across numerous domains where complex rule reasoning is essential. The English-to-Prolog-to-English pipeline offers a promising path toward more robust, explainable, and accurate AI reasoning systems that can truly understand and apply the logical rules that govern human knowledge.