PaperlayerView exact revision on arXiv

Source-linked AI summary

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

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

arXiv:2608.22753v1cs.CL

TL;DR

LLMs lack reliable evaluation and handling of reusable procedural rules drawn from large repositories. The paper introduces RuleWorld and DynaRule, which integrates rules into the KV cache and performs learnable step-wise retrieval and updating. DynaRule improves QA accuracy and retrieval substantially under large rule pools, while the benchmark and method remain bounded by representation and scalability limitations.

  • Problem

    Existing evaluations often provide rules as instance-specific premises, leaving localization and application of reusable procedural rules from large repositories insufficiently measured.

  • Method

    RuleWorld benchmarks single-rule, parallel multi-rule, and multi-hop reasoning, while DynaRule injects rules into the KV cache and uses <search>-driven step-wise attention for dynamic retrieval and updating.

  • Results

    DynaRule consistently outperforms baselines, improving average QA accuracy by up to 19 points and achieving over 85% Recall@1 at 10K rules.

  • Takeaways & Limitations

    The results support step-level dynamic integration as a way to improve reliable procedural rule application across diverse rule-injection settings.

  • Takeaways & Limitations

    RuleWorld currently uses only FOL and natural-language rules, while DynaRule’s embedding-only representations can lose information and scalability beyond 10,000 injected rules remains unresolved.

Abstract

from arXiv · show

Large language models (LLMs) excel at text understanding and generation, yet still struggle to reliably understand and apply externally provided procedural rules at scale. To evaluate this capability, we introduce RuleWorld, a large-scale benchmark that reformulates rules as globally reusable abstract units rather than instance-specific facts. In RuleWorld, several scenarios, including single-rule, parallel multi-rule, and multi-hop reasoning, are settled for comprehensive evaluation. We further propose DynaRule, an end-to-end framework that injects the given rules into the KV cache and turns retrieval into an internal, learnable, step-wise process. Specifically, DynaRule employs Stacked Step-Level Attention Training with a special <search> token to enable dynamic rule re-attention and updating during inference. In this way, the model can re-attend to the most relevant rules at each step, dynamically replacing outdated ones to support more stable multi-step reasoning. Experiments on RuleWorld show that existing LLMs face challenges under large rule pools, while DynaRule improves average QA accuracy by up to 19 points and achieves over 85% Recall@1 at 10K rules, outperforming strong baselines by large margins. We make our code and dataset available here: https://github.com/SharkSpicy-NLP/Beyond-Factual-Knowledge.

1 Introduction

The paper introduces RuleWorld to evaluate whether LLMs can locate and apply reusable procedural rules from large repositories, and DynaRule to make this process dynamic and step-wise. Experiments show that DynaRule substantially improves reasoning and retrieval performance under large rule pools.

  • Motivation and contributions: Existing evaluations often provide rules as instance-specific premises, overlooking the need to reuse and compose rules from a shared repository.This design makes rule localization and multi-step application central evaluation challenges.
  • Challenges: Current LLMs struggle with abstract rule retrieval and changing rule targets during parallel and multi-hop reasoning at scale.The paper identifies semantic mismatch and unstable step-wise rule selection as major challenges.
  • Results: Up to 19 points of average QA accuracy improvement and over 85% Recall@1 at 10K rules demonstrate DynaRule’s gains over strong baselines.The method also achieves gains of up to 48 points on specific sub-tasks and over 90% Recall@10.
  • Motivation and contributions: RuleWorld contains millions of abstract procedural rules for evaluating rule application across diverse reasoning settings.The benchmark covers four rule types, seven sub-types, and eleven QA sub-tasks.
  • DynaRule: DynaRule injects external rules into the KV cache and uses <search>-driven step-wise attention to select and update them during inference.The framework identifies a confidence layer and trains stacked step-level attention so outdated rules can be replaced as reasoning proceeds.

2 Related Work

Prior logical-reasoning benchmarks generally treat rules as per-instance premises rather than reusable, globally consistent knowledge. Existing LLM rule-reasoning methods use fine-tuning, prompting, or injection, but have limitations in scalability, explicit rule reuse, or robustness.

  • Benchmarks: Existing benchmarks usually model rules as per-instance premises instead of shared, globally consistent rule systems.They cover only parts of the space, such as FOL or NL rules, faithful chains, or controlled composition.
  • Methods: Full fine-tuning internalizes reasoning patterns but is costly and does not explicitly represent globally reusable rules.This limits its fit for evaluating or using large shared rule repositories.
  • Methods: Prompting-based methods decompose reasoning into stages but often depend on strong closed-source models or external tools and remain brittle.

