CB-Orchestrator: Adaptive Workflow Optimization for LLM Agents via Contextual Bandits

• Task-level optimization fixes one workflow, while query-level optimization generates anew for each input; neither effectively reuses high-quality workflows.Workflow effectiveness varies by query, so a fixed workflow may be too heavy for simple cases or insufficient for complex ones; generating from scratch is a difficult program-synthesis problem.Source: §1 · pp. 1–2
• CB-Orchestrator constructs a diverse workflow pool via execution-guided evolutionary search, then learns a query-conditioned contextual-bandit policy for sample-efficient selection.The bandit formulation balances exploration and exploitation while reducing the workflow evaluations needed to learn a strong policy.Source: §1 · p. 2
• The paper formalizes adaptive workflow reuse as learning a query-conditioned routing policy over a reusable pool, rather than deploying a fixed workflow or generating one per query.Source: §1 · p. 2
• Across five benchmarks, CB-Orchestrator consistently improves over strong baselines; on MATH, it reduces training-phase token overhead by ≥40.55% and end-to-end training overhead by ≥29.73%.Source: §1 · p. 2

2.1 AGENTIC WORKFLOWS AND AUTONOMOUS AGENTS

• Agentic workflows structure model and tool calls, sometimes iteratively using feedback (Self-Refine; Reflexion); autonomous agents maintain state and choose actions online.Source: §2.1 · pp. 2–3

2.2 AUTOMATED WORKFLOW OPTIMIZATION

• Task-level systems optimize query-invariant workflows, whereas query-level systems construct or orchestrate workflows per input; this paper instead studies adaptive reuse and selection.Other work optimizes inter-agent graphs (GPTSwarm; G-Designer (Zhang et al., 2025c)) or supernet distributions (MaAS (Zhang et al., 2025b)).Source: §2.2 · p. 3

3.1 WORKFLOW REPRESENTATION AND PROBLEM FORMULATION

• A reusable pool of executable workflows replaces per-query generation: CB-Orchestrator learns a query-level policy to select a workflow that maximizes expected answer reward.Workflows are programs that orchestrate LLM calls and tool invocations; queries are split into training and test sets.Source: §3.1 · pp. 3–4

3.2 STAGE 1: WORKFLOW POOL CONSTRUCTION

• Stage 1 generates workflows from seed queries, evolves failed ones using execution feedback, and transfers successful workflows from similar queries when evolution fails.Pool construction targets validity and coverage of training queries; completeness is a design goal, with measured coverage reported in the appendix.Source: §3.2 · p. 4

3.3 STAGE 2: CONTEXTUAL BANDIT SELECTION

• The contextual bandit treats query embeddings as context, workflows as arms, and answer quality as bounded reward, assuming semantic similarity and smooth expected rewards.The paper also assumes expected reward is a function of joint query-workflow features and says these assumptions are empirically validated in Appendix D.Source: §3.3 · p. 4, §3.3.1 · pp. 4–5

3.3.2 FEATURE REPRESENTATION

• Queries and workflow source code are encoded separately with one frozen text embedder, then their L2-normalized embeddings are concatenated to represent compatibility.Workflow code summarizes its problem-solving strategy, including operator sequences and composition structure.Source: §3.3.2 · p. 5

3.3.3 HYBRID NEURAL-LINEAR ARCHITECTURE

• The hybrid UCB score combines neural reward prediction with a linear exploration bonus, whose uncertainty term proxies feature-space novelty under the smoothness assumption.The parameter α controls the exploration-exploitation trade-off; the uncertainty term is a practical proxy, not a direct estimate of reward variance.Source: §3.3.3 · p. 5

3.3.4 TRAINING ALGORITHM

• Training begins with uniform exploration, then selects the highest-scoring eligible workflow while avoiding repeated query-workflow evaluations and executing pairs in parallel batches.After each batch, rewards update the precision matrix and training buffer, and the reward predictor is reset and retrained.Source: §3.3.4 · p. 5, §3.4 · p. 6

3.4 STAGE 3: INFERENCE WITH ADAPTIVE SELECTION

• At inference, CB-Orchestrator selects the workflow with the highest predicted reward without an exploration bonus; confidence intervals filter workflows with too few trials or low success rates.An optional online mode adapts under distribution shifts and can expand the pool for queries outside its coverage.Source: §3.4 · p. 5

4.2 PERFORMANCE ANALYSIS

