DyCoder: How Human Developers Think About Code Dependencies

Repository-level code generation requires reasoning over complex dependencies. Early RAG approaches use similarity-based retrieval, which misses dependent code. Recent work introduces graph-based retrieval, but relies on static global graphs that are expensive to maintain.

Human developers don't build global dependency graphs. They implicitly construct partial dependency graphs and iteratively inspect along them. DyRetriever replicates this behaviour: an LLM selects entry-point functions, performs multi-hop reasoning along the dependency graph, and validates semantically — all on-demand.

The result: +25.63% Pass@1 on CoderEval, +59.73% on DevEval, and 7.4x faster than static graph baselines.

The Code Retrieval Problem

When generating code for a function, you need context from:

• Direct dependencies: Functions called by the target
• Transitive dependencies: Functions called by dependencies
• Type definitions: Interfaces, data structures
• Imports: External modules, packages

Similarity-based retrieval (vector search) fails here. It finds semantically similar code, not structurally dependent code.

# Target function to generate
def calculate_user_revenue(user_id):
    # Needs: get_user(), get_orders(), calculate_total()
    pass

# Vector search might return:
# - calculate_total_sales()  # Similar text, wrong context
# - get_user_profile()       # Similar name, wrong dependency

# What you actually need:
# - get_user()               # Direct dependency
# - get_orders(user_id)      # Direct dependency
# - calculate_total(orders)  # Direct dependency

Graph-based retrieval helps, but static global graphs have problems:

• Construction cost: Parse entire codebase upfront
• Maintenance cost: Rebuild on every change
• Memory cost: Store all dependencies for all files
• Flexibility: Cannot adapt to different generation tasks

DyRetriever's Solution: Partial Graphs On-Demand

DyRetriever replicates human developer behaviour:

1. Entry-Point Selection

The LLM selects entry-point functions relevant to the generation task:

def select_entry_points(query, codebase):
    # Query: "Generate calculate_user_revenue function"
    # LLM identifies likely entry points:
    candidates = [
        "get_user",
        "get_orders", 
        "calculate_total",
        "User",
        "Order"
    ]
    return candidates

2. Multi-Hop Reasoning Along Dependencies

Starting from entry points, the LLM performs multi-hop traversal along the dependency graph:

Entry: calculate_user_revenue
  │
  ├─► get_user (direct call)
  │     │
  │     └─► User class (type dependency)
  │           │
  │           └─► User.__init__ (method dependency)
  │
  ├─► get_orders (direct call)
  │     │
  │     └─► Order class (type dependency)
  │
  └─► calculate_total (direct call)
        │
        └─► Order.total property (attribute dependency)

Each hop is validated semantically by the LLM:

• "Does get_user actually return the User type needed?"
• "Is calculate_total the right function for this context?"
• "Should I explore this dependency further?"

3. Semantic Validation

Unlike static graph traversal (follow all edges), DyRetriever validates each step:

def validate_hop(current_func, next_func, context):
    # LLM judges: is this dependency relevant?
    prompt = f"""
    Target: {current_func}
    Candidate dependency: {next_func}
    Generation context: {context}
    
    Is {next_func} relevant for generating {current_func}?
    Answer: Yes/No + explanation
    """
    return llm.generate(prompt)

This eliminates manually designed rules (e.g., "follow all import edges") and enables flexibility across scenarios.

4. On-Demand Construction

Instead of a static global graph, DyRetriever builds partial graphs on-demand:

def build_partial_graph(entry_points, max_depth=3):
    graph = DependencyGraph()
    visited = set()
    
    def traverse(func, depth):
        if depth > max_depth or func in visited:
            return
        visited.add(func)
        graph.add_node(func)
        
        # Parse only this function's dependencies
        deps = parse_dependencies(func)
        for dep in deps:
            graph.add_edge(func, dep)
            traverse(dep, depth + 1)
    
    for entry in entry_points:
        traverse(entry, 0)
    
    return graph

Key insight: Build only what you need, discard after use.

The DyCoder System

DyCoder integrates DyRetriever with a similarity-based retriever:

┌─────────────────┐      ┌──────────────────┐
│  Query          │      │  Similarity      │
│  "Generate X"   │─────►│  Retriever       │
└─────────────────┘      │  (vector search) │
                         └────────┬─────────┘
                                  │
                                  ▼
                         ┌──────────────────┐
                         │  DyRetriever     │
                         │  (dependency     │
                         │   traversal)     │
                         └────────┬─────────┘
                                  │
                                  ▼
                         ┌──────────────────┐
                         │  Combined        │
                         │  Context         │
                         └────────┬─────────┘
                                  │
                                  ▼
                         ┌──────────────────┐
                         │  LLM Generation  │
                         └──────────────────┘

Similarity retriever finds semantically relevant code. DyRetriever finds structurally dependent code. Combined context beats either alone.

What the Benchmarks Say

DyCoder was evaluated on two repository-level code generation benchmarks:

Benchmark	Task	Similarity-Only	Graph-RAG	DyCoder	Improvement
CoderEval	Function generation	0.31 Pass@1	0.38 Pass@1	0.39 Pass@1	+25.63% vs similarity
DevEval	Repository-level	0.18 Pass@1	0.24 Pass@1	0.29 Pass@1	+59.73% vs similarity

