acceptodds
Under review as a conference paper at ICLR 2027

TASKGRAPH: DYNAMIC HIERARCHICAL MEMORY FOR LONG-HORIZON LANGUAGE MODEL AGENTS

Abstract

Long-horizon tasks require agents to sustain extended interactions and multi-step reasoning. As context grows, fragmented memories can draw attention toward local details, causing agents to lose track of task progress and forget earlier goals and constraints. Existing methods organize historical information through hierarchies and relational links. These structures improve retrieval but do not explicitly organize memory around task progress and the requirements of each execution step. We propose TaskGraph, a unified model of task and memory that represents memory as the evolving structure of task execution. Task goals, stages, steps, and atomic records of constraints, evidence, and variables form a hierarchical graph linked by inclusion, mainline, and dependency relations. The graph therefore turns memory into an execution structure: it binds goals to completed work and makes the constraints, variables, and evidence required by the next step immediately accessible. For each current step, TaskGraph selects relevant historical dependencies and constructs its execution context from the graph. Observed results are then written back to update the memory available to subsequent steps. This process allows task execution and memory to evolve together within a shared representation. On StableToolBench, TaskGraph improves macro-average final answer correctness by 14.97 percentage points over the same-backbone DFS baseline using Qwen3-14B-AWQ, validating the effectiveness of jointly modeling task progression and memory

Primary area:
foundation or frontier models, including LLMs
Keywords:
LLM agents, agent memory, long-horizon planning, hierarchical memory, context management

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_eEoLOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates how long-horizon language model agents can link historical information with current task progress and execution requirements. The authors propose TaskGraph, a four-layer graph composed of goals, phases, steps, and atomic records, which unifies the organization of tasks and memory through attribution, backbone, and dependency relations. During execution, the system expands phases on demand, filters historical dependencies for the current step, and writes execution results back into the graph to support subsequent actions. The paper evaluates the approach across five settings: tool use, historical interaction QA, dialogue summarization, multi-document QA, and long-form generation. Furthermore, it analyzes the contribution of specific design components through ablation studies on the tool use task.

Critical strengths

The paper addresses the meaningful problem that "historical information may be semantically relevant but not necessarily meet the actual needs of the current step." It provides a coherent solution through a unified task-and-memory graph, step-oriented dependency filtering, and result back-writing, demonstrating clear value in system design. The experiments also provide substantial support: on StableToolBench, compared to DFS with the same backbone, TaskGraph improves the final answer accuracy by 14.97 and 8.18 percentage points for Qwen and DeepSeek, respectively. Four component ablation studies further support the effectiveness of the main design. Additionally, the long-form generation experiments, which utilize human evaluation, showcase the potential of leveraging distant historical information to advance plot development. These results make the method worthy of further research and application.

Critical weaknesses
  1. The alignment and modification rules for task paths are unclear. Appendix A.2 does not explain how new inputs are mapped to existing paths, nor when the system should continue, modify, or create a path; Appendix A.3 further stipulates that already-expanded phases usually retain their original decomposition. As a result, it remains unclear how the system adjusts or creates branches when execution results invalidate the original plan, limiting the assessment of its dynamic execution capability.
  2. Performance on dynamic state and temporal reasoning is weak. TaskGraph achieves 20.9% accuracy on the LongMemEval Dynamic category, lower than Atomic RAG’s 50%; on the MultiHop-RAG Temporal category, it scores 58.82%, below all three baselines. This suggests that maintaining historical order and state records is not yet sufficient to ensure information applicability, and the paper lacks further analysis distinguishing errors from state extraction, outdated-value handling, retrieval, and final reasoning.
  3. The three recall channels lack independent ablation. The existing Hard-Dependency Only ablation changes the dependency construction method as a whole, making it impossible to identify the individual contributions of the structural, semantic, and activity channels. The candidate-count statistics in Figure 8 also do not establish their complementarity; channel-by-channel comparisons with controlled candidate counts are still needed.
  4. Attribution and generalization evidence for long-horizon capability is limited. In M5, each method generates only one novel, with long-distance dependency evaluation based on 10 foreshadowing items; local coherence covers only a subset of chapters. The paper also does not analyze performance by task length or dependency distance, so it is difficult to judge how the advantage changes as tasks become longer and whether it generalizes stably.
  5. Key details of context packing are missing. Figures 1 and 2 use Pack(B), but B is not clearly defined, and the paper does not explain how dependencies are preserved and evidence is truncated when content exceeds the limit. This directly affects the actual execution input and makes it difficult to determine whether the budget and truncation rules are consistent in the Flat-Context ablation.
