💻 computer science

VASO: Formally Verifiable Self-Evolving Skills for Physical AI Agents

VASO is a novel framework that enables the self-evolution of LLM-generated robot skill contracts through formal verification, using counterexamples to iteratively refine reusable skills against temporal safety specifications without modifying foundation model weights, thereby achieving high compliance on physical agents with minimal optimization samples.

Original authors: Yunhao Yang, Neel P. Bhatt, Kevin Wang, Samuel Tetteh, Zhangyang Wang, Ufuk Topcu

Published 2026-06-05

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yunhao Yang, Neel P. Bhatt, Kevin Wang, Samuel Tetteh, Zhangyang Wang, Ufuk Topcu

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

The Big Problem: "Smart" Robots That Can't Be Trusted

Imagine you hire a very talented, creative chef (the AI) to write recipes (skills) for a robot kitchen. The chef can write a recipe for "Make a sandwich" or "Avoid the cat" in seconds.

However, there's a catch: Just because the recipe sounds good in English doesn't mean the robot won't burn the house down.

Current methods try to fix this by letting the robot try the recipe, seeing if it fails, and asking the chef to rewrite it. This is like tasting a soup and saying, "It's too salty, try again." But this only tells you the soup was salty this one time. It doesn't prove the recipe is safe for every possible situation (like if the stove gets too hot, or if a cat jumps on the counter).

The Solution: VASO (The "Mathematical Editor")

The authors introduce VASO, a system that acts like a strict, mathematical editor for these robot recipes. Instead of just tasting the soup, VASO checks the recipe against a set of unbreakable safety laws (like "Never touch fire" or "Always stop if a person is near").

Here is how VASO works, step-by-step:

1. The "Translator" (The Bridge)

Robots speak "code" (move left, stop, speed up), but safety rules are written in "logic" (If Person is Seen, Then Stop).

The Analogy: Imagine the robot is a foreigner who only speaks "Robot," and the safety inspector only speaks "Logic."
What VASO does: It creates a translator (called a labeling function) that instantly converts the robot's movements into logical statements. This allows the safety inspector to understand exactly what the robot is doing.

2. The "Math Check" (Formal Verification)

Before the robot even tries the recipe, VASO runs a mathematical simulation.

The Analogy: Think of this like a flight simulator for a pilot. Before the plane takes off, the simulator runs millions of scenarios to see if the flight plan crashes into a mountain.
What VASO does: It checks if the recipe could ever break the safety rules. If the math says "Yes, this recipe might crash," it doesn't just say "Fail." It finds the exact moment the crash happens (the "counterexample").

3. The "Text Gradient" (The Feedback Loop)

This is the magic part. Usually, when a math check fails, you have to rewrite the whole code. VASO is smarter.

The Analogy: Imagine the math check sends the chef a note that says: "Your recipe says 'Walk forward' even when a person is there. Change that line to 'Stop'."
What VASO does: It turns the math failure into a text instruction (a "textual gradient"). It tells the AI chef exactly how to rewrite the recipe itself to fix the error.
Crucial Detail: The AI chef's brain (the underlying model) stays frozen. We aren't retraining the chef; we are just editing the specific recipe card they wrote.

Why This is a Big Deal

The paper tested this on two real robots: a ground robot (like a Roomba on steroids) and a drone.

