PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning Hierarchical Procedural Memory for LLM Agents through Bayesian Selection and Contrastive Refinement

Saman Forouzandeh, Wei Peng, Parham Moradi, Xinghuo Yu, Mahdi Jalili

arXiv:2512.18950v1cs.LGcs.AI

TL;DR

LLM agents can miss useful intermediate steps when trajectory training reduces episodes to terminal outcomes, while step-level training is computationally costly. MACLA keeps the LLM frozen and learns through external procedural memory using Bayesian selection and contrastive refinement. It achieves the highest reported average performance across four benchmarks, while its performance varies with task structure.

  • Problem

    Trajectory-level training can overlook useful intermediate steps by treating whole episodes according to terminal outcomes, while step-level training requires costly repeated policy training on densely labeled data.

    Source: §1 · p. 1

  • Method

    MACLA freezes the LLM and adapts structured external procedural memory through Bayesian selection and contrastive refinement of procedures from successful and failed contexts.

    Source: §1 · p. 1

  • Results

    78.1% average performance across four benchmarks is the highest among all methods; MACLA also reports state-of-the-art results on ALFWorld and TravelPlanner.

    Source: §1 · p. 2, §6 · p. 8

  • Takeaways & Limitations

    MACLA compresses 2,851 ALFWorld training trajectories into 187 reusable procedures, demonstrating efficient knowledge distillation.

    Source: §6 · p. 8

    Performance depends on task structure: SQL has low reuse (51%), reliability (64%), and composition (18%) because queries are schema-specific and atomic.

    Source: Task-Specific Memory Effectiveness · p. 8

Abstract

from arXiv · show

We present MACLA, a framework that decouples reasoning from learning by maintaining a frozen large language model while performing all adaptation in an external hierarchical procedural memory. MACLA extracts reusable procedures from trajectories, tracks reliability via Bayesian posteriors, selects actions through expected-utility scoring, and refines procedures by contrasting successes and failures. Across four benchmarks (ALFWorld, WebShop, TravelPlanner, InterCodeSQL), MACLA achieves 78.1 percent average performance, outperforming all baselines. On ALFWorld unseen tasks, MACLA reaches 90.3 percent with 3.1 percent positive generalization. The system constructs memory in 56 seconds, 2800 times faster than the state-of-the-art LLM parameter-training baseline, compressing 2851 trajectories into 187 procedures. Experimental results demonstrate that structured external memory with Bayesian selection and contrastive refinement enables sample-efficient, interpretable, and continually improving agents without LLM parameter updates.

1 INTRODUCTION

MACLA keeps the LLM frozen and learns through structured external procedural memory, addressing limits of trajectory-level training and enabling continual adaptation. Across four benchmarks, it reports the highest average performance among the evaluated methods.

1 INTRODUCTION

  • Trajectory-level fine-tuning often weights whole episodes by terminal success or failure, overlooking correct substeps in failures and suboptimal actions in successful trajectories.Step-level rewards address this issue but require repeated policy training on densely labeled data, which incurs substantial computational cost.Source: §1 · p. 1
  • MACLA fixes the LLM as a semantic reasoner for segmentation, abstraction, and action generation while learning through explicit, interpretable operations in external procedural memory.Its memory tracks Bayesian posteriors and refines procedure preconditions through contrastive analysis.Source: §1 · p. 1
  • Bayesian selection scores procedures using relevance, success probability, failure risk, and information gain, while contrastive refinement uses successful and failed contexts to adjust procedures.With sufficient evidence, refinement tightens preconditions, repairs action sequences, and refines postconditions; meta-procedural learning composes procedures into conditional playbooks for long-horizon tasks.Source: §1 · p. 1
  • Online adaptation updates procedural and meta-procedural memory during and after episodes without LLM weight updates, unlike offline post-training approaches that remain static at inference.The stated contributions also include decoupling reasoning from learning and avoiding the computational cost and catastrophic-forgetting risks of parameter fine-tuning.Source: §1 · pp. 1–2
  • 78.1% average performance across four benchmarks is the highest among all methods; on ALFWorld, MACLA reaches 87.2% on seen and 90.3% on unseen tasks, with a +3.1% generalization gap.Memory construction uses 0.016 GPU-hours, 2,800× faster than the 44.8 GPU-hours required by the parameter-training baseline.Source: §1 · p. 2

2 RELATED WORKS

Related work spans memory location and stored content, from episodic traces and text snippets to structured artifacts and reusable procedures. MACLA’s related-work comparison centers on limitations in procedural memory systems and its structured, hierarchical alternative.

