SpecProto: A Parallelizing Compiler for Speculative Decoding of Large Protocol Buffers Data

Zhijie Wang, Chales Hong, Dhruv Parmar, Shengbo Ma, Zhijia Zhao, Qidong Zhao and 1 other

Protocol Buffers (Protobuf) is the binary format cloud services use to ship data everywhere, but the decoders their compilers generate run on a single core — reading field after field in strict order — so decoding a large blob cannot use the other cores sitting idle; this paper (UC Riverside, NC State — Zhijie Wang, Zhijia Zhao, Xu Liu, and colleagues) presents SpecProto, a compiler that generates parallel decoders by skimming the length-prefixed binary to find independent decode tasks and, when fields are many or uneven, by speculatively cutting the data into equal segments and predicting the decoder state at each boundary — turning a serial decode into one that scales across CPU cores.

The argument in one glance

Problem

Protobuf is everywhere in the cloud, but its decoders run on one core

Protocol Buffers, or Protobuf, is one of the most widely used ways to serialize structured data — to turn a message, defined by a schema, into a compact stream of bytes that can be stored or sent over a network, and later decoded back into fields. It is especially common in cloud environments, where services constantly exchange large volumes of Protobuf-encoded data. The tool that turns a schema into code (a compiler such as the standard protoc) generates a decoder that walks the binary from front to back, reading one field at a time. That is fine for small messages, but for large datasets it is a scalability wall: the decoder is serial, so no matter how many CPU cores a machine has, decoding uses only one of them. As data volumes grow, this single-threaded decode becomes a bottleneck. Parallelizing it is not obvious, because decoding is naturally sequential — you generally cannot tell where the next field begins until you have finished reading the current one. Parallel parsing has been studied for textual formats like XML, but binary formats like Protobuf were left unexplored, even though, as the paper argues, their structure offers unique opportunities that text does not.
What people did

Borrow parallel-parsing ideas from textual formats like XML

The natural place to look is the existing work on parallel parsing of textual, semi-structured formats such as XML and JSON. There, researchers split a document into chunks and parse them on different cores, coping with the fact that a chunk boundary might land in the middle of a tag or a nested structure by reasoning about the parser state at each boundary. The obvious move is to carry these techniques over to Protobuf: cut the binary into pieces and decode the pieces in parallel.
Why it fell short

Text-parsing tricks ignore what makes a binary format both harder and easier

Directly transplanting textual-parsing techniques misses the point in both directions. On one hand, a binary format is harder to split blindly than text: there are no human-readable delimiters, and a byte in the middle of the stream gives no obvious clue whether it starts a new field or sits inside one, so a naive cut can leave a core unable to tell what it is looking at. On the other hand, Protobuf carries structure that text does not expose: length-delimited fields are length-prefixed, meaning each such field announces how many bytes it spans before its contents begin. That prefix is a gift — it lets a reader jump over a field without decoding its interior — and textual-parsing methods, designed for formats without it, never exploit it. So the gap is twofold: existing parallel parsers do not use Protobuf's length prefixes, and they have not confronted the specific difficulty that Protobuf data is often made of many small or unevenly sized fields, which makes balanced parallel decoding tricky. What was missing was a parallelization approach designed for the binary format itself.
This paper's idea

Skim the length prefixes, and speculate decoder state across even cuts

SpecProto is a parallelizing compiler: given a Protobuf schema, it generates a parallel decoder tailored to that schema, rather than the serial decoder standard tools produce. It rests on two techniques. The first is skimming: because Protobuf's length-delimited fields are length-prefixed, SpecProto can quickly traverse the binary by reading each field's tag and length and jumping over its payload, without fully decoding it. This cheap pass identifies independent decoding tasks — regions that can be handed to different cores — by using the structure the format already provides. The second technique addresses a weakness of skimming: when the data contains many small or imbalanced fields, skimming-derived tasks can be uneven or the skim itself costly, so SpecProto adds speculative parallelization. It partitions the binary into even segments, one per core, and because a segment boundary may fall in the middle of a field where the decoder state is unknown, it predicts the decoding state at each boundary, lets every segment decode in parallel on its guess, and reconciles across boundaries. Even segments give balanced work regardless of how the fields are sized. The paper reports that decoders generated by SpecProto achieve significant speedups on real-world and synthetic datasets by using multiple CPU cores.

Why this problem is worth solving

The reason a serial decoder is a real bottleneck, and not a minor inefficiency, is that Protobuf sits on a hot path in cloud systems where data volume only grows.

