acceptodds
Under review as a conference paper at ICLR 2027

Error-Propagation-Aware Routing with Adaptive Horizons for Multi-Model LLM Agent DAG Execution

Abstract

AI agents increasingly execute multi-step workflows whose subtasks vary in difficulty and are connected by complex dependencies. Recent LLM-routing approaches reduce cloud cost by selecting models at the subtask level. However, none of these approaches jointly considers error propagation across dependent subtasks, dynamically controls how long routing decisions remain in effect, and concurrently executes runnable subtasks, which form a frontier. We present PARA, an Error-Propagation-Aware Routing framework with Adaptive horizons for multi-model LLM agent DAG execution. PARA represents each request as a subtask DAG and concurrently executes the subtasks in each frontier. At each routing point, PARA jointly determines a model allocation scheme and an adaptive commitment horizon—the number of consecutive frontier waves for which the routing decision remains in effect before being reconsidered. This adaptive horizon balances routing overhead against the need to respond to evolving execution states and error propagation. Across seven benchmarks, PARA reduces cloud cost by 68.50% and end-to-end latency by 43.15% relative to all-cloud execution while remaining within 1.71–6.75 points of its task quality. Compared with the original HybridLLM and Router-R1 baselines and Minions, PARA improves average score by up to 15.02 points while reducing average latency and cloud cost by up to 46.06% and 41.51%, respectively.

Primary area:
infrastructure, software libraries, hardware, systems, etc.
Keywords:
LLM Agents, Multi-Model Routing, LLM–SLM Collaboration, Agent Orchestration, Efficient AI Inference

Reviews

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

The paper presents PARA for executing agent tasks over a pool of local and cloud language models. A planner decomposes a request into a dependency DAG, and an RL router chooses model preferences for subtask types together with a commitment horizon. Runnable subtasks execute in parallel. At the next commitment boundary, the planner updates the remaining graph using completed outputs. The motivation is to balance routing overhead against the need to respond to upstream errors. Across seven benchmarks, the paper reports 68.50% lower cloud cost and 43.15% lower latency than all-cloud execution, with some loss of task quality, and improvements over several routing baselines.

Critical strengths
  1. Sharing model preferences across subtask types and reconsidering them after several execution waves is a sensible way to control routing overhead. The paper treats model selection as a decision made during workflow execution, which is more appropriate for dependent subtasks than choosing one model for the whole request.

  2. The evaluation reports task quality alongside latency and cloud cost, and includes training-matched HybridLLM and Router-R1 controls. This makes the efficiency comparisons more informative than comparisons with the original baseline configurations alone.

Critical weaknesses
  1. The paper repeatedly emphasizes error propagation, but does not show clearly what the router learns about it beyond using upstream outputs as part of its state. The motivating analysis labels error and recovery relative to a cloud-model reference. Deterministic checks are used where available, but free-form outputs can differ while both are valid, making the irrecoverable label difficult to interpret. The missing-edge repair experiment supports correcting graph dependencies, but offers less direct evidence for the claimed behavior of the routing policy.

  2. The most relevant comparison is missing. The paper identifies Division of Thoughts as the closest structural work, yet does not evaluate it. Comparisons with methods that use different execution structures do not fully establish the routing advance over existing DAG methods. The horizon study also compares adaptation only with reconsidering after every wave or never reconsidering. A reasonable finite fixed horizon seems necessary to judge how much the learned horizon adds.

The writing in this paper omits context needed for human readers, while creating unnecessarily long, repetitive basic claims and presenting long lists of experimental numbers with little interpretation.

Questions for authors
  1. How does PARA compare with DoT using the same executor models and task setup?

  2. Could a finite fixed horizon chosen on validation tasks recover most of the latency and cost savings? Table 5 only compares the learned policy with the two endpoint choices.

  3. Could the authors walk through a case where the policy responds to an upstream error? Since completed outputs are preserved, how does replanning deal with an incorrect cached result that later subtasks depend on?

  4. Has the error categorization in Section 2 been checked against independent correctness judgments for a sample of free-form intermediate outputs? In particular, how are different but valid local and cloud answers distinguished from errors?

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

