Appearance Space Texture Synthesis (ASTS) provides fast texture synthesis by example. Unfortunately, speed is only achieved at the cost of a long pre-processing step. This is tedious for artists and limits the input resolution. In addition, the aggressively pruned search space results in strong artifacts when synthesizing multiple textures under user guidance (Texture-By-Numbers, TBN). In this paper, we replace the $k$-coherence search step used by most modern synthesis algorithms with a new parallel, coherent random walk. We show that this drastically improves the synthesis quality with TBN, while maintaining the parallel nature, speed, and flexibility of the original ASTS runtime. Since it removes the expensive pre-computation of $k$-coherent candidates, we are able to use larger inputs, and start synthesis much faster. This is essential for artists designing high-quality exemplars.