GARV: Graph-Aware Refinement and Safety Verification for High-Level Robot Plans

Stabak Das; Priyesh Ranjan; Xiangfang Li; Lijun Qian

cs.LGOct 2, 2026

GARV: Graph-Aware Refinement and Safety Verification for High-Level Robot Plans

Authors: Stabak Das, Priyesh Ranjan, Xiangfang Li, Lijun Qian

Organizations: CREDIT Center & Department of Electrical and Computer Engineering, Prairie View A&M University, Texas A&M University Systems, Prairie View, TX 77446, USA

Abstract

High-level robot actions such as goto(region) can hide intermediate traversal, allowing a monitor of the listed actions to accept a plan whose graph-level execution violates a safety rule. We present Graph-Aware Refinement and Verification (GARV), which composes graph-grounded action contracts with a safety monitor to produce a model-relative certificate or counterexample and, when route choice is enforceable, a minimum-cost safe refinement. In a 28-case controlled audit, refinement exposed all 12 targeted hidden hazards and produced the expected verdicts on 16 controls; a separate 14-case SPINE-RoboGuard instantiation yielded two false-safe cases and five action-interface errors. In standalone finite-graph simulation, all 16 designed cases met their expected outcomes, and product verification agreed with exhaustive enumeration on classification, minimum safe hop count, and witness safety in 160 comparisons across 40 graphs. Across 90 graph-contract evaluations on 30 graphs with a hazard deliberately placed on the selected shortest route, GARV found a safe refinement in 72 evaluations and no safe route within the permitted hop bound in 18. For the static forbidden-region rule, synthesis matched a simple hazard-deletion baseline in all 90 evaluations; GARV's guarantees remain conditional on the semantic graph, action contract, safety specification, and enforceability of any selected route.

Figures & tables

Fig. 1: Concrete SPINE-RoboGuard instantiation of graph-aware refinement and verification. The high-level plan, semantic graph, action contract, and safety monitor are the algorithm inputs. Refinement exposes intermediate events before monitor evaluation. The right-hand replanning and robot-execution pathway is conceptual and is not evaluated in the current experiments.

Suite/scenario	$n$	Hidden	Blocked	Safe	Err.
Controlled suite	28	12	2	14	0
Unique unsafe bridge	5	2	0	1	2
Matched safe corridor	3	0	0	2	1
Unsafe shortest route	3	0	2	0	1
Safe shortest route	3	0	0	2	1
End-to-end total	14	2	2	5	5

TABLE I: Observed outcomes. Hidden: surface trace accepted but graph-refined trace rejected. Blocked: unsafe event explicit in the surface trace. Safe: safe control accepted. Errors yield no safety verdict.

Case	Surface	Refined	S/R	Outcome
N2	$g_{L}$	$g_{C},g_{L}$	S/U	Hidden
N4	$g_{L},m_{L}$	$g_{C},g_{L},m_{L}$	S/U	Hidden
N5	$g_{C},g_{L}$	$g_{C},g_{L}$	U/U	Blocked
N7	$g_{C},g_{L},m_{L}$	$g_{C},g_{L},m_{L}$	U/U	Blocked
C2	$g_{L}$	$g_{H},g_{L}$	S/S	Safe
C4	$g_{L},m_{L}$	$g_{H},g_{L},m_{L}$	S/S	Safe

TABLE II: Representative end-to-end traces.

C

H

, and

L

are the construction region, safe hallway, and laboratory.

g_{X}

denotes goto (

X

);

m_{X}

denotes map_region (

X

). S/U reports the surface/refined verdict.

Fig. 2: Mean monitor-call time overall and by action family (case counts in parentheses). Only validate_action_sequence was timed; the bars do not measure end-to-end latency.

Case	Selected	Permitted	Safe route
RS01: tied shortest paths	Safe	Mixed	2 hops
SR01: safe detour	Unsafe	All unsafe	3 hops
SR04: wider contract	Safe	Mixed	2 hops
SR05: checkpoint first	Unsafe	All unsafe	3 hops
RS05: forbidden bridge	Unsafe	All unsafe	None

