1 Introduction↩︎

Effective reasoning requires not only the ability to draw inferences but also the ability to manage what is known, what is uncertain, and what remains to be determined [1]–[3]. Language model agents that interleave reasoning with tool use [4], [5] have made striking progress on multi-hop question answering [6]–[8], yet they exhibit a characteristic failure as reasoning chains grow: agents that reliably answer 2-hop questions degrade sharply on 3- and 4-hop problems, even when the constituent sub-questions are individually straightforward. Why does composing more reasoning steps cause such disproportionate difficulty?

We argue that the root cause is context dilution—the progressive burial of decision-relevant information under accumulating tool outputs. While retrieval-augmented generation [9], [10] has made single-hop retrieval effective, multi-hop problems compound the challenge: a ReAct agent [4] must attend over dozens of retrieved paragraphs while simultaneously tracking which sub-questions are resolved, which hypotheses remain viable, and what to investigate next. This investigative state is never made explicit; it exists only implicitly in the growing context window, where early discoveries compete for attention with later retrievals. The longer the chain, the more severe the dilution.

Human investigators—detectives, diagnosticians, scientists—solve precisely this problem by maintaining structured working notes that separate what is known from what is hypothesized from what remains to be determined. This tripartite organization serves a dual purpose: it compresses the investigation state into a decision-relevant summary, and it directly determines the next action (investigate the highest-priority open question). We operationalize this insight for language agents.

We introduce SLEUTH (Structured Layered Evidence-Updated Tracking of Hypotheses), a working memory framework, implemented entirely through prompting, in which the agent maintains three typed components after every action: Confirmed Facts grounded to specific sources, Active Hypotheses ranked by evidentiary support, and Open Questions that drive action selection. By outputting and updating this structure on every turn, the agent carries an explicit epistemic state across the trajectory rather than leaving it implicit in the context window. This sets SLEUTH apart from memory systems that accumulate experience across episodes [11]–[13] and from methods that scale test-time compute by searching more trajectories [14]–[16]: SLEUTH instead organizes information within a single trajectory, requiring no extra episodes, search, or training. Our key contributions are:

• We introduce SLEUTH, which makes an agent’s epistemic state explicit and actionable: confirmed facts, ranked hypotheses, and open questions that directly drive the next action. Unlike approaches that externalize state through code execution, symbolic controllers, or training, SLEUTH requires only prompting.

• We show that this structured state yields gains that scale with reasoning difficulty—widening from +4.7 points on HotpotQA to +10.9 on 4-hop chains over five established baselines across five benchmarks—and surpasses Reflexion without multiple episodes.

• We identify the evidence sufficiency problem: agents gather enough evidence but fail to commit under bounded computation. Our commitment mechanism resolves it, but only when coupled with structured state—the identical trigger that lifts SLEUTH by double digits leaves an unstructured agent unchanged, isolating organized epistemic state as the necessary condition.

• We establish that protocol adherence, not model capability, is the active ingredient: enforcing consistent working-memory maintenance on a weaker model (GLM-5) recovers up to +19 points on the hardest problems.

2 Related Work↩︎

ReAct [4] established the interleaved thought-action paradigm, but leaves the agent’s epistemic state implicit in the growing context. Chain-of-Thought [17] and its variants [18]–[20] improve single-turn reasoning but do not track beliefs across turns. Self-Ask [21] decomposes questions sequentially without persistent state; IRCoT [22] interleaves retrieval with chain-of-thought but represents neither what is established nor what remains open. Recent work trains iterative retrieval-reasoning policies [23]–[25] or adds multi-agent backtracking [26], improving retrieval integration without an explicit epistemic state. Reflexion [11] adds post-episode self-reflection but requires multiple episodes; Tree of Thoughts [14] and LATS [15] scale test-time compute through trajectory search. SLEUTH is complementary, improving reasoning quality within a single trajectory.

CoALA [27] provides cognitive-architecture scaffolding with modular memory types; MemGPT [28] manages context through OS-inspired paging. CLIN [12], ExpeL [13], and A-Mem [29] learn or evolve cross-episode knowledge, whereas SLEUTH maintains prospective within-episode state. HiAgent [30] compresses subgoal-level information; [31] add neurosymbolic working memory for deductive reasoning; CAT [32] exposes context maintenance as a callable tool. Programmatic and graph-structured controllers [33] externalize state with stronger guarantees but require code execution, training, or auxiliary infrastructure. SLEUTH achieves substantial gains at the lightest design point—prompting alone—distinguished by its tripartite epistemic structure and the direct coupling between open questions and action selection.

Adaptively allocating inference-time computation can match or exceed scaling model parameters [16], [34], [35], but these approaches operate on single-turn reasoning; the analogous multi-turn challenge is allocating a fixed action budget across evidence gathering and commitment. RL-based methods [25], [36] train models to decide when to search but not how to organize gathered evidence. Our nudge addresses the complementary exploration-exploitation tradeoff at the trajectory level, triggering commitment after a principled fraction (70%) of the turn budget. Crucially, SLEUTH requires no reinforcement learning or fine-tuning—it is implemented entirely through prompting and a lightweight runtime check, making it immediately applicable to any instruction-following model.

3 SLEUTH: Structured Epistemic Working Memory↩︎

SLEUTH augments a language agent with an explicit epistemic working memory—a structured scratchpad [37] that the agent reads and updates on every turn, organized as a tripartite epistemic structure that separates established knowledge from hypotheses and open uncertainties. The framework requires no fine-tuning or architectural modification; it is implemented entirely through prompting. We describe the working memory structure (§3.1), the update protocol (§3.2), and the commitment mechanism that addresses the evidence sufficiency problem (§3.3). Figure 1 illustrates the framework on a multi-hop question.

3.1 Working Memory Structure↩︎

At each turn \(t\), the agent maintains a working memory state \(W_t\) comprising three typed components:

\(\mathcal{F}_t = \{f_1, \ldots, f_n\}\) are verified statements extracted from tool outputs, each grounded to a specific source. Entry format: [F\(i\)]\(\langle\)statement\(\rangle\)(source:\(\langle\)title\(\rangle\)). Facts are monotonically accumulated—once confirmed, they are never retracted within an episode. This monotonicity ensures that evidence is preserved rather than lost to context dilution.

