acceptodds
Under review as a conference paper at ICLR 2027

CARTA: Composing Deep-Search Tasks with Relational Contracts

Abstract

Training deep-search agents requires tasks whose web evidence jointly constrains the answer: clues chained through intermediate entities (depth), conditions converging on one entity (branching), and distinct paths closing a loop on the same entity pair (coupling). Longer chains need not add the latter two, so composition is a design variable, not a byproduct of length. Yet composition is not enough: in graph-based synthesis, realizing a graph as a question can silently drop a relation or break an identity binding while the answer stays valid, so checking the answer cannot establish whether structure was preserved.We introduce CARTA (Compositional Answer-Rooted Task Assembly), which treats relational structure as a checkable specification. Three operations (Extend, Branch, Couple) compose answer-rooted graphs; the resulting structure compiles into a Relational Contract of relation obligations and identity constraints, against which each realized question is audited, localizing violations for revision. With SFT alone and at matched example count, CARTA data trains stronger agents than recent synthesis corpora across benchmarks at two backbone scales. Further experimental analysis shows that mixing composition levels beats either single level, that contract-guided realization raises whole-query conformance from to and lifts downstream accuracy by – points, and that selecting rollouts by contract score beats random selection among equally correct ones. Treating relational structure as something to specify and check, rather than to infer from answer correctness, turns structure into a supervision signal that trains measurably stronger agents.

Primary area:
applications to computer vision, audio, language, and other modalities
Keywords:
Deep-search agents, Synthetic training data, Graph-based task synthesis

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_KJVNOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes CARTA, a framework for synthesizing structurally controlled deep-search tasks using relational contracts. CARTA introduces three graph construction operations, EXTEND, BRANCH, and COUPLE, to compose relational structures involving depth, branching, and cross-path coupling. The resulting graphs are compiled into explicit relational contracts that specify relation obligations and entity identity constraints. These contracts guide question realization, structural verification, targeted revision, and teacher trajectory selection.

The authors evaluate CARTA using supervised fine-tuning on Qwen3.5-4B and Qwen3.5-9B across three deep-search benchmarks: BrowseComp, BrowseComp-ZH, and xbench-DeepSearch-2510. Under matched training conditions, CARTA consistently outperforms REDSearcher and OpenSeeker-v1. Additional experiments investigate structural composition, realization fidelity, trajectory selection, and the reliability of generated tasks.

Critical strengths

S1. A coherent framework for structure-aware task synthesis. The paper addresses an important limitation of existing deep-search data synthesis approaches: generating longer reasoning chains does not necessarily ensure relational diversity or consistency. The proposed EXTEND, BRANCH, and COUPLE operations, together with explicit relational contracts, provide a systematic way to construct and verify compositional search tasks. The integration of construction, realization, and trajectory selection is a meaningful contribution.

S2. Strong empirical results with useful controlled analyses. CARTA consistently outperforms the evaluated baselines across three benchmarks and two model scales. The authors also provide stage-specific ablations, including matched-source-graph realization comparisons and trajectory selection from answer-correct rollouts. These experiments go beyond aggregate benchmark improvements and provide evidence for the utility of preserving relational structure during task synthesis.

Critical weaknesses

W1. The independent contribution of relational composition remains insufficiently isolated. Although the paper introduces three graph construction operations, the structural enrichment experiments vary depth, branching, and coupling jointly. Consequently, it is difficult to determine whether the improvements primarily arise from deeper reasoning chains, branching constraints, coupling structures, or their interactions. The current results support the overall framework but provide limited evidence for the individual necessity of each construction operation. This also makes it harder to assess the contribution beyond existing graph-based synthesis approaches.

W2. The reliability and efficiency of contract-based verification require further justification. The structural conformance evaluation relies substantially on LLM-based judges, and the authors acknowledge that the operational audit can miss certain unlicensed relations. While human calibration is provided, the calibration subsets are relatively small. Moreover, CARTA requires multiple model calls, retrieval operations, and iterative verification for each synthesized task. A more explicit analysis of generation cost, acceptance rate, and performance gains under matched computational budgets would strengthen the practical significance of the framework.

Questions for authors

Q1. Can the authors provide a more fine-grained ablation that independently varies depth, branching, and coupling while controlling the remaining structural properties? This would help clarify which relational patterns contribute most to downstream improvements.

Q2. How robust are the reported structural conformance improvements to the choice of LLM-based evaluator? Could the authors provide additional human validation or cross-judge evaluations, particularly for violations involving additional relations between already licensed entity pairs?

Q3. What is the end-to-end cost of generating 5,000 accepted CARTA tasks, including rejected candidates, verification, and revision? How does CARTA compare with the graph-to-query baseline when total generation cost is matched, rather than only the planning-and-revision budget?

