Which Flow Architecture Wins Depends on the Dequantizer: Search That Accounts for It

Normalizing flows are generative models that turn simple noise into data through a chain of invertible functions, which lets them compute exact likelihoods. They only work on continuous values. To model discrete data such as pixels, tokens or categorical records, practitioners "dequantize": they add noise so that each discrete point becomes a small continuous box. That noise can be fixed and uniform, or it can come from a second learned model, a dequantizer. Two findings suggest the flow and the dequantizer cannot be designed separately. First, a flow trained under uniform noise wastes capacity modeling the sharp edges of the boxes. Second, an expressive dequantizer can make up for a weak flow. Automated architecture search for flows exists, but it has only been tested on continuous data. On discrete data, it would therefore rank candidate flows under whatever dequantizer happens to be fixed.

This note asks whether that ranking is stable, and builds a search procedure that stays correct when it is not. We will measure how much the ordering of flow architectures changes across dequantizers. We will then extend density-space architecture search to discrete data in two ways. One relaxation shares a single dequantizer across candidates. The other gives each candidate its own lightweight dequantizer. We expect the shared version to show a new failure mode: the dequantizer adapts to the mixture of candidates rather than to the one that is finally selected. This is the density-modeling analogue of the collapse differentiable search suffers when a trained mixture of operations is pruned to a single operation.

Core Claim

We claim three things. On discrete data, the best flow architecture under uniform noise differs from the best one under a learned dequantizer. A search that shares one dequantizer across candidates picks architectures that are overrated. A search that is aware of each candidate's dequantizer, with dequantizer capacity included in the cost, recovers standalone-optimal architectures at the cost of a single supernet training run.

The prior work plays three roles here. It motivates the gap, supplies the method, and constrains the design.

The gap comes from two dequantization papers. Flow++ showed that replacing uniform with variational dequantization alone improved CIFAR-10 by 0.127 bits/dim at fixed parameter count. Learning Discrete Distributions by Dequantization identified the "compensation effect": an autoregressive dequantizer let even a Gaussian-prior flow fit a checkerboard density. Both papers used hand-designed flows, so neither asks whether the compensation changes which flow is best.

The method comes from AutoNF. It relaxes the architecture choice as a convex mixture of candidate densities rather than a sum of operations, which keeps each candidate invertible. It also proves that the relaxed problem converges to a single chosen candidate, and it adds a compute-cost penalty. AutoNF evaluated only continuous UCI data and BSDS300 patches, and it has no dequantization component. We reuse its relaxation and cost term. What we add is the dequantization layer and an analysis of how it interacts with the relaxation.

The constraint comes from differentiable architecture search. Discretization-Aware Architecture Search documents a DARTS supernet dropping from about 88% to about 10% accuracy after pruning, because the shared weights had co-adapted to the mixture. EC-DARTS reports near-zero rank correlation between supernet and standalone performance. We expect a shared dequantizer to be exactly this kind of shared, co-adapting weight.

The Two Relaxations

Let $x$ be a discrete datum, $u$ the dequantization noise, $p_k$ the density of candidate flow $k$, and $\alpha$ the mixture weights on the simplex. The discrete probability of $x$ under candidate $k$ is $P_k(x)=\int p_k(x+u)\,du$.

With a single shared dequantizer $q(u|x)$, Jensen's inequality gives a valid bound on the mixture's log-likelihood:

$$\log \sum_k \alpha_k P_k(x) \;\ge\; \mathbb{E}_{u\sim q(u|x)}\Big[\log \sum_k \alpha_k\, p_k(x+u) - \log q(u|x)\Big].$$

This bound is cheap. Its weakness is that $q$ is optimized for the mixture. When the search collapses $\alpha$ to one candidate, the fitted $q$ is no longer optimal for that candidate, and candidates that benefit most from mixture-tailored noise will look better than they are.

The candidate-aware alternative gives each candidate $k$ its own dequantizer $q_k$. Each $q_k$ is a small head on a shared trunk, and it has its own bound $\mathcal{L}_k(x)\le\log P_k(x)$. The search objective is then:

$$\log \sum_k \alpha_k P_k(x) \;\ge\; \log \sum_k \alpha_k \exp\big(\mathcal{L}_k(x)\big) \;-\; \lambda\big(C_{\text{flow}}(\alpha)+C_{\text{deq}}(\alpha)\big).$$

Here $C_{\text{flow}}$ and $C_{\text{deq}}$ are the expected compute costs of the flow and the dequantizer, and $\lambda$ sets the trade-off. Because the objective is the log of a quantity that is linear in $\alpha$ when the $\mathcal{L}_k$ are held fixed, its maximum lies at a vertex of the simplex. This preserves AutoNF's argument that the search ends on a single candidate. Including dequantizer capacity in the candidate set, as a choice among uniform, small variational and autoregressive dequantizers, makes the search decide explicitly how to split capacity between the flow and the dequantizer. The compensation effect suggests this split should matter.

Research Program

