Static sentence encoders offer efficient multilingual inference, but their vocabularies are fixed independently of the sentence-level objective. We introduce loss-guided vocabulary discovery, a train-time procedure that uses contrastive-loss utility to identify useful adjacent token pairs, assigns each selected pair its own row, and keeps the selected pair set unchanged during continued training. In our main run, the method selects 56,071 pairs, increasing the number of embedding rows by 21.74% without changing the tokenizer or introducing contextual inference. We train the resulting encoder on 176 languages. Over three training seeds, loss-guided discovery outperforms an independently collected equal-cardinality frequency selector by 1.70±0.07, 0.12±0.05, and 0.62±0.02 points on Tatoeba, BUCC, and Flores, and the margin widens with continued training. Under matched update budgets, it also improves all 12 comparisons across four additional base-model families. The selected-pair model improves the no-pair control in all four training-resource quartiles on Tatoeba, including by 0.86 points in the lowest-resource quartile. On MTEB, our encoder outperforms the strongest competing static model by 2.92 points. Loss-guided discovery thus lets the sentence-level training signal allocate multilingual vocabulary capacity within a static encoder.