PaperlayerView exact revision on arXiv

Source-linked AI summary

CoSTA$\ast$: Cost-Sensitive Toolpath Agent for Multi-turn Image Editing

Advait Gupta, NandaKiran Velaga, Dang Nguyen, Tianyi Zhou

arXiv:2503.10613v1cs.CV

TL;DR

Multi-turn image editing remains challenging, while LLM planning and conventional search each have limitations for choosing efficient toolpaths. CoSTA* combines LLM subtask planning with cost-sensitive A* search; on a challenging benchmark, it advances the cost-quality Pareto frontier over existing agents.

  • Problem

    Multi-turn image editing requires composite, delicate changes, while LLMs may lack precise tool knowledge and graph search can require costly exploration.

    Source: §1 · p. 2

  • Method

    CoSTA* uses an LLM-generated subtask tree to prune a tool-dependency graph, then runs cost-sensitive A* using tool benchmark information and execution updates.

    Source: §1 · p. 2

  • Results

    CoSTA* advances the cost-quality Pareto frontier over existing agents on a challenging multi-turn image-editing benchmark.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The authors describe this neurosymbolic approach as a promising direction toward more capable and reliable agents.

    Source: §6 · p. 9

    CLIP similarity can miss small critical edits and semantic coherence in complex multimodal tasks, motivating human evaluation.

    Source: §5.2 · p. 7

Abstract

from arXiv · show

Text-to-image models like stable diffusion and DALLE-3 still struggle with multi-turn image editing. We decompose such a task as an agentic workflow (path) of tool use that addresses a sequence of subtasks by AI tools of varying costs. Conventional search algorithms require expensive exploration to find tool paths. While large language models (LLMs) possess prior knowledge of subtask planning, they may lack accurate estimations of capabilities and costs of tools to determine which to apply in each subtask. Can we combine the strengths of both LLMs and graph search to find cost-efficient tool paths? We propose a three-stage approach "CoSTA*" that leverages LLMs to create a subtask tree, which helps prune a graph of AI tools for the given task, and then conducts A* search on the small subgraph to find a tool path. To better balance the total cost and quality, CoSTA* combines both metrics of each tool on every subtask to guide the A* search. Each subtask's output is then evaluated by a vision-language model (VLM), where a failure will trigger an update of the tool's cost and quality on the subtask. Hence, the A* search can recover from failures quickly to explore other paths. Moreover, CoSTA* can automatically switch between modalities across subtasks for a better cost-quality trade-off. We build a novel benchmark of challenging multi-turn image editing, on which CoSTA* outperforms state-of-the-art image-editing models or agents in terms of both cost and quality, and performs versatile trade-offs upon user preference.

1. Introduction

CoSTA* combines LLM subtask planning with graph search to find toolpaths for composite, multi-turn image editing. It targets a cost-quality trade-off, and the paper reports that it dominates existing agents on both metrics.

1. Introduction

  • CoSTA* reaches Pareto optimality and dominates four recent image-editing agents on cost and quality.The paper reports this comparison on its multi-turn editing benchmark.Source: Figure 1 · p. 1, §1 · p. 2
  • Composite multi-turn edits remain difficult because models struggle to make several delicate changes while preserving other image details.The cited example combines recoloring, redacting text, adding text, and detecting children.Source: §1 · p. 1
  • LLM-only planning can be heuristic and fail, while A* search can be computationally expensive and does not scale well across large tool graphs.Search depends on accurate per-step value and cost estimates and sufficient exploration.Source: §1 · p. 2
  • CoSTA* uses an LLM to build a subtask tree, then applies A* to the tool-dependency subgraph spanned by that tree.Each root-to-leaf path in the tree represents a feasible high-level plan.Source: §1 · p. 2
  • Tool inputs, outputs, and subtasks define graph connections, while benchmark tool costs and quality inform A* heuristics and actual completed-subtask outcomes update execution cost.The trade-off coefficient α lets the search target user preferences for quality versus cost.Source: §1 · p. 2
  • The paper introduces a challenging benchmark of multi-turn image-editing tasks spanning different complexities.It also presents CoSTA* as a hierarchical agent combining LLMs and graph search for composite editing toolpaths.Source: §1 · p. 3

2. Related Work

Prior image-generation and editing work improves generation, conditioning, and multimodal planning, but precise control and complex prompts remain challenging. Existing multimodal agents coordinate models or support iterative refinement, while Figure 4 depicts tool dependencies for toolpath search.

