Rank-Budgeted Facial Reduction for Binary SDP Layers

1. Integration point: implement a differentiable structured-discrete layer whose input is neural logits l and whose output is a soft or rounded binary vector x satisfying Ax=b. Form the Shor/RLT SDP variable Y of size n+1 and solve an SDP projection or entropy-regularized SDP during the forward pass; use implicit differentiation or unrolled differentiation through the solver. This is most relevant to exact-cardinality MoE routing, graph selection, matching relaxations, or binary feature selection. 2. Precompute the numerical rank r of A using an SVD, counting singular values larger than tau_rank=max(m,n)*eps*||A||_2. Set B=min(r,n-r). Pseudocode: initialize the SDP cone and equality constraints; for k=1,...,B, solve the current exposing-vector subproblem for a PSD dual certificate Z_k; if <Z_k,Y> is below tau_expose for all primal iterates, parameterize the current face as Y=V_k S V_k^T with V_k spanning ker(Z_k), otherwise stop; solve the reduced SDP in S and recover Y. Add a small diagonal regularizer mu I inside the reduced cone only if the solver requires strict positivity. 3. The paper supplies B; estimate rank numerically, exposing certificates, and residual tolerances empirically. Log primal residual ||Ax-b||, RLT residual ||AX-bx^T||_F, minimum eigenvalue, number of Newton iterations, and backward-gradient norm. 4. First experiment: use a 32-variable exact-k routing layer in a 2-layer MLP on synthetic constrained assignment data, comparing a standard unreduced SDP solver against rank-budgeted facial reduction at equal accuracy. Test ranks r=1,4,8,16,24. Success means fewer solver iterations or fewer failed backward passes, lower condition numbers, and unchanged assignment feasibility; a useful target is at least 1.5x faster forward/backward solves or a clear reduction in NaN/indefinite-matrix failures. Also compare against naive truncation after 1 and n rounds to verify that the rank-based cap is informative.