Lifting Traces to Logic: NSI and the Evolution of State-Aware Agents

TL;DR

The "reasoning" of current AI agents is often transient—once a task is over, the logic is lost. Neuro-Symbolic Skill Induction (NSI) changes this by "lifting" execution traces into permanent, logic-grounded programs. Unlike previous methods that just memorize action sequences, NSI invents control flows (branches and loops) and dynamic variable bindings, allowing agents to solve complex, 50+ step tasks where traditional models fail.

The Problem: The Fragility of "State-Blind" Scripts

Most current agents learn "skills" as simple macros: Open(Fridge) -> Pick(Apple). But what if the fridge is already open? Or what if there is no apple inside?

Existing Programmatic Skill Induction methods suffer from being state-blind. They struggle with:

1. Environmental Deviations: They cannot handle unexpected changes in the world.
2. Horizon Collapse: Errors accumulate over long sequences, leading to a total failure in tasks requiring more than 20-30 steps.
3. Rigid Binding: They often hard-code object IDs instead of understanding the logic of why an object was chosen.

Methodology: The Neuro-Symbolic Architecture

NSI solves this by decoupling Neural Perception from Symbolic Execution.

1. The Skill Representation

A skill in NSI is not a list; it is a Directed Acyclic Graph (DAG) of logic nodes:

• DataOp: Logic meant for "Thinking"—resolving which object to interact with using First-Order Logic (e.g., Find an item that is 'clean' and 'edible').
• Check/LoopOp: Decision gates that determine "When" and "Why" to act based on the current state.
• PrimitiveOp: The actual physical interaction (e.g., take apple).

2. Trace-to-Logic Induction

The system watches successful demonstrations and "lifts" them into these graphs. It uses the Minimum Description Length (MDL) principle to ensure the programs are concise but cover as many scenarios as possible. If two traces differ, the system "invents" a predicate (a conditional branch) to explain why the agent acted differently in those two cases.

Experiments: Overcoming the Long-Horizon Collapse

The results are striking. In ALFWorld, NSI reached a 98% success rate, but the most interesting finding is the Horizon Compression.

While baseline agents (like ReAct or Reflexion) undergo a "Long-Horizon Collapse" after 22 steps, NSI maintains high performance up to 50+ steps. It does this by encapsulating roughly 7.4 atomic actions into a single modular skill, essentially shrinking the complexity of the task for the LLM planner.

Continuous Evolution: Honing the Skills

NSI doesn't stop learning once the code is written. Through Reflective Planning, if a skill fails during execution, the agent analyzes the failure, finds a recovery path, and grafts that new logic back into the original skill graph. This turns a "mistake" into a permanent upgrade of the agent's capability.

Critical Insights & Conclusion

NSI represents a significant move away from "Prompt Engineering" toward "Software Engineering" for agents. By treating skills as executable, verifiable programs rather than just text snippets, we gain:

• Interpretability: You can read the Mermaid graph to see exactly why an agent branched.
• Robustness: The agent checks the state before it tries to open an already-open door.
• Efficiency: Significant planning overhead is removed by calling high-level macros.

Limitations: Currently, NSI relies on a predefined vocabulary of predicates. Future work will likely focus on unsupervised predicate invention, where the LLM determines which state variables are worth tracking without human guidance.

Final Takeaway: To build agents that can handle the complexity of the real world, we must stop giving them "scripts" and start teaching them "logic."