\(\mathcal{H}_t = \{h_1, \ldots, h_m\}\) are candidate answers ranked by evidentiary support. Each hypothesis is linked to the confirmed facts that support or contradict it, with an explicit confidence level (high/medium/low). Entry format: [H\(j\)]\(\langle\)hypothesis\(\rangle\)| confidence:\(\langle\)level\(\rangle\)| supports:\(\langle\)fact IDs\(\rangle\)| contradicts:\(\langle\)fact IDs\(\rangle\). Rankings change as new evidence arrives: hypotheses gain confidence when supporting facts accumulate and lose confidence when contradicted.

\(\mathcal{Q}_t = \{q_1, \ldots, q_l\}\) are uncertainties whose resolution would most change the hypothesis rankings, each with a proposed action. Entry format: [Q\(k\)]\(\langle\)question\(\rangle\)| action:\(\langle\)proposed query\(\rangle\)| priority:\(\langle\)level\(\rangle\). The highest-priority open question directly determines the agent’s next tool call, creating a tight coupling between epistemic state and action selection. When \(\mathcal{Q}_t = \emptyset\) and some \(h_j\) has high confidence, the agent commits to an answer.

The complete state \(W_t = (\mathcal{F}_t, \mathcal{H}_t, \mathcal{Q}_t)\) is output in full on every turn, creating an explicit chain of epistemic states that constitutes the agent’s reasoning trace.

3.2 Update Protocol↩︎

After every tool call, the agent performs a structured update \(W_{t-1} \rightarrow W_t\):

1. Extract facts. Parse the tool output for new verifiable information. Add each as a confirmed fact with a source pointer: \(\mathcal{F}_t \supseteq \mathcal{F}_{t-1}\).

2. Update hypotheses. For each \(h_j \in \mathcal{H}_{t-1}\), determine whether new facts support, contradict, or are irrelevant to it. Adjust confidence accordingly. Generate new hypotheses if evidence suggests explanations not yet considered.

3. Update questions. Remove questions answered by the new observation. Generate new questions targeting remaining uncertainty—specifically, questions whose answers would most change hypothesis rankings.

4. Select action. Execute the highest-priority question’s proposed action. If \(\mathcal{Q}_t = \emptyset\) and some hypothesis has high confidence, call finish(answer).

This protocol enforces two key properties. First, evidence monotonicity: confirmed facts never disappear, preventing the context dilution that degrades standard agents. Second, action grounding: every tool call is justified by an explicit open question, eliminating redundant or unfocused searches. Empirically, facts accumulate from \({\sim}2\) to \({\sim}4\) while open questions decrease from \({\sim}1.5\) to \({\sim}1.1\) across a typical 4-hop trajectory (Appendix 12). The working memory is enforced at runtime: the agent’s response must contain all three sections in prescribed notation before a tool call is executed.

3.3 Commitment Mechanism↩︎

A structured working memory improves evidence organization but introduces a new failure mode: over-verification. The hypothesis-confidence framework, while useful for ranking alternatives, provides no clear stopping criterion. We observe empirically that agents maintaining high standards for “sufficient evidence” continue gathering confirmatory evidence even after the answer is determinable, exhausting their turn budget on questions that have already been effectively resolved.

We address this with a nudge mechanism—a commitment trigger that fires when two conditions are jointly satisfied: (1) the agent has consumed at least fraction \(\alpha\) of its turn budget \(T\) (i.e., turn \(t \geq \alpha T\)), and (2) the agent has accumulated at least \(\tau\) confirmed facts (\(|\mathcal{F}_t| \geq \tau\)), ensuring there is enough evidence to synthesize from. We set \(\tau{=}2\), which we find works well empirically: it is the minimum needed to compose a multi-hop answer while still gating out premature commitment when the agent has barely begun gathering evidence. The trigger is deliberately independent of the agent’s open-question state: in multi-hop problems, resolving one sub-question surfaces the next link in the chain, so \(\mathcal{Q}_t\) is legitimately non-empty until the reasoning chain completes—conditioning on \(\mathcal{Q}_t = \emptyset\) costs \({\sim}\)​4 EM points as the nudge effectively never fires. When triggered, the agent receives a synthesis message instructing it to construct an answer from its confirmed facts and active hypotheses without further search. This transforms the open-ended investigation into a commitment decision, forcing the agent to exploit its accumulated evidence rather than continuing to explore. The threshold \(\alpha\) controls an exploration-exploitation tradeoff: too small (e.g., \(\alpha{=}0.3\)) cuts off investigation before sufficient evidence is gathered; too large (e.g., \(\alpha{=}0.8\)) leaves insufficient margin for synthesis. We find \(\alpha{=}0.7\) optimal empirically (§[sec:nudge-ablation]).

3.4 Implementation↩︎

SLEUTH is implemented as a system prompt that instructs the agent to maintain the working memory structure described above. The agent is given three tools: search(query), which returns the top-\(k\) most relevant paragraphs from the question’s context; lookup(title), which returns the full text of a specific paragraph; and finish(answer), which terminates the episode with a final answer. The same tool interface is used across all baselines; only the system prompt differs.

For models with weaker instruction-following, working memory adherence can be enforced through two mechanisms: (1) prompt adaptation with explicit structural delimiters that make the format unambiguous, and (2) a runtime check that rejects responses missing proper notation and re-prompts the agent. Together, these raise adherence from \({\sim}\)​15% to \({\sim}\)​99% of turns on GLM-5, recovering over 19 points on the hardest problems (§5.5). Sonnet requires neither mechanism—it maintains the protocol through instruction-following alone.

4 Experimental Setup↩︎

We evaluate SLEUTH against five established baselines, together with a set of working-memory ablations, on five multi-hop reasoning benchmarks spanning 2- to 4-hop reasoning chains, using two model families.

We evaluate on three multi-hop QA benchmarks: HotpotQA [6] (\(N{=}7{,}405\), 2-hop, distractor setting with 10 paragraphs per question), MuSiQue [7] (2/3/4-hop answerable splits with \(N{=}1{,}252/760/405\) and 20 paragraphs, enabling controlled difficulty analysis), and 2WikiMultiHopQA [8] (\(N{=}12{,}576\), comparison and bridge reasoning). All use the validation split with full paragraph context provided to the retrieval toolkit. Full dataset statistics are in Appendix 8.

