Identification Capacity and Rate-Query Tradeoffs in Classification Systems

Tristan Simas · 2026

Read Identification Capacity and Rate-Query Tradeoffs in Classification Systems by Tristan Simas (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-14252.txt.

Introduction

Tristan Simas asks a basic question about sorting things into classes in this 2026 paper. An observer must tell which class an entity belongs to, but can only look so much. He extends rate-distortion theory, a classic tool from information theory, to this discrete classification setting. Three costs frame the trade-off.

The first cost is tag rate, the bits of storage kept per entity. The second is identification cost, the number of queries used to test class membership. The third is distortion, the chance of a wrong call. Simas studies how the three costs trade off against each other. His results mark the best balance a system can reach.

Catalog record

CREATORTristan Simas
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE80 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-14252

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Identification Capacity and Rate-Query Tradeoffs in Classification Systems Tristan Simas Abstract We extend classical rate-distortion theory to a discrete classification setting with three resources: tag rate L L (bits of storage per entity), identification cost W W (queries to determine class membership), and distortion D D (misidentification probability). The fundamental question is: how do these resources trade off when an observer must identify an entity’s class from limited observations? Information barrier (zero-error identifiability). When distinct classes share identical attribute profiles, no algorithm, regardless of computational power, can identify the class from attribute queries alone. Formally: if π \pi is not injective on classes, then zero-error identification from attribute queries alone is impossible. Rate-identification tradeoff. We identify the unique Pareto-optimal zero-error point in the ( L , W , D ) (L,W,D) tradeoff space and describe the induced tradeoff geometry. A nominal tag of L = ⌈ log 2 ⁡ k ⌉ L=\lceil\log_{2}k\rceil bits for k k classes yields W = O ⁡ ( 1 ) W=O(1) with D = 0 D=0 . Without tags ( L = 0 L=0 ), zero-error identification requires W = Ω ⁡ ( d ) W=\Omega(d) attribute queries, where d d is the distinguishing dimension; in the worst case d = n d=n (the ambient attribute count), giving W = Ω ⁡ ( n ) W=\Omega(n) . In the presence of attribute collisions, any tag-free scheme incurs D > 0 D>0 . Converse. In any information-barrier domain, any scheme achieving D = 0 D=0 requires L ≥ log 2 ⁡ k L\geq\log_{2}k bits. This is tight: nominal tagging achieves the bound with W = O ⁡ ( 1 ) W=O(1) . Matroid structure. Minimal sufficient query sets form the bases of a matroid. The distinguishing dimension (the common cardinality of all minimal query sets) is well-defined, connecting to zero-error source coding via graph entropy. Applications. The theory instantiates to type systems (duck vs. nominal typing), databases (attribute vs. key lookup), and biological taxonomy (phenotype vs. species identifier). The unbounded gap Ω ⁡ ( d ) \Omega(d) vs. O ⁡ ( 1 ) O(1) (with a worst-case family where d = n d=n ) explains convergence toward hybrid systems combining structural observation with nominal tagging. All results are machine-checked in Lean 4 (6,000+ lines, 0 sorry ). Keywords: rate-distortion theory, identification capacity, zero-error source coding, query complexity, matroid structure, classification systems † † footnotetext: © 2026 Tristan Simas. This work is licensed under CC BY 4.0. License: https://creativecommons.org/licenses/by/4.0/ I Introduction I-A The Identification Problem Consider an encoder-decoder pair communicating about entities from a large universe \mathcal{V} . The decoder must identify each entity, determining which of k classes it belongs to, using only: • A tag of L bits stored with the entity, and/or • Queries to a binary oracle: “does entity v satisfy attribute I ?” This is not reconstruction (the decoder need not recover v ), but identification in the sense of Ahlswede and Dueck [ 1 ] : the decoder must answer “which class?” with zero or bounded error. Our work extends this framework to consider the tradeoff between tag storage, query complexity, and identification accuracy. We prove three results: 1. Information barrier (identifiability limit). When the attribute profile \pi:\mathcal{V}\to\{0,1\}^{n} is not injective on classes, zero-error identification via queries alone is impossible: any decoder produces identical output on colliding classes, so cannot be correct for both. 2. Optimal tagging (achievability). A tag of L=\lceil\log_{2}k\rceil bits achieves zero-error identification with W=O(1) query cost. This is the unique Pareto-optimal point in the (L,W,D) tradeoff space for D=0 in the information-barrier regime. 3. Matroid structure (query complexity). Minimal sufficient query sets form the bases of a matroid. The distinguishing dimension (the common cardinality of all minimal sets) is well-defined and lower-bounds the query cost W for any tag-free scheme. These results are universal: the theory applies to type systems, databases, biological taxonomy, and knowledge graphs. We develop the mathematics in full generality, then exhibit concrete instantiations. I-B The Observation Model We formalize the observational constraint as a family of binary predicates. The terminology is deliberately abstract; concrete instantiations follow in Section VIII . Definition I.1 (Entity space and attribute family) . Let \mathcal{V} be a set of entities (program objects, database records, biological specimens, library items). Let \mathcal{I} be a finite set of attributes : observable properties that partition the entity space. Remark I.2 (Terminology) . We use “attribute” for the abstract concept. In type systems, attributes are interfaces or method signatures . In databases, they are columns . In taxonomy, they are phenotypic characters . In library science, they are facets . The mathematics is identical. Definition I.3 (Interface observation family) . For each I\in\mathcal{I} , define the interface-membership observation q_{I}:\mathcal{V}\to\{0,1\} : q_{I}(v)=\begin{cases}1&\text{if }v\text{ satisfies interface }I\\ 0&\text{otherwise}\end{cases} Let \Phi_{\mathcal{I}}=\{q_{I}:I\in\mathcal{I}\} denote the interface observation family. Remark I.4 (Notation for size parameters) . We write n:=|\mathcal{I}| for the ambient number of available attributes (interfaces). We write d for the distinguishing dimension (the common size of all minimal distinguishing query sets; Definition V.9 ), so d\leq n and there exist worst-case families with d=n . We write m for the number of query sites (call sites) that perform attribute checks in a program or protocol (used only in the complexity-of-maintenance discussion). When discussing a particular identification/verification task, we may write s for the number of attributes actually queried/traversed by the procedure (e.g., members/fields checked in a structural type test, phenotypic characters checked in taxonomy), with s\leq n . Definition I.5 (Interface profile) . The interface profile function \pi:\mathcal{V}\to\{0,1\}^{|\mathcal{I}|} maps each value to its complete interface signature: \pi(v)=(q_{I}(v))_{I\in\mathcal{I}} Definition I.6 (Interface indistinguishability) . Values v,w\in\mathcal{V} are interface-indistinguishable , written v\sim w , iff \pi(v)=\pi(w) . The relation \sim is an equivalence relation. We write [v]_{\sim} for the equivalence class of v . Definition I.7 (Interface-only observer) . An interface-only observer is any procedure whose interaction with a value v\in\mathcal{V} is limited to queries in \Phi_{\mathcal{I}} . Formally, the observer interacts with v only via primitive interface queries q_{I}\in\Phi_{\mathcal{I}} ; hence any transcript (and output) factors through \pi(v) . I-C The Central Question The central question is: what semantic properties can an interface-only observer compute? A semantic property is a function P:\mathcal{V}\to\{0,1\} (or more generally, P:\mathcal{V}\to Y for some codomain Y ). We say P is interface-computable if there exists a function f:\{0,1\}^{|\mathcal{I}|}\to Y such that P(v)=f(\pi(v)) for all v . I-D The Information Barrier Theorem I.8 (Information barrier) . Let P:\mathcal{V}\to Y be any function. If P is interface-computable, then P is constant on \sim -equivalence classes: v\sim w\implies P(v)=P(w) Equivalently: no interface-only observer can compute any property that varies within an equivalence class. Proof. Suppose P is interface-computable via f , i.e., P(v)=f(\pi(v)) for all v . Let v\sim w , so \pi(v)=\pi(w) . Then: P(v)=f(\pi(v))=f(\pi(w))=P(w) \blacksquare Remark I.9 (Information-theoretic nature) . The barrier is informational , not computational. Given unlimited time, memory, and computational power, an interface-only observer still cannot distinguish v from w when \pi(v)=\pi(w) . The constraint is on the evidence itself. Corollary I.10 (Provenance is not interface-computable) . Let \text{type}:\mathcal{V}\to\mathcal{T} be the type assignment function. If there exist values v,w with \pi(v)=\pi(w) but \text{type}(v)\neq\text{type}(w) , then type identity is not interface-computable. Proof. Direct

Read the complete text