# ArbiGraph: Arbitrarily Scalable Verifiable Task Graphs for Evaluating Context Management

arXiv: https://arxiv.org/abs/2607.20764 · HTML: https://mlsanity.com/paper/2607.20764/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 33 of its 40 references that are in the map.
- First posted on arXiv 22 Jul 2026.

## Builds on (most cited first, 30 of 33)

- [Lost in the Middle: How Language Models Use Long Contexts](https://mlsanity.com/paper/2307.03172/) (2023)
- [LiveCodeBench: Holistic and Contamination Free Evaluation of Large Language Models for Code](https://mlsanity.com/paper/2403.07974/) (2024)
- [LongBench: A Bilingual, Multitask Benchmark for Long Context Understanding](https://mlsanity.com/paper/2308.14508/) (2023)
- [τ-bench: A Benchmark for Tool-Agent-User Interaction in Real-World Domains](https://mlsanity.com/paper/2406.12045/) (2024)
- [RULER: What's the Real Context Size of Your Long-Context Language Models?](https://mlsanity.com/paper/2404.06654/) (2024)
- [GAIA: a benchmark for General AI Assistants](https://mlsanity.com/paper/2311.12983/) (2023)
- [Measuring Coding Challenge Competence With APPS](https://mlsanity.com/paper/2105.09938/) (2021)
- [Evaluating Very Long-Term Conversational Memory of LLM Agents](https://mlsanity.com/paper/2402.17753/) (2024)
- [LongMemEval: Benchmarking Chat Assistants on Long-Term Interactive Memory](https://mlsanity.com/paper/2410.10813/) (2024)
- [GSM-Symbolic: Understanding the Limitations of Mathematical Reasoning in Large Language Models](https://mlsanity.com/paper/2410.05229/) (2024)
- [LongLLMLingua: Accelerating and Enhancing LLMs in Long Context Scenarios via Prompt Compression](https://mlsanity.com/paper/2310.06839/) (2023)
- [LongBench v2: Towards Deeper Understanding and Reasoning on Realistic Long-context Multitasks](https://mlsanity.com/paper/2412.15204/) (2024)
- [∞Bench: Extending Long Context Evaluation Beyond 100K Tokens](https://mlsanity.com/paper/2402.13718/) (2024)
- [Towards AI-Complete Question Answering: A Set of Prerequisite Toy Tasks](https://mlsanity.com/paper/1502.05698/) (2015)
- [CRUXEval: A Benchmark for Code Reasoning, Understanding and Execution](https://mlsanity.com/paper/2401.03065/) (2024)
- [MT-Bench-101: A Fine-Grained Benchmark for Evaluating Large Language Models in Multi-Turn Dialogues](https://mlsanity.com/paper/2402.14762/) (2024)
- [BABILong: Testing the Limits of LLMs with Long Context Reasoning-in-a-Haystack](https://mlsanity.com/paper/2406.10149/) (2024)
- [MultiChallenge: A Realistic Multi-Turn Conversation Evaluation Benchmark Challenging to Frontier LLMs](https://mlsanity.com/paper/2501.17399/) (2025)
- [CLUTRR: A Diagnostic Benchmark for Inductive Reasoning from Text](https://mlsanity.com/paper/1908.06177/) (2019)
- [NoLiMa: Long-Context Evaluation Beyond Literal Matching](https://mlsanity.com/paper/2502.05167/) (2025)
- [HELMET: How to Evaluate Long-Context Language Models Effectively and Thoroughly](https://mlsanity.com/paper/2410.02694/) (2024)
- [Michelangelo: Long Context Evaluations Beyond Haystacks via Latent Structure Queries](https://mlsanity.com/paper/2409.12640/) (2024)
- [LeetCodeDataset: A Temporal Dataset for Robust Evaluation and Efficient Training of Code LLMs](https://mlsanity.com/paper/2504.14655/) (2025)
- [From f(x) and g(x) to f(g(x)): LLMs Learn New Skills in RL by Composing Old Ones](https://mlsanity.com/paper/2509.25123/) (2025)
- [MathFusion: Enhancing Mathematical Problem-solving of LLM through Instruction Fusion](https://mlsanity.com/paper/2503.16212/) (2025)
- [The SIFo Benchmark: Investigating the Sequential Instruction Following Ability of Large Language Models](https://mlsanity.com/paper/2406.19999/) (2024)
- [MTR-Bench: A Comprehensive Benchmark for Multi-Turn Reasoning Evaluation](https://mlsanity.com/paper/2505.17123/) (2025)
- [LOCA-bench: Benchmarking Language Agents Under Controllable and Extreme Context Growth](https://mlsanity.com/paper/2602.07962/) (2026)
- [REST: Stress Testing Large Reasoning Models by Asking Multiple Problems at Once](https://mlsanity.com/paper/2507.10541/) (2025)
- [h1: Bootstrapping LLMs to Reason over Longer Horizons via Reinforcement Learning](https://mlsanity.com/paper/2510.07312/) (2025)

## Abstract (arXiv)

We introduce ARBIGRAPH, a benchmark generator for evaluating whether tool-assisted language agents can retain, update, compose, and discard task-relevant context across extended reasoning workflows. ARBIGRAPH represents each task as a natural-language problem with an executable Python solver, and composes tasks through typed intermediate states, instantiated here as scalar and list values. This design enables controllable task graphs whose length, dependency structure, distractor count, and value type can be varied while preserving exact automatic verification. We instantiate ARBIGRAPH with math, GSM-style word-problems, and Python-tracing task categories, and evaluate a Qwen3.5-27B tool-assisted agent across four topologies. The results show high accuracy on isolated tasks but substantial degradation on more complex dependent tasks: accuracy drops by up to 33.3% on branching chains of dependent math tasks. This shows that ARBIGRAPH exposes failures that are not visible from single-task evaluation alone. Our code, generated datasets, and evaluation results are available at https://github.com/pavelgolikov/ArbiGraph.git