DeonticBench: A Benchmark for Reasoning over Rules

1. Problem Statement

Large Language Models (LLMs) struggle with deontic reasoning—the process of reasoning about obligations, permissions, and prohibitions under explicit, context-specific rules. This capability is critical for high-stakes domains such as legal systems, tax administration, and policy enforcement.

• Current Limitations: Existing benchmarks often focus on short-context mathematical reasoning or synthetic logic puzzles. They fail to capture the complexity of real-world, long-context rule reasoning where models must interpret statutes, extract case facts, and apply multi-factor legal criteria.
• The Gap: There is a lack of benchmarks that evaluate both non-symbolic (direct natural language reasoning) and symbolic (translation to executable code) approaches in high-stakes, statute-grounded environments. Furthermore, current models frequently hallucinate rules or fail to faithfully execute complex logical constraints.

2. Methodology: DEONTICBENCH

The authors introduce DEONTICBENCH, a comprehensive benchmark comprising 6,232 tasks across four distinct real-world domains:

1. SARA (U.S. Federal Taxes): Adapted from prior work, featuring numeric tax liability calculations and binary entailment checks based on the Internal Revenue Code.
2. Airline (Baggage Policies): Derived from RuleArena, focusing on numeric fee computations based on complex carrier policies (weight, dimensions, cabin class).
3. Housing (U.S. State Law): Based on legal retrieval tasks involving state-specific housing statutes and binary yes/no questions.
4. USCIS-AAO (Immigration Administration): A newly constructed dataset of 242 binary immigration appeal cases (Accepted vs. Dismissed) derived from Administrative Appeals Office records.

Key Features of the Benchmark:

• Dual-Mode Evaluation: Tasks can be solved via:
  • Direct Reasoning: The model outputs the answer directly in natural language.
  • Symbolic Solver-Assisted Workflow: The model translates statutes and case facts into Prolog code, which is then executed by an external SWI-Prolog solver to generate the answer. This provides an auditable program trace.
• Hard Subsets: To avoid saturation and focus on genuine reasoning difficulties, the authors curated "Hard" subsets for each domain. These are instances where frontier models consistently fail, requiring longer Prolog programs and more complex rule grounding.
• Reference Artifacts: The authors release reference Prolog programs for all instances, enabling training and analysis of program-trace fidelity.

Dataset Construction Details:

• USCIS-AAO Construction: Involves extracting "facts-only" narratives from complex legal decisions to prevent data leakage (ensuring the model doesn't see the conclusion in the prompt). This was done via LLM extraction followed by human verification.
• Prolog Generation Pipeline: The authors utilize a "generate-on-the-fly" approach where models create statute modules and question programs per instance, rather than relying on a pre-compiled global library, to better simulate real-world regulatory updates.

3. Experimental Setup

• Models Evaluated: Eight frontier general-purpose LLMs (including GPT-4.1, GPT-5.1, GPT-5.2, O3, Claude Sonnet 4.5, Gemini 2.5 Flash, Kimi K2, Qwen3-235B) and three specialized coding models.
• Prompting Strategies:
  • Direct: No code generation.
  • Zero-Shot: Generate Prolog without examples.
  • Few-Shot: Generate Prolog with in-context exemplars.
• Training Experiments: The authors fine-tuned Qwen2.5-32B-Instruct using:
  • Supervised Fine-Tuning (SFT).
  • Direct Preference Optimization (DPO).
  • Reinforcement Learning (specifically Dr. GRPO, a variant of Group Relative Policy Optimization with a predicate-aware reward function).

4. Key Results

• Overall Performance: Even the strongest frontier models perform poorly on the "Hard" subsets.
  • Best performance on SARA Numeric (Hard) was only 44.4% (O3).
  • Best performance on Housing (Hard) was 46.6% macro-F1.
  • Performance varies significantly by domain and prompting strategy; no single model dominates all settings.
• Symbolic vs. Non-Symbolic:
  • Trade-off: Symbolic (Prolog) generation leads to higher abstention rates (models failing to produce executable code) but offers interpretability. Direct prompting reduces abstentions but increases hallucinated answers (incorrect logic).
  • Error Analysis: Errors are domain-dependent:
    • Legal domains (Housing, USCIS): Dominated by Wrong Rule selection (applying incorrect statutes).
    • Structured tasks (SARA): Dominated by Entity/Fact extraction errors (misinterpreting filing status or dependencies).
    • Quantitative tasks: Dominated by Numerical precision errors.
• Training Impact:
  • SFT and RL improve performance on binary classification tasks (e.g., USCIS, SARA Binary) but yield limited gains on numeric reasoning (SARA Numeric).
  • Current RL methods (DPO, GRPO) fail to reliably solve these tasks end-to-end. Models remain highly sensitive to prompting strategies even after training.
  • Coding Models: Specialized coding LLMs (e.g., GPT-5.2-Codex) showed strong performance on specific domains (Airline) but remained unstable and prompt-sensitive, often failing to generate executable Prolog for complex rule sets.

5. Key Contributions

1. DEONTICBENCH Benchmark: The largest dataset to date (6,232 tasks) for executable rule-based reasoning in high-stakes, real-world domains (Tax, Immigration, Housing, Airline).
2. Comprehensive Evaluation: A systematic analysis of failure modes across frontier models, revealing that increased reasoning effort (e.g., "thinking" models) does not consistently improve performance on statute-grounded tasks.
3. Training Insights: An investigation into SFT and RL for symbolic program generation, highlighting that while training improves code quality, current methods are insufficient for reliable, end-to-end rule reasoning.
4. Open Resources: Release of all reference Prolog programs and the USCIS-AAO dataset to facilitate future research in neuro-symbolic reasoning.

6. Significance

• Safety and Reliability: The paper underscores that LLMs are currently unreliable for high-stakes legal and policy applications where adherence to explicit rules is mandatory. Hallucinations in rule application can lead to significant financial or legal harm.
• Neuro-Symbolic Future: The results suggest that while translating natural language to symbolic code (Prolog) is a promising path for interpretability, the "translation" step remains a major bottleneck. Future work must focus on improving rule grounding (retrieving the correct statute) and faithful execution rather than just improving general reasoning capabilities.
• Benchmarking Standard: DEONTICBENCH sets a new standard for evaluating LLMs in long-context, rule-constrained environments, moving beyond synthetic logic puzzles to real-world regulatory complexity.