Source-linked AI summary
Long-Horizon State Tracking in LLMs: Executing MD5 through a Deep Sequence of Dependent Tool Calls
Dheeraj Mohandas Pai, Lu Xian
TL;DR
Long-horizon dependent tasks can fail through compounding bookkeeping errors, but direct evidence about exact state tracking is limited. This paper tests the issue with a ground-truthed, 196-call MD5 procedure and finds that gpt-oss-120b succeeds on a majority of completed runs, including a driver/worker configuration where LLMs perform the arithmetic. Success depends on preserving reasoning in context and voting over worker computations, under serving conditions that are not bit-deterministic.
Problem
Long-horizon benchmarks do not isolate whether LLMs can carry exact intermediate state across many dependent tool calls.
Method
The paper evaluates step-by-step MD5 execution across 196 dependent calls, checking every operation against a from-scratch ground-truth trace and testing LLM workers for the primitives.
Results
A ∼5.5B-active-parameter gpt-oss-120b model carries the full state across all 196 calls and produces the correct digest on a majority of completed runs.
Takeaways & Limitations
Reasoning-in-context and worker self-consistency enable exact long-horizon execution without changing model weights.
Takeaways & Limitations
Temperature 0 is not bit-deterministic on quantized serving, so results are treated as distributions and reported with N.
Abstract
from arXiv · showhide
Long-horizon tasks remain uncommon in large language model (LLM) evaluation, and for a reason: when each step depends on the last, per-step accuracy that looks excellent in isolation decays catastrophically, as errors cascade and the end-to-end failure probability grows sharply with length. Existing agentic benchmarks report end-to-end success but confound this state-tracking difficulty with instruction interpretation, give no control group that isolates it, and are vulnerable to shortcuts such as a hallucinated final answer, so they cannot say why a long run fails. Whether an LLM can carry exact intermediate state across many tool calls at all is itself not well established. We test this cleanly by having the model compute a cryptographic hash, MD5, step by step: a sequence of $196$ dependent tool calls over $64$ rounds while it carries four $32$-bit words $(a,b,c,d)$ in its own context from one call to the next. Interpretation is trivial and, because we implement MD5 from scratch (RFC~1321), we align every call to the ground-truth trace and check the digest to the bit, so any failure is pure bookkeeping. gpt-oss-120b, a mixture-of-experts model with only $\sim$5.5B active parameters per token, at temperature $0$ with a short fixed prompt, carries the full state across all $196$ calls and returns the correct digest on a majority of completed runs. In the strongest setting we replace every primitive tool with a second LLM, so a driver and a worker compute the whole hash from scratch with no exact-arithmetic oracle in the loop. Two ingredients decide success and neither changes the weights: keeping the model's own reasoning in its context each turn, and voting over a thinking-enabled worker to remove its modular-arithmetic slips. We localize the residual failures by origin, separating state-carrying from arithmetic and from serving.
1 Introduction
The paper tests whether an LLM can independently execute a long, exact procedure rather than relying on a hand-built controller. Using step-by-step MD5, it finds that the model can carry state across 196 dependent calls, including when another LLM performs the arithmetic.
- Long-horizon procedures are difficult because dependent per-step errors compound and growing contexts degrade model quality.
- The driver calls primitive operations in sequence while preserving the intermediate state, making each step and the final digest bit-checkable.
- The paper isolates state tracking with a canonical 196-call MD5 procedure that carries four 32-bit words across 64 rounds.
- In the strongest configuration, a worker LLM replaces every primitive, so the driver and worker compute the hash from scratch without an exact-arithmetic oracle.
- A ∼5.5B-active-parameter gpt-oss-120b model carries the full state across all 196 calls and produces the correct digest on a majority of completed runs.
- Success depends on keeping the model’s reasoning in context and using majority voting for worker arithmetic, while residual failures are separated by origin.
2 Background
The background frames MD5 as a demanding, exact test because every one of 196 dependent operations must be correct and its arithmetic is difficult for LLMs. This creates a controlled probe of sustained execution rather than interpretation or guesswork.
- At n ≈196, the independent-step model predicts roughly 14% success for p = 0.99 and ∼4 × 10^-5 for p = 0.95.
- Long-context effects provide a second hazard, with many models falling below half their short-context score by ∼32k tokens.
- A 196-step transcript combines long-horizon dependence with a growing sequence of tool calls and results.
- MD5 maps a message to a 128-bit digest through padded 512-bit blocks, four 32-bit state words, and 64 rounds.
- Each round combines a nonlinear function, message word, per-round constant, modular addition, and left rotation before rotating the state words.
- The harness uses two setup calls, three calls per round across 64 rounds, and two finalization calls, totaling 196 tool calls.
- The procedure is demanding because MD5 offers no exploitable shortcut and requires exact 32-bit arithmetic with carries and rotations.
3 Related Work
Related work identifies compounding errors, context-length degradation, and brittle exact arithmetic as barriers to long-horizon tool use. The paper connects these barriers to reasoning traces, self-consistency, and self-managed memory.
- Long-horizon execution and long context: Prior work finds that high single-step accuracy overstates multi-step capability because errors compound and models condition on earlier outputs.
- Long-horizon execution and long context: Long-context retrieval, reasoning, and tool-calling quality degrade through positional and length-driven effects.
- Long-horizon execution and long context: The 196-step transcript exercises both long-horizon execution and long-context weaknesses.
- Reasoning traces and exact arithmetic: Scratchpads and chain-of-thought externalize intermediate work, while the worker path targets known weaknesses in exact arithmetic.
- Reasoning traces and exact arithmetic: Primitive-level self-consistency is used to make worker arithmetic reliable rather than introducing a new arithmetic method.
- Tool-using agents and self-managed memory: The MD5 harness offers a bit-checkable testbed for whether self-managed memory preserves exact state over long horizons.
4 Experimental Setup
The experiment implements MD5 from scratch and validates the implementation against RFC test vectors, providing exact reference digests and operation traces for evaluation.
- The study uses a from-scratch MD5 implementation validated against RFC 1321 test vectors as ground truth.
- The implementation supplies the exact digest and canonical primitive-operation sequence for every input.
4.1 Models and configuration
The study uses gpt-oss-120b as both a stateful driver and, in swap mode, a stateless worker, with exact verification used for measurement rather than correction.
- gpt-oss-120b is a mixture-of-experts model with approximately 117B total and 5.1–5.5B active parameters per token.
- The driver runs at temperature 0 with a short fixed prompt and context caching, while swap-mode workers use temperature 0.7 with three-sample majority voting.
- The evaluation repeats runs on multiple non-memorized single-block inputs and treats temperature-0 serving as a distribution because quantized inference is not bit-deterministic.
- Ground-truth alignment compares actual and canonical calls, injects first divergences into the algorithm, and separates fresh errors from downstream propagation.
- Worker outputs are checked against a CPU twin for measurement, while reported from-scratch runs do not use that verification as a corrective oracle.
- Success is the exact final digest, complemented by first-divergence round, calls-to-completion, per-operation worker pass rate, and latency as context.
5 Results
The driver can complete the exact 196-call MD5 procedure, while worker voting removes most arithmetic slips; remaining failures primarily arise from state-carrying or serving.
- 5.1 State-carrying driver: The driver completes the canonical 196-call sequence and returns the correct 32-hex digest on multiple distinct inputs.The seven primitives are exact CPU tools, and failures begin when the driver mis-carries a 32-bit word.
- 5.2 Removing the arithmetic oracle: Three-sample worker voting returns a majority primitive value to the driver, while each worker remains stateless and only the driver carries state.Ties trigger an escalation round.
- 5.2 Removing the arithmetic oracle: Worker pass rates are high across all six computed primitives, and majority voting corrects most modular-reduction slips without an exact arithmetic oracle in the loop.The characteristic error is subtracting the wrong multiple of 2^32 from an unreduced sum.
- 5.3 What makes it work: Keeping the driver’s reasoning in the Harmony reasoning channel is the largest lever; byte-identical reasoning in a visible assistant message still fails early.Such failures usually occur within the first 12 to 24 of 196 steps.
- 5.4 Failure analysis: Seven long runs skip rounds 40 through 47 and jump from round 39 to round 48, a position-locked pattern absent from successful runs.The skip occurs in the back half of the third, H, quarter.
- 5.4 Failure analysis: The same weights can differ sharply by serving route, with a gateway path taking approximately 2.5 seconds per step versus approximately 13 seconds directly.The paper controls the endpoint per experimental cell and reports speed only as context.
- 5.4 Failure analysis: Failure sources partition into driver state errors, worker arithmetic errors, and serving collapses, with driver errors dominating and worker errors usually corrected by voting.The 40 →48 skip recurs only in failing runs and is described as a candidate model signature.
6 Discussion
The paper argues that LLMs can drive long, stateful workflows when context is managed explicitly, and proposes self-managing context as the next step toward autonomous agents.
- State preservation is relevant to accounting, compliance, provisioning, and reconciliation workflows where one copied value can silently corrupt the outcome.The paper contrasts this with the prevailing use of hand-built controllers that restrict LLMs to leaf tasks.
- The driver/worker split assigns long-horizon state and sequencing to one agent while another performs bounded, verifiable computation.Both roles use the same model, making the decomposition scaffolding toward a single self-managing agent.
- Self-editing context: A proposed self-editing context tool would let the model write and read durable scratch values, summarize or compress its transcript, and discard unneeded material.The paper connects this design to memory architectures such as MemGPT, which expose paging between in-context and external memory as tool calls.
- Self-editing context: The MD5 task offers a bit-checkable test of whether self-management preserves the four working words and round index after each context edit.The paper suggests this could improve robustness to long transcripts and extend to procedures with larger, messier state.
7 Conclusion
The paper uses step-by-step MD5 execution as a bit-checkable probe of long-horizon reliability. It finds that, with suitable context management and arithmetic voting, an LLM can complete the procedure end to end and motivates agents that eventually manage their own context.
- 196 dependent tool calls provide a clean test of whether an LLM can carry exact state through a deterministic algorithm.The task uses a mixture-of-experts model with ∼5.5B active parameters and can replace every primitive with a self-consistent worker.
- Two context-level levers support success: retain the model’s reasoning in context and improve arithmetic reliability through voting.Neither lever changes the model weights.
- Residual failures are few and mechanical, including a reproducible 40 →48 skip signature.
- The broader conclusion is that models need not always be removed from long exact workflows when they receive the context required to drive them.The paper presents this as a foundation for agents that eventually manage their own context.