# Seed-Anchored Budgeted Graph Context

- ID: 3032
- Canonical URL: https://synthcore.org/idea/3032/seed-anchored-budgeted-graph-context
- API JSON: https://synthcore.org/api/idea/3032.json
- API Markdown: https://synthcore.org/api/idea/3032.md
- Verification status: mech_ok_no_baseline
- Source: [arXiv:2609.02011](https://arxiv.org/abs/2609.02011)
- Category: architecture
- Solves: accuracy, scalability, stability
- ML areas: retrieval, graph-nn, transformer, attention
- Math tags: graph-theory, combinatorics, information-theory
- Ratings: usefulness 8/10; difficulty 4/10; novelty 7/10

## Idea description

Replace arbitrary graph serialization or global top-k retrieval with deterministic locality tiers centered on entities matched by the question. Render every candidate unit in the highest-priority seed-local tiers before admitting more distant or weakly connected material, and use stable identifiers to make ties reproducible. If the complete seed-local candidate region fits within the context budget, no relevant unit in that region is lost to truncation.

## Mathematical statement

Let $G=(V,E)$ be a graph, $S=S(q)\subseteq V$ the deterministic seed set extracted from query $q$, $k$ the maximum hop radius, and $B$ the token or character budget. Define the candidate units $U_k(S)$ as node-description units $\mathrm{desc}(v)$ for nodes with $d(v,S)\le k$ and edge-render units $\mathrm{rend}(e)$ for edges $e=(u,r,w)$ whose endpoints both satisfy $d(u,S),d(w,S)\le k$. Assign each unit hop level $h(x,S)=d(v,S)$ for node units and $h(x,S)=\max(d(u,S),d(w,S))$ for edge units. Let $\ell(x)$ be the rendered length including separators, and let $D_k(S)=\sum_{x\in U_k(S)}\ell(x)$. When $D_k(S)\le B$, the renderer returns every unit in $U_k(S)$, giving candidate recall one. When $D_k(S)>B$, it emits units in increasing hop level and resolves ties with an injective deterministic identifier. The predicted transition is at $D_k(S)=B$: full candidate coverage should hold below the boundary and begin failing above it.

## Key formulas

- $$U_k(S)=\{\mathrm{desc}(v):d(v,S)\le k\}\cup\{\mathrm{rend}(e):e=(u,r,w),\ d(u,S)\le k,\ d(w,S)\le k\},$$
- $$h(\mathrm{desc}(v),S)=d(v,S),\qquad h(\mathrm{rend}(e),S)=\max\{d(u,S),d(w,S)\},$$
- $$D_k(S)=\sum_{x\in U_k(S)}\ell(x),\qquad D_k(S)\le B\ \Longrightarrow\ \mathrm{Render}(q)=U_k(S),\quad \mathrm{Recall}_{\mathrm{candidate}}=1,$$
- $$\mathrm{key}(x)=\big(h(x,S),\mathrm{id}(x)\big),\qquad \mathrm{Render}_B(q)=\operatorname{prefix}_{B}\left(\operatorname{sort}_{\mathrm{key}}(U_k(S))\right).$$

## Implementation notes

Integrate this method as the retrieval and context-construction layer before a graph-RAG reader or graph transformer. Given a question, deterministically name-match entities to obtain $S$, perform a bounded breadth-first search to depth $k$ (start with $k=2$), create one render unit for every eligible node description and edge, and record each unit's exact serialized length including separators. Do not use an LLM or learned retriever initially. Pseudocode is: `S = name_match(question, graph); d = BFS_distances(graph, S, k); U = []; for v with d[v] <= k: append(desc(v), h=d[v], id=node_id[v]); for edge (u,r,w) with d[u] <= k and d[w] <= k: append(render(edge), h=max(d[u],d[w]), id=edge_id[e]); sort U by (h,id); D=sum(length(x) for x in U); if D<=B: context=concat(U); else: context=greedy_prefix(U,B)`; pass `context` to the same frozen reader used by the baseline. Compute graph distances, lengths, $D_k(S)$, and exact annotated evidence recall directly; estimate reader correctness empirically. The first cheap experiment should use a synthetic knowledge graph and a frozen 7B QA reader, comparing global serialization, random truncation, learned top-k retrieval, and seed-anchored rendering at budgets from 512 to 8,000 tokens. Annotate gold node and edge evidence. The quantitative prediction is a sharp coverage boundary: queries with $D_k(S)/B\le1$ should have candidate recall approximately 1.0, while recall should decrease monotonically after the ratio exceeds one, with the largest loss at the first overflowing hop tier. Conditional reader accuracy given gold evidence should remain similar across methods; unconditional accuracy should differ mainly because naive methods truncate evidence. Verify that the measured full-coverage threshold agrees with $D_k(S)=B$ within 10% and that repeated runs produce identical contexts.

## Verification

- Status: mech_ok_no_baseline
- Mechanism evidence: yes
- Mechanism confirmed: yes
- Practical verdict: no_effect
- Verdict: Built a deterministic seed-matched BFS graph-context renderer with hop-tier ordering, stable identifiers, exact separator-inclusive lengths, and greedy budget truncation. The formal check showed an exact transition at D_k(S)=B=4119 characters: all tested budgets below D were incomplete, while B=D and larger budgets achieved candidate recall 1.0; repeated anchored renders were identical. Across 8 synthetic queries whose budgets fit all seed-local one-hop evidence, anchored rendering achieved 1.0 average relevant recall versus 0.273 for global ordering and 0.316 for random truncation.

### Mechanism check

- Verdict: Built a deterministic seed-matched BFS graph-context renderer with hop-tier ordering, stable identifiers, exact separator-inclusive lengths, and greedy budget truncation. The formal check showed an exact transition at D_k(S)=B=4119 characters: all tested budgets below D were incomplete, while B=D and larger budgets achieved candidate recall 1.0; repeated anchored renders were identical. Across 8 synthetic queries whose budgets fit all seed-local one-hop evidence, anchored rendering achieved 1.0 average relevant recall versus 0.273 for global ordering and 0.316 for random truncation.
- Confidence: 9/10
- Limitations: Only synthetic graphs and exact name matching were tested; no graph-RAG reader, QA accuracy, learned retriever, pretrained model, tokenization effects, latency, or real-world noisy queries were evaluated. The evidence-recall comparison used budgets deliberately sized to fit the one-hop seed-local region, so it verifies retrieval behavior rather than end-to-end reader gains.

### Practical benchmark

- Paired seeds: 8
- Baseline mean: 0
- Idea mean: 0
- p-value: 1
- Paired wins: 0/8
- Benchmark verdict: no measurable effect

## Artifacts

- [bench_graph_context.py](https://synthcore.org/code/1210/bench_graph_context.py)
- [bench_report.json](https://synthcore.org/code/1210/bench_report.json)
- [experiment.py](https://synthcore.org/code/1210/experiment.py)
- [mini_experiment.py](https://synthcore.org/code/1210/mini_experiment.py)
- [mini_results.json](https://synthcore.org/code/1210/mini_results.json)
- [report.md](https://synthcore.org/code/1210/report.md)
- [report_bench_2026-09-03T115239.md](https://synthcore.org/code/1210/report_bench_2026-09-03T115239.md)
- [results.json](https://synthcore.org/code/1210/results.json)
- [Download all files as ZIP](https://synthcore.org/download/1210)

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.