Image Editing via Generative AI

  • Text-to-image methods produce realistic, diverse images but often lack precise control; ControlNet and sketch-based conditioning refine user-driven edits (Zhang et al., 2023b; Voynov et al., 2022).Layout-to-image systems also synthesize compositions from spatial object arrangements.Source: §2 · p. 3
  • Despite advances in conditioning and multimodal editing, current models still struggle with complex prompts.Figure 4 presents a directed Tool Dependency Graph whose edges denote legal output-to-input dependencies and enable toolpath search for composite editing tasks.Source: §2 · p. 3, Figure 4 · p. 4

Large Multimodal Agents for Image Editing

  • Multimodal agents coordinate models to decompose complex tasks, support iterative image refinement, or improve instruction-based editing (Wang et al., 2024b; Huang et al., 2024; Huang et al., 2023).The section also describes preference aggregation for compositional generation and foundational vision-language systems (Zhang et al., 2024b; Li et al., 2023a; Brooks et al., 2023).Source: §2 · pp. 3–4

3. Foundations of CoSTA∗

CoSTA* represents tool capabilities, dependencies, and benchmark-derived cost and quality information in structures used for planning and search. Its foundations include an extensible model table, a directed dependency graph, and benchmark-based heuristic scores.

3.1. Model Description Table

  • The Model Description Table covers 24 models and 24 tasks across image and text modalities, and can be extended with models and their supported tasks.It records model inputs, dependencies, and outputs.Source: §3.1 · p. 4

3.2. Tool Dependency Graph

  • The Tool Dependency Graph links tools when one tool depends on another's output, and can be generated from model input-output specifications.The graph is a directed graph whose edges encode tool dependencies.Source: §3.2 · p. 4

3.3. Benchmark Table for Heuristic Scores

  • Tool heuristics use execution-time and quality scores from existing benchmarks or studies, with missing tool-task values evaluated on 137 instances across 121 images.Quality values are normalized per subtask to a [0, 1] scale.Source: §3.3 · p. 4
  • Figure 5 shows an LLM-generated subtask tree, its conversion to a dependency-preserving tool subgraph, and A* search for a cost-and-quality-balanced execution path.The Benchmark Table is presented in Table 11.Source: Figure 5 · p. 5, §3.3 · p. 5

4. CoSTA∗: Cost-Sensitive Toolpath Agent

CoSTA* combines LLM-generated subtask plans with A* search on a task-specific tool subgraph. The staged design maps subtasks to dependency-preserving model options and ranks paths using cost and quality.

4.1. Task Decomposition & Subtask Tree Planning

  • The LLM encodes subtasks and dependencies as a DAG, whose root-to-leaf paths represent valid solutions and alternative workflows.Different subtask orders and workflows can be represented in the tree.Source: §4.1 · p. 5

4.2. Tool Subgraph Construction

  • Each subtask maps to its eligible model subgraph, with the node set covering models needed to execute every subtask.The eligible models are listed in the Model Description Table.Source: §4.2 · p. 5
  • Backtracked TDG dependencies connect models through required intermediate outputs, preserving feasible, logically consistent execution paths.Source: §4.2 · pp. 5–6
  • Figure 6 reports that CoSTA* excels on complex multimodal tasks and outperforms all baselines.Source: Figure 6 · p. 6

4.3. Path Optimization with A∗Search

  • A* minimizes f(x) = g(x) + h(x), combining real-time execution costs with precomputed heuristic estimates to select an execution path.Source: §4.3 · p. 6

4.4. Heuristic Cost h(x)

  • h(x) estimates best-case cost from a tool-task node to a leaf, recursively combining benchmark time and quality under α.The heuristic excludes the cost of the current node itself.Source: §4.4 · p. 6

4.5. Actual Execution Cost g(x)

  • g(x) updates from runtime and validated quality on explored paths; threshold failures trigger retries, and paths failing all retries leave the queue.The observed execution cost is updated to the minimum observed value.Source: §4.5 · p. 6

5. Experiments

CoSTA* is evaluated on multi-turn image-editing tasks using human accuracy assessments and comparisons with agentic baselines. Results and ablations report advantages on complex and text-plus-image tasks, with feedback and multimodal support examined separately.

5.1. Experimental Settings

  • The benchmark contains 121 curated images, with prompts spanning 1–8 subtasks; 81 tasks involve image-only edits and 40 require multimodal processing.Compared agentic baselines support 5–6 subtasks, versus CoSTA*’s 24 supported subtasks.Source: §5.1 · p. 6

5.2. Evaluation Metrics

  • CoSTA* outperforms baselines across task categories, with stronger advantages on complex (5+) tasks and text+image edits, and offers adjustable cost-quality trade-offs.The comparison covers accuracy across task types and categories.Source: Table 2 · p. 7, §5.3 · pp. 7–8
  • Human evaluation scores each subtask for full, partial, or failed correctness; CLIP scores can overstate performance on complex editing tasks.On 50 tasks with intentional errors, CLIP similarity was 0.93–0.98 while human accuracy was 0.7–0.8; CLIP is useful for isolated subtask validation but misses localized errors in full-task evaluation.Source: §5.2 · p. 7, Table 3 · p. 7
  • Qualitative comparisons highlight real-time feedback, dynamic heuristic adjustments, and LLM integration with A* search as capabilities absent from baselines.Figure 2 presents qualitative comparisons of multimodal tasks.Source: §5.3 · p. 8, Table 5 · p. 8

