The answer is hard to understand until you remember that Vx and Vy are performance numbers based on excess power. The ability of an airplane to climb in still air (disregarding thermal lift or orographic lift from mountains, etc) is dependent on excess power beyond that required to sustain level flight, at a given airspeed. This means, for example that at 100 knots in level flight at 50% power, adding more power either means we go faster, or if we maintain 100 knots, we climb. Climb performance, then, is a function of excess thrust.
As you know, climb speeds such as Vx and Vy have a lot to do with angle of attack and drag. In a light airplane where we don't have an indication of angle of attack, we base our understanding of it in part on airspeed. You're familiar with the drag curve and the power required curves. You understand the differences between Vx and Vy and what they do. The only mystery, then, is why the numbers decrease with altitude.
First of all, remembering that power equals climb performance, we know there's some point in the climb where we're going to run out of power and performance. We just can't climb any more. We've reached the absolute ceiling. At this point, there's just one angle of attack at which we can maintain level flight on the power we've got...pitch up any more, and the airplane descends. Pitch down, and the airplane descends. Vx and Vy have come together. But why?
The only answer can be that power changes a we climb. The rate at which Vx and Vy come together is a function of the power available...and this depends on how we get that power to a useable state of thrust. The engine loses power as it climbs. As air density decreases, manifold pressure decreases (talking about a normally aspirated airplane here, for simplicity), and so forth. You're already familiar with that. Also as the airplane climbs and density decreases, propeller efficiency decreases (let's use a fixed pitch propeller for simplicity, here). In a typical light airplane, climbing only a few thousand feet has already decreased engine output by 25% or so...which is part of the reason that manufacturers generally recommend against leaning below three or four thousand feet...they're idiot proofing to some degree the process by asking you not to lean until you're at an altitude where there's far less chance of hurting the engine. When you've climbed just a few thousand feet and there's less power, the distance between Vx and Vy begins to decrease...with less and less power there's less and less difference between the two...until we reach a point at the absolute ceiling where the airplane can only maintain altitude at one angle of attack...there's no separation between them.
It's important to note that at the absolute ceiling when one can fly a single angle of attack to maintain altitude on one engine...one isn't going to stall...the ceiling is determined by available power...not by the airplane reaching a point where it's run out of wing or the ability to produce lift. When one is barely able to maintain altitude at the absolute ceiling, one isn't on the edge of a stall...on has simply run out of power. As an example, I've flown airplanes well above their ceiling when experimenting before, strictly using thermal and other lift...when no more engine power was available to lift the airplane any higher...the airplane still flies just fine, and will keep on climbing and flying on other forms of lift such as a mountain wave or rising air...it's just run out of engine power to make it go any higher.
You mentioned Vx staying the same and Vy decreasing. Not so. Vx increases with altitude, and Vy decreases. They don't increase and decrease at the same rate, however.
As a ballpark rule of thumb, in a light, normally aspirated, reciprocating-engine airplane, you can reduce both Vx and Vy by about one knot for each 100 lbs of aircraft weight below the max gross takeoff weight. You can do this because usually Vx and Vy are published for maximum weight at sea level...and the airplane climbs better when it's lighter, and has excess thrust available that's not needed to matain level flight...every pound or kg lighter means more available thrust, means more available climb performance, and this takes place at a different speed...about 1 knot less per 100 lbs of weight.
Vy may also be reduced about 1% for each 1,000' of density altitude. Roughed out, this still amounts to about 1 knot per thousand feet. Vx doesn't decrease, however. It increases with altitude. Of interest, you'll probably find the Vx numbers in your handbook published for a short field takeoff, which is done with flaps down...but you probably won't find the numbers published for Vx with flaps up...and Vx differs between flaps down and flaps up...just as the power to sustain level flight differs with flaps down or flaps up...and thus any excess power beyond that differs between flaps down or up.
If that data isn't available, you can make it for yourself with some experimentation. You can do that by making a series of climbs at differing airspeeds and noting the performance on your vertical speed indicator, and repeating it at increasing altitudes to see what happens.
A ballpark rule for Vx is that it increases about 1/2 percent per thousand feet of altitude increase. Whereas Vy decreases (again, normally aspirated piston powered airplane, here, with a fixed pitch prop) by 1%, Vx increases by 1/2 percent...or about 1 knot per two thousand feet of density altitude increase.
If the temperature change remains constant and linear with a climb to altitude the change in Vx and Vy with altitude also remains fairly constant...so that if you know your sea level numbers and you know your service ceiling numbers, you can interpolate fairly accurately what the Vx and Vy numbers are for all the altitudes in between.
If you change the situation by turbocharging or using a turbine engine, it becomes a little more complicated, because the way the power changes with altitude is affected, and the rates of change therefore also affected.