💬 NLP

Beyond Factual Knowledge: Benchmarking and Learning Step-Level Procedural Rule Reasoning in Large Language Models

This paper introduces RuleWorld, a large-scale benchmark for evaluating step-level procedural rule reasoning, and proposes DynaRule, an end-to-end framework that significantly improves LLM performance on complex multi-step reasoning tasks by dynamically injecting and re-attending to rules within the KV cache.

Original authors: Bohan Yu, Pengfei Cao, Chen Han, Chenxi Zhou, Zhiheng Zhang, Zhiyang Xie, Wenhao Teng, Xiangwen Liao, Jun Zhao, Kang Liu

Published 2026-08-25

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Bohan Yu, Pengfei Cao, Chen Han, Chenxi Zhou, Zhiheng Zhang, Zhiyang Xie, Wenhao Teng, Xiangwen Liao, Jun Zhao, Kang Liu

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

Large language models are the engines behind a new generation of artificial intelligence, capable of writing stories, solving math problems, and translating languages with startling fluency. They work by absorbing vast amounts of text, learning the statistical patterns of how words fit together to form meaning. For years, researchers have tested these models on their ability to recall facts, like knowing that Paris is the capital of France. But there is a different kind of knowledge that is just as vital for real-world thinking: procedural knowledge. This is not about knowing what is true, but knowing how to act or reason based on a set of instructions. Imagine a lawyer who must apply a specific, complex set of laws to a new case, or a doctor following a detailed protocol to diagnose a rare condition. In these situations, the answer isn't stored in memory; it must be found, selected, and applied step-by-step from a large, external rulebook. The question facing the field is whether these powerful models can truly learn to do this, or if they simply pretend to understand the rules while relying on their internal guesses.

To answer this, a team of researchers created a massive testing ground called RuleWorld. Instead of giving the models a few rules to solve a single puzzle, they built a library containing nearly five million abstract rules. These rules are deliberately strange and unrelated to everyday life, such as "if a creature enters a forest, it catches fire," to ensure the models cannot use their own internal knowledge. The rules are written in two ways: as formal logical statements and as plain English sentences. The researchers then designed three types of challenges to test the models. The first was simple: find one rule to answer a question. The second was more complex: answer several questions at once, each requiring different rules. The third was the hardest: solve a chain of problems where the answer to the first step becomes the starting point for the next, requiring the model to track its progress through a long sequence of logical steps.

When they tested existing models on this new benchmark, the results were stark. Even the most advanced models struggled when the number of available rules grew large. When forced to choose from a pool of thousands of rules, they often grabbed the wrong ones or got lost in the middle of a multi-step chain. Standard methods that try to help models by searching for relevant text before answering proved brittle; they would find the right rule for the first step but fail to update their search for the second, leading to a cascade of errors. The models were essentially trying to hold the entire rulebook in their heads at once, a task that overwhelmed their capacity to focus on what mattered at each specific moment.

To solve this, the researchers developed a new system called DynaRule. Instead of treating the rules as a static list to be read once, DynaRule teaches the model to treat the rules as a dynamic resource that it can reach into and update as it thinks. The system works by embedding the rules directly into the model's internal memory structure, a process that allows the model to access them without slowing down. Crucially, the model is trained to recognize when it needs to switch gears. It learns to emit a special internal signal, a mental "search" command, whenever it finishes one step of reasoning and needs to find the next rule. When this signal fires, the model instantly re-evaluates the entire library of rules, discarding the ones it used previously and focusing its attention on the new set of rules required for the current step. This turns the act of finding a rule from a one-time search into a continuous, learnable process that evolves with the reasoning chain.

The results of this approach were significant. On the RuleWorld benchmark, DynaRule consistently outperformed all other methods, including those using powerful external search tools. When faced with a pool of ten thousand rules, the new system maintained a high level of accuracy, correctly identifying the right rule more than eighty-five percent of the time on the first try, while other methods saw their performance collapse. In tasks requiring multiple steps, DynaRule improved the average accuracy by nearly twenty points compared to the best existing alternatives. The system proved that by teaching a model to actively manage its own attention to a large set of instructions, it could reliably navigate complex logical landscapes. The researchers found that the model did not simply memorize the rules; it learned a general method for locating and applying them, even when tested on rules it had never seen before. This suggests that the gap between a model's vast internal knowledge and its ability to follow external instructions can be bridged, provided the model is given a way to dynamically update its focus as the task unfolds.

Technical Summary: Beyond Factual Knowledge – Benchmarking and Learning Step-Level Procedural Rule Reasoning in Large Language Models

1. Problem Statement

While Large Language Models (LLMs) excel at text understanding and generation, they struggle to reliably localize and apply externally provided procedural rules at scale. Existing evaluations of LLM knowledge capabilities primarily focus on factual knowledge, often ignoring procedural knowledge (how to act or reason). Furthermore, current benchmarks for rule reasoning typically provide relevant rules as instance-specific premises, reducing reusable rules to per-question hints. This design obscures whether a model can:

Identify the correct reusable rules from a large, shared rule repository for a specific query.
Apply these rules reliably across multi-step reasoning chains where the target rules change dynamically.

Current methods face two primary challenges:

Retrieval and Utilization Brittleness: Injected rules are often highly abstract and weakly match the surface form of questions, making retrieval and application unstable at scale.
Step-Wise Instability: In parallel aggregation and multi-hop reasoning, the required rules change across steps. Existing approaches, such as Retrieval-Augmented Generation (RAG) or internal injection methods, often suffer from semantic mismatches or unstable rule selection during multi-step reasoning.

2. Methodology

2.1 RuleWorld Benchmark

