Interactive and Expressive Code-Augmented Planning with Large Language Models

Motivation

• Code-augmented planning can struggle with fuzzy subproblems, bottom-up task construction, and coding bugs.Fuzzy tasks may require interpreting unstructured observations or subjective choices; accurate code can also be difficult to produce in one pass.Source: §1 · pp. 1–2

Approach

• REPL-Plan has an LLM write and execute code line by line, then recursively spawn child LLM-REPLs for top-down subtasks, including fuzzy ones.The interactive REPL lets the model inspect results and correct mistakes as it proceeds.Source: §1 · p. 2

Contributions

• The paper reports strong REPL-Plan performance in ALFWorld, WebShop, and a real-world web-navigation task involving complex observations.The introduction also says the authors test robustness through ablations involving faulty demonstrations and/or incorrect short-term decisions.Source: §1 · pp. 2–3

2.1 Problem Statement

• Interactive planning tasks require agents to act from observations over multiple timesteps, often using expert demonstrations; code can structure decisions for complex, long-horizon tasks.REPL-Plan is proposed to address fuzzy subproblems, bottom-up planning, and coding errors.Source: §2.1 · p. 3

2.2 LLM-REPLs

• A REPL evaluates code one statement at a time and displays outputs, allowing the model to respond to results and correct mistakes.LLM-REPLs extend this paradigm by recursively spawning child REPLs to solve top-down subtasks, including fuzzy ones.Source: §2.2 · p. 3
• Child LLM-REPLs receive parent arguments and return answers, but do not share the parent's variable state.The subtask, get_args, and answer primitives manage spawning and context passing.Source: §2.2 · p. 3

2.3 REPL-Plan

• REPL-Plan runs REPL code until an act call interacts with the environment, with observations available for processing and REPL history reused across tasks.Figure 2 illustrates dividing a search-page task into filtering the current page, parsing item links, and matching item pages to a description.Source: §2.3 · pp. 3–4, Figure 2 · p. 4

3.1 Environments

• The experiments cover ALFWorld household tasks, WebShop product selection, and real-world web navigation with pages of 4k–20k tokens.Real-world tasks include simple item additions and complex searches for multiple items matching specified attributes.Source: §3.1 · p. 5

3.2 Results

• On ALFWorld, REPL-Plan achieved 97.0% success rate (SR), compared with THREAD’s 95.5% SR.Both approaches divide tasks into subtasks and can change plans when environment issues arise.Source: Table 1 · p. 5, §3.2 · p. 5
• THREAD’s recursive and dynamic elements accompany high success on ALFWorld and k=3 WebShop, but it fails to scale to k=10 WebShop and real-world web tasks.The authors identify code expressivity as important for high success in WebShop and real-world web settings.Source: §3.2 · p. 5
• On WebShop, THREAD led the Top-3 setting at 49% SR, while REPL-Plan reached 52% SR with GPT4o-mini in the k=10 Page setting.The k=10 setting tests strategies that search beyond the first three items, including Top-20.Source: Table 2 · p. 6, §3.2 · p. 6
• On complex real-world web tasks, REPL-Plan reached 39.6% of expert score, versus 17.6% for ReACT and 0.0% for THREAD.The pages contained 4k–20k tokens; the authors report that THREAD could not effectively plan with these long observation contexts.Source: Table 3 · p. 6, §3.2 · p. 6

3.3 Ablations

• With minor demonstration bugs, REPL-Plan was relatively robust, failing only one more GPT-4o-mini task than without errors.The injected errors were unescaped strings and missing variable definitions.Source: §3.3 · p. 7
• Without child LLM-REPLs, WebShop performance fell from 52% to 24% for GPT-3.5-instr. and from 44% to 20% for GPT-4o-mini.The authors attribute the difficulty to accumulated code and observation history becoming too large without task decomposition.Source: §3.3 · p. 7
• When a required subtask REPL was removed, the LLM inferred its description and code correctly in half of trials, with performance falling to 28% from 52% and 16% from 44%.The respective model pairs are GPT-3.5-instr. and GPT-4o-mini; incorrect inference often led to a failure loop.Source: §3.3 · p. 8

LLM-Agents

• LLM-agents often turn observation–action histories into single actions; code augmentation and recursive task division have also been proposed to address hallucinated actions and planning.Source: §4 · p. 8

Code-Augmented LLMs

• PAL (Gao et al., 2023) runs generated Python for reasoning tasks, while REPL-Plan targets interactive decision-making; CodeAct and Mint (Wang et al., 2024a, 2023c) target human-user tasks.Source: §4 · p. 8
• AdaPlanner (Sun et al., 2023) refines code plans but is non-interactive because the plan must be written in one pass.Source: §4 · p. 8

Decomposing Tasks

• Compared with THREAD (Schroeder et al., 2024), REPL-Plan supports arbitrary code and reusable named child REPLs, rather than anonymous, non-reusable subtasks.Source: §4 · p. 8

5 Conclusion

• REPL-Plan extends the REPL paradigm with interactive code generation and recursively spawned child REPLs, and reports superior performance to baseline methods across diverse planning benchmarks.Source: §5 · p. 9

6 Limitations

• Generalization beyond k-shot settings remains difficult for zero-shot code on substantial new subtasks and for code that is improperly structured.Source: §6 · p. 9
• Some subtasks solvable with pure code still use an LLM-REPL; automating such subtasks is proposed as future work to improve efficiency.Source: §6 · p. 9

A.1 LLM-REPL Implementation

• Algorithm 1 is titled “LLM-REPL Pseudocode.”Source: §A.1 · p. 12