The first phase is a ranking study, and it decides whether the rest of the program is necessary. We will build a small tabular benchmark in the style of NAS-Bench-201, where every architecture in a fixed space is trained standalone and its score is recorded. The space will contain a few hundred flow architectures. They vary coupling type (affine, logistic-mixture CDF as in Flow++, rational-quadratic spline), depth, conditioner width, and whether self-attention is included.

Each architecture will be trained standalone under three dequantizers on binarized MNIST and USCensus90. On binarized MNIST these are uniform, variational and autoregressive. USCensus90 is categorical, so its three are simplex dequantization, argmax dequantization in the style of Argmax Flows, and Voronoi dequantization from Semi-Discrete Normalizing Flows through Differentiable Tessellation. We will report Kendall tau between the architecture rankings produced by different dequantizers, and whether the top-5 architectures overlap. If the rankings agree (tau above roughly 0.9, with the same top architectures), then dequantizer-aware search is unnecessary. In that case we publish the benchmark and the negative result, and stop there.

The second phase implements both relaxations on top of AutoNF's block-by-block search and runs them on the same spaces. Having the benchmark lets us compare the architecture each search selects against the ground-truth standalone optimum.

The third phase scales the better relaxation to CIFAR-10 and text8 under matched compute. There we compare it with hand-designed flows.

Baselines

The naive reference is a hand-designed flow with uniform dequantization, trained standalone at matched parameter count. It shows the cost of doing nothing.

The strongest hand-designed competitors are Flow++ with variational dequantization, which reports 3.08 bits/dim on CIFAR-10 (Flow++), and autoregressive dequantization, which reports 3.06 bits/dim on CIFAR-10 (Learning Discrete Distributions by Dequantization). On binarized MNIST the reference is importance-weighted dequantization at 0.159 bpd, from the same paper. On USCensus90 it is Voronoi dequantization at an NLL of 24.19 (Semi-Discrete Normalizing Flows). For text8, no reported bpc number was found on Lacuna for Voronoi or argmax flows, so we will rerun both.

The strongest search competitor is AutoNF run as published on the discrete data, with its dequantizer fixed. We will run it in two configurations, one with uniform noise and one with a fixed pretrained variational dequantizer. It is the only existing method that searches flow architectures while keeping each candidate invertible.

The key ablation is the shared-dequantizer relaxation against the candidate-aware one, with identical supernet, data and search budget. It isolates whether each candidate's dequantizer needs its own parameters.

Fairness applies throughout. Every final architecture is retrained from scratch with a refit dequantizer, for the same number of steps and with the same hyperparameter sweep. Search cost is reported in GPU-hours, including dequantizer training.

To count as beating AutoNF, the method must do two things. On the tabular benchmark, it must select architectures whose standalone NLL is closer to the oracle than both AutoNF configurations. On CIFAR-10 it must match or beat 3.06–3.08 bits/dim at lower inference cost. Alternatively, it must reach the same bits/dim with fewer flow parameters, where the difference in parameter allocation is attributable to the dequantizer–flow split the search chose.

Why not just…?

Why not just run AutoNF with uniform noise and swap in a variational dequantizer at retraining? This is the hypothesis the ranking study tests. If the rankings under uniform and variational noise agree, this shortcut is correct and we will say so. Flow++'s finding that uniform noise forces the flow to spend capacity on box edges predicts that the uniform-search winner will be over-provisioned. Such a winner would be dominated once a learned dequantizer absorbs that burden.

Why not just fix a strong autoregressive dequantizer and search only the flow? This is the most serious threat, because the compensation effect makes the dequantizer an equally important capacity choice. Fixing it presumes the optimal split between the two models. The AutoNF configuration with a fixed variational dequantizer runs exactly this alternative. If it matches the candidate-aware search on the benchmark, joint search adds nothing and we will report that.

Why not just use random search with short training? NAS-Bench-201 found that random search and evolution often beat DARTS in small spaces. We include random search at equal GPU-hours on the tabular benchmark. Short-trained flow likelihoods are themselves ranking proxies of unknown quality, and the benchmark will measure how well they rank. In small spaces random search could win. The claim of this proposal is about correctness under a fixed search budget, not about beating random search everywhere.

Why not just model discrete data natively and skip dequantization? Native Discrete Flows reach an NLL of 55.62 on USCensus90, against 24.19 for Voronoi dequantization. Autoregressive models sample slowly. The question here only arises for continuous flows used on discrete data.

Decisive Checks

The first check is the phase-one Kendall tau across dequantizers. The second is the "refit gap": the NLL lost when the architecture chosen with a shared dequantizer is evaluated with its search-time dequantizer instead of a refit one. We predict this gap will be large for the shared relaxation, and that the candidate-aware relaxation will close it. The third is whether the searched split between flow and dequantizer capacity moves toward the dequantizer on categorical data, where Voronoi dequantization already wins. If the rankings agree and the refit gap is negligible, the proposal's premise is false, and the benchmark documents that for others.