When AI agents started assisting developers with code, many expected a leap beyond primitive tools. Instead, these agentic coding tools are finding themselves relying on decades-old technology, most notably grep. This reliance highlights a critical gap: the need for advanced search capabilities tailored to AI workflows, a challenge detailed in a recent Cursor Blog post.
For years, developer tools evolved from simple text search utilities like grep to sophisticated Language Server Protocols (LSP) that parse code syntactically. However, the advent of agentic AI has circled back to the basics, with agents frequently employing regular expressions for context gathering. While semantic indexing offers broad improvements, specific queries demand the precision of regex. This has led tools like Cursor to revisit and optimize foundational search algorithms.
The default choice for many agent harnesses, including Cursor's, is ripgrep. Developed by Andrew Gallant, ripgrep offers a faster, more sensible alternative to traditional grep. Its performance is legendary, but it still faces a significant bottleneck: it must scan every file. For developers working with massive monorepos, this can translate to search times exceeding 15 seconds, disrupting the interactive coding experience with AI assistants.
Recognizing this limitation, the focus is shifting to creating specialized indexes for text lookup, mirroring how IDEs build syntactic indexes for features like 'Go To Definition.' This proactive indexing aims to accelerate the core text-searching operations that modern agentic AI relies upon.
The Classic Algorithm: N-grams and Inverted Indexes
The concept of indexing text for faster regular expression matching isn't new, dating back to a 1993 paper by Zobel, Moffat, and Sacks-Davis. Their approach, later popularized by Russ Cox, utilizes n-grams—segments of text of a fixed width 'n'—to build inverted indexes. These indexes map n-grams to the documents they appear in.
An inverted index, the backbone of search engines, works by tokenizing documents. Each unique token (in this case, n-grams) becomes a key, with its value being a list of documents containing that token. Searching involves intersecting these lists to find common documents.
While effective for natural language search, directly applying this to source code for regex matching is problematic. Naive tokenization fails to capture the nuances of programming languages. Early attempts, like GitHub's initial code search, struggled with complex tokenizers and massive search clusters, yielding poor results and failing to match arbitrary regex patterns.
Trigram Decomposition: The Sweet Spot
To bridge the gap, the strategy shifts to trigrams—overlapping sequences of three characters. Using trigrams as tokens offers a balance: too few keys with massive posting lists (like bigrams) or too many keys with tiny posting lists (like quadgrams) are inefficient. Trigrams provide a manageable middle ground.
Indexing involves extracting all overlapping trigrams from a document. The complexity arises when decomposing a regular expression into a queryable set of trigrams. This requires parsing regex syntax and applying heuristics to identify constituent trigrams. Literal strings are straightforward, while alternations and character classes demand more intricate decomposition logic.
This process yields a list of potential documents. The final verification still requires a traditional regex match against this subset, but it drastically reduces the search space compared to scanning the entire codebase.
Beyond Trigrams: Suffix Arrays and Future Directions
Alternative approaches, like suffix arrays, have also been explored. Livegrep's implementation, for instance, indexes all suffixes of a string in a sorted array. Regex searches are then performed via binary searches on this array. While efficient for certain operations, suffix arrays face scalability challenges, especially when dealing with large, dynamic codebases that require concatenation into a single string and complex mapping back to original files.
The ongoing evolution of agentic coding tools necessitates faster, more efficient indexing strategies. As AI assistants become more integrated into the development lifecycle, optimizing core functionalities like text search is paramount. Techniques like probabilistic masks and sparse n-grams are being explored to further refine these search capabilities, ensuring that AI-powered coding remains fluid and productive.
