PaperlayerView exact revision on arXiv

Source-linked AI summary

Lifting Traces to Logic: Programmatic Skill Induction with Neuro-Symbolic Learning for Long-Horizon Agentic Tasks

Jie-Jing Shao, Haiyan Yin, Yueming Lyu, Xingrui Yu, Lan-Zhe Guo, Ivor Tsang, James Kwok, Yu-Feng Li

arXiv:2605.01293v1cs.AI

TL;DR

Foundation-model agents can struggle with long-horizon planning, and existing skill-induction methods often produce state-blind scripts that miss conditional logic. NSI lifts interaction traces into modular, logic-grounded programs with explicit control flow, dynamic binding, and reflective planning. Across embodied, web, and game domains, the paper reports that NSI compresses planning horizons and achieves efficient generalization.

  • Problem

    Foundation-model agents can have domain-specific reasoning gaps, while state-blind parameterized skills struggle to represent execution logic needed in dynamic environments.

    Source: §1 · p. 1

  • Method

    NSI lifts interaction traces into modular logic-grounded programs with explicit control flow and dynamic variable binding, and uses reflective planning to refine skill graphs from runtime failures.

    Source: §1 · p. 2

  • Results

    Across embodied, web, and game domains, NSI compresses planning horizons and achieves efficient generalization.

    Source: §7 · p. 9

  • Takeaways & Limitations

    Reflective planning can turn runtime failures into permanent logic improvements in skill graphs.

    Source: §1 · p. 2, §7 · p. 9

    More capable autonomous agents could be misused in sensitive domains, so the authors call for rigorous safety alignment and ethical guardrails.

    Source: §8 · p. 9

Abstract

from arXiv · show

Foundation model-driven agents often struggle with long-horizon planning due to the transient nature of purely prompting-based reasoning. While existing skill induction methods mitigate this by distilling experience into state-blind parameterized scripts, they fail to capture the conditional logic required for robust execution in dynamic environments. In this paper, we propose Neuro-Symbolic Skill Induction (NSI), a framework that lifts interaction traces into modular, \textit{logic-grounded} programs. By synthesizing explicit control flows and dynamic variable binding, NSI empowers agents to discover \textit{when} and \textit{why} to act. This paradigm enables the efficient generalization, allowing agents to induce skills from few-shot examples and flexibly adapt to unseen goals. Experiments on a series of agentic tasks demonstrate that NSI consistently outperforms state-of-the-art baselines, empowering agents to self-evolve into architects of logic-grounded skills.

1. Introduction

Foundation-model agents can struggle with domain-specific reasoning and long-horizon planning, while state-blind induced scripts may fail to capture the logic needed in changing environments. NSI lifts interaction traces into modular, logic-grounded skills with explicit control flow, dynamic variable binding, and reflective refinement.

1. Introduction

  • State-blind parameterized scripts struggle to represent execution logic and can fail when environmental deviations require checking conditions or branching.For example, an agent may need to check whether an apple is present after opening a fridge, then pick it or search elsewhere.Source: §1 · pp. 1–2, Figure 1 · p. 1
  • NSI redefines skills as modular, logic-grounded programs that lift interaction histories into control workflows with explicit symbolic predicates.The framework also enables dynamic variable binding to adapt execution to environments with varying topologies and recursive complexities.Source: §1 · p. 2
  • NSI’s representation uses First-Order Logic to provide explicit control flows and dynamic variable bindings for state-aware, modular skill composition.This contrasts with state-blind scripts that execute rigid action sequences.Source: §1 · p. 2
  • An empirical consistency objective iteratively consolidates local experts into global skills to maximize empirical coverage.The induction framework lifts individual instances into generalized programs.Source: §1 · p. 2
  • Reflective planning turns runtime failures into skill refinement by grafting successful recovery trajectories onto failure nodes.This mechanism is intended to let agents continuously grow their skill graphs during deployment.Source: §1 · p. 2