We compare against five established agent reasoning paradigms: ReAct [4] interleaves reasoning and acting with no persistent state; ReAct-CoT augments ReAct with explicit chain-of-thought before each action; Self-Ask [21] decomposes questions into sub-questions answered sequentially; IRCoT [22] interleaves retrieval with chain-of-thought; and Reflexion [11] adds post-episode self-reflection over 2 episodes.

To isolate the contribution of each working-memory component, we additionally evaluate variants of SLEUTH itself. Notes augments ReAct with an unstructured scratchpad, testing whether any persistent state helps. Facts-Only maintains structured fact extraction without hypotheses or questions; Facts+Hyp. adds ranked hypotheses; and Facts+Q. instead adds open questions (omitting hypotheses). SLEUTH completes the tripartite structure with both. These two-component variants test whether either added component alone suffices (schema sensitivity, §16). All methods share the same tool interface; only the system prompt differs.

Primary experiments use Claude Sonnet 4.6; cross-model experiments use GLM-5. All agents operate with a 20-turn budget and search top-\(k{=}3\) paragraphs. We report Exact Match (EM) after standard normalization (lowercasing, article removal, whitespace). For analysis, we decompose EM into conditional accuracy (EM among questions answered within the turn budget) and timeout rate (fraction exhausting all turns without calling finish). F1 scores are reported in Appendix 9.

5 Results↩︎

5.1 Main Results↩︎

Table 1 presents exact match scores across all five benchmarks. SLEUTH achieves the highest score on every dataset, with improvements over external baselines that scale with difficulty. On HotpotQA (2-hop), SLEUTH achieves 66.1% EM, surpassing Reflexion (61.4%) by 4.7 points without requiring multiple episodes. The advantage grows on MuSiQue: +11.9 points on 2-hop, +10.4 on 3-hop, and +10.9 on 4-hop over the strongest external baseline. On 2WikiMultiHopQA, SLEUTH achieves 76.4%, a 2.8-point improvement over Reflexion.

The middle block isolates each working-memory component, all sharing SLEUTH’s commitment and verbatim-extraction rules. Maintaining sourced facts alone (Facts-Only) already recovers most of the advantage—49.9% on 4-hop, +7.9 over ReAct—confirming that preventing context dilution is the dominant effect. Adding hypotheses or open questions in isolation does not help further (Facts+Hyp.%, Facts+Q.% on 4-hop); only the full tripartite structure adds a further +3.2 points, because open questions become actionable only once ranked hypotheses give them candidates to discriminate (§16). Notes—an unstructured scratchpad—provides inconsistent benefit, confirming that structured state, not merely persistent state, is the active ingredient.

5.2 Scaling with Reasoning Difficulty↩︎

The MuSiQue splits enable controlled comparison across reasoning depth. Figure 2 (a) plots EM against hop count for both model families. All agents degrade as chains lengthen, but SLEUTH degrades more gracefully: its margin over ReAct holds near +11 points across 2-, 3-, and 4-hop on Sonnet, and widens to +11.1 on 4-hop with GLM-5. The advantage is largest precisely where implicit state tracking breaks down—on the longest chains, where unstructured agents lose track of intermediate findings and exhaust their budget (timeout dynamics analyzed in §5.3). Structured working memory becomes more valuable as the reasoning it must support grows harder. All SLEUTH–ReAct gaps are significant at \(p<0.001\) by a paired bootstrap, and the scaling trend is robust: even the lower bound of the 4-hop confidence interval exceeds the HotpotQA point estimate (Appendix 14).

5.3 The Evidence Sufficiency Problem and Commitment Mechanism↩︎

Why does SLEUTH still fall short on 4-hop questions? We decompose EM into conditional accuracy (accuracy given an answer is produced) and timeout rate (fraction exhausting the 20-turn budget without committing). The decomposition is revealing: SLEUTH without the commitment mechanism reasons far better than ReAct (conditional accuracy 64.6% vs.%) yet squanders this on a 24.7% timeout rate, and 92% of those timed-out episodes contain the gold answer in their history. The agent finds the answer but fails to commit. We term this the evidence sufficiency problem: the hypothesis-confidence framework that improves reasoning provides no principled stopping criterion, so the agent’s evidence standard recedes continually and it over-verifies even when the answer is effectively determined.

We characterize the resulting exploration–exploitation tradeoff by sweeping the commitment trigger across the turn budget (Table 2). EM peaks and plateaus in the 50–70% range, indicating robustness to exact timing. The two extremes show the tension directly: early nudges (Nudge@6) force premature commitment and depress conditional accuracy, while no nudge attains the highest conditional accuracy (64.6%) but bleeds it away to timeouts. Nudge@14 (\(\alpha{=}0.7\)) is the sweet spot—it converts SLEUTH’s superior reasoning into superior task performance, lifting EM from 49.1% to 53.1%. Accuracy-at-turn curves (Appendix 11.3) confirm the mechanism: SLEUTH and ReAct track closely through turns 12–14, diverging sharply only once the nudge fires.

A natural objection is that SLEUTH’s gains come from the nudge alone, not the structured state. We test this by applying the identical commitment trigger to ReAct (same message at turn 14, no working memory). ReAct+nudge achieves 42.2% (\(+\)​0.2 vs.vanilla ReAct)—effectively unchanged—while SLEUTH+nudge achieves 53.1% (\(+\)​4.0 over no-nudge SLEUTH). The nudge alone provides no benefit without organized evidence to synthesize from; SLEUTH’s structured facts and ranked hypotheses provide the substrate that makes commitment effective. The working memory is the necessary condition—the nudge merely exploits it (full analysis in Appendix 11.4).

5.4 Cross-Model Generalization↩︎

To test whether SLEUTH’s advantage reflects the structured protocol rather than model-specific behavior, we replicate key experiments with GLM-5, a model from a different family (Table 3). SLEUTH uses runtime enforcement to ensure protocol adherence on GLM-5 (analyzed in §5.5).

