PaperlayerView exact revision on arXiv

Source-linked AI summary

GRADS: Graph-Regulated Agentic Data Synthesis with Controllable Difficulty

Gaocheng Yang, Ruijie Tao, Kai Ye, Senhua Zhang, Zhengqin Zhu, Ziyang Li

arXiv:2610.21167v1cs.AI

TL;DR

Synthetic tasks may look multi-hop without requiring the intended reasoning, making difficulty labels unreliable. GRADS controls synthesis through evidence-dependency graphs; across domains, it produces empirically ordered difficulty and post-training gains, with SFT raising automatic termination from 6% to above 95%.

  • Problem

    Synthetic task expansion does not reliably make added evidence necessary, so intended difficulty can diverge from empirical reasoning difficulty.

    Source: §1 · p. 2

  • Method

    GRADS grows and verifies evidence-dependency graphs, then conditions question generation on a relevant subgraph to control necessary reasoning depth.

    Source: §1 · p. 2, §4.2 · p. 5, §4.3 · p. 6

  • Results

    Across three domains, GRADS produces empirically ordered difficulty and post-training gains; SFT raises automatic-termination rate from 6% to above 95%.

    Source: §1 · p. 2, §5.5 · p. 9, §6 · p. 10

  • Takeaways & Limitations

    The 4B model approaches Sonnet 4 on GitHub and surpasses it on Physics and Security after post-training.

    Source: §5.4 · p. 8

    Under the tested 30-step budget, RL showed no separable improvement over SFT, and LLM-judged edge necessity is evidence rather than proof that solvers cannot bypass a hop.

    Source: §5.6 · pp. 9–10

Abstract

from arXiv · show

Deep research agents are increasingly deployed to retrieve precise information from large corpora, yet multi-hop, long-horizon tasks remain challenging. Synthetic data generation has emerged as a scalable solution, with existing pipelines typically expanding seed tasks to increase their apparent depth and breadth. However, this expansion does not reliably translate into necessary reasoning: newly introduced evidence may be only weakly coupled to the answer, creating a mismatch between intended and empirical difficulty. To address this problem, we introduce GRADS, a graph-guided agentic data synthesis framework with explicit difficulty control. GRADS runs a closed loop of seed selection, evidence expansion, question--answer construction, and verification while maintaining a graph of the evidence and inference dependencies required to derive each answer. At each step, it conditions generation on a relevant subgraph, preserving indispensable inference without accumulating irrelevant context. Experiments across security, software-engineering, and scientific-document domains show that GRADS consistently generates verified tasks with empirically separated difficulty distributions, as measured by independent solvers. Moreover, under matched training budgets, post-training on this data delivers consistent gains at every level: SFT raises the solution-termination rate to over 95% while cutting tool calls and turns by up to 75%, RL trims tool use by up to a further 19.5%, and on our held-out, domain-specific benchmarks, the resulting 4B model matches Sonnet~4 on software engineering and surpasses it on the scientific and security domains.

1 INTRODUCTION

GRADS addresses the gap between intended and actual reasoning difficulty by regulating evidence dependencies rather than merely enlarging questions. Across three domains, it reports empirically controllable difficulty and post-training gains.

1 INTRODUCTION

  • Synthetic QA data can train deep search agents, but agent quality depends on data that reliably exercises genuine multi-step reasoning.Deep search agents iteratively plan, search, read retrieved documents, and reason over them.Source: §1 · p. 1
  • Added evidence may be weakly coupled to answers, so nominally multi-hop questions can be solved through shortcuts and their intended difficulty may diverge from empirical difficulty.This mismatch can make difficulty labels unreliable for evaluation or curriculum design.Source: §1 · pp. 1–2
  • GRADS defines an evidence graph whose nodes are source-grounded claims and whose edges encode necessary inference, using graph depth to control and evaluate reasoning difficulty.The framework decouples exploration from difficulty control rather than assuming that added evidence is required to answer the question.Source: §1 · p. 2
  • To address large corpora and answer hallucinations, GRADS combines cleaned and clustered records with local and online search, source-span-linked claim rubrics, and verification subagents.Every item is checked before acceptance.Source: §1 · p. 2
  • Across three domains, GRADS alone among three baselines yields monotonic difficulty ordering, and matched-budget SFT beats all baselines before RL further improves efficiency.The domains are GitHub issue tracking, experimental particle physics, and security.Source: §1 · p. 2

