From Traces to Programs: Learning Programmatic Skill Routing for LLM Agents

Large Language Model (LLM) agents increasingly reuse skills distilled from prior experience, but deciding which skill to apply at each step of execution remains difficult. Existing approaches either provide all skills in context, increasing the reasoning burden during execution, or select skills by semantic similarity, conflating task relevance with applicability at the current step of execution. We introduce SCRIPT (Skill Composition and Routing via Interpretable Programmed Transitions), which represents experience as skill-level trajectories and separates local skill execution from global routing. Skills encode reusable procedures, while a coding agent learns an executable Python router from skill-level trajectories as execution unfolds. Minimum description length (MDL)-guided refinement favors compact routing programs, and a verifier evaluates each revision against cached routing decisions from prior and newly collected trajectories, without re-executing tasks. Separating skills from routing also enables failure attribution and repair. At deployment, the learned router selects skills directly without additional LLM calls. SCRIPT improves Success Rate over the strongest baseline by 21.1% on ScienceWorld and 11.5% on AppWorld while using up to 28.4$\times$ fewer learning tokens. With additional experience, verified router updates further improve task success while preserving prior routing decisions.