2. Related Work

Related work spans learned skills in traditional reinforcement learning, programmatic skill induction for foundation-model agents, and automated agentic workflow generation. NSI distinguishes itself by inducing state-grounded execution logic rather than relying on opaque policies, brittle scripts, or predefined reasoning nodes.

2.1. Skill Discovery in Traditional RL

  • Traditional reinforcement-learning skills encapsulate primitive actions into temporally extended behaviors, but are often black-box policies requiring costly, sample-inefficient optimization.These properties make them difficult to align with interpretable, text-based LLM reasoning and impractical to optimize at foundation-model scale.Source: §2.1 · p. 2

2.2. Programmatic Skill Induction in the LLM Era

  • Programmatic skill induction uses executable code to turn experience into reusable procedures, but parameterized scripts without logical grounding can fail under environmental change.Programs are synthesizable and understandable to foundation models, unlike opaque neural parameters.Source: §2.2 · p. 2

2.3. Automated Agentic Workflow Generation

  • Unlike workflow-generation methods that optimize prompts or topology over predefined reasoning nodes, NSI invents control and variable-binding nodes grounded in state.These nodes organize primitive actions and determine when and why to act.Source: §2.3 · p. 2

3. Preliminaries

The preliminaries cast agentic tasks as goal-conditioned planning and define programmatic skills as executable procedures for parameterized sub-goals. Skills are induced from successful trajectories to maximize execution success and, once validated, can be added to a skill library.

3. Preliminaries

  • The task is formulated as a goal-conditioned POMDP with raw states, observations, actions, a transition function, and goals.The agent must generate a trajectory ending in a state that satisfies the task goal.Source: §3 · pp. 2–3
  • The formulation uses object-centric relational features and task-related predicates to describe states and actions over environment entities.A ground atom expresses a predicate applied to specific arguments, such as Contains(bridge, apple).Source: §3 · pp. 2–3
  • A programmatic skill is executable code that composes primitive actions to achieve a parameterized sub-goal, and induction seeks to maximize execution success over successful trajectories.Validated skills enter a library as reliable sub-routines, expanding the agent’s available actions.Source: §3 · p. 3

4. A Neuro-Symbolic Skill Representation

NSI separates neural perception from symbolic execution in a graph-structured skill representation, grounding observations as predicates that govern actions. Its invented operators support variable binding, conditional control, execution feedback, and interactive traversal of the resulting workflow.

4.1. Skill Workflows with Neuro-Symbolic Grounding

  • A skill schema combines invocation parameters, a neural grounding module, and a symbolic execution graph to separate perception from execution logic.This neuro-symbolic representation is designed to transform static scripts into dynamic, logic-grounded workflows.Source: §4.1 · p. 3, §4 · p. 3
  • The neural grounding module converts raw observations into a structured symbolic state that the program can use to determine subsequent actions.The LLM updates predicates in response to environmental feedback.Source: §4.1 · p. 3
  • A symbolic interpreter executes the workflow graph, using grounded predicates and explicit branching to map different state configurations to actions.This makes the workflow adaptive to environmental feedback rather than a rigid sequence.Source: §4.1 · p. 3

4.2. Inducing Execution Logic via Node Invention

  • The workflow is a directed graph with shared scope for invocation parameters and intermediate variables, built from synthesized logic nodes rather than predefined tools.The modular node design supports localized refinement without regenerating the whole skill.Source: §4.2 · pp. 3–4
  • DataOps query symbolic state and update shared variables, enabling dynamically resolved action arguments instead of static values.The framework composes predicate and logical primitives into binding expressions, such as selecting a target object that satisfies a type and location condition.Source: §4.2 · pp. 3–4
  • CheckOps and LoopOps synthesize conditions for branching or iteration, while PrimitiveOps execute actions using arguments bound in shared scope.This connects state-dependent decision boundaries to grounded physical actions.Source: §4.2 · p. 4
  • TerminalOps report success or failure, with failure feedback providing a logic-grounded diagnosis that can inform replanning.The modular nodes also allow localized correction, such as refining a DataOp’s binding logic.Source: §4.2 · p. 4