2 RELATED WORK

Prior work expands synthetic tasks, estimates or selects difficulty, and builds deep-research benchmarks. GRADS maintains evidence and inference dependencies during synthesis and targets specialized domain corpora for both training and evaluation.

Synthetic Data Generation for Agentic Tasks

  • Synthetic-data pipelines expand tasks or graphs, but isolated-seed generation can leave added evidence weakly connected to answers; GRADS tracks evidence and inference dependencies throughout synthesis.Earlier approaches include task expansion, graph sampling, and end-to-end synthesis pipelines.Source: §2 · pp. 2–3

Difficulty-Aware Data Selection and Curriculum

  • Difficulty-aware curricula select or adapt training data, while policy drift can make existing difficulty estimates unreliable as training progresses.GRADS extends difficulty control into synthesis by conditioning expansion on a dependency subgraph and checking that introduced evidence is necessary.Source: §2 · p. 3

Datasets and Benchmarks for Deep Research

  • Deep-research benchmarks include expert-written, fixed-corpus, and synthesized suites, whereas GRADS targets heterogeneous domain corpora and treats questions and evidence graphs as post-training artifacts as well as evaluation material.The named domains are GitHub, physics, and security.Source: §2 · p. 3

3 QUESTION EXPANSION WITH GRAPH STRUCTURE

GRADS grows an evidence graph online and computes its complexity deterministically to control question difficulty. Expansion retains necessary inference and increases depth toward the requested threshold.

3 QUESTION EXPANSION WITH GRAPH STRUCTURE

  • The section defines online graph growth and deterministic complexity as the basis for difficulty control, with agent use of the graph deferred to §4.Source: §3 · p. 3

3.1 GRAPH STRUCTURE AND DEFINITIONS

  • An evidence graph is a DAG of claims linked by necessary dependencies; its node types distinguish core conclusions, inference steps, and supporting details.Depth measures the longest necessary chain, breadth independent branches converging on the anchor, size vertices, and information flow squared throughput through intermediate hubs.Source: §3.1 · pp. 3–4
  • A weighted score combines graph size, depth, breadth, and information flow, with depth and information-flow weights dominant so wide-but-shallow graphs are not mistaken for deep ones.Source: §3.1 · p. 4
  • Difficulty bands are governed by depth; the interval between Medium and Hard is left unassigned, and breadth is capped per band so the control targets depth rather than width.Source: §3.1 · p. 4

3.2 EXPANSION PROCESS

  • Expansion proposes graph edits, verifies which added hops are necessary, then commits the edit that most extends the longest necessary chain until the target depth is reached.The loop begins from a seed graph and re-explores until the graph reaches the requested depth threshold.Source: §3.2 · p. 4

4 METHOD

GRADS separates evidence exploration from difficulty control, using an evidence graph to guide synthesis and select context at a requested depth. Its agent workflow combines retrieval, question-and-answer construction, and verification, while preserving source provenance.

4 METHOD

  • GRADS decouples open-ended synthesis from difficulty control, using graph structure to regulate the context supplied for each question.The workflow is designed to accumulate reasoning depth through alternating exploration and generation.Source: §4 · p. 4, §4.2 · p. 5

4.1 DATA PREPROCESSING

  • Each synthesis run starts from a deduplicated, clustered record corpus and uses structured lookup, BM25 retrieval, and online tools to expand evidence.Clustering bounds initial exploration to a coherent provenance neighborhood.Source: §4.1 · pp. 4–5
  • Across expansion rounds, the graph adds provenance-linked claims and necessary-dependency edges until the requested reasoning-depth band is reached.A target-depth subgraph is then selected and verbalized as one multi-hop question.Source: Figure 1 · p. 5