Serialization formats are the connective tissue of distributed systems: every time a service sends a record to another service, writes a log, or reads a dataset, that data is decoded from its serialized form. Protobuf is a dominant choice for this because it is compact and fast, so decoding it happens constantly and in enormous quantity. When the decoder is single-threaded, its throughput is fixed by one core’s speed no matter how powerful the machine, and modern servers have many cores standing idle during that decode. As datasets grow into the large sizes the paper targets, the gap between what one core can do and what the machine could do widens, and decode time becomes a limiting factor on end-to-end performance. Making the decoder parallel directly converts otherwise-idle cores into throughput on an operation that runs everywhere. That is why an approach that scales Protobuf decoding across cores is worth building: it attacks a ubiquitous, high-volume operation whose cost was previously capped by a single thread.

The deeper insight is that a binary format is not just a harder version of text to parse in parallel — its own encoding hands you a tool that text never had.

Parsing text in parallel is hard because you cannot know, at an arbitrary byte, what structural context you are in — inside a tag, a string, a nested element — without having read everything before it. Binary Protobuf shares part of that difficulty, but it also has a property textual formats lack: its length-delimited fields state their length up front. That single fact changes the game, because it means a reader does not have to decode a field to get past it — it can read the length and skip ahead, cheaply. This is what makes skimming possible: a fast pass that uses only the tags and length prefixes to map out the structure and locate independent pieces of work, at a fraction of the cost of full decoding. Recognizing that the format’s own encoding contains a shortcut to its structure is the conceptual pivot of the paper: instead of treating the binary as an opaque stream to be cut blindly, SpecProto treats the length prefixes as sign-posts. And where those sign-posts are too dense or uneven to give balanced work, it falls back on speculation — guessing state at even cuts — so the approach stays efficient across the messy shapes real Protobuf data takes.

What people did before, and where it broke

Standard Protobuf compilers (protoc). Generate a decoder that reads the binary field by field, front to back. Where it broke. The decoder is strictly serial, so it uses only one CPU core and cannot scale to large datasets no matter how many cores are available.
Parallel parsing of textual formats (XML, JSON). Split a document into chunks and parse them on multiple cores, reasoning about parser state at chunk boundaries. Where it broke. These methods were designed for text without length prefixes, so they do not exploit the structural shortcut Protobuf’s binary encoding provides, and binary parallel decoding was left unexplored.
Blindly cutting the binary into pieces. Divide the byte stream into segments and decode each independently. Where it broke. In a binary format a cut can land inside a field, and there are no delimiters to reveal the decoding state, so a segment cannot tell what it is looking at without help.
Skimming alone. Use the length prefixes to traverse the binary and carve out decoding tasks. Where it broke. When the data has many small or imbalanced fields, the tasks skimming produces can be uneven, giving poor load balance across cores.
The gap. No approach was designed for parallel decoding of the binary format itself — one that both exploits Protobuf’s length prefixes and stays balanced when fields are numerous and unevenly sized.

How SpecProto works

From a serial schema-generated decoder to a parallel one

↓ →
new
↓ →
new
↓ →
new
↓ →
new
↓ →
new

The idea

Use the format’s own length prefixes to skim past what you do not need to decode. SpecProto’s first move is to read only tags and length prefixes to fast-forward through the binary and locate independent work, rather than fully decoding every byte to discover its structure. Exploiting a format’s structural markers to skip rapidly over regions instead of parsing them in full is the same fast-forwarding idea the work on streaming semi-structured data with bit-parallel fast-forwarding (JSONSki) covered elsewhere on this site is built on, jumping over irrelevant content to reach the parts that matter. SpecProto brings that skim-don’t-decode discipline to Protobuf, where the length prefixes make the skip exact.

When the guess is cheap and the check is cheaper, speculate. For data where skimming gives uneven work, SpecProto cuts the binary into equal segments and predicts the decoder state at each boundary, decoding optimistically in parallel and reconciling afterward. Making a prediction to unlock parallel progress and then verifying and fixing it, rather than waiting for the exact answer serially, is the same draft-then-verify strategy the work on a draft-then-verify exploration mechanism (Pruner) covered elsewhere on this site relies on, trading a cheap speculative guess for parallelism. SpecProto speculates about decoder state at segment boundaries so every core can start immediately on balanced work.

Generate the specialized decoder from the schema with a compiler. Rather than a fixed library routine, SpecProto is a compiler that takes a Protobuf schema and emits a parallel decoder tailored to it, baking the skimming and speculation logic into generated code. Turning a high-level specification into efficient, specialized, parallel low-level code through a compiler is the same code-generation approach the work on a compiler for vectorizing encrypted arithmetic circuits (Coyote) covered elsewhere on this site takes, producing parallel executables from a declarative description. SpecProto plays the role protoc does today, but its generated decoders scale across cores instead of running on one.

