We make Dolt, the first version-controlled database. We think that there’s clear value in versioning your data just like you do with code, and our big breakthrough was figuring out how to make that scalable, performance, and space-efficient. We identified that prolly trees, a relatively novel data structure, can be used to implement key-value maps with strong structural sharing between versions alongside efficient diff and merge operations.

We’re not the only ones to figure that out, although we were the first. Bluesky and HuggingFace independently made this discovery and built their data model on the same core structures as Dolt. There are enough different implementations of the concept that there are even research groups creating benchmarks to compare them.

I find this all tremendously exciting. I love it when people recognize our work and engage with it. Not just because the attention is nice, but because it’s just cool to geek out with people over a shared interest.

So imagine my excitement last week when I get this message from Tim, our CEO:

The paper he shared with me claims to have discovered a novel improvement on prolly trees that not only eliminates some of their tradeoffs but also boasts a “30-50% reduction in insertion time for DoltHub workloads.” The paper had even been accepted into the ACM journal “Distributed Ledger Technologies: Research and Practice”.

This was incredible. It was awesome that people were talking about us. I wasn’t bothered that something beat us in a benchmark, because that just meant we had an opportunity to learn from them and improve.

Tim tasked me with reading the paper and their code, and attempting to reproduce their results.

Before I continue, I want to congratulate the authors Abhimanyu Rawat, Tarun Kumar Vangani, and Vanesa Daza, on getting a paper accepted into an ACM journal, which is no easy feat. It’s clear they put a lot of time and effort into their paper, and they identified real improvements to the original prolly tree design. I encourage them to continue to explore this space.

That said, when I read their paper, a couple of issues immediately stood out and gave me some pause.

Imprecise language#

A significant portion of the paper was dedicated to explaining how prolly trees work, but these explanations were in many places vague and informal, with important steps missing and the meaning of some operations undefined.

For example, when they mention DoltHub in their “Related Work” section, they have this to say:

A primary distinction, however, lies in the utilization of a rolling hash for the incoming data at the leaf level to determine the initiation point for boundary node creation. Unlike the Canvas model, the DoltHub approach does not incorporate the concept of an anchor node. Instead, it features a continuous bucket of nodes that receive incoming data nodes, from which no boundary node is derived.

I’m not quite sure what to make of this, because it’s not at all clear what they mean by “a continuous bucket of nodes that receive incoming data nodes” and how that makes our implementation different from Canvas’s.

This is also apparent in their tree construction algorithms (labelled Algorithm 1 and Algorithm 2 in the paper), which describe how to assign levels to tree nodes but glosses over how the a node’s children and edges are determines. It’s possible to infer the gaps, but the descriptions on their own are not sufficient to describe the actual algorithms used.

Filler language#

The language in the paper is also verbose, with many sentences that serve little purpose other than to repeat nonspecific statements about prolly trees.

For example, here’s a paragraph I found early on that could have been cut entirely without changing the meaning of the paper:

4.2 Construction of Prolly Tree The construction of the prolly tree is pivotal, serving as the foundational step to initialize the tree using existing key-value data. This data, irrespective of its origin, is seamlessly integrated into the tree’s framework, demonstrating the implementation’s flexibility. The process of building the prolly tree adheres to two methodologies outlined in Base Level construction Algorithms 1 and Other Levels construction Algorithm 2. These two algorithms play a vital role in bootstrapping a prolly tree.

Confusion and Contradiction#

At times, the explanations in the paper contain errors or contradictions. These appear to be mistakes in the explanation, not problems with the underlying approach. But their presence impedes readability and makes it harder to evaluate the paper’s claims.

For example, when describing how to make sequential updates to a prolly tree in section 4.3, they make the claim that only anchor nodes (the nodes along the right-hand side of the tree) require rehashing. But this is only true in the limited circumstance that the new keys compare greater than every existing key in the tree. This is the most common outcome for their desired use case (where key-values are messages in a distributed system ordered by timestamp), but even then, it’s not guarenteed, and they fail to consider situations where this claim doesn’t hold.

As another example, one of the claims in the abstract is that their alternative tree building algorithm eliminates using a rolling hash, but their description of chunk splitting in section 5.1 explicitly mentions a rolling hash. My interpretation is that they meant to suggest hashing concatenated node key-values here, which is distinct from a rolling hash.

