💬 NLP

Global Optimization and Inference-Time Region Grafting for Agentic Workflows

The paper introduces GRAFT, a training-free method that enables agentic workflows to adaptively replace failed execution regions with better alternatives using label-free quality signals, thereby achieving instance-wise optimization and improved performance across diverse tasks without requiring computationally expensive whole-workflow re-optimization.

Original authors: Donghyeok Koh, Gyuwan Kim, Jinyeong Bak, Seung-Hoon Na, Tao Yang, Haneol Jang, Cheoneum Park

Published 2026-08-04

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Donghyeok Koh, Gyuwan Kim, Jinyeong Bak, Seung-Hoon Na, Tao Yang, Haneol Jang, Cheoneum Park

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a giant, complex puzzle. In the world of artificial intelligence, these puzzles are called "agentic workflows." Instead of just asking a smart computer to "solve this," we give it a specific recipe—a step-by-step plan involving different tools like searching for facts, planning ahead, checking its own work, and refining the answer. Think of it like a kitchen where a head chef (the AI) doesn't just cook; they have a sous-chef to chop, a taste-tester to verify, and a planner to organize the menu.

For a long time, scientists have tried to find the perfect recipe for every type of puzzle. They run thousands of tests offline to figure out the best order of steps. But here's the problem: not every puzzle is the same. A simple math problem might only need a quick chop, while a tricky history question might need a deep dive and a double-check. If you use the same rigid recipe for every single puzzle, you might get stuck or make a silly mistake because the plan wasn't flexible enough for that specific moment. The big question is: Can we keep a great, pre-planned recipe but still tweak the steps while we are cooking, just for the specific dish we are making right now, without having to start over from scratch?

This is exactly what the paper "Global Optimization and Inference-Time Region Grafting for Agentic Workflows" tackles. The authors introduce a new system called GRAFT. Instead of forcing the AI to stick to one fixed plan or re-inventing the entire wheel for every single question, GRAFT acts like a master chef who has a "golden recipe" for a specific type of meal but is willing to swap out just one or two ingredients if the taste test says they need it.

Here is how it works in the real world of the paper: First, the system finds a globally optimized workflow (the "golden recipe") for a whole category of tasks, like math or coding, using standard testing methods. This happens before the AI starts answering questions. Then, when a specific question comes in, GRAFT doesn't just run the recipe blindly. It breaks the recipe down into small, self-contained sections called "regions." As the AI works through the problem, it checks each region. If a region (like the "reasoning" step) seems to be struggling or producing a weak result, GRAFT swaps that specific section with a better version on the fly.

Crucially, this swap happens without needing to know the correct answer beforehand (which is usually impossible during real-time use). Instead, the system uses clever "label-free" signals to judge quality. For example, in math, it might run the same problem five different ways and see if they all agree (a technique called self-consistency). In coding, it might run the code to see if it passes the tests. If a new version of a step looks better and doesn't break the connection to the next step, GRAFT "grafts" it in. If it doesn't, it keeps the original. This happens instantly for every single input.

The paper finds that this approach is a game-changer. When tested on five different benchmarks ranging from math problems (like GSM8K and MATH) to coding tasks (HumanEval) and complex questions (HotpotQA), GRAFT outperformed the previous best method, called MaAS, by an average of 3.85 points. In the world of AI benchmarks, that is a massive leap. For instance, on the GSM8K math dataset, GRAFT scored 95.04, beating the next best method which scored 92.30.

The authors also discovered something fascinating about the "recipe" itself. They found that an optimized workflow isn't just a static set of instructions; it's a flexible policy. Even if they swapped the "chef" (the underlying AI model) for a stronger one without changing the workflow at all, the performance went up. This suggests that a good workflow is adaptable; it can evolve and get better just by having a smarter tool to do the work, without needing to be re-designed.

However, the paper is careful to note where this magic works and where it hits a wall. The "label-free" signals used to judge quality work very well for math and code, where the answer is either right or wrong. But for complex knowledge questions (like those about history or science), the signals are less reliable, and the system doesn't improve as much. The authors suggest that while GRAFT is a powerful way to adapt workflows in real-time, it relies heavily on being able to verify the quality of a step without knowing the final answer.

In short, GRAFT proves that you don't have to choose between a rigid, pre-planned strategy and a chaotic, make-it-up-as-you-go approach. By grafting small, smart adjustments onto a solid foundation, AI agents can become more robust, efficient, and accurate, solving problems that were previously too tricky for a one-size-fits-all plan.

Technical Summary: GRAFT for Agentic Workflow Optimization

1. Problem Statement

Recent advances in agentic workflows have established automated methods for designing task-specific workflows through offline search or architecture selection (e.g., AFlow, MaAS). However, these approaches suffer from a fundamental limitation: they determine a single, fixed workflow structure before execution. This static approach fails to account for the variability in difficulty and reasoning requirements across individual inputs. For instance, a simple arithmetic problem may require a single reasoning step, while a complex compositional problem necessitates decomposition, verification, and re-reasoning.

