Can this convention encode zero?

Yes. A single byte with final flag 1 and zero payload represents zero, though positive postings gaps normally exclude it.

Can it encode negative values directly?

The nonnegative construction here cannot. A separate signed mapping or format is required.

Does fewer bytes always mean faster queries?

No. Reduced transfer volume and decoding work interact with the rest of the retrieval workload.

AI Glossary / Retrieval and knowledge systems / Intermediate

Variable byte encoding

Definition

Variable byte encoding represents an integer using one or more bytes, reserving a bit in each byte to mark whether the number continues. Small integers use fewer bytes. It is commonly discussed in information retrieval as a way to compress gaps between document identifiers.

What it means

An index often stores a sorted list of document identifiers for each search term. The differences between successive identifiers can be much smaller than the identifiers themselves. A variable-length representation can exploit those small values without allocating a fixed machine-sized field to each one.

This entry uses the textbook's convention: each byte carries seven data bits, and the high bit is 1 on the final byte and 0 on earlier bytes. The seven-bit groups are written most significant first.

Other formats called varints can use the opposite flag convention or a different group order. The general idea is related, but the actual byte streams are not automatically interchangeable. A format specification must make these choices explicit.

How it works

Split a nonnegative integer into groups of seven binary digits. Pad the leading group if necessary to fill its seven data positions. Add a high flag bit to each group, marking only the last group with 1 under this convention.

The decoder starts an accumulator at zero. For each byte, it multiplies the current accumulator by 128 and adds the byte's seven-bit payload. A final-byte flag means the accumulated value is complete and a new integer can begin.

Values from 0 through 127 fit in one byte; values from 128 through 16,383 fit in two. The boundaries follow the seven payload bits available per byte.

When encoding postings gaps, decoding the integers is only the first stage. The system then adds the gaps cumulatively to recover document identifiers. The surrounding format must also describe where a list ends and how its first identifier is represented.

Three practical examples

A keyword index stores short document-ID gaps in one byte instead of a fixed four-byte integer.
An engineer examines values around 127 and 128 to verify that an encoder handles the one-byte boundary correctly.
A data interchange review rejects an assumed compatibility between two varint formats after finding different termination-bit conventions.

Think of it this way

Think of sending a number across several small cards, each with space for part of the number and a box saying whether this is the last card. A small number needs one card; a larger number uses several.

The analogy explains grouping and termination. Actual bytes contain precisely seven payload bits in this format, and their order matters. Merely receiving the right set of cards would not be enough if their sequence changed.

Worked example

Consider document identifiers 3, 130 and 260. Store the first identifier followed by differences, giving integers 3, 127 and 130.

The number 3 has seven-bit payload 0000011. Adding the final flag produces 10000011. The number 127 becomes 11111111: a final flag followed by seven ones.

For 130, divide by 128: 130 = 1 × 128 + 2. Its payload groups are 0000001 and 0000010. The first byte is 00000001, and the final byte is 10000010.

The complete sequence uses four bytes. Decoding recovers 3, 127 and 130; cumulative addition gives 3, 130 and 260 again. A comparison with three fixed four-byte integers gives four versus twelve payload bytes in this invented example, excluding list metadata. This is a small demonstration, not a general compression ratio.

Illustrative case study

The fictional ElmSearch team exchanges a postings file between two prototypes. Both developers describe their format as variable byte, yet the second prototype reconstructs incorrect identifiers.

They compare a two-byte example and discover that one implementation marks continuation with 1 while the other marks termination with 1. They agree on the flag meaning and group order, then add examples crossing several size boundaries.

The team also checks reconstruction of cumulative gaps separately from byte decoding. That catches a second mistake in the treatment of the first identifier. This invented case illustrates interoperability and representation issues; it reports no production benchmark or measured business saving.

Common misconceptions and mistakes

Every number uses exactly one byte. The number of bytes grows when the value exceeds a payload boundary.
All varints share the same layout. Flag meaning, group order and signed-number mappings vary.
Compressing identifiers and compressing gaps are identical. Gap formation changes the input numbers before the byte encoding step.

Business use

Variable byte encoding helps explain the storage and decoding tradeoffs inside search systems. Byte alignment can simplify processing compared with some bit-oriented formats, while small gaps can reduce the amount of stored or transferred data.

Evaluate the complete workload rather than assuming one codec always wins. Record gap distributions, decoding throughput, memory use and metadata costs. Test large values, truncated sequences and accumulator overflow. A missing final-byte marker should be treated as malformed input. For interoperability, publish exact examples with both byte values and the recovered integer sequence.

Check your understanding

Using this entry's convention, decode bytes 00000010 and 10000101 as one integer.

Answer: Their payloads are 2 and 5, so the value is 2 × 128 + 5 = 261. The high bit on the second byte terminates the number.

Related terms

Unary code
Inverted index
Integer compression
varint
postings list
gap encoding
gamma code
byte

Learn next

Compare variable byte and gamma representations for a sequence containing both tiny and large gaps. Count the complete payload size, then identify what additional framing information a usable file would need.

Sources

Christopher Manning, Prabhakar Raghavan and Hinrich Schutze, Introduction to Information Retrieval, Variable byte codes: https://nlp.stanford.edu/IR-book/html/htmledition/variable-byte-codes-1.html

The primary textbook's payload layout and final-byte convention were reviewed. The 3, 130, 260 postings example, byte calculations and fictional interoperability case are original illustrations. No current performance ranking among codecs is asserted.

Previous: Variable bitrate Next: Variable elimination