acceptodds
Under review as a conference paper at ICLR 2027

ArbiGraph: Composing Arbitrary Verifiable Tasks for Agent Evaluation

Abstract

Language model agents must often solve a sequence of problems and retain earlier answers as the workflow grows. Evaluating problems one at a time does not show how well agents retain and use earlier answers. To evaluate this ability, we intro- duce ARBIGRAPH, a framework for generating benchmark instances that combine problems with verifiable answers into graphs of dependent tasks. Each task is a problem, and each connection specifies an earlier answer that the agent must report to obtain the next problem’s input. An incorrect report returns an alternative input whose verified answer differs from the intended answer. This mechanism sup- ports tasks from different domains without requiring conversions between their input and output types. We test the framework with math problems and tasks that ask agents to predict the output of Python code. We evaluate three models on the same problems both in isolation and in three topologies, each containing 18 tasks. We construct an independent-error baseline by multiplying the isolated accuracies of the final task and all tasks it depends on. Averaged across the three topologies and the math and Python categories, measured accuracy falls below this baseline by 45.0 percentage points for Gemma-4-31B-it, 35.6 for Qwen3.8-27B, and 11.0 for GPT-OSS-120B. These additional losses indicate that solving problems within a larger workflow adds difficulty beyond the accumulation of errors on isolated problems. We also study how graph structure affects accuracy on the final task while keeping the number of tasks fixed.

Primary area:
datasets and benchmarks
Keywords:
LLMs, agents, agentic eval, benchmarks

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_Ty2XOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduces ArbiGraph, a framework for generating benchmark instances that compose arbitrary verifiable tasks into DAG-structured workflows for agent evaluation. The core mechanism is answer-gated input access: to obtain a task's input, the agent must report the answers of its parent tasks via a get_input tool; only if all reported answers are correct does the tool return the intended input, otherwise it returns an alternative valid input whose verified answer differs. This design allows heterogeneous tasks to be composed without I/O type matching or hand-written adapters, while keeping every node's intermediate answer independently verifiable, preventing conversions (e.g., rounding) from masking errors, and preserving difficulty control. The framework also exposes an RLVR interface (no training is performed).

Critical strengths

It decouples task composability from I/O type compatibility, replacing adapters with report checking plus alternative inputs whose verified answers differ from the intended one. This enables tasks from different domains to be composed into arbitrary DAG topologies while retaining per-node verifiability and error traceability. It also avoids the error-masking problem of conversion-based composition, where rounding, for example, can map a wrong parent answer to the same child input; the paper shows this to be a real flaw in prior approaches such as RACES and Composition-RL. This point is consequential to my assessment because the community currently lacks a way to vary dependency structure while holding the difficulty of individual problems fixed. Combined with per-node verification records and an RLVR interface, the mechanism has the potential to become shared infrastructure rather than a one-off benchmark.

The paired designs (the same problems are reused across topologies, and the shuffled braid changes only task numbering, not problems or edges), the bootstrap intervals for the independent-error baseline, the Wilson intervals for measured accuracy, and the per-node failure localization together reflect above-average statistical and experimental discipline. In particular, the observation that most failures begin at a node that received its intended input, and that even root-node accuracy degrades once a problem is placed inside a larger workflow, extends the self-conditioning and long-horizon degradation results of Sinha et al. into the compositional-task setting. This constitutes substantive evidence supporting acceptance, rather than merely constituting yet another benchmark.

Critical weaknesses

Root-node accuracy degrades even at nodes with no dependencies whatsoever, and topology (edge structure) has no consistent effect on target accuracy. Together these strongly suggest that a large fraction of the headline loss may stem from generic interference caused by presenting many problems in one prompt within a long context, rather than from dependency composition itself. The paper lacks a REST-style control, in which the same tasks are presented in a single prompt, solvable independently, and without get_input gating, that would decompose these two effects. This is consequential: if most of the loss does not come from dependency structure, the paper's central empirical claim reduces to a reconfirmation of known long-context and multi-task degradation phenomena in the line of REST and RULER, leaving the engineering framework as the main contribution. The Limitations section acknowledges this gap but provides no ablation.

(a) Only three mid-size open-weight models are tested, and the strongest model loses the least by a wide margin, which suggests the phenomenon may fade rapidly with model capability; the absence of frontier models leaves the implicit claim that this benchmark will remain discriminative for the next generation of models entirely untested. (b) Tasks are filtered to those each model solves perfectly in isolation, so the results characterize only the easy-task regime; the mixed-category experiment reuses a handful of RLVE and HotpotQA tasks across all instances, offering little diversity. (c) The RLVR interface is listed as a contribution but is never validated by any training experiment. (d) The alternative-input mechanism silently swaps inputs when a report is wrong, so the agent is never told its report was incorrect and continues solving on the wrong branch; unlike real workflows where failed tool calls return error feedback, this design may artificially amplify error propagation, and the paper does not analyze sensitivity to this choice.

Questions for authors

Q1 Could you add a no-dependency control, in which the same tasks from each instance are presented jointly in the prompt, solvable independently, and without get_input gating, to decompose how much of the additional loss comes from dependency structure versus from the multi-task context itself? This result directly determines whether the paper's central finding is incremental over prior work such as REST or a replication of known phenomena.

