Ch. 7 — Memory-Augumented Planning

Chapter 7 of [[ai-ml/nvidia-certs/ncp-aai/cognition-planning-and-memory/Understanding-the-planning-of-LLM-agents-A-survey|Understanding the planning of LLM agents: A survey]]

Abstract

This chapter establishes the empirical validation and future theoretical trajectories for memory-augmented planning in large language model (LLM) agents. It details interactive evaluation benchmarks, specifically web service and programming environments, and quantifies the performance trade-offs of prompt-based methods such as Reflexion and SayCan. The central argument posits that while planning capabilities enhance through increased token consumption and reflection mechanisms, critical challenges regarding hallucination, plan feasibility, and efficiency remain unresolved for industrial deployment.

Key Concepts

• Interactive Web Service Environments: These are simulated digital platforms used to test agent planning, where actions include searching keywords or navigating links via click, forward, and backward operations. Common benchmarks include HotPotQA and Fever for question-answering, alongside WebShop, Mind2Web, and WebArena for information retrieval tasks. The primary metric for success is the task completion rate.
• Interactive Programming Environments: These environments simulate human-computer interaction for solving computer-related problems, requiring agents to write code or instructions. Agents receive feedback including compile and runtime error messages, as well as execution results. Popular implementations involve operating system and database issues, tested through benchmarks like Agent Bench and MiniWoB++.
• Golden Path Constraint: Most simulated environments lack fine-grained evaluation metrics, relying predominantly on a binary task success rate. Unlike real-world scenarios offering multiple valid paths, these environments typically define a single “golden” path due to high annotation costs, limiting the scope of feasible planning strategies.
• Prompt-Based Planning Methods: A suite of techniques including task decomposition, multi-path selection, and reflection, implemented here with limited budgets to validate performance. These methods leverage the LLM’s inherent capabilities to structure complex interactions without additional model training.
• SayCan Value Function: A method that grounds LLM output actions into the action space using a specific value function. In this context, the value function is realized via the textual embedding model $bgesmall-en-v1.5$, mapping textual descriptions to feasibility scores within interactive gaming and question-answering contexts.
• Reflexion Mechanism: An error-correction capability where the agent consumes approximately twice the tokens compared to ReAct to review and refine its actions. This mechanism was configured with a round of retries in Reflexion set to 1, demonstrating improved success rates in complex tasks despite higher computational expenses.
• Action Space Unawareness: A limitation where zero-shot methods like ZeroShot-CoT fail because the model is unaware of the specific action space available in the environment. Consequently, methods requiring action space grounding, such as SayCan, are necessary for interactive tasks.
• Few-Shot Prompting: The inclusion of example instructions is suggested for complicated tasks to mitigate performance degradation. Without examples, the magic instruction “Let’s think step by step” is insufficient for LLMs to fully understand task constraints in benchmarks like HotPotQA and FEVER.

Key Equations and Algorithms

• Performance-Efficiency Relationship: The empirical observation suggests that planning performance $P$ scales with token expense $E$, where $P\propto E$. This relationship indicates that additional thoughts, plans, and reflections inherently require more tokens but yield detailed reasoning and improved outcomes.
• Reflexion Retry Procedure: The algorithmic procedure involves executing a task, evaluating the result, and retrying if unsuccessful. The specific configuration set the round of retries to 1, allowing the agent to incorporate feedback from previous failures into subsequent planning steps without infinite looping.
• Action Retrieval Logic: For web browsing and QA tasks, the system obtains 5 answers each step for CoT-SC, while gaming tasks yield 3 actions. This logic dictates the branching factor of the planning tree, where the agent must select the optimal action from the retrieved set based on the current state.

Key Claims and Findings

• Performance increases monotonically with computational expenses, as methods like CoT-SC, ReAct, and Reflexion involve multiple plans, additional thoughts, and reflections respectively.
• ZeroShot-CoT exhibits severe performance degradation in two question-answering benchmarks, demonstrating the necessity of few-shot examples for LLMs to understand complex task structures.
• Reflection plays a crucial role in improving success rates, particularly for complex tasks like ALFWorld and ScienceWorld, despite consuming about twice the tokens compared to ReAct.
• LLMs frequently suffer from hallucinations during the planning process, leading to irrational plans, unfaithfulness to task prompts, or the interaction with non-existent environmental items.
• Plans generated by LLMs often lack feasibility because statistical learning struggles to obey complex constraints, especially when dealing with less common constraints encountered during training.
• Existing LLM agents generate plans greedily based on output probabilities without considering the efficiency of the generated plans, necessitating additional efficiency evaluation modules.
• Current interactive environments are limited by a single “golden” path due to high annotation costs, lacking the fine-grained evaluation found in real-world scenarios.

Terminology

• Task Success Rate: The metric used to evaluate agent performance in interactive environments, defined by the binary outcome of completing the assigned task versus failure.
• Interactive Programming Environments: Systems that test agent planning by simulating interactions with computers through code or instruction writing, providing compile and runtime error feedback.
• Hallucination (Planning Context): A failure mode where the LLM plans actions interacting with items that do not exist in the environment or fails to follow complex instructions.
• Feasibility of Generated Plans: The property of a plan being executable within the constraints of the environment, which LLMs often fail to ensure due to their statistical optimization nature.
• Action Space: The set of valid actions available to the agent within a specific environment, which zero-shot methods fail to utilize without explicit grounding.
• Value Function: A mechanism used to ground output actions, implemented here as a textual embedding model $bgesmall-en-v1.5$ to assess action viability.
• Few-Shot Examples: Instructional examples provided to the model to aid understanding, which are shown to be necessary for complicated tasks where Zero-Shot methods fail.
• Golden Path: The single pre-defined correct sequence of actions in a simulated environment, contrasting with the multiple paths available in real-world scenarios.
• Multi-Modal Environment Feedback: The requirement for LLMs to process non-textual feedback from environments, identified as a critical area for future development in Chapter 9 conclusions.
• ZeroShot-CoT: A baseline method using Chain-of-Thought prompting without examples, which demonstrated degradation in specific QA benchmarks without few-shot support.