2 RELATED WORKS

  • Memory systems differ both in where memory resides and what it stores, including episodic or long-term stores and text, structured artifacts, or procedures.Buffer-based approaches store conversational or episodic traces, while hierarchical systems separate working, episodic, and long-term stores.Source: §2 · p. 3
  • Text snippets can suffer retrieval drift and weak compositionality, while tuples and key–value frames aid filtering but lack executable semantics for reuse.Procedural-memory approaches capture reusable action patterns and workflows across related tasks.Source: §2 · p. 3
  • The paper characterizes prior procedural memory as largely monolithic, heuristically retrieved, and lacking uncertainty-aware selection, paired success–failure refinement, and meta-procedural composition.MACLA instead represents experience as hierarchical procedures with preconditions, action schemas, and postconditions for interpretable reuse and composition.Source: §2 · p. 3

3 THE PREAMBLE

This section provides ACM submission and manuscript-preparation instructions rather than research content.

3 THE PREAMBLE

  • Authors receive a submission number upon abstract registration on OpenReview and should include it using the \acmSubmissionID command.The passage specifies that the number is assigned at registration.Source: §3 · p. 3
  • The title and author information belong in the preamble, with separate affiliation and email commands for each author.Multiple affiliations for one author are specified with separate \affiliation commands.Source: §3 · p. 3
  • The manuscript should include a short abstract and a small number of descriptive keywords.The passage names the abstract and keywords environments or commands.Source: §3 · p. 3

4 PROPOSED METHOD

MACLA builds a reusable procedural library from trajectories, selects procedures using Bayesian expected utility, and refines them from contrasting execution outcomes. It composes recurring procedures into conditional playbooks, supports semantic matching across contexts, and bounds memory and runtime costs.

4.1 LLM-based Procedural Abstraction

  • The frozen LLM segments trajectories into coherent subtasks and abstracts each into a procedure with a goal, preconditions, action sequence, and postconditions.Semantic embeddings support retrieval and duplicate detection; similar procedures are merged by expanding condition sets, while dissimilar ones are added as new entries.Source: §4.1 · p. 3

4.2 Bayesian Reliability and Utility Selection

  • Each procedure’s Beta posterior estimates its success probability and uncertainty, and expected utility combines contextual relevance, reward, failure risk, and information gain.If no candidate meets the confidence threshold, the agent falls back to zero-shot LLM reasoning; selection balances exploitation, risk aversion, and exploration.Source: §4.2 · pp. 3–4

4.3 Contrastive Refinement of Procedures

  • Contrastive refinement compares successful and failed contexts to identify differences in preconditions, action sequences, and postconditions.When it detects distinct execution modes, MACLA specializes a procedure into variants that inherit reliability priors, making changes through memory edits rather than gradient updates.Source: §4.3 · p. 4

4.4 Meta-procedural Composition

  • Repeatedly successful procedure sequences under a common goal become meta-procedures with conditional policies to continue, skip, repeat, or abort.Their control policies are distilled from successful traces, and each meta-procedure maintains a Beta success posterior.Source: §4.4 · p. 4

4.5 Ontological Semantic Grounding

  • MACLA clusters frequent task and action words into semantic categories, allowing procedures to match contexts with lexically different but semantically equivalent terms.The paper gives mug, cup, and glass as examples within a container category.Source: §4.5 · p. 4

4.6 System Efficiency and Memory Management

  • Memory management uses approximate nearest-neighbor retrieval, a bounded episode buffer, capped failure histories, and pruning based on reliability, usage, and recency.LLM calls have a fixed per-episode budget, while retrieval, scoring, and updates are symbolic or vectorized so inference cost does not scale with experience.Source: §4.6 · pp. 4–5

4.7 Algorithm

  • At runtime, MACLA retrieves procedures and meta-procedures for the current observation, ranks them by Bayesian utility, checks execution conditions, and updates reliability from outcomes.It repeats retrieval as observations change, triggers contrastive refinement when procedures have both successes and failures, and abstracts stable successful sequences into meta-procedures.Source: §4.7 · p. 5

5 EXPERIMENTS

Across four interactive benchmarks with consistent settings, MACLA achieves the highest average performance. The experiments also examine component contributions, memory capacity, Bayesian learning, pruning, and training cost.

5.1 Experimental Setting

  • Experiments use consistent hyperparameters across ALFWorld, WebShop, TravelPlanner, and InterCodeSQL, with Llama-2-7B frozen and 2,851 ALFWorld trajectories compressed into 187 procedures.The benchmarks cover embodied tasks, shopping, itinerary planning, and interactive text-to-SQL; MACLA does not store raw trajectories.Source: §5 · p. 5, §5.1 · pp. 5–6