This paper presents PARA, a framework for efficiently executing LLM agent workflows across local and cloud models. PARA represents each request as a directed acyclic graph of dependent subtasks and addresses the risk that errors in intermediate outputs propagate to downstream steps. Its router jointly selects model preferences for different task types and an adaptive commitment horizon. Independent subtasks execute concurrently, and the remaining workflow is replanned at commitment boundaries using cached outputs. The router is trained through supervised fine-tuning followed by reinforcement learning to balance final task quality against cloud cost. Across seven benchmarks, PARA reports 68.50% lower cloud cost and 43.15% lower latency than executing every subtask with a cloud model, with a mean benchmark score of 80.99 versus 84.84.

Critical strengths
  • I like the fact that the quality–efficiency tradeoffs are shown in this paper. Across seven benchmarks, PARA reports 68.50% lower cloud cost and 43.15% lower latency than All-LLM, with mean score decreasing from 84.84 to 80.99. Including planner, router, and synchronization overhead in latency makes the comparison more practically informative.
  • Also comprehensive ablation study supports the architectural choices well. The ablations cover SFT vs. GRPO, task-type vs. per-node routing, fixed vs. adaptive horizon, and parallel vs. sequential scheduling. Adaptive horizons reduce latency by 25.83% versus rerouting every wave, at a cost of only 0.85 score points. Task-type routing stays within 0.63 points of per-node routing while reducing latency by 20.01%. Parallel execution provides a 1.64× speedup, and GRPO adds 6.25 score points over supervised training alone.
  • Story telling wise, I like the paper separates intrinsic model difficulty from failures caused by incorrect upstream outputs. Its distinction between robust, recoverable, and irrecoverable executions helps explain why switching to a stronger model may sometimes be insufficient. This gives the routing problem a concrete empirical motivation.
Critical weaknesses
  • My the biggest concern is that the experiments do not establish whether PARA’s gains come specifically from handling error propagation. The router receives dependency context and intermediate outputs, but learns end-to-end. Nothing in the method explicitly estimates propagation risk. And there is no ablation removes the dependency or depth context from the router state. It is highlighted in the paper title and it needs more experiments around it.
  • Another concern is about the performance itself. From table 3, I can see that GPT-5 Direct (no DAG, no routing) averages 85.66 against PARA's 80.99. Its latency is 22.69 s against 20.59 s, and its normalized cost is 43.45 against 31.50. So DAG decomposition itself loses accuracy. The texts frame everything relative to All-LLM, which is a weaker reference than Direct. Some discussions should be added around this.
