PaperlayerView exact revision on arXiv

Source-linked AI summary

GraphEcho: Structural Redundancy and Evidence Provenance in LLM Graph Agents

Sikun Wang, Yixi Zhou, Lei Fan, Fan Zhang

arXiv:2609.17695v1cs.AIcs.CL

TL;DR

Graph agents can encounter repeated paths to one observation without gaining independent evidence, making it important to assess both their judgments and what they acquire. GraphEcho tests this with controlled provenance interventions and finds that PAPT reduces repeated walks while improving synthetic accuracy but lowering source recall and SciFact accuracy.

  • Problem

    A graph agent may encounter one observation through several paths, and treating those paths as independent corroboration changes its assessment without adding evidence.

    Source: §1 · p. 1

  • Method

    GraphEcho evaluates judgments and evidence acquisition under controlled provenance interventions, pairing verdict measures with source-count, repeated-walk, coverage, and cost measures.

    Source: §3.2 · p. 2, §5.4 · p. 5

  • Results

    PAPT improves synthetic accuracy and reduces repeated walks, but lowers source recall and SciFact accuracy; redundant support raises echo walk rates across frozen agents despite heterogeneous judgment effects.

    Source: §1 · p. 1, §7 · p. 8

  • Takeaways & Limitations

    Evaluation should measure both repeated and unobserved evidence, since shorter trajectories can improve echo rate while leaving distinct evidence unobserved.

    Source: Limitations of the Work · p. 8, §7 · p. 8

    Synthetic source independence and equal-weight labels simplify evidence; SciFact uses document identifiers as a provenance proxy and gold rationales, and training uses one seed.

    Source: Limitations of the Work · p. 8

Abstract

from arXiv · show

A large language model (LLM) agent can follow more graph paths without acquiring more independent evidence. GraphEcho tests whether agents mistake these repeated encounters for additional corroboration. The benchmark varies path counts and evidential origins while holding evidence content fixed, and evaluates both judgments and active exploration. Controlled synthetic experiments reveal model-dependent judgment shifts, but redundant supporting paths increase the share of repeated walks across all evaluated frozen agents. Provenance-aware post-training (PAPT) reduces revisits and improves synthetic accuracy, yet covers fewer distinct sources. On scientific claims, it continues to reduce repetition while accuracy declines. These findings expose a gap between efficient exploration and effective evidence use: an agent can learn to stop repeating itself while overlooking information it needs. GraphEcho provides a controlled way to evaluate both what graph agents conclude and whether their exploration reaches distinct evidential sources.

1 One observation can yield many paths

GraphEcho tests whether graph agents distinguish repeated representations of one observation from additional evidential origins. Its controlled interventions separate judgment from evidence acquisition, revealing model-dependent judgments and increased repeated walks under redundant support.

1 One observation can yield many paths

  • One experimental observation can appear as a result node, conclusion node, or table entry, so repeated retrieval may consume exploration budget without adding evidence.Related work motivates testing how structural representations affect both judgment and evidence acquisition.Source: §1 · p. 1
  • The central comparison holds the claim and five path templates fixed while varying whether paths come from one study or five; a second comparison adds paths from one study.Matched path lengths and evidence wording control reasoning difficulty and information content in the synthetic source-count intervention.Source: §1 · p. 1, Figure 1 · p. 2
  • Across 800 fictional claims, GraphEcho-Syn separates redundant paths from distinct origins, and static judgment shifts differ in direction across models.The benchmark also evaluates active evidence acquisition.Source: §1 · p. 1
  • Redundant supporting paths raise echo walk rates in all four frozen agents, while accuracy changes in both directions.The benchmark assesses active acquisition alongside judgments.Source: §1 · p. 1
  • PAPT raises synthetic accuracy by 41.5 percentage points over frozen Qwen3-4B, but lowers source recall and SciFact accuracy.Cheap controls and reward ablations distinguish reduced repetition from improved evidence use.Source: §1 · p. 1

2 Related Work

GraphEcho builds on work in evidence selection, graph retrieval, and adaptive acquisition. It distinguishes its focus on repeated paths from prior work on context conflicts, provenance tracking, and retrieval strategies.

Related Work

  • GraphEcho isolates repeated graph paths that share one evidential origin, matching evidence wording and path templates to separate structural repetition from source count.Prior work addresses context conflict, irrelevant passages, context position, and retrieval redundancy (Chen et al., 2022; Yoran et al., 2024; Liu et al., 2024; Ross et al., 2026).Source: §2 · p. 2
  • GraphEcho varies provenance assignments while holding evidence content fixed, testing visible source identifiers against preprocessing that collapses repeated evidence.Related graph-retrieval work includes ALCE (Gao et al., 2023), HippoRAG (Gutiérrez et al., 2024), HippoRAG 2 (Gutiérrez et al., 2025), and PAGE-RAG (Deng et al., 2026).Source: §2 · p. 2
  • GraphEcho examines whether acquisition reaches distinct origins within a fixed action budget, evaluating accuracy alongside repeated walks and source recall to distinguish fewer revisits from broader evidence coverage.PAPT uses group-relative policy optimization (Shao et al., 2024) with rewards for judgments, source counting, and distinct evidence acquisition.Source: §2 · p. 2

