RuAG: Learned-rule-augmented Generation for Large Language Models

1 INTRODUCTION

• Fine-tuning, ICL, RAG, and knowledge graphs each face limitations involving computation, long contexts, retrieval quality, or manual construction.These challenges motivate more efficient knowledge transformation for LLM reasoning.Source: §1 · p. 2
• Logic rules compactly encode relationships from diverse data and can be translated into natural language for interpretable LLM knowledge injection.Their structured form is presented as more concise than lengthy passages and more aligned with LLMs than complex graph structures.Source: §1 · p. 2, Figure 2 · p. 2
• RuAG automatically compresses external data into logic rules using LLM-aided MCTS, then injects translated rules into prompts for downstream reasoning.The framework combines automated search formulation, MCTS rule discovery, and rule-based generation.Source: §1 · pp. 2–3
• RuAG automates predicate formulation, uses MCTS for compositional rule search, and evaluates the approach across NLP, time-series, decision-making, and industrial tasks.The stated evaluation includes relation extraction, log anomaly detection, cooperative games, and abuse detection.Source: §1 · pp. 2–3

2 RELATED WORK

• External knowledge is commonly incorporated through supervised fine-tuning, ICL, RAG, knowledge graphs, or logic-rule summaries.These methods have been applied to tasks including OpenQA, games, relation extraction, and entity recognition.Source: §2 · p. 3
• Fine-tuning is computationally costly, while logic-rule summarization can require frequent commercial-LLM calls and high computation.RAG, ICL, and knowledge graphs are described as alternative external-knowledge formats for task-specific use.Source: §2 · p. 3
• Manual logic-rule construction is labor-intensive and domain-dependent, while automatic extraction still requires expert intervention to identify predicates.This leaves predicate selection and commonsense reasoning as unresolved burdens in prior rule-learning methods.Source: §2 · p. 3

3 ENHANCE LLMS’ REASONING THROUGH APPLYING LOGIC RULES

• RuAG converts external data into concise logic rules that guide LLM generation instead of directly fine-tuning or relying only on retrieval.The rules are intended to preserve essential patterns while improving performance and interpretability.Source: §3 · p. 3, Figure 3 · p. 4

3.1 FROM DATA TO RULE SEARCH: LLM-BASED LOGIC RULE SEARCH FORMULATION

• LLM-based formulation defines target and body predicates, removes irrelevant candidates, and can suggest new targets to reduce or enrich the search space.Labels initialize target predicates and features initialize body predicates, with continuous variables converted through the Gini-index.Source: §3.1 · pp. 4–5

3.2 LOGIC RULE SEARCH WITH MCTS

• MCTS searches for logic rules by representing partial rules as states, adding candidate predicates as actions, and evaluating rule quality with rewards such as precision.The search is motivated by the compositional size of the rule space.Source: §3.2 · p. 5
• MCTS uses selection, expansion, simulation, and backpropagation, with UCT balancing exploration and exploitation during predicate selection.Rules are collected at terminal nodes when they exceed a length threshold and meet a precision threshold.Source: §3.2 · p. 5

3.3 LEARNED-RULE-AUGMENTED GENERATION

• Learned-rule-augmented generation cleans searched rules, translates them into natural-language sentences, optionally retrieves relevant rules, and injects them into prompts.The method can retain higher-reward rules when one rule’s body predicates subsume another’s.Source: §3.3 · pp. 5–6

4.1 RELATION EXTRACTION

• 60.42% F1-score with GPT-4 distinguishes RuAG from traditional document-level relation extraction models and other LLM-based methods.Source: Table 1 · p. 6, §4.1 · p. 7

4.2 LOG-BASED ANOMALY DETECTION

• 92.59% F1 with 100% recall lets RuAG outperform all baselines in log-based anomaly detection by improving precision through reliable MCTS-extracted rules.Source: §4.2 · p. 7, Table 2 · p. 7

4.3 MULTI-AGENT GAME: ALICE&BOB

• RuAG is tested on Alice&Bob, where agents must plan and collaborate under unintuitive paths, using win rate, cumulative rewards, and episode length across 30 episodes.The setup compares reinforcement-learning, rule-generated, RAG, and ICL baselines using 1,000 collected trajectories.Source: §4.3 · pp. 7–8, Table 3 · p. 8

4.4 ABLATION STUDY

• Across backbones, RuAG consistently enhances performance beyond vanilla and chain-of-thought systems because learned external rules provide domain context that CoT alone lacks.Source: §4.4 · p. 8, Table 5 · p. 9
• Fewer MCTS search episodes can still produce high-quality rules, while additional episodes yield more rules with diminishing returns and sometimes introduce ineffective or incorrect rules.Source: §4.4 · pp. 8–9, Table 6 · p. 9

4.5 CASE STUDY

• Case studies show rules adding implicit relations, matching anomalous log patterns with confidence, and redirecting an agent toward a strategically important skyblue block.The examples cover relation extraction, log anomaly detection, and cooperative gaming.Source: §4.5 · pp. 9–10, Figure 4 · p. 10

