Long-Horizon State Tracking in LLMs: Executing MD5 through a Deep Sequence of Dependent Tool Calls

1. 1.

   A controlled, ground-truthed benchmark in which an LLM executes MD5 step by step through tools, turning long-horizon exactness into a measurable, bit-checkable task with a canonical $196$-call reference trace.

2. 2.

   A positive result: a $\sim$5.5B-active-parameter LLM executes the full $196$-step procedure end-to-end and returns the correct digest, and, with a worker LLM replacing every primitive, the driver/worker pair computes the hash from scratch, arithmetic included.

3. 3.

   A driver/worker method with self-consistent workers that separates state tracking (driver) from primitive arithmetic (worker), and shows the arithmetic is made reliable by majority voting while the state is carried by the driver.

4. 4.

   An identification of the two context conditions that make it work, reasoning-in-context and self-consistency, and a characterization of the residual failures by origin (driver state, worker arithmetic, serving).

A high per-step accuracy $p$ yields an end-to-end success rate of roughly $p^{n}$ over $n$ dependent steps; at $n\approx 196$ even $p=0.99$ predicts a $\sim$14% success rate, and $p=0.95$ predicts $\sim$$4\times 10^{-5}$. Sinha et al. (2025) formalize this: strong single-step accuracy systematically overstates long-horizon capability, models degrade as they condition on their own prior outputs, and larger models and chain-of-thought (Wei et al. 2022) push the horizon out but do not remove the wall.

Independently, retrieval and reasoning quality drop as context length grows, the “lost in the middle” positional effect (Liu et al. 2024) and length-driven degradation (Modarressi et al. 2025), with many models falling below half their short-context score by $\sim$32k tokens, and function-calling accuracy degrading in long contexts specifically (Adhikary, Contractor et al. 2025).

A $196$-step exact procedure sits squarely in the intersection of both hazards: long horizon and a growing transcript of tool calls and results. That is exactly why success here is informative, and why the conditions that produce it (reasoning-in-context, self-consistency, a driver/worker split) are the point.

MD5 (Rivest 1992) maps a message to a $128$-bit digest. The message is padded and split into $512$-bit blocks; each block is read as sixteen $32$-bit words $M[0..15]$. A running state of four $32$-bit words $(a,b,c,d)$ is initialized to fixed constants. Each block is processed by $64$ rounds. Round $i$ computes a nonlinear function of three of the state words, $f=F(b,c,d)$ where $F$ is bitwise selection $(b\wedge c)\vee(\neg b\wedge d)$ for $i<16$ and the analogous $G,H,I$ for the later quarters, together with a message index $g$. It then forms

where $K[i]$ is a per-round sine constant, $s[i]$ a per-round rotation amount, $+$ is addition modulo $2^{32}$, and $\mathbin{{<}\mkern-6.0mu{<}\mkern-6.0mu{<}}$ is a left rotation; finally the four words are rotated $(a,b,c,d)\leftarrow(d,b^{\prime},b,c)$. After $64$ rounds the block’s result is added, again modulo $2^{32}$, into the running state, and the final $(a,b,c,d)$ is emitted little-endian as the digest. In our harness one block is a canonical $196$ tool calls: two to set up, three per round (constants, function, mix) across $64$ rounds, and two to finalize.

Two properties make this a demanding test. First, it is a long, strictly dependent computation: the $196$ steps must each be exactly right, and by design MD5 has no exploitable structure (its add-rotate-xor construction targets the avalanche effect, so the digest cannot be guessed or interpolated, only computed step by step). This makes it a clean probe of sustained exact execution. Second, the per-step arithmetic, $32$-bit modular addition with carries and bit rotations, is exactly the kind of large-number exact computation on which LLMs are known to be brittle (Lee et al. 2024), so the worker path stresses a second, independent weakness.

Our result pushes against two strands of pessimism. Sinha et al. (2025) show that high single-step accuracy overstates multi-step capability because errors compound and models self-condition on their own outputs, the analytical $p^{n}$ wall. Separately, quality decays with context length: the “lost in the middle” positional effect (Liu et al. 2024), length-driven degradation past roughly $32$k tokens (Modarressi et al. 2025), and tool-calling specifically degrading in long contexts (Adhikary, Contractor et al. 2025). A $196$-step transcript exercises both.