Attempting to re-optimize the entire workflow for every input at inference time is computationally prohibitive due to the exponential search space of operator combinations. Furthermore, offline methods rely on ground-truth labels for optimization, which are unavailable during inference. Without external feedback, relying solely on an LLM to evaluate and revise its own reasoning can be unreliable. Additionally, multi-agent systems face "inter-region interference," where locally replacing a component can alter downstream inputs and degrade the final outcome, even if the local component improves.

2. Methodology: GRAFT

To address these challenges, the authors introduce GRAFT (Global Optimization and Inference-Time Region Grafting), a training-free framework that preserves a globally optimized workflow while enabling instance-wise adaptation through local region replacement.

Core Architecture

Global Workflow Prior: GRAFT begins with a task-specific global workflow ( $W_c^*$ ) searched offline. This workflow is structured as a sequence of Single-Entry Single-Exit (SESE) regions. Each region corresponds to a specific role (e.g., plan, evidence, reason, verify) and contains a local candidate space of operators.
Inference-Time Local Grafting: For each input, GRAFT does not re-optimize the entire graph. Instead, it identifies regions requiring adaptation and explores a small local candidate space restricted to that region's role.
Label-Free Assessment: Since ground truth is unavailable at inference, GRAFT evaluates candidates using label-free proxy signals:
- Self-Consistency: Agreement across multiple reasoning chains.
- Groundedness: The extent to which an answer is supported by provided evidence (lexical coverage of content words).
- Verifier Signals: Code test pass rates or LLM-based judgments.
Coupling Guard: To prevent "inter-region interference," a coupling guard accepts a replacement only if it improves local quality and preserves boundary support (consistency with upstream evidence) within a tolerance $\epsilon$ . This ensures that local improvements do not degrade global workflow consistency.
Memory and Amortization: Winning configurations are stored in a memory indexed by input-type signatures. For subsequent inputs, GRAFT retrieves these configurations, bypassing the need for repeated local search and amortizing the computational cost.

Algorithmic Flow

Offline Phase: A global workflow is constructed by selecting operators for each region to maximize performance on a validation set, balancing quality and token cost.
Online Phase:
- The system processes regions in upstream-first order.
- It attempts to retrieve a known optimal configuration from memory.
- If no match exists or the retrieved configuration fails quality targets, a local search is performed over the region's candidate space.
- Candidates are evaluated using the label-free proxy and the coupling guard.
- Accepted configurations update the workflow state and memory; downstream regions are marked "stale" for re-evaluation in subsequent passes.
- The process terminates when no further changes occur or quality targets are met.

3. Key Contributions

Inference-Time Adaptation Paradigm: GRAFT proposes a framework that treats a workflow not as a static artifact but as an adaptable execution policy. It re-optimizes region-level structures for each input without gradient updates or re-training.
Label-Free Local Optimization Mechanism: The design introduces specific proxies (self-consistency, groundedness, verifier signals) and a coupling guard to enable reliable local search without ground truth, ensuring that local improvements do not compromise global consistency.
State-of-the-Art Performance: The method achieves superior performance across diverse tasks, demonstrating that an optimized workflow can evolve with inference-time feedback and stronger executors.

4. Experimental Results

The authors evaluated GRAFT on five benchmarks spanning mathematical reasoning (GSM8K, MATH, MultiArith), code generation (HumanEval, MBPP), multi-hop QA (HotpotQA, DROP), and knowledge-intensive QA (MMLU-Pro, GPQA).

Performance Gains: Under matched optimizer and executor settings (using GPT-4o-mini), GRAFT achieved an average score of 87.44, outperforming the strongest prior method, MaAS, by 3.85 points. It also surpassed AFlow by 5.19 points.
Ablation Studies:
- Removing local grafting (executing the global workflow unchanged) resulted in a significant performance drop (average -4.10), confirming that the gains stem from inference-time adaptation.
- Replacing label-free proxies with random scores caused a similar drop, validating the efficacy of the proxy signals.
- Removing the coupling guard led to a smaller but consistent drop, highlighting its role in preventing interference.
Executor Transfer: When the executor model was swapped for a stronger one (e.g., from GPT-4o-mini to Claude Sonnet) without re-optimizing the global workflow, GRAFT achieved substantial gains. This suggests the optimized workflow acts as a flexible policy that adapts to stronger models.
Efficiency: Configuration memory significantly reduced search costs. For tasks with uniform input types (e.g., GSM8K), memory reuse rates reached 0.86–0.92, effectively amortizing the cost of local search across inputs.

5. Significance and Claims

The paper claims that GRAFT demonstrates that an optimized workflow is not merely a static optimization artifact but an adaptable execution policy. By decoupling global structural optimization from instance-wise local adaptation, GRAFT enables systems to handle the variability of individual inputs without the prohibitive cost of full re-optimization. The framework proves that high-performance agentic workflows can be achieved without training, relying instead on a combination of offline global search and online, label-free local refinement. The results suggest that future agentic systems can evolve dynamically, leveraging stronger executors and inference-time feedback to improve performance on a per-instance basis.