TABLE III: Representative designed cases. “Selected” checks one canonical shortest route; “permitted” classifies every route in the verification contract. A synthesized safe route may use a broader, explicitly controllable contract. Hops count graph edges.

Regions	Slack	Safe route	V (ms)	S (ms)
25	0	6/10	0.093	0.093
25	2	7/10	0.276	0.287
25	4	8/10	0.514	0.543
49	0	5/10	0.123	0.137
49	2	10/10	0.427	0.462
49	4	10/10	0.912	0.957

TABLE IV: Synthetic graph scaling. Each row evaluates ten worlds; each world is reused for three slack settings. Times are median Python wall times in ms for product verification (V) and synthesis (S), excluding graph construction and external systems.

Robot Safety

Robot safety studies how to prevent harmful physical actions while enabling robots to complete tasks around people and in uncertain environments.

See all 230 papers

Refuse the Harm, Complete the Task via Graph-of-Rules Planning for LLM-Enabled Robots
Oct 17, 2026Ali Taheri, Alireza Taban, Qizhou Wang +1LLM Agent Safety Large Language Model-Based Robot Planning
Nanyang Technological University · Queen’s University · RIKEN AIP
SafeInferCom: Safe Inference-Time Compute via Verifier-Guided Mid-Generation Intervention for Robotic Task Planning
Oct 8, 2026Weizhe Xu, Jialiang Fan, Mengyu Liu +1Large Language Model-Based Robot Planning Inference-Time Guidance
University of Notre Dame · Washington State University
Using large language models for embodied planning introduces systematic safety risks
Apr 20, 2026Tao Zhang, Kaixian Qu, Zhibin Li +4Large Language Model-Based Robot Planning Robot Safety
ETH Zurich, Zurich, Switzerland. · University College London, London, United Kingdom. · Stanford University, Stanford, California, United States. +2

Oct 17, 2026J/K move · Enter open · S save

Refuse the Harm, Complete the Task via Graph-of-Rules Planning for LLM-Enabled Robots

Ali Taheri, Alireza Taban, Qizhou Wang, Wanhua Li

Nanyang Technological University · Queen’s University · RIKEN AIP

LLM Agent Safety Large Language Model-Based Robot Planning LLM Safety Evaluation Symbolic Planning

Open paper AskPDF arXiv

Large Language Models (LLMs) are increasingly used in embodied AI for robotic manipulation and planning, but their deployment in physical systems exposes vulnerabilities such as jailbreak attacks that induce unsafe behavior. Existing inference-time defenses are mainly evaluated on short instructions containing a single hazard, whereas realistic tasks may interleave safe and unsafe sub-tasks, conceal hazardous steps, or combine individually safe actions into unsafe outcomes. Such compound instructions make it harder for a single safety decision to distinguish hazardous sub-tasks from legitimate ones, risking either overlooking the hazard or rejecting the whole instruction. We introduce safe task completion, a task that requires an LLM-enabled robot to refuse the harmful part of an instruction while completing its legitimate part. To address this problem, we propose RuleGraph, a multi-agent Graph-of-Rules planning framework that distributes safety enforcement across multiple reasoning and verification stages. Five cooperating agents are used to ground general safety principles into world-specific rules, assess the instruction's sub-tasks in context, and derive a safe goal from the legitimate ones. Planning toward this goal is then organized as a graph of rule-specific nodes, where higher-level nodes inherit the union of their parents' rules, and candidate plans are progressively verified and aggregated until a single plan satisfies every relevant rule. In this way, RuleGraph reduces reliance on a single centralized safety decision. We evaluate RuleGraph on pure-attack and compound instructions across two benchmarks in two environments using Attack Success Rate (ASR) and Task Success Rate (TSR). RuleGraph reduces ASR to 0% on both benchmarks while achieving the highest TSR among all methods, reaching 98.57% on the RoboGuard benchmark and 84.54% on our long-horizon compound instructions.

Abstract

Robot Safety

Explore similar work

Refuse the Harm, Complete the Task via Graph-of-Rules Planning for LLM-Enabled Robots

SafeInferCom: Safe Inference-Time Compute via Verifier-Guided Mid-Generation Intervention for Robotic Task Planning

Using large language models for embodied planning introduces systematic safety risks