Q4. How do the authors assess potential benchmark contamination or near-duplicate overlap between synthesized tasks and evaluation benchmarks? Since the current prevention mechanism primarily excludes benchmark-related search terms and domains, would an additional post-generation overlap audit affect the reported results?

7 comments
AuthorsOpenReview ↗

Response to W1 & Q1: Contributions of Relational Composition

Thank you for your constructive feedback on the contributions of depth, branching, and coupling. We provide additional experimental evidence to clarify the practical value of these relational structures.

1. Component-level Relation-Deletion Analysis

Removing BRANCH and COUPLE constraints increases alternative-answer discovery by 11.3 and 6.7 percentage points, respectively, demonstrating that these relations contribute meaningful answer-disambiguating constraints.

We conduct a within-task leave-one-relation-out analysis on accepted CARTA tasks. For each task, we remove one BRANCH or COUPLE clause while preserving the remaining applicable relations and identity constraints, with minimal grammatical adjustments. The same independent evidence-backed solver evaluates the original and modified questions under identical retrieval budgets.

Removed relationBeforeAfterIncreaseMcNemar p
BRANCH2.5%13.8%+11.3 pp0.00028
COUPLE2.5%9.2%+6.7 pp0.039

Both removals significantly increase the discovery of alternative satisfying answers. These results demonstrate that BRANCH and COUPLE impose meaningful constraints on the answer space rather than merely increasing graph complexity.

2. Structural Composition and Downstream Training

The original Low/High/Mixed experiment provides complementary training-level evidence. Under matched training examples, source counts, trajectory lengths, tool calls, and supervised tokens, Mixed consistently outperforms both Low and High across all three benchmarks.

StructureBrowseCompBC-ZHxbench-2510
Low43.050.548.3
High46.754.653.7
Mixed48.856.955.7

Mixed improves over Low by 5.8/6.4/7.4 percentage points and over High by 2.1/2.3/2.0 points, respectively. These results show that combining different structural composition levels provides more effective training supervision than either level alone.

3. Interpretation

Together, these experiments demonstrate the practical value of relational composition at both the task and training levels: BRANCH and COUPLE provide meaningful answer-disambiguating constraints, while diverse structural compositions improve downstream SFT performance.

Combined with the structural guarantees established by Lemma 1 and Proposition 1, these findings provide complementary theoretical and empirical support for CARTA's controllable relational composition framework.

AuthorsOpenReview ↗

Response to W2, Q2 & Q3: Reliability and Efficiency of Contract-Based Verification

We provide additional cross-judge evaluations, independent human validation, targeted error-detection experiments, and synthesis cost analyses to address the reviewer's concerns.

1. Reliability of Structural Conformance Evaluation (W2 & Q2)

We appreciate the concern regarding LLM-based evaluation, particularly the possibility of missing additional relations between already licensed entity pairs. We conducted three complementary evaluations to directly address this issue.

(1) Strict relation-level evaluation with cross-family judges.

We re-evaluated the same 480 outputs from 240 paired source graphs, without regeneration or filtering, using a stricter relation-level protocol. Unlike the original pair-level addition check, the new protocol examines every expressed relation and flags unlicensed predicates even between already licensed entity pairs, while allowing equivalent paraphrases and valid inverse relations.

JudgeGraph-to-QueryCARTAImprovement
GPT-4o70.8%83.3%+12.5 pp
Gemini-3-Flash-Preview69.6%82.9%+13.3 pp

Although the stricter protocol lowers absolute conformance relative to the original 72.9%/86.3%, CARTA retains a substantial 12.5–13.3 pp advantage across both evaluator families. This directly addresses the identified blind spot and shows that the structural-fidelity improvement is not an artifact of the original pair-level check.

(2) Independent human validation.

We additionally randomly sampled 60 source graphs and both methods' outputs (120 questions) for independent blind annotation by two annotators. Their inter-annotator agreement reached Cohen's κ = 0.87 before adjudication.

Against the adjudicated human labels, GPT-4o and Gemini achieved 94.2% and 95.0% overall agreement, respectively, with violation-detection rates of 88.9% and 92.6%. We also report Wilson 95% confidence intervals to reflect uncertainty, particularly for the 27 human-confirmed violations.

(3) Targeted minimal-edit evaluation.

We constructed 180 examples from 60 human-confirmed conforming questions, including original questions, versions with one added unlicensed predicate, and valid paraphrases. GPT-4o and Gemini detected added predicates at rates of 91.7% and 93.3%, respectively, while maintaining low false-rejection rates (1.7–5.0% across the original and paraphrase conditions).

Together, these results demonstrate that CARTA's structural-fidelity advantage remains robust under stricter relation-level verification, cross-family evaluation, and independent human calibration. We will include the full protocols and uncertainty estimates in the revision, while continuing to characterize automated conformance as an estimate rather than a formal guarantee.