Following a large binary through SpecProto

Decoding one large Protobuf binary in parallel

A walkthrough, at the level the paper's abstract describes, of SpecProto's two techniques. The full paper was not available for this explainer, so internal mechanism details are omitted.

Step 1 of 5

Compile the schema to a parallel decoder

A developer runs SpecProto on their Protobuf schema. Instead of a serial decoder, it generates one specialized to that schema but built to run across multiple CPU cores, containing both the skimming and the speculative-parallelization logic.

This is a compile-time step, done once per schema.

Why it works

Length prefixes make skimming exact and cheap. Text has no reliable way to skip a region without parsing it → but Protobuf length-delimited fields announce their span → so a reader can jump over a field by reading only its prefix.
Skimming finds parallelism without full decoding. Discovering structure normally means decoding everything serially → but a skim reads only tags and lengths to map the binary → so independent decoding tasks emerge at a fraction of the cost.
Even segments balance the load skimming cannot. Many small or uneven fields make skim-derived tasks lopsided → but cutting the binary into equal segments → so every core gets the same amount of work regardless of field sizes.
Speculating boundary state unlocks the even cuts. A segment boundary inside a field leaves the decoder state unknown → but predicting that state and reconciling later → so each segment decodes in parallel instead of waiting its turn.
Compiling from the schema specializes the decoder. A generic parallel routine cannot know a message’s shape → but generating decoder code from the specific schema → so the skimming and speculation are tailored to the data being decoded.

What it costs (trade-offs and scope)

Speculation can be wrong and must be reconciled. Predicting the decoder state at a boundary means some guesses may need correcting, so speculative parallelization carries reconciliation work and the risk of misprediction cost, which the abstract does not quantify here.
Skimming and speculation suit different data. The paper presents two techniques because neither alone is best everywhere — skimming shines when fields are large and regular, speculation when they are many or uneven — so the decoder must choose or combine them appropriately.
The benefit needs large data and spare cores. Parallel decoding pays off on large binaries and multi-core machines; for small messages the coordination overhead may not be worth it, so the gains are a large-dataset story.
It targets the Protobuf binary format specifically. The techniques lean on Protobuf’s length-prefixed encoding, so they are not a drop-in for arbitrary formats, though the ideas may transfer to other length-prefixed binary formats.
This explainer is built from the abstract only. The exact skimming and speculation algorithms, how state is predicted and reconciled, the datasets, and the measured speedup numbers are in the full paper, which was not available here; only the abstract’s stated design and its claim of significant speedups are reported.

The comparison

Decoding large Protobuf data

Property	Standard serial decoder	Blind chunking	SpecProto
Uses multiple cores
Uses Protobuf length prefixes
Handles a cut inside a field
Balances work across cores
Reported outcome

A comparison of ways to decode large Protobuf data. Standard compilers generate a serial decoder capped by one core; blindly chunking a binary fails because a cut can land inside a field with no way to recover the decoder state. SpecProto generates a parallel decoder that skims the length-prefixed binary to find independent tasks and, for many small or imbalanced fields, speculatively cuts the data into even segments and predicts decoder state at each boundary — reporting significant speedups on real-world and synthetic datasets using multiple CPU cores. Exact figures should be read from the paper.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

This explainer is based only on the paper’s abstract and TLDR (obtained via Semantic Scholar); the full text was not available — the paper is behind the ACM Digital Library with no open preprint reachable at the time of writing, so this page is marked a draft. What is reported here is what the abstract states: Protobuf compilers generate only serial decoders, limiting scalability for large datasets; parallel parsing has been studied for textual formats like XML but binary formats like Protobuf were unexplored; and the paper proposes two techniques for parallel Protobuf decoding — skimming, which leverages Protobuf’s length-prefixed encoding to traverse the binary and identify decoding tasks, and speculative parallelization, which partitions a binary into even segments and predicts decoding states across boundaries to handle many small or imbalanced fields. These are implemented in SpecProto, a parallelizing compiler that generates parallel decoders for a given Protobuf schema, and the abstract reports significant speedups on real-world and synthetic datasets using multiple CPU cores. Everything beyond these claims — the exact skimming and speculation algorithms, how decoder state is predicted and reconciled, the benchmark datasets, and the specific speedup numbers — is not contained in the abstract and should be read in the full paper. Background on Protobuf, serialization, length-prefixed encoding, and parallel parsing is standard context, and the step-by-step walkthrough is an illustration at the abstract’s level, not a verbatim trace of the paper’s mechanism.

