acceptodds
Under review as a conference paper at ICLR 2027

Coverage-Gated Coalitional Coding for Multi-Modal Discrete Tokens

Abstract

Discrete multimodal codes, such as semantic IDs, neural codecs, unified tokenizers, are distributed: each token observes only a subset of modalities, and synergistic targets vanish unless every constituent is present. Existing analyses typically treat the tokenizer as a centralized quantizer of a fused vector and report a single rate-distortion curve. That formulation conceals an operational constraint. A missing factor is information-theoretically invisible, independent of decoder skill; even after every factor is covered, recovery remains a finite-rate problem. We develop a coverage-gated theory of this constraint. For independent Gaussian factors and a product interaction, local channels with information budgets attain an exact one-letter MMSE given by a product of scalar Gaussian gains. Average-rate codes replace that product by its concave envelope, which for order has a genuine setup phase ( bits per modality at ). Allocating a global budget across an access hypergraph of such edges is coalitional water-filling, which strictly dominates order-scalar rules; finite tokens inherit a plug-in guarantee. Seeded operational checks recover these predictions. On Flickr8k captions with frozen OpenCLIP residual tokens, exact-budget allocation is compared with MMQ-style shared/specific schedules and a peak-rate analogue of bursting.

Primary area:
learning theory
Keywords:
rate-distortion, discrete tokens, coalitional allocation, residual quantization

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_XgKhOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

The paper studies how separately compressed inputs can support reconstruction of interactions between modalities. For independent Gaussian factors and product targets, it derives reconstruction-error formulas and an average-rate coding characterization, then uses these results to motivate token-budget allocation. Experiments include synthetic checks and a small frozen-OpenCLIP study on Flickr8k.

Critical strengths

The paper explicitly states several limitations of its theoretical guarantees and includes proofs and numerical checks of the mathematical predictions.

Critical weaknesses

The submission does not establish a sufficiently significant contribution for ICLR.

First main weakness: The familiar two-factor setup threshold is inherited from prior work [1], while the importance of the higher-order and unequal-rate extensions is insufficiently demonstrated. Several additional components, including dynamic programming and allocation through standard optimization, provide limited methodological novelty.

Second main weakness: the presentation makes the contribution unnecessarily difficult to assess. Definitions are deferred, terminology is dense and not adequately explained. The lack of overall clarity is apparent from the abstract, which fails to communicate the main objectives, methodology, and contributions of the paper in a comprehensible manner. The abstract introduces several symbols and technical terms without adequately defining or explaining them. For instance, what do rir_i, MMSE, kk, 2Lϵ2L\epsilon, and V/rankV/rank represent? While the reviewer does not claim to be an expert in this specific domain, the abstract appears unnecessarily difficult to follow, potentially even for readers with substantial expertise in the field. This raises concerns also about the overall clarity and organization of the manuscript. No figures are present in the paper, which is not a substantial form of concerns but they would help in better understanding some concepts and formulations.

Minor weaknesses: The connection to practical multimodal tokenizers remains weak. The exact results rely on independent Gaussian factors, product targets, and an architecture that prohibits message reuse across interaction tasks. The real-data experiment does not validate these assumptions or demonstrate a convincing downstream benefit. In Table 7, for example the proposed allocation performs worse than specific-only allocation on retrieval at larger budgets.

The claimed practical error certificate is also insufficiently justified: disagreement between validation subsets does not establish the population estimation-error bound required by the theorem.

[1] O. Ordentlich and Y. Polyanskiy, "Optimal Quantization for Matrix Multiplication," 2025 IEEE International Symposium on Information Theory (ISIT), Ann Arbor, MI, USA, 2025, pp. 1-6, doi: 10.1109/ISIT63088.2025.11195544. keywords: {Lower bound;Vector quantization;Large language models;Loading;Rate-distortion;Lattices;Machine learning;Approximation error;Decoding;Compression algorithms},

Questions for authors

Could the authors clarify the paper’s main novel contributions relative to prior work and explain the practical implications of the analysis? Concrete examples of how the theoretical results inform token-allocation decisions would be particularly helpful.

Reviewer_kiznOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates access constraints and finite-rate allocation in discrete multimodal coding, focusing on synergistic interaction targets that require information from multiple modalities for recovery. The authors first derive an exact MMSE for local encoders under an independent Gaussian product model and characterize the setup phase of higher-order interactions through concave-envelope analysis under average-rate constraints. They then formulate coalitional water-filling on an access hypergraph to allocate coding budgets across multiple interaction targets. The framework is further extended to finite-token allocation using dynamic programming with error guarantees and to dependent modalities through information leakage bounds. Experiments validate the theoretical predictions on synthetic data and evaluate discrete token allocation strategies using frozen OpenCLIP representations on Flickr8k.

