My question is, in the implementations of VLAs that store the array on the stack, do they store the size of the array somewhere at runtime?

Yes, if it is needed. Effectively, the compiler creates a variable whose name you do not know and stores the size of the array in it. (This is not specified by the C standard, but we can see the effects are equivalent: A user-declared automatic variable retains a run-time value, and that is just what is needed for the size of a variable length array.)

There are embellishments on this. If you define int A[2*n+3]; and then use A without applying sizeof to it, then, once the compiler has allocated stack space for it, it no longer needs to know the size of the array except to release the stack space. It is as if you wrote this code:

size_t SizeOfA = 2*n+3;
int A[SizeOfA];

… Some loop that uses a[i]…

foo(SizeOfA, A);

In that code, the compiler needs to keep SizeOfA at least until the call to foo, since it is passed as an argument. Similarly, if you wrote foo(sizeof A, A);, the compiler would need to keep its hidden hypothetical variable until the call to foo. But if you did not have the call to foo in that code, then optimization could discard the SizeOfA variable since it is never used. Similarly, the compiler can discard its hypothetical variable since it is never used (because it may have another way to release the stack space, per below).

If yes, where?

Likely the size of an array is treated as just one more thing the compiler has to keep track of in a routine, along with user variable, and it is subject to optimization just like anything else.

Also note that, if you have int A[2*n+3];, the compiler does not need to keep the size if it can recalculate it from n, which it can do if n does not change (or it keeps a copy). This would all be up to optimization and other software inside the compiler.

If not, how do you know at runtime how much to decrement the stack pointer once the array goes out of scope?

It is common to have a frame pointer that is a copy of the stack pointer made at the time the routine was started (or some fixed point relative to the start of the routine, such as just after doing some stack housekeeping). If we have a saved frame pointer, everything that the routine pushed onto the stack can be popped simply by copying the frame pointer to the stack pointer.

If we do not have a frame pointer, then the amount to adjust the stack pointer can be calculated from the hypothetical variable described above.

Things get more complicated if you have variable length arrays inside nested blocks that may or may not get executed, due to if statements or other control statements. You can still pop everything with a frame point, but are you going to keep everything that was allocated inside a nested block between the time the block is exited and the time the function returns? Or are you going to pop the variable length arrays when the block is exited? Do you do that by calculating space or by making copies of the stack pointer when such blocks are entered?