We discuss the formulation of convex hulls of incidence vectors of strings in a language as systems of linear inequalities over the rationals. In particular, for a graph $(V,E)$, existing linear formulations for the minimum cut problem require $\Theta(|V||E|)$ variables and constraints and can be interpreted as a composition of $|V|-1$ polyhedra for minimum $s$-$t$ cuts in much the same way as early algorithmic approaches to finding globally minimum cuts relied on $|V|-1$ calls to a minimum $s$-$t$ cut algorithm. We present the first formulation to beat this bound, one that uses $O(|V|^2)$ variables and $O(|V|^3)$ constraints. Applications of our result include strong relaxations for the traveling salesman problem with fewer variables than previously known and a polynomial time verifiable certificate of size $n$ for the NP-complete problem of $l_1$-embeddability of a rational metric on an $n$-set (as opposed to one of size $n^2$ known previously).