RobustAgent: Provable Recovery Guarantees for Long-Running Autonomous Agents Under Adversarial Interrupts

Long-running autonomous agents face a critical challenge: maintaining correct state and recovering gracefully when interrupted by adversarial attacks or system failures.We present RobustAgent, a framework that integrates and formalizes checkpoint-based recovery with cryptographic verification to provide provable robustness guarantees for stateful autonomous agents.Our key contributions include: (1) formal definitions of state consistency and recovery correctness for persistent agents, (2) adaptive checkpointing with a capped exponentialbackoff schedule that bounds the replay window while minimizing per-checkpoint storage through incremental delta encoding, (3) binarysearch recovery over a root-validated hash chain with O(|S|(log n + k)) total time complexity, and (4) resistance to time-shifted prompt injection attacks.Experimental validation on more than 500 synthetic agent workflows demonstrates a 100% recovery success rate, 82.6× faster recovery than naive restart (0.39 ms vs. 32.2ms), 75.2% attack detection, and a 96.5% storage reduction compared to naive periodic checkpointing, reflecting a deliberate storage-recovery trade-off relative to fixed-interval baselines.This work provides a theoretical foundation and practical implementation for deploying autonomous agents in production environments requiring formal robustness guarantees.