Skip to content

ArbiGraph: Arbitrarily Scalable Verifiable Task Graphs for Evaluating Context Management

🕒 Published (v1): 2026-07-22 22:30 UTC · Source: Arxiv · link

Why this paper was selected

Scalable benchmark for context management in tool-assisted agents; evaluates retain/update/discard across workflows

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

ArbiGraph is a benchmark generator that composes parameterized, executable natural-language tasks into verifiable dataflow graphs to evaluate context management in tool-assisted LLM agents. It independently controls context length, dependency topology, and value type, enabling exact automatic verification. Evaluating Qwen3.5-27B reveals that baseline task accuracy does not predict dependent-chain accuracy: math accuracy drops from 94.5% (isolated) to 61.2% on branching multichain topologies.

Problem

Existing long-context and memory benchmarks fix composition patterns (packed problems, dependency chains, instruction sequences) rather than treating dependency topology as a controlled variable. They do not cleanly separate local task-solving failure from failures of intermediate-state propagation, selective forgetting, or cross-task interference. There is no benchmark that simultaneously varies context length, dependency structure, and value type while supporting user-specified DAG topologies with exact automatic verification.

Method

ArbiGraph represents each task as a typed tuple \(T_i = (x_i, a_i, p_i, b_i, y_i, s_i)\): input, pre-processing adapter, natural-language prompt, post-processing adapter, output, and an executable solver \(s_i\) hidden from the agent. Tasks are composed into DAGs by type-matching: an edge \(T_i \to T_j\) is valid when \(T_i\)'s output type is compatible with \(T_j\)'s input type. Intermediate data is typed as scalars or lists; adapters handle bounding (lists capped at length 10, scalars modulo 100) and type coercion to prevent complexity explosion. The framework is instantiated with three task categories: 40 hand-selected math operators (linear algebra, polynomial arithmetic, discrete transforms, combinatorics, geometry, number theory), 80 Python-tracing tasks from LeetCode, and 41 GSM-Symbolic word-problem templates. Four evaluation topologies are tested: baseline (single target task), forgetting (3 independent distractors preceding the target), chain (4-task linear dependency path), and multichain (8-task branched DAG with split/recombine structure). Agents interact via a calculator tool and a multi-turn harness with targeted repair prompts to handle mechanical failures (malformed tool calls, missing boxed answers, context cutoffs) as separate confounds from reasoning failures.

Key Contributions

  • Formal definition of context management as typed task-to-task state propagation, distinct from generic long-context retrieval or single-task reasoning.
  • ArbiGraph: a benchmark generator accepting user-specified DAG topologies via NetworkX node-link JSON, producing auto-generated, auto-verified single-prompt instances at arbitrary scale.
  • Instantiation with three task categories (math, Python tracing, GSM-style) covering scalar-to-scalar, scalar-to-list, list-to-scalar, and list-to-list type signatures.
  • Empirical demonstration that high baseline accuracy does not predict chain/multichain accuracy, with quantified accuracy degradation per topology and task category.
  • Repair protocol that isolates context-management failures from mechanical trajectory failures.

Results

All results are for Qwen3.5-27B with a calculator-tool agent harness:

  • Baseline accuracy: math 94.5%, Python tracing 96.8%, GSM 100.0%
  • Forgetting topology (3 distractors + target): math 89.2% (−5.3 pp), Python tracing 92.5% (−4.3 pp), GSM 100.0% (no degradation)
  • Chain topology (4-task linear dependency): math 75.5% (−19.0 pp), Python tracing 90.1% (−6.7 pp), GSM 96.0% (−4.0 pp)
  • Multichain topology (8-task branched DAG): math 61.2% (−33.3 pp from baseline), Python tracing 90.5% (stable relative to chain), GSM n/a (scalar-only outputs preclude branching)
  • Math chains generate substantially longer trajectories (up to ~52K tokens on multichain vs. ~13K baseline), confirming increased reasoning effort rather than only harder final answers.

Limitations

  • Only one model (Qwen3.5-27B) is evaluated; results are preliminary and not a multi-model comparison.
  • Typed intermediate states are restricted to scalars and lists; richer types (structured objects, text, images) are not yet supported.
  • GSM-style multichain instances cannot be generated because GSM tasks produce only scalar outputs, precluding the branching layout.
  • Evaluation uses only four fixed topologies; the framework's arbitrary scalability is asserted but not fully exercised in the reported experiments.
  • ~105 wall-clock inference hours required for the reported evaluation, indicating high cost for comprehensive benchmarking.
  • Repair protocols may partially mask genuine context-management failures by prompting the agent to produce missing outputs.

Relevance to Agentic AI / LLM Agents

ArbiGraph directly targets the failure modes of tool-assisted agents operating on extended, multi-step workflows—precisely the regime in which deployed agents must propagate, transform, and selectively discard intermediate computational state. The finding that an agent solving 94.5% of isolated tasks drops to 61.2% on branching dependent chains quantifies a gap that single-task benchmarks hide, and establishes a reproducible, scalable substrate for tracking context-management progress as models and agent designs evolve. The typed DAG abstraction is complementary to memory systems research (MemGPT, LongMemEval) and extends naturally to evaluating retrieval-augmented and multi-agent orchestration pipelines where intermediate state handoffs are critical.