3 Separate paths from evidential origins

GraphEcho separates path multiplicity from provenance multiplicity, then tests those interventions on synthetic conflicts and scientific claims. The synthetic setup controls evidence content and origin assignments; SciFact uses document identifiers as an observable provenance proxy.

3.1 Provenance defines the intervention

  • Nprov counts distinct evidential origins across paths, while redundant-path interventions change Npath and source-count interventions change Nprov at a fixed path count.For each path p, π(p) maps it to its underlying evidential origin e.Source: §3.1 · p. 2

3.2 Synthetic graphs control provenance

  • GraphEcho-Syn contains 800 fictional claims across four domains, with five supporting and five refuting atoms per claim and equal reliability weights of 1.0.The gold verdict follows the balance of distinct origins; the primary 1S5P versus 5S5P comparison preserves evidence wording and relation templates, changing only origin assignments.Source: §3.2 · pp. 2–3

3.3 Conflict exposes false corroboration

  • Table 1 specifies five conflict conditions; C2 adds four supporting representations to the same two opposing atoms, while C3 supplies five distinct supporting origins.C4 reverses the provenance majority, and C2R tests redundant refuting paths.Source: §3.3 · p. 3, Table 1 · p. 3

3.4 SciFact tests document provenance

  • The SciFact evaluation retains 188 claims with gold evidence and produces 584 graph instances; only ten eligible claims have multiple evidence documents.Document identifiers provide observable provenance but do not establish study independence; the gold-rationale experiment excludes claims without gold evidence, and PAPT uses synthetic supervision only.Source: §3.4 · p. 3

4 Acquire distinct evidence within a budget

The agent environment exposes graph actions under a walk budget, while mitigation comparisons test provenance metadata, instructions, and path grouping. PAPT trains a policy with rewards for judgments, source counting, and evidence acquisition.

4.1 Observe graph actions

  • A walk reveals a selected neighbor’s full content, while a stop returns the judgment; the primary budget permits six walk actions.The environment exposes visited nodes, available neighbors, short previews, and remaining budget; connector movements are recorded separately from repeated evidence acquisition.Source: §4.1 · p. 3
  • The agentic comparison includes balanced provenance, redundant supporting routes, and distinct supporting origins, with previews withholding unseen evidence content and gold stance.An atom’s first evidence-bearing visit supplies its complete synthetic observation, making later visits to equivalent representations redundant in this setup.Source: §4.1 · p. 3

4.2 Compare cheap mitigations

  • M0 shows source nodes, M1 adds provenance identifiers, M2 also instructs distinct-origin counting, and M3 groups equivalent paths while preserving multiplicity.These four controls test mitigation through metadata, instructions, and preprocessing.Source: §4.2 · p. 3

4.3 Train a provenance-aware policy

  • PAPT combines a verdict reward with source counting and evidence acquisition; its reward also scores distinct-origin coverage, repeated provenance acquisition, and walk cost.The protocol applies GRPO to Qwen3-4B with groups of four trajectories and LoRA rank 16; training uses 500 examples for one epoch.Source: §4.3 · p. 4
  • Reward variants remove the echo reward, coverage reward, or retain only verdict reward, with checkpoint selection based on development full-objective reward.Test labels and SciFact supervision do not enter checkpoint selection.Source: §4.3 · p. 4

5 Measure judgment and acquisition separately

This section defines how GraphEcho records model judgments and contrasts redundant paths with independent-source evidence, then specifies acquisition measures and uncertainty checks.

5.1 Models and outputs

  • Frozen evaluation uses Qwen3-1.7B, Qwen3-4B, and Qwen3-8B, with GPT-5-mini as a supplementary API baseline; outputs include verdicts, confidence, provenance counts, source IDs, and rationales.Confidence is the subjective probability of the claim, not confidence in the selected verdict; parsing failures count as incorrect verdicts.Source: §5.1 · p. 4

5.2 Static effects use paired claims

  • Paired static comparisons measure confidence changes from redundant paths and distinct sources, with PME and ISE reported separately.For one-sided support, positive PME indicates increased confidence from redundant paths; their ratio is reported only when ISE exceeds 0.5 percentage points. Additional diagnostics track evidence-count inflation, verdict flips, and conflict bias.Source: §5.2 · p. 4