• Initialization takes the task description as input to the LLM-REPL constructor.Source: §1 · p. 12
• The program state is seeded with get_args, answer, act, and get_obs primitives.Source: §1 · p. 12
• Control checks whether a new REPL block is needed.Source: §1 · p. 12

• Generated code is executed with the REPL's locals as its environment.Source: §11 · p. 12
• The history records formatted code, stdout, and stderr.Source: §11 · p. 12
• The code-finished-without-interrupt condition marks a distinct execution outcome.Source: §11 · p. 12

• Runtime NameErrors provide a flexible trigger for creating a child LLM-REPL when a function or variable is undefined.The text notes that determining undefined functions or variables in advance is undecidable.Source: §14 · p. 12
• The implementation saves each REPL iteration's state and reruns code after a NameError creates a child REPL.An alternative is to intercept errors in a modified interpreter and synchronize parent-child execution with threads or coroutines.Source: §14 · p. 12
• Rerunning can repeat context-sensitive calls, so per-REPL call counters and cached returns avoid duplicate computation and must sync across parent-child context passing.Source: §14 · p. 12
• Undefined-variable mistakes raise REPLNameError feedback, while an undefined function call can dispatch to its named child REPL.The examples distinguish an undefined max_price variable from a get_max_price() call.Source: §14 · p. 13
• In the count-to-four example, the main REPL delegates even-number counting and passes context between REPLs before producing the final action trace.Source: Figure 4 · p. 13

• On the authors’ codebase, GPT4o and GPT4o-mini tended to loop after observations by generating #START# tokens.Source: §A.2 · p. 13
• The authors suggest GPT4o-series models may follow web-task demonstrations less reliably than GPT3.5-instruct.Source: §A.2 · p. 13
• The modification re-queries generations containing #START#, then adds a “don’t loop” prompt if the token recurs.Source: §A.2 · p. 13
• 21% WebShop success: the modification improved THREAD from always looping with GPT4o-mini.Source: §A.2 · p. 14

A.3 WebShop GPT4o-mini experiment details

• THREAD’s Top-20 strategy looped indefinitely, while Top-3 used the same prompts as the GPT-3.5 setting for both THREAD and REPL-Plan.Both Top-3 and Top-20 strategies were tested for THREAD and REPL-Plan.Source: §A.3 · p. 14

A.4 Real-World Web Task Details

• The real-world environment exposes pruned browser accessibility trees with unique IDs for interactive elements, and web pages can be 10–20 times longer than the Google example.Tasks span five e-commerce sites, from adding any matching item to finding all items matching specific attributes; each approach-task combination was run for three trials and averaged against an author-completed expert score.Source: §A.4 · pp. 14–15

A.5 WebShop Example Top-3 Trajectory

• Across four logged helper-function errors, the trajectory records Name errors for generate_query, filter_ids_by_price, select_best_product, and check_requirements, followed each time by “injecting with cached LLM func.”Source: §A.5 · pp. 15–17
• In the top-3 trajectory, REPL-Plan checks listings against request requirements, scores candidates by matches, and selects a highest-scoring product.For one headset listing, it counts only the noise-cancelling requirement as met; the selection code returns the first candidate tied for the maximum score.Source: §A.5 · pp. 18–19
• When purchase helpers are undefined, the trajectory injects cached LLM functions, checks for options, and clicks Buy Now to complete the purchase flow.The trace shows missing buy_best_product and select_options functions being injected, then no page options found before the Buy Now action.Source: §A.5 · p. 19

A.6 WebShop REPL-Plan Prompt Samples

• In the shopping example, the prompt’s 3-ounce bright-citrus deodorant request is represented by non-price attributes; code generates and submits a search query, selects the best product, then calls the purchase routine.Source: §A.6 · p. 20
• The WebShop prompt samples decompose shopping into query generation, candidate scoring against product requirements, and selecting variations before purchase.The examples search for a product, inspect candidate pages and score matching requirements, then select required buying options and click Buy Now.Source: §A.6 · pp. 20–21

A.7 WebShop Ablation Bug correction Samples

• Hand-picked WebShop examples show REPL-Plan recovering from demonstration bugs, including malformed quoted strings and an undefined max_price variable.The examples show syntax errors being corrected by escaping quotes and a NameError addressed by defining max_price.Source: §A.7 · pp. 21–22

A.8 WebShop Ablation Zero-shot Subtask-REPL Analysis

• The zero-shot ablation removes the demonstrated check_description REPL, requiring the agent to infer code for reading requirements, inspecting product pages, and returning matching-attribute counts.The appendix includes successful GPT3.5-instruct examples, including one that counts three matching attributes.Source: §A.8 · pp. 22–23
• One agent misunderstands the task and attempts to click a product, but recovers and completes it.The example's click attempt produces a NameError because product_id is undefined.Source: §A.8 · p. 23
• The GPT3.5-instruct samples generally show agents with the “right intentions” failing because their code contains bugs or crashes the system.The appendix labels these as failed code samples.Source: §A.8 · p. 23
• Another failure misunderstands how to parse and string-match attributes.Its task is to count attributes matching the product description, but the example is explicitly identified as a parsing and matching failure.Source: §A.8 · p. 24
• One failure misinterprets the task and enters a looping fail state.The example then attempts to use a scores dictionary operation that raises an AttributeError.Source: §A.8 · p. 24
• A separate example counts matches by string-matching the description instead of matching attributes to the product page.The example is explicitly characterized as using the wrong matching approach.Source: §A.8 · p. 24