2. End-to-End Generation Cost and Efficiency (W2 & Q3)

We provide additional accounting covering rejected candidates, model calls, tool calls, and token consumption.

(1) Full-scale generation cost.

Producing 5,000 accepted CARTA tasks requires approximately 5,556 candidate attempts (90% acceptance rate), including 556 rejected or failed attempts.

MetricTotal
Candidate attempts5,556
LLM calls157,222
Tool calls100,789

Including unsuccessful attempts, this corresponds to approximately 31.4 LLM calls and 20.2 tool calls per accepted task. Mean synthesis runtime is approximately four minutes per task. Teacher trajectory generation and SFT are excluded from these synthesis totals.

(2) Generation cost and structural-fidelity comparison.

We additionally re-tallied the original 240-graph realization experiment using total LLM calls and token consumption, rather than only planning-and-revision budgets.

MethodLLM callsTokensConformance
Graph-to-Query6,43246.8M72.9%
CARTA6,79252.1M86.3%

CARTA improves whole-query structural conformance by 13.3 pp with only 5.6% more LLM calls and 11.3% more tokens.

Separately, the matched-source-graph SFT experiment (Table 2) shows downstream improvements of +6.1/+4.1/+6.6 pp with supervised tokens matched within 1%.

These results support the practical training value of contract-guided realization, delivering substantial structural-fidelity and downstream performance improvements with modest additional generation overhead.

We will incorporate these analyses into the revised paper. We hope the additional evidence addresses the reviewer's concerns and supports a more favorable assessment of our work.

AuthorsOpenReview ↗

Response to Q4: Benchmark Contamination and Near-Duplicate Overlap

Beyond the benchmark-related keyword and domain exclusions described in the paper, we conducted an additional post-generation overlap audit covering all 5,000 accepted CARTA tasks against the three evaluation benchmarks.

The audit combines normalized exact matching, cross-lingual semantic retrieval using BGE-M3 (top-5 candidates, cosine similarity above 0.80), and human verification. The overlap criteria consider the target answer, core relational conditions, and their composition rather than surface wording alone.

BenchmarkExact matchesNear-duplicate candidatesConfirmed overlap
BrowseComp060
BrowseComp-ZH030
xbench-2510050
Total0140

Among the 14 candidates, 11 share only entities or topics but have different target answers. The remaining three share a target answer but differ in their essential relational conditions and composition.

No question-level overlap was confirmed, and no training examples required removal, leaving the reported results unchanged.

Reviewer_b4JwOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The authors propose CARTA, a synthetic task generation framework that composes deep-search tasks with explicit relational structure and checks that this structure survives question writing. The framework consists of three components: (1) three graph operations (EXTEND, BRANCH, COUPLE) that build answer-rooted graphs over a verified Wikidata-based knowledge graph to combine depth, branching, and coupling, (2) a Relational Contract compiled from each graph that lists relation obligations and identity constraints, and guides clause-by-clause question writing and a model-based audit-and-revise loop, and (3) contract-based scoring of teacher trajectories to select training demonstrations. The authors fine-tune Qwen3.5-9B and Qwen3.5-4B on 5,000 tasks per corpus, with trajectories regenerated by a shared DeepSeek-V4-Pro teacher, and evaluate on BrowseComp, BrowseComp-ZH, and xbench-DeepSearch-2510. They report that CARTA data outperforms REDSearcher and OpenSeeker-v1 on all three benchmarks at both scales, for example 52.4 versus 44.3 on BrowseComp at 9B. They also report that contract-guided realization raises whole-query conformance from 72.9% to 86.3%, which they claim shows that specifying and checking relational structure is a useful supervision signal.

Critical strengths

S1. The authors tackle an important problem in search-task synthesis, namely that a generated question can drop or alter intended relations while its reference answer remains valid, and they measure this failure directly.

S2. The authors compare synthesis corpora under a controlled protocol in which all corpora are re-solved by the same teacher with the same tools and answer filter at equal example counts.

Critical weaknesses

W1. Insufficient validation of relational structure as meaningful supervision

Although CARTA improves downstream accuracy, the experiments do not establish whether the constructed relations are necessary for solving the tasks or whether contract-selected trajectories genuinely integrate evidence across them.

W1.1. The necessity of the constructed relations is not established. CARTA verifies that generated questions preserve the intended relations, but this does not establish whether those relations are required to identify the answer. The filters only reject single-page shortcuts and identifying cues (Appendix B.5), while Appendix B.12 explicitly acknowledges that the tasks are not shown to be unshortcuttable. The authors should evaluate whether removing individual relational constraints, particularly coupling edges, leaves the answer uniquely identifiable.