• 81.37% average score, surpassing MaAS by 1.58% and AFlow by 2.61%; CB-Orchestrator achieves the best performance across the reported math and code benchmarks.On GAIA, it achieves the highest average score of 21.0%, with a 28.6% solve rate on L1 tasks.Source: §4.2 · pp. 6–7, Table 1 · p. 7

4.3 COST EFFICIENCY AND TRAINING DYNAMICS

• At T = 800, CB-Orchestrator reaches 54.36% solve rate while reducing MATH training token cost by at least 40.55%, or 29.73% including one-time pool construction.At T = 400, it reaches 52.43% with about 4.28 million tokens; Figure 2 places the method on a superior Pareto front, with convergence before T = 800 and around round 650 in Figure 4.Source: Figure 2 · p. 7, §4.3 · pp. 7–8

4.4 ABLATION STUDY AND STRATEGIC ANALYSIS

• 68.96% average score with evolution versus 68.03% for Without Evolution; the authors describe bandit selection as the primary driver of adaptation and evolution as an additional refinement.The study evaluates variants on MATH and MBPP, including PureRandom, RandomNN, GreedyNN, LinUCB, NeuralUCB, and WithoutEvo.Source: §4.4 · p. 8
• All bandit variants significantly outperform PureRandom, while HybridUCB outperforms the baseline selection strategies; its exploration bonus matters more when duplicate evaluations are allowed.With duplicates, Ours scores 54.03% versus GreedyNN at 51.89%, a 2.14% gap compared with 1.24% without duplicates; the no-duplicate protocol itself forces some exploration.Source: §4.4 · pp. 8–9

4.5 GENERALIZABILITY AND SCALABILITY ANALYSIS

• Retraining the selector on GSM8K while retaining the source pool raises MATH performance to 54.94%, above the strongest baseline and the model trained on MATH.The authors also report that zero-shot transfer outperforms many baselines; they hypothesize that GSM8K's larger training set may provide richer selector feedback.Source: Table 2 · p. 9, §4.5 · p. 9
• With Llama-3.1-70B on MATH and HumanEval, CB-Orchestrator averages 64.24%, slightly exceeding MaAS and outperforming Vanilla by a large margin.The authors present this as evidence that the approach scales to open-source LLMs.Source: §4.5 · p. 9

4.6 CASE STUDY

• Two MATH cases show query-specific routing: the selector chooses different workflows for decimal-expansion and trigonometric-curve problems, and both answers are correct on the first attempt in all five test runs.On the related training problems, workflow 31 succeeds where workflow 3 fails in one case, and the reverse holds in the other.Source: §4.6 · p. 9

5 CONCLUSION

• Stage 1 builds a diverse workflow pool through execution-guided evolutionary search, and Stage 2 selects workflows using a contextual bandit with Hybrid Neural-Linear UCB.The selector explores query–workflow pairs sample-efficiently.Source: §5 · p. 9
• Across five benchmarks, CB-Orchestrator consistently outperforms strong baselines.On MATH, training-phase token overhead falls by at least 40.55% and end-to-end training overhead by at least 29.73%.Source: §5 · p. 9
• The authors present CB-Orchestrator as a practical path toward versatile, cost-efficient LLM agents across diverse real-world applications.They also cite its ability to incorporate prior knowledge into the workflow pool.Source: §5 · p. 10

A.1 DATASET STATISTICS

• Validation data supports Stage 1 workflow-pool construction and Stage 2 bandit training, while test data is reserved for Stage 3 inference.Table 3 summarizes the datasets used in the experiments.Source: §A.1 · p. 14, Table 3 · p. 14
• For GSM8K workflow-pool construction, the authors sample 100 training queries from the full training split.The sample also supports pool-coverage statistics.Source: §A.1 · p. 14

A.2 HYPERPARAMETERS

• Bandit training uses T = 1200 rounds for MATH, GSM8K, MBPP, and GAIA, and T = 500 for HumanEval.Table 4 summarizes the hyperparameters.Source: §A.2 · p. 14, Table 4 · p. 14

A.3 ARCHITECTURE AND FEATURE REPRESENTATION DETAILS