Q2 When a report is wrong, get_input silently returns an alternative input, giving the agent no signal that its report was incorrect. How sensitive are the results to this design choice? If the tool instead returned explicit error feedback, allowing corrections within the existing per-node request limit, would the additional loss remain significant? This bears on whether the framework measures compositional ability under realistic feedback or error propagation in a no-feedback setting.

Q3 The task-selection filter retains only tasks that each model solves on all screened inputs"which systematically excludes tasks at the boundary of each model's ability. Does the direction and magnitude of the additional loss hold on an unfiltered or relaxed task pool? If the conclusions hold only for tasks that are near-ceiling in isolation, the claims in the main text should be explicitly scoped to that regime.

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

The paper composes problems with verifiable answers into a graph of dependent tasks and studies whether an agent solves problems worse inside a workflow than in isolation. Instead of passing a parent's answer into the child as its input, each node keeps a fixed problem and the agent reports the answers to the tasks it depends on: if all reports are correct the tool returns the intended input, otherwise it returns an alternative input whose verified answer differs, so a wrong reported answer cannot yield a correct-looking result. They evaluate three open-weight models (Qwen3.8-27B, GPT-OSS-120B, Gemma-4-31B-it) and compare measured accuracy to an independent-error baseline formed by multiplying the isolated single-task accuracies.

Critical strengths
  1. In direct composition a conversion can turn both a correct and an incorrect parent answer into the same input for the next task, hiding the upstream error. ArbiGraph checks the reported answers before supplying an input: an incorrect report returns an alternative input with a different verified answer, so a wrong report cannot produce a correct-looking target.
  2. Because earlier answers are checked before an input is supplied rather than computed by upstream tasks, each problem keeps its original input and answer format, and magnitudes and sequence lengths do not grow across tasks.
Critical weaknesses
  1. The comparison is between a single task and an 18-node instance, which changes the number of listed tasks and the retained reasoning from earlier tasks at the same time as the dependency edges; the abstract attributes the loss to "solving problems within a larger workflow." Its own data points the other way: the root, which has no parents, still drops from 98.4% alone to 92.9% in math, and 78–100% of failed instances first go wrong at a node that received its intended input. The paper lists varying "what the context contains, such as the number of listed tasks," as future work rather than running it.
  2. ArbiGraph supports math, Python tracing, RLVE, and HotpotQA, but the workflow experiments use only 18 math or 18 Python tasks. RLVE and HotpotQA appear only as a minority of replaced nodes in the mixed-category instances, and HotpotQA single-node accuracy is 30% to 40% under joint exact match, so no instance is dominated by the categories that most need conversion between input and output types.
Questions for authors
  1. The independent-error baseline multiplies the single-task accuracies and so assumes no context load at all, while the 18-node instance carries both context load and dependency edges, so the reported loss conflates the two. Suggested experiment: run the same 18 tasks in one prompt but with no dependency edges — every node then issues an empty get_input call and receives its intended input directly, as root nodes already do — and report its loss below baseline; the part of the reported loss it reproduces is context load, and only the remainder is attributable to composition.
  2. The workflow experiments use only math and Python, the categories least in need of conversion between input and output types, so the generality claim is not measured. Suggested experiment: run an instance whose nodes come mostly from RLVE or HotpotQA and report its loss below baseline — if the weakest category's single-node accuracy drives target accuracy to near zero, that bound on generality is itself a result worth reporting.
Reviewer_m9UWOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
3
Soundness
1
Read review
Paper summary

The paper introduces ArbiGraph, which is a framework for generating benchmark problems that combine multiple verifiable tasks. The authors use their framework on math and python tasks and test 3 open source models. They find that introducing these dependencies seemingly introduces additional challenges beyond the accumulation of errors.

Critical strengths
  • The paper is well motivated: real world applications often require solving multiple related tasks. Automating the generation of problem instances that automatically combine such tasks into a single benchmark problem is an interesting idea that could help reusing existing benchmarks for future evaluations.
  • The selection of the three different models in the evaluation seems reasonable.
  • The experiment on unnecessary task completion is quite interesting.
  • The overall presentation is good.
Critical weaknesses
  • It is unclear to me why the authors do not include more tasks from existing benchmarks for their evaluation. There are numerous benchmarks for mathematics and code, yet the authors select a specific subset of LeetCode problems and math tasks that are "selected by hand" (l. 194).
  • The choice of topologies is not sufficiently justified.
  • The authors compute in section 4.1 the performance on individual tasks. Another very natural baselines would be to give the model all 18 tasks including the correct inputs and ask it to solve all tasks. Given that model performance is known to drop with increased context length, it is not a priori clear that a model solving all 18 tasks can perform as good as the "independent error baseline" suggests.
  • The authors state that their framework allows for the composition of arbitrary tasks. However, in practice, workflows are particularly relevant when combining related tasks. For example, a math task might first require constructing a numerical counterexample before formalizing the result in Lean. Such dependencies are ubiquitous, yet they are not studied in the paper.
Questions for authors
  • Could the authors provide a more detailed failure mode analysis?
  • Could the authors test the baseline where a model has to solve all 18 tasks given the correct inputs for all tasks?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.