OSCAR: Optimization-Steered Agentic Planning for Composed Image Retrieval

AI summary

Overview

Research area: Composed image retrieval (CIR) — multimodal retrieval that combines a reference image with a modification text — and agentic/LLM-driven retrieval planning.

Technical level: Advanced. The paper assumes familiarity with vision-language models, retrieval benchmarks, mixed-integer programming (MIP), and boolean set operations.

Scope: The paper proposes OSCAR, a training-free framework that solves CIR by deriving optimal tool-call trajectories offline through two-stage mixed-integer programming, then reusing them as in-context demonstrations to steer a VLM planner at inference.

What This Paper Is About

Composed image retrieval requires finding images that satisfy a text modification of a reference image, which involves reasoning over heterogeneous visual and textual constraints. Existing methods fall into two camps: unified embedding retrieval, which collapses the query into one representation and therefore suffers from "single-model myopia," and heuristic agentic retrieval, which uses LLM/VLM tool calls but relies on greedy, trial-and-error orchestration with no global objective. OSCAR's goal is to replace that heuristic search with a principled optimization problem that yields provably structured planning trajectories.

Key Contributions

1. Optimization perspective. The authors state they are the first to formulate agentic CIR as a mixed-integer programming problem, mathematically deriving optimal planning trajectories for training samples that maximize ground-truth coverage while minimizing computational redundancy — with no human annotation.

2. Set-theoretic composition logic. They introduce a logic for composing CIR results via boolean set operations (union, intersection, difference), enabling explicit inclusion and conservative exclusion reasoning that they argue is mathematically intractable for single-embedding models and heuristic agentic methods.

3. The OSCAR framework. A novel offline-online paradigm: MIP solutions are stored in a "golden library" and used as in-context demonstrations that steer a VLM to perform complex compositional planning in a single inference pass.

4. Empirical superiority. OSCAR outperforms state-of-the-art single-embedding and agentic baselines on three public benchmarks and a private industrial benchmark, while using only 10% of the training data for library construction.

Main Findings

• CIRCO and CIRR results. In Table 1, OSCAR reaches mAP@5/10/25/50 of 56.54 / 58.53 / 61.92 / 62.67 on CIRCO and Recall@1/5/10/50 of 51.18 / 79.50 / 87.45 / 96.56 on CIRR. Relative improvements against the best baseline are reported as 23.13%, 24.19%, 22.88%, and 21.81% on CIRCO, and 18.67%, 7.40%, 5.25%, and -0.22% on CIRR.

• Strongest baselines for context. On CIRCO the best non-OSCAR numbers come from QQMM-embed-v2 (45.92 / 47.13 / 50.39 / 51.45); on CIRR the best baselines include QQMM-embed-v2 (28.98 / 73.66 / 82.98 / 96.72), FiRE (43.33 / 74.02 / 83.51 / 95.83), and X^R (43.13 / 73.59 / 83.09 / 94.05).

• FashionIQ results. Table 2 shows OSCAR at R@10/R@50 of 38.47 / 65.15 (Dress), 44.50 / 67.52 (Shirt), 48.24 / 71.24 (Toptee), and 43.73 / 67.97 averaged. Relative improvements are 2.92%, 5.13%, -3.40%, 2.84%, 3.61%, 4.02%, and 1.25% / 4.82% on the averages. The best baseline on the average is MRA-CIR at 37.85 / 58.98.

• Ablation: trajectory demonstrations matter. Removing demonstrations ("w/o Demo.") drops CIRCO m@25/m@50 to 59.72 / 59.84, CIRR R@10/R@50 to 75.01 / 82.02, and FashionIQ averages to 46.57 / 61.62.

• Ablation: set operations matter. Removing set difference ("w/o Set.Diff.") gives 59.54 / 59.62 on CIRCO, 87.32 / 93.80 on CIRR, and 46.46 / 62.08 on FashionIQ.

• Ablation: removing both is worst. "w/o Set.Diff. & Demo." yields 58.63 / 58.66 on CIRCO, 39.11 / 54.53 on CIRR, and 49.44 / 53.96 on FashionIQ. The authors characterize this variant as close to a simple union of retrieved results, akin to multi-channel retrieval, with particularly large drops at Recall@50.

• Generalization across VLM backbones. Table 4 on CIRCO reports relative improvements from adding OSCAR: Qwen3-VL-4B from 59.22 / 59.33 / 88.62 / 88.75 to 61.18 / 61.91 / 93.75 / 96.12 (3.31% / 4.35% / 5.79% / 8.30%); Qwen3-VL-8B from 59.22 / 59.31 / 88.12 / 88.25 to 61.65 / 62.40 / 94.88 / 97.12 (4.10% / 5.21% / 7.68% / 10.05%); Qwen3-VL-32B from 59.72 / 59.84 / 86.88 / 87.00 to 61.92 / 62.67 / 94.62 / 97.50 (3.68% / 4.73% / 8.91% / 12.07%); InternVL3.5-38B from 60.29 / 60.62 / 90.88 / 91.75 to 61.20 / 61.58 / 92.38 / 93.75 (1.51% / 1.58% / 1.65% / 2.18%).

• Weaker tool-calling models underperform. The authors report that preliminary experiments with Qwen2.5-VL and MiniCPM-V showed that models with weaker tool-calling capabilities often fail to follow tool-use instructions and cannot reliably execute the required calls, leading to degraded performance.

• Training-free and data-efficient. OSCAR is described as a training-free framework based on open-sourced models that requires no parameter updates, and the demonstrations are derived from only 10% of training data.

Methodology in Plain English

