💬 NLP

Skill-as-Pseudocode: Refactoring Skill Libraries to Pseudocode for LLM Agents

The paper proposes Skill-as-Pseudocode (SaP), an automatic method that converts free-form markdown skill libraries into typed pseudocode with deterministic verification, enabling LLM agents to achieve significantly higher success rates and reduced token usage on the ALFWorld benchmark by providing clear typed signatures and concrete invocation templates.

Original authors: Xinze Li, Yuhang Zang, Yixin Cao, Aixin Sun

Published 2026-05-28

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Xinze Li, Yuhang Zang, Yixin Cao, Aixin Sun

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are teaching a very smart but literal robot how to do chores, like cleaning a house or organizing a kitchen. You give the robot a giant, messy instruction manual written in normal English (Markdown).

The Problem: The "Confused Loop"
Every time the robot needs to do something, it has to read through long paragraphs of text to figure out two things:

What the task is (e.g., "move the mug").
Exactly how to say it to the house's computer system (e.g., the system only accepts the command move mug to shelf, not put mug on shelf).

Because the instructions are buried in paragraphs, the robot often guesses wrong. It tries to "put" the mug, the house says "Nothing happens," and the robot gets confused. It then goes back to read the manual again, guesses wrong again, and gets stuck in a loop of failure. This wastes time and makes the robot run out of energy (or "tokens," in AI terms).

The Solution: "Skill-as-Pseudocode" (SaP)
The authors of this paper created a system called Skill-as-Pseudocode (SaP). Think of this as a "translator" that takes the messy human manual and rewrites it into a clean, structured cheat sheet for the robot.

Here is how the translator works, using a simple analogy:

1. The Detective (Finding Patterns)

Imagine a librarian who looks through hundreds of different instruction manuals. They notice that many manuals say the same thing in different ways.

Manual A says: "Go to the kitchen, grab the salt, and put it in the cabinet."
Manual B says: "Find the salt on the counter and move it to the cupboard."

The librarian realizes these are actually the same underlying action. They group these similar instructions together into a "cluster."

2. The Architect (Drafting the Blueprint)

For each group of similar instructions, the system asks an AI to draft a Typed Contract.

Instead of a paragraph, this contract looks like a computer function: move_object(from: "counter", to: "cabinet").
It clearly lists: What inputs are needed? What happens after? What are the rules?

3. The Safety Inspector (The Four Checks)

Before the system lets the robot use this new blueprint, a strict Safety Inspector runs four specific checks to make sure the translation is perfect:

Coverage: Did we miss any important details from the original text?
Binding: Do we know exactly where to get the "salt" or "mug" from the original sentence?
Replacement: If we swap the old paragraph for this new blueprint, does the rest of the manual still make sense?
Risk: Does this new instruction accidentally tell the robot to do something dangerous (like delete a file or break a window)?

If the blueprint passes all four checks, it gets approved. If it fails even one, it is thrown out to prevent the robot from getting confused.

4. The Delivery (The "Bundle")

When the robot needs to do a task, it doesn't get the old, messy manual. Instead, it gets a Bundle that has three parts, presented in the perfect order:

The "How-To" Template: The exact words the robot must type to the house computer (e.g., move {object} to {target}).
The "What" Signature: A clear summary of what the skill does.
The Context: The rest of the instructions, now cleaned up so they don't contradict the new template.

The Results

The researchers tested this on a game called ALFWorld, where an AI agent has to solve household puzzles.

Old Way (Graph-of-Skills): The robot read the messy manual, guessed wrong, got stuck in loops, and failed often.
New Way (SaP): The robot got the clean "cheat sheet." It knew exactly what to do and how to say it immediately.

The Outcome:

The robot solved 82 out of 134 games with the new method, compared to only 47 with the old method.
It also used 22% less memory and made 14% fewer calls to the AI brain because it didn't have to re-read the manual over and over when it got stuck.

In Short:
The paper shows that if you stop giving AI agents long, messy paragraphs and instead give them structured, verified "code-like" instructions, they stop getting confused, stop making mistakes, and get the job done much faster. The system acts like a rigorous editor that turns human prose into robot-ready blueprints.

Technical Summary: Skill-as-Pseudocode (SaP)

Problem Statement

Modern LLM-based agents rely on skill libraries—collections of procedural documents (typically Markdown) that agents retrieve and follow during task execution. However, these libraries are currently authored as free-form prose. This representation creates a significant bottleneck: the agent must re-derive both the input schema (what the skill does) and the concrete invocation syntax (how to call it) on every retrieval.

The authors observe that this prose-heavy format induces a "confused → re-retrieve → still confused" loop. When an agent issues a partially correct action based on a prose description, the environment often returns uninformative feedback (e.g., "Nothing happens"). The agent then re-retrieves the same prose, fails to extract the missing detail, and repeats the cycle. This loop drives both task failures and inflated LLM call costs. While typed catalogs like OpenAPI exist, they are not the standard deployment surface for agent skills, which remain in Markdown.

Methodology: Skill-as-Pseudocode (SaP)