Critical strengths

After reading this paper, I find two core strengths provided by authors.

  1. The paper develops a coherent theoretical framework for access-constrained rate–distortion, covering exact Gaussian product MMSE, higher-order setup phases, and coalitional resource allocation. The authors provide both converse and achievability proofs, along with a characterization of the multivariate concave envelope, demonstrating mathematical rigor and theoretical completeness.
  2. The paper systematically validates its main theoretical predictions through synthetic experiments, with results closely matching the derived bounds. The authors also carefully distinguish between independent and dependent modalities, continuous and discrete token budgets, and average-rate and per-sample constraints. The Flickr8k experiments further provide an initial exploration of the framework in a practical multimodal setting.
Critical weaknesses

The main weakness of this paper lies in the gap between its theoretical contributions and their practical validation. While the paper develops a comprehensive theoretical framework around higher-order setup phases and coalitional water-filling, the Flickr8k experiments mainly rely on reconstruction gains measured on the validation set and standard dynamic programming to determine token allocation. It remains unclear how the proposed theoretical results provide additional practical guidance beyond conventional empirical allocation methods, since similar decisions could be made using the same measured gain curves without the Gaussian product theory. Furthermore, the allocation objective minimizes the total reconstruction error across image, text, and joint interaction branches, while the downstream retrieval evaluation only uses unimodal tokens. As a result, allocating more tokens to joint interactions improves reconstruction quality but does not necessarily benefit retrieval performance. In fact, the specific-only strategy achieves better retrieval results at larger token budgets. Therefore, although the experiments support the proposed allocation strategy under its reconstruction objective, they do not sufficiently demonstrate how the theoretical framework translates into meaningful improvements in practical multimodal tasks.

Questions for authors

I hope the authors can clarify the following questions to help me better understand the theoretical contributions and practical value of this work.

1.In the Flickr8k experiments, token allocation mainly relies on reconstruction gains measured on the validation set and standard dynamic programming. Could the authors explain how the proposed setup-phase and coalitional water-filling theory specifically guides token allocation decisions in practice? What additional practical value do these theoretical results provide compared with directly optimizing empirical reconstruction gains? 2.The token allocation objective includes the reconstruction of joint interaction features, but the downstream retrieval evaluation does not use joint tokens. Could the authors explain the motivation behind this evaluation design? Would it be possible to evaluate a downstream task that directly uses joint representations to better demonstrate the benefits of allocating tokens to synergistic information? 3.The main theoretical results rely on specific assumptions, including independent Gaussian factors and an edge-separable coding architecture. However, practical multimodal tokenizers often involve correlated modality representations and information sharing across different coding branches. Could the authors clarify which theoretical conclusions remain applicable in these settings? In particular, does the optimality of coalitional allocation still hold when the same encoded information can be reused across multiple interaction targets? 4.The paper extends previous results on Gaussian product coding to higher-order interactions and uses established tools such as concave envelopes, water-filling, and dynamic programming. Could the authors clarify which theoretical results they consider the most significant new contributions? In particular, what are the main extensions in terms of mathematical results and proof techniques compared with Ordentlich and Polyanskiy (2025)?

Reviewer_6k2ROpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

This paper is an information-theoretical study of tokenizer design for multi-modal models. For independent Gaussian factors and a product interaction, local channels with information budgets ri attain an exact one-letter MMSE given by a product of scalar Gaussian gains. Theorem 2 shows the operational average-rate distortion with an exact converse for separate vector encoders. Theorem 5 is a concave KKT "coalitional water-filling" program over an edge-separable access hypergraph, with a strict-separation example (Corollary 6) against order-scalar allocation rules. Experiments are seeded Monte Carlo verifications of every formula, plus a small frozen-OpenCLIP/Flickr8k allocation study.

Critical strengths

Theorem 18 is a genuine nontrivial contribution: the exact multivariate concave envelope with the contact function A_k and the radial two-point mixture is clean and, to my knowledge, new in this form; the supporting-plane argument is elegant.

Critical weaknesses

The main concerns are about significance and positioning rather than correctness: the mathematical core is a tensorization of the scalar Gaussian RDF equality plus a self-contained concave-envelope computation; the k = 2 equal-rate special case coincides with Ordentlich & Polyanskiy (2025); and the experimental bridge to actual tokenizer design is a small toy example.

The abstract packs setup threshold, water-filling, plug-in bounds, and two experiment suites into six sentences with heavy compound nouns ("peak-rate analogue of bursting"); a reader-neutral sentence stating the single operational recommendation would help.

Questions for authors

The proofs are for independent Gaussian cases. Does the real model follow this condition?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.