SLEUTH with GLM-5 follows the same pattern as with Sonnet: gains grow with difficulty, from +1.0 on HotpotQA to +11.1 on 4-hop. The non-linear jump tracks timeout dynamics—without structured memory, GLM-5’s timeout rate climbs from 17% (2-hop) to 35% (4-hop), while SLEUTH holds it below 12% throughout. The modest HotpotQA gain is itself informative: GLM-5’s ReAct agent averages 4.3 searches per question (vs. for Sonnet), brute-forcing easy problems through thoroughness where structure is not yet needed. Notably, Reflexion underperforms ReAct on every multi-hop split, indicating that post-episode reflection without structured within-episode state is insufficient as chains lengthen.

5.5 Protocol Adherence↩︎

The component ablation (§5.2) shows that the content of the working memory matters; here we ask whether consistent maintenance is necessary. We compare GLM-5 under two configurations: (1) the general SLEUTH prompt (identical to Sonnet’s) with no additional enforcement, and (2) a model-adapted prompt with explicit structural delimiters and a runtime check that rejects malformed responses. Together, these ensure near-complete protocol adherence (\({\sim}\)​99% of turns).

Given the same prompt as Sonnet, GLM-5 maintains the protocol on only \({\sim}\)​15% of turns, drifting into unstructured reasoning for the rest; prompt adaptation and the runtime check raise this to \({\sim}\)​99%. The payoff scales steeply with difficulty—+8.9 on 2-hop, +11.7 on 3-hop, +19.0 on 4-hop. This provides the clearest evidence that how an agent organizes its reasoning, not raw model capability, is the active ingredient: a fixed model gains up to 19 points on the hardest problems purely from being held to the structure it was already told to maintain. The working memory must be live and continuously updated—merely seeing the prompt is not enough.

We decompose SLEUTH’s remaining errors on 4-hop MuSiQue into three categories: reasoning errors (32.1%)—incorrect inferences from relevant evidence; timeouts (11.1%)—budget exhaustion without committing; and verbose answers (4.4%)—the gold answer is present but includes extraneous context. The primary bottleneck is inference quality over correctly-retrieved evidence, not retrieval or state management. In head-to-head comparison, SLEUTH wins 59 questions that ReAct misses while losing only 14, a net advantage of 45 (full decomposition in Appendix 17).

Our default uses top-\(k{=}3\) paragraphs per search. To test whether SLEUTH’s advantage depends on this setting, we vary \(k \in \{1, 3, 5\}\) on 4-hop MuSiQue. The advantage holds across all three: +10.1 points at top-\(k{=}1\), +11.1 at the default \(k{=}3\), and +10.9 at top-\(k{=}5\) (Appendix 13). The mechanism cuts both ways: under sparse retrieval, fact-tracking preserves a relevant paragraph that might otherwise be buried under later turns, while under noisy retrieval, separating confirmed facts from unverified content helps the agent ignore irrelevant paragraphs.

Our results trace SLEUTH’s advantage to addressing two distinct failure modes of implicit state management, each dominant at a different difficulty. Information loss—confirmed evidence getting buried under accumulating context—is addressed by structured fact-tracking and accounts for most of the gain on 2- and 3-hop problems, where agents find the evidence but lose it. Information paralysis—knowing the answer but failing to commit under bounded computation—is addressed by the commitment mechanism and accounts for most of the gain on 4-hop, where timeouts dominate (cf.the 24.7% no-nudge timeout rate, §5.3). Standard agents suffer both; SLEUTH’s structure is what makes each remedy possible—the same organized state that prevents loss is also the substrate the commitment trigger exploits (Appendix 11.4).

6 Discussion↩︎

SLEUTH achieves substantial improvements through structured state management alone—no additional training, parameters, or trajectory search. This suggests that as agents tackle increasingly complex tasks, the bottleneck shifts from reasoning capability to reasoning organization [33]. The cross-model results make this strikingly concrete: on 4-hop problems, GLM-5 with enforced structure (48.9%) outperforms the stronger Sonnet running unstructured ReAct (42.0%)—organization on a weaker model beats raw capability without it. Because the working memory is output in natural language on every turn, SLEUTH’s reasoning is also inherently more interpretable than that of black-box agents: each step’s epistemic state is externalized, enabling human oversight and debugging. As instruction-following improves, we expect structured protocols to become effective without runtime enforcement, extending the benefit to any agentic workflow where state accumulates.

Our nudge ablation identifies a general tension for agents with rich internal state: the richer the uncertainty model, the harder it becomes to commit under bounded computation. This “certainty trap” is not unique to SLEUTH—it arises in any agent framework that makes evidence quality explicit, from autonomous research agents [38] to diagnostic systems. We address it here via a simple time-based nudge; principled alternatives may draw on optimal stopping theory, conformal or coverage-calibrated stopping rules that offer formal guarantees, learned value functions over epistemic states [39], or RL-trained stop/continue policies [25]. A natural common substrate is SLEUTH’s structured state features—fact count, hypothesis confidence, question resolution rate—over which any of these criteria could be calibrated, connecting language agent design to classical decision theory.

SLEUTH’s working memory adds token overhead, though it is smaller on the harder problems where the framework helps most (1.33\(\times\) the API cost of ReAct on 4-hop vs.\(\times\) on HotpotQA; Appendix 10) and benefits most from budgets allowing at least \({\sim}2.5\times\) the reasoning depth, while remaining advantageous even at tighter budgets (Appendix 13). The commitment threshold (70% of budget) was tuned on our benchmarks and may need re-tuning for very different task structures, and the monotonic fact policy can entrench early reasoning errors when a confirmed fact is contextually misleading (Appendix 20). Finally, our closed-context setting does not capture contradictory or time-sensitive open-domain sources.

7 Conclusion↩︎

We introduce SLEUTH, a structured working memory framework that decomposes an agent’s epistemic state into confirmed facts, ranked hypotheses, and prioritized open questions. SLEUTH’s advantage scales with reasoning difficulty, and our analysis isolates two failure modes of implicit state management—information loss and evidence-sufficiency paralysis—each addressed by a distinct component: structured fact-tracking prevents the first, while a commitment mechanism resolves the second, but only when it has organized state to exploit. The central lesson is that how an agent organizes its reasoning can matter more than how well it reasons: a weaker model held to the structure outperforms a stronger one without it. Because these gains require no training, search, or auxiliary infrastructure—only prompting—epistemic state management emerges as a design dimension for language agents complementary to scaling model size or test-time compute.

