Lance FSL Leaf Compression Community Discussion Proposal

[Xuanwo]

Abstract

I propose adding shape-preserving leaf compression for FixedSizeList in Lance File Format 2.3.

The immediate motivation for this proposal comes from token dataset compression: when the input column is FixedSizeList<Int64/UInt64>, Lance v2.2 fixed-size storage currently consumes about 8.03 bytes/token. Given a token vocabulary on the order of 128K, the information-theoretic lower bound is roughly 17 bits/token, i.e., 2.125 bytes/token. Lance's current results essentially indicate that it is still writing out 64-bit raw values without routing the child primitive values through an integer compression path.

The proposed direction is to treat FixedSizeList as a shape layer, treat the primitive child values as a leaf value stream, and apply existing or new general-purpose physical compression on that leaf stream.

The target model is:

FixedSizeList<T>[dimension]
=> FixedSizeListShape {
     dimension,
     validity,
     values: PrimitiveLeaf<T> {
       compression: chosen_by_leaf_statistics
     }
   }

For token IDs, leaf compression would typically choose integer bitpacking. For float embeddings, leaf compression could select byte-stream splitting or general compression. For timestamps, decimals, or integer-like values, the corresponding primitive encodings can also be reused. FixedSizeList itself remains responsible for preserving the fixed shape, while the physical layout of child values is determined by the leaf encoding.

Background

Lance is positioned as a columnar format for ML workloads, and FixedSizeList is a critically important type for such workloads:

• embedding vectors: FixedSizeList<Float32>[dim]
• token IDs: FixedSizeList<Int64/UInt64>[seq_len]
• multimodal feature tensors after flattening
• fixed-shape numeric features

The logical schema for these data types should stay Arrow-native, while the physical encoding should make compression choices based on the actual domain of the leaf values.

Lance’s structure already moves in this direction:

• In the format/proto layer, FixedSizeList.values is already a CompressiveEncoding, which in theory can express combinations such as FixedSizeList -> Bitpacking.
• In the encoding data model, FixedSizeListBlock keeps the dimension and child block.
• The primitive FSL path does not introduce list-style repetition/definition levels for every item, which is the correct behavior for fixed-shape ML data.
• The statistics layer can already observe the primitive domain from the child values.

The gap is that the actual writer/reader paths still largely treat FSL child values as flat raw values. As a result, FixedSizeList<UInt64> token IDs, even when their maximum value is far smaller than 2^64, still consume close to 8 bytes/token.

Proposal

Enable shape-preserving leaf compression for FixedSizeList in Lance 2.3.

Core semantics:

shape layer:
  FixedSizeList / nested FixedSizeList / validity / row-to-item mapping

leaf layer:
  primitive values encoded by normal primitive compression

During writing, the FSL wrapper is responsible for maintaining row boundaries; the leaf encoder is responsible for compressing the primitive item stream.

rows:         N rows
dimension:    D values per row
leaf items:   N * D primitive values

chunk:
  contains whole rows only
  leaf item count = chunk_rows * D
  leaf encoding = chosen primitive encoding for those values

This approach simultaneously ensures that:

• Compression observes the actual primitive value domain.
• Chunk boundaries do not cut across FSL rows.
• take(row) / range scans can still perform chunk-local decoding.
• Decoded leaf values can be unambiguously restored to the original FixedSizeList.
• The primitive encoder does not need to know whether it is wrapped inside an FSL.

The physical encoding for a token column could then become:

FixedSizeList {
  items_per_value: 2048,
  values: OutOfLineBitpacking {
    uncompressed_bits_per_value: 64,
    compressed_bits_per_value: 17
  }
}

This encoding still expresses the same Arrow logical schema:

FixedSizeList<UInt64>[2048]

The change occurs only at the physical encoding level.

Applicability

The same shape-preserving leaf compression mechanism can serve:

• FixedSizeList<UInt64>: integer bitpacking / frame-of-reference / delta-like encoding
• FixedSizeList<Int64>: signed integer encoding, zigzag, frame-of-reference
• FixedSizeList<Float32>: byte-stream splitting, general compression
• FixedSizeList<Boolean>: bitmap / sparsity-aware boolean encoding
• FixedSizeList<FixedSizeList<T>>: stacked shape layers over a single primitive leaf stream

All these types share the same core requirement: the shape layer is responsible for restoring the logical layout, and the leaf layer is responsible for selecting the physical encoding based on the primitive value domain.

Compatibility Boundary

This capability can be introduced as a Lance 2.3 physical encoding feature. The compatibility boundary is:

new reader reads old files: yes
old reader reads new compressed FSL files: no
logical Arrow schema compatibility: yes
physical encoding compatibility without version gate: no

The reason is that although the existing proto shape allows FixedSizeList.values = CompressiveEncoding, the old reader’s implementation semantics do not fully support arbitrary inner encodings. If a new writer directly writes the following under an old file version:

FixedSizeList(values = OutOfLineBitpacking(...))

the old reader may panic, report an internal error, or misinterpret the buffers. This risk cannot be avoided simply by relying on the presence of a proto field.

Therefore, Lance 2.3 should explicitly introduce this feature as a physical encoding capability:

• The reader first gains support for FixedSizeList(values = supported leaf encoding).
• The writer outputs compressed FSL only when the target file version / required feature allows it.
• When writing files for older versions, the writer continues to use FixedSizeList -> Flat.
• When encountering an unsupported FSL leaf encoding, the reader returns a clear error instead of panicking.

The recommended strategy is to gate this capability through the Lance 2.3 file version, because it changes the reader’s semantic contract for FSL inner encodings.

Writer Behavior

A Lance 2.3 writer can enable FSL leaf compression when the following conditions are met:

target file version supports fsl leaf compression
data type is a fixed-shape wrapper over primitive leaf
leaf encoder supports the primitive physical type
estimated encoded size + metadata < raw size
chunk planner can preserve row boundaries

If the benefit is insufficient, the writer continues to write flat. High-entropy 64-bit values entering the FSL path should still maintain the size-based fallback.

The writer does not require explicit user configuration for token columns. The default strategy should be driven by data statistics.

Reader Behavior

A Lance 2.3 reader should change FSL decompression to a wrapper model:

decode FixedSizeList layer:
  read dimension
  read validity
  create leaf decompressor from values encoding
  decode primitive leaf items
  restore FixedSizeList shape

The reader must retain the old path:

FixedSizeList -> Flat

and simultaneously support the new path:

FixedSizeList -> supported primitive leaf encoding

When encountering an unsupported inner encoding, the error should directly state the missing capability, for example:

unsupported FixedSizeList leaf encoding: OutOfLineBitpacking
required reader capability: fixed-size-list-leaf-compression

Expected Impact

For token workloads:

current Lance v2.2: ~8.03 bytes/token
128K vocab lower bound: 17 bits/token = 2.125 bytes/token
target Lance 2.3: close to the bitpacking lower bound plus small metadata overhead

Real-world results will be affected by chunk size, validity, page metadata, signedness, and fallback strategy, but the goal should be to eliminate the ~4× size gap caused by FSL blocking primitive compression.

For non-token workloads:

• Integer FSL can gain bit-width savings based on value range.
• Float FSL can reuse float leaf compression.
• Nested FSL can preserve the shape stack while compressing the leaf stream only once.
• High-entropy data can automatically fall back.

Lance 2.3 Scope

This proposal suggests that the Lance 2.3 implementation scope be converged at the physical encoding layer:

• The logical Arrow schema remains FixedSizeList<T>[dimension].
• The old FixedSizeList -> Flat reader path remains readable.
• New compressed FSL files express the reader requirement through the Lance 2.3 file version.
• The initial leaf encoding can focus on integer bitpacking and flat fallback.
• Variable-size List encoding can continue to evolve as an independent design.
• The logical nullability semantics of FSL stay unchanged.

[westonpace]

+1 I have no problem with pursuing this. I am curious what kinds of tokens you were encountering. When working with embeddings (FSL) I've found that compression is typically a lost cause (embeddings should be high entropy by definition).

Still, there is no harm (other than some write penalty) in attempting to find good compression and there are cases where it can be done (e.g. if the user originally had f16 data and they inflated it into f32 or something like that).

[westonpace]

Also, I think most of this "shape preserving" logic should be there already in the mini-block and full-zip encodings.