W1.2. Contract-based trajectory selection does not verify evidence-grounded reasoning. The contract score evaluates relations mentioned in reasoning traces rather than their support in retrieved evidence (Section 3.3). A separate analysis shows that correct trajectories cover 93% of required relations in reasoning but only 64% in retrieved evidence (Table 8). This raises concerns about whether the selection criterion rewards genuine evidence integration rather than verbal coverage. The authors should compare against evidence-grounded trajectory selection and measure evidence coverage in the selected trajectories.

W2. Insufficient validation of CARTA's specific contributions

The experiments demonstrate improvements over the evaluated baselines but do not sufficiently establish the additional benefits of CARTA's formalization and contract-guided auditing over existing alternatives.

W2.1. An important baseline is missing. WebShaper [1] also uses formal task representations and compositional construction to synthesize training data for search agents. However, Table 1 compares CARTA only against REDSearcher and OpenSeeker-v1. The authors should include WebShaper [1] under matched training conditions to establish whether CARTA improves over existing formalization-driven task synthesis.

W2.2. The benefit of contract-guided auditing is not isolated. CARTA uses its relational contract to locate errors in generated questions and guide targeted revision (Section 2.3). Although revision improves question quality on accepted tasks (Appendix B.11, Table 6), this does not show that contract-guided revision is better than generic LLM revision. Table 3 cannot isolate this benefit either, because CARTA and the graph-to-query baseline start from different initial questions. The authors should compare contract-guided revision with generic revision that receives the same contract but no located violations, using the same initial questions and revision budget.

[1] Tao, Zhengwei, et al. "Webshaper: Agentically data synthesizing via information-seeking formalization." International Conference on Learning Representations. Vol. 2026. 2026.

Questions for authors

Please refer to W1 and W2.

7 comments
AuthorsOpenReview ↗

Response to W1: Insufficient validation of relational structure as meaningful supervision

W1. Insufficient validation of relational structure as meaningful supervision

Although CARTA improves downstream accuracy, the experiments do not establish whether the constructed relations are necessary for solving the tasks or whether contract-selected trajectories genuinely integrate evidence across them.

W1.1. The necessity of the constructed relations is not established.

W1.2. Contract-based trajectory selection does not verify evidence-grounded reasoning.

Thank you for your constructive feedback on the role of relational structure in training supervision. We provide a detailed yet concise response to W1 below, supported by additional experiments.

W1.1. Necessity of Constructed Relations

Removing BRANCH and COUPLE constraints increases alternative-answer discovery by 11.3 and 6.7 percentage points, respectively, providing direct evidence that these relations contribute to answer disambiguation.

We conduct a leave-one-relation-out analysis on accepted CARTA tasks. For each task, we remove one BRANCH or COUPLE clause with minimal grammatical adjustments, preserving the remaining applicable relations and identity constraints. The original and modified questions are evaluated by the same independent evidence-backed solver under identical retrieval budgets.

Removed relationOriginalAfter removalIncreaseMcNemar p
BRANCH2.5%13.8%+11.3 pp0.00028
COUPLE2.5%9.2%+6.7 pp0.039

Both removals significantly increase the discovery of alternative satisfying answers. Thus, BRANCH and COUPLE impose meaningful constraints on the answer space rather than merely increasing surface complexity. These results characterize marginal disambiguation under a fixed retrieval budget.


W1.2. Evidence Grounding in Trajectory Selection

Contract-selected outperforms Evidence-only selection across all three benchmarks (+1.7/+1.6/+2.3 pp), showing that relational alignment is an effective supervision-selection signal beyond maximizing evidence coverage alone.

Table 8 measures required-edge coverage in two different places: 93% in reasoning traces and 64% in retrieved evidence for successful trajectories. To examine whether reasoning-side coverage provides useful supervision rather than merely rewarding relational mentions, we add the Evidence-only selection baseline you suggested.

We use the same 3,000 tasks and five teacher rollouts per task as in §3.3. All strategies select one trajectory from the identical answer-correct pool and use the same SFT configuration. We measure R (relations correctly used in reasoning), E (relations supported by retrieved evidence), and J (relations satisfying both).

SelectionBrowseCompBC-ZHxbench-2510R ↑E ↑J ↑Tool calls
Random Correct48.055.947.392.8%63.5%61.0%25.6
Evidence-only50.658.450.094.1%81.2%78.6%28.9
Contract-selected52.360.052.397.6%67.9%66.7%26.1

Evidence-only achieves higher evidence coverage (81.2% vs. 67.9%), while Contract-selected yields better downstream accuracy on all three benchmarks with fewer tool calls (26.1 vs. 28.9). The advantage persists when restricting comparisons to trajectories whose tool-call counts differ by at most 10% (+1.5/+1.4/+2.0 pp).

These results establish relational alignment as a useful trajectory-selection criterion distinct from evidence coverage. We will clarify that the contract score measures relational reasoning alignment, rather than certifying evidence-grounded correctness, and report R, E, and J separately.