The task is broken into a space of discrete actions. The authors define an atomic retrieval as a four-tuple: a retrieval tool, a rewritten query, a polarity (positive for inclusion, negative for exclusion), and a top-k truncation level. Taking the Cartesian product over tools, rewritten queries, polarities, and truncations produces a decision space of 1,182 atomic retrievals per sample. Because results are monotonic in k (a larger k strictly contains a smaller one), retrieval is executed once at the maximum k and smaller top-k variants are produced by slicing.

Stage one (recall-oriented selection MIP). Binary variables decide which positive atomic retrievals to select. Auxiliary variables track which images are covered by at least one selected retrieval and which tools are active. The objective balances three terms: maximizing ground-truth coverage, minimizing inclusion of irrelevant images, and encouraging tool diversity to avoid single-model myopia. A constraint enforces truncation exclusivity — at most one k per "family" of retrievals sharing the same tool, query, and polarity. The union of selected retrievals forms a recall-oriented candidate set.

Stage two (precision-oriented composition MIP). The final result set is defined as the union of selected positive retrievals minus the intersection of selected negative retrievals. Intersection is used for the negative clause so an image is removed only if all selected negative tools agree it is irrelevant — conservative exclusion intended to prevent deleting ground-truth samples because of a single-tool hallucination. A regularization term mitigates trivial solutions such as selecting no negative tools, and a constraint requires at least one positive atomic retrieval. The authors note in Appendix E that they compare this conservative design against more aggressive negative filtering.

Online steering. Offline MIP solutions become trajectories stored in a golden library. Each training instance's problem context — the modification query concatenated with the caption of the reference image — is encoded with Qwen3-Embedding-8B (captions are produced by Qwen3-VL-32B). At test time the composed query is embedded and the top-N most similar cases are retrieved by cosine similarity to serve as in-context demonstrations for the VLM planner, whose output is fed to a VLM verifier for final ranking. The claim is that this transfers generalized planning logic — tool choice, exclusion polarity, and truncation calibration — rather than memorized answers.

Why This Matters

Impact on research. The paper reframes agentic retrieval from heuristic search into a global optimization problem, and provides an explicit set-theoretic composition mechanism (union/intersection/difference) that single-embedding architectures cannot express. If the approach generalizes, it offers a way to get optimality-informed agent behavior without iterative ReAct-style loops or human-annotated planning data, and the 10%-data result is framed as evidence of abstract meta-strategy learning rather than dataset memorization.

Real-world applications (as implied by the paper's framing):

• E-commerce and fashion search, where users combine a reference product photo with attribute edits.
• Industrial retrieval over private user galleries, which the paper evaluates on a private industrial benchmark.
• General multimodal search assistants that must coordinate multiple retrieval tools, including captioners, rewriters, and retrievers.
• Any retrieval setting that needs explicit inclusion and exclusion constraints, where boolean composition is more precise than a single similarity score.

Industry relevance. The work originates from a collaboration involving OPPO, Shanghai Jiao Tong University, and Shanghai Innovation Institute, and is supported by the National Natural Science Foundation of China (624B2096, 72595872, 72542012, 62322603). Because OSCAR is training-free and plug-and-play across VLM backbones, and since gains scale with the planner model's tool-calling ability, it is directly relevant to product teams that already have strong VLMs and want better retrieval without training a new embedding model.

Future Directions

• Extending beyond retrieval. The stated limitation is that OSCAR is designed for retrieval tasks naturally decomposable into atomic retrievals and set-theoretic composition; non-retrieval tasks would require redefining the action space, optimization objective, and composition logic. The authors explicitly name multi-hop question answering and open-ended tool use as future targets.

• Improving planner capability alignment. The observation that weaker tool-calling VLMs fail to follow instructions and degrade performance raises the question of how to make the framework robust for models below a certain tool-use capability threshold.

• Scaling and efficiency questions. The MIP pipeline is described as computationally intensive and dependent on ground truth, which is why it is offline-only. The paper defers efficiency and scalability analysis, robustness to the number of demonstrations, and OOD generalization analysis to the appendix, leaving open how the golden library scales.

• Composition expressiveness. The composition template is deliberately restricted to a fixed two-clause structure (positive union minus negative intersection). The authors discuss in Appendix G.9 the design choice of this template versus a more expressive DNF formulation, which points to richer boolean compositions as an open direction.

Target Audience

Researchers and engineers working on composed image retrieval, multimodal embedding systems, and agentic/VLM-based retrieval pipelines. It is also relevant to practitioners of optimization-guided agent design, since the central idea — solving a MIP offline over historical data and distilling the solutions into in-context demonstrations — is transferable to other planning domains. Readers without background in mixed-integer programming or boolean set composition will find the methodology section demanding.

Authors’ abstract

Composed image retrieval (CIR) requires complex reasoning over heterogeneous visual and textual constraints. Existing approaches largely fall into two paradigms: unified embedding retrieval, which suffers from single-model myopia, and heuristic agentic retrieval, which is limited by suboptimal, trial-and-error orchestration. To this end, we propose OSCAR, an optimization-steered agentic planning framework for composed image retrieval. We are the first to reformulate agentic CIR from a heuristic search process into a principled trajectory optimization problem. Instead of relying on heuristic trial-and-error exploration, OSCAR employs a novel offline-online paradigm. In the offline phase, we model CIR via atomic retrieval selection and composition as a two-stage mixed-integer programming problem, mathematically deriving optimal trajectories that maximize ground-truth coverage for training samples via rigorous boolean set operations. These trajectories are then stored in a golden library to serve as in-context demonstrations for online steering of VLM planner at online inference time. Extensive experiments on three public benchmarks and a private industrial benchmark show that OSCAR consistently outperforms SOTA baselines. Notably, it achieves superior performance using only 10% of training data, demonstrating strong generalization of planning logic rather than dataset-specific memorization.