Questions for authors
  • Can we have more comparison against DoT and ToolOrchestra (I know these baselines weren't run)
Reviewer_kyiJOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

The paper targets cost-efficient execution of multi-model LLM agent workflows. A request is decomposed into a subtask DAG; a scheduler exposes the currently runnable frontier and executes it in parallel; and an LLM router (Qwen3-4B, SFT-initialised on GPT-5-generated trajectories, then trained with GRPO) emits two coupled decisions at each routing point: a task-type-conditioned model-preference matrix P_t ∈ R^{|T|×|M|} over six task types (T = {Retrieve, Transform, Math, Code, Reason, Synthesize}), and a commitment horizon h_t — the number of frontier waves for which that allocation is reused before the remaining DAG is re-planned from cached outputs. The reward is terminal task score minus α = 0.7 times accrued cloud cost (Eq. 2). The paper contributes (i) a measurement study separating intrinsic model error (ME) from Robust / Recoverable / Irrecoverable outcomes under noisy parent inputs, including an IRC rate conditioned on dependency depth ≥ 3 (Table 2); (ii) the PARA framework combining task-type routing, adaptive horizons, and concurrent frontier execution; and (iii) a seven-benchmark, two-model-pool evaluation against All-SLM, All-LLM, Random, HybridLLM, Router-R1, Minions, GPT-5 Direct and GPT-5 ReAct, plus ablations over training, allocation granularity, horizon and scheduler.

Critical strengths

S1. The failure taxonomy in Section 2.3 is a genuine, reusable diagnostic that prior routing work lacks. Table 2 decomposes node outcomes under noisy parent inputs with crisp operational definitions — "Recoverable (RC), where the SLM differs but the LLM matches; and Irrecoverable (IRC), where both differ" — and the three-way split is internally coherent (e.g. HotpotQA 56.4 + 24.1 + 19.5 = 100). The depth-conditioned column separates "escalate this node" from "the upstream context is broken", which is exactly the distinction a propagation-aware router needs and which, as far as the cited literature shows, the request-level and subtask-level routing work does not make. This is consequential because it is the one piece of the paper that would survive as an independent contribution: it is directly reusable as a profiling tool for anyone building a DAG-level router, independently of whether PARA's particular policy works.

S2. The system-level evaluation is real, internally consistent, and contains one cleanly isolated mechanism result. The numbers are not a modelled summary: I recomputed the headline arithmetic from Table 3 (All-LLM 84.84 / 36.22 s / 100.00; PARA-pool 80.99 / 20.59 s / 31.50) and obtained 68.50% cost, 43.15% latency and 87.49% of the All-SLM→All-LLM gap, the last matching the paper's own "87.50%" to rounding; Table 4's +13.34 / +10.44 / +6.74 deltas and Table 5(d)'s per-benchmark GRPO deltas also reproduce from their own component tables. The frontier-parallelism ablation is isolated from the policy entirely — "Parallel frontier execution reduces latency from the sequential scheduler's 33.74 s to 20.59 s, a 1.64× speedup" while "maintaining similar task score and cloud cost" (Table 5(a): 80.61 vs 80.99). This is consequential because consistent two-decimal agreement across eight tables is what separates a real end-to-end system evaluation from a fabricated one, and the 1.64× result is a mechanism-level claim that stands on its own regardless of the routing story.

Critical weaknesses

W1. The "state-of-the-art" claim is refuted by the paper's own Table 3, and the baseline suite is both dominated by a trivial baseline and applied outside the regimes its sources evaluate. (a) The claim. The abstract states "Compared with the state-of-the-art methods, PARA improves average score by up to 15.02 points", and Section 4.2 defines that comparison as HybridLLM, Router-R1 and Minions. Those are not the strongest rows in Table 3: PARA (pool) averages 80.99, while GPT-5 Direct averages 85.66 (22.69 s, Ca 43.45) and GPT-5 ReAct averages 85.73. Recomputing per benchmark from Table 3, PARA is below GPT-5 Direct on six of seven benchmarks — HotpotQA −7.05, GSM8K −2.25, DROP −4.75, HumanEval −7.31, MATH −9.52, ToolBench −5.81 — and wins only FRAMES (+4.00); it is below All-LLM on all seven. The abstract's "up to 15.02 points" is therefore a maximum taken over the three weakest comparators while the two strongest sit in the same table. (b) The baselines are not running where their source papers run. Every routing baseline, including the "matched" variants that "share the same 16K SFT requests, GRPO rollout budget, executor pool, and validation-based operating-point selection" (Section 4.1), scores below a single GPT-5 call: Router-R1 (matched) 77.88 and HybridLLM (matched) 73.50 are 7.78 and 12.16 points below GPT-5 Direct's 85.66 on the seven-benchmark mean, and on HotpotQA the pair is 74.09 vs 83.97. In Router-R1's own report the router beats the largest single model in the pool (+7.8 average EM points; 0.449 vs 0.416 F1 on HotpotQA), so the relative ordering is inverted here [public source: Router-R1, arXiv:2506.09033, Tables 2–3]. I note that the absolute magnitudes are not comparable across the two settings — Router-R1's pool tops out at Mixtral-8x22B and its main runs use cost coefficient α = 0.0 with at most 4 routing rounds — so this may be a regime mismatch rather than a broken re-implementation. It is nevertheless the authors' burden to report the configuration and show the inversion is not an artifact. The same problem affects Minions: its published evaluation is long-document QA (FinanceBench, LongHealth, QASPER) at 5.7×–30.4× cloud-cost reduction [public source: Minions, arXiv:2502.15964], whereas Table 3 reports Minions on HumanEval, MATH, ToolBench and FRAMES, with no description anywhere of how the chunk-decomposition protocol was adapted to code generation or tool use. And the closest structural prior work is absent altogether: "DoT (Shao et al., 2025) is closest structurally" (Section 5), yet DoT appears in neither Table 3, Table 4 nor Table 5. (c) No cost-matched control, and the omitted method's published operating point is at least as good. At PARA's budget (Ca 31.50, 20.59 s) the natural control is one strong model with only a fraction of requests going to the cloud, or with self-consistency; this is not run. Meanwhile DoT — which also builds a dependency graph, executes same-depth subtasks in parallel, and routes between a local SLM and a cloud LLM — publicly reports an 83.57% cloud-cost and 66.12% latency reduction at "comparable reasoning accuracy" [public source: DoT, arXiv:2502.04392, §5.2 / Table 1], against PARA's 68.50% and 43.15% at a 3.85-point accuracy loss. The settings differ (GPT-4o and Llama-3-8B vs GPT-5 and a four-SLM pool), so this is not a head-to-head result and I do not treat it as one; but on the one overlapping benchmark where both report a delta versus cloud-only, the sign differs — DoT reports DROP +5.59 points, while I recomputed PARA's DROP gap from Table 3 as −2.68 (91.72 → 89.04). This is consequential because it is the difference between "PARA advances the state of the art" and "PARA occupies a point on a Pareto curve that a one-line baseline already dominates on quality and that a cited, structurally identical method may already dominate on cost", and the abstract currently claims the former while declining to test either.

W2. Neither of the two mechanisms the paper is named for is instantiated, and one is contradicted by the paper's own ablation. (a) Error propagation is never operationalised. The router observes "the request, DAG topology ..., current frontier, summaries of completed outputs, model executor profiles φ(m) and token prices" (Section 3.2); nothing in that state is an error or propagation estimate, and the reward R = r_succ − α Σ_t ΔCost_t (Eq. 2) has no propagation term. The ME / RB / RC / IRC quantities computed in Section 2.3 never reappear at routing time, in training, or in any table of Section 4; the entire link is one sentence in Section 2.4 ("Insight 2 motivates a router that accounts for both the current node and upstream execution state"), which amounts to "the policy can read cached upstream text". Correspondingly, Table 5 contains no condition that removes propagation information — no request-plus-topology-only state, no per-node IRC estimate — so the title claim has no test. (b) The adaptive horizon is a cost dial, not a propagation mechanism. Section 2.3 argues the horizon should "shorten commitments before irrecoverable errors propagate", but Table 5(a) shows quality decreasing monotonically in horizon length: Fixed h = 1 scores 81.84, Adaptive horizon 80.99, Fixed h = ∞ 66.26. Section 4.4 reports this honestly ("with scores of 80.99 and 81.84, respectively") but never reconciles it, and there is no analysis of when h_t is chosen or whether it correlates with dependency depth or IRC risk. (c) The replanning confound is not isolated. h = ∞ collapsing to 66.26 (−18.6 vs All-LLM's 84.84) shows that boundary re-planning from cached outputs, not routing, does most of the work; but no ablation holds re-planning fixed while routing everything to the cloud, so the 1.71–6.75 point gap to All-LLM conflates routing gains with re-planning gains. This is consequential because the paper's identity — the title, the abstract's three-part "jointly considers" claim, and the measured contamination argument in Section 2 — rests on these two mechanisms, and as written a reader cannot tell whether PARA is a propagation-aware router or a re-planner with a cost-aware model picker attached.