3 Preliminaries

DynaRule represents external rules as key-value pairs and inserts their projected representations into the model’s KV cache. This expands the attention memory with rule entries while preserving the standard output dimensionality.

  • Rule knowledge injection: Each rule is represented as a key-value pair whose full rule forms the key and whose conclusion forms the value.A pretrained sentence encoder produces the rule representations before adapter projection.
  • Rule knowledge injection: Single-linear adapters project rule encodings from the encoder dimension into the model embedding space at a selected layer.Layer-specific adapters are trained to integrate rule embeddings into attention.
  • KV-cache integration: Projected representations for M rules are inserted into a KV cache containing N contextual entries, producing sequences of length M+N.The rule instances are added directly to the corresponding layer’s key and value representations.
  • Attention computation: A dedicated projection adapter transforms hidden states into auxiliary queries for attending to the injected rule representations.Standard contextual self-attention is retained while the key-value sequence length changes.

4 RuleWorld Benchmark

RuleWorld evaluates localization and application of reusable procedural rules from a large, globally consistent repository. Its QA design spans single-rule, parallel multi-rule, and multi-hop reasoning, organized into eleven sub-tasks with increasing rule-count or hop difficulty.

  • Benchmark design: RuleWorld contains 3.37M QA instances and 4.94 million abstract, non-commonsense, conflict-free rules in FOL and NL forms.The rules are entity-independent and reusable across instances without relying on prior knowledge.
  • Benchmark design: The benchmark organizes rules into four major types and seven subtypes, with conclusions able to become premises for other rules.This enables cross-rule interactions across reasoning chains.
  • QA types: Single-Rule QA applies exactly one rule, providing the simplest test of rule grounding and application.This split contains 50K instances.
  • QA types: Parallel Multi-Rule QA independently answers several sub-questions and combines their conclusions, scaling to eight gold rules.It contains 3.25M instances.
  • QA types: Multi-Hop Rule QA requires sequential reasoning across intermediate states, scaling to four hops.It contains 77.7K instances.
  • QA types: The three QA types form eleven sub-tasks by varying gold-rule counts and hop counts.

5 DynaRule

DynaRule trains step-wise rule retrieval by supervising attention over injected rules at a confidence layer, using question and <search> queries across reasoning steps. During inference, it selects top-K rules at prefill and updates them when <search> triggers re-attention.

  • Training Objective: Stacked Step-Level Attention Loss applies cross-entropy supervision across reasoning steps, sharpening rule-score contrasts against hard negatives.The final objective combines this retrieval loss with standard autoregressive language-modeling loss.
  • Confidence Layer Identification: DynaRule identifies a confidence layer with the lowest average attention entropy over injected rule keys for decisive rule relevance signals.This layer concentrates attention on a small subset of relevant rules and receives explicit retrieval supervision.
  • Step-Level Retrieval: The first reasoning step retrieves rules from question-token queries, while later steps use a dedicated <search> token conditioned on intermediate reasoning states.Single-step questions do not use a <search> token.
  • Inference: At inference, DynaRule computes layer-wise attention and Top-K selection during prefill, then updates the confidence-layer KV cache when the model emits <search>.This makes rule retrieval, updating, and reasoning an end-to-end process within the model’s internal intent space.
  • Candidate Construction: Training uses a shared Top-K candidate pool augmented with gold rules from all reasoning steps, preserving future-step rules as hard negatives.At each step, required rules are positives while other candidates, including rules needed at different steps, provide cross-step discrimination.

6 Experiments