4.2 AGENTIC MAIN LOOP

  • A stateless Brain interleaves exploration and generation: role-decomposed agents retrieve evidence, draft an answer and rubric, form a question, and verify the item.The Long History stores explored text as immutable events, while graph nodes retain event pointers rather than copying the text.Source: §4.2 · p. 5, Figure 2 · p. 6
  • Accepted items undergo deterministic checks and two adversarial LLM reviews of source entailment and whether each inference step is necessary.The resulting verification record links claims to verbatim source spans and checks their reasoning dependencies.Source: §4.2 · pp. 5–6

4.3 CONTEXT MANAGEMENT

  • The Selector chooses a feasible subgraph containing the answer anchor and its necessary ancestors, with bounded breadth and depth closest to the requested target.A pure code function computes graph complexity; a necessity filter and graph verification test whether edges add indispensable hops and whether nodes and edges remain source-faithful.Source: §4.3 · pp. 6–7

5 EXPERIMENTS

Across three real-world domains, GRADS produces data that improves post-training performance and yields controllable empirical difficulty. SFT on GRADS trajectories beats the raw model and every synthesis baseline in every domain; RL adds tool-use efficiency, while several scope and validation limits remain.

5.1 DOMAINS AND SETUP

  • The study evaluates GitHub issue tracking, CMS experimental-physics notes, and security traces, using an unmodified tool-using solver with a 25-turn cap to measure empirical difficulty.The corpora span roughly 1.07M GitHub records, 5.9k physics files, and 18.8k security traces.Source: §5.1 · p. 7

5.2 DATA-SYNTHESIS MAIN RESULTS

  • Depth has the strongest negative correlation with rubric-graded solver score (pooled Spearman rs = −0.45), ahead of information flow (−0.39) and graph size (−0.38).Breadth is only weakly related (−0.17), motivating the use of depth alone to band difficulty.Source: §5.2 · pp. 7–8

5.3 POST-TRAINING: SFT MAIN RESULTS

  • SFT on GRADS trajectories beats the raw model and every synthesis baseline in every domain.The comparison uses the same benchmark and training configuration across arms, so only the data differs.Source: Figure 4 · p. 8, §5.3 · p. 8

5.2 DATA-SYNTHESIS MAIN RESULTS

  • GRADS is the only synthesis method whose delivered depth rises monotonically with requested difficulty, with solver scores falling monotonically across the same bands.The bands are Easy at depth ≤3, Medium at depth 4–5, and Hard at depth ≥8; TaskCraft and WebShaper stay flat, while Claude-Code does not separate Medium and Hard.Source: §5.2 · pp. 7–8

5.4 POST-TRAINING: RL MAIN RESULTS

  • GRPO yields small positive score estimates that are not statistically separable from SFT under the 30-step budget, while reducing tool calls by up to 19.5%.After post-training, the 4B model approaches Sonnet 4 on GitHub and surpasses it on Physics and Security.Source: §5.4 · p. 8

5.5 DISCUSSIONS

  • Across all three domains, solver scores decline both as capability weakens across model tiers and as problems become harder for each model.The authors interpret this pattern as evidence that difficulty ordering belongs to the data rather than a particular solver.Source: §5.5 · p. 8, Figure 7 · p. 9
  • SFT raises automatic termination from 6% to above 95%, roughly halves to quarters tool calls and turns, and reduces 25-turn-cap hits from 28–77% to 0–5%.RL leaves termination nearly unchanged but further reduces tool calls and turns by up to 19.5% relative to SFT.Source: §5.5 · p. 9, Figure 6 · p. 9
  • Hard synthesis items cost approximately 2.3× the API calls and 2.4× the tokens of Easy items.The authors report that GRADS balances synthesis cost and results better than the baselines.Source: §5.5 · p. 9

6 CONCLUSION

GRADS separates open-ended evidence exploration from graph-based difficulty control, using graph complexity both to set synthesis difficulty and measure it. The conclusion reports aligned requested and achieved complexity, empirically ordered difficulty, and training gains from the resulting data.

6 CONCLUSION

  • Graph complexity sets synthesis difficulty through reasoning depth, breadth, size, and information flow through hub nodes, while keeping answer claims traceable to source spans.The graph's reasoning depth is the governing axis; complexity also serves as an evaluation-time measure.Source: §6 · p. 10
  • Requested and achieved complexity align closely, while solver accuracy declines monotonically with requested difficulty under an independent judge and graph builder.Source: §6 · p. 10
  • SFT on GRADS trajectories improves a 4B model by up to roughly threefold on the strongest domain and beats three synthesis baselines at matched sample count.The controlled, verified corpus serves both evaluation and post-training.Source: §6 · p. 10

