Audit an Agent Trace for Step Limits and Loops

easyFREEAgent Loop Control & PlanningAI AgentsAI Agents 1

Problem Statement

The defining failure of the first generation of autonomous agents was not bad reasoning - it was never stopping. AutoGPT would search the same query, read the same page, decide it needed more information, and search again, until someone killed the process. Every serious agent runtime now ships a guard that watches the trace and trips.

Background

An agent trace is a list of steps, each an action with arguments. Two guards:

Step limit. If the trace is longer than max_steps, that is a breach - the agent overran its budget.

Repeat loop. Compute a canonical signature for each step:

tool + "|" + ",".join(f"{k}={args[k]}" for k in sorted(args))

Then look for consecutive runs of identical signatures. A maximal run of length >= repeat_limit is one breach, reported once, at the run's starting index.

Consecutive matters. A, B, A, B, A, B is a ping-pong, not a stuck action - a naive implementation that just counts occurrences would flag it, and would then trip on any agent that legitimately alternates between two tools. Only an unbroken run counts here.

Your Task

Implement:

def audit_trace(steps, max_steps, repeat_limit):

steps: list of {"tool": str, "args": dict} - args may be absent, meaning {}.

Return {"ok": bool, "steps_used": int, "violations": list[str]} where violations are:

"step_limit:<len(steps)>" when the trace overran
"repeat_loop:<signature>@<start_index>" for each maximal run of length >= repeat_limit

Sort the violations list ascending before returning. ok is True only when it is empty.

Input/Output Format

Returns the three-key dict. Argument values are stringified with str(), and argument keys are sorted so that {"a":1,"b":2} and {"b":2,"a":1} produce the same signature.

Sample

steps = [{"tool": "search", "args": {"q": "x"}}] * 3
print(audit_trace(steps, 10, 3)["violations"])
# ['repeat_loop:search|q=x@0']

Example

Input

steps = [{'tool': 'search', 'args': {'q': 'x'}}] * 3
print(audit_trace(steps, 10, 3)['violations'])

Output

['repeat_loop:search|q=x@0']

Reasoning

Inputs: steps is a trace of 3 actions, each the tool search called with the single argument $q = x$ . The budget max_steps is 10 and repeat_limit is 3.
Signatures: each step becomes the tool name, a pipe, then its arguments as key=value pairs in ascending key order. With one argument, all three steps read search|q=x, so positions 0, 1 and 2 are identical.
Runs: the identical signatures sit back to back with nothing in between, so they form one maximal run covering indices 0 to 2, of length 3. Since $3 \ge 3$ , it is a loop, reported once at its first index: repeat_loop:search|q=x@0.
Step limit: the trace length is 3 and $3 \le 10$ , so no budget breach is added.
Output: the violations list holds exactly one entry. Notice that with repeat_limit set to 4 the same trace would be clean, because a run of 3 falls short, giving ok true and no violations.

Constraints

0 <= len(steps) <= 1000; max_steps >= 0; repeat_limit >= 2
Signature keys are sorted ascending; values are stringified with str()
Only consecutive identical signatures count as a loop
Each maximal run yields exactly one violation, at its start index
The step-limit check is strict: len(steps) > max_steps
The violations list is sorted ascending

Learn this in

The Agent Loop & ReAct FoundationsAgent Engineering Study Plan Multi-Agent Coordination & Failure ModesAgent Engineering Study Plan Production: Observability, Benchmarks, Runtimes & Eval-Driven DevelopmentAgent Engineering Study Plan Planning Patterns: Plan-and-Execute, ReWOO, HTNAgent Engineering Study Plan

More from AI Agents 1

Cheapest Cache TTL Meeting a Freshness SLAhard Bootstrap Confidence Interval Width for Eval Accuracymedium Route to the Cheapest Model Meeting Qualitymedium pass@k Estimatormedium Savings from a Semantic Cachemedium

Concept primer

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.

Preprocessing: First, check the total number of steps against max_steps. If the limit is exceeded, record the step limit violation immediately.
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.
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.

Final Check: After the loop ends, perform one final check on the last run to see if it constitutes a violation.
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

Initialize Variables: Create an empty list violations. Define a helper function or inline logic to generate the signature for a single step.
Check Step Limit: Compare len(steps) with max_steps. If len(steps) > max_steps, append "step_limit:<len(steps)>" to violations.
Handle Edge Cases: If steps is empty, return {"ok": True, "steps_used": 0, "violations": []} immediately.
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.

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.
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)$ .

solution.py

Python 3.13

Test results