API Gateway Timeouts from Lambda

Hello, so I have API Gateway integrated with a java lambda method, but I'm getting 504 Errors from API gateway when I modify the java method in such a way that it takes several hundred ms longer.
Lambda has no errors and is completing successfully, and only takes about a second or two to finish. My Lambda timeout is set to 300 seconds and my API Gateway timeout is set to the default 29s.
Despite that, API Gateway is almost instantly timing out as indicated by the logs.
00:13:56 Sending request to lambda
00:13:56 Execution failed due to a timeout error

Any ideas on how to fix this would be greatly appreciated. I'm sure there has to be a simple reason that I've missed so far.