Codebase-scale retrieval using AST-derived graphs + BM25 — reducing LLM context from 100K to 5K tokens [D]
Our take
In the rapidly evolving landscape of machine learning and code understanding, the approach to retrieval-augmented generation (RAG) showcased in the article presents a significant advancement. Traditional methods often struggle with the complexities inherent in codebases, primarily due to the limitations of chunk-based text segmenting. The author’s innovative use of Abstract Syntax Tree (AST)-derived graphs addresses a critical gap: capturing the structural relationships between code components. This is not merely a technical refinement; it fundamentally enhances how we think about data retrieval in programming contexts. For those wrestling with limitations in their own RAG systems, as discussed in articles like [Three limitations I keep hitting with retrieval-augmented generation in production and I'm running out of ideas [D]](/post/three-limitations-i-keep-hitting-with-retrieval-augmented-ge-cmoh5dq4c149vzxsxzrrakema), this method could serve as a beacon of potential solutions.
The AST-derived graph approach stands out because it aligns with the inherent nature of code: it is not just text but a structured representation of logic and relationships. By parsing code into a typed node and edge graph, the author effectively transforms static code into a dynamic, interrelated structure that mirrors the code’s operational dependencies. This is crucial because, in programming, a function's utility often depends on its interactions with other functions and types across different files. The author emphasizes that by utilizing BM25 scoring over node metadata instead of relying solely on semantic embeddings, the method significantly reduces the context needed for large codebases—from approximately 100K tokens to about 5K tokens. This efficiency not only streamlines the retrieval process but also enhances the relevance of returned results, ultimately improving developer productivity.
Moreover, the methodology invites a deeper discussion about the appropriateness of retrieval techniques in different contexts. The decision to rely on BM25 rather than embedding similarity highlights the nuanced nature of code queries, where lexical distinctiveness plays a crucial role. This raises important questions about the future of retrieval systems: how can we continue to refine these techniques for various data types? As the author notes, there are still open questions about edge-weighting strategies and the potential benefits of cross-encoders. These considerations are vital for practitioners seeking to optimize their systems further.
Looking ahead, the implications of this approach extend beyond mere efficiency. They challenge developers and researchers to rethink their assumptions about data retrieval in programming contexts. What if, as the author suggests, we could leverage ASTs not only for code but also for other structured data formats? The potential for cross-disciplinary applications could redefine how we approach data management and retrieval across various fields. As we continue to innovate and explore these avenues, it will be fascinating to see how the community responds to these challenges and whether new paradigms will emerge in the realm of retrieval-augmented generation. For now, the conversation around AST-derived graphs and their applicability is one worth watching closely.
Wanted to share an approach I've been using for retrieval-augmented generation over large codebases and get feedback from people thinking about similar problems.
The problem Naive codebase RAG typically works by chunking files into text segments and embedding them for similarity search. This breaks down on code because semantic similarity at the chunk level doesn't capture structural relationships — a function in file A calling a type defined in file C won't surface that dependency through embedding proximity alone.
The approach: AST-derived typed graphs Instead of chunking, I parse every file using Tree-sitter into its AST, then extract a typed node/edge graph:
- Nodes: functions, classes, interfaces, types, modules
- Edges: imports, exports, call relationships, inheritance, composition
This gets stored in SQLite as a persistent graph. Parse cost is one-time per project.
Retrieval: BM25 over graph nodes At query time, instead of embedding similarity, I run BM25 scoring over node metadata (names, signatures, docstrings, file paths). Top-scoring nodes get passed to the LLM. The graph structure means a retrieved function automatically pulls in its direct dependencies via edge traversal.
Empirically this lands at ~5K tokens per query on medium-large codebases that would otherwise require ~100K tokens with naive full-context approaches.
Hierarchical fallback for complex queries For multi-file reasoning tasks:
- A Mermaid diagram of the full graph serves as a persistent architectural map always in context
- BM25 node retrieval handles targeted lookup
- At 70% context capacity, a fast model compresses least-relevant nodes before passing to the primary model
Why BM25 over embeddings here Code identifiers (function names, type names, module paths) are highly distinctive lexically. BM25 outperforms embedding similarity on exact and near-exact identifier matching, which is the dominant retrieval pattern in code queries. Embeddings would likely help more for natural language docstring queries — haven't benchmarked that comparison rigorously yet.
Open questions I'm still thinking about:
- Better edge-weighting strategies for the graph — currently all edges are unweighted
- Whether re-ranking with a cross-encoder would meaningfully improve precision over BM25 alone
- Handling dynamic languages where call graphs can't be fully resolved statically
Has anyone tackled codebase-scale RAG differently? Particularly curious if anyone's compared AST-graph approaches against embedding-based chunk retrieval on real codebases with quantitative benchmarks.
[link] [comments]
Read on the original site
Open the publisher's page for the full experience