That intermediate work must be externalized to enable multi-step computation is the scratchpad finding (Nye et al. 2022) and, at prompting time, chain-of-thought (Wei et al. 2022); our reasoning-channel result is its serving-time analogue. The worker path stresses a second known weakness, exact arithmetic on large numbers, where LLM competence is surface-form and magnitude dependent (Lee et al. 2024); we make it reliable with primitive-level self-consistency (Wang et al. 2023) rather than a new method.

Tool-augmented agents such as ReAct (Yao et al. 2023) and Toolformer (Schick et al. 2023) raise capability but leave workflow state implicit in context, which is exactly what we stress. Our forward direction, a model that edits its own context, connects to self-editing memory architectures like MemGPT (Packer et al. 2023); our MD5 harness offers a bit-checkable testbed for whether such self-management preserves exact state across a long horizon.

We implement MD5 from scratch (RFC 1321; no hashlib), validated against the RFC test vectors. This is ground truth: for any input we can produce the exact digest and the exact canonical sequence of primitive operations.

Seven primitives are exposed as tools: prepare_message (pad and split into sixteen $32$-bit words), initial_state, get_step_constants($i$), compute_f_and_g($i,b,c,d$) (round function $F/G/H/I$ plus the message index), mix_step, add_states, and to_hex_digest. Each is a thin exact wrapper over the reference (CPU mode) or an LLM twin (worker mode). Figure 1 shows a single driver run with deterministic tools, and Figure 2 shows how a tool call is computed by voting workers.

A single-block input ($\leq 55$ bytes, one $512$-bit block, $64$ rounds). The driver agent reads a short, fixed instruction library and must call the tools in order while carrying $(a,b,c,d)$ between calls and applying the state-update rotation itself. A correct hash is a canonical $196$ tool calls ($2$ setup $+\,64\times 3\,+2$ finalize); the driver’s final answer is a $32$-hex digest compared for exact equality with $\mathrm{md5}(\mathrm{input})$.

MD5 is a clean difficulty dial: interpretation is trivial and every primitive is provably correct, so what remains to be tested is purely (i) whether the model can relay exact state between tools without dropping any, and (ii) whether it can take many mechanical turns consistently. We fix a single block deliberately, it keeps the instruction library linear, and note that scaling the horizon is as easy as adding blocks (each block is another $64$ rounds of the same loop), so the benchmark extends to arbitrarily long horizons without adding interpretive difficulty. We never use famous vectors (e.g. "abc") whose digests may be memorized; inputs are varied non-memorized single-block strings, including random ones, so a correct digest cannot be recalled and must be computed.

Long-horizon exactness is not a toy concern. Accounting and bookkeeping close-out, legal and compliance workflows, provisioning and reconciliation pipelines, all require an intermediate state to be preserved verbatim across many steps, where a single dropped or mis-copied value silently corrupts the outcome. The prevailing assumption is that such workflows must be driven by a hand-built controller with the LLM confined to leaf tasks. Our result says the LLM can hold the state itself when its context is managed for it, reasoning kept in context, arithmetic made reliable by voting, which widens where a model may be trusted to drive, not just assist.

The driver/worker split is deliberately a two-agent decomposition: one agent owns the long-horizon state and sequencing, the other owns bounded, verifiable computation. We use the same model for both roles on purpose. The split is scaffolding, not the destination: because driver and worker are one model, the natural next step is to collapse them into a single agent that carries its own state, computes its own primitives, and, critically, curates its own context.

The most direct version of that next step is to give the model a tool that edits its own context: operations to write a value into a durable scratch region, read it back, summarize or compress the transcript so far, and drop material it no longer needs. In our task the state to be managed is tiny and exact, the four working words and the round index, so a self-editing policy has an unusually clean success criterion: we can check to the bit whether the model preserved the right state after every edit, rather than judging memory quality qualitatively. This connects to self-editing memory architectures such as MemGPT (Packer et al. 2023), which expose paging between in-context and external memory as tool calls; our contribution would be a ground-truthed testbed for whether such self-management actually keeps exact state across a long horizon. Would this be useful? We expect so: a model that can offload $(a,b,c,d)$ to a scratch tool and reload it on demand should be far more robust to the length-driven degradation of long transcripts, and the same mechanism generalizes to the branching, real-world procedures (accounting close-outs, compliance workflows) where the state that must survive is larger and messier than four words. Whether a single model can own its state and its computation and its context is the question this setup is designed to open.