AuthorsOpenReview ↗

Response to W2.1: An important baseline is missing.

Thank you for highlighting WebShaper [1] as an important formalization-driven synthesis baseline. We provide additional methodological comparisons and empirical evidence on structural coverage and relational fidelity.

1. Matched SFT Comparison

WebShaper reports 5,000 training trajectories but publicly releases only 500 QA examples and their formalizations. We could not identify a complete public synthesis implementation sufficient to reproduce its training corpus under our matched SFT protocol. Therefore, a faithful 5,000-example matched comparison is not feasible with the available resources.

Our comparisons with REDSearcher [2] and OpenSeeker-v1 [3], both recent Deep Search data synthesis methods, already provide controlled evidence of CARTA's downstream training utility. These experiments evaluate the effectiveness of different synthesized training corpora under a shared SFT protocol. The additional WebShaper analyses below complement these training comparisons by directly examining CARTA's methodological contributions.

2. Methodological Distinction and Structural Coverage

WebShaper uses Knowledge Projections and an Agentic Expander for formalization-driven task construction and validation. CARTA instead explicitly controls depth, branching, and coupling through EXTEND, BRANCH, and COUPLE, and compiles the resulting graphs into Relational Contracts for structure-preserving question realization, localized auditing, and teacher trajectory selection.

We compare WebShaper's 500 publicly released QA examples and formalizations with 500 CARTA tasks sampled using a fixed seed, applying the same structural metrics.

Structural metricWebShaperCARTA
Observed structural cells3069
Maximum answer degree48
Maximum min-fill treewidth34

CARTA covers 69 structural configurations versus WebShaper's 30, including 29 of WebShaper's observed configurations and 40 additional ones, primarily involving higher answer-side branching and more complex coupling.

Both methods can generate depth, branching, and coupling. CARTA's contribution lies in explicitly controlling their composition, with broader observed coverage of the structural parameter space.

3. Structural Fidelity

Beyond constructing relational structures, CARTA explicitly verifies whether the generated questions preserve them. We re-evaluate both methods using a unified two-stage blind protocol that extracts relations from question text and aligns them with each method's declared structure, using the same GPT-5.4 judge and consistent evaluation criteria.

We report relation recall (Expr.), dropped relations (Drop), and altered relations (Alt.) following the metric definitions in Appendix B.10 of our paper.

MetricWebShaperCARTADifference
Relation Recall (Expr.) ↑44.4%92.5%+48.1 pp
Dropped (Drop) ↓25.8%5.4%−20.4 pp
Altered (Alt.) ↓29.8%2.1%−27.7 pp

CARTA achieves 48.1 pp higher relation recall, while reducing dropped relations by 20.4 pp and altered relations by 27.7 pp. These results demonstrate substantially stronger preservation of intended relational obligations in the generated questions.

This comparison uses each method's own formalization rather than identical source graphs.

Together, these results highlight CARTA's two key methodological contributions: explicitly controlling relational composition and preserving the intended structure through question realization.

[1] Tao, Zhengwei, et al. "Webshaper: Agentically data synthesizing via information-seeking formalization." International Conference on Learning Representations. Vol. 2026. 2026.

[2] Chu, Zheng, et al. "REDSearcher: A Scalable and Cost-Efficient Framework for Long-Horizon Search Agents." arXiv preprint arXiv:2602.14234 (2026).

[3] Du, Yuwen, et al. "OpenSeeker: Democratizing Frontier Search Agents by Fully Open-Sourcing Training Data." arXiv preprint arXiv:2603.15594 (2026).

AuthorsOpenReview ↗

Response to W2.2: The benefit of contract-guided auditing is not isolated.

On identical initial questions and Relational Contracts, obligation-localized revision improves whole-query conformance from 79.17% to 85.83% (+6.67 pp; McNemar p = 0.017).

To isolate violation localization from contract access, we conduct a paired ablation on 240 fixed initial questions using the same revision model and matched revision budgets. We compare No Revision, Generic Revision, Generic + Contract, and Contract-localized Revision. Crucially, both Generic + Contract and Contract-localized receive the complete contract and overall audit feedback; only the latter additionally receives localized violation types and affected obligations or identity bindings. All outputs are evaluated by the same independent blind evaluator.

Revision methodExpr. ↑Drop ↓Alt. ↓Add ↓Split ↓Merge ↓Conformance ↑
No Revision88.97.63.56.99.77.372.50%
Generic89.66.93.56.39.06.375.00%
Generic + Contract91.25.83.05.06.34.279.17%
Contract-localized93.24.42.43.84.22.185.83%

Providing the contract improves conformance from 75.00% to 79.17%, while localized feedback provides a further +6.67 pp improvement with the contract held fixed. In the paired comparison, 28 questions become conforming and 12 change in the opposite direction, yielding 16 additional conforming questions (two-sided exact McNemar test, p = 0.017). Relation omissions, alterations, and identity-binding errors also decrease.