• The reward-prediction network is a 3-layer MLP with pre-norm design and progressive dimensionality reduction.Its embedding representation compresses from 2d = 5120 to 1, using d = 2560, d1 = 2048, and d2 = 64.Source: §A.3 · p. 15
• Workflow source code summarizes each strategy through its operator sequence, composition structure, and operator-specific parameters and prompts.Composition may be sequential, branching, or iterative.Source: §A.3 · p. 15
• At inference, Wilson score filtering requires at least five trials per workflow and retains the top 50% by score.The filter removes workflows with insufficient trials or consistently poor performance.Source: §A.3 · p. 15

A.4 ONLINE LEARNING MODE

• Optional online learning updates the selection model from observed rewards, with periodic retraining intended to adapt to query-stream distribution shifts.The paper links this adaptation to improved performance on recurring query patterns.Source: §A.4 · p. 15
• Low pool coverage combined with high uncertainty signals a likely missing strategy, triggering on-demand workflow generation from the query as a seed.A successful new workflow is added to the pool and its high initial uncertainty encourages later exploration; generation adds latency and cost.Source: §A.4 · pp. 15–16

A.5 WORKFLOW POOL COVERAGE AND TRAINING SUBSET

• MATH pool coverage is 72.3%, reflecting the difficulty of competition-level mathematics, while the bandit learns to select effective workflows for covered queries.Coverage is the fraction of Stage 1 training queries for which at least one pool workflow succeeds.Source: §A.5 · p. 16, Table 5 · p. 16
• Stage 2 trains on about 30 workflows because that subset provides sufficient diversity and more observations per arm under a fixed training budget.HumanEval uses all 31 available workflows; inference filtering also reduces the active set.Source: §A.5 · p. 16

A.6 COST BREAKDOWN AND ACCOUNTING

• Cost accounting includes all LLM calls, including workflow generation and evaluator calls, and counts tokens consumed by failed executions as well as input and output tokens.Table 7 breaks down input and output token consumption.Source: §A.6 · pp. 16–17, Table 7 · p. 17
• Excluding pool generation, CB-Orchestrator at T=800 reaches 54.36% solve rate with 5.55M tokens, reducing total token cost by 26.97% versus MaAS.The 0.59M-token MATH pool-generation cost is a one-time expense that can be amortized across deployments.Source: §A.6 · p. 17, Table 6 · p. 17

A.8 TRAINING DYNAMICS

• Figure 4 reports cumulative average reward during MATH bandit training and describes rapid convergence around Round 650.The caption interprets this as the policy learning effective workflow selection.Source: Figure 4 · p. 17

A.9 OPERATOR LIBRARY

• The operator library uses reusable atomic building blocks for common LLM interactions, and the MATH example composes decomposition, code-based solving, and LaTeX formatting.Experimental code is partly adapted from AFlow (Zhang et al., 2025d) and MaAS (Zhang et al., 2025b); Stage 1 generation and evolution prompts are provided.Source: §A.7 · p. 17, §A.9 · p. 18, §A.10 · p. 20

B.1 DESIGN RATIONALE AND THEORETICAL POSITIONING

• The hybrid design prioritizes stability and computational efficiency over theoretical optimality, and does not directly inherit neural-bandit regret bounds.Its exploration rationale combines reward smoothness with feature-space novelty, but the uncertainty score is not a calibrated predictor-error bound.Source: §B.1 · p. 25, §B.2 · p. 25

B.3 COMPARISON WITH NEURAL BANDITS

• The design avoids gradient computation and storage while keeping exploration stable and tunable, but its uncertainty may be less accurate when rewards are highly nonlinear in the original feature space.NeuralUCB underperforms the hybrid approach on this task in the reported comparison.Source: §B.3 · p. 26

B.4 SAMPLE-EFFICIENCY INTUITION

• A shared reward model learns from selected query–workflow pairs instead of exhaustively evaluating all nK possible pairs.The nK count describes the possible pairs, not a sample-complexity bound.Source: §B.4 · p. 26
• The joint query–workflow embedding shares information across pairs, while the precision matrix tracks feature-space coverage for the linear exploration bonus.Under the smoothness assumption, nearby embeddings may have similar expected rewards; the passage does not establish a finite-sample guarantee for the neural reward model or policy.Source: §B.4 · p. 26

B.5 COMPUTATIONAL COMPLEXITY AND SCALABILITY

