GraphScent: Calibrating Directional Relevance Signals for Bounded-Context Code Localization

Ramesh Arvind NaagarajanarXiv 2026 · arXiv

TL;DR

GraphScent is a training-free search controller that enables local LLMs to find bugs in large codebases using a fraction of the memory required by traditional agents. By discovering a "directional relevance asymmetry"—where upstream callers are far more informative about bugs than downstream callees—the authors developed a calibrated search algorithm that nearly doubles bug localization accuracy on difficult targets within a single-GPU budget.

What Problem Does This Paper Address?

Modern AI coding agents typically work by maintaining a long, multi-turn conversation history as they explore a repository. While effective, this approach is a memory hog: the expanding history rapidly exhausts the VRAM of consumer-grade GPUs, making local deployment difficult.

To solve this, researchers are moving toward "stateless" code inspection, where the model looks at small, isolated snippets of code one at a time. However, this creates a needle-in-a-haystack problem: if an LLM looks at a function that isn't the bug but is near the bug, how does it know which way to go next? Traditional methods treat all code relationships (like "A calls B") as equally informative, but this paper proves that assumption is wrong.

Methods

The authors introduce GraphScent, a system designed to navigate code repositories efficiently using three main stages:

  1. Runtime Typed-AST Multigraph: Instead of relying on slow external language servers, GraphScent builds a lightweight graph of the repository on the fly using Python’s standard ast module. It maps relationships like lexical containment (parent/child), calls, and inheritance.
  2. Calibrated Directional Propagation: The core innovation. The system uses "Directional Relevance Scent." When an LLM evaluates a code snippet, GraphScent doesn't just take the raw score. It uses Laplace-smoothed log-likelihood ratios (LLRs) to propagate that relevance specifically along "high-scent" edges (e.g., from a caller to a callee).
  3. Listwise Commitment: After 24 stateless probes, the system takes the top 6 candidates and performs a single "listwise" comparison (looking at all 6 side-by-side) to break ties and make a final commitment.

Additionally, they introduce AST Ripple, a post-edit tool that checks for "missed co-edits"—files that should have been changed alongside the main fix but were overlooked.

System architecture of GraphScent and AST Ripple

Datasets

The study evaluates the Gemma 4 family of models (4B, 12B, and 31B parameters) across two panels:

  • Public Panel (public_113): 113 tasks from the Gemma 4 Developer Agent Challenge (including popular repos like fastapi and requests).
  • Temporally Held-Out Panel (post2025_98): A new benchmark created by the authors featuring 98 tasks from 82 repositories with issues dated between 2025 and 2026. This ensures the models weren't trained on the solutions.

Key Insights and Ideas

  • The Asymmetry Discovery: LLMs are surprisingly good at recognizing that an upstream caller is relevant to a bug, but they are near-chance at recognizing a callee. Intuition: A caller often contains the "symptom" or the entry point that delegates to a broken routine. A downstream helper function, however, usually looks perfectly benign when viewed in isolation.
  • Static Metrics are Insufficient: Popular algorithms like PageRank, which rank code based on graph "centrality," actually performed worse than simple keyword search (BM25) unless paired with live LLM judgments.
  • Calibration is Mandatory for Small Models: Smaller models (like the 4B) tend to be overconfident, frequently hallucinating that a caller is a "definite bug." Using log-likelihood ratios (LLRs) instead of raw scores helps stabilize these models, preventing them from chasing false positives.
Figure 2: Directional relevance asymmetry across model scales and disjoint repository panels. Point estimates and 95% task-cluster bootstrap CIs for Scent(r) on (a) public_113 (4 repositories) and (b) temporally held-out post2025_98 (82 repositories). Enclosing scopes (parent) and up- stream callers (called_by) consistently exceed the 0.50 distractor baseline and τ = 0.55 gate across E4B, 12B, and 31B, whereas downstream callees (calls) remain near 0.48–0.51.

Key Results

  • Localization Boost: On "lexically hard" targets (where the bug isn't obvious from the issue text), GraphScent improved exact localization from 12.8% to 23.4% for the 31B model.
  • Tie-Breaking Effectiveness: Moving from a simple "highest score wins" approach to the top-6 listwise comparison added a massive +7.6 to +12.3 percentage point boost in accuracy.
  • AST Ripple: This lightweight tool successfully surfaced missed reference-patch files in 50.0% of unresolved multi-file runs for the 31B model.
  • Efficiency: The entire process fits within <21.5 GiB of VRAM, meaning it can run comfortably on a single NVIDIA RTX 3090/4090 or H200 GPU.

Limitations and Future Work

  • Language Specificity: The current implementation is optimized for Python. Statically typed languages (like Java or C++) might exhibit different relevance patterns due to explicit type signatures.
  • Pretraining Exposure: While the authors used a 2025-2026 dataset to minimize leakage, they acknowledge that absolute "non-exposure" is hard to guarantee without knowing the exact training cutoffs for the Gemma models.
  • Future Direction: The authors suggest integrating AST Ripple into a closed-loop test-suite improvement cycle, rather than just using it as a retrospective recall tool.

Summary updated

Abstract

Running open-weight language models locally on a single consumer GPU requires replacing expanding multi-turn exploration histories with short, stateless code inspections. Stateless repository localization, however, hinges on a foundational question: when a frozen language model evaluates an unedited code entity from a compact view, which structural relationships make its relevance judgment informative about a nearby repair target? Studying Gemma 4 models across 211 real-world Python issues in 86 repositories, we uncover a systematic directional relevance asymmetry: zero-temperature relevance scores on enclosing scopes and upstream callers consistently separate true structural neighbors from hard lexical distractors, whereas scores on downstream callees, peer methods, historical co-change partners, and dense node embeddings remain near chance. Zero-leakage masked-scope probes and regressions controlling for lexical similarity and snippet length confirm that this asymmetry reflects functional role (callers expose symptom entrypoints delegating to defective routines, while downstream helpers appear benign alone) rather than target leakage or surface overlap. Guided by this finding, we introduce GraphScent, a training-free search controller that propagates out-of-repository, relation-conditioned log-likelihood ratios over runtime Typed-AST multigraphs before resolving ties via a single listwise comparison, alongside AST Ripple, a lightweight post-edit check for missed co-edits. Likelihood calibration prevents overconfident smaller models from chasing false-positive callers while lifting exact localization on lexically hard targets from 12.8 to 23.4 percent at 31B within a single-GPU budget.
BibTeX
@misc{naagarajan2026graphscent,
  author = {Ramesh Arvind Naagarajan},
  title = {{GraphScent: Calibrating Directional Relevance Signals for Bounded-Context Code Localization}},
  year = {2026},
  eprint = {2611.17527},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.17527},
}
Figure