The authors propose Skill-as-Pseudocode (SaP), an automatic pipeline that converts Markdown skill libraries into typed pseudocode with deterministic quality control. The core insight is that two specific signals short-circuit the retrieval-action loop:

A Typed Contract: A structured signature exposing the trigger, input/output schemas, and pre/post-conditions.
Concrete Action Templates: The exact token sequences the environment accepts (e.g., move {obj} to {target}), distinct from the abstract contract.

The Pipeline

The SaP pipeline processes a library of parent skills (Markdown documents) through five stages plus two LLM-aware post-verifier passes:

Parser: Splits Markdown documents into procedural units (sections under headings).
Candidate Proposer: Groups units from one or more parents into candidate clusters based on shared verbs, objects, and code linkage using embedding-based clustering.
Contract Extractor (LLM): For each cluster, a single LLM call drafts a strict JSON typed contract ( $\kappa$ ).
Verifier (Deterministic): A four-check deterministic verifier evaluates the draft contract. A contract is only promoted if it passes:
- Coverage: The contract's trigger and I/O strings must be present in the parent unit text.
- Binding: Every required input in the contract must have a corresponding span in the parent text.
- Replacement: The parent unit must be syntactically replaceable by an invoke(κ, args) placeholder without breaking control flow.
- Risk: The contract must not contain unsafe side effects (e.g., rm -rf, undeclared network egress).
Refactor: Validated contracts are inlined into the parent skills.
- Binding Extraction (BE): An LLM pass that verifies if a specific unit is a genuine instance of the contract and extracts the specific argument bindings. Spurious matches are dropped.
- Rewrite Cleanup (RC): An LLM pass that detects and rewrites residual prose conflicts (e.g., an example block using a verb like put when the environment requires move) to align with the verified contract.

Retrieval-Time Substitution

At inference time, the agent retrieves a substituted skill bundle rather than raw prose. For a retrieved parent skill, the system replaces the original content with:

Action Templates: Concrete, executable command sequences with extracted bindings (placed first).
Rewritten Skeleton: The parent structure with invoke(κ, args) placeholders.
Inlined Contract: The typed signature and schema for the invoked child skill.

Crucially, the system employs a hierarchical-only retrieval pool. Promoted child contracts are stored internally and are only accessible via the parent's invoke placeholder. Surfacing children as standalone top-level results is avoided, as it deprives the agent of the necessary context (the parent's action templates).

Key Contributions

Reframing Skill Improvement: The paper reframes skill-library optimization as a prose-to-typed-pseudocode conversion problem with deterministic quality control, complementing existing typed-routing work that assumes contracts already exist.
The SaP Pipeline: A novel architecture featuring a four-check deterministic verifier and two LLM-aware post-verifier passes (BE and RC), each guarded by deterministic post-checks to ensure safety and consistency.
Hierarchical Retrieval Interface: A retrieval mechanism that delivers a structured bundle (typed contract + concrete template) per invocation, separating the "what" (contract) from the "how" (template).
Empirical Validation: Demonstration that SaP simultaneously improves task success rates and reduces token/LLM call costs compared to the Graph-of-Skills (GoS) baseline.

Results

Experiments were conducted on the ALFWorld unseen split (134 games) using gpt-4o-mini and a subset of SkillsBench (10 tasks) using gpt-5-codex.

ALFWorld Performance: Across three seeds (402 paired games), SaP won 82/402 games compared to 47/402 for the GoS baseline. This represents a 74% relative reward increase (McNemar $p = 8.2 \times 10^{-5}$ ).
Efficiency Gains: SaP achieved these gains while reducing input tokens by 22.8%, output tokens by 17.3%, and LLM calls by 14.5% per game.
Mechanism Analysis: The improvement is attributed to breaking the "retrieval-action loop." SaP agents issued significantly fewer "Nothing happens" errors and re-retrieval requests. Post-retrieval action correctness improved from 20.5% (GoS) to 29.3% (SaP).
Ablation: Removing the hierarchical separation (surfacing children as standalone results) caused a 27% drop in reward, confirming the necessity of the parent-child bundle structure. The BE and RC passes were shown to repair distinct failure modes (spurious cluster membership and syntax conflicts, respectively).

Significance and Claims

The paper claims that the prose representation itself, rather than a lack of factoring, is the dominant bottleneck for LLM agents consuming skill libraries. By automating the conversion of prose to typed pseudocode with deterministic verification, SaP provides agents with a "what" (contract) and "how" (template) signal in a single response.

The authors position SaP as a producer-side solution to the typed-routing problem. While existing work assumes contracts are hand-written, SaP recovers them from prose. The methodology is presented as a disciplined approach where every LLM extraction is a hypothesis checked by deterministic rules, rather than a black-box output.

The paper modestly notes that while the pipeline is architecturally supported for typed APIs (OpenAPI), the current empirical evaluation is limited to Markdown libraries. Furthermore, the replacement mechanism is static (syntactic) rather than dynamic (runtime expansion), relying on the retrieval interface to provide child contracts on demand. The results suggest that for static skill libraries, the cost of prose-to-structure conversion can be paid at index time rather than at every retrieval, significantly improving agent efficiency and reliability.