• RuAG automatically distills large volumes of offline data into understandable first-order logic rules for LLM downstream reasoning.The framework uses LLM commonsense to formulate predicates and Monte Carlo Tree Search to address the combinatorial search space.Source: §5 · pp. 10–11
• Empirical evaluations across NLP, time-series, decision-making, and industrial tasks demonstrate RuAG’s effectiveness in improving LLM performance across diverse domains.Source: §5 · p. 11

• The paper follows the ICLR Code of Ethics and considers human-subject impact, data privacy, and fairness in algorithmic decisions.The authors specifically state that the three public datasets do not have potential risk.Source: ETHICS STATEMENT · p. 11
• Private industrial data were released in compliance with legal and ethical standards, with security measures implemented to safeguard personal information.Source: ETHICS STATEMENT · p. 11

• The paper and appendix provide evaluation prompts, experimental setup, implementation details, and hyperparameters for LLM reasoning and MCTS.Source: REPRODUCIBILITY STATEMENT · p. 11
• Code will be available upon publication to support reproduction of the method.Source: REPRODUCIBILITY STATEMENT · p. 11

Task and setup

• The UPA task classifies incidents as unauthorized abuse or legitimate activity using temporal and static features, with high precision and recall required.The private dataset is imbalanced and large, so evaluation uses a balanced sample and smaller batches with F1, Recall, Precision, and Accuracy.Source: A EXPERIMENTAL RESULTS ON PRIVATE… · p. 16

Implementation details

• MCTS discretizes continuous features into ten states using Gini-index split points before extracting rules from the training set.Source: A EXPERIMENTAL RESULTS ON PRIVATE… · p. 16
• MCTS searches rules for IsUPA=1 and IsUPA=0 using 500 rollouts, a maximum length of 5, and a 0.85 precision terminal threshold.The reward is based on rule precision, and rules of lengths 1 to 5 are collected.Source: A EXPERIMENTAL RESULTS ON PRIVATE… · p. 16

Main result

• MCTS-extracted rules achieve high precision comparable to traditional machine learning methods while obtaining higher recall on the small-batch abuse-detection dataset.The cited table reports the comparison across methods.Source: A EXPERIMENTAL RESULTS ON PRIVATE… · p. 16, Table 8 · p. 17
• 96% F1 is achieved when MCTS-extracted rules guide the LLM alongside scenario features, compared with 22.64% F1 for direct LLM use.Using the first extracted rule alone yields an F1 score of 0.6623 when used directly for detection.Source: A EXPERIMENTAL RESULTS ON PRIVATE… · p. 16, Table 9 · p. 17

• The paper provides searched rules in Table 10 for relation extraction and Table 11 for log-based anomaly detection.Source: B MORE EXAMPLES OF SEARCHED RULES · p. 17, Table 10 · p. 17, Table 11 · p. 19

Alice&Bob

• Alice&Bob rules map Bob’s positions and actions to standing on purple, skyblue, or yellow blocks under specified conditions.Source: B MORE EXAMPLES OF SEARCHED RULES · p. 18
• Additional Alice&Bob rules map Alice’s locations and actions to standing on green or yellow blocks, often conditioned on visited locations.Source: B MORE EXAMPLES OF SEARCHED RULES · p. 18
• The searched rules also associate joint states and actions with team penalties of -10.0 or game-winning rewards of 100.0.Source: B MORE EXAMPLES OF SEARCHED RULES · p. 18
• Listing 1 presents the searched rules for the Alice&Bob scenario, including conditions involving both agents’ visited locations and actions.Source: B MORE EXAMPLES OF SEARCHED RULES · p. 18

• Table 12 summarizes the MCTS parameters and LLM configurations across tasks.Source: C IMPLEMENTATION DETAILS · p. 19
• The three public tasks receive detailed implementation descriptions in Table 12.Source: C IMPLEMENTATION DETAILS · p. 19
• Hyperparameter settings for the public-task experiments are reported in Table 12.Source: C IMPLEMENTATION DETAILS · p. 19

C.1 RELATION EXTRACTION

• For relation extraction, MCTS searches training-set relation triplets, retaining 20 terminal-node rules with precision greater than 0.5.Source: §C.1 · p. 19
• During relation extraction, the LLM selects the most relevant retained rule by similarity, using either GPT-3.5 or GPT-4.Source: §C.1 · p. 19

C.2 LOG-BASED ANOMALY DETECTION

• For log anomaly detection, MCTS searches ordered event-subsequence rules using rule accuracy as the reward over time-split HDFS data.Source: §C.2 · p. 19
• Inference combines event-sequence and semantic information to retrieve matching rules, while unmatched sequences are flagged as unknown historical patterns.Source: §C.2 · p. 19

C.3 ALICE&BOB SCENARIO

• Alice and Bob navigate a 13x9 grid toward a treasure while coordinating actions under walls, doors, levers, limited visibility, and a 50-step episode limit.Source: §C.3 · p. 19
• The rule search uses agent observations and actions to target team penalties, colored-block positions, and game wins.Source: §C.3 · p. 19
• The section includes prompt templates for relation extraction, log anomaly detection, and Alice&Bob action generation, plus the Alice&Bob scenario illustration.Source: Figure 5 · p. 20, Figure 6 · p. 21, Figure 7 · p. 21
• Table 12 summarizes the MCTS parameters and LLM configurations used across tasks.Source: Table 12 · p. 21