Technical Summary: TraceCompiler

Problem Definition

Tool-using language model (LLM) agents frequently rediscover procedures they have already executed, incurring significant costs in token usage and latency. A single recurring intent (e.g., requesting a payment or listing tickets) often triggers a trace containing a mix of reusable structure (necessary tools, true data dependencies, stable configuration) and accidental execution history (retries, schema-discovery lookups, stylistic ordering, and repeated fact resolution).

Current approaches, such as summarizing traces as textual guidance, still require the LLM to reinterpret the procedure at runtime. Conventional process discovery is insufficient because observed event order does not imply dependency; consecutive calls may result from independent operations, failed attempts, or data flow. Furthermore, deployed logs often suffer from partial observability, recording arguments but not tool outputs, making it impossible to verify dependencies by matching producer outputs to consumer inputs.

The core challenge is to compile noisy, partially observable agent traces into executable, mostly deterministic workflows where decisions supported by evidence are removed from the model's runtime responsibility, leaving only genuinely open choices for the LLM.

Methodology

TraceCompiler is a skill-guided system that mines clusters of noisy traces and compiles them into typed workflows. The pipeline consists of the following stages:

1. Intent Discovery and Clustering

Conversations are embedded as documents combining the initial request and interleaved reasoning/tool calls. Threshold agglomeration (cosine distance, average linkage) groups traces into intent clusters. The system prioritizes conservative under-merging to avoid contaminating distinct intents. Idempotent pre-passes detect and split conversations mixing unrelated intents.

2. Normalization and Behavioral Denoising

Raw traces are normalized to a canonical app.action vocabulary. Actions are labeled as:

• Essential: Required for the task.
• Recovery/Exploratory/Redundant: Retained for analysis but potentially removable.
• Dead Output: Actions whose outputs are never consumed downstream (e.g., schema lookups).
• Retry vs. Variation: The system distinguishes between noise (jittering arguments converging to a success) and genuine fan-out (systematically distinct arguments, e.g., per-song searches). Pagination loops are detected via literal counters.

3. Argument-Level Dependency Verification

This is the core innovation. An edge $a \to b$ is admitted as a hard dependency only if:

1. A value in $b$'s argument is traceable to $a$'s output.
2. Exclusion: Every alternative origin for that value is excluded (user utterances, static context, tool defaults, and outputs of all other preceding calls).

If a plausible alternative origin exists (e.g., two type-compatible producers), the edge is downgraded to suspected and imposes no ordering constraint. This prevents the compiler from inferring false dependencies based solely on adjacency.

4. Provenance Classification and Static Context

Bindings are classified into:

• Constant: Stable across traces (resolved at build time).
• User Input: Resolved at runtime.
• Copy Edge: A value proven to originate from a specific producer.
• Transform: Deterministic transformations.
• LLM/Dynamic: Genuine semantic bindings requiring runtime model resolution.

The compiler is specified to perform scope-bound static-context injection, resolving stable values at build time and forbidding the discovery tools for those values at runtime. However, this feature was not exercised in the reported results; neither case study reports an injected value, and the design element remains awaiting evidence. If an irreversible side effect is under-determined (e.g., the direction of a mutation is ambiguous), the compiler abstains and emits no executable graph, escalating the request instead.

5. Compilation and Runtime

The analysis is compiled into an executable definition (DAG) with typed nodes (TOOL, TRANSFORM, DECISION, LLM, HUMAN). The runtime router dispatches requests to compiled workflows if they match a conservative similarity threshold; unmatched requests fall back to the general agent.

The compiler's engine (v1) is implemented as a versioned LLM skill—an instruction package loaded by an agent—rather than a trained model. This allows for adversarial auditing and rapid revision without retraining.

Key Contributions

1. Formulation: Framing recurring agent-trace reuse as a compilation problem over workflow structure, parameter provenance, and residual LLM decisions under partial observability.
2. Pipeline: A complete unsupervised pipeline for intent discovery, behavioral denoising, dependency verification, provenance classification, and executable workflow generation.
3. Dependency Rule: A formalized, conservative argument-level dependency rule that admits edges only via exclusion of alternative origins. It introduces explicit evidence tuples and a "suspected" relation for ambiguous cases.
4. Evaluation: Evaluation against two ground truths (T1 and AppWorld) that share no machinery, comparing against order-based and recurrence-based baselines.
5. Case Studies: Demonstration of successful compilation (Venmo money request) and refusal to compile (Spotify/Todoist) when irreversible side effects are under-determined.

Results

Dependency Accuracy

• T1 Corpus (Training Split): The mechanized rule achieved 0.928 precision and 0.943 recall on 15,775 def–use edges. This significantly outperforms adjacency-based baselines (0.711 F1) and frequency-thresholded directly-follows measures (0.712 F1).
  • Caveat: Ablation studies reveal that on this specific corpus, the exclusion test is nearly vacuous because every relation has at least one candidate producer. Consequently, the reported accuracy relies heavily on recency (selecting the most recent survivor) among surviving candidates rather than the full exclusion test. The exclusion discipline is exercised by the LLM skill, not the mechanized rule, due to corpus limitations.
• Blind Skill Run: On a 250-edge subset of T1, the LLM skill achieved 0.992 precision/recall in a single run.
• AppWorld: Against a replay-based reference (which recovers masked values), the rule achieved 0.993 precision on 563 token edges. This serves as a self-consistency check rather than an independent validation, as the reference construction shares the same assumption (preferring same-application tokens) as the rule being tested. Furthermore, this arm bounds session-token attribution only and does not validate the recovery of non-token identifier flows.

Workflow Compilation and Execution

• Venmo Intent: Compiled 34 observed API calls (including retries and schema lookups) into 11 runtime calls. The workflow passed 15 of 21 state tests on withheld instances. The 6 failures occurred because the specific branch required for the held-out instance was never observed in the training set, causing the system to escalate rather than act.
• Spotify/Todoist Intent: The compiler correctly refused to compile this intent because the direction of the mutation (add vs. remove) was under-determined by the traces, representing an irreversible side effect.
• Call Reduction: Across 56 AppWorld scenarios, the median removable fraction of calls (schema discovery and byte-identical repeats) was 51.4%.

Intent Discovery

On T1, the clustering achieved 0.930 purity over covered dialogues but a low Adjusted Rand Index (0.235) against reference labels. This indicates the system discovers a partition finer than the reference labels (subdividing domains into template-level tasks) rather than misclassifying them.

Significance and Claims

The paper claims that observed adjacency does not imply dependency. By enforcing an evidence discipline that requires the exclusion of alternative origins, TraceCompiler can compile noisy traces into deterministic workflows that reduce runtime tool calls and LLM invocations.

• Safety: The system prioritizes safety over completeness. It abstains from compiling workflows where irreversible actions are under-determined, preventing the execution of unsafe, speculative procedures.
• Efficiency: While the paper measures call reduction (e.g., 34 $\to$ 11 calls), it explicitly does not claim net efficiency because offline compilation costs are not measured. The economic premise is that a capable model can amortize the cost of analysis over repeated executions.
• Limitations: The authors acknowledge that the current evaluation relies on synthetic or simulator-generated data. The "exclusion" discipline is exercised by the LLM skill but not fully by the mechanized rule due to corpus limitations (lack of decoy tokens). The system currently lacks workflow versioning and invalidation mechanisms for API drift.

The work establishes that observational traces bound claims about necessity as tightly as they bound claims about dependency, and that the instruments used to test compiled workflows (execution harnesses) are themselves inference procedures requiring validation.