REPRODUCIBILITY STATEMENT

The authors release pipeline materials and describe a fixed evaluation setup with paired statistical tests and fixed seeds.

REPRODUCIBILITY STATEMENT

ETHICS STATEMENT

Source records are used under their original licenses, and sensitive content is handled according to responsible-disclosure norms. Benchmark scores are reported as relative comparisons on a fixed harness because source documents may appear in model pretraining.

ETHICS STATEMENT

  • Source records are used under their original licenses.Source: ETHICS STATEMENT · p. 11
  • Sensitive content is handled in line with responsible-disclosure norms.Source: ETHICS STATEMENT · p. 11
  • Because source documents may appear in model pretraining, benchmark scores are reported as relative comparisons on a fixed harness rather than contamination-free absolutes.Source: ETHICS STATEMENT · p. 11

AI USE STATEMENT

GRADS uses LLMs to explore corpora, synthesize question–answer pairs, and verify them. Other generative-AI use supported editing and auxiliary code, with authors reviewing the output and taking responsibility for the final content.

AI USE STATEMENT

  • GRADS uses large language models as agents to explore corpora, synthesize question–answer pairs, and verify them.Source: AI USE STATEMENT · p. 11
  • Other generative-AI use assisted readability editing and auxiliary plotting and data-processing code.Source: AI USE STATEMENT · p. 11
  • Authors reviewed all AI-assisted output and take full responsibility for the final content.Source: AI USE STATEMENT · p. 11

A NUMERICAL DATA FOR FIGURES

This appendix section identifies the scope and measures of the numerical data reported for Section 5 figures. The Physics domain is the CMS experimental-physics notes.

A NUMERICAL DATA FOR FIGURES

  • The appendix reports exact values behind Section 5 figures and identifies Physics as CMS experimental-physics notes.Source: A NUMERICAL DATA FOR FIGURES · p. 15
  • Table 1 reports rubric-weighted solver score and delivered reasoning depth by method, domain, and requested band.It gives the data behind Figure 3.Source: Table 1 · p. 15
  • Solver score is on a 0–1 scale with 20 items per cell, while reasoning depth counts the longest necessary-inference chain.Source: Table 1 · p. 15

A.1 REASONING DEPTH AS THE DOMINANT COMPLEXITY AXIS

The appendix examines how solver scores relate to graph-topology measures across the delivered benchmarks. Depth is the strongest predictor in GitHub, Physics, and pooled data, while Security is a qualified exception.

A.1 REASONING DEPTH AS THE DOMINANT COMPLEXITY AXIS

  • Depth is most strongly negatively correlated with solver score on GitHub, Physics, and pooled data; size and dispersion are marginally stronger in Security.The reported correlations use rubric-graded scores on 100 GitHub items, 100 Physics items, and 135 Security items, with DeepAgent on Opus 4.8 as the solver.Source: §A.1 · p. 15, Table 2 · p. 15
  • Depth correlates closely with cinfo and size (Spearman rs ≈0.6–0.85), so one depth scalar captures most of the full topology’s information.Source: §A.1 · p. 15
  • For depth, the linear fit is moderate (R2 ≈0.2–0.3), consistent with structural complexity being a controlled difficulty variable rather than a complete determinant of success.Source: §A.1 · p. 15
  • Table 2 reports per-domain and pooled Spearman correlations between solver score and each term of C(G); dispersion counts distinct source records.Source: Table 2 · p. 15

B SYNTHESIS COST

This section describes GRADS’s synthesis costs and its prompt-based process for gathering evidence, constructing and verifying evidence graphs, and selecting subgraphs to control task difficulty. It also distinguishes true inference depth from parallel evidence aggregation and treats question type as independent of difficulty.

C AGENT PROMPTS

  • GRADS uses fixed-prompt roles with enforced JSON outputs, while code—not the prompts—computes sums, claim counts, depth, and substring checks.This design keeps difficulty measured rather than self-reported.Source: C AGENT PROMPTS · p. 17

