One Proposal for Every Margin: Zero-Shot Amortized Sequential Importance Sampling for Binary Matrices
Abstract
In ecology, psychometrics, and the analysis of social and financial networks, binary matrices are often analyzed conditional on their observed row and column sums, which restricts the problem to a finite sample space of matrices with the same margins. Two fundamental problems are to count this space and to sample uniformly from it. Sequential importance sampling (SIS) addresses both with independent weighted samples and an unbiased count estimator, but its efficiency depends critically on the proposal distribution. Existing proposals are analytically designed, and their accuracy can vary substantially with the margins. We show that the ideal SIS proposal, under which every weight equals the count and the variance vanishes, is exactly the policy of a generative flow network (GFlowNet) with unit reward on every matrix that has the given margins. We therefore propose MarginFlow, a framework that turns the design of the proposal into a learning problem and amortizes it across margins by exploiting their self-similarity. Every partial matrix is itself an instance with reduced margins, so one set transformer that reads the remaining margins serves every margin. We train MarginFlow on a pool of 1904 margins and evaluate it zero-shot on 1190 held-out margins, synthetic and real, from 3×3 to 870×6. On 1187 of the 1190 margins it matches or beats the best of 31 analytically designed configurations, chosen post hoc for each margin, and its median effective sample fraction is 99.8%. On the 56 margins where that best loses more than one nat of effective sample size, MarginFlow wins every one and raises the median effective sample fraction from 10.3% to 94.1%.
Related
- Amortized ratio-estimation importance sampling and localized simulation-based calibration for intractable likelihoods
- Proximal Policy Optimization for Amortized Discrete Sampling
- Likelihood-Free Schrödinger--Föllmer Sampling for Bayesian Inference with Fixed-Proposal Reuse
- On skew-symmetric distributions and their use in Monte Carlo sampling algorithms: coordinate-free, Gibbs-style and manifold versions of the Barker proposal
- Multiple Importance Sampling for Guided Speculative Inference
BibTeX
@misc{chen2026proposal,
title = {{One Proposal for Every Margin: Zero-Shot Amortized Sequential Importance Sampling for Binary Matrices}},
author = {Ruishuo Chen and Weijia Li and Xun Wang and Yu Chen and Leheng Cai and Longbo Huang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.35514},
eprint = {2609.35514},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.35514},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - One Proposal for Every Margin: Zero-Shot Amortized Sequential Importance Sampling for Binary Matrices
AU - Ruishuo Chen
AU - Weijia Li
AU - Xun Wang
AU - Yu Chen
AU - Leheng Cai
AU - Longbo Huang
PY - 2026
DA - 2026/09/28
PB - arXiv
DO - 10.48550/arxiv.2609.35514
UR - https://arxiv.org/abs/2609.35514
AB - In ecology, psychometrics, and the analysis of social and financial networks, binary matrices are often analyzed conditional on their observed row and column sums, which restricts the problem to a finite sample space of matrices with the same margins. Two fundamental problems are to count this space and to sample uniformly from it. Sequential importance sampling (SIS) addresses both with independent weighted samples and an unbiased count estimator, but its efficiency depends critically on the proposal distribution. Existing proposals are analytically designed, and their accuracy can vary substantially with the margins. We show that the ideal SIS proposal, under which every weight equals the count and the variance vanishes, is exactly the policy of a generative flow network (GFlowNet) with unit reward on every matrix that has the given margins. We therefore propose MarginFlow, a framework that turns the design of the proposal into a learning problem and amortizes it across margins by exploiting their self-similarity. Every partial matrix is itself an instance with reduced margins, so one set transformer that reads the remaining margins serves every margin. We train MarginFlow on a pool of 1904 margins and evaluate it zero-shot on 1190 held-out margins, synthetic and real, from 3×3 to 870×6. On 1187 of the 1190 margins it matches or beats the best of 31 analytically designed configurations, chosen post hoc for each margin, and its median effective sample fraction is 99.8%. On the 56 margins where that best loses more than one nat of effective sample size, MarginFlow wins every one and raises the median effective sample fraction from 10.3% to 94.1%.
ER -