Rebind: Learning Safer Agent Skills from Evolving Experience

Even a successful execution can leave a skill's incorrect rules undetected. For example, a reusable calendar skill might select the correct participants by choosing the first matching meeting, but then invite the wrong people after the meeting is canceled and recreated. Simply fixing an execution error might allow the invitations to be sent, but it leaves the selection rule unchanged. We propose Rebind, which learns safer executable skills by building rehearsals from the current skill. Each rehearsal changes the environment surrounding the objects used by the skill while maintaining the feasibility of the requests. Task results and actual effects provide feedback for repair. In the calendar example, Rebind detects invitations to former participants and repairs the skill to copy participants from the current confirmed meeting. It replays previous requests and rehearsals to check the revision, then uses the revised skill to build the next rehearsal. Across ten tool workflows, Rebind safely completes all 462 controlled conditions, compared with 425 for a baseline that prepares rehearsals in advance, and reduces harmful conditions from 33 to zero. The learned skills can be reused directly without further language-model calls. On 3,018 injected AgentDojo and AgentDyn conditions, Rebind completes 86.1% of tasks with a 0% attack success rate, compared with 78.4% and 14.4%, respectively, for SkillOpt.