5.4. Ablation Study

  • On 35 high-risk tasks, integrating real-time feedback raised accuracy from 0.798 with h(x) alone to 0.923 with g(x).Feedback penalizes poorly performing tools and dynamically selects alternatives.Source: Table 6 · p. 8, §5.4 · p. 8, Figure 7 · p. 8
  • For text-related edits, CoSTA* reached 0.93 accuracy, while image-focused tools achieved 0.48.The comparison tests tasks requiring both text and image processing; Figure 8 highlights qualitative advantages in preserving visual and textual fidelity.Source: Table 7 · p. 8, §5.4 · p. 8, Figure 8 · p. 8

6. Conclusions

CoSTA* combines a large multimodal model planner with A* search to find editing paths that balance cost and quality. The paper reports reliable handling of complex editing queries, higher image quality than existing baselines, and support for 24 tasks.

6. Conclusions

  • CoSTA* combines a large multimodal model planner with A* search to find an editing path balancing cost and quality.The conclusion describes this as a neurosymbolic approach.Source: §6 · p. 8
  • CoSTA* handles complex real-world editing queries reliably, surpasses existing baselines in image quality, and supports 24 tasks.The authors identify potential misuse and persistent pretrained-model biases as responsible-deployment concerns.Source: §6 · p. 9, Impact Statement · p. 9

Impact Statement

  • The impact statement identifies misleading image alterations and persistent pretrained-model biases as risks, and calls for provenance tracking, watermarking, dataset audits, and bias mitigation.These are framed as responsible-deployment safeguards and future considerations.Source: Impact Statement · p. 9

A. Step-by-Step Execution of Tasks in Figure 2

Figure 9 visualizes selected subtasks executed sequentially within a composite task. It shows intermediate outputs and stepwise image transformations, not CoSTA*’s full decision-making process.

A. Step-by-Step Execution of Tasks in Figure 2

B. Human Evaluation for Accuracy Calculation

The appendix describes human scoring of subtask correctness, aggregation into task accuracy, and averaging across tasks for overall accuracy. It also explains that the Tool Dependency Graph is constructed from tool input-output relationships.

B. Human Evaluation for Accuracy Calculation

  • Human evaluators assess subtasks using criteria that account for nuanced errors, semantic inconsistencies, and multi-step dependencies.The section outlines scoring criteria and aggregation.Source: B. Human Evaluation for Accuracy… · p. 12

B.1. Subtask-Level Accuracy

  • Subtask scores are 1 for fully correct, 0 for failed, or a predefined task-specific partial score.The partial-score rules are specified for different subtasks in Table 8.Source: §B.1 · p. 13, Table 8 · p. 13

B.2. Task-Level Accuracy

  • Task accuracy is the mean correctness score across its subtasks.This makes task accuracy reflect overall subtask correctness.Source: §B.2 · p. 13

B.3. Overall Accuracy Across Tasks

  • Overall accuracy is the average of task-level accuracies across all evaluated tasks.The number of evaluated tasks is denoted by |T|.Source: §B.3 · p. 13

C. Automatic Construction of the Tool Dependency Graph

D.1. A. Dataset Construction for Benchmarking

The benchmark combines LLM-generated, human-curated editing prompts with deliberately constructed images, then covers 121 image-task pairs across image-only and text+image tasks. Its composition spans diverse subtasks, including common object edits and rarer complex operations.

D.1. A. Dataset Construction for Benchmarking

  • For real-world image-editing tasks, an LLM generated diverse structured prompts covering object, text, and scene operations, and human annotators manually curated each prompt to ensure edits were logically feasible.Source: §D.1.1 · p. 14
  • Meta AI generated the starting images under instructions to include prompt elements and make scene attributes and text clear for editing evaluation.Images were also designed for sufficient complexity and diversity; an example prompt image explicitly contains the objects later edited.Source: §D.1.2 · p. 14

D.2. B. Dataset Composition & Subtask Distribution

  • The dataset contains 121 image-task pairs spanning image-only and text+image tasks, with each prompt decomposed into subtasks mapped to supported models.Figure 11 showcases representative inputs and prompts across visual and multimodal editing scenarios.Source: §D.2 · p. 14, Figure 11 · p. 15
  • Object Replacement, Object Recoloration, and Object Removal are most common, while rarer operations such as Keyword Highlighting remain part of the benchmark.Figure 10 depicts the number of instances for each subtask.Source: Figure 10 · p. 15, §D.2 · p. 16