4.3. Interactive Execution Semantics with Control Flow

  • During interactive execution, a semantic state tracker updates predicates from observations, an interpreter evaluates the current node for binding or branching, and primitive actions trigger environment transitions.The system emits a null action when the current node is not a primitive operation, leaving the observation unchanged.Source: §4.3 · pp. 4–5

5. Logic-Grounded Skill Induction

The section synthesizes sub-goal skills from segmented interaction traces, using trace-based consistency and iterative consolidation to build generalized programs. It also describes reflective execution that can refine skills after failures.

5. Logic-Grounded Skill Induction

  • Interaction trajectories are segmented into sub-goal-directed demonstrations that provide the data for skill induction.The framework lifts these instances into generalized programs through iterative refinement.Source: §5 · p. 5

5.1. Empirical Programmatic Consistency

  • Empirical programmatic consistency checks whether a skill reproduces expert actions from recorded states, while the induction objective balances consistency with program simplicity.The consistency region comprises states from which the skill reproduces subsequent expert actions; program complexity is penalized.Source: §5.1 · p. 5

5.2. Progressive Skill Induction from Experiences

  • Because direct global optimization is intractable, induction proceeds from trajectory-specific local experts to a generalized global skill under the Minimum Description Length principle.The process has intra-trajectory consolidation and inter-trajectory merging stages.Source: §5.2 · p. 5
  • Within each trajectory, the system refines a local expert when it finds an uncovered state, adding branches that can reveal conditional logic even from a single trace.The uncovered state is one where the current policy fails the consistency check.Source: §5.2 · p. 5
  • Across trajectories, the system repeatedly merges the least-covered local expert and accepts a candidate only when it expands coverage while preserving consistency.The Consolidate operator uses LLM-based synthesis and the MDL principle to avoid overfitting.Source: §5.2 · pp. 5–6
  • Structural operators generalize skills by adding predicate-guarded branches, reusing modular subgraphs, lifting constants into parameters, and folding repeated actions into loops.These operations handle divergent paths and equivalent resources while keeping programs compact.Source: §5.2 · p. 6

5.3. Online Skill Evolution via Reflective Planning

  • During planning, failed skills return symbolic diagnostics for corrective plans, and successful recovery logic can be added as a tentative branch and later solidified.When recovery fails, the skill description is updated to exclude the infeasible context.Source: §5.3 · p. 6

6. Empirical Study

The study evaluates NSI across three agentic benchmarks and reports consistent improvements over baselines. Its analyses connect those results to longer skills, sustained execution on long tasks, and online growth of skill graphs.

6.1. Experimental Setup and Baselines

  • Evaluation spans three agentic benchmarks—ALFWorld, WebShop, and TextCraft—comparing GPT-4o-backed methods against prompting, memory, decomposition, state-analysis, workflow, and programmatic-skill baselines.ALFWorld has 134 test instances across six task types and uses two demonstrations per task type for offline skill induction; WebShop skill induction uses one successful purchase trajectory. TextCraft has 200 recursive tasks at depths 2–4 and uses three expert trajectories at depth 1; reported mean ± standard deviation over three runs applies to skill-induction methods.Source: §6.1 · pp. 6–7