B SYNTHESIS COST

  • API calls and token use rise monotonically with requested depth; versus baselines, GRADS spends a moderate budget while delivering greater depth than WebShaper and TaskCraft.The comparison notes that Claude-Code spends about as much as GRADS but never reaches the target depth; cost measurement quality differs by method.Source: B SYNTHESIS COST · pp. 15–16, Table 9 · p. 19, Table 10 · p. 19

C AGENT PROMPTS

  • The Brain alternates precise evidence exploration with generation, which converts fetched evidence into graph nodes and extends necessary chains until the target depth is reached or links run dry.When evidence cannot support the requested depth, the prompts call for reporting the shortfall and building the deepest honest chain rather than dropping the item.Source: C AGENT PROMPTS · pp. 18–19
  • The Analyst targets hop-by-hop necessary paths, and the Respondent expresses inference as an explicit dependency ladder rather than parallel facts.A rubric of independent facts supports breadth, not depth; the prompts ask later inference claims to name their prior claims.Source: C AGENT PROMPTS · p. 20
  • Two verifier lenses challenge whether claims are supported by cited evidence and whether each reasoning hop is necessary.The Verifier also checks answer completeness, question shape, and answer hygiene.Source: C AGENT PROMPTS · p. 21
  • Evidence graphs use necessary edges that pass a deletion test, with core and inference nodes carrying reasoning and detail nodes attached as leaves.Unrelated claims belong in separate graphs rather than forced chains.Source: C AGENT PROMPTS · p. 22
  • The graph verifier checks correctness, completeness, simplicity, minimality, and consistency, targeting errors that could inflate measured depth or leave contradictions unrepresented.It checks edge relations, sufficient parents for derived nodes, duplicates and transitive edges, necessary-edge deletion tests, and missing refutation links.Source: C AGENT PROMPTS · p. 23
  • Difficulty is selected by necessary-chain depth, with breadth capped by band: Easy depth ≤3, Medium depth 4–5, and Hard depth ≥8.The selector chooses a subgraph closed under necessary parents and anchored at a root-allowed node; it does not fabricate hops when evidence is insufficient.Source: C AGENT PROMPTS · p. 23

D QUESTION-TYPE TAXONOMY

  • Question type is orthogonal to difficulty, and coding types apply only when selected evidence contains code, a diff, or a patch.The taxonomy labels each item with one of ten types; coding-type anchors must cite the actual change.Source: D QUESTION-TYPE TAXONOMY · p. 24

E POST-TRAINING CONFIGURATION

The post-training configuration uses a shared supervised fine-tuning recipe for agent trajectories and applies GRPO from each domain’s SFT checkpoint. The appendix tables summarize training data, evaluation scores, and GRPO settings.

E POST-TRAINING CONFIGURATION

  • SFT uses full-parameter fine-tuning of Qwen3.5-4B with a fixed recipe: six epochs, 16 sequences per optimizer step, and a 32,768-token context.Training uses LlamaFactory and DeepSpeed ZeRO-3 on 8×A100-40GB GPUs, learning rate 10^-5, cosine decay, 3% warmup, and seed 42.Source: E POST-TRAINING CONFIGURATION · p. 24
  • Each SFT example is a complete multi-turn agent trajectory built from a QA pair, with loss applied only to assistant tokens.The loss covers reasoning, tool calls, and the final report.Source: E POST-TRAINING CONFIGURATION · p. 24
  • GRPO starts from each domain’s SFT checkpoint and trains for 30 steps on 240 synthesized pairs disjoint from the benchmark.Rollouts receive claim-level rewards against their own pair’s weighted reference claims, plus an answer-format bonus.Source: E POST-TRAINING CONFIGURATION · p. 24
  • Table 12 summarizes SFT data and benchmark scores per arm, while Table 13 lists shared GRPO settings and notes shorter observation and turn limits during training than evaluation.GRPO training truncates observations to 3,000 characters and allows 12–14 turns, versus 12,000 characters and 25 turns at evaluation.Source: Table 12 · p. 25, Table 13 · p. 25

Related papers

Loading 2610.21167v1…