Questions for authors
  1. How are new inputs aligned with existing task paths and nodes? When execution results conflict with the original plan, what rules determine whether the system continues along the current path, modifies it, or creates a new branch? Please provide a complete worked example.
  2. At which stage do most Dynamic and Temporal errors occur? For multiple historical values of the same variable, how does the system select the applicable state based on the temporal conditions in the question?
  3. Are there results that remove the structural, semantic, and activity channels one at a time? When the number of candidates is controlled, does each channel still contribute independently?
  4. Can existing logs be used to report performance by task length or dependency distance? Are there results from other independent long-horizon tasks that support the generalizability of the current findings?
  5. How is B in Pack(B) defined? When the limit is exceeded, how does the system retain necessary dependencies while truncating other content? Does Flat-Context use the same budget and truncation rules?
2 comments

Thank you for the detailed response and additional experiments. The channel-wise ablations, execution-length analysis, and repeated long-form generations provide useful evidence, and the context-packing description clarifies the implementation. My main concerns remain the handling of tool observations that invalidate an existing plan and the selection of applicable historical states for dynamic and temporal questions. The added explanations and diagnostics clarify the current behavior, while reliable handling of these cases remains insufficiently demonstrated. I therefore retain my original rating.

Thank you for the follow-up and the concrete examples from the execution logs. The traces clarify how failed prerequisites affect scheduling, and the historical-state examples demonstrate how graph expansion can recover relevant earlier evidence. Together with the additional ablations and common-budget comparisons, these results strengthen my assessment of the method’s practical value. I will raise my rating to 3.

Reviewer_D1oFOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes TaskGraph, which represents an agent's memory as the evolving execution structure of the task rather than as a transcript, a summary, or a semantic index.

(1) Representation. Memory is a typed directed graph over four levels:

  • L1 task;
  • L2 stage;
  • L3 executable step;
  • L4 atomic records of constraints, evidence and variables.

Edges are INCLUSION (hierarchy), MAINLINE (execution order) and DEPENDENCY (prerequisite/evidence). L2 and L3 nodes carry PENDING/ACTIVE/DONE/DROPPED states.

(2) Coupled update rules. Initialization builds only the goal, stages and explicitly stated global L4 records, and does not pre-generate future steps. When the scheduler reaches an unexpanded stage, that stage alone is expanded into L3 steps using accumulated state. For the selected step, dependencies are built from three candidate channels (structural: same stage; semantic: global dense+lexical hybrid; activity: active/unresolved/recently used), deduplicated and filtered by the agent, followed by a readiness check. The step's context is then assembled from goals, dependency L4 records and recent state, and execution results are written back immediately, updating L4 variables/evidence or the step status. A separate FinalizationStage produces the answer from written-back L4 records.

(3) Validation across five settings, split into online execution and offline (frozen-graph) evaluation:

-*StableToolBench (291 solvable queries): +14.97 pp macro FAC over same-backbone DFS-w2 on Qwen3-14B-AWQ (41.63 vs 26.66), and +8.18 on DeepSeek-V4-Flash. Component ablations show Flat-Context −10.11 FAC and No-Structured-L4 −7.36.

  • LongMemEval-V2-Text (294 q): 64% overall, +25.2 pp over atomic RAG with 52.6% fewer tokens, but Dynamic (changing state) is 21% vs 50% for atomic RAG.
  • LoCoMo event summarization: best ROUGE and FActScore recall/F1 (73.81/65.42), lower FActScore precision than long context.
  • M5 long-form generation: one 320-chapter novel per method, 10 preregistered hooks, two independent human reviewers with a third adjudicating (κ=0.97, 59/60 agreement); TaskGraph reaches 8/10 hooks vs 3/10 for the best baseline (B4) and the highest plot coherence (4.44).
  • MultiHop-RAG (200 q): 79.0% overall, not significantly different from RAPTOR/GraphRAG, and lowest Temporal accuracy (58.8%).

Code, prompts, configurations and the six generated novels are released.

Critical strengths
  1. The formulation is well motivated and the ablations actually test it, rather than just decorating it. TaskGraph's claim is that the relationship between memory and task progress carries the signal, not the memory content. The component ablations support exactly that claim while holding the pipeline fixed:
  • replacing step-anchored context with a flat serialized history costs 10.11 FAC points;
  • removing structured L4 records costs 7.36;
  • restricting dependencies to planning-time declarations costs 6.75;
  • expanding all stages up front (Static-L3) costs 7.89.