6.2. Main Results

  • NSI consistently improves performance over baselines across ALFWorld, WebShop, and TextCraft.The reported metrics are Success Rate for all three domains and Reward Score additionally for WebShop.Source: §6.2 · p. 7, Table 1 · p. 7
  • Reflexion yields negligible gains over ReAct, ADaPT’s decomposition is limited in ALFWorld, and linear programmatic scripts underperform text workflows.The paper links ADaPT’s limitation to partial observability and long-horizon execution, and the script gap to insufficient expressiveness for task logic.Source: §6.2 · p. 7
  • NSI executes 100%–140% more atomic steps per skill invocation than ASI while maintaining a high sub-goal success rate.The analysis attributes this efficiency to state-dependent logic, including conditional recovery and dynamic binding, inside each skill.Source: §6.2 · p. 8, Figure 4 · p. 8
  • Beyond 22 steps, baselines drop to zero success while NSI sustains performance for about 50 steps, with ∼7.4 atomic actions per skill.The paper describes this as compressing the planning horizon from fragile micro-management to macro-execution.Source: §6.2 · p. 8, Figure 4 · p. 8

6.3. Modular Skill Honing

  • During deployment, Reflective Planning turns runtime failures into corrective subgraphs grafted onto failure nodes, growing skills into branching recovery networks.The process preserves correctly functioning parts while adding conditional branches for emerging edge cases.Source: §6.3 · p. 8, Figure 3 · p. 8

7. Conclusion

NSI turns interaction traces into persistent, logic-grounded skills, with explicit control flows and dynamic bindings. Across embodied, web, and game domains, the paper reports planning-horizon compression and efficient generalization.

7. Conclusion

  • NSI lifts interaction traces into modular programs with explicit control flows and dynamic variable bindings.The framework also uses Reflective Planning to repair and grow skill graphs during deployment.Source: §7 · p. 9
  • Reflective Planning converts runtime failures into permanent logic improvements by autonomously repairing and growing skill graphs.The conclusion describes this as turning failures encountered during deployment into durable skill changes.Source: §7 · p. 9
  • Across embodied, web, and game domains, NSI compresses planning horizons and achieves efficient generalization.Source: §7 · p. 9

8. Impact Statement

The impact statement presents NSI as enhancing long-horizon planning and generalization for LLM-driven agents, while warning that more capable agents could be misused in sensitive domains. It calls for deployment alongside safety alignment and ethical guardrails.

8. Impact Statement

  • NSI is presented as enhancing long-horizon planning and generalization capabilities of LLM-driven agents.Source: §8 · p. 9
  • The statement warns that more capable autonomous agents could potentially be misused in sensitive domains.Source: §8 · p. 9
  • The authors call for rigorous safety alignment and ethical guardrails to mitigate risks of biased or unintended behaviors.Source: §8 · p. 9

A. The Representation Language of NSI

The representation language section specifies a Domain Specific Language for NSI’s logic-grounded skills. It uses a First-Order Logic-grounded vocabulary to bridge neural perception and symbolic execution.

A. The Representation Language of NSI

A.1. Syntax

The logic-grounded language has two layers: expressions query states and derive variables, while control structures define workflow branching and loops.

A.1. Syntax

  • The language separates expression operations from control-flow structure.Expressions query states and derive variables; control is encoded in the graph topology of πω.Source: §A.1 · p. 11
  • The expression layer uses first-order logic predicates and set operations to query states and derive variables.Examples include is open(x) and select one.Source: §A.1 · p. 11
  • The control layer encodes workflows, including conditional branching and loops, in the graph topology of πω.Source: §A.1 · p. 11

A.2. Semantics of Skill Nodes

A skill executes by traversing a graph whose nodes operate on shared scope and symbolic state. DataOps bind variables, ControlOps select branches, and primitive and terminal nodes handle execution and outcomes.

A.2. Semantics of Skill Nodes

  • Skill execution traverses graph Gω, with each node type operating on shared program scope C and symbolic state Z.Source: §A.2 · p. 11
  • DataOps resolve abstract variables from scope C against symbolic state Z and write concrete bindings back to C before actions.For example, a logic expression selects an apple that is clean and binds it as target.Source: §A.2 · p. 11
  • ControlOps evaluate predicates over scope and symbolic state to choose a branch, while task-specific predicates ground observations across ALFWorld, WebShop, and TextCraft.The example condition is is closed(target); a true result takes the Then branch and a false result takes the Else branch.Source: §A.2 · pp. 11–12, Table 3 · p. 12
  • Explicit condition checks let skills handle environmental variations such as open or closed doors without hallucinating actions.Source: §A.2 · p. 12
  • PrimitiveOps invoke environment APIs using arguments fetched from shared scope C.An example is Env.step(pick, id = target.id).Source: §A.2 · p. 12
  • TerminalOps end execution with a success or failure signal and return a symbolic diagnosis on failure.That diagnosis drives Reflective Planning.Source: §A.2 · p. 12

