Active automata learning is a promising approach for the automated construction of system models in black-box settings. However, existing algorithms have issues scaling to large systems. Addressing this issue, we present \({L^\texttt {s}}\) , a new learning algorithm for Mealy machines. It decouples state characterization from state identification to identify transition targets more efficiently. Its backbone is a new data structure, the sparse observation table. We define constructiveness as a sufficient criterion to infer unique hypotheses from this table and develop the granularity metric. This metric naturally translates into a heuristic for establishing constructiveness efficiently. We prove the correctness of the algorithm and experimentally evaluate it with models of real applications. While asymptotic worst-case complexity is not improved over existing algorithms, our experiments indicate performance gains in practice.