PASTA: PROVENANCE-GUIDED ABDUCTIVE SELECTION FOR TAILORED AGENTS

Self-correction repairs a failed LLM agent from feedback on its final output, and a common design choice is to revise or regenerate that output as a whole. We show that, for agents that act on a user profile, this discards information that the trajectory carries in the provenance of its commitments. The dominant failure, which we call inference promotion, turns an inference about the user into a constraint the user never stated and builds later decisions on it; it accounts for 55% of 300 annotated natural failures. PASTA extracts a provenance-typed belief graph from the trajectory, scores each commitment that could explain a verifier-reported violation by a provenance prior and predicted repair, and regenerates from the candidate that best trades this score against downstream cost. With gold answers withheld from every model-visible stage, PASTA reaches 74% repair success against 66% for matched Reflexion and 68% for the strongest simple restart rule, and its margin grows with the number of faults. On five multi-hop and planning benchmarks with injected faults and identical feedback, it outperforms the strongest baseline on every dataset by 2.6 to 9.8 points. On the 300 natural failures, it repairs 76% against 64% for matched full-output retry, comes within one point of annotated-root restart, and cuts reuse of the unsupported belief on follow-up tasks from 30% to 10%. Provenance relative to the user profile is a repair signal, and where to restart is a different question from where the fault began.