Reproducibility Statement↩︎

SLEUTH is implemented entirely through prompting—no fine-tuning, custom architectures, or additional training is required. Complete system prompts for SLEUTH and all baselines and ablations appear in Appendix 18, and the retrieval implementation (lexical/sparse scoring over the per-question paragraph collection) is detailed in Appendix 20. All experiments use publicly available datasets (HotpotQA, MuSiQue, 2WikiMultiHopQA) from the HuggingFace Hub, with statistics and splits in Appendix 8. Unless otherwise noted, all runs use a 20-turn budget, top-\(k{=}3\) retrieval, the EM normalization described in §4, and greedy decoding (temperature 0); GLM-5 additionally uses the runtime enforcement specified in §5.5 and Appendix 20. We fix random seeds for dataset loading and report the model versions used (Claude Sonnet 4.6, GLM-5). As with any hosted model, exact outputs may shift across provider-side model updates; we therefore document all prompts, configurations, and decoding settings needed to reproduce our protocol independent of a specific endpoint.

8 Dataset Statistics↩︎

Table 5 summarizes the benchmarks used in our evaluation. All datasets use the distractor setting, where gold supporting paragraphs are mixed with distractors to create a realistic retrieval challenge. Question and answer lengths are measured in tokens. MuSiQue’s controlled hop structure enables our difficulty-scaling analysis (§5.2).

9 F1 Scores↩︎

Table 6 reports token-level F1 scores corresponding to the main results in Table 1. SLEUTH attains the highest F1 on every benchmark, and its lead widens with difficulty (e.g., 62.2 vs. for ReAct on 4-hop, a +11.9-point gap that mirrors the EM result). The component ablations track their EM ordering, confirming that the F1 picture reflects genuinely more correct answers rather than merely longer or shorter outputs; the source-faithful extraction rule, which copies answer phrasing verbatim from confirmed facts, keeps SLEUTH’s exact-match rate close to its token-overlap rate.

10 Token Efficiency↩︎

Table 7 reports average token usage per question. SLEUTH’s working memory output increases token usage modestly on easy tasks (42% on HotpotQA) and minimally on hard tasks (29% on 4-hop), while using comparable or fewer tool calls.

11 The Commitment Mechanism: Supporting Analyses↩︎

This appendix collects the analyses underpinning the evidence sufficiency problem and the nudge mechanism (§5.3): the timeout/conditional-accuracy decomposition that defines the problem, the commitment-timing sweep, accuracy-at-turn convergence, the nudge-isolation control showing structure is necessary, and a comparison against alternative stopping strategies.

11.1 Timeout Decomposition↩︎

Table 8 decomposes EM into conditional accuracy (accuracy among answered questions) and timeout rate (fraction of questions where the agent exhausts its 20-turn budget). A key insight: on 4-hop, SLEUTH achieves both higher conditional accuracy (58.9% vs.%) and lower timeout rate (11.1% vs.%). The 11.1-point EM gap reflects improvements on both dimensions: the structured working memory enables better reasoning, while the commitment mechanism ensures that reasoning translates into answers.

11.2 Nudge Ablation Visualization↩︎

Figure 3 visualizes the exploration-exploitation tradeoff from Table 2. EM plateaus in the 50–70% range while timeout rate increases monotonically with later nudges.

On HotpotQA (2-hop) with GLM-5, the same nudge sweep yields a total spread of only 0.55pp (EM ranges from 64.9 to 65.4 across thresholds \(\alpha \in [0.2, 0.8]\)), confirming that the commitment mechanism’s value is concentrated on hard problems where the evidence sufficiency problem is acute. On easy questions, most episodes terminate naturally before any nudge fires.

11.3 Convergence Analysis↩︎

Figure 4 shows accuracy at turn \(t\): the EM that would result if all agents were forced to stop at turn \(t\) (episodes not yet terminated count as incorrect). This reveals how quickly each method converts evidence into correct answers.

Two patterns emerge. On HotpotQA (easy 2-hop), both methods converge by turn 5, but SLEUTH reaches a higher plateau—the working memory enables more accurate answers even without the nudge, because the structured decomposition prevents redundant searches and aids inference. On harder problems (3- and 4-hop), the curves are nearly identical through turn 12–14, then diverge sharply. This confirms that SLEUTH’s advantage on hard problems comes primarily from the commitment mechanism converting potential timeouts into answers, while its advantage on easy problems comes from better reasoning quality via structured state tracking.

11.4 Nudge Isolation↩︎

A natural question arises from the convergence analysis (§11.3): if SLEUTH and ReAct perform similarly before turn 14, does the nudge alone explain SLEUTH’s advantage? We test this by applying the same commitment trigger to ReAct—identical nudge message at turn 14, without any working memory structure.

The nudge has no effect on ReAct (\(+\)​0.2pp, within noise): forced to commit at turn 14, ReAct’s performance is unchanged because its conversation history is a flat sequence of searches and thoughts with no organized state to synthesize from—the nudge simply triggers whatever the agent would have guessed anyway. In contrast, SLEUTH gains +4.0pp from the nudge because its working memory provides structured facts and ranked hypotheses ready for synthesis. This result establishes that the working memory is the necessary condition for effective commitment. The nudge is not independently beneficial—it is a mechanism that exploits the organized epistemic state that SLEUTH maintains. The same argument applies to other baselines (IRCoT, Self-Ask): none maintain persistent organized state across turns, so a commitment trigger would find no structured evidence to synthesize from.

The nudge isolation result can be understood through the lens of the exploration-exploitation tradeoff in sequential decision-making. In bandit settings, forced exploitation (greedy action selection) is harmful when the agent’s estimate of reward is noisy—it exploits an unreliable signal. The analogous situation here: ReAct’s implicit state after 14 turns is a noisy, unorganized signal—the agent has encountered the relevant facts but has no structured representation of what they collectively imply. Forcing commitment exploits noise.