5.2 Experimental Results and Analysis

  • 85.6%→90.3% unseen success across 100–200 capacity follows 64.1% at 25, then declines by 0.2% at 300.Beyond 150 procedures, gains diminish; the average posterior plateaus at 0.79 as extra capacity adds redundancy rather than quality.Source: §5.2 · p. 6, Figure 2 · p. 7
  • By episode 50, all top procedures stabilize above 0.75 posterior with α+β>30 and standard deviations <0.05; Navigate accumulates evidence faster than specialized procedures.The reported posterior variance decreases as evidence accumulates.Source: §5.2 · p. 6, Figure 3 · p. 8
  • 73% of pruned procedures have success below 0.5, while 81% of retained procedures exceed 0.7; 68% of pruned procedures are young and rarely used.No procedures with >0.7 success and >10 uses are pruned.Source: §5.2 · pp. 6–7
  • 78.1% average performance is highest among methods; MACLA also reaches 83.3 CS on TravelPlanner and 90.3% on ALFWorld-Unseen.The comparison spans four benchmarks and includes methods using models 10× larger.Source: §5.2 · p. 6, Table 1 · p. 7
  • Removing Bayesian selection yields –7.7 seen and –9.1 unseen, while removing meta-procedural composition drops unseen performance by –11.9.Removing contrastive learning and ontological clustering yields smaller drops of –3.5/–4.6 and –4.3/–6.2, respectively.Source: §5.2 · p. 6, Table 2 · p. 7
  • 56 seconds (0.016 GPU-hours) for MACLA memory construction is 2,800× faster than IPR’s 44.8 GPU-hours of iterative training.MACLA avoids iterative parameter training; new trajectories can be ingested in seconds.Source: §5.2 · pp. 6–7, Table 3 · p. 7

Task-Specific Memory Effectiveness

InterCodeSQL underperforms where procedures are difficult to reuse, less reliable, and rarely benefit from hierarchical composition.

Task-Specific Memory Effectiveness

6 CONCLUSION

MACLA separates reasoning from learning by keeping the LLM frozen and adapting an external hierarchical procedural memory. Across four benchmarks it reaches 78.1% average performance, while compressing 2,851 ALFWorld trajectories into 187 procedures.

6 CONCLUSION

  • MACLA decouples reasoning from learning: a frozen LLM works with an external hierarchical procedural memory adapted through Bayesian selection, contrastive refinement, and meta-procedural composition.Source: §6 · p. 8
  • 78.1% average performance across four benchmarks is achieved with a 7B model, with state-of-the-art results on ALFWorld and TravelPlanner.ALFWorld results are 87.2% seen and 90.3% unseen; TravelPlanner reaches 83.3%.Source: §6 · p. 8
  • 2,851 ALFWorld training trajectories are compressed into 187 reusable procedures through semantic abstraction and duplicate detection.Source: §6 · p. 8

A DETAILED ABLATION STUDIES AND MEMORY ANALYSIS

Ablations show that Bayesian selection and hierarchical composition are especially consequential, while capacity tests identify a useful memory range and diminishing returns beyond it.

A DETAILED ABLATION STUDIES AND MEMORY ANALYSIS

A.1 Memory Capacity Scaling

  • At capacity 25, ALFWorld performance is 68.3% seen and 64.1% unseen, while capacity 150 reaches 86.4/88.7 and capacity 200 reaches 87.2/90.3.The low-capacity setting leaves task coverage insufficient; the capacity table reports results after 200 training episodes.Source: §A.1 · p. 10, Table 5 · p. 10
  • As procedural-memory capacity grows from 25 to 200, average posterior rises from 0.61 to 0.79 and then plateaus; beyond 200, quality does not improve because task space is saturated.Source: §A.1 · p. 11

A.2 Task-Specific Memory Effectiveness

Memory effectiveness varies with task structure: MACLA’s components and finite capacity matter, while SQL’s low reuse and short procedures contrast with ALFWorld’s reusable multi-step skills.