Because these variants keep the same graph machinery, the same LLM roles and roughly the same call structure, the deltas are not explainable by "more compute". That is the right experiment design for this paper, and it is the main reason I lean toward acceptance. The StableToolBench gain is also large in absolute terms (+15pp FAC, from 26.7 to 41.6), and it holds on a second backbone (+8.18).
2. The reporting is candid, including results that weaken the paper, and the artifacts are complete enough to check it. The paper states plainly that Dynamic-state accuracy is 21% versus 50% for atomic RAG and explains why (the graph is frozen, so it cannot re-derive which state applies); that MultiHop-RAG differences are not statistically significant; that Temporal accuracy is below all three baselines; and that M5 uses more tokens in total. It also reports the per-advanced-hook normalization (1.41M tokens, 41.9% below B4) as an explicitly different accounting from total tokens, rather than quietly switching metrics. Combined with the released code, prompts and all six novels, and human adjudication at κ=0.97, this is a paper a reader can audit.

Critical weaknesses
  1. The headline StableToolBench result is confounded with inference compute, and no compute accounting is given for that benchmark. TaskGraph issues many additional LLM calls per query (instruction parsing, per-stage expansion, per-step dependency filtering over up to 192 candidates, and per-step L4 extraction), whereas CoT@1 is a single chain and DFS-w2 explores tool paths without candidate filtering. The paper reports token cost for LongMemEval, LoCoMo and M5, but for StableToolBench — the setting that supplies the abstract's headline number — there is no token count, no call count and no latency, only a note that the traces record call counts. The closest ablations (Flat-Context, No-Structured-L4) do control for structure at roughly fixed pipeline, which is good evidence for which component matters, but they do not tell us how much of the +14.97 pp would be recovered by spending the same extra calls on a simpler intervention (e.g., the same backbone allowed k rounds of self-reflection, or best-of-n with a verifier, at matched token budget). Without that, the paper's central quantitative claim cannot be separated from "more structured inference is better than one chain", which is not the contribution being claimed.
  2. The evidence is narrower than the "five settings" framing implies, and the remaining comparisons are statistically thin. (a) Where TaskGraph wins clearly is static facts (72% vs 22%) and procedures (100% vs 57%), but on procedures the AgentRunbook-R baseline also scores 100% (74/74), so that cell does not discriminate. Where the benchmark actually probes state maintenance — Dynamic — TaskGraph is 29 points worse than a trivial atomic RAG. On MultiHop-RAG the overall difference against RAPTOR and GraphRAG is not significant, and Temporal is the worst of all methods. So the multi-setting claim rests on one online tool-use benchmark plus one long-form generation study.

(b) Variance is largely unreported. StableToolBench runs one retained trajectory per query per method, and the reported ± for baselines describes repeated judging, not generation seeds, as the appendix states; TaskGraph's own rows carry no intervals at all. M5 is a single novel per method judged on 10 hooks (60 method-hook units), with plot coherence over 32 fixed pairs, and no repeated generation. The per-advanced-hook token metric additionally divides by each method's own number of successes, which mechanically favors the method that advances more hooks; total tokens (11.28M vs 7.28M for B4) tell the opposite story. These are all reported honestly, but they mean the effect sizes should be read as indicative rather than established.

Questions for authors
  1. Compute accounting for StableToolBench. What are the mean input/output tokens, LLM calls and wall-clock latency per query for TaskGraph versus CoT@1 and DFS-w2 on the three subsets? Can you add a matched-budget control — the same backbone with the same token or call budget spent on, e.g., k rounds of self-reflection or best-of-n with a verifier — and report FAC? This is the single result I would most like to see de-confounded.
  2. Dynamic-state failure. TaskGraph scores 21% on Dynamic versus 50% for atomic RAG, and the paper attributes this to the frozen graph. Is that a limitation of the frozen protocol or of the representation? An experiment in which the graph is allowed query-time state resolution (or an added MAINLINE-based "latest value" rule) would separate the two, and would tell us whether the online claim extends to state tracking.
  3. Procedure questions. Both TaskGraph and AgentRunbook-R score 74/74 on Procedure. Are these questions answerable from a stored runbook without any retrieval? If so, what does this category measure, and should it be excluded from the overall average or reported separately?
  4. MultiHop-RAG. Given that the overall paired difference is not significant and Temporal is the worst, how do you reconcile this with the claim of gains "across five settings"? Would you restate the scope as online tool use plus long-form generation, with the retrieval benchmarks as diagnostic?
  5. Variance. Can you report generation-seed variance (or at least Wilson intervals on FAC and SoPR) for Table 1, and a second novel per method for M5 on at least a subset of hooks? Please also report the M5 comparison as total tokens and tokens per chapter alongside the per-advanced-hook figure, so both accountings are visible side by side.
  6. M5 human evaluation. Were P1–P3 independent of the author list, and how were their judgments audited (the paper mentions gpt-5.6-sol for "supplementary metric auditing")? Since the paper has no ethics statement, a brief note on the reviewer protocol would help.