This directly isolates the incremental benefit of obligation-level violation localization beyond providing the Relational Contract itself.

Thank you again for your constructive feedback. We hope these new results provide a clearer picture of CARTA's contributions and would welcome your thoughts on whether they change your overall assessment.

Reviewer_qgGqOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper introduces CARTA, a framework for generating deep-search training tasks with explicitly controlled relational structure and contract-based verification. CARTA is a synthetic data generation and validation pipeline but this is not stated clearly. The experimental setup is designed as a controlled comparison where the only varying factor is the synthetic training corpus but this is not clearly exposed. The research question is something like “Can deep-search training data be improved by explicitly constructing, preserving, and checking relational structure (depth, branching, and coupling) instead of only validating the final answer?” but is not explicitly stated. The reader should not have to infer this from the text.

While the idea of structure-aware task generation and validation is not entirely new, CARTA's main novelty lies in introducing a reusable relational contract that explicitly encodes relation obligations and identity constraints, and employing this contract for realization auditing, targeted revision, and trajectory selection. The paper should more clearly distinguish this contribution from prior validation frameworks such as LoHoSearch, WebShaper, and QUEST.

CARTA does not actually ensure that an agent respects the relational contract at inference time. This should be made clearer. CARTA uses the relational contract during data generation. This should be made clearer.

Critical strengths

The paper introduces an explicit relational contract that captures relation obligations and identity constraints, enabling auditing and revision of generated questions beyond answer correctness. The underlying intuition, which is interesting, is that preserving the structure of a search task synthesis is a separate challenge than constructing it. Answer validation alone does not establish structural fidelity. This effect is well isolated by the comparison of several question-generation conditions, including a strong graph-to-query baseline (72.9% of generated questions satisfy whole-query structural conformance, Full CARTA increases this figure to 86.3%).

Strong empirical validation with controlled ablations. The authors show consistent gains over competing synthetic-data pipelines under matched SFT settings and isolate the effects of task composition, realization fidelity, and trajectory selection through dedicated ablations, making the evidence for the proposed approach unusually thorough. But the paper fails at expliciting why it did so.

Critical weaknesses

The primary weakness of the paper is conceptual positioning. While the empirical results are clearly presented, the manuscript does not articulate a sufficiently precise research question. It is unclear whether CARTA should be understood principally as (i) a graph-to-question fidelity framework, (ii) a synthetic task generation method, (iii) a supervision-selection mechanism, or (iv) a method for constructing higher-quality SFT corpora. The paper would benefit from explicitly stating the hypothesis being tested and clarifying how each component contributes to answering that hypothesis.

In addition, the literature review does not sufficiently distinguish CARTA from adjacent graph-aware retrieval, reasoning, and verification frameworks. The discussion focuses on introducing the Relational Contract as a novel object, but does not clearly explain what capabilities it provides beyond existing graph-based reasoning, relation-aware evaluation, or verification pipelines. A more explicit comparison would help the reader assess the methodological novelty.

Third, several core concepts are introduced without adequate exposition: SFT appears in the abstract and is central to the experimental evaluation, yet it is not defined upon first use. Readers outside the immediate agent-training literature may not immediately recognize that SFT refers to Supervised Fine-Tuning. The framework is built around verified knowledge graphs (KGs), yet knowledge graphs are largely introduced only when the formalism begins. The introduction would benefit from explaining earlier why a graph representation is the appropriate abstraction for modeling relational structure in deep-search tasks. The paper evaluates improvements through downstream SFT performance, but provides little discussion of why SFT is the chosen training paradigm. If the objective is to demonstrate that relational contracts provide higher-quality supervision, the manuscript should explicitly explain why SFT constitutes the appropriate experimental vehicle and how improvements in realization fidelity are expected to transfer into better SFT training signals.

Questions for authors

What precise problem is CARTA solving? Is the primary target loss of relational fidelity during graph-to-question realization, identity-binding failures, schema-resolution errors, or another specific failure mode?

How should the proposed Relational Contract be understood relative to prior graph-aware retrieval and verification frameworks? What functionality is provided by contract compilation and auditing that is not already captured by existing graph-constrained retrieval, evidence-verification, or relation-aware evaluation pipelines?

Can the authors provide a more explicit novelty comparison with prior graph-based agent frameworks and GraphRAG approaches? A discussion of which components are genuinely new (e.g., contract-guided realization, clause-localized auditing, trajectory selection via contract satisfaction) versus adaptations of existing ideas would help assess the methodological contribution.