None of these errors invalidate the results, but it obscures the details of the actual research the paper is documenting.

Impossible Results#

The biggest red flag for me was that the explanation that the paper provides for its results is not sufficient to account for the performance improvements that it claims. Although the paper proposes three different improvements, the one that gets the most attention is their decision to add a marker to nodes along the right edge of the tree, giving these nodes the special name of “anchor nodes”. There are legitimate reasons to do this; these are the nodes that don’t contain a boundary key, because the chunker reached the end of the input stream instead. Treating these nodes specially can help prevent a category of errors that occurs attempting to combine changes from multiple prolly trees. But there’s no performance impact to this decision.

The other two proposals (eliminating the rolling hash and batching insert operations) would actually improve the performance of prolly tree operations. But those proposals are not unique to the paper: Dolt already does both of them. Thus, I was skeptical that they could contribute to reducing runtime by 30-50% as was claimed.

Calling in the Expert#

As I mulled over these initial impressions, part of me became paranoid. Was there a chance that at least part of the paper was machine-generated? I felt guilty even thinking it, because the problems in the paper could just as easily be explained because it was written by a student with a non-English first language. If the research was done in good faith, I wanted to engage with it constructively. But it’s also an unfortunate reality that LLMs have resulted in a sharp uptick in error-ridden academic papers. How could I tell the difference?

I decided to rope in my partner Jared, who has a lot more experience with academic research papers than me. I showed him the above excerpts and asked him for his take. He wasn’t sure either, but he pointed out that even if the paper had flaws, it didn’t mean that the results were bad, and this was especially true for non-English researchers.

He gave me the following pieces of advice:

1. Who are the Authors?#

“Who wrote it? What are their credentials? Do they work for reputable institutions, and are those institutions named on the paper?”

The paper has three authors. Abhimanyu Rawat and Vanesa Daza both work for Pompeu Fabra University in Spain. The third author, Tarun Kumar Vangani, works for the Institute for Infocomm Research at A*STAR in Singapore. These are both reputable institutions established in the 1990s. Looking up the names of the authors on the websites for these instutitions revealed that Vanesa Daza is a real professor who has published 31 papers since 2001, and Abhimanyu Rawat and Tarun Kumar Vangani are real students.

This lends weight to the possibility that the research is real.

2. Look at the Citations#

“Are the paper’s citations real? Do the citations say what the paper claims they say? Are the cited works also cited by other papers?”

The first citation is a previous version of the same paper from a conference in 2024, strongly suggesting that the paper was indeed written by the credited authors, without any LLM assistance. Most of the other citations are real: most of them are either cited in the “Related Works” section and are seminal contributions to the field, or are more niche sources (including multiple of our own blog posts), cited in places that make sense for the works being referenced.

This further lends credibility to both the authors and their research.

3. Look at the Supplemental Materials#

For a computer science paper, supplemental materials typically means two things: the raw data used in the paper, and the code used to produce the data.

The code is the more important part, and fortunately, the paper does link to the researcher’s code on GitHub

This code was definitely written by human hands. The comments have a voice and formatting that you wouldn’t see from a machine. They even included a nim port of their code! This gave me hope: even if the paper wasn’t a good representation of the research, the research was real. I hoped that the code itself would do a better job of demonstrating the researcher’s design.

Analyzing the Code#

As a brief aside, one thing that authors do in their implementation is to store each level of the prolly tree in-memory as a doubly-linked list whose values are pointers into the child level. So while they compute a hash for each node. Nodes aren’t stored in a hash table, and traversing the tree does not require lookups in a hash table. Computing Merkle hashes is still useful because it allows for efficient diff operations, even when there’s no hash table.

This is actually pretty interesting and draws from Canvas’s explanation that compares prolly trees to skip lists. It allows for a lot of freedom in how the tree is stored in memory and even allows for things like representing the leaf level of the tree as an arbitrary data structure and passing it to functions that don’t know about prolly trees without requiring any conversion or indirection. I’m not sure if this is immediately useful, but it’s given me some things to think about, and I appreciate the perspective shift it provides.