5.3 Acquisition measures expose repeated visits

  • Acquisition ratios track unique provenance coverage, echo walks, unique-source recall, and walk efficiency; source-count error differs from full-graph verdict accuracy.The measures distinguish unique acquired origins from repeated visits; zero denominators yield zero, and shared-claim edges make each origin accessible in one acquisition action.Source: §5.3 · pp. 4–5

5.4 Mitigation must preserve source sensitivity

  • The mitigation comparison tracks PME, ISE, verdict accuracy, and source-count error; agentic evaluation adds coverage, repeated walks, and cost.SciFact results are separated into SUPPORT and REFUTE strata, and document-count effects use eligible multi-document claims at matched path counts.Source: §5.4 · p. 5

5.5 Uncertainty respects repeated measurements

  • The main evaluation randomizes path order across five seeds and uses claim-level bootstrap confidence intervals; primary accuracy counts malformed outputs as incorrect.A post hoc comparison restricted to matched pairs with valid finals is selection-sensitive and cannot isolate a causal reasoning effect.Source: §5.5 · p. 5

6 Redundancy changes judgment and acquisition

Across static judgments and active walks, redundancy affects models differently, while PAPT’s reduced repetition comes with incomplete coverage and weaker SciFact accuracy.

6.1 Static effects depend on the model

  • Static responses vary by model: Qwen3-4B reacts more to redundant than additional-origin paths, while Qwen3-8B and GPT-5-mini probability shifts can leave SUPPORT rates unchanged.Source-count errors also differ: at 1S5P, Qwen3-8B overcounts by four origins, while Qwen3-4B undercounts by one.Source: §6.1 · p. 5, Table 2 · p. 6

6.2 Redundant paths raise echo walk rates

  • For Qwen3-1.7B, restricting accuracy analysis to valid-final pairs reverses the estimated change, but the interval spans zero and the subset covers 168 of 200 claims.Valid finals rise from 39.1% in C1 to 90.5% in C2, so the primary gain depends on which outputs enter the analysis.Source: §6.2 · p. 5
  • Redundant support raises echo walk rates by 5.80–38.84 percentage points in all four frozen agents, while accuracy changes in both directions.All four paired intervals exclude zero.Source: §6.2 · p. 5, Table 3 · p. 6

6.3 PAPT learns shorter, less repetitive walks

  • In C3, PAPT reaches about one-third of six origins versus over four-fifths for the frozen policy, averaging roughly two walks despite one-action reachability.The shorter trajectories reduce repetition but leave most available origins unvisited.Source: §6.3 · p. 6
  • On common seed zero, PAPT exceeds M3 accuracy by about four percentage points, yet revisits more evidence and reaches fewer origins; provenance collapse nearly eliminates redundant-path sensitivity.M3 groups equivalent evidence, changing the action space as part of the comparison.Source: §6.3 · p. 6

6.4 Transfer reduces echoes but loses accuracy

  • PAPT raises synthetic accuracy by 41.5 percentage points over frozen Qwen3-4B while lowering echo walk rate, but on SciFact lowers accuracy by 3.6 points despite reducing echoes.The synthetic echo walk rate falls by 36.9 points; on SciFact it falls by 36.0 points.Source: §6.3 · p. 6, §6.4 · p. 6, Table 5 · p. 7

6.5 Reward ablations expose competing effects

  • Full-reward training beats verdict-only synthetic accuracy by about 16 points but reduces echo and source recall; its SciFact advantage is uncertain, while positive accuracy differences persist across tested budgets and topologies.Echo rate falls in all five additional settings, but source recall rises only at budget three and falls in the others.Source: §6.5 · p. 7

6.6 Stopping depends on unobserved sources

  • After one supporting and one refuting origin, C2 is complete but C3 has four unseen supporting origins; stopping on observed balance alone treats these states alike.Source recall captures the remaining-origin difference; matching acquired evidence could separate judgment from evidence-access effects.Source: §6.6 · pp. 7–8

7 Conclusion and Future Work

GraphEcho separates structural repetition from provenance, finding that frozen agents repeat walks under redundant support while PAPT’s benefits come with reduced source recall and lower SciFact accuracy. The authors call for evaluating repeated and unobserved evidence and for multi-source scientific tests.

7 Conclusion and Future Work

  • Frozen agents showed heterogeneous judgment effects and more repeated walks under redundant support, while PAPT improved synthetic accuracy but lowered source recall and SciFact accuracy.The authors conclude that neither reduced repetition nor higher synthetic accuracy alone establishes effective evidence use.Source: §7 · p. 8
  • Evaluation should measure both repeated and unobserved evidence because an agent can stop repeating while still overlooking distinct sources.Source: §7 · p. 8
  • Future scientific benchmarks could track shared datasets and experiments across papers to test recognition of common empirical origins across documents.Such annotations would also support comparisons of evidence grouping and learned exploration when document boundaries incompletely capture source dependence.Source: §7 · p. 8