A.2 Task-Specific Memory Effectiveness

  • InterCodeSQL has 51% reuse and 0.64 average posterior reliability, versus ALFWorld’s 76–78% reuse and 0.79–0.81 posteriors.SQL failures include schema mismatches, join complexity, and edge cases; the task-specific table summarizes benchmark metrics over 50 test episodes.Source: §A.2 · p. 11, Table 6 · p. 11
  • Only 18% of SQL episodes use meta-procedures, versus 51% for TravelPlanner, as SQL queries are commonly atomic 2–3-action sequences.SQL procedures average 2.8 actions, compared with 4.1–6.3 actions in the cited other tasks.Source: §A.2 · p. 11, Table 6 · p. 11
  • ALFWorld combines 76–78% reuse, 0.79–0.81 posteriors, 38–42% meta-procedure hits, and 4.1–4.2-action procedures.These metrics are reported as characteristics associated with ALFWorld’s effectiveness for procedural memory.Source: §A.2 · p. 11
  • The authors identify schema-aware templates, cross-schema ontology, and compositional query building as improvement directions for SQL.Source: §A.2 · p. 11
  • Bayesian selection, contrastive learning, and meta-procedures contribute synergistically; performance gains diminish beyond 150–200 procedures as the average posterior plateaus at 0.79.Source: §A.2 · p. 11

B.1 Bootstrapping and Memory Growth Dynamics

This section examines how MACLA bootstraps and grows procedural memory from imperfect experience through conditional compositions, Bayesian updates, and contrastive refinement. It illustrates selection and post-episode learning on an unseen task and discusses inference-call reduction and per-procedure learning credit relative to alternatives.

B.1 Bootstrapping and Memory Growth Dynamics

  • 82% success after 1,425 trajectories and 87.2% after 2,851 accompany compression of 2,851 trajectories into 187 procedures.The first 1,425 trajectories are half the training data; the final 1,426 add 5.2 percentage points as performance plateaus.Source: Figure 6 · p. 12, §B.1 · pp. 12–13

C DETAILED EXECUTION TRACE ANALYSIS

  • A timestamped execution trace follows MACLA solving an unseen ALFWorld task and shows information flow through online inference and post-episode learning.The trace covers time steps t0–t8 during inference and t9 for learning.Source: C DETAILED EXECUTION TRACE ANALYSIS · p. 13

C.1 Task Description and Setup

  • “Put chilled lettuce on the counter” tests compositional generalization because the lettuce-fridge-countertop combination was absent from training.The modifier “chilled” requires cooling before placement.Source: §C.1 · p. 13

C.2 Execution Timeline

  • The unseen episode succeeds via cooling then placement, updates both procedures’ Bayesian posteriors, and creates a meta-procedure from a composition seen in 3 of 15 recent episodes.The new meta-procedure conditionally applies cooling before placement when the task includes a cooling modifier.Source: §C.2 · pp. 15–16

C.3 Trace Verification Methodology

  • Replay verification confirmed all 8 actions and 2 LLM calls matched the recorded trace.The trace also reports that intermediate actions used template-based instantiation without LLM generation.Source: §C.3 · p. 17

C.4 Key Observations and Architectural Insights

  • Bayesian selection favored the fridge over the freezer with expected success of 76.9% vs. 40.0%; template reuse enabled >85% token reduction vs. ReAct.The episode used two LLM calls, with subsequent actions instantiated from learned templates.Source: §C.4 · p. 17
  • After successful cooling, the posterior changes from Beta(10,3) to Beta(11,3), raising expected success from 76.9% to 78.6% with information gain of ΔH=0.136 nats.This update occurs during episode execution without changing the frozen LLM’s parameters.Source: §C.4 · p. 17
  • 20% of recent episodes triggered meta_cool_and_place_object, composing cooling and placement under a conditional policy and reducing planning from 2 retrievals to 1.The procedure abstracts across object and location configurations and applies cooling only when the task includes a cooling modifier.Source: §C.4 · p. 18
  • With 11 cooling successes and 3 failures, MACLA prepares contrastive refinement once min(|S|, |F|)≥3, distinguishing cold appliances from heat sources.The episode logs “chilled via fridge” as a success pattern for later comparison with failures.Source: §C.4 · p. 18

C.5 Comparison to Alternative Approaches

  • 2 LLM calls versus ReAct’s 16–20 calls reduce inference overhead by >85% for this task [26].ReAct’s estimate includes reasoning before each of 8 actions, plus initial planning and reflection; MACLA retrieves learned procedures.Source: §C.5 · p. 18
  • 5–8 additional LLM calls for Reflexion’s post-episode critique are avoided by MACLA’s Bayesian updates and contrastive refinement, which quantify uncertainty with Beta posteriors [15].The passage describes the memory improvements as similar, without the extra calls.Source: §C.5 · p. 18
  • MACLA decomposes an 8-action trajectory into reusable cooling and placement procedures with independent Bayesian credit assignment, updating cooling immediately upon success at t6.This step-level update precedes episode completion, unlike SFT’s terminal-success-only training signal.Source: §C.5 · p. 18