Experiments evaluate DynaRule across rule-reasoning, retrieval, generalization, iterative-retrieval, and efficiency settings. DynaRule generally remains strongest as rule pools grow and reasoning becomes multi-step, while retrieval errors compound across steps.

  • 6.3.1 Experiments on Rule Reasoning: DynaRule consistently performs best across rule scales, exceeding the strongest baseline by up to 19.88 points on average.It remains strong under 10000 rules on parallel multi-rule QA, including over 0.72 exact match on multi-rule (5–8).
  • 6.3.2 Experiments on Rule Retrieval: DynaRule beats the strongest retrieval baseline by up to 61.98 points on FOL and 53.42 points on NL.Baselines are limited by semantic mismatch, while single-step retrieval cannot capture interacting rules.
  • 6.3.2 Experiments on Rule Retrieval: Step-wise attention shifts from each step’s gold rules to the next, indicating targeted retrieval triggered by <search>.In a four-step example, attention moves from Rules 0–1 to Rules 2–3 and then follows the same pattern later.
  • 6.4 Analysis: At 10K rules, unseen-rule evaluation reaches 50.20% overall exact match accuracy, 6.80 points below the original split.The models receive no further adaptation on the disjoint rule repository.
  • 6.4 Analysis: At 10K rules, DynaRule achieves 57.00% exact match accuracy and 88.29% Recall@1, exceeding iterative retrieval agents.IRCoT and ReAct reach 19.96%/17.96% exact match accuracy and 27.68%/19.54% Recall@1, respectively.
  • 6.4 Analysis: Removing all correct injected rules often reduces accuracy to zero, while KV-cache injection scales as O((M + N)N).The ablation supports reliance on injected rules, and the efficiency analysis reports lower latency and memory with improved throughput under large rule sets.

7 Conclusion

The paper introduces RuleWorld for evaluating external procedural-rule use across single-rule, parallel multi-rule, and multi-hop settings, and proposes DynaRule for internal step-level rule integration. Experiments show that DynaRule improves the reliability and accuracy of procedural rule application.

  • 7 Conclusion: RuleWorld evaluates LLM use of external procedural rules in single-rule, parallel multi-rule, and multi-hop settings.The benchmark is built from a globally consistent rule set.
  • 7 Conclusion: DynaRule unifies rule retrieval, updating, and reasoning within the model’s internal space.The conclusion presents this as a step-level rule integration framework.
  • 7 Conclusion: DynaRule substantially improves the reliability and accuracy of procedural rule application.The conclusion frames the work as exposing a gap between parametric knowledge and explicit rule grounding.

Limitations

RuleWorld is currently limited to first-order logic and natural-language rule representations, while DynaRule’s embedding-only representations may lose information. Scalability also remains bounded: evaluation reaches 10,000 rules, but the full corpus contains millions and models degrade at 1,000 rules.

  • RuleWorld currently supports only FOL and natural-language rule representations, leaving richer executable or complex triggering formats for future work.
  • Embedding-only rule representations may lose information, causing retrieval or application errors as rule pools scale.
  • The evaluation reaches 10,000 injected rules, whereas the full RuleWorld corpus contains millions and LLMs already degrade at the 1,000-rule scale.
  • Future scalability directions include jointly trained rule encoders, hierarchical or clustered indexing, and more structured rule representations.

A.1 Data Statistics

RuleWorld is a programmatically generated benchmark built from millions of abstract, conflict-free rules and millions of QA instances spanning single-rule, parallel multi-rule, and multi-hop reasoning. Its construction combines controlled vocabularies, logical consistency checks, structured reasoning traces, and LLM-assisted question composition.

  • 4.94 million abstract, conflict-free procedural rules span four major types and seven relation sub-types.Entity2Attr and State2Attr account for 1.87M and 3.05M instances, respectively.
  • 3.37 million QA pairs cover Single-Rule, Parallel Multi-Rule, and Multi-Hop Rule QA across eleven sub-tasks.Parallel Multi-Rule QA contributes 3.25M examples and supports up to eight gold rules, while Multi-Hop QA reaches four hops.
  • The sampled training and evaluation corpus uses 100,235 rules and 111,200 training QA instances with disjoint, difficulty-balanced test instances.Training includes 25,000 Single-Rule, 49,200 Parallel Multi-Rule, and 37,000 Multi-Hop examples.
  • RuleWorld is generated programmatically from predefined vocabularies, abstract interaction patterns, valid condition-effect combinations, and consistency filtering in both NL and FOL formats.The pipeline expands lexical diversity and automatically enumerates or samples valid rules.
  • Parallel Multi-Rule QA merges independent sub-questions into composite prompts while preserving semantics and executing their effects in parallel.The construction covers up to eight atomic rules and uses Qwen2.5-72B-Instruct for coherent question merging.
  • Multi-Hop QA uses predefined reasoning skeletons, simulated state transitions, logical consistency checks, and stored derivation traces to create sequentially dependent instances.Metadata records reasoning depth, intermediate proofs, and full derivations.
  • Together, these procedures yield a scalable benchmark for evaluating rule retrieval and execution across single-rule, parallel, and multi-hop reasoning.Representative examples distinguish atomic inference, independent reasoning threads, and causally connected chains.