Reviewer_4jATOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes TaskGraph, a memory framework that represents task goals, stages, executable steps, and atomic records of variables, constraints, and evidence in a shared graph. Stages are expanded when they become active. For each step, the agent selects historical dependencies through structural, semantic, and activity-based retrieval, assembles the execution context, and writes observed results back into the graph. The main contribution is this coupling of task progression with memory construction and use.

The evaluation covers StableToolBench, three offline memory/retrieval settings, and a 320-chapter novel-generation task. The strongest result is on StableToolBench, where final-answer correctness improves over same-backbone DFS by 14.97 points with Qwen and 8.18 with DeepSeek. Component ablations support the usefulness of the proposed design.

Critical strengths
  1. The task and memory representation fit the problem well. A useful aspect of TaskGraph is that it records why a piece of historical information matters to the current step. Variables, constraints, evidence, and prerequisites have explicit roles, and the graph is used for both context construction and execution control. The distinction between informational dependencies and prerequisites that gate execution is particularly sensible. This gives the framework a concrete purpose beyond storing a more elaborate history and makes its behavior easier to inspect.

  2. The tool-use improvements are substantial and supported by meaningful ablations. On the same 291 StableToolBench queries, final-answer correctness increases from 26.66% to 41.63% with Qwen and from 46.78% to 54.96% with DeepSeek (Table 1). Seeing gains with two backbones strengthens the empirical case. The ablations also provide useful evidence within the proposed system: removing structured L4 records reduces Qwen FAC to 34.27%, and replacing the step-specific context with flat history reduces it to 31.52% (Table 12). These results make the memory organization worth taking seriously.

Critical weaknesses
  1. The main online comparison does not adequately isolate the contribution of the proposed graph.

StableToolBench compares TaskGraph with CoT and DFS, while TaskGraph introduces a more involved pipeline for stage expansion, dependency selection, state extraction, and finalization. Appendix B explains the evaluation protocol and mentions recorded call counts, but the paper does not report per-method model calls, total input/output tokens, or the effective execution limits for this comparison. The ablations are helpful, although some also change the amount or timing of computation. I therefore cannot tell how much of the gain comes from the graph representation versus differences in planning and inference expenditure.

A closer task-aware memory baseline is also missing from this online evaluation. For example, HiAgent (Hu et al., ACL 2025) already organizes working memory around subgoals, summarizes completed subgoals, and retrieves earlier trajectories when needed. TaskGraph’s explicit dependency edges and typed state records provide a plausible distinction, but a comparison under comparable resources would make their added value much clearer. This matters to my assessment because the proposed integration is the central contribution.

  1. The evidence for dynamic long-horizon execution is narrower than the breadth of benchmarks suggests.

As the authors state in Section 4 and Appendix A.6, LongMemEval, LoCoMo, and MultiHop-RAG use frozen graphs. These experiments test useful aspects of memory organization, but they do not exercise online stage expansion and execution write-back. M5 does provide an extensive history, yet it uses a fixed chapter plan and one novel per method, with ten hooks evaluated within that novel. Its results are encouraging as a case study, but provide limited evidence of generalization across long tasks.

This leaves StableToolBench as the only evaluation of the full dynamic execution loop. The paper does not characterize the actual execution horizons or show how the gains vary with task length or dependency distance. The changing-state result on LongMemEval also warrants attention: TaskGraph answers 18/86 Dynamic questions correctly, compared with 43/86 for atomic RAG (Table 13). Although this is a frozen-memory setting, it shows that preserving structure and order does not yet reliably recover the applicable state. Taken together, the evidence is stronger for useful memory organization than for robust dynamic execution over long horizons.

Questions for authors
  1. Clarification of experimental controls. For Tables 1 and 12, what were the model-call counts, input/output token usage, tool-call counts, and stopping limits for each method? Please include planning, dependency filtering, state extraction, and finalization. Were any budgets matched across methods? A comparison at a common inference budget, particularly against a task-aware memory baseline or the same planner with hierarchical summaries, would materially affect my assessment.

  2. Analysis of the existing online runs. What are the typical and upper-tail execution lengths on StableToolBench? Can you show whether the FAC improvement and the Static-L3/Flat-Context ablation gaps persist on the longer tasks, using the same query groups across methods? This would help establish which results directly support the long-horizon claim.

  3. Clarification of adaptation after unexpected observations. Appendix A.3 states that an expanded stage is not decomposed again unless a user correction directly affects it. What happens when a tool observation invalidates the remaining steps of an already expanded stage? Can the agent revise those steps or introduce a recovery step, or does it proceed through the existing plan and drop blocked steps? A concrete execution trace would help clarify the scope of the claimed dynamic adaptation.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.