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

AI summary

Overview

Research area: Natural Language Processing — specifically tool-using LLM agents and inference-time adaptation (neuro-symbolic rule learning).

Technical level: Advanced. The paper combines LLM agent evaluation, Explanation-Based Learning, and a Minimum Description Length (MDL) objective with symbolic rule schemas.

Scope: The paper proposes a method, RimRule, that distills compact, interpretable, human-readable rules from an agent's failure traces and injects them into the prompt at inference time to improve tool-use accuracy without modifying model weights. Published in the Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 34631–34646.

What This Paper Is About

LLMs often fail to use tools reliably in domain-specific settings where APIs are idiosyncratic, under-documented, or tailored to private workflows. Existing adaptation approaches — few-shot example retrieval, globally tuned prompts, or fine-tuning model weights — each lack some combination of abstraction, reuse, and interpretability. RimRule's goal is to adapt a tool-using agent by learning a small set of human-readable, reusable "if–then" rules from its own failures, then dynamically injecting the relevant rules at inference time.

Key Contributions

1. A fourth adaptation paradigm for LLMs. Instead of retrieving demonstrations or tuning weights, the paper induces interpretable rules from failure traces and injects them at inference time, emphasizing abstraction and compression over raw example replay.

2. A two-stage, order-agnostic rule-learning pipeline. Local rule generation (candidate rules produced independently from individual failures, in parallel) followed by MDL-guided consolidation (pruning and generalizing rules to a compact, high-utility library), avoiding the path dependence of sequential rule learning.

3. A dual natural-language and symbolic rule representation. Each rule is stored both as an if–then statement and as a five-field symbolic schema (Domain, Qualifier, Action, Strength, ToolCategory) with closed vocabularies, enabling principled description-length computation and more robust structure-aware retrieval.

4. Demonstrated portability of symbolic knowledge across LLMs. Rules learned from one model's failures can be reused to improve other models — including a long-reasoning model — without retraining, and are shown to complement fine-tuning as an orthogonal axis of generalization.

Main Findings

• Rule injection improves accuracy, including on unseen tools. With Llama3.2 on ToolHop, accuracy moves from 26.5 ± 1.3 (test-rand) and 35.1 ± 1.6 (test-unseen) at zero-shot to 31.1 ± 1.3 and 43.1 ± 1.6 after consolidation. On BFCL, the corresponding numbers are 50.1 ± 0.9 and 45.0 ± 1.0 at zero-shot, rising to 56.6 ± 1.2 and 48.5 ± 1.4.

• Consolidation simultaneously shrinks the rule library and improves performance. Rule generation produces 72 rules on ToolHop and 151 on BFCL; MDL-guided consolidation reduces this to 67 and 121 respectively — a 7% reduction on ToolHop and 20% on BFCL.

• Rules transfer across models in both directions. With rules learned from Llama3.2, GPT-4o goes from 71.6 ± 0.8 to 75.6 ± 1.1 on BFCL, Llama4 from 73.8 ± 1.2 to 76.7 ± 1.2 on ToolHop, and O1 from 53.2 ± 1.4 to 57.4 ± 1.4 on ToolHop. With rules learned from GPT-4o, Llama3.2 improves from 26.5 ± 1.3 to 31.3 ± 1.3 on ToolHop, and O1 improves from 75.6 ± 0.8 to 77.9 ± 1.1 on BFCL. The paper describes these as "consistent gains in both directions," though Table 3 shows one small decrease: GPT-4o on ToolHop with Llama3.2-learned rules moves from 58.1 ± 1.4 to 57.4 ± 1.4.

• RimRule beats prompting-based adaptation baselines. On ToolHop and BFCL respectively, RimRule scores 31.1 ± 1.3 and 56.6 ± 1.2 on test-rand, and 43.1 ± 1.6 and 48.5 ± 1.4 on test-unseen, compared with Zero-shot (26.5 ± 1.3, 50.1 ± 0.9, 35.1 ± 1.6, 45.0 ± 1.0), Few-shot (29.9 ± 1.4, 54.5 ± 0.9, 37.9 ± 1.4, 46.6 ± 1.4), and SEE (27.6 ± 1.5, 52.2 ± 1.0, 35.9 ± 1.5, 45.5 ± 1.0).