(Deliberately not listed as critical, but relevant to the recommendation: no score anywhere has a confidence interval, seed count or significance test, and the evaluation-set size per benchmark is never stated; Table 5(d) reports GRPO−SFT deltas to two decimals from what appears to be a single A100 run; Appendix B.1's "350 request pairs" is "50 requests per benchmark and five repeats per request", i.e. pseudo-replication, so its "[0.001, 0.253] s" interval is understated by roughly √5; Table 8 reports a constant score of 82 while Ca varies 30.21 / 29.38 / 31.15 across cloud-concurrency caps, which should not change total tokens, and gives latencies as "T(c) = 11.85 + 9.60/c" rather than measurements; Table 6's caption calls its numbers "whole-benchmark scores" while Section B.1 refers to "50 requests per benchmark"; and no code, checkpoint, planner prompt or data release is promised.)

Questions for authors
  1. Cost-matched control and the baseline inversion (W1a, W1c). At PARA's budget (Ca 31.50, 20.59 s), what does a budget-matched GPT-5 baseline achieve — a query-level cascade, or direct GPT-5 with self-consistency — and does it match or exceed 80.99? Separately, Router-R1's own report has the router beating the largest single model in its pool, whereas your Router-R1 (matched) sits 9.88 points below GPT-5 Direct on HotpotQA (74.09 vs 83.97). Please state the configuration you used (pool ceiling, cost coefficient, routing rounds, aggregation) and whether the inverted ordering is a deliberate consequence of the DAG scheduler rather than the method.

  2. DoT (W1b, W1c). Section 5 calls Division of Thoughts "closest structurally"; it also builds a dependency graph and executes same-depth subtasks in parallel, i.e. it occupies very nearly PARA's problem setting, and it reports an 83.57% cloud-cost / 66.12% latency reduction at comparable accuracy on its own benchmarks. Can you run DoT under the same planner, scheduler, executor pool and 16K SFT budget and add it to Table 3, and report the DROP comparison directly? On DROP it reports +5.59 points versus cloud-only, whereas your Table 3 shows PARA 2.68 points below All-LLM.

  3. Minions (W1b). Minions' published evaluation is FinanceBench, LongHealth and QASPER long-document QA. Table 3 reports Minions on HumanEval, MATH, ToolBench and FRAMES. Please describe the adaptation of its chunk-decomposition protocol to code generation and tool use, and state whether it was tuned for these benchmarks.

  4. Where propagation lives (W2a). Which element of the state or reward encodes the risk that an upstream error becomes irrecoverable, as opposed to merely making upstream text visible? Please add an ablation in which the router sees only the request and DAG topology (no "summaries of completed outputs") and report the score/cost delta. If that ablation is null, the title should be changed.

  5. Horizon behaviour and the replanning control (W2b, W2c). Please report the empirical distribution of h_t (histogram, mean, fraction at h_t = 1) and its correlation with frontier index, dependency depth and the IRC@Depth≥3 statistic. If quality is highest at h = 1 (81.84 vs 80.99), in what sense is the horizon propagation-aware? Also add "same planner + boundary re-planning + All-LLM" to Table 5 to separate re-planning gains from routing gains.

  6. Statistics, splits and reproducibility (noted above). For each benchmark, report the evaluation-set size, repeats and a 95% interval on every score cell, and give at least three GRPO seeds for the Table 5(d) deltas. Either recompute Table 7 from per-request paired samples (n = 50, not 350) or remove it, and explain why Ca moves between cloud-cap 1/2/4 in Table 8 at an identical score. Finally, are the "16K requests: 8K HotpotQA (50%), 4K GSM8K (25%), and 4K APPS (25%)" router-SFT requests, the 1,000-request task-tagging sample and the α-selection validation set disjoint from all seven evaluation sets? Please also give H_max, the units of r_succ and ΔCost (α = 0.7 is unreconstructable without them), model version dates, and the Pool-A→Pool-B model-slot mapping with absolute Pool-B scores.

Criteria under which my score would rise: a cost-matched strong-model control, DoT and a corrected Router-R1 configuration in the main table, and a re-statement of the contribution as a cost/quality Pareto result rather than a SOTA claim (W1); plus a state ablation that removes propagation information and a horizon analysis showing h_t tracking IRC risk, together with the "same planner + re-planning + All-LLM" control (W2). Per-cell confidence intervals, ≥3 GRPO seeds, an explicit train/eval disjointness statement and raw data behind Tables 7–8 would remove the remaining soundness concerns. Meeting (1)–(5) would move me to 3 (weak acceptance); the current manuscript does not let me verify either headline claim.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.