Towards Effective Data Structures for AI Agents in Complex Real World Jobs

AI agents generate rich execution trajectories, but standard frameworks typically store experience as prose-heavy message logs, leaving downstream agents to reconstruct implicit interaction semantics. We introduce TRACE (Trajectory Representation for Agent Context and Experience), a write-time protocol that makes interaction structure explicit without introducing additional task requirements or evaluator outcomes. TRACE labels each message with its type and coordination state, links it to the message it answers, tags evaluator feedback by dimension, and derives each evaluation's outcome; the linked messages form a directed graph that preserves response lineage across attempts. On 62 real-world web-development jobs, an agent using TRACE passes 53.2% of jobs versus 16.1% with plain text on the first attempt, 71.0% versus 48.4% within two attempts, and 74.2% versus 69.4% within the maximum of three attempts. On the 41 jobs completed by both conditions, agents using TRACE need 37.4% fewer attempts on average.