The second and third contributions are supported through controlled empirical comparisons and dedicated audits. By contrast, the first contribution, namely the proposed compositional graph language and its characterization of reachable graph families, is primarily justified through formal definitions and proofs rather than comparative empirical analysis. Consequently, the paper provides stronger evidence for the utility of contract-guided realization and trajectory selection than for the practical necessity of the specific EXTEND/BRANCH/COUPLE construction formalism itself. Can the author work on how they support the three claims defined at the end of the introduction ?

7 comments
AuthorsOpenReview ↗

Response to W1 & Q1: Research Positioning and Core Hypothesis

We thank the reviewer for the constructive feedback and for recognizing the motivation behind the Relational Contract and the value of our controlled experiments.

1. W1: Research Positioning and Core Hypothesis

CARTA is an offline framework for synthesizing Deep Search training tasks and supervision data. Its central research question is: Can Deep Search training data be improved by explicitly constructing, preserving, and verifying relational structure, rather than relying solely on answer correctness?

Clarifying the four research aspects. The four categories identified in the review are not competing research directions or equally positioned contributions. Constructing high-quality SFT corpora for Deep Search agents is CARTA's overarching objective, while Synthetic Task Generation, Graph-to-Question Fidelity, and Supervision Selection are three complementary technical components serving this objective.

Specifically, task generation defines the intended relational requirements, structural-fidelity verification ensures that these requirements are preserved in the generated questions, and supervision selection identifies answer-correct teacher trajectories aligned with those requirements. The resulting corpus is evaluated through controlled Supervised Fine-Tuning (SFT) experiments.

These components jointly test our central hypothesis: preserving the intended relational requirements from task construction through question realization and supervision selection produces more effective training data.


2. Q1: Targeted Failure Modes and Contract Scope

The primary problem CARTA addresses is the loss of intended relational structure during synthetic training-data construction, particularly during graph-to-question realization. This includes three concrete failure modes:

  • Relation omission or alteration: Required relations are omitted, semantically changed, or expressed with incorrect directionality.
  • Identity-binding failures: Shared entities are incorrectly split across clauses, or distinct entities are mistakenly merged.
  • Unlicensed relations: Generated questions introduce relations not authorized by the intended task structure.

These failures can occur even when the generated question remains answer-correct. Answer correctness alone therefore cannot establish structural fidelity.

CARTA addresses this problem through Relational Composition, which explicitly constructs tasks with controlled Depth, Branching, and Coupling using EXTEND, BRANCH, and COUPLE; and through the Relational Contract, which audits and guides revision of generated questions while supporting contract-aligned teacher trajectory selection.

Regarding inference time, CARTA does not impose contracts on the trained agent's inference behavior. The Relational Contract serves as a task specification during offline data construction, not for online retrieval, agent control, or inference-time contract enforcement.

AuthorsOpenReview ↗

Response to W2 & Q2: Relational Contract and Verification Novelty

Response to W2 & Q2: Relational Contract and Verification Novelty

Thank you for recognizing the importance of structural fidelity beyond answer correctness. We clarify the specific functionality introduced by Relational Contract compilation and auditing, supported by controlled experimental evidence.

1. W2: What Is the Methodological Novelty of the Relational Contract?

CARTA's methodological contribution is not another graph representation or correctness judge, but an actionable relational task specification that connects task construction, structural auditing, targeted revision, and supervision selection.

Graph representations, LLM-based verification, and iterative revision are established techniques. CARTA builds on them by compiling the intended task structure into a reusable Relational Contract:

Rq=(Eq,Πq,a)R_q = (E_q, \Pi_q, a)

where EqE_q specifies required relational obligations, Πq\Pi_q encodes cross-relation entity identity and distinction constraints, and aa denotes the target answer.

This specification connects three technical capabilities:

  1. Structural-fidelity auditing: Checks whether the final question expresses every required relation with correct semantics and directionality, preserves entity identities across clauses, and avoids unlicensed relations.
  2. Obligation-level localization and revision: Identifies precisely which relation or identity constraint is violated, enabling targeted repair and re-auditing.
  3. Contract-based supervision selection: Reuses the same relational obligations to select answer-correct teacher trajectories aligned with the intended relational structure.

The novelty is the explicit, checkable specification of the intended task and its reuse across these stages—not the isolated use of verification or revision tools.


2. Q2: What Does Contract Compilation and Auditing Provide Beyond Existing Verification?

The key additional capability is verifying fidelity to a predefined relational task, rather than only the correctness of individual facts or the final answer.

Consider a task requiring two relational paths to share an entity and form a coupling structure. A generated question may omit one relation or incorrectly split the shared entity while retaining a valid answer. Answer verification alone cannot detect that the intended relational reasoning requirement has been lost.

More importantly, Contract auditing identifies the specific missing, altered, or unauthorized relation or violated identity binding, rather than returning only an overall correctness judgment. These violations become explicit targets for revision and subsequent verification.

We provide two controlled experiments supporting this functionality.