Background

Why parsing keeps being a target for parallelism, and why binary is a new frontier

It helps to see SpecProto within a long line of work on speeding up parsing. Parsing — turning a stream of bytes into structured data — is one of the most universal operations in computing, and it has historically resisted parallelism because it feels inherently sequential: you seem to need to read everything up to a point to know what that point means. Researchers have chipped away at this for textual, semi-structured formats, using bit-level tricks, SIMD, and speculation to parse XML and JSON across lanes and cores. Binary serialization formats like Protobuf are a newer frontier, and the paper’s argument is that they are not merely a harder version of the same problem but a different one, because their encoding carries structural information — length prefixes — that text lacks. The recurring theme across all this work is spreading irregular, data-dependent work evenly across parallel hardware, which is exactly why SpecProto pairs skimming with even-segment speculation. This effort to take a stubbornly sequential-seeming computation and spread it across many cores, balancing uneven work, is the same terrain the work on supporting dynamic task parallelism beyond static parallel loops (dynamic task parallelism) covered elsewhere on this site occupies, keeping cores busy on irregular workloads. SpecProto’s particular contribution is to show that a binary format’s own structure can be turned into parallelism, and to deliver it through a compiler that generates the parallel decoder automatically.

If you remember only three things

1. Protobuf is a dominant binary serialization format in the cloud, but the compilers that turn a schema into a decoder produce only serial decoders — they read a binary field by field, front to back, so decoding a large dataset uses a single CPU core no matter how many the machine has. This is a scalability wall. Parallelizing it is non-obvious because decoding seems inherently sequential, and while parallel parsing had been studied for textual formats like XML, parallel decoding of binary formats like Protobuf was unexplored, even though the binary encoding offers opportunities text does not.
2. SpecProto is a parallelizing compiler that generates parallel decoders from a Protobuf schema, using two techniques. Skimming leverages Protobuf's length-prefixed encoding: because length-delimited fields announce their size, the decoder can read only tags and length prefixes to jump over payloads, cheaply mapping the binary and identifying independent decoding tasks for different cores. Because many small or imbalanced fields can make skimming-derived tasks uneven, SpecProto adds speculative parallelization: it cuts the binary into equal-size segments for balanced work, and since a boundary may fall inside a field, it predicts the decoder state at each boundary, decodes all segments in parallel on those predictions, and reconciles across boundaries to produce the same result a serial decoder would.
3. The payoff, per the abstract, is significant speedups on real-world and synthetic datasets by using multiple CPU cores — converting otherwise-idle cores into throughput on a ubiquitous, high-volume operation. This explainer is drawn only from the paper's abstract, since the full text was not reachable, so the exact skimming and speculation algorithms, how decoder state is predicted and reconciled, the benchmark datasets, and the specific speedup figures are not covered here and should be read in the full paper. The core idea is clear, though: a binary format's own structure — its length prefixes — can be turned into parallelism, and a compiler can generate that parallel decoder automatically.

Check yourself

Check your understanding

1. Why is decoding large Protobuf data a scalability problem?
2. What structural property of Protobuf does SpecProto's skimming technique exploit?
3. Why does SpecProto add speculative parallelization on top of skimming?
4. What is SpecProto, and how should this page be read?

Sources

The paper is “SpecProto: A Parallelizing Compiler for Speculative Decoding of Large Protocol Buffers Data” by Zhijie Wang, Chales Hong, Dhruv Parmar, Shengbo Ma, Zhijia Zhao, Qidong Zhao, and Xu Liu (University of California, Riverside and North Carolina State University), published at ASPLOS 2026, DOI 10.1145/3779212.3790225.

This explainer is written only from the paper’s abstract and TLDR, obtained via the Semantic Scholar API; the full text was not available, because the paper is behind the ACM Digital Library and no open preprint was reachable at the time of writing. Accordingly this page is marked a draft. The abstract describes SpecProto as a parallelizing compiler that generates parallel decoders for a given Protobuf schema, using two techniques: skimming, which leverages Protobuf’s length-prefixed encoding to traverse the binary and identify decoding tasks, and speculative parallelization, which partitions a binary into even segments and predicts decoding states across boundaries to handle many small or imbalanced fields. The abstract reports significant speedups on real-world and synthetic datasets by leveraging multiple CPU cores. Background on Protobuf, serialization, length-prefixed encoding, and parallel parsing is standard context. All quantitative claims are the paper’s own; the internal mechanisms and full evaluation, including specific speedup numbers, should be confirmed in the paper.