How to remove excess whitespace in matplotlib legend for PGF plot

Question

I'm creating a fairly small plot with matplotlib which needs to include a certain legend. However, while space is tight, for some reason matplotlib makes the legend excessively wide, adding a lot of whitespace to the right part of the legend:

Is there a way to fix this? Although I can't give all the code to reproduce this figure, here are some parts that might be relevant:

text_width_in_inches = 5.95114 # Used to scale PGF plots
very_small_font_size = 5
small_font_size = 7
medium_font_size = 9
thin_line_width = 0.75
small_marker_size = 3.75
...
def set_plot_width(fig, text_width_ratio):
    old_width, old_height = fig.get_size_inches()
    new_width = text_width_ratio*text_width_in_inches
    new_height = (new_width/old_width)*old_height
    fig.set_size_inches(new_width, new_height)
...
matplotlib.use("pgf")
matplotlib.rcParams.update({
    "pgf.texsystem": "pdflatex",
    'font.family': 'serif',
    'text.usetex': True,
    'pgf.rcfonts': False,
    'axes.labelsize': small_font_size,
    'axes.titlesize': medium_font_size,
    'xtick.labelsize': small_font_size,
    'ytick.labelsize': small_font_size,
    'legend.fontsize': small_font_size,
    'lines.linewidth': thin_line_width,
    'lines.markersize': small_marker_size,
})
...
plt.legend(fontsize=very_small_font_size)
plt.xlabel("Mode storage order")
plt.ylabel("Normalized compression factor")
plt.ylim(miny, maxy)
set_plot_width(plt.gcf(), 0.4 if len(mode_storage_orders) <= 10 else 0.6)
plt.savefig(figure_path + dataset_name.replace(" ", "-") + "-core-flattenings.pgf", bbox_inches="tight")
plt.close()

As you can see, I'm rendering the plot to a PGF file so that it can be included directly in my Latex document with matching fonts etc. However, this might be part of the problem: when I switch back to my default "TkAgg" back-end, remove a few Latex/PGF-related rcParams settings and save the plot to a PNG file, I get the following result:

which fixes the legend problem, but is not what I want of course.

Finally, I also tried messing a bit with certain legend kwargs, such as borderpad and columnspacing, but this didn't help.