• RimRule complements fine-tuning. Adding RimRule to an SFT-tuned Llama3.2 lifts ToolHop test-rand from 43.8 ± 1.4 to 50.0 ± 1.4 and test-unseen from 38.5 ± 1.5 to 45.1 ± 1.6; on BFCL the gains are 65.0 ± 0.9 to 68.6 ± 1.2 and 58.7 ± 1.4 to 62.7 ± 1.3. For a GPT-4o model tuned for function calling, ToolHop moves from 63.8 ± 1.4 to 66.1 ± 1.4 and 83.0 ± 1.2 to 85.4 ± 1.1, and BFCL from 79.6 ± 0.7 to 81.7 ± 1.0 and 77.2 ± 0.8 to 79.8 ± 1.0.

• Sample efficiency on a small dataset. On the BFCL multi_turn_base split with only 90 training samples, the method learns just four rules and raises accuracy from 55.2% to 62.1% on test-rand and from 46.0% to 60.0% on test-unseen.

• Both symbolic retrieval and MDL consolidation matter. Symbolic-guided retrieval scores 31.1 ± 1.3 (ToolHop) and 56.6 ± 1.2 (BFCL) test-rand, versus 29.4 ± 1.3 and 54.1 ± 1.0 for natural-language retrieval. MDL-guided consolidation scores 31.1 ± 1.3 and 56.6 ± 1.2 versus 27.5 ± 1.4 and 52.1 ± 0.9 for prompt-based merging.

• Failure analysis distinguishes reasoning errors from propagation errors. Only the former are used to generate rules; propagation errors are explicitly ignored because they stem from prior mistakes. Rules are tagged as decomposition (dec), tool selection (sel), or argument construction (arg) errors.

Methodology in Plain English

Stage 1 — Local rule generation. The researchers run a zero-shot LLM agent over every training sample and record its execution trace. Traces that produce incorrect answers or terminate early due to tool-calling errors are kept as "experience." Each instance is stored as a tuple of the query, available tools, the agent's incorrect trace, and the ground-truth trace. An LLM-based generator then compares the incorrect and correct traces to identify a root-cause reasoning failure (not downstream propagation), and proposes a compact rule to correct similar errors. The approach follows Explanation-Based Learning: build a grounded explanation and then generalize it by stripping out instance-specific details. Each generated rule must pass a predictive check (does injecting it improve performance on the originating query?) and a linguistic check (clean if–then form, bounded length). If a rule only partially fixes the trace, the generator is re-invoked for additional atomic rules.

Symbolic compilation. Because the same rule can be phrased many ways in natural language, the researchers compile each rule into fixed fields with closed vocabularies: Domain, Qualifier, Action, Strength, and ToolCategory. The vocabulary is induced by prompting an LLM over batches of natural-language rules and selecting the most compact vocabulary across randomized orderings; once fixed, the vocabulary makes the rule set deterministic and auditable.

Stage 2 — MDL-guided consolidation. Rule generation produces many overlapping, overly specific rules. The paper minimizes MDL(H) = L(H) + L(D|H), where L(H) penalizes rule complexity (based on symbolic token length, scaled by a regularization strength α) and L(D|H) measures how many observed failures the rule set corrects, modeled with a Bernoulli likelihood. Consolidation runs greedily from the full rule pool, applying only local edits that strictly reduce the objective: pruning a rule, or generalizing a tool-specific rule into a category-level rule. An edit is accepted only when the drop in model cost outweighs any increase in data cost. The procedure terminates when no local edit improves the objective. α is chosen by picking the value that gives the best end-to-end accuracy after consolidation on the failure set.

Inference-time retrieval. Injecting every rule is inefficient and noisy, so rules are retrieved per query. The query and available tools are converted into the same symbolic representation. A coarse filter first removes inapplicable rules (decomposition rules are always retained; tool-use rules are filtered by whether their scope matches available tools or tool categories). Remaining rules are ranked by semantic similarity between symbolic fields using a generic embedding model, and the top-k are injected into the prompt in natural-language form.