B. Experimental Details

This section details reproducibility settings and prompt constraints for grounding observations, extracting reusable sub-goals, and synthesizing executable skill workflows. It also describes a flow-graph scaffold and a two-stage prompt protocol for routing tasks to skills or raw actions and executing recommendations.

B. Experimental Details

  • All baselines use GPT-4o at temperature 0.0, and the paper says full prompts will be released with the code.The authors also provide key NSI system directives to support reproducibility.Source: B. Experimental Details · p. 12

OBSERVATION TO PREDICATES PROMPT

  • The observation prompt converts observations into newly entailed or falsified predicate facts, using canonical names and separate add- and remove-fact blocks.Its predicates cover location, reachability, receptacle state and contents, possession, and item properties; persistent facts are not repeated.Source: OBSERVATION TO PREDICATES PROMPT · pp. 12–14

SUBGOAL EXTRACTION PROMPT

  • Sub-goals must generalize beyond examples, use typed parameters, and specify checkable, minimal start and success conditions grounded in observable state.The prompt permits common types such as ReceptacleName, ItemName, and lists of allowed types.Source: SUBGOAL EXTRACTION PROMPT · pp. 14–15
  • Each sub-goal should capture multi-step intent rather than a single primitive action, with a sequence of 2–5 steps including at least two nonredundant actions; express branches and loops using production rules.Source: SUBGOAL EXTRACTION PROMPT · p. 16

SKILL INDUCTION PROMPT

  • The skill-induction prompt asks for one Mermaid flowchart per sub-goal, instantiated from its scaffold and interaction trajectories, with no prose.It directs the synthesizer to solve only the specified sub-goal.Source: SKILL INDUCTION PROMPT · p. 16

# Sub-goal to implement

  • The workflow specification requires distinct local and global variables, runtime placeholders, and resolvable parameters, while routing state writes through DataOp or LoopControl nodes.Check nodes alone branch using Yes/No labels, loops use body/done and Start Loop or Continue Loop edges, and selection helpers belong only in DataOp nodes.Source: # Sub-goal to implement · p. 17
  • Sub-goal graphs use unique node IDs, domain predicates and quantified checks, with object selection restricted to DataOp nodes.The predicate vocabulary includes location, containment, receptacle state, item state, and type checks; selection supports one or all items or receptacles.Source: # Sub-goal to implement · p. 17
  • The graph scaffold separates primitive actions, foreach-only loop controls, Yes/No checks, and global writes and data binding in DataOp nodes.Available action-node templates include navigation, opening, taking, moving, cleaning, heating, cooling, and using items.Source: # Sub-goal to implement · pp. 18–19

SKILL-ACTION ROUTER PROMPT

  • The router selects the active or next ordered sub-task, matches skill or action triggers to current facts, proposes up to three evidence-backed candidates, and recommends one or reports missing information.Candidates include an expected outcome; the recommendation may be a skill, action, or none.Source: SKILL-ACTION ROUTER PROMPT · p. 20

SKILL-ACTION EXECUTION PROMPT

  • The executor follows the routing recommendation unless impossible, avoids repeating failed choices, prioritizes applicable skills, and otherwise selects a raw action.Its JSON output includes reasoning, skill or action selection, start-condition evidence, a pre-span summary, intent, and parameter bindings.Source: SKILL-ACTION EXECUTION PROMPT · pp. 21–22

Related papers

Loading 2605.01293v1…