Paper · 2026-11-08 · cs.SE, cs.AI
Replay Fidelity in LLM Agent Evaluation: Randomness, Hidden State, and Test Oracles in AppWorld
Replays all 71 failed executions of one historical AppWorld corpus with fixed code. Strict admission (printed output, database deltas, native verdict) admits 42 replays under declared settings and 68 when the RNG is reset before each interaction. Database, RNG and export effects are measured case by case (author-reported).
LLM agentAgent trace replayBenchmark validityTool useagentsevaluationreproducibilitydebuggingbenchmark
AI-compiled by claude-haiku-5-5 on 2026-11-21, not yet reviewed by a human. Every claim cites its source; check it when a detail matters.
In plain words
Engineers debug AI agents by re-running a recorded failed attempt. A replay is only useful if it really reproduces what happened: the same printed output, the same changes to the test database and the same final verdict. This paper takes 71 failed attempts from an older AppWorld benchmark run, replays each one with the original code unchanged, and checks those three things.
The replay rules matter a lot. Under the strict rule, 42 of 71 replays are accepted when the random-number generator is set up as the original run declared. When it is also reset before each step, 68 are accepted. Most of that difference goes away when the database and test-oracle checks are applied, but not all of it. Some runs match on output and verdict and still leave different rows in the database. Some depend on hidden state, such as an authentication token whose value can come out equal under controlled random settings.
The authors also show one fix. Exporting the database after the test oracle has run changed the comparison for some cases. Exporting from output trackers that were saved before the oracle ran restored it. The results describe one old benchmark version and one model lineage. They do not estimate how often these problems occur in general.
TL;DR
- The study audits all 71 unsuccessful executions in one historical AppWorld corpus. Each replay uses the archived code unchanged and runs in two fresh processes §2.1 tab. 1.
- Strict admission (printed output, pre-oracle database deltas, native verdict and test counts) accepts 42 of 71 with the declared settings and 68 of 71 when the RNG is reset before each interaction (author-reported) §3.1 tab. 2.
- Under the database/oracle check the 26-case gap shrinks to four. One endpoint stays unknown under both controls §3.1 tab. 2 fig. 1.
- Output and verdict can match while materialized database rows differ. An identical API call can give different row effects depending on future Python RNG state §4.2 §5.2.
- Exporting after the oracle changes the comparison for all 10 affected cases. Exporting from output trackers saved before the oracle restores it without changing the cached contents §7.1 §7.2.
Problem
Replay is used for agent debugging, failure analysis and counterfactual evaluation, but a replay that prints the same text is not automatically the same execution. A replay can be rejected because a printed output differs even though the state matches, or accepted because only printed text and the verdict were compared §1. The paper asks three questions. How does execution control (RNG handling and reconstructed settings) change admission under a fixed validation target? Which differences in materialized rows or continuations appear when the checked observations agree? Can post-oracle exclusions be localized and corrected at the export step? §1
The paper makes no claim about debugger accuracy, repair gains or effects on method rankings §1.1 §9.2.
Study design
The source is an archived set of 147 historical train/dev ReAct executions run under the GPT-4o-2024-05-13 alias. Of these, 76 are native-evaluator successes and 71 are failures spread over 32 task families. Thirty failures were inspected earlier and 41 were not measured before §2.1. The output bundle is version 0.1.3. Per-record code, data and evaluation metadata are version 0.1.0. The reference endpoint is the agent's final database change stream, not a gold correct-solution terminal state §2.1.
| Study block | Source unit | Attempts | Role |
|---|---|---|---|
| Primary AppWorld census | 71 failures, 32 families | 284 | Two fresh processes per control; one C resource-censored case tab. 1 |
| Fixed-code completion | 25 early N text stops | 50 | Runs the remaining recorded code without replacing actions §2.1 tab. 1 |
| Earlier mechanism studies | 1 credential case; 10 export cases | 16 + 20 | Kept separate from the census tab. 1 |
| Closeout supplement | Existing cases and a known control | 66 | 58 complete, 8 censored or unknown tab. 1 tab. 5 |
| BFCL pilot | 10 failures and 2 successes | 24 | Independent second environment §8.1 tab. 1 |
Missing repetitions stay in the record and are not filled in tab. 1 tab. 4. Resource-censored attempts and infrastructure deviations are kept as evidence §2.3.
Method
Replay controls
Both controls start a fresh AppWorld 0.1.0 world and run the archived code unchanged §2.1.
- N (declared settings): seed 123 and a 60 s cell timeout §2.1.
- C (N plus RNG reset): the same, and additionally
random.seed(123)immediately before each recorded interaction §2.1. C is a uniform intervention, not a proof that the original RNG lifecycle was reproduced §9.3.
# Replay one archived case under a control [§2.1]
# Input: archived case (recorded interactions), policy "N" or "C"
# Output: replayed observations (printed output, deltas, verdict)
def replay_case(case, policy):
# N: declared seed 123 as recorded in the reconstruction [§2.1]
random.seed(123)
for interaction in case.interactions:
# C only: reseed before every recorded interaction [§2.1]
if policy == "C":
random.seed(123)
# Each cell is limited to 60 s [§2.1]
run(interaction, cell_timeout=60)
return observations(case)The primary protocol stops at the first output mismatch. A separate fixed-code completion study runs the remaining recorded code without replacing any actions §2.1.
Admission rule
A replay is admitted under the primary rule only if three checks pass in fresh processes: O AND D_pre AND V §2.2.
- O (outputs): printed outputs are equal after CRLF normalisation and outer-whitespace stripping. Nothing else is normalised §2.2.
- D_pre (database deltas): all 12 archived delta files are byte-equal to the replayed ones, checked against both immutable pre-oracle snapshots (the automatic one and the explicit one) §2.2.
- V (verdict): the native success flag and the passed, failed and total test counts are equal. Individual test identities are not compared §2.2.
# Primary admission of one case [§2.2]
# Input: archived run, one replay (two fresh processes per control)
# Output: True if the replay is admitted
def admit(archived, replay):
# O: printed outputs match after CRLF and outer-whitespace normalisation
outputs_match = (
normalise(archived.output) == normalise(replay.output)
)
# D_pre: all 12 archived delta files are byte-equal to the replay's,
# checked against both pre-oracle snapshots [§2.2]
deltas_match = all(
same_bytes(archived.deltas[i], replay.deltas[i])
for i in range(12)
)
# V: native success flag and pass/fail/total counts only [§2.2]
verdict_match = (
archived.verdict.success == replay.verdict.success
and archived.verdict.counts == replay.verdict.counts
)
return outputs_match and deltas_match and verdict_matchThree-valued evidence
Each check gives match, difference or unknown. A missing endpoint is not an observed state difference. A conjunction is known false when one checked output differs, even if another component is unknown §2.2. The paper reports counts of matched, different and unknown cases separately and never pools them into a failure probability §2.2 tab. 2.
Database materialization (mechanism study)
The table-level state after an endpoint is compared by row fingerprints. For each table, rows are encoded, sorted and hashed as one representation. The password-reset fields for phone and Spotify users are hashed separately. The hash function is not stated §4.1.
# Materialized fingerprint per table [§4.1]
# Input: database after one endpoint finishes
# Output: one fingerprint per table
def table_fingerprints(database):
fingerprints = {}
for table in database.tables():
# Encode, sort and hash the rows as one representation [§4.1]
encoded = sorted(encode(row) for row in table.rows())
fingerprints[table.name] = digest(encoded) # digest: not stated
return fingerprintsNative verdict and counts come from a separate child process. The parent process records output-row fingerprints, bindings, RNG state and persisted deltas §4.1.
RNG and identical API calls (mechanism study)
The source case e85d92a_2 has 65 recorded interactions, 20 login calls and
1,365 API requests. It satisfies all three checks in both policies §5.1.
The probe is one public-wrapper call to a password-reset function with the same
predeclared literal email and raise_on_failure=False. The concrete argument
hash is identical in both policies. The task time is fixed and no
clock-changing permission is added §5.1 fig. 2.
With RNG preserved, both policies return HTTP 200 and the same printed response.
Their post-call Spotify-user and Gmail entity-row fingerprints differ, and the
reset-field hashes differ too. This holds in both paired repetitions §5.2.
A fixed control aligns only the future Python RNG with random.seed(20261107)
before the same statement. In that control the row difference disappears in both
pairs §5.2.
fig. 2 summarises five arms for this one case: RNG preserved, RNG aligned, natural JWT, shared JWT and distinct JWT. Equality is checked between N and C for four observation types: concrete API arguments, future Python RNG, HTTP statuses and post-call SQLite rows fig. 2.
JWT credential equality (mechanism study)
The credential program comes from a source whose JWT expiry is sampled during login. Repeated generation at a fixed task time can produce equal signed values under the controlled RNG. Logout blacklists the supplied token value, so the database does not encode every credential fact §6.1.
The program is a short public-wrapper sequence, shown symbolically in the paper: a logout with the current token, a read of the account with a shared token, and a playlist creation with the shared token and a fixed title tab. 4 §6.2. Only the current-token binding changes between arms: the natural binding, a forced shared token, or a forced distinct token taken from a recorded N endpoint §6.2. The shared token uses the suffix seed 20261107 §6.2. Read/write HTTP results concern the shared token tab. 4.
Export-source correction (corrective study)
A naive post-oracle export changes the comparison for 10 affected C cases. Those cases span four task families: phone in three cases, Venmo in six and the supervisor app in one. The pinned export helper serializes the database that the class is currently bound to. Binding changes alone are not enough to predict the different bytes, so the paper compares actual source objects and files rather than a binding flag §7.1.
The correction keeps the output trackers that are identified by their output-cache identity before the in-process oracle runs. After the oracle, it calls each tracker's native save operation. The expected deltas are read only afterwards, to validate. The writer neither copies gold bytes nor uses them to select data §7.2.
# Export-source correction for one affected case [§7.2]
# Input: case with output-cache trackers and archived delta files
# Output: exported deltas, read only afterwards for validation
def replay_with_retained_trackers(case):
# Keep the output trackers, identified by output-cache identity,
# before the in-process oracle runs [§7.2]
trackers = retain_output_trackers(case.output_caches)
run_in_process_oracle(case)
# Export through each retained tracker's native save operation [§7.2]
for tracker in trackers:
tracker.native_save()
# Validation only: the gold bytes are never used to pick data [§7.2]
return read_exported_deltas(case)Independent BFCL pilot
The pilot runs bfcl-eval 2025.12.17 at a pinned code and data commit. Its recorded outputs come from a fixed result commit and a Qwen3-8B FC run on the multi-turn base category §8.1. The 12 IDs are frozen as 0, 1, 2, 3, 4, 5, 6, 9, 51, 52, 106 and 152. Their two success controls are 1 and 52 §8.1. Selection is purposeful, not random, and covers seven stateful tool classes §8.1. Each case runs twice in a fresh, network-disabled process with native decoding, execution and checking. It loads the native return bodies without an inference client §8.1.
Hyperparameters
| Name | Value | Where | Notes |
|---|---|---|---|
| Declared seed (N) | 123 | §2.1 | Reconstructed declared setting |
| RNG reset (C) | random.seed(123) before each interaction | §2.1 | C only |
| Cell timeout | 60 s | §2.1 | Both controls; retained in closeout |
| Future-RNG alignment control | random.seed(20261107) | §5.2 | Fixed control, not a primary arm |
| JWT suffix seed | 20261107 | §6.2 | Shared-token programs |
| Repetitions per case and control | 2 fresh processes | §2.1 tab. 1 | Not independent samples §9.3 |
| Primary attempt caps | 120 s external watchdog, 5 s kill grace | §2.3 | Network-disabled containers |
| Container resources | 2 CPUs, 4 GB RAM, read-only inputs | §2.3 | At most 2 concurrent tasks |
| Closeout ordinary cap | 180 s | §2.3 | |
| Closeout resource supplement | one predeclared 600 s limit | §2.3 | Four attempts, all resource-censored tab. 5 |
| Closeout scheduling bound | 4 h overall | §2.3 | Amended from an expired 3 h window |
| Sentinel attempts | 20 | §2.3 | Included in the 284 primary attempts |
| BFCL pilot | 12 IDs, 2 repetitions each | §8.1 | Purposeful selection |
Results
Author-reported. Setup: one historical AppWorld 0.1.0 corpus (71 failures from 32 families, runs of the GPT-4o-2024-05-13 alias); BFCL pilot of 12 cases with the Qwen3-8B FC run §2.1 §8.1.
| Measure | N | C | Source |
|---|---|---|---|
| Admitted, primary rule O AND D_pre AND V (of 71) | 42 (59.2%) | 68 (95.8%) | §3.1 tab. 2 |
| Admitted, family macro average | 58.33% | 92.71% | §3.1 |
| Admitted, D_pre AND V (of 71) | 66 (4 different, 1 unknown) | 70 (0 different, 1 unknown) | tab. 2 |
| Admitted, V only (of 71) | 70 (1 unknown) | 70 (1 unknown) | tab. 2 |
| Exception-normalised O, D_pre, V (of 71) | 42 (29 different) | 70 (1 unknown) | tab. 2 |
| Naive post-oracle export replaces pre-oracle check | 35 | 58 | §7.1 |
| Materialized row differences under the primary rule | 4 cases, 2 task families; phone rows differ in both repetitions | — | tab. 3 §4.2 |
| Affected C export cases matching the reference | Naive: 0 of 10 | Retained trackers: 10 of 10 | fig. 3 §7.2 |
| Known controls admitted after export correction | — | 1 of 2 observed (1 unknown) | fig. 3 §7.2 |
| BFCL pilot, native checks | 12 cases, 24 attempts, 0 measured discrepancies | — | §8.1 tab. 5 |
| Closeout attempts completed | 58 of 66 | 8 censored or unknown | tab. 5 |
fig. 1 shows the gap by rule: 26 cases under O AND D_pre AND V, 4 under D_pre AND V, and 0 under V alone. One endpoint stays unmeasured under the last two comparisons fig. 1.
Table 2 in the paper reads as matched/different/unknown per cell tab. 2. The four database-discrepancy cases are admitted by O AND V but excluded by the primary rule. They are not accepted-primary-contract counterexamples §4.3.
Closeout attempts (tab. 5): literal RNG continuation 8 of 8 complete; actual JWT program 10 of 12; materialized database checks 16 of 16; oracle export correction 22 of 24; 600 s endpoint supplement 0 of 4; known BFCL calibration 2 of 2 tab. 5.
Paper vs code
No official code. The paper links no repository or project page. On the GitHub API, repository searches for "appworld replay", "replay fidelity", "appworld replay fidelity", "appworld oracle replay", "Replay Fidelity LLM agent" and "appworld audit" found no repository owned by the authors. A user search for the two author names returned nothing. Two repositories named replay-fidelity (MitchBaba) are audit tools for conversational datasets by an unrelated owner, so they are not used.
The paper's artifact note says the complete local archive contains protected benchmark-derived material and is not a public redistribution package, and that the authors ran no new tasks p. 11. The external benchmarks it runs, AppWorld 0.1.0 and bfcl-eval 2025.12.17 at a pinned commit, are third-party projects. They are not the authors' code §2.1 §8.1.
Pitfalls
- Unknown is not failure, and vice versa. The admission rule is a conjunction. A missing endpoint is not an observed difference, and reports must keep match, difference and unknown counts apart §2.2 fig. 1.
- Text stops overstate the gap. Treating every N text stop as an endpoint failure overstates the gap. The paper resolves 24 checked endpoints by running the remaining archived code twice §3.2. The primary protocol itself stops at the first output mismatch §2.1.
- Output normalisation is narrow. Only CRLF and outer whitespace are normalised. Anything else must match exactly §2.2.
- Verdicts compare counts, not test identities. V can match while different tests pass or fail. Exact per-test identities are not verified §2.2 §9.3.
- Database equality is row equality. Exact delta bytes can be stricter than semantic equality, while aggregate scores can miss data another operation needs §4.4. Row fingerprints do not certify the serialized heap §9.3.
- Source deltas differ from the correct-solution reference. The reference is the agent's final database change stream, so do not use gold data as the expected state §2.1 §9.3.
- Export timing decides the comparison. A naive post-oracle export lowers admission (N 42 to 35; C 68 to 58). Immutable pre-oracle snapshots avoid this comparison-stage error §7.1 §7.3.
- The tracker fix is narrow. It corrects the export source only. It does not undo global ORM rebinding, serialize variables or prove safe continuation after a later execution §7.3.
- Token equality is value equality. Logout blacklists the token value, not a Python object identity. Two equal-valued tokens can come from controlled RNG; this is not a live authentication-service vulnerability §6.1.
- Prefix token strings differ. Existing request logs already differ in token arguments, and a canonical-request matcher could reject them. The SymTrace represented-state guarantee is not falsified §6.3 §10.2.
- Repetitions are not samples. Two fresh processes give repeatability evidence, not an estimate of stochastic failure probability §9.3.
- Closeout caveats. Eight of 66 closeout attempts are censored or unknown. Four closeout attempts have cap conformance explicitly false, so passing integrity checks does not mean every protocol was followed §8.3 §9.3.
- Undefined unit in §6.1. The paper says "N uses 20" for the JWT case without naming the unit. The surrounding text suggests login calls; check before relying on it §6.1.
- Scope is narrow. One AppWorld version, one source harness and model lineage, 32 failure families, and 12 purposeful BFCL cases. These are not prevalence estimates and say nothing about newer runtimes §1.1 §9.3.
- Original stack not fully identified. The original Python and controller stack is incompletely identified, so C cannot be called a proven reconstruction §9.3.
- Figure 2 boundary. Prefix-based canonical API-argument matching is outside the baseline qualification rule fig. 2.
Lineage
- Builds on: AppWorld (arXiv:2407.18901) [1], the benchmark and archived executions; this study uses the archived code unchanged except for the controls above §2.1.
- Builds on: BFCL (ICML 2025 proceedings) [8], used for the independent pilot §8.1.
- Related work compared against §10.1–§10.3: Who&When (arXiv:2505.00212) [15]; DoVer (arXiv:2512.06749) [13]; ReplayRCA (arXiv:2610.41025) [2]; SymTrace (arXiv:2608.25920) [3]; DFAH (arXiv:2601.15322) [12]; Replay Gap (arXiv:2608.08239) [6].
- Superseded by: not stated.
Source and license
Adapted from “Replay Fidelity in LLM Agent Evaluation: Randomness, Hidden State, and Test Oracles in AppWorld” by You Liu, Quanchao Lu (arXiv:2611.11216), used under CC BY 4.0. Changes: condensed and restructured for implementation, with tables, equations and algorithms taken from the paper and its code, each cited to its source. Not affiliated with or endorsed by the authors.