Now armed with the code, I was finally able to evaluate the claims made in the paper. As per the abstract, they had three novel additions to the prolly tree design:

(1) a deterministic chunking algorithm that eliminates cascading effects by localizing boundary decisions, (2) anchor nodes along the rightmost path that maintain structural stability during sequential insertions, and (3) a batch insertion mechanism that amortizes update costs.

Let’s look at these one at a time, with real code examples.

1. Localizing Boundary Decisions#

The code makes clear that what the authors mean here is eliminating the rolling hash when determining chunk boundaries, instead relying on only hashing an individual key-value pair. To ensure that this key produces different hashes at different tree levels, the tree level is used as a salt.

This is exactly what Dolt does as well. It’s a standard improvement that modern prolly tree implementations use to guarentee that a chunk split doesn’t cause additional chunk splits. But it’s also not without it’s tradeoffs: if every key-value pair is hashed truly independently to determine chunk boundaries, then it necessarily follows that node sizes follow a geometric distribution. This has a negative affect on lookup performance because larger chunks are both more likely to appear on the search path, and take longer to iterate over. We have another blog post that describes this tradeoff in more detail, and the additional steps we’ve taken to mitigate it.

I commend the authors for this discovery but regret to inform them that their approach is not as novel as they were hoping.

2. Designating “Anchor Nodes” on the Tree’s Right Edge#

This was already discussed previously in this article, but to reiterate: treating nodes along the right edge of the tree specially is useful for preventing correctness bugs. A common bug that we’ve seen in prolly tree implementations is assuming that that the final key-value pair in any node exceeded the threshold for creating a new chunk boundary. But this doesn’t hold for nodes along the right edge, and assuming that it does can result in building an incorrect tree. But there is no performance impact from this change.

3. Batching Inserts#

The authors propose batching inserts by creating a separate prolly tree out of the to-be-inserted key-value pairs and then combining it with the original tree via a single tree-walk. This is a creative idea that is indeed a lot more efficient than performing individual insert operations for each new key-value pair.

There are other ways to batch inserts beyond the method described by the authors which predate their proposal. For example, the to-be-inserted pairs could be stored in any kind of ordered data structure, and then inserted into the prolly tree in a single linear pass. This is what Dolt has traditionally done by buffering insert operations into a standard in-memory map before flushing them in large batches.

Using prolly trees instead has some interesting consequences, mainly that it allows for peers in a network to efficiently compare and merging two versions of the same tree, a use case that is valuable for the author’s use cases, although they do not discuss their batch insert proposal in that context.

As for prior art of their specific method of batching, Dolt has a similar optimization that we talk about here. However, our optimization was added in July 2025, while the conference version of the paper was published in December 2024. To the best of our knowledge there was no similar optimization in use at the time, which makes the paper’s proposal truly novel.

Unfortunately, their proposed method cannot account for their results, since it does not appear to be implemented in their code, and does not appear in their benchmarks. Instead, it is framed as possible future work.

It’s also worth noting that when we added our own tree-merging to Dolt, we discovered that while the high-level design was straightforward, the algorithm was actually full of corner cases. It was not sufficient to simply link the nodes together as described by the paper, mostly because the handling the edges of both input trees required special consideration. The majority of the time that we spent implementing the operation was spent making sure that these corner cases were correctly handled.

Understanding the Benchmarks#

So if these changes all already exist in Dolt, how were the paper’s benchmarks able to report 30-50% reduction in runtime for insert operations?

Simply put, the difference can be chalked up to the fact that the author’s code is entirely in-memory, while Dolt is a persistent database where operations are immediately persisted to disk. In order to make the comparison more accurate, the authors would have had to run Dolt on top of a RAM-backed file system, but there’s no indication that the benchmarks they ran did this.

Conclusion#

Again, I commend the authors for their efforts. I love getting to nerd out about algorithms and data structures, and the authors clearly understand the domain and have interesting ideas and a fresh perspective. It’s unfortunate that their proposals don’t actually have the impact that their paper suggests, but I hope that they aren’t too discouraged by this.

If you have any questions or thoughts about the paper or my analysis, feel free to join our Discord and chat with me about it. I hope this blog post makes it clear that I love this kind of discussion.