To address the lack of rigorous evaluation, the authors introduce RuleWorld, a large-scale benchmark designed to measure the rule utilization capability of LLMs.

Scale and Nature: It comprises 4.94 million externally provided procedural rules that are abstract, non-commonsense, and entity-independent. This prevents models from relying on internalized knowledge.
Structure: Rules are organized into four major types (Attributes, Environments, Actions, States) and seven subtypes, available in both First-Order Logic (FOL) and Natural Language (NL). The rules are globally consistent and conflict-free, allowing conclusions of one rule to serve as premises for others.
Task Types: The benchmark defines three QA types to capture distinct modes of rule utilization:
1. Single-Rule QA: Applying exactly one rule (50K instances).
2. Parallel Multi-Rule QA: Solving multiple independent sub-questions within one instance, aggregating answers (3.25M instances, up to 8 gold rules).
3. Multi-Hop Rule QA: Sequential reasoning where intermediate conclusions become premises for subsequent steps (77.7K instances, up to 4 hops).
Total Scope: The benchmark includes 3.37 million QA instances across 11 sub-tasks.

2.2 DynaRule Framework

The authors propose DynaRule, an end-to-end framework that injects rules into the model's internal KV cache and transforms retrieval into a learnable, step-wise process.

Rule Injection via KV Cache: External rules are encoded using a pretrained sentence encoder and projected into the LLM's embedding space via single-layer adapters. These rule representations (Key-Value pairs) are directly inserted into the KV cache alongside contextual tokens, expanding the attention mechanism to include the rule set.
Confidence Layer Identification: The authors identify a specific "confidence layer" within the transformer where attention entropy over injected rules is minimized. This layer exhibits the sharpest attention distribution, indicating the most decisive focus on relevant rules.
Stacked Step-Level Attention Training:
- A special <search> token is introduced to guide attention to the rules required at each specific reasoning step.
- Training involves a Stacked Step-Level Attention Loss. For the first step, retrieval is question-conditioned. For subsequent steps ( $t \ge 2$ ), a <search> token is inserted before the answer, and the hidden state of this token acts as a query to re-attend to the rule set.
- The training objective constructs a shared candidate pool of Top-K rules (augmented with gold rules from all steps) and applies a cross-entropy loss to encourage high attention on the correct rules for the current step while treating rules from other steps as hard negatives.
Inference Process: During inference, the model performs rule retrieval and updating entirely within its internal space. When the decoder outputs a <search> token, the model re-computes attention over the rule set at the confidence layer, replacing outdated rule entries in the KV cache with newly selected ones. This enables dynamic rule re-attention and updating to support stable multi-step reasoning.

3. Key Contributions

RuleWorld Benchmark: A large-scale benchmark containing millions of abstract procedural rules in FOL and NL, covering four types, seven sub-types, and eleven QA sub-tasks. It uniquely combines a large shared rule pool with controlled evaluation of single-rule, parallel multi-rule, and multi-hop reasoning.
DynaRule Framework: An end-to-end rule integration method that injects external rules into the KV cache. It utilizes a learnable <search>-driven step-wise attention mechanism to dynamically select and update rules, transforming retrieval into an internal, differentiable process.

4. Experimental Results

Experiments were conducted on RuleWorld using Qwen2.5-7B-Instruct as the base model, comparing against strong baselines including Prompting, RAG (Dense, BM25, Hybrid), KBLaM, and SR-KI.

Rule Reasoning Performance:
- Existing LLMs (including DeepSeek V3.2 and GPT-5.5) face significant challenges under large rule pools (e.g., 10K rules), with accuracy dropping sharply.
- DynaRule consistently outperforms all baselines. It improves average QA accuracy by up to 19 points over the strongest baselines.
- On specific sub-tasks, gains reach up to 48 points.
- Under 10K rules, DynaRule achieves over 85% Recall@1 and over 90% Recall@10, surpassing the strongest baseline by more than 60 points.
Retrieval Performance:
- DynaRule demonstrates superior rule localization, beating the strongest baseline by up to 61.98 points (FOL) and 53.42 points (NL) in Recall@1.
- Unlike iterative RAG methods (IRCoT, ReAct) which fail to close the gap with multiple retrieval steps, DynaRule's internal step-level retrieval aligns rule localization with the decoding process.
Efficiency:
- DynaRule scales efficiently. KV cache injection scales as $O((M+N)N)$ , which is significantly cheaper than quadratic prompt injection for long rule contexts.
- It reduces Time to First Token (TTFT) and total inference time while maintaining high token throughput.
Generalization:
- When tested on a held-out rule repository (unseen rules), DynaRule maintains substantial performance (50.20% exact match at 10K rules), indicating the model learns a transferable alignment rather than memorizing specific training rules.
Ablation:
- Removing correct rules from the injected set collapses accuracy to near zero, confirming the model relies on the injected rules rather than internal knowledge.

5. Significance and Claims

The paper claims that DynaRule addresses the critical gap between parametric knowledge and explicit rule grounding. By unifying rule retrieval, updating, and reasoning entirely within the model's internal space, the framework enables LLMs to:

Identify relevant procedural rules at each reasoning step.
Dynamically replace outdated rules to support stable multi-step reasoning.
Achieve reliable procedural reasoning even when faced with large, abstract rule pools where traditional retrieval methods fail.

The work highlights that current LLMs struggle with step-level procedural rule reasoning and demonstrates that step-level dynamic integration is a viable path toward more robust and reliable reasoning capabilities. The authors note limitations regarding the current scope (FOL/NL only) and the information loss inherent in embedding-only rule representations as rule pools scale to millions, suggesting future work in hierarchical indexing and richer rule representations.