SLEUTH’s working memory acts as a sufficient statistic for the evidence gathered: the confirmed facts and ranked hypotheses compress the full trajectory into a decision-relevant representation. When the nudge fires, the agent synthesizes from this compressed state rather than the raw conversation history. The quality of the commitment depends on the quality of this compression—which is precisely what structured working memory provides.

This decomposition—working memory as state compression, nudge as exploitation trigger—suggests a general design principle for bounded-computation agents: before adding commitment mechanisms, ensure the agent maintains state in a form suitable for commitment. Concretely, any agent framework that (a) maintains structured intermediate state and (b) provides a principled exploitation trigger should achieve the same synergy. The working memory need not follow SLEUTH’s exact tripartite format; what matters is that it separates signal (confirmed evidence) from noise (raw observations) and rankings (hypotheses) from uncertainties (open questions), enabling a single synthesis step to produce a coherent answer.

11.5 Alternative Stopping Strategies↩︎

The commitment mechanism (nudge at \(\alpha{=}0.7\)) is one solution to the evidence sufficiency problem. We evaluated four alternative strategies on 4-hop MuSiQue, each embodying a different principled answer to “when should an agent commit?”

The time-based nudge outperforms all structural alternatives by a wide margin (+5.9 to +10.6 EM). We analyze why each structural strategy fails:

This strategy requires the agent to decompose the question into sub-questions upfront and commit when all are marked “resolved.” The failure mode is twofold: (1) the agent’s initial decomposition may be incomplete or poorly scoped—a 4-hop question might be decomposed into 3 sub-questions, causing premature commitment; and (2) the “resolved” criterion is itself ambiguous—the agent may mark a sub-question resolved based on weak evidence to satisfy the structural requirement. Timeout rate drops modestly (18.8% vs.%) but conditional accuracy falls 6.8pp, indicating that the commitment criterion triggers at the wrong time.

By preventing the agent from revisiting earlier conclusions, this strategy eliminates over-verification but also eliminates beneficial re-evaluation. On 4-hop chains, early errors propagate: if the agent incorrectly identifies an intermediate entity (e.g., the wrong birth state), the forward-only constraint prevents correction even when contradicting evidence appears later. The lowest conditional accuracy (54.6%) among the structural strategies confirms that irreversibility is too strong a constraint.

Searching for evidence that distinguishes hypotheses is in principle more efficient than confirmatory search, but in practice the agent struggles to formulate effective contrastive queries. Multi-hop questions often have only one viable hypothesis by mid-trajectory; the contrastive protocol then generates artificial alternatives to “eliminate,” wasting turns on searches for non-existent distinctions. The 19.0% timeout rate reflects this wasted effort.

This strategy separates search (free-form) from verification (chain check before answering). The intent is to impose structure only at decision time, avoiding per-turn overhead. However, without continuous state tracking, the free-form search phase suffers from the same context dilution as ReAct—by the time verification occurs, the agent cannot reliably reconstruct the full chain from its unorganized history. The worst EM (42.5%) and highest timeout (29.9%) confirm that structure imposed only at the end cannot compensate for the lack of ongoing state management.

because it does not constrain how the agent reasons or what criteria define sufficiency—it simply bounds the exploration phase. The agent retains full freedom during the first 70% of its budget and receives one intervention that triggers synthesis from existing structured state. This separates the commitment decision (which the model makes) from the commitment trigger (which the mechanism provides), exploiting rather than overriding the model’s reasoning.

12 Working Memory Dynamics↩︎

Figure 5 visualizes how the working memory evolves across turns on 4-hop MuSiQue (\(n{=}405\)), restricted to episodes lasting \({\geq}14\) turns to avoid survivorship bias. Panel (a) shows evidence monotonicity in practice: confirmed facts accumulate steadily across the trajectory, reflecting continuous evidence extraction. Active hypotheses remain stable (\({\sim}2\) throughout), reflecting the agent’s ability to maintain and rank competing explanations without proliferation. Open questions decrease gradually, reflecting progressive uncertainty resolution. Panel (b) shows that \({\sim}\)​66% of episodes terminate naturally before the nudge at turn 14 (the agent finds sufficient evidence and calls finish without intervention). The commitment mechanism fires only in the remaining \({\sim}\)​34% of episodes—the fixed cohort plotted in panel (a)—precisely those that would otherwise risk timeout.

13 Robustness Analysis↩︎

We test SLEUTH’s sensitivity to two key hyperparameters: turn budget and retrieval breadth.

Table 11 varies the maximum number of turns on 4-hop MuSiQue. For each budget, we sweep the nudge timing and report the best configuration (turn 6, 10, and 14 for budgets 10, 15, and 20 respectively—all near \(\alpha{=}0.7\)).

SLEUTH’s advantage is robust across budgets (+8.6 to +11.4pp), demonstrating that the structured working memory provides consistent benefit regardless of computational constraints. Notably, SLEUTH saturates at budget=15 (52.1%), nearly matching its budget=20 performance (53.1%)—the commitment mechanism at \(\alpha{=}0.7\) effectively resolves all questions that are resolvable within the evidence space. ReAct continues to improve with additional budget (34.1\(\to\)​40.7\(\to\)​42.0) but never closes the gap, confirming that SLEUTH’s advantage comes from organizing evidence rather than merely having more time. This confirms that the \({\sim}\)​2.5\(\times\) hops guideline noted in §6 is not a hard constraint but a soft one: SLEUTH benefits at any budget where at least one full reasoning chain can be completed.

Table 12 varies the number of paragraphs returned per search query on 4-hop MuSiQue. SLEUTH’s advantage is substantial under sparse (top-\(k{=}1\): +10.1pp), default (top-\(k{=}3\): +11.1pp), and noisy (top-\(k{=}5\): +10.9pp) retrieval. With sparse retrieval, the working memory’s fact-tracking prevents information loss when relevant paragraphs are found only once across multiple searches. With noisy retrieval, the structured fact/hypothesis separation helps the agent distinguish signal from irrelevant context. The consistent \({\sim}\)​10–11pp advantage across all retrieval settings confirms that SLEUTH’s benefit is robust to retrieval quality.

14 Statistical Significance↩︎