Pass@1 values are rounded to two decimal places; improvement percentages are calculated from unrounded values.

Key findings:

• DyCoder beats all RAG-based methods on both benchmarks
• 7.4x faster than static graph construction baselines
• Partial graphs reduce memory by 60-80% vs global graphs
• Semantic validation reduces noise in retrieved context

Production Considerations

Dependency Parsing

DyRetriever needs language-specific dependency parsers:

# Python dependency parsing
def parse_python_dependencies(func_source):
    import ast
    
    tree = ast.parse(func_source)
    deps = set()
    
    for node in ast.walk(tree):
        if isinstance(node, ast.Call):
            if isinstance(node.func, ast.Name):
                deps.add(node.func.id)
            elif isinstance(node.func, ast.Attribute):
                deps.add(node.func.attr)
        elif isinstance(node, ast.Import):
            for alias in node.names:
                deps.add(alias.name)
        elif isinstance(node, ast.ImportFrom):
            if node.module:
                deps.add(node.module)
    
    return deps

# TypeScript/JavaScript, Java, etc. need separate parsers

Existing tools:

• Python: ast, libcst, pydeps
• TypeScript: @typescript-eslint/parser
• Java: Eclipse JDT, JavaParser
• Rust: rust-analyzer

Graph Storage

Partial graphs are ephemeral — built and discarded per query:

class EphemeralDependencyGraph:
    def __init__(self):
        self.nodes = {}
        self.edges = []
    
    def add_node(self, func_name, metadata):
        self.nodes[func_name] = metadata
    
    def add_edge(self, from_func, to_func, edge_type):
        self.edges.append((from_func, to_func, edge_type))
    
    def to_context_string(self) -> str:
        # Convert to text format for LLM context
        lines = []
        for node, meta in self.nodes.items():
            lines.append(f"Function: {node}")
            lines.append(f"  Signature: {meta['signature']}")
        for src, dst, typ in self.edges:
            lines.append(f"  {src} ──[{typ}]──► {dst}")
        return "\n".join(lines)

Cost Implications

DyCoder adds traversal overhead but reduces context waste:

• Graph construction: 50-200ms per query (partial, on-demand)
• Semantic validation: 100-300ms per hop (LLM calls)
• Context efficiency: 40-60% fewer irrelevant tokens
• Memory: 60-80% reduction vs global graphs

For production: net positive for repository-level generation.

Implementation Pattern

Here's the minimal architecture:

class DyRetriever:
    def __init__(self, codebase, llm, parser):
        self.codebase = codebase
        self.llm = llm
        self.parser = parser
    
    def retrieve(self, query):
        # Step 1: Select entry points
        entries = self.llm.select_entry_points(query, self.codebase)
        
        # Step 2: Build partial graph on-demand
        graph = self._build_partial_graph(entries)
        
        # Step 3: Validate edges semantically
        valid_graph = self._validate_edges(graph)
        
        # Step 4: Extract context
        context = self._extract_context(valid_graph)
        
        return context
    
    def _build_partial_graph(self, entries, max_depth=3):
        graph = EphemeralDependencyGraph()
        visited = set()
        
        def traverse(func, depth):
            if depth > max_depth or func in visited:
                return
            
            visited.add(func)
            source = self.codebase.get_source(func)
            graph.add_node(func, {"source": source})
            
            deps = self.parser.parse(source)
            for dep in deps:
                graph.add_edge(func, dep, "calls")
                traverse(dep, depth + 1)
        
        for entry in entries:
            traverse(entry, 0)
        
        return graph
    
    def _validate_edges(self, graph):
        valid = EphemeralDependencyGraph()
        valid.nodes = graph.nodes.copy()
        
        for src, dst, typ in graph.edges:
            is_valid = self.llm.validate_dependency(src, dst, typ)
            if is_valid:
                valid.add_edge(src, dst, typ)
        
        return valid
    
    def _extract_context(self, graph):
        """Convert validated dependency graph into LLM context string."""
        return graph.to_context_string()

## Where the Field Is Heading

DyCoder reveals three trends:

### 1. Partial Over Global

Static global graphs are expensive. **Partial, on-demand graphs** are the future for code retrieval.

### 2. Semantic Validation Over Rules

Manually designed traversal rules (follow all imports, follow all calls) are brittle. **LLM-validated edges** adapt to context.

### 3. Human-Inspired Patterns

Human developers don't think in global graphs. They **incrementally explore dependencies**. Replicating this pattern beats engineered solutions.

## The Bottom Line

DyCoder solves the code retrieval problem by:
- **Selecting** entry points via LLM
- **Building** partial dependency graphs on-demand
- **Validating** edges semantically
- **Discarding** graphs after use

For repository-level code generation, the implication is clear: **partial beats global**. Human-inspired patterns outperform engineered solutions.

---

## Further Reading

- **DyCoder paper:** [arXiv:2608.01927](https://arxiv.org/abs/2608.01927)
- **ACE-GraphRAG:** Context engineering for GraphRAG [arXiv:2608.01269](https://arxiv.org/abs/2608.01269)
- **DocNavRAG:** Document navigation pattern [arXiv:2608.01565](https://arxiv.org/abs/2608.01565)
- **PGMem:** Persona-memory graph for agent memory [arXiv:2608.01708](https://arxiv.org/abs/2608.01708)