B Training and Evaluation Settings

The experiments evaluate exact-match QA and step-wise retrieval under controlled injection, held-out QA instances, multiple seeds, and FOL/NL rule formats. DynaRule identifies a confidence layer and performs KV-cache-based retrieval, while baselines use specified sparse, dense, hybrid, or confidence-layer retrieval methods.

  • Evaluations use five random seeds, 110 samples per seed, and 550 total questions from held-out QA instances.Parallel multi-rule samples are manually checked, while the underlying rule pool is shared with training.
  • Rule injection uses all rules at size 100 and top-K=100 selection for larger rule sets, while KBLaM and prompting inject all rules without retrieval.
  • RAG baselines use BM25 and Qwen3-Embedding-8B, while hybrid retrieval fuses them with Reciprocal Rank Fusion using k = 60.End-to-end approaches perform confidence-layer retrieval.
  • Exact-match accuracy scores normalized comma-separated answer lists by position-wise agreement after requiring equal list lengths.Predictions receive zero when predicted and gold list lengths differ.
  • DynaRule’s step-wise retrieval recall matches each retrieval step against the corresponding gold step, assigning zero to missing steps and truncating extras.
  • Confidence-layer identification consistently finds a format-invariant layer across tested models and encoders, including layer 22 for Qwen2.5-7B-Instruct with bge-m3.The layer is defined by minimized attention entropy over injected rules.

C.2 Prompting Results with Strong LLMs

Strong prompting baselines degrade as injected rule pools grow, especially on parallel and longer multi-hop reasoning, while DynaRule remains strongest across scales and representations. Case studies attribute failures to omission, semantic misapplication, and action-type misalignment, and robustness analysis finds its large-scale gains exceed uncertainty intervals.

  • C.2 Prompting Results with Strong LLMs: DynaRule achieves the best overall results across rule scales and representations, exceeding the strongest prompting baseline by up to 13.86 average points and 36 subtask points.
  • C.3 Case Study: Case studies identify three recurrent errors: rule omission, incorrect application, and action-type misalignment.
  • C.3 Case Study: A rule-omission case produces 7 instead of the correct 1 by stopping before propagating a multi-step attribute reduction.
  • C.3 Case Study: The attention heatmap tracks how required rules are weighted across reasoning steps, while retrieval results compare Recall@100, Recall@10, and Recall@1 across steps and injection sizes.
  • C.3 Case Study: A semantic trigger error yields 10 instead of 14 crimson essences, while an action-operator mismatch yields 10 instead of 16 muddy livers.
  • C.4 Statistical Robustness: At 10K rules, DynaRule’s QA confidence interval is ±4.3 points and its retrieval interval ±1.3 points, smaller than its gains over SR-KI and Hybrid RAG.

C.5 Detailed Retrieval Results across Reasoning Steps and QA Types

Step-level retrieval remains strong across rule representations and scales, but becomes less reliable as reasoning deepens. DynaRule outperforms baselines across QA types, with sequential multi-hop reasoning remaining the most difficult setting.

  • Retrieval across reasoning steps: Recall generally stays above 0.8 across FOL and NL representations as rule-set size grows from 100 to 10000.Step 1 retrieval remains nearly perfect under all metrics.
  • Retrieval across reasoning steps: Retrieval performance declines from Step 2 to Step 4, especially under stricter Recall@1 evaluation.The decline is slightly sharper for FOL than NL at larger rule scales.
  • QA-type comparisons: DynaRule consistently outperforms all baselines across QA types and rule-injection settings.Its performance is near perfect on Single-Rule and Parallel Multi-Rule QA.
  • QA-type comparisons: Multi-Hop Rule QA shows greater degradation than Single-Rule and Parallel Multi-Rule QA, indicating higher sensitivity to intermediate retrieval errors.This pattern is reported across the evaluated QA types and injection settings.
  • Stepwise attention behavior: Attention shifts toward the rules required at each reasoning step, jointly attending to multiple rules when a step needs them.The resulting staircaselike pattern reflects dynamic rule selection and application during multi-step reasoning.
Loading 2608.22753v1…