We report bootstrap confidence intervals (10,000 resamples, paired by question) for the key comparison: SLEUTH vs.ReAct with Claude Sonnet 4.6. All differences are significant at \(p < 0.001\). Note that confidence intervals widen with difficulty (from \(\pm\)​0.7 on HotpotQA to \(\pm\)​4.0 on 4-hop) due to decreasing sample size (\(N{=}7405 \to 405\)), yet even the lower bound of the 4-hop CI (+7.2) exceeds the HotpotQA point estimate, confirming that the scaling-with-difficulty finding is robust.

15 Head-to-Head Analysis↩︎

Table 14 shows per-question win/loss counts between SLEUTH and ReAct. SLEUTH’s advantage is broad-based: it wins approximately 4–6\(\times\) more questions than it loses on every dataset. The “both wrong” category is largest on 4-hop (176/405 = 43%), indicating substantial headroom—these are questions where better retrieval or inference could help both methods, and where complementary approaches (e.g., deliberative verification) would add value orthogonally to SLEUTH’s state management contribution.

16 Working Memory Schema Sensitivity↩︎

The ablation block of Table 1 includes three two-component variants—Facts-Only (F), Facts+Questions (F+Q), and Facts+Hypotheses (F+H)—that each maintain a different subset of SLEUTH’s working memory while sharing the identical commitment mechanism (nudge at \(\alpha{=}0.7\)) and source-faithful extraction. This isolates the effect of which structural components are maintained, and answers whether SLEUTH’s full tripartite schema is over-specified: could a single added component (hypotheses or questions, but not both) recover the full gain?

Two observations emerge. First, the three two-component variants cluster tightly—within \({\sim}\)​2pp of each other on every split (e.g., 47.7–49.9 on 4-hop)—and none approaches full SLEUTH, which leads the best two-component variant by 3.2–4.9 points on HotpotQA and MuSiQue (and a smaller +1.4 on the easier 2Wiki, consistent with structure mattering most as difficulty grows). Second, open questions are not independently beneficial when added to facts alone: Facts+Questions is the weakest of the three subsets on every split, consistently below Facts-Only. This indicates that open questions do not help by themselves—they require ranked hypotheses to anchor what each question is trying to resolve. The full tripartite structure is thus synergistic rather than additive: hypotheses give the agent candidate answers to discriminate between, and open questions turn that discrimination into directed action. Removing either collapses the benefit, confirming that each component earns its place only in the presence of the others.

17 Error Decomposition↩︎

Table 15 decomposes failures into three categories: timeouts (agent exhausts turn budget without answering), reasoning errors (agent retrieves relevant evidence but produces an incorrect answer), and verbose answers (prediction contains the gold answer but includes extraneous context that causes exact-match failure). The “Other” column captures remaining partial-match failures where the gold is not contained in the prediction (e.g., wrong entity from a related passage).

Three findings emerge. First, SLEUTH’s timeout rate scales much more gracefully: 2.2%\(\to\)​4.1%\(\to\)​11.1% versus ReAct’s 2.8%\(\to\)​3.8%\(\to\)​17.8%. The commitment mechanism effectively addresses the evidence sufficiency problem—without it, SLEUTH’s timeout rate on 4-hop is 24.7% (§[sec:nudge-ablation]). Second, SLEUTH achieves lower reasoning error rates at every difficulty level (\(-\)​6.0pp on 2-hop, \(-\)​7.8pp on 3-hop, \(-\)​3.7pp on 4-hop), confirming that the structured working memory helps the model draw correct inferences. On 4-hop, SLEUTH’s EM is 11 points higher because its lower timeout rate (11.1% vs.%) and lower reasoning error rate combine to produce substantially more correct answers. Third, SLEUTH achieves substantially lower verbose answer rates (4.4–8.1% vs.–13.3% for ReAct), as the source-faithful extraction rule successfully reduces paraphrasing errors by anchoring answers to confirmed facts.

This per-split decomposition substantiates the two-failure-mode account in §[sec:retrieval]: SLEUTH’s reasoning-error reduction (information loss prevented by fact-tracking) dominates the gain on 2- and 3-hop, while its timeout reduction (information paralysis prevented by the commitment mechanism) dominates on 4-hop. Among SLEUTH’s remaining reasoning errors on 4-hop, the primary bottleneck is inference quality over correctly-retrieved evidence—the model draws wrong conclusions from the right facts. This bottleneck is orthogonal to SLEUTH’s contribution (state organization) and would benefit from complementary approaches such as deliberative verification [40], context compression [41], or logic-aware retrieval [42].

18 System Prompts↩︎

All methods share identical tool interfaces (search, lookup, finish) and a basic answer format instruction (brief factual answer, no explanation). SLEUTH additionally includes a source-faithful extraction rule that instructs the agent to copy answers verbatim from its confirmed facts—this leverages the structured working memory’s sourced citations to eliminate paraphrasing errors. This instruction is architecturally motivated: it references SLEUTH’s typed [F] entries with source citations, which only exist within the working memory structure; an equivalent “use exact source wording” instruction is already included in the shared format for all agents but lacks a structured target to reference. Below we show the reasoning protocol portion of each prompt—the only component that differs between methods.

Ablation variants. The structural ablations (Notes, Facts-Only, Facts+Hyp.) use prompts of comparable length to SLEUTH, differing only in which working memory components are included. Notes uses an unstructured scratchpad; Facts-Only maintains only the Confirmed Facts section; Facts+Hyp.adds ranked hypotheses but omits Open Questions. All include the same shared answer format and tool instructions above.

19 Example Trace↩︎

Figure 6 shows a comparative trace on a real 4-hop MuSiQue question where SLEUTH succeeds in 11 turns and ReAct times out at 20. Both agents achieve 100% supporting paragraph recall—demonstrating that the failure is not retrieval but state management. The reasoning chain requires: album \(\to\) performer \(\to\) birth state \(\to\) largest city \(\to\) race winner.

None

20 Design Rationale↩︎

We address several design questions that arise from SLEUTH’s architecture.

