Audit an Agent Trace for Step Limits and Loops

1. Background Knowledge

Agent Traces represent the chronological history of actions taken by an autonomous AI agent. In production systems, these traces are critical for debugging and safety monitoring. An Agent Loop Control mechanism is a safety guardrail designed to prevent agents from entering infinite loops or exceeding computational budgets. Without these controls, agents can waste resources or hang indefinitely, a common failure mode in early large language model (LLM) based agents.

The core concept here is Canonicalization. To detect repeated actions, we must normalize the representation of each step. Two steps are considered identical if they use the same tool and the same arguments, regardless of the order in which the arguments were provided in the dictionary. By converting each step into a deterministic string signature, we can easily compare steps for equality. This process involves sorting dictionary keys and formatting them into a standard string structure.

Maximal Runs refer to contiguous sequences of identical elements in a list. Identifying these runs is a classic pattern matching problem. The distinction between a "loop" (consecutive identical steps) and a "ping-pong" (alternating steps) is crucial. A naive frequency count would incorrectly flag alternating patterns as loops. Therefore, the algorithm must track the current run length and reset it whenever the signature changes, only flagging a violation if the run length meets or exceeds a specified threshold.

2. Algorithm Approach

The problem can be solved using a Single-Pass Linear Scan with state tracking. This approach is efficient because it processes the trace exactly once, maintaining the necessary context to detect both step limits and consecutive loops.

1. Preprocessing: First, check the total number of steps against max_steps. If the limit is exceeded, record the step limit violation immediately.
2. Signature Generation: For each step in the trace, compute its canonical signature. This involves handling missing args (defaulting to an empty dict), sorting the keys of the args dictionary, and formatting them into the string tool|k1=v1,k2=v2.
3. Run Detection: Iterate through the list of signatures. Maintain a current_run_start index and a current_run_length.

• If the current signature matches the previous one, increment the run length.
• If it differs, check if the previous run length was $\ge$ repeat_limit. If so, record a violation for that run. Then, reset the run tracking variables to start a new run at the current index.

4. Final Check: After the loop ends, perform one final check on the last run to see if it constitutes a violation.
5. Result Compilation: Collect all violations, sort them lexicographically, and determine the ok status based on whether the violations list is empty.

3. Step-by-Step Strategy

1. Initialize Variables: Create an empty list violations. Define a helper function or inline logic to generate the signature for a single step.
2. Check Step Limit: Compare len(steps) with max_steps. If len(steps) > max_steps, append "step_limit:<len(steps)>" to violations.
3. Handle Edge Cases: If steps is empty, return {"ok": True, "steps_used": 0, "violations": []} immediately.
4. Iterate and Track Runs:

• Initialize run_start = 0 and run_len = 1.
• Loop from index i = 1 to len(steps) - 1.
• Compute sig_prev (signature of steps[i-1]) and sig_curr (signature of steps[i]).
• If sig_curr == sig_prev, increment run_len.
• If sig_curr != sig_prev:
• Check if run_len >= repeat_limit. If true, append "repeat_loop:<sig_prev>@<run_start>" to violations.
• Reset run_start = i and run_len = 1.

5. Post-Loop Check: After the loop, check the final run. If run_len >= repeat_limit, append the violation for the last signature starting at run_start.
6. Sort and Return: Sort the violations list. Return the dictionary with ok = len(violations) == 0, steps_used = len(steps), and the sorted violations.

4. Common Pitfalls

• Dictionary Key Ordering: Python dictionaries preserve insertion order, but the problem requires canonicalization. Always sort the keys of args before joining them. {"b": 1, "a": 2} must produce the same signature as {"a": 2, "b": 1}.
• Missing Arguments: The problem states args may be absent. Ensure your code handles step.get("args", {}) to avoid KeyError or TypeError when trying to iterate over None.
• Off-by-One Errors in Runs: Be careful with the indices. The violation should report the starting index of the run. If a run starts at index 0 and has length 3, the violation is @0, not @2 or @3.
• Final Run Missed: A common bug is forgetting to check the last run after the loop terminates. The loop only checks for violations when a run ends (i.e., when the signature changes). The very last run never "changes" within the loop, so it must be checked explicitly after the loop.
• Sorting Violations: The problem requires the violations list to be sorted ascending. Since violations are strings, standard lexicographical sorting applies. Ensure you sort the list before returning.

5. Time & Space Complexity

Time Complexity: $O(N \cdot K \log K)$, where $N$ is the number of steps and $K$ is the maximum number of arguments in a single step.

• We iterate through the steps once ($O(N)$).
• For each step, we sort the argument keys. Sorting $K$ keys takes $O(K \log K)$.
• String joining and comparison take $O(K)$ time.
• Sorting the final violations list takes $O(V \log V)$, where $V$ is the number of violations. Since $V \le N$, this is bounded by $O(N \log N)$.
• Overall, the dominant term is usually the signature generation: $O(N \cdot K \log K)$.

Space Complexity: $O(N \cdot K)$ for storing the signatures and violations.

• We store the signature for the current and previous steps, which is $O(K)$.
• In the worst case, every step is a violation (e.g., repeat_limit=1), so we store $N$ violation strings. Each string is $O(K)$ length.
• Thus, the space complexity is $O(N \cdot K)$.