🤖 AI

QMFOL: Benchmarking Large Language Model Reasoning via Quantifiable Monadic First-Order Logic Test Case Generation

This paper introduces QMFOL, an automated framework that generates controllable monadic first-order logic reasoning tasks to create the QMFOLBench benchmark, enabling precise evaluation of how logical complexity, label types, and semantic variations impact the performance and efficiency of large language models.

Original authors: Xinyi Zheng, Ling Shi, Tianlong Yu, Yongxin Zhao, Lorenz Goette, Kailong Wang

Published 2026-06-19

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Xinyi Zheng, Ling Shi, Tianlong Yu, Yongxin Zhao, Lorenz Goette, Kailong Wang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a group of very smart, but sometimes overconfident, students how to solve logic puzzles. You want to know if they are truly getting smarter or just memorizing the answers to the puzzles you've given them before.

This paper introduces QMFOL, a new "puzzle factory" designed to test how well Large Language Models (LLMs)—the brains behind AI chatbots—can actually reason.

Here is the breakdown of how it works, using simple analogies:

1. The Problem: The "Cookie Cutter" vs. The "Master Chef"

Previous tests for AI reasoning were like cookie cutters. They took a basic logic shape, stamped it out, and maybe changed the flavor (the words) slightly.

The Issue: Because the shapes were so predictable, AI models could just memorize the pattern rather than actually thinking. Also, it was hard to make the puzzles slightly harder in just one way (like making the chain of logic longer) without messing up everything else.
The Goal: The authors wanted a Master Chef approach. They wanted to build a kitchen where they could control every single ingredient: the length of the recipe, the number of confusing ingredients, and the type of dish, all while ensuring the final meal actually tastes like the recipe intended.

2. The Solution: The QMFOL Factory

The authors built an automated system called QMFOL. Think of it as a two-step assembly line:

Step 1: Building the Skeleton (The Logic):
First, the system builds a strict, mathematical skeleton using "Monadic First-Order Logic." Imagine this as building a tower out of Lego blocks.
- Depth: How tall the tower is (how many steps of logic you need to take).
- Width: How wide the base is (how many facts you have to juggle at once).
- Distractors: The system adds "decoy blocks"—pieces that look like they belong but actually do nothing. It's like putting a red herring in a mystery story to see if the detective gets distracted.
Step 2: Dressing the Skeleton (The Language):
A computer program (an LLM) then takes this rigid Lego tower and translates it into a natural story about a specific topic, like "University Life" or "Animals."
- The Safety Check: This is the most important part. The system doesn't just trust the story. It takes the story, translates it back into Lego blocks, and checks if it matches the original tower. If the story changed the meaning (e.g., turning a "must" into a "maybe"), the system throws it away and tries again. This ensures the AI is being tested on logic, not just confused by bad English.

3. The Result: QMFOLBench

Using this factory, they built a massive test bank called QMFOLBench containing 2,880 unique puzzles.

They tested 8 different AI models (both open-source and big commercial ones).
They varied the difficulty: some puzzles were short and simple; others were long, wide, and full of distractions.

4. What They Found (The Report Card)

The results were revealing, like watching a student take a test under different conditions:

Complexity Kills Performance: As the puzzles got deeper and wider (more steps, more facts), the AI models got worse. It's like asking a human to solve a math problem in their head; the more steps you add, the more likely they are to make a mistake.
The "True" Bias: The models were much better at proving something was True than proving it was False or Unknown. It's as if they are eager to say "Yes!" but are afraid to say "No" or "I don't know," often guessing "I don't know" when they should have found a contradiction.
Distractions Work: When the puzzles included "decoy" facts (distractors), the models' scores dropped. The more decoys, the more confused they got. Interestingly, adding decoys sometimes made the AI think harder, but often just made it give up.
Topic Matters: Even with the exact same logic, the models performed differently depending on the story topic. They were generally better at "University" stories than "Math" stories. This suggests they rely on what they've read before (memorized knowledge) rather than pure logic. If the topic felt familiar, they did better; if it felt abstract, they stumbled.

The Bottom Line

The paper argues that to truly know if an AI is getting smarter, we can't just give it more of the same old puzzles. We need a system that can precisely dial up the difficulty in specific ways and guarantee the puzzle is fair. QMFOL provides that dial, showing us that while AI is good at reasoning, it still struggles when the logic gets complex, the path is blocked by distractions, or the topic is unfamiliar.