Limitations of the Work

The benchmark relies on controlled assumptions and proxies that constrain how its results should be interpreted. Training-seed variation is not captured by the reported claim-bootstrap intervals.

Limitations of the Work

  • Synthetic source independence is a controlled benchmark assumption, while equal-weight evidence balance defines its synthetic verdict labels.Real scientific evidence varies in strength and dependence, and repeating identical evidence text covers only a limited form of graph extraction.Source: Limitations of the Work · p. 8
  • SciFact document identifiers serve only as an observable provenance proxy, and its gold-rationale setting omits retrieval errors.Self-reported probabilities do not establish calibration; agentic findings concern the implemented topologies, previews, and action costs.Source: Limitations of the Work · p. 8
  • Training used one random seed, so claim-bootstrap intervals omit variation across training runs and ablations compare policies from that shared seed.Source: Limitations of the Work · p. 8

Declaration on Generative AI

The section declares manuscript language polishing by generative AI, reports construction checks for the data, and describes the controlled provenance comparison and its interpretation.

Declaration on Generative AI

A Data construction checks

  • Construction checks verified split disjointness, atom and path properties, matched evidence content, and preservation of source identity and evidence-balance labels.SciFact conversion preserves document identifiers and rationale sets, grouping each document’s rationale sentences as one origin.Source: A Data construction checks · p. 10

B Static and conflict responses

  • The source-count intervention preserves path templates and evidence wording, so response differences reflect provenance assignment within this construction while model-specific directions remain.An unchanged SUPPORT rate can coexist with a probability shift toward redundant evidence.Source: B Static and conflict responses · p. 10

C Static mitigation and task quality

The section specifies how task-quality and document-count effects are estimated, then clarifies the agent-validity and condition-level denominators used in reporting.

C Static mitigation and task quality

  • Task-quality estimates average each claim’s available conditions before pooling, giving claims equal weight despite differing numbers of variants.Document-count effects use ten eligible multi-document claims and compare the available two-to-five-document set with one document at matched path count.Source: C Static mitigation and task quality · p. 10
  • A stratum with one claim is descriptive only and receives no inferential interval.Source: C Static mitigation and task quality · p. 10

D Agent validity and condition-level behavior

  • Agent validity reporting distinguishes all received outputs from the valid-output subset; malformed responses count as incorrect, and only valid repeated visits enter the echo numerator.Invalid actions remain in the walk denominator.Source: D Agent validity and condition-level… · p. 10

E Training and sensitivity settings

The training analysis compares reward-variant trajectories and tests fitted policies across alternative graph settings. Supplementary materials describe conflict, scientific-claim, and validity diagnostics.

E Training and sensitivity settings

  • All four reward policies share 500 balanced training instances, one epoch, seed 42, and the same development-based checkpoint-selection objective.The shared settings include learning rate 10−5, group size four, LoRA rank 16, and alpha 32; development reward selects the test policy.Source: E Training and sensitivity settings · p. 10
  • Sensitivity tests pair frozen and trained agents across alternate budgets and graph constructions, including ring adjacency and two-to-six-hop paths, with training fixed.The variable-hop construction preserves evidence and gold labels.Source: E Training and sensitivity settings · p. 10, Table 11 · p. 13

F Supplementary SciFact baselines

  • Supplementary tables cover paired C2-minus-C1 conflict effects, Qwen3-4B mitigation and transfer, task quality, final-output validity, and policy output counts.Table 10's accuracy contrast uses matched pairs with valid finals on both sides; Table 9 counts received outputs, not correct verdicts.Source: Table 6 · p. 10, Table 7 · p. 11, Table 8 · p. 12
  • Figure 3 contrasts repeated paths from one source with paths from distinct origins, while Figure 4 describes frozen-agent acquisition and accuracy under echo-rich conditions.Both figures report 95% claim-bootstrap intervals; Figure 4 uses 200 claims, five seeds, and budget six.Source: Figure 3 · p. 11, Figure 4 · p. 12

E Training and sensitivity settings

F Supplementary SciFact baselines

  • Table 12 compares scientific-rationale baselines and API controls; static PME and seed-zero 1S5P agent columns measure different outcomes and scopes.Agent estimates use 188 claims; static PME uses 188 except GPT-5-mini M3, which uses 187 valid paired outputs.Source: F Supplementary SciFact baselines · p. 10, Table 12 · p. 13

Related papers

Loading 2609.17695v1…