oscar optimization steered agentic planning for composed image retrieval
content_hash: cab0a065f07522be ---# OSCAR: Optimization-Steered Agentic Planning for Composed Image Retrieval
Conference: EMNLP 2026
Paper: ACL Anthology
Code: https://github.com/tengwang0318/OSCAR
Area: Information Retrieval & RAG
Keywords: Composed Image Retrieval, Mixed-Integer Programming, Agentic Planning, Boolean Set Operations, Offline-Online Paradigm
TL;DR¶
OSCAR reframes agentic composed image retrieval (CIR) from heuristic trial-and-error into a two-stage mixed-integer programming (MIP) trajectory optimization problem, building a golden trajectory library of positive unions and conservative negative intersections offline to steer a vision-language model (VLM) planner via in-context demonstrations during single-pass online inference, outperforming prior SOTAs using only 10% of training data.
Background & Motivation¶
Composed image retrieval (CIR) aims to retrieve target images from a large gallery that satisfy specific textual modifications while preserving the visual context of a reference image. As real-world search demands become increasingly sophisticated, user queries incorporate heterogeneous constraints ranging from high-level stylistic shifts to fine-grained visual attribute edits and explicit element additions or removals. Existing CIR approaches predominantly adhere to the Unified Embedding Retrieval paradigm, compressing multimodal queries into a single continuous latent space via monolithic multimodal encoders or fine-tuned models for nearest-neighbor search. However, user intents exhibit vast diversity across domains, inevitably causing "single-model myopia"—a model optimized for natural images struggles with fashion-specific attributes, while a domain-specific model lacks broader reasoning capacity. Furthermore, a single continuous embedding space cannot mathematically guarantee strict inclusion and exclusion constraints.
To overcome this representation bottleneck, Heuristic Agentic Retrieval has emerged, decomposing CIR into multi-step workflows executed by LLMs or VLMs using external tools (such as captioners, rewriters, and multiple retrievers) in ReAct-style trial-and-error loops. Nevertheless, these pipelines suffer from "suboptimal orchestration": models make greedy, iterative decisions based solely on local intermediate context without a global objective. This leads to unstructured, redundant tool calls, flawed execution logic, and brittle handling of set-theoretic operations (inclusion and exclusion). In addition, repeated multi-round interactions incur substantial computational latency without providing any mathematical guarantees of finding the optimal retrieval trajectory.
Confronted with the dual dilemma of single-model myopia and suboptimal agentic orchestration, this paper realizes that when individual retriever invocations are treated as discrete decision units, the ideal tool combination and candidate filtering for annotated training samples mathematically mirror a Set Cover variation. Core idea: reframe agentic CIR from a heuristic search process into a discrete mixed-integer programming (MIP) global trajectory optimization problem, solving offline for a golden library of high-recall selections and high-precision boolean compositions that steer a VLM planner via in-context demonstrations to achieve near-optimal, single-pass retrieval planning at online inference.
Method¶
Overall Architecture¶
OSCAR introduces a novel Offline-Online Paradigm to bridge mathematical optimization and agentic retrieval. In the offline stage, for each annotated training sample, the system generates multi-polarity queries via VLM rewriting and maps heterogeneous retrieval tools across discretized top-\(k\) truncation cutoffs into an extensive atomic retrieval action space. It then solves a two-stage MIP formulation: Stage I ("Recall-Oriented Selection MIP") identifies an optimal subset of positive atomic retrievals to maximize ground-truth coverage, while Stage II ("Precision-Oriented Composition MIP") applies structured boolean set logic (positive union minus conservative negative intersection) to eliminate irrelevant noise. The resulting globally optimal trajectories are indexed into a Golden Library. In the online stage, given an unannotated test query, OSCAR encodes the cross-modal problem context to retrieve the most similar golden demonstrations, steering the VLM planner to generate a complete tool-call and set-operation execution plan in a single forward pass, followed by binary relevance reranking via a VLM verifier.
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["Input Query (Reference Image + Modification Text)"] --> B["Atomic Retrieval Space Construction<br/>Tools × Query Rewrites × Polarity (+/-) × Top-k Discretization"]
B --> C["Recall-Oriented Selection MIP<br/>Maximize ground-truth coverage & tool diversity"]
C --> D["Precision-Oriented Composition MIP<br/>Positive Union + Conservative Negative Intersection + Difference"]
D --> E["Golden Library Construction<br/>Store offline global optimal trajectories & context embeddings"]
E --> F["Optimization-Steered Online Inference<br/>Similar trajectory demos steer VLM planner in single pass"]
F --> G["Final Reranked Retrieval Results"]
Key Designs¶
1. Atomic Retrieval Space Construction: Decoupling Multimodal Retrieval into Discrete Action Units
To address the lack of structured, discrete planning spaces in conventional heuristic agents, OSCAR decomposes complex user intent into standardized atomic retrieval tuples \(r = (f, \hat{q}, p, k)\). Here, \(f \in \mathcal{T}\) denotes a specific retrieval tool (encompassing multimodal joint embeddings and caption-based text retrievers), \(\hat{q} = \{q_{img}, \hat{q}_{txt}\}\) represents visual attributes or semantic constraints extracted and rewritten by a VLM from the original instruction, \(p \in \{+, -\}\) specifies polarity (positive for mandatory inclusion, negative for explicit exclusion), and \(k \in \mathcal{K} = \{k_1, k_2, \dots, k_{max}\}\) represents discretized top-\(k\) candidate cutoffs (stepped by 5 from 5 to 50). Taking the Cartesian product constructs a rich decision space \(\mathcal{R}\) of 1,182 atomic retrievals per sample. Monotonicity (\(S_{k_1} \subset S_{k_2}\) for \(k_1 < k_2\)) is exploited by executing retrieval once at \(k_{max}\) and slicing smaller subsets, avoiding redundant model inferences.
2. Recall-Oriented Selection MIP: Global Pruning for High-Coverage Candidate Sets
To eliminate combinatorial explosion before fine-grained boolean composition, Stage I performs global pruning via a recall-oriented MIP. Binary decision variables \(x_r \in \{0, 1\}\) indicate whether positive atomic retrieval \(r \in \mathcal{R}^+\) is selected; auxiliary state variables \(c_i \in \{0, 1\}\) track whether candidate image \(i\) is covered by at least one selected retrieval, and \(t_f \in \{0, 1\}\) denotes tool activation. Grouping retrievals sharing the same tool, query, and polarity into a family \(\mathcal{F}\) enforces truncation exclusivity \(\sum_{r \in \mathcal{F}} x_r \le 1\). The objective balances positive coverage, negative noise penalty, and tool diversity:
where \(\lambda_{div}\) regularizes against single-model myopia. Solving this yields an optimal positive subset \(\mathcal{R}^{+*}\), inducing a compact, high-recall candidate universe \(\mathcal{U} = \bigcup_{r \in \mathcal{R}^{+*}} \mathcal{S}_r\).
3. Precision-Oriented Composition MIP: Conservative Boolean Logic for Noise Elimination
While \(\mathcal{U}\) guarantees high ground-truth recall, it inevitably contains noise because negative constraints have not yet been applied. OSCAR refines \(\mathcal{U}\) using a structured two-clause boolean formulation:
Crucially, the negative clause uses Conservative Intersection: a candidate is excluded only when all selected negative tools unanimously agree it matches the unwanted concept, preventing accidental deletion of valid targets due to single-tool hallucinations. In the MIP formulation, \(u_i \in \{0, 1\}\) tracks positive union coverage, \(v_i \in \{0, 1\}\) tracks negative intersection coverage, and \(z_i = 1 \iff u_i = 1 \land v_i = 0\) indicates retention in \(\mathcal{S}_{final}\). The solver maximizes ground-truth retention while penalizing non-targets:
The resulting plan \((\mathcal{R}^{+**}, \mathcal{R}^{-*})\) constitutes the mathematically optimal trajectory for the training instance.
4. Optimization-Steered Online Inference: Few-Shot Generalization of Planning Logic
During online inference, ground-truth labels are absent, precluding online MIP solving. OSCAR resolves this by constructing a cross-modal Golden Library: Qwen3-VL-32B generates a caption for reference image \(q_{img}\), which is concatenated with modification query \(q_{txt}\) and encoded into a dense vector via Qwen3-Embedding-8B to serve as an index key pointing to the offline MIP trajectory. At test time, top-\(N\) similar trajectories are retrieved via cosine similarity as in-context demonstrations for the VLM planner (Qwen3-VL-32B). Rather than memorizing instance-specific answers, the planner abstracts transferable meta-strategies—such as choosing suitable tools, identifying exclusion intent, assigning polarities, and calibrating \(k\). The planner generates tool calls and a set_operation in a single pass. Finally, a VLM verifier computes binary logit relevance scores to produce the final ranking:
A Worked Example¶
Consider a FashionIQ query: "purple dress with black belt, is shorter floral patterned and has a belt, remove leaves":
1. Intent Decomposition & Retrieval Generation: Guided by golden demonstrations, the planner recognizes the attribute changes and generates positive queries: "Short purple floral dress with black belt..." (invoking QQMM_embed_v2 with top-\(k=50\); invoking Qwen3_Embed_8B caption search with top-\(k=50\)) and a negative query targeting absent elements: "Mid-long purple dress with floral embroidery and no belt" (invoking ops_embedding with top-\(k=10\)).
2. Structured Set Operation: The agent executes set_operation by taking the union of positive retrievals, computing the intersection of negative retrievals, and performing set difference.
3. Verification & Reranking: Dresses that matched the floral motif but retained unwanted features or background leaves are cleanly subtracted by the difference operation, shrinking the candidate pool and enabling the verifier to rank the true target dress 1st.
Key Experimental Results¶
Main Results¶
OSCAR was evaluated across three public benchmarks (CIRCO, CIRR, FashionIQ) and consistently outperformed state-of-the-art baselines across all metrics. The table below details performance on CIRCO and CIRR:
| Dataset / Setting | Metric | OSCAR (Ours) | Best Baseline (Model) | Relative Gain |
|---|---|---|---|---|
| CIRCO (Zero-shot, Multi-GT) | mAP@5 | 56.54 | 45.92 (QQMM-embed-v2) | +23.13% |
| CIRCO (Zero-shot, Multi-GT) | mAP@10 | 58.53 | 47.13 (QQMM-embed-v2) | +24.19% |
| CIRCO (Zero-shot, Multi-GT) | mAP@25 | 61.92 | 50.39 (QQMM-embed-v2) | +22.88% |
| CIRCO (Zero-shot, Multi-GT) | mAP@50 | 62.67 | 51.45 (QQMM-embed-v2) | +21.81% |
| CIRR (Real-world, Single-GT) | Recall@1 | 51.18 | 43.13 (XR / Agentic) | +18.67% |
| CIRR (Real-world, Single-GT) | Recall@5 | 79.50 | 74.02 (FiRE / CIR-Dedicated) | +7.40% |
| CIRR (Real-world, Single-GT) | Recall@10 | 87.45 | 83.09 (XR / Agentic) | +5.25% |
| CIRR (Real-world, Single-GT) | Recall@50 | 96.56 | 96.77 (RzenEmbed-v2-7B) | -0.22% |
| FashionIQ (Multi-category Average) | Recall@10 | 43.73 | 43.19 (RzenEmbed-v2-7B) | +1.25% |
| FashionIQ (Multi-category Average) | Recall@50 | 67.97 | 64.84 (RzenEmbed-v2-7B) | +4.82% |
Ablation Study¶
Table 3 investigates the essential contributions of golden trajectory demonstrations and set-theoretic operations across CIRCO, CIRR, and FashionIQ:
| Config | CIRCO m@25 | CIRCO m@50 | CIRR R@10 | CIRR R@50 | FIQ.Avg R@10 | FIQ.Avg R@50 | Note |
|---|---|---|---|---|---|---|---|
| OSCAR (Full model) | 61.92 | 62.67 | 87.45 | 96.56 | 43.73 | 67.97 | Full optimization-steered framework |
| w/o Demo. | 59.72 | 59.84 | 75.01 | 82.02 | 46.57 | 61.62 | Trajectory demonstrations removed; planning degrades |
| w/o Set.Diff. | 59.54 | 59.62 | 87.32 | 93.80 | 46.46 | 62.08 | Difference filtering omitted; false positives accumulate |
| w/o Set.Diff. & Demo. | 58.63 | 58.66 | 39.11 | 54.53 | 49.44 | 53.96 | Degrades to naive multi-channel union; CIRR R@10 drops 48.34% |
Key Findings¶
- Conservative Negative Intersection is Essential: Comparing negative filtering strategies (Table 7), negative intersection achieves 61.92 (m@25 on CIRCO), markedly surpassing aggressive negative majority (59.13) and negative union (57.26). Aggressive exclusion easily prunes ground-truth candidates mistakenly captured by imperfect negative tools, which can never be recovered during reranking.
- High Data Efficiency & Robust OOD Transfer: OSCAR constructs its golden library using only 10% of available training data. In cross-dataset transfer (Table 14), a library built on CIRR tested on CIRCO yields an R@10 of 85.25 (+5.50 gain over baseline), virtually matching the in-domain library's 85.50, proving the transferability of meta-planning logic over memorization.
- Superior Latency Over Iterative Agents: OSCAR avoids multi-turn conversational loops. Compared to AutoCIR (33.9s on CIRCO, 29.4s on CIRR) and XR (36.5s on CIRCO, 43.0s on CIRR), OSCAR lowers end-to-end latency to 23.8s and 24.1s while delivering much higher retrieval accuracy.
Highlights & Insights¶
- Bridging Operations Research and Agentic Planning: Replaces trial-and-error ReAct loops with mathematically rigorous, globally optimal mixed-integer programming (MIP), opening an optimization-steered paradigm for multi-tool agent orchestration without human demonstrations.
- Rigorous Boolean Composition for Discontinuous Constraints: Addresses the fundamental inability of continuous latent embeddings to express negative attribute exclusion, providing clean, predictable set filtering via positive unions and conservative negative intersections.
- Single-Pass Meta-Logic Transfer: By decoupling offline trajectory derivation from online few-shot in-context steering, the framework enables zero-training, plug-and-play deployment across various VLM backbones (Qwen3-VL, InternVL3.5) with minimal inference latency overhead.
Limitations & Future Work¶
- Authors' Acknowledged Limitations: OSCAR is tailored for retrieval tasks that decompose cleanly into atomic actions and set-theoretic operations. Applying it to open-ended non-retrieval reasoning requires redefining action spaces and optimization objectives.
- Identified Limitations: Offline construction involves evaluating thousands of candidate tool combinations per query, creating high upfront preprocessing compute overhead. Furthermore, online execution quality still depends on the base VLM's adherence to tool-calling schemas.
- Future Directions: Direct reinforcement learning (e.g., DPO or PPO) could internalize offline MIP trajectories directly into model parameters, eliminating library lookups. Additionally, extending boolean logic to full DNF formulations with soft-margin relaxation presents an attractive research avenue.
Related Work & Insights¶
- vs. Unified Embedding Retrieval (e.g., QQMM-embed, RzenEmbed, FiRE): Monolithic embeddings compress queries into a single latent space, suffering from single-model myopia and failing at explicit exclusion. OSCAR treats models as complementary atomic tools coordinated through discrete boolean logic.
- vs. Heuristic Agentic Retrieval (e.g., AutoCIR, MRA-CIR, XR): Prior agentic methods rely on iterative, multi-round trial-and-error interaction prone to redundant calls and high latency. OSCAR computes global offline MIP trajectories to steer single-pass VLM inference, offering formal optimality guarantees and faster execution.
Rating¶
- Novelty: ⭐⭐⭐⭐⭐ Formulates agentic CIR as a two-stage MIP trajectory optimization problem with boolean set algebra, establishing a novel offline-online paradigm.
- Experimental Thoroughness: ⭐⭐⭐⭐⭐ Validated across three public benchmarks and real-world industrial photo galleries, complete with ablation, latency, OOD, and scalability analyses.
- Writing Quality: ⭐⭐⭐⭐⭐ Clear mathematical formulations, rigorous notation, cohesive narrative flow, and thorough documentation of design rationale and negative results.
- Value: ⭐⭐⭐⭐⭐ Demonstrates how combinatorial optimization can ground multimodal agentic planning, serving as a blueprint for tool-use systems beyond retrieval.