• With embedding dimension 2d = 5120, the precision matrix requires about 100MB, and Cholesky solves reduce per-query complexity from O(d^3) to O(d^2).The Cholesky factor is recomputed once per batch after updating A, amortizing decomposition cost across B queries.Source: §B.5 · p. 26
• At d = 2560, K ≈30, T ≈1200, and B = 25, decomposition takes ∼0.5 seconds about 48 times, while per-round UCB computation takes ∼10ms.These costs are negligible compared with workflow execution, which takes seconds to minutes per query.Source: §B.5 · p. 26
• With K = 500 workflows, scoring all arms takes ∼150ms, while memory scales as O(d^2) and Cholesky decomposition as O(d^3).The precision matrix is independent of K, so a larger workflow pool increases per-round UCB computation linearly.Source: §B.5 · pp. 26–27
• Embedding dimensions of 1,024–8,192 are described as within the implementation’s efficient operating regime, and d = 2560 balances representational capacity with computational tractability.The experiments use d = 2560.Source: §B.5 · p. 27

C.1 LLM BACKBONE SCALABILITY RESULTS

• Table 12 reports CB-Orchestrator’s scalability results against Vanilla and MaAS using Llama-3.1-70B as the backbone.The supplied passage identifies the table and comparison scope but gives no numerical results.Source: §C.1 · p. 27, Table 12 · p. 27

C.2 ABLATION STUDY RESULTS

• Table 13 covers MATH and MBPP ablations of bandit selection strategies and the evolution process, including variants that allow duplicate query–workflow sampling.The supplied passages do not provide ablation values.Source: §C.2 · p. 27, Table 13 · p. 28

C.3 GAIA BENCHMARK RESULTS

• Table 14 reports GAIA results by L1, L2, and L3 task levels, with GPT-4o-mini used as the backbone for all experiments.The supplied passages identify the table’s scope but provide no results by level.Source: §C.3 · p. 27, Table 14 · p. 28

D EMPIRICAL VALIDATION OF ASSUMPTIONS

• The empirical validation uses 486 MATH test problems, 68 workflows, and T = 1200 bandit training rounds.The validation examines assumptions underlying CB-Orchestrator.Source: D EMPIRICAL VALIDATION OF ASSUMPTIONS · p. 27

D.1 ASSUMPTION 3.1: SEMANTIC EMBEDDING

• All 5 closest query pairs share problem templates or reasoning patterns, while all 5 farthest pairs span different mathematical domains.Distances were computed over all 117,855 pairs among 486 MATH problems.Source: §D.1 · p. 28, Table 15 · p. 28, Table 16 · p. 29
• Close workflow pairs share operator composition with minor variations, whereas far pairs use fundamentally different strategies or operator orderings.The analysis covers all 2,278 pairs among 68 workflows.Source: §D.1 · pp. 28–29, Table 17 · p. 29

D.2 ASSUMPTION 3.2: REWARD SMOOTHNESS

• 84.75% KNN reward-prediction accuracy exceeds the 51% random baseline, with reward similarity correlated with embedding proximity (r = 0.73, p < 10^-6).The predictor uses nearest workflows evaluated on the same query.Source: §D.2 · p. 29, Table 18 · p. 29
• Successful workflows are on average 20% closer to one another than to failed workflows, consistent with reward smoothness.The clustering analysis compares intra-success and successful-to-failed workflow distances.Source: §D.2 · p. 30, Table 19 · p. 30

D.3 ASSUMPTION 3.3: REALIZABILITY

• The existence of a function mapping embeddings to expected rewards cannot be directly verified, though later training rewards generally increase and the paper reports strong KNN prediction.The paper treats these as indirect evidence; it says the assumptions may not hold perfectly but hold sufficiently well in practice.Source: §D.3 · p. 30

E.1 GENERATED WORKFLOW CODE

• Workflow 31 directly generates three solutions, while workflow 3 first produces an analysis shared by its three solution calls; both use ScEnsemble and format an answer.Repeated calls and response unpacking are omitted from the code excerpts.Source: §E.1 · p. 31

E.2 TRAINING-TO-TEST COMPARISONS

• 90 integers satisfy the terminating-decimal test query, and workflow 31 returned that answer on the first attempt in all five test runs.The training query rewarded workflow 31 with 1 and workflow 3 with 0; the selected workflow’s three differently prompted direct solutions provide multiple opportunities to check the count.Source: §E.2 · p. 31
• Workflow 3 was selected for the trigonometric test query and gave the answer 9 on the first attempt in all five test runs.The training comparison rewarded workflow 3 with 1 and workflow 31 with 0; its shared analysis suited eliminating the parameter and identifying the algebraic relation.Source: §E.2 · p. 31