💬 NLP

RIMRULE: Improving Tool-Using Language Agents via MDL-Guided Rule Learning

RIMRULE is a neuro-symbolic approach that enhances large language models' tool-use reliability in domain-specific settings by dynamically injecting compact, interpretable rules distilled from failure traces via a Minimum Description Length objective, thereby improving accuracy across seen and unseen tools without modifying model weights.

Original authors: Xiang Gao, Yuguang Yao, Qi Zhang, Kaiwen Dong, Avinash Baidya, Ruocheng Guo, Hilaf Hasson, Kamalika Das

Published 2026-07-09

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Xiang Gao, Yuguang Yao, Qi Zhang, Kaiwen Dong, Avinash Baidya, Ruocheng Guo, Hilaf Hasson, Kamalika Das

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 teaching a very smart, but slightly clumsy, robot assistant how to use a new set of tools. Maybe the tools are weird, the instructions are missing, or the robot keeps pressing the wrong buttons.

In the past, if the robot failed, we had two main ways to fix it:

Show it examples: "Here is how I did it once, try to copy me." (This is like showing a student a textbook example).
Rewire its brain: We would retrain the robot from scratch to remember the new way. (This is expensive, slow, and you can't easily share the new "brain" with other robots).

The paper introduces a third, smarter way called RIMRULE. Think of it as teaching the robot to write its own cheat sheet based on its mistakes.

Here is how it works, broken down into simple steps:

1. The "Oops" Moment (Learning from Failure)

First, the robot tries to do a task and fails. Maybe it tried to call a tool incorrectly. Instead of just saying "try again," the system looks at why it failed.

Analogy: Imagine you are trying to bake a cake, but you burn it because you forgot to preheat the oven. Instead of just baking another one and hoping for the best, you write a note: "If the recipe says 'bake,' check the oven temperature first."

2. Writing the Cheat Sheet (Rule Generation)

The robot (using a Large Language Model) looks at its mistake and writes a simple rule to fix it.

The Twist: The robot doesn't just write a long, messy paragraph. It writes a short, clear "If-Then" rule.
- Example: "IF the user asks about family trees, THEN break the question into smaller steps (find the mom, then find the grandpa) instead of asking for the whole thing at once."

3. The "Editor" (MDL Consolidation)

At first, the robot might write 100 rules, many of which are repetitive or too specific (e.g., "If the user asks about John's mom..." and "If the user asks about Sarah's mom...").
The system uses a principle called Minimum Description Length (MDL). Think of this as a strict editor who says, "Stop writing 100 rules. Combine them into one powerful rule that covers all cases."

The Goal: Keep the cheat sheet as short and simple as possible while still fixing the most problems. This makes the rules easy to read and easy to remember.

4. The "Pocket Guide" (Retrieval)

When the robot faces a new task, it doesn't read its entire 100-page history book. Instead, it quickly looks up the specific rule that applies to the current situation and puts it in its "pocket" (the prompt).

Analogy: It's like a mechanic who, before fixing a car, quickly checks their pocket for the specific manual page about "brake squeaks" rather than reading the whole book on how cars work.

Why is this special?

It's Portable: Because the rules are written in plain English (and a simple code format), you can take the cheat sheet written by a "dumb" robot and give it to a "super-smart" robot. The smart robot doesn't need to be retrained; it just reads the new cheat sheet and gets better immediately.
It's a "Cheat Sheet," not a "Brain Surgery": Unlike other methods that require retraining the model (which is like brain surgery), this just adds a note to the instructions. It's fast and doesn't change the robot's core personality.
It Works on New Tools: Even if the robot has never seen a specific tool before, if the rule says "Always check the tool's requirements first," that advice still helps.

The Results

The researchers tested this on two big sets of tool-use challenges. They found that:

Giving the robot these cheat sheets made it much better at using tools, even on tasks it had never seen before.
It worked better than just showing examples or trying to optimize the text prompts.
It even helped robots that were already "fine-tuned" (trained specifically for the job), acting as a safety net to catch remaining mistakes.

In short: RIMRULE teaches AI to learn from its mistakes by writing its own simple, reusable instructions, rather than just memorizing examples or rewriting its entire brain. It turns "trial and error" into a permanent, shareable lesson.

Technical Summary: RIMRULE – Improving Tool-Using Language Agents via MDL-Guided Rule Learning

1. Problem Statement

Large Language Models (LLMs) frequently struggle to reliably utilize tools in domain-specific settings where APIs are idiosyncratic, under-documented, or tailored to private workflows. Current adaptation paradigms—few-shot prompting, global prompt optimization, and fine-tuning—have significant limitations:

Few-shot prompting reuses raw examples without abstracting underlying patterns, often leading to shallow pattern extraction.
Global prompts are static and brittle in interactive environments.
Fine-tuning is computationally costly, requires retraining when environments change, and prevents the easy sharing of acquired knowledge across different model architectures.

There is a need for an adaptation method that mirrors human learning: trying, erring, and compressing experience into reusable, interpretable heuristics that generalize across tasks and models without modifying model weights.

2. Methodology: RIMRULE

The authors propose RIMRULE (Reusable, Interpretable, and MDL-guided Rules), a neuro-symbolic framework that adapts LLM agents by distilling compact rules from failure traces and injecting them dynamically during inference. The framework operates in two distinct phases:

Phase 1: Local Rule Generation

Experience Collection: A zero-shot LLM agent executes tasks on a training set. Execution traces resulting in incorrect answers or premature termination due to tool-calling errors are retained as "failure traces."
Rule Induction via EBL: Using Explanation-Based Learning (EBL), the system compares a failure trace ( $\tau^-$ ) with its ground-truth counterpart ( $\tau^*$ ) to identify the root cause of the error (e.g., decomposition, tool selection, or argument construction). An LLM proposes a compact, natural-language rule to correct similar errors.
Filtering: Proposed rules undergo predictive checks (ensuring they improve performance on the specific query) and linguistic checks (enforcing a clean if-then form).
Symbolic Translation: To ensure structural matching and consistent complexity measurement, natural-language rules are compiled into a symbolic representation with fixed fields: Domain, Qualifier, Action, Strength, and ToolCategory. This creates a deterministic, auditable rule set.

Phase 2: MDL-Guided Consolidation

The initial rule set often contains overlapping and overly specific rules. RIMRULE consolidates this set using the Minimum Description Length (MDL) principle to balance rule complexity against empirical effectiveness.

Objective: Minimize $MDL(H) = L(H) + L(D | H)$, where $L(H)$ is the model cost (penalizing rule complexity/token length) and $L(D | H)$ is the data cost (measuring how well the rules correct observed failures).
Greedy Consolidation: Starting from the full rule pool, the system iteratively applies local edits—pruning redundant rules or generalizing tool-specific rules to category-level rules. An edit is accepted only if the reduction in model cost outweighs the increase in data cost.
Result: A compact, high-utility rule library that generalizes well.

Inference-Time Retrieval

At inference, injecting all rules is inefficient. RIMRULE employs a symbolic-based retrieval mechanism:

The current query and tool context are converted into a symbolic representation.
A coarse filter removes inapplicable rules based on tool scope.
Remaining rules are ranked by semantic similarity between their symbolic fields and the query's symbolic fields.
The top- $k$ relevant rules are retrieved, converted back to natural language, and injected into the prompt.

3. Key Contributions

A New Adaptation Paradigm: RIMRULE introduces a distinct approach to LLM adaptation that emphasizes abstraction and compression over raw example replay (few-shot) or weight modification (fine-tuning).
MDL-Guided Rule Consolidation: The paper demonstrates that using MDL to prune and generalize rules yields a more compact and effective rule set than prompt-based heuristics.
Cross-Architecture Portability: The method produces symbolic, human-readable rules that can be distilled from one LLM (e.g., a weaker model) and reused to improve others (including stronger, long-reasoning models) without retraining.
Dual Representation: By storing rules in both natural language and structured symbolic forms, the system supports efficient retrieval and principled complexity measurement.

4. Experimental Results

The method was evaluated on two tool-use benchmarks: ToolHop (compositional, multi-turn) and BFCL (single-step, diverse tools).

Performance Gains: RIMRULE consistently improved accuracy on both in-distribution (test-rand) and out-of-distribution (test-unseen) splits. For example, on ToolHop, accuracy increased from 26.5% (zero-shot) to 31.1% after rule generation and consolidation.
Comparison to Baselines: RIMRULE outperformed few-shot prompting, prompt optimization (SEE), and standard ReAct prompting across all datasets.
Complementarity with Fine-tuning: Adding RIMRULE to fine-tuned models (SFT) and models with native function-calling capabilities yielded further performance gains, indicating that rule-based adaptation operates on an orthogonal axis to weight-based adaptation.
Transferability: Rules distilled from Llama3.2 improved the performance of GPT-4o, Llama4, and O1. Conversely, rules from GPT-4o improved Llama3.2, demonstrating bidirectional transferability.
Sample Efficiency: In a low-resource setting (90 training samples), the method learned only four rules but achieved significant accuracy improvements (e.g., from 46.0% to 60.0% on unseen BFCL tasks).
Ablation Studies: Symbolic retrieval significantly outperformed natural-language based retrieval, and MDL-guided consolidation outperformed prompt-based merging, confirming the necessity of both components.

5. Significance and Claims

The paper positions RIMRULE as a practical path toward modular and interpretable LLM adaptation. Its primary significance lies in:

Interpretability: Unlike black-box weight updates, RIMRULE produces explicit, human-readable rules that explain why an agent failed and how to fix it.
Reusability: It decouples knowledge acquisition from model training, allowing knowledge to be shared across different LLM architectures without retraining.
Generalization: By compressing failure patterns into abstract rules, the method improves performance on tools and queries never seen during training.

The authors acknowledge limitations, noting that the approach requires access to failure signals during training and relies on a greedy consolidation procedure that does not guarantee global optimality. They also caution that learned rules could overgeneralize if applied outside their intended scope, though the interpretability of the rules allows for auditing and revision.