Abstract: After matching treated units to controls in observational data, it is common to conduct inference by permuting treatment assignments as in a Fisher randomization test (FRT). This approach is subject to at least two weaknesses. Firstly, it does not account for differences in treatment propensities between matched individuals, which typically do not agree exactly in practice. Secondly, it does not consider whether permuted versions of treatment would have led to the selection of the same matched-pair configuration. We show that these problems can lead to substantive Type I error violations and propose solutions to both. To address propensity discrepancies, we propose covariate-adaptive randomization inference, which modifies the permutation probabilities to vary with estimated propensity score discrepancies. To address the second, we present new graph-based inference procedures for optimal pair matching with propensity scores that eliminate incompatible treatment assignments from consideration. We also show how to extend existing sensitivity analysis for unobserved confounding to these new test procedures. We demonstrate the empirical effectiveness of our new methods via simulations and a data example. This is joint work with Yaxuan Huang (UC Berkeley) and Ruoqi Yu (Univ. of Illinois Urbana-Champaign), supported by the National Science Foundation (grant #2142146) and the Hellman Family Foundation.