Setup. Experiments use ReAct-style prompting, with agents permitted to retry based on tool feedback or error messages. Evaluated models are Llama3.2 (meta.llama3-2-3b-instruct-v1-0), Llama4 (meta.llama4-maverick-17b-instruct-v1-0), GPT-4o (gpt-4o-2024-11-20), and O1 (o1-mini-2024-09-12, a long-reasoning model). Benchmarks are ToolHop (392 train / 70 test-rand / 51 test-unseen) and BFCL, split into Live-Multiple (735 / 175 / 143) and Multi-Turn-Base (90 / 60 / 50). Ground-truth execution traces are assumed available at training time, but no ground-truth rules are provided. The paper notes it does not compare against symbolic rule learners designed for clean, structured data because the tasks involve noisy natural-language queries and purely symbolic rule application would be brittle.

Why This Matters

Impact on research. The paper positions inference-time rule learning as a distinct adaptation axis alongside few-shot prompting, prompt optimization, and weight fine-tuning. Because rules are stored symbolically and applied without touching parameters, they are transferable artifacts — the results show rules learned from a small model (Llama3.2) improving a long-reasoning model (O1) and vice versa, and adding gains on top of fine-tuned and natively function-calling models. This suggests adaptation knowledge can be a shareable, auditable asset rather than something baked into weights.

Real-world applications (grounded in the settings the paper describes):

• Enterprise agents operating over private, idiosyncratic, or under-documented internal APIs.
• Function-calling assistants that need to select correctly from large, diverse tool sets (the live-multiple BFCL setting).
• Multi-step, compositional query agents that must decompose tasks and resolve intermediate entities — the case study involves a genealogical query that fails until the agent resolves intermediate familial relationships step by step.
• Low-resource deployments: on the BFCL multi_turn_base split with only 90 training samples, four learned rules delivered a 6.9-point test-rand gain (55.2% to 62.1%) and a 14.0-point test-unseen gain (46.0% to 60.0%).

Industry relevance. The method requires no weight updates, which means lower compute cost and no retraining when the environment changes. Rules are human-readable, so they can be audited, revised, or removed — an important property for regulated or high-stakes deployments.

Future Directions

1. Extending rule induction to reward-only settings. The paper notes that where a score or reward function exists instead of ground-truth traces, the same mechanism could propose multiple candidate rules and select those maximizing observed reward, and leaves a full treatment to future work.

2. Moving beyond greedy local edits. Consolidation currently uses local pruning and generalization, which does not guarantee a globally optimal rule set and may miss beneficial non-local edits. The authors call for exploring more global or approximate inference strategies.

3. Broader symbolic abstractions. The five-field symbolic schema is manually designed for noisy natural-language tool-use tasks; other domains may benefit from different symbolic abstractions.

4. Safeguards for rule usage. The paper flags the risk that learned rules could overgeneralize or reflect biases present in observed failures if applied outside their intended scope, and suggests future work on monitoring and validating rule usage in high-stakes settings.

Target Audience

This paper is most valuable to researchers and engineers working on LLM agents, tool use, and function calling; to practitioners adapting agents to private or under-documented APIs without retraining; and to readers interested in neuro-symbolic methods, interpretable adaptation, and model compression objectives such as Minimum Description Length. Familiarity with LLM prompting, tool-calling benchmarks, and basic information-theoretic ideas will help, given the paper's advanced technical framing.

Authors’ abstract

Large language models (LLMs) often struggle to use tools reliably in domain-specific settings, where APIs may be idiosyncratic, under-documented, or tailored to private workflows. This highlights the need for effective adaptation to task-specific tools. We propose RIMRULE, a neuro-symbolic approach for LLM adaptation based on dynamic rule injection. Compact, interpretable rules are distilled from failure traces and injected into the prompt during inference to improve task performance. These rules are proposed by the LLM itself and consolidated using a Minimum Description Length (MDL) objective that favors generality and conciseness. Each rule is stored in both natural language and a structured symbolic form, supporting efficient retrieval at inference time. Experiments on tool-use benchmarks show that this approach improves accuracy on both seen and unseen tools without modifying LLM weights. It outperforms prompting-based adaptation methods and complements finetuning. Moreover, rules learned from one LLM can be reused to improve others, including long reasoning LLMs, highlighting the portability of symbolic knowledge across architectures.