Technical Summary: QMFOL

Problem Statement
While Large Language Models (LLMs) and Large Reasoning Models (LRMs) have advanced significantly in deductive reasoning, existing evaluation benchmarks face critical limitations. Current benchmarks often lack fine-grained control over logical complexity dimensions (such as depth and width) and struggle to balance semantic diversity with logical consistency. Template-based methods preserve logic but limit semantic variety, while manual or LLM-based generation improves linguistic richness but risks introducing hallucinations and logical inconsistencies. Furthermore, many existing datasets may overlap with training data, leading to potential data contamination. There is a need for a scalable, automated framework that can generate deductive reasoning tasks with quantifiable complexity and guaranteed logical consistency.

Methodology
The authors propose QMFOL, an automated framework for generating Quantifiable Monadic First-Order Logic (MFOL) reasoning tasks. The framework operates through two primary modules:

Logic Construction:
- Formal Representation: The system uses MFOL, restricting predicates to unary forms to maintain controllability while preserving core quantifier structures.
- Structural Generation: It constructs logical structures using conjunction and disjunction patterns. The framework allows precise control over depth (reasoning steps) and width (logical connectives).
- Task Derivation: Based on a basic rule set ( $R_{basic}$ ), the system derives fact-conclusion pairs labeled as True, False, or Unknown.
- Distractor Integration: To increase difficulty and test robustness, the framework introduces distractor rules ( $R_{distract}$ ) that share predicates with the basic rules but do not alter the inference path.
FOL2NL (Formal Logic to Natural Language):
- Translation: An LLM translates the formal MFOL instances into natural language based on a specific topic keyword (e.g., Food, Animal, University, Mathematics). The LLM assigns domain-specific semantics to predicates while preserving the logical structure.
- Verification (Round-Trip): To ensure logical consistency, the generated natural language text is translated back into FOL by an LLM and verified using an external Automated Theorem Prover (ATP) (specifically Vampire). If the predicted label from the ATP does not match the ground truth, the task is discarded or regenerated.

Key Contributions

QMFOL Framework: An automated pipeline that constructs formal logical structures, derives labeled reasoning tasks with controlled difficulty, and translates them into natural language with verification.
QMFOLBench: A comprehensive benchmark constructed using QMFOL, comprising 2,880 instances across 960 unique configurations. These configurations vary across five dimensions:
- Depth: 5, 10, 15, 20
- Width: 5, 10, 15, 20
- Label Types: True, False, Unknown
- Distractor Count: 0, 5, 10, 15, 20
- Topics: Food, Animal, University, Mathematics
Comprehensive Evaluation: The authors evaluated six LRMs and two LLMs on QMFOLBench, providing structured insights into how models perform across different logical and semantic dimensions.

Results
Evaluations on models including Gemini-3.1-Pro, GPT-5.4-High, Qwen3.5-27B, and others yielded the following findings:

Complexity Impact: Performance degrades non-linearly as logical complexity (depth and width) increases, accompanied by a rise in computational overhead (time and token usage).
Label Bias: Models consistently perform better on True-labeled tasks compared to False or Unknown tasks. Errors on True and False tasks are frequently misclassified as Unknown.
Robustness to Distractors: As the number of distractor rules increases, model accuracy generally declines. While advanced models (e.g., Gemini-3.1-Pro, GPT-5.4-High) show greater robustness, even they experience performance drops.
Semantic Dependence: Performance varies significantly across different topic domains. For instance, models generally perform better on the University topic, while the DeepSeek series showed notable degradation on the Mathematics topic, often due to the incorporation of external knowledge rather than strict adherence to premises.
Model Performance: Gemini-3.1-Pro achieved the highest accuracy (99.03%), while GPT-5.4-High offered the best trade-off between performance and computational cost. The open-source Qwen3.5-27B performed strongly, surpassing several larger models.

Significance
The paper claims that QMFOL offers a scalable and reliable approach for constructing deductive reasoning benchmarks with controllable complexity. By addressing the trade-off between semantic diversity and logical consistency, QMFOL enables more precise evaluation of reasoning capabilities in modern language models. The authors posit that their benchmark is essential for identifying specific weaknesses in model reasoning (e.g., sensitivity to distractors, label bias, and semantic dependence) and for ensuring that model improvements represent genuine gains rather than data contamination artifacts. The framework is designed to be extensible to full First-Order Logic and richer task configurations in future work.