SwiftNJ: Fast Exact Neighbour Joining via Correctness-Gated Coding Agents

This paper demonstrates that a correctness-gated coding agent can significantly outperform the established RapidNJ baseline in computational phylogenetics by producing SwiftNJ, an optimized Neighbour Joining implementation that achieves a 0.565 geometric-mean runtime ratio while maintaining exact correctness against reference standards.

The Gist

Imagine you are trying to figure out how a group of strangers are related to each other, like building a family tree for a massive crowd. In the world of biology, scientists do this all the time with bacteria and viruses to understand how they evolve. The tool they use to draw these trees is called "Neighbour Joining."

For years, the fastest way to draw these trees has been like a master craftsman using a custom-made, hand-tuned chisel. This "chisel" is a piece of computer code called RapidNJ. It's incredibly fast because it was built by expert human programmers who tweaked every single screw to make it run as efficiently as possible.

The Experiment: Can an AI Apprentice Do Better?

This paper asks a bold question: In 2026, can a super-smart AI coding assistant, acting like a highly skilled apprentice, build a tool that is even faster than the master craftsman's hand-tuned chisel?

To test this, the researchers didn't just let the AI guess. They set up a strict "safety harness." Think of this harness as a rigorous quality control inspector. Every time the AI wrote a new line of code, the inspector checked it against a trusted reference (called QuickTree) to make sure the answer was 100% correct. If the AI made a mistake, the code was rejected immediately. This ensured that while the AI was trying to be faster, it never sacrificed accuracy.

The Result: A New Champion

The AI, guided by this strict inspector, created a new tool called SwiftNJ.

When they put SwiftNJ head-to-head against the old champion (RapidNJ) on a test set of 59 different data puzzles:

• SwiftNJ was, on average, nearly twice as fast (specifically, it took only about 56% of the time the old tool needed).
• It beat the old tool in 58 out of the 59 tests.
• Crucially, on 400 extra tests, SwiftNJ produced the exact same perfect family trees as the trusted reference, proving it didn't cut corners to get its speed.

The Takeaway

This study shows that in the specific, high-stakes world of building evolutionary trees, a human-guided AI can actually outperform the best human-written code that has been optimized for years. It suggests that if you give an AI a strict "rulebook" to ensure it never makes mistakes, it can find clever shortcuts to make complex scientific tools run much faster. However, the paper stops there, noting that we still need to see if this trick works for other types of scientific problems.

Technical Summary

Technical Summary: SwiftNJ: Fast Exact Neighbour Joining via Correctness-Gated Coding Agents

Problem Statement
The paper addresses the variability in the capability profiles of frontier coding agents across different technical domains. Specifically, it investigates whether these agents can contribute to specialized, performance-critical technical work in computational phylogenetics. The focus is on the Neighbour Joining (NJ) algorithm, a standard distance-based method for inferring evolutionary trees used in microbial epidemiology, comparative genomics, and large-scale sequence clustering. While NJ is widely used, its runtime performance is currently dominated by highly optimized, hand-tuned native implementations, such as RapidNJ, which serve as the state-of-the-art baseline. The core question is whether a current-generation coding agent, operating under strict oversight, can surpass the constant-factor runtime performance of these established native binaries.

Methodology
The study employs a "correctness-gated optimisation harness" to guide a coding agent in generating an optimized implementation of the NJ algorithm. The methodology involves:

1. Agent Oversight: The coding agent operates within a harness that enforces deterministic correctness gates.
2. Reference Calibration: These gates are calibrated against a reference implementation, QuickTree, to ensure that any generated code produces mathematically correct phylogenetic trees.
3. Benchmarking: The resulting implementation, named SwiftNJ, is evaluated against a locally rebuilt binary of RapidNJ, a widely cited representative of hand-tuned native implementations.
4. Test Corpus: Evaluation is conducted on a corpus of 59 distance matrices. Additionally, robustness is tested on 400 shuffled inputs derived from 16 small matrices (where $n \le 2000$).

Key Contributions
The primary contribution is the development of SwiftNJ, a high-performance NJ implementation generated by a coding agent under a correctness-gated harness. The paper demonstrates that this approach can produce code that not only matches the functional correctness of established reference tools but also improves upon the runtime performance of strong native baselines.

Results

• Runtime Performance: Across the 59-matrix corpus, SwiftNJ achieved a geometric-mean runtime ratio of 0.565 against the RapidJNI-native binary. This indicates that SwiftNJ is, on average, nearly twice as fast as the baseline.
• Consistency: SwiftNJ demonstrated sub-parity performance (faster than the baseline) on 58 out of 59 matrices.
• Correctness: On the 400 shuffled inputs, SwiftNJ matched the QuickTree reference with a Robinson-Foulds distance of zero, confirming that the performance gains did not come at the cost of algorithmic accuracy.

Significance and Claims
The paper claims that, within the specific domain of computational phylogenetics, a correctness-gated coding agent can meaningfully improve upon a strong, hand-tuned native baseline. This suggests that harness-guided optimization holds promise for accelerating performance-critical bioinformatics tools. However, the authors maintain a modest scope regarding the generalizability of these findings, explicitly stating that further work is required to determine how broadly this approach generalizes to other technical domains. The study serves as a domain-specific empirical investigation into the potential of frontier coding agents for specialized optimization tasks.