(1) Structural fidelity beyond direct graph prompting (original Table 3).

Strong Graph-to-Query receives the complete relation list, shared-entity identifiers, and explicit preservation instructions under matched planning-and-revision budgets.

MethodWhole-query Conformance
Strong Graph-to-Query72.9%
Full CARTA86.3%
Improvement+13.3 pp

This demonstrates that providing the complete graph does not by itself ensure faithful realization of its relational requirements.

(2) Independent benefit of obligation-level violation localization (additional experiment).

We hold the initial questions, complete Contract, revision model, and revision budget fixed, varying whether the reviser receives explicit obligation-level violation localization.

Revision settingStructural Conformance
Generic revision with full Contract79.17%
Contract-localized revision85.83%
Improvement+6.67 pp

McNemar p = 0.017. With the same initial questions, Contract information, model, and revision budget, obligation-level localization significantly improves structural conformance.

The two experiments establish complementary results: contract-guided realization improves fidelity beyond direct graph prompting, while localized violation feedback provides an additional benefit beyond generic revision with the same Contract.

AuthorsOpenReview ↗

Response to W2 & Q3: Methodological Novelty Relative to Prior Work

1. W2: Methodological Novelty

CARTA's contribution is not the use of graphs or verification alone, but explicitly constructing and preserving relational structure throughout offline training-data synthesis.

Existing methods have explored graph representations, formalization-driven task generation, and verification. CARTA introduces two complementary contributions:

  1. Relational Composition: EXTEND, BRANCH, and COUPLE explicitly control depth, branching, and coupling during task construction.
  2. Relational Contract: The constructed task's relation obligations and identity constraints are compiled into a reusable specification for auditing question realization, identifying violations for targeted revision, and selecting teacher trajectories.

The same relational requirements are used throughout task construction, question realization, and supervision selection, rather than only validating the final answer.


2. Q3: Comparison with Prior Graph-Based Methods

GraphRAG addresses a different research problem. GraphRAG improves retrieval and answer generation for existing queries, whereas CARTA synthesizes training tasks and supervision for Deep Search agents offline. GraphRAG is therefore not a directly comparable training-data synthesis method. Its retrieval mechanisms do not address preserving predefined relational requirements in newly generated training questions.

WebShaper is a directly relevant synthesis method. It uses Knowledge Projections, set operations, and an Agentic Expander for formalization-driven task construction and validation. Both WebShaper and CARTA can generate depth, branching, and coupling. CARTA differs by explicitly controlling their composition through EXTEND, BRANCH, and COUPLE, and by using Relational Contracts for structure-preserving question realization, targeted revision, and teacher trajectory selection.

We compare WebShaper's 500 publicly released QA examples and formalizations with 500 CARTA tasks sampled using a fixed seed, applying the same structural metrics. Relational fidelity is evaluated using the same GPT-5.4 judge and evaluation criteria, comparing each method's generated questions against its own formalization.

MetricWebShaperCARTADifference
Observed structural cells3069+39
Maximum answer degree48+4
Maximum min-fill treewidth34+1
Relation Recall (Expr.) ↑44.4%92.5%+48.1 pp
Dropped Relations (Drop) ↓25.8%5.4%−20.4 pp
Altered Relations (Alt.) ↓29.8%2.1%−27.7 pp

CARTA covers 69 observed structural configurations versus WebShaper's 30, including 29 shared configurations and 40 additional ones. It also achieves 48.1 pp higher relation recall, with fewer dropped and altered relations. These results provide evidence of broader observed structural coverage and stronger relational fidelity.

REDSearcher and OpenSeeker-v1 are directly relevant Deep Search data synthesis methods. REDSearcher controls task complexity through graph topology and evidence dispersion, while OpenSeeker-v1 uses Web Graph expansion, entity obfuscation, and trajectory denoising. Our matched SFT comparisons with these methods provide controlled evidence of CARTA's downstream training utility.

LoHoSearch and QUEST provide related precedents for structured task construction and verification. LoHoSearch focuses on long-horizon search benchmark construction, including structural complexity and answer verification; QUEST explores verifiable Deep Research task synthesis and rubric-guided training. CARTA focuses on preserving predefined relational requirements throughout question realization and supervision selection.

3. Summary: What Is New Versus Adapted?

Graph representations, formalization-driven synthesis, LLM-based verification, and iterative revision are established techniques. CARTA's contributions are (i) controllable Relational Composition through EXTEND, BRANCH, and COUPLE; and (ii) a reusable Relational Contract that records relation obligations and identity constraints, guides question realization, supports auditing and targeted revision, and is reused for teacher trajectory selection.

The WebShaper comparison provides empirical evidence of broader structural coverage and higher relational fidelity, while the controlled realization and revision experiments detailed in our response to W2 & Q2 support the practical value of contract-guided realization and targeted revision.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.