The Result: VASO got the robots to follow safety rules 97.2% of the time using fewer than 100 tries.
The Comparison: Other methods (like just asking the AI to try again, or retraining the AI's brain) were either less safe or took much longer and cost more computing power.

The "Self-Evolving" Part

The paper calls this "Self-Evolving Skills."

Old Way: You train a robot on a million examples, and it learns a general "feeling" of what to do.
VASO Way: You give the robot a specific skill (like "Drive"), check it with math, find the flaw, and update the skill definition. Now, that same skill is better for every future task. It's like upgrading the blueprint of a car engine so that every car built from that blueprint is safer, rather than just fixing one specific car.

Summary in One Sentence

VASO is a system that uses mathematical proof to find flaws in robot instructions, translates those flaws into simple text feedback, and automatically rewrites the robot's "skill recipes" to be perfectly safe, without needing to retrain the AI's brain.

What the Paper Does Not Claim

It does not claim this works for medical surgery or life-or-death decisions yet (it was tested on navigation and drones).
It does not claim the robot is "conscious" or "understands" safety; it just follows the mathematically verified rules.
It does not claim this works for every possible robot scenario instantly; it relies on the "translator" (labeling function) being written correctly. If the translator makes a mistake, the math check might give a false sense of security.

Technical Summary: VASO – Formally Verifiable Self-Evolving Skills for Physical AI Agents

Problem Statement

Reusable robot skills serve as the interface between foundation models and physical control, allowing embodied agents to execute long-horizon tasks under safety constraints. While foundation models have reduced the cost of generating these skills from natural language, they have not solved the problem of skill assurance. Existing self-evolving methods rely on "soft" feedback signals—such as execution outcomes, unit tests, environment rewards, or LLM self-critique. These signals provide only trace-level evidence, demonstrating that a skill worked on sampled executions but failing to guarantee that the skill-induced plans satisfy temporal safety contracts under untested conditions. In robotics, a single rare but severe safety violation (e.g., a ground robot moving after detecting a person) is unacceptable, yet soft feedback often fails to detect these edge cases.

The core challenge is to close the loop between formal verification and skill evolution without merely filtering unsafe plans or fine-tuning model weights. There is a need for a representation where formal counterexamples can directly update reusable skill contracts, ensuring that improvements are inspectable, reusable, and verifiable.

Methodology: VASO Framework

The authors propose VASO (Verification-Guided Automated Skill Optimization), a closed-loop framework for the self-evolution of LLM-generated robot skill contracts. VASO operates by treating skills as semantic contracts that couple a formal interface with a planner-facing interface.

1. Verifiable Skill Representation

A skill $sk$ is defined as a tuple $(G, \psi_{sk}, C_{sk})$ :

$G$ (Global Specifications): A set of LTL formulas representing safety constraints that must always hold.
$\psi_{sk}$ (Local Rule): An LTL formula defining the specific intent or goal of the skill.
$C_{sk}$ (Semantic Contract): The core component consisting of:
- $L_{sk}$ (Proposition-Aligned Labeling Function): A function that maps low-level robot states, observations, and control commands to atomic logical propositions. This bridges the gap between physical execution and symbolic model checking.
- $C^p_{sk}$ (Text-Based Plan Template): A behavioral prior that guides the planner in generating executable commands (e.g., API calls or trajectories).

2. Two-Level Verification Loop

VASO employs a hierarchical verification process to refine skills:

Skill-Level Verification (Feasibility Check): Before sampling plans, the framework checks if the local rule $\psi_{sk}$ is logically consistent with the global specifications $G$ . A universal transition system is constructed to verify satisfiability. If the local rule contradicts global safety (e.g., a rule commanding movement when a person is observed), the skill is rejected, and the foundation model is queried to refine the local rule.
Plan-Level Verification (Behavioral Check): Once a feasible skill is obtained, a planner generates an executable plan $\pi$ . This plan is compiled into a symbolic transition system (automaton) using the labeling function $L_{sk}$ . A model checker (NuSMV) verifies the plan against $G \land \psi_{sk}$ .

3. Optimization via Textual Gradients

When verification fails, the model checker returns a counterexample trace. VASO converts this trace into a textual gradient (e.g., "violate specification: $G(\text{person\_observed} \to X \text{ stop})$ "). This textual feedback is fed back into the foundation model to update the semantic contract $C_{sk}$ and the local rule $\psi_{sk}$ .

Key Constraint: The foundation model weights remain frozen. The optimization occurs entirely at the prompt/contract level, refining the reusable skill artifact rather than tuning the model parameters or a single task prompt.
Process: The loop alternates between forward generation (Contract $\to$ Plan $\to$ Automaton) and backward refinement (Automaton $\to$ Textual Gradient $\to$ Updated Contract).

Key Contributions

Verifiable Self-Evolving Skill Representation: The paper introduces a skill structure that explicitly connects temporal-logic specifications, proposition-aligned robot semantics, and planner-facing templates. This allows LLM-generated skills to be used for planning while remaining exposed to formal verification.
Formal Counterexamples as Optimization Feedback: The authors develop a two-level verification loop where counterexample traces are converted into textual gradients. This enables the refinement of the reusable skill contract itself, rather than just rejecting a specific plan or tuning a prompt.
Physical-Agent Validation: The framework is validated on real robotic platforms (Clearpath Jackal and PX4 quadcopter), demonstrating that optimized skills can achieve high formal specification compliance without fine-tuning the underlying foundation model.

Empirical Results

The framework was evaluated on 11 temporal-logic specifications across 400 generated plans on two robotic platforms.

Compliance: VASO achieved 97.2% formal-specification compliance using fewer than 100 optimization samples (under 20 minutes per skill).
Comparison: It outperformed zero-shot baselines, prompt-optimization methods (like LAD-VF), and fine-tuning-based approaches (like RLVF). Notably, VASO reached higher safety scores than fine-tuning methods while requiring only a fraction of the training cost and time.
Generalization: Optimized skills demonstrated strong generalization to unseen task prompts within the same task family, maintaining high safety and task completion rates without additional refinement.
Automatic Alignment: The study showed that automatically generated proposition-aligned labeling functions performed on par with handcrafted mappings, eliminating the need for manual domain expertise in defining symbolic abstractions.

Significance and Claims

The paper claims to be the first framework to close the loop between formal verification and self-evolving LLM-generated skills for physical AI agents.

Shift in Paradigm: Unlike standard verified planning pipelines that use verification merely as a pass/fail filter for one-off plans, VASO uses the reason for rejection (the counterexample) to improve the source of the plan (the reusable skill).
Efficiency and Safety: By optimizing the skill contract rather than model weights, VASO provides a mechanism for generating safer, more reliable behaviors that are inspectable and reusable across different tasks, addressing the critical bottleneck of skill assurance in physical AI.
Limitations: The authors acknowledge that the formal guarantees are conditional on the correctness of the AI-generated proposition-aligned labeling function. Errors in mapping low-level dynamics to symbolic propositions could lead to spurious verification results, though empirical data suggests this occurs infrequently (<1% degradation in safety scores). The current framework also assumes sequential, non-concurrent execution.