The search(query) tool uses lexical (sparse) scoring over the paragraph collection provided with each question (10 paragraphs for HotpotQA/2Wiki, 20 for MuSiQue): each paragraph is ranked by token overlap with the query (a Jaccard-style overlap over word tokens). The query is the agent’s free-form search string; the top-\(k\) paragraphs by this score are returned verbatim. The lookup(title) tool returns the full text of a named paragraph if it exists in the collection. Both tools are identical across all methods—no method-specific retrieval tuning is applied. Supporting paragraph recall (fraction of gold paragraphs retrieved at least once) exceeds 90% for all methods on 4-hop MuSiQue, confirming that retrieval quality is not the bottleneck; the difference lies in how agents organize and act on retrieved evidence.

A natural concern is whether the protocol adherence mechanism (§5.5) introduces an asymmetric advantage. Enforcement consists of two components: (1) a model-adapted prompt with explicit structural delimiters that raises adherence from \({\sim}\)​15% to \({\sim}\)​90%, and (2) a runtime check that rejects responses missing proper notation and re-prompts the agent, raising adherence to \({\sim}\)​99%. Rejected turns do not count against the 20-turn budget; the mechanism allows up to 5 reminders per episode. This combined enforcement is only applied in the cross-model experiments with GLM-5 (Table 3 and Table 4). The primary Sonnet results in Table 1 use no runtime enforcement and no prompt adaptation—the model maintains the working memory structure through instruction-following alone with the general prompt. Baselines do not receive equivalent format checks because they have no structured format to validate: ReAct, Self-Ask, etc.produce free-form reasoning text, so a format checker would have nothing to enforce beyond the shared answer-format instruction that all methods already receive. One might still ask whether a lightweight answer-structure validator (e.g., rejecting verbose answers and re-prompting for a short span) could help baselines. We argue it cannot close the gap, for two reasons grounded in our analysis. First, baseline errors on hard problems are dominated by timeouts and reasoning errors, not answer-formatting: on 4-hop, ReAct’s verbose-answer rate is only 4.4% (Table 15), so even perfect answer extraction would recover at most \({\sim}\)​4 points, far short of the \({\sim}\)​11-point gap. Second, the source-faithful extraction rule that addresses verbose answers is already included in the shared answer format given to every method (Appendix 18); SLEUTH’s advantage comes from having structured [F] entries to copy from, not from the instruction itself. The enforcement is thus best understood not as an external aid but as a mechanism to surface the cost of protocol drift—it answers the question “what if the model consistently followed the protocol it was given?” and demonstrates that the protocol itself (not model capability) is the active ingredient. Regarding token cost: re-prompts add \({\sim}\)​50 tokens per occurrence and occur on average 1.2 times per episode for GLM-5; this overhead (\(<\)​0.5% of total tokens) is included in the reported token counts for Table 7.

SLEUTH’s confirmed facts are monotonically accumulated—once confirmed, they are never retracted within an episode. This design choice prioritizes evidence preservation over revision: in multi-turn episodes, the primary failure mode we observe is evidence loss (facts getting buried under subsequent context) rather than evidence error (facts being wrong). Our error analysis supports this: among SLEUTH’s errors on 4-hop MuSiQue, 96% of wrong answers occur despite the agent correctly retrieving \(\geq\)​75% of supporting paragraphs. The bottleneck is inference over correctly-retrieved evidence, not fact extraction accuracy.

However, monotonicity can entrench early reasoning errors. We observe a characteristic failure mode: the agent confirms a fact that is technically correct but contextually misleading. For example, on the question “What city shares a border with the city where a person went to work during the gold rush in the state where the Shakespeare Bridge is located?” (gold: Rio Linda), the agent confirms [F2] “Samuel Brannan worked in San Francisco during the California Gold Rush”—a true statement—and proceeds to search for cities bordering San Francisco (arriving at “Daly City”). The correct reasoning chain requires recognizing that Brannan founded Sacramento during the gold rush, making Sacramento the target city, with Rio Linda as its neighbor. Once San Francisco was confirmed as a fact, the alternative interpretation was never explored.

In open-domain settings with potentially contradictory sources, monotonicity poses greater risk. We identify three extensions that could address this without sacrificing evidence preservation: (1) a confidence level per fact (not just per hypothesis) that degrades when contradicting evidence appears; (2) a contradiction-detection step that flags when a new extraction conflicts with an existing fact, triggering explicit disambiguation rather than silent overwriting; and (3) temporal grounding that preferentially trusts more recent sources when temporal conflicts arise. These extensions are orthogonal to SLEUTH’s core contribution and represent promising directions for open-domain deployment.

The commitment threshold \(\alpha{=}0.7\) was characterized primarily on 4-hop MuSiQue, raising the question of whether it generalizes. Two pieces of evidence suggest robustness. First, on easy tasks (GLM-5 HotpotQA), sweeping \(\alpha \in [0.2, 1.0]\) produces only 1.4pp total spread in EM—the threshold is effectively irrelevant when most questions are answered naturally before the nudge fires. Second, the 70% threshold has a structural interpretation: it reserves 30% of the budget (\({\sim}6\) turns) for synthesis and answer construction, which empirically provides sufficient margin for answer construction even on 4-hop problems. This suggests that 70% is a reasonable default for any bounded-horizon task where synthesis requires fewer turns than exploration.

That said, tasks with very different exploration-to-exploitation ratios (e.g., tasks requiring extensive tool use but trivial synthesis, or tasks requiring deliberative multi-step synthesis) may benefit from re-tuning. An adaptive threshold—based on state features such as hypothesis confidence entropy, the ratio of open questions to confirmed facts, or the rate of new fact discovery—could offer broader robustness. We leave principled adaptive mechanisms as future work, noting that our fixed threshold achieves strong results across all five benchmarks without per-dataset tuning.

SLEUTH occupies a deliberate design point: lightweight (prompt-only, no symbolic controller), portable (works with any instruction-following model), and interpretable (state is natural language). Graph-structured approaches that maintain explicit evidence graphs or employ external controllers [33] offer stronger guarantees about information flow but require additional infrastructure. Verification-oriented pipelines that decouple search from synthesis address similar bottlenecks to our evidence sufficiency analysis but typically require multi-agent coordination. SLEUTH’s results suggest that substantial gains are achievable at the lightest end of this spectrum—structured prompting with a single agent—and that more complex architectures may be most valuable for the residual errors (inference quality over correctly-retrieved evidence) that SLEUTH does not address.

References↩︎