More noticeable as map size increases. I'm guessing that Unity just has a single array each for verts/indices for the entire navmesh that it passes to recast when a tile is rebuilt. That in itself wouldn't account for the huge jump in rebuild times for a single tile as the overall navmesh size increases. It wouldn't be good but I'm seeing huge increases that seem to be the same pattern but applied in other areas as well. Where it's calculating something for the entire navmesh area that it shouldn't be. To be clear it gets worse the smaller the tile size is. Going from 256 to 128 roughly doubles the rebuild time for a single tile on a 4k navmesh.