E. Consistency in CoSTA* Outputs

CoSTA* outputs are reported as consistent across repeated runs, with captioning showing more variation. The accompanying model description maps 24 specialized models to subtasks, dependencies, and outputs, supporting construction of the Tool Dependency Graph.

E. Consistency in CoSTA* Outputs

  • Across repeated runs on 20 images per subtask, CoSTA* showed high CLIP similarity, with negligible variability except for image captioning at 0.92 similarity.The paper attributes captioning variation to the existence of multiple valid descriptions.Source: E. Consistency in CoSTA* Outputs · p. 16

F. Model Description Table (MDT)

  • The Model Description Table lists 24 specialized models and maps their supported subtasks, input dependencies, and outputs to enable automatic Tool Dependency Graph construction.The table notes that some standard inputs are omitted for simplicity.Source: F. Model Description Table (MDT) · p. 17

G. Benchmark Table (BT)

CoSTA* uses empirical tool-task accuracy and execution-time estimates to guide cost-sensitive tool selection. It constructs a task-specific tool subgraph and applies A* search, updating execution costs when quality checks fail.

G. Benchmark Table (BT)

  • The Benchmark Table supplies empirical execution time and normalized accuracy for each tool-task pair, using published benchmarks where available and evaluations otherwise.For tools without prior benchmarks, evaluations covered 137 instances of a subtask on 121 dataset images.Source: G. Benchmark Table (BT) · p. 17

H. Algorithms

  • A* search uses benchmark data, a trade-off parameter, and a quality threshold to find the lowest-cost valid path through the tool subgraph.The algorithm initializes heuristic values, explores neighbors, and terminates when it finds a valid path.Source: H. Algorithms · p. 18, Step 2: Output Optimal Path · p. 18

Step 2: Output Optimal Path

  • The task-specific tool subgraph is built by generating an LLM subtask tree, finding supported models for each subtask, and backtracking their dependencies in the Tool Dependency Graph.The resulting tool graphs replace the corresponding subtask nodes in the tree.Source: Step 2: Output Optimal Path · p. 18

I. A* Execution Strategy

  • When execution quality falls below threshold, CoSTA* retries with adjusted parameters and updates execution costs using real-time performance before continuing the search.The search selects the node with the lowest f(x) and continues until a leaf node is reached.Source: §I · p. 19, Figure 12 · p. 19

J. Correlation Analysis of CLIP Scores and Human Accuracy

Across 40 tasks, CLIP scores correlate weakly with human accuracy, limiting their reliability for complex image-text edits. The accompanying prompts specify how to structure dependent editing subtasks and handle text replacement spatially.

J. Correlation Analysis of CLIP Scores and Human Accuracy

  • Across 40 tasks, CLIP similarity had weak correlation with human accuracy (Spearman’s ρ = 0.59; Kendall’s τ = 0.47) and missed fine-grained errors in complex edits.The analysis notes missed objects, multiple valid outputs, context-dependent errors, and cases above 0.95 CLIP similarity with human accuracy below 0.75.Source: J. Correlation Analysis of CLIP Scores… · p. 19, Figure 13 · p. 20

K.1. Understanding the Subtask Tree

  • A subtask tree represents atomic image operations and orders dependent operations after their prerequisites, with each operation building on prior steps.For example, segmentation should follow replacement when both are required.Source: §K.1 · p. 21, §K.2 · p. 21, §K.3 · p. 21

K.2. Steps to Generate the Subtask Tree

  • Tree-generation instructions require identifying and labeling subtasks, ordering dependencies, and distinguishing repeated occurrences when independent valid paths exist.Replacement may be represented either as a direct replacement or as replacement followed by recoloration.Source: §K.2 · p. 21

K.4. Supported Subtasks

  • The prompt restricts trees to a defined set of supported subtasks and requests JSON nodes containing the subtask name, parent, and execution order.The output should include the logical flow and relevant object labels.Source: §K.4 · p. 21, §K.5 · p. 21

L.1. Your Task

  • The text-replacement prompt asks the model to identify words to remove and replacements that preserve spatial coherence and fit naturally in the image.Added words may require rewriting adjacent words to maintain spacing.Source: §L.1 · p. 24, §L.2 · p. 24

L.2. Guidelines for Text Replacement 1. Identify Words to Remove:

  • Text-replacement guidance uses shared bounding boxes for replaced phrases and adjusts placements or line breaks when longer text needs more space.Bounding boxes should follow the text’s natural flow, and an example permits splitting a replacement across lines if it does not fit.Source: §L.2 · p. 24
Loading 2503.10613v1…