C.6 Generalization to Unseen Tasks

MACLA generalizes to unseen tasks through object-level transfer, composition of learned procedures, and Bayesian reliability estimates aggregated across contexts.

C.6 Generalization to Unseen Tasks

  • Cooling learned from potato and apple episodes transfers to lettuce without lettuce-specific training through object placeholders.Training included 7 potato and 2 apple episodes; semantic abstraction parameterizes procedures over entity types rather than instances.Source: §C.6 · p. 18
  • The unseen lettuce cooling-to-placement sequence is composed by matching cooling’s postcondition to placement’s precondition, without composition supervision.The cooled(object) postcondition satisfies the placement precondition, enabling automatic chaining.Source: §C.6 · p. 18
  • Fridge selection uses a Beta(10,3) posterior from 10 successes and 3 failures across objects and contexts, transferring reliability knowledge across contexts.The paper contrasts this with episodic systems that treat experiences independently.Source: §C.6 · p. 18

C.7 Limitations and Edge Cases

The section describes edge cases in precondition inference, selection overhead, and memory capacity, then examines empirical thresholds and theoretical alternatives.

C.7 Limitations and Edge Cases

  • Ambiguous task modifiers can trigger unnecessary cooling: without “chilled,” co-occurrence may lead MACLA to spend 4–5 actions cooling an object that needs no cooling.The section says contrastive refinement may learn that chilled, frozen, or cold modifiers are necessary.Source: §C.7 · p. 18
  • Scoring 5–10 retrieved procedures takes 0.4 ms per decision, but the overhead accumulates in episodes of 50+ steps.Meta-procedures partially address this by skipping lower-level selection and reducing decision points by 40–60% for complex tasks.Source: §C.7 · p. 18
  • With memory capped at 200 procedures, pruning evicts procedures below 60% success and fewer than 5 uses first, potentially forgetting rare but important skills.The section gives emergency procedures used less than 1% of the time as an example.Source: §C.7 · p. 18

D.1.1 Duplicate Detection Threshold 𝜃dup.

  • The theoretical-foundations section notes that MACLA’s threshold values were chosen empirically and that duplicate-detection performance varies by ±4.2% over thresholds 0.75–0.95.For duplicate detection, the proposed information-theoretic formulation trades memory compression against information loss from overly aggressive merging.Source: §D.1 · p. 19, §D.1.1 · p. 19

D.1.2 Confidence Threshold 𝜃conf.

The section examines MACLA’s threshold and tuning choices, reporting a calibrated confidence alternative and proposing value- or evidence-based alternatives for several mechanisms. It also reports an informed prior’s faster learning and low power for the current refinement evidence threshold.

D.1.2 Confidence Threshold 𝜃conf.

  • Under Llama-2-7B baseline assumptions, expected zero-shot utility is −0.02; a calibration-aware threshold of about 0.38 is closer to the empirical 0.4.The calculation uses success rate ≈0.42, maximum reward 1.0, failure cost 0.5, and normalized LLM cost 0.15.Source: §D.1.2 · pp. 19–20

D.1.3 Meta-Procedure Formation Threshold 𝜃meta.

  • The ≥15% sequence-frequency trigger ignores sequence length, dependence, and memory-slot cost; the proposed value criterion incorporates composition gain and storage cost.The proposed criterion aims to form meta-procedures by value maximization rather than an arbitrary frequency threshold.Source: §D.1.3 · p. 20

D.2 Bayesian Prior Initialization

  • On ALFWorld, an empirical-Bayes prior Beta(3.2, 1.8), with mean reliability about 0.64, accelerates learning by 12–18 episodes versus uniform initialization.The hyperparameters were estimated from the first 500 training trajectories.Source: §D.2 · p. 20

D.3 Utility Function Weight Selection

  • The utility weights 0.5, 0.3, and 0.2 require manual task-specific tuning; adaptive online gradient-free weight learning is proposed to address this.The paper says this approach eliminates manual tuning while adapting to domain characteristics.Source: §D.3 · p. 21

D.4 Contrastive Refinement Evidence Requirement

  • A refinement minimum of nmin = 3 provides very low statistical power (≈0.15), leading to unreliable refinements; the note recommends nmin in [8, 12] for adequate power or sequential testing.Source: §D.4 · p. 21

D.5 Memory Pruning Utility Function

  • Under Markovian task-distribution assumptions, the expected-future-value derivation recovers MACLA’s pruning form with λ=1/τ.The derivation incorporates task similarity and temporal decay.Source: §D.5 · p. 21

Related papers

Loading 2512.18950v1…