{"id":"76f82096-2983-4bf4-a83e-b081e258bef8","arxiv_id":"2504.15247","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"Lance's adaptive structural encoding, full-zip for wide values and miniblock for narrow values, achieves faster random access on NVMe storage than Parquet or Arrow without sacrificing scan performance.","lead":"This paper introduces Lance, a columnar storage format whose adaptive structural encoding speeds up random access on NVMe disks. Benchmarking against Parquet and Arrow, the authors report that Lance matches or beats both on random access and full scans.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The 'no RAM trade-off' claim rests on search-cache sizes that favor Lance only for large types; for small types Lance's miniblock metadata can exceed Parquet's page offset index, and no RAM is measured.","rationale":"The reader's weakest assumption was that warm search-cache I/O is amortized away. My concern is adjacent but more specific and more directly tied to the paper's own wording: the abstract promises 'without making trade-offs in ... RAM utilization,' yet no RAM measurement appears in Section 6. The analytical argument for Lance's smaller cache in Section 4.2.4 only covers large data types, where the full-zip encoding has no search cache. For small data types, a simple calculation from the paper's own numbers (24 bytes per miniblock chunk versus 20 bytes per Parquet page) shows Lance's search cache can be about 2.4x larger per value for UInt64, and the repetition index adds further overhead for nested or variable-width types. This does not invalidate the random-access or scan results, but it means the headline claim is overstated unless RAM usage is measured and reported. Since the reader already assigned CONDITIONAL, my verdict remains CONDITIONAL, which corresponds to UNCHANGED in this schema. The concrete test of measuring search-cache sizes for representative small types would settle whether the RAM claim holds or needs to be scoped.","tokens_in":16650,"tokens_out":7872,"duration_ms":71033,"concrete_test":"Instrument lance 2.1 and parquet-rs to report the in-memory search-cache size after opening 100M-row files of UInt64 and Utf8 columns, using the paper's settings (Parquet 8KiB pages, statistics disabled; Lance default parameters). Record bytes per row for Parquet's page offset index and for Lance's miniblock metadata plus repetition index. If Lance's bytes-per-row exceeds Parquet's for these small data types, the 'no RAM trade-off' and 'smaller search cache' claims must be scoped to large data types or the miniblock metadata must be compressed to the 2-byte on-disk form described in Section 4.2.4.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim in the Abstract and Section 7 has three parts: random access, full scan, and RAM utilization. The first two are benchmarked in Section 6, but RAM utilization is only argued analytically, and the argument in Section 4.2.4 is selective. It shows that for large data types Parquet's page offset index needs roughly 20 bytes per page, often one page per value (~20 GiB per billion rows), while Lance's full-zip encoding has no search cache. That is a real advantage. However, for small data types Lance uses the miniblock encoding, whose search cache is 24 bytes per chunk without a repetition index and 41 bytes per chunk with one (Section 4.2.4). Parquet's page offset index is 20 bytes per page. With a 4KiB Lance miniblock, a UInt64 column holds 512 values per chunk, giving 24/512 = 0.047 bytes per value; with an 8KiB Parquet page the same column holds 1024 values, giving 20/1024 = 0.020 bytes per value. Thus for scalar columns Lance requires about 2.4x more RAM for the search cache than Parquet with the paper's own page-size setting. For strings and nested lists, the additional 17-byte repetition index widens the gap. The evaluation is also warm-only (Section 2.3), so the cost of loading and holding this cache is never measured. The 'without RAM utilization trade-offs' claim therefore is not established for small data types, and the stated 'smaller search cache' advantage in Section 7 is inverted for the small-type regime unless the miniblock metadata is compressed or otherwise reduced.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces 'structural encoding' as a unifying lens for understanding how columnar formats lay out nested data, and uses it to analyze Parquet, Arrow/IPC-style layouts, and the authors' Lance 2.1 format. It proposes an adaptive scheme in which large data types use a full-zip encoding with a repetition index, while small data types use a miniblock encoding with chunked opaque compression, plus optional struct packing. The experimental sections compare random access, compression, and full-scan performance on a local NVMe drive, using large datasets to reduce coalescing effects, a tuned best-case Parquet configuration, and direct file-level APIs. The central claim is that Lance achieves better random access than Parquet and Arrow-style encodings without sacrificing scan performance or RAM utilization.","tokens_in":17038,"tokens_out":8386,"duration_ms":76938,"significance":"If the central claims hold, the paper makes a useful design contribution: it identifies structural encoding as a first-class design dimension and shows, at least for the tested NVMe setting, that a format can combine good random access with good scan performance. The experimental design has notable strengths: it explicitly analyzes and mitigates coalescing effects (Section 5.4), benchmarks against a deliberately tuned best-case Parquet rather than a strawman default, uses direct file-level readers, and reports that reproduction scripts are available. The compression comparison across realistic ML-oriented datasets is also valuable. The most consequential claim, however, is the 'without trade-offs in RAM utilization' assertion, and that claim needs substantially stronger support before the paper's main conclusion can be accepted.","major_comments":[{"comment":"The claim that Lance's adaptive encoding provides random access 'without making trade-offs in ... RAM utilization' is not established for the small-data-type regime, which is exactly the regime in which the miniblock encoding is used. Section 4.2.4 states that Lance's miniblock search cache is 24 bytes per chunk without a repetition index and 41 bytes per chunk with one, while Parquet's page offset index is 20 bytes per page. With the paper's own sizes (a 4KiB Lance miniblock and an 8KiB Parquet page), a UInt64 column holds 512 values per Lance chunk and 1024 values per Parquet page, giving 24/512 = 0.047 bytes per value for Lance versus 20/1024 = 0.020 bytes per value for Parquet. Lance's search cache is therefore roughly 2.4x larger for scalar columns under the paper's own settings, and the additional 17-byte repetition index widens the gap for strings and nested types. Because Section 6 evaluates only warm searches (Section 2.3) and reports no memory-footprint measurements, the 'smaller search cache' statement in Section 7 is inverted for the small-type regime. The numerical cap in Section 4.2.4 (1.28 GiB for one billion rows) is also inconsistent with the stated 24 bytes per chunk and 32 values per chunk, since 24 x 10^9/32 = 0.70 GiB; this needs correction and direct measurement.","section":"Section 4.2.4, Abstract, Section 7"},{"comment":"The performance comparisons that carry the paper's main claims are reported without any indication of run-to-run variability. The text describes ten-second averages for random access but does not state whether multiple independent runs were performed, and the figures contain no error bars, confidence intervals, or raw throughput values. This matters because several conclusions are stated as ties or modest margins, such as Lance 'generally tie[ing] or beat[ing] Parquet' on scalar and string categories in Figure 11. Without repeated trials or a variance statement, the central empirical claim cannot be distinguished from machine noise, especially for the sub-10% differences that support the 'no trade-off' conclusion. Please report at least three runs per configuration with standard deviation, or otherwise justify why the observed margins are stable.","section":"Section 6, Figures 10-18"}],"minor_comments":[{"comment":"The Arrow evaluation uses Lance 2.0 as a proxy for Arrow IPC, and Section 5.3 acknowledges one difference: Lance 2.0 uses special offsets for null lists instead of a dedicated validity bitmap. This difference can affect both the number of IOPS and the benefit of coalescing, so the conclusion that Arrow-style encodings 'require too many IOPS' should be stated as applying to the Lance 2.0 approximation, or verified against Arrow IPC directly.","section":"Section 5.3"},{"comment":"The 128-byte threshold for switching between full-zip and miniblock encoding is described as 'based on experimental measurements,' but no measurement or sensitivity analysis is shown. A short threshold sweep would make the adaptive scheme's robustness more convincing.","section":"Section 4.1"},{"comment":"The search cache is defined as aiming for 0.1% of data size, but the later arithmetic in Section 4.2.4 implies larger fractions under the stated settings: Parquet's 20-byte offset entry per 8KiB page is about 0.24% of the page data, and Lance's 24-byte entry per 4KiB miniblock is about 0.59%. Please clarify whether 0.1% is a target, a bound, or an approximate guideline.","section":"Section 2.3"},{"comment":"The phrase 'ascoalesced access' should read 'as coalesced access.'","section":"Section 5.4"},{"comment":"The terms 'miniblock' and 'mini-block' are used inconsistently; please choose one spelling and use it consistently.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"This is a vendor-authored paper evaluating a format developed by the same authors, so the editor should ensure that independent replication is feasible before publication. On the positive side, the benchmarking methodology is considerably more careful than typical vendor benchmarks: the authors tune Parquet to its best configuration, use large datasets to control coalescing, and provide reproduction scripts. The main technical risk is the RAM-utilization claim, which is analytically questionable for small data types and never measured. I would also note that reference [31] is a co-authored submission and reference [20] is a company blog; both are used for substantive claims about Lance's design and should be clearly labeled as such."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The useful core here is the adaptive structural encoding idea: full-zip for wide values, miniblock for narrow ones, with a repetition index and struct packing. That is a real, new systems design, and the paper does a good job separating structural encoding from compressive encoding—a framing worth keeping. The benchmark work is also a cut above the usual vendor post: large datasets to blunt coalescing, best-case Parquet tuning, and direct file-level APIs. The 60x improvement from configuring Parquet properly is a useful data point on its own, and the scan experiments show Lance is at least competitive, often better, on disk utilization.\n\nThe soft spots are real but localized. The stress-test note is right: the 'without RAM utilization trade-offs' claim is not established for small data types. With the paper's own numbers, a 4KiB Lance miniblock costs 24 bytes per chunk versus 20 bytes per Parquet page at 8KiB, which works out to about 0.047 bytes/value for Lance versus 0.020 for Parquet on a UInt64 column. So for scalar columns, Lance's search cache is actually about 2.4x larger, and the repetition index widens that. The paper's Section 4.2.4 argument only covers the large-type case, and Section 7's 'smaller search cache' claim is inverted in the small-type regime. That is a substantive overreach, not a nitpick, though it does not sink the random-access or scan results.\n\nThe evaluation is warm-only, which is a defensible modeling choice for repeated searches, but it means the cost of loading and holding the search cache is never measured, so the RAM claim is analytic rather than empirical. I would also like error bars or repeated runs; the reported numbers are suspiciously clean. The Arrow proxy via Lance 2.0 is reasonable given the API problems with Arrow IPC, but it is still a proxy. Self-citation is not an issue here—the Lance v2 blog and Rottnest are appropriately cited, and the core structural ideas trace back to Dremel.\n\nWho is this for? Practitioners choosing or building columnar formats for NVMe-backed search and retrieval workloads, and researchers working on file format design. It deserves a serious referee; the empirical core is solid enough that the RAM claim can be fixed with additional measurements. I would send it to review with a request to add small-type RAM comparisons and ideally cold-cache numbers.\n\nRecommendation: engage with it, but push on the RAM claim before accepting.","headline":"Genuinely new adaptive structural encoding with careful NVMe benchmarking, but the 'no RAM utilization trade-off' claim only holds for large types and the warm-only evaluation leaves it under-supported.","tokens_in":17530,"tokens_out":1175,"would_cite":true,"duration_ms":12407,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Lance's adaptive structural encoding gives fast random access without scan or RAM trade-offs.","keywords":["columnar storage","random access","structural encoding","NVMe","Parquet","Apache Arrow","Lance","search cache"],"falsifier":"Measure point-lookup throughput on a billion-row Lance file after clearing the page cache and with available RAM set below the size of the search cache, so metadata is re-read from disk on every lookup; if the row-fetch rate falls to Parquet's cold-cache level, the 'no RAM trade-off' claim is falsified.","tokens_in":16479,"feed_emoji":"⚡","tokens_out":10081,"duration_ms":78540,"temperature":0.7,"pith_summary":"The paper argues that the layout of a column's structural metadata—the repetition levels, definition levels, offsets, and validity information—is what decides how many I/O operations a random lookup costs, and that this has been underappreciated relative to compression and encoding choices. It shows that a standard format like Parquet can be tuned for random access with a page offset index, but only by paying for it in scan performance or in the RAM needed to hold per-page metadata. It then presents Lance's structural encoding scheme, which alternates between two layouts: a full-zip encoding that transposes all buffers of a column into one value-by-value record for large data types, and a miniblock encoding that keeps vectorized columnar chunks for small data types. Benchmarks on NVMe storage show Lance matching or beating Parquet and Arrow-style encodings on random access while keeping full-scan throughput and a small search cache. If right, the finding matters because columnar formats are widely assumed to be inherently bad at search-oriented workloads, and it identifies a concrete, format-level reason why that assumption needs revision.","feed_headline":"Lance format gets fast random access without scan trade-offs","feed_subtitle":"The right layout of repetition and validity metadata makes NVMe fast for both scans and point lookups.","key_machinery":"The central objects are the two structural encodings and the rule that chooses between them. In full-zip encoding, the repetition and definition levels of each value are bit-packed into a one-to-four-byte control word and stored immediately before the value's data, so a column becomes a sequence of self-describing records preceded by a repetition index that maps row indices to byte offsets; this gives one or two IOPS per lookup regardless of nesting. In miniblock encoding, arrays are divided into chunks sized to one or two disk sectors (4–8 KiB), each with a small header and its own repetition/definition buffers and data buffers, and the repetition index is reduced to per-chunk counters; this keeps vectorized scans fast for small types. The adaptive rule is a threshold: data types with at least 128 bytes per value use full-zip; smaller types use miniblock. The load-bearing mechanism is the repetition index, which converts arbitrary nesting depth and variable widths into a fixed-cost lookup, and the per-chunk metadata that keeps the search cache small enough to be held in RAM.","core_discovery":"The paper's central claim is that the encoding of a column's structure—how repetition levels, definition levels, offsets, and validity are laid out relative to the data—determines random-access cost in columnar storage, and that this cost can be made nearly independent of nesting depth and data width by choosing the right layout. Parquet, with a page offset index and small pages, achieves strong point-lookup performance but needs about 20 bytes of in-memory search cache per page, which becomes prohibitive for wide types such as embeddings where a page may contain a single value. Arrow-style layouts avoid the cache but require one I/O per buffer, so a nested value like List<String> can cost five IOPS. Lance's scheme alternates: for values of at least 128 bytes it uses full-zip encoding, which interleaves repetition/definition control words and all data buffers into one fixed-layout stream plus a repetition index, giving one or two IOPS for any lookup; for smaller values it uses a miniblock encoding with 4–8 KiB chunks and a 2-byte on-disk chunk header, trading a small amount of read amplification for vectorized encoding and opaque compression. The benchmarks report that this combined scheme matches or exceeds Parquet's random-access rate and full-scan throughput on NVMe without the RAM cost, and avoids the need to tune row-group size.","pith_inferences":["Editorial inference: the same structural-encoding lens should apply to formats beyond Lance—any format that separates structural metadata from data buffers can be analyzed by the number of dependent IOPS per lookup; the paper's methodology suggests a cost model of the form 'IOPS × (1 + nesting) + read amplification + search-cache bytes per value'.","Editorial inference: because the repetition index is itself a bit-packed array that can be range-read, the scheme suggests a testable extension where range scans (e.g., fetching rows 1,000 to 2,000 of nested data) cost two IOPS regardless of length, which could make secondary indexes cheaper by avoiding per-row lookups.","Editorial inference: the adaptive threshold of 128 bytes per value is an empirical constant measured on one NVMe drive; on storage with different IOPS/bandwidth ratios (e.g., cloud object storage with low IOPS), the crossover point between full-zip and miniblock likely moves, so a cost-aware writer that chooses the encoding per column based on device characteristics is a natural follow-up.","Editorial inference: the paper's warm-search assumption means files opened once and queried sparingly would pay metadata-loading IOPS not counted in the benchmarks; for such workloads, a format that inlines minimal metadata or uses a compact on-disk header (like Lance's 2-byte chunk metadata) would close the gap, but the paper does not measure this cold-start case."],"forward_implications":["If Lance's scheme is correct, columnar file formats can serve search workloads such as vector retrieval and RAG directly from NVMe-backed object storage without a separate in-memory copy or a secondary row-oriented format.","Parquet's default configuration leaves a large random-access margin on the table; the paper measures over 60x improvement with correct configuration, implying that existing Parquet users can gain most of the same benefit by enabling page offset indexes and choosing small pages.","The 'no RAM trade-off' claim implies that search caches can be kept at roughly 24–41 bytes per chunk plus a 2-byte on-disk header, which changes the sizing rules for NVMe cache tiers in data-lake engines.","Because repetition and definition levels are Dremel-style, the scheme extends to arbitrary nesting and lists without additional IOPS per level, so applications with deeply nested JSON-like columns can expect point lookup cost to stop growing with nesting depth.","Struct packing offers a tunable knob: packing a struct into a single column trades single-field scan speed for whole-record random access, giving engines a gradient between columnar and row-based layout."],"supporting_citations":[{"why":"Apache Parquet is the primary baseline format whose page offset index and page-size trade-offs anchor the random-access comparisons.","marker":"[12]"},{"why":"Apache Arrow IPC format provides the Arrow-style structural encoding that the paper shows requires multiple IOPS for nested and variable-width values.","marker":"[13]"},{"why":"Supplies the page offset lookup structure that is critical for Parquet random access and serves as the search-cache baseline.","marker":"[19]"},{"why":"Describes the Lance format and its design goals, which this paper extends with the adaptive structural encoding.","marker":"[20]"},{"why":"Introduces repetition and definition levels, the Dremel-style mechanism that Lance's control words and repetition index build on.","marker":"[23]"},{"why":"Shows Parquet can be used for vector search against cloud storage, establishing the IOPS-limited context this work targets.","marker":"[31]"},{"why":"Prior empirical evaluation of ORC and Parquet on vector search that this paper extends with a more detailed NVMe-focused analysis.","marker":"[32]"}],"fun_headline_variants":["Lance's adaptive encodings deliver random access at NVMe speed","No scan or RAM sacrifice: Lance's adaptive layout speeds random access","Lance columnar format: random access without scan or RAM trade-offs","Columnar storage gets random access without scan trade-offs via Lance","Lance's alternating encodings make random access as fast as scans"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing assumption is that the metadata used to locate values—page offsets in Parquet, miniblock and repetition metadata in Lance—fits in RAM and is loaded once, so its own I/O cost is ignored; cold caches or one-off searches would add IOPS that the paper does not measure.","fun_headline_variants_meta":{"raw":{"variants":["Lance's adaptive encodings deliver random access at NVMe speed","No scan or RAM sacrifice: Lance's adaptive layout speeds random access","Lance columnar format: random access without scan or RAM trade-offs","Columnar storage gets random access without scan trade-offs via Lance","Lance's alternating encodings make random access as fast as scans"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001137,"raw_usage":{"total_tokens":4766,"prompt_tokens":1037,"completion_tokens":3729,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":653,"completion_tokens_details":{"reasoning_tokens":3636}},"tokens_in":653,"tokens_out":3729,"duration_ms":23455,"temperature":1.0,"reasoning_tokens":3636,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T11:29:07.723027+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Measure point-lookup throughput on a billion-row Lance file after clearing the page cache and with available RAM set below the size of the search cache, so metadata is re-read from disk on every lookup; if the row-fetch rate falls to Parquet's cold-cache level, the 'no RAM trade-off' claim is falsified.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Apache Parquet is the primary baseline format whose page offset index and page-size trade-offs anchor the random-access comparisons."},{"cited_title":"[n.d.].Arrow Columnar Format","cited_arxiv_id":null,"evidence_quote":"Apache Arrow IPC format provides the Arrow-style structural encoding that the paper shows requires multiple IOPS for nested and variable-width values."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the page offset lookup structure that is critical for Parquet random access and serves as the search-cache baseline."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Describes the Lance format and its design goals, which this paper extends with the adaptive structural encoding."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Shows Parquet can be used for vector